About the new compiler, Part I

stephane ducasse stephane.ducasse at free.fr
Sat Jan 19 10:55:30 UTC 2008

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