About the new compiler, Part I

nicolas cellier ncellier at ifrance.com
Sat Jan 19 23:25:57 UTC 2008

OldCompiler also has a parseTree, no change at this level.
The visitor pattern versus direct tree recursion at worst double method 
stack, not a drama because less parameters should be passed (stored in 
visitor inst vars). IMO visitor leads to better code (maintainable, 
Anyway you follow the steps of ParcPlace there (they switched long time 
ago, in Objectworks version maybe).

OldCompiler code to resolve variable scoping is:
- hard to understand
- bugged
	* http://bugs.squeak.org/view.php?id=6704
	* http://bugs.squeak.org/view.php?id=6831
	* http://bugs.squeak.org/view.php?id=6720
	* http://bugs.squeak.org/view.php?id=3448
Anyone to deny a clear relationship?
Many thanks for rewriting this part cleanly!

NewCompiler has one step more than VW: the abstract bytecode sequence 
produced by IRBuilder.
VW directly encodes byteCodes on a stream, no reification at this level.

This steps might stress ObjectMemory accumulating objetcs not reclaimed 
immediately (exactly like the parse tree does) and adds one more walk. 
For these reasons I guess it should be responsible for roughly a factor 
2 (Sure Marcus has the tallies).

If this is true, and speed really matters, a rewrite is possible here 
and would give another tradeoff. But does speed matters that much?

It seems that Marcus has good applications for this reification as 
explained in part II, and implemented really easily compared to pure 
stream processing like VW::InstructionClient.

So a big thank you to Marcus and his crew, I see much more progress here 
than regression.


stephane ducasse a écrit :
> 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
>     newcompiler
>     compiler
> in terms of error hanlding, decompilation, block closures support.
> Stef
> 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 architecture.
>> 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 Generator
>>   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 
>> grammer)
>>     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].
>>         aMessageNode isInlineAndOr ifTrue: [^ self emitAndOrNode: 
>> aMessageNode].
>>         aMessageNode isInlineWhile ifTrue: [^ self emitWhileNode: 
>> aMessageNode].
>>         aMessageNode isInlineToDo ifTrue: [^ self emitToDoNode: 
>> aMessageNode].
>>         aMessageNode isInlineCase ifTrue: [^ self emitCaseNode: 
>> aMessageNode].
>>         ^ 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';
>>             returnTop;
>>             jumpAheadTarget: #else;
>>             pushLiteral: 'no';
>>             returnTop;
>>             ir.
>>         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:
>> http://www.iam.unibe.ch/~denker/talks/07SCGSmalltalk/11Bytecode.pdf
>>     Marcus
>> -- 
>> Marcus Denker  --  denker at iam.unibe.ch
>> http://www.iam.unibe.ch/~denker

More information about the Squeak-dev mailing list