About the new compiler, Part I

Joshua Gargus 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
> 	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