About the new compiler, Part I
schwa at fastmail.us
Sat Jan 19 11:06:22 UTC 2008
Is SmaCC the major bottleneck, or is it tree traversal? If scanning/
parsing is the slowest part, perhaps it is worth evaluating Alex
Warth's OMeta as a potential replacement (http://www.cs.ucla.edu/~awarth/ometa/
Thanks for the write-up about the new compiler, I'm sure that many
others found it as informative as I did. I'm looking forward to Part
On Jan 19, 2008, at 2:55 AM, stephane ducasse wrote:
> Hi marcus
> Thanks for the information. I have the impression that you stressed
> too much the speed of the new compiler.
> I imagine that it has the same architecture as the one of VW.
> I know that you use it a lot and that reflectivity is completely
> based on it and working great.
> Now what are the next steps?
> The decompiler is working/error handling.
> Can we use it for Squeak...
> So could you let us know the status
> in terms of error hanlding, decompilation, block closures support.
> On Jan 19, 2008, at 11:19 AM, Marcus Denker wrote:
>> Part I: Compiling is slower, so it's bad
>> This part will not talk about closures at all, just about the
>> overall system archicture of the compiler.
>> I will write with Math something about Closures, their design and
>> performance later.
>> Before I go into the details, I think I need to clearify one thing:
>> from the start, I always saw Squeak in terms
>> of it's possibilities, never as "what it is now". I think all what
>> follows comes from that point of view.
>> If you see Squeak an artifact that should never be changed, then
>> you won't like any of the arguments that
>> follow. But I am truly convinced that the greatness of Squeak never
>> was the artifact, it was always the possibility
>> it promised.
>> So.The Compiler is slower to compile code (factor ca. 4). But then,
>> this is not that of a problem. Most people
>> will now think about the slowness of loading code with MC, but that
>> has multiple causes, the compiler is not
>> the slowest thing here... (in 3.9, we managed to speed up code
>> loading with MC by a factor of two just by caching
>> the class category in the "category" variable of the class objec).
>> Another "problem" of the NewCompiler is that it has far more
>> classes then the old one. Horrible for some people,
>> but interestingly, this makes it far easier to understand than the
>> old one...
>> So, Slower and More Classes. What do we get for that? Of course we
>> need some payout. One is that the NewCompiler
>> is *far* easier to understand. I can explain it to a student in
>> half an hour, and the student can hack it.
>> Slower. The Slowness is caused by two things: 1) Use of SmaCC for
>> parsing 2) multi-pass visitor based architecture.
>> Before explaining (with examples) why both are indeed very nice to
>> have, I will in this Part I just do a short overview of the
>> 1) Scanning/Parsing. This is wher the text is analyzed and a tree-
>> structure (AST) is build up. The NewCompiler does not
>> implement the Scanner/Parser "by hand", but instead it uses a
>> Parser-Generator. This is an application that takes a
>> description of the Grammar of the language in a fairly
>> standardized form (BNF). Then this is compiled using the Parser
>> to build the Scanner/Parser classes.
>> The nice thing about this are three things:
>> 1) easier to understand and modify (grammar is formulated as a
>> 2) less bugs, as the grammar is transformed automatically. This is
>> not that important for a simple language is Smalltalk.
>> 3) Easy to modify, Easy to add a slightly changed / extended
>> Smalltalk-like language. (We see examples for that later)
>> 2) The AST (Abstract Syntax Tree).
>> This encodes the syntax as a tree. For a compiler, a very simple
>> AST is mostly enough. For the NewCompiler, the AST of
>> the Refactoring Browser was used instead. This is an overkill for
>> a compiler, but it has some cool aspects:
>> 1) One AST for the sytem. No duplicated code between the RB and
>> the Compiler. Less bugs.
>> 2) the RB can use the Parser of the Compiler. No problem with
>> differences, less duplicated code.
>> The nice thing about the RB AST are two things: Visitors and
>> Transformations. Visitors are used a lot in the NewCompiler.
>> 3) Now we have the AST. The AST does not encode any semantics yet,
>> e.g. meaning of variables. We know that there is
>> Variable "a", but is it a definition or use? Are variables
>> shadowing each other?
>> This we need to check and add information to all variables. For
>> this, we have a Visitor that walks over the AST,
>> grows a scope-chain for each block entered, records variable
>> definitions, annotated variable uses with the definition
>> that it referes to.
>> 4) The annotated AST now can be used to generate Code. The
>> NewCompiler uses a very nice small "Squeak Assembler" to emit
>> the code. The class for Code Generation is ASTTranslator. Again a
>> visitor, walks over the tree and calls IRBuilder to
>> emit code.
>> Here in ASTTranslator the magic happens for the inlining of if/and/
>> while and so on:
>> acceptMessageNode: aMessageNode
>> aMessageNode isInlineIf ifTrue: [^ self emitIfNode: aMessageNode].
>> aMessageNode isInlineIfNil ifTrue: [^ self emitIfNilNode:
>> aMessageNode isInlineAndOr ifTrue: [^ self emitAndOrNode:
>> aMessageNode isInlineWhile ifTrue: [^ self emitWhileNode:
>> aMessageNode isInlineToDo ifTrue: [^ self emitToDoNode:
>> aMessageNode isInlineCase ifTrue: [^ self emitCaseNode:
>> ^ self emitMessageNode: aMessageNode
>> Uncomment the line with "isInlineIfNil" --> no compiler generates
>> normal message send for ifNil:. Easy.
>> 5) The IRBuilder. A symblic assembler for Squeak Bytecode. Here is
>> an example of
>> a method that compared the first iVar with the argument and
>> returns yes or no
>> ir := RBuilder new
>> numRargs: 2;
>> addTemps: #(self a); "rcvr, arg"
>> pushTemp: #self;
>> pushInstVar: 1;
>> pushTemp: #a;
>> send: #=;
>> jumpAheadTo: #else if: false;
>> pushLiteral: 'yes';
>> jumpAheadTarget: #else;
>> pushLiteral: 'no';
>> we can run this method likes this:
>> ir compiledMethod valueWithReceiver: (5 at 4) arguments: #(5)
>> As the "ir" suggests, this bytecode assembler does not directly
>> generate bytecode,
>> but it builds up an Intermediate Representation instead. This is
>> nice, as it allows
>> the backend to be changed quite easily, so changeing the bytecode
>> encoding is easy
>> with this kind of architecture. The other thing is that on the IR,
>> we can do transformation,
>> too. (example later).
>> The IRBuilder can be used to implement compiler for other
>> languages, it's actually very simple
>> to do: walk the AST of your language, call method on the
>> IRBuilder. (Example later).
>> 6) ByteCodeBuilder now is called by the IRBuilder to emit bytecode
>> and build a compiledMethod object.
>> This is the only class that encodes the actual bytecode set used.
>> So, comparing that to the old compiler, it's actually amazing that
>> this is just slower by a factor of 4. It's not
>> a black box compiler, it's a "Compiler Framework" that can be used
>> to experiment. Building yout own compiler
>> is simplified a lot with this framwork.
>> Part II will show some examples for how we used this compiler
>> framework in the past. I will try to write that
>> later today.
>> There are some slides that explain all this in some more detail:
>> Marcus Denker -- denker at iam.unibe.ch
More information about the Squeak-dev