About the new compiler, Part I
Marcus Denker
denker at iam.unibe.ch
Sat Jan 19 10:19:19 UTC 2008
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
|