source: project/wiki/chicken-internal-structure @ 14110

Last change on this file since 14110 was 14110, checked in by sjamaan, 12 years ago

Fix most direct links to the manual sections

File size: 26.0 KB
2[[tags: internals]]
4== A guide to the CHICKEN compiler
6''This is insane. What we clearly want to do is not exactly clear, and is rooted in NCOMPLR.''[1]
8=== Preliminaries
10==== Files
12The compiler is made up from the following files:
14; {{chicken.scm}} : command-line parsing
15; {{batch-driver.scm}} : option processing and invocation of the compiler passes
16; {{compiler.scm}} : basic passes of translation
17; {{optimizer.scm}} : high-level optimization
18; {{support.scm}} : various support routines
19; {{c-backend.scm}} : C-code generator
20; {{c-platform.scm}} : tables and rewrite rules
21; {{tweaks.scm}} : some performance hacks to speed up the compiler
22; {{banner.scm}} : the banner shown by {{-version}}
23; {{private-namespace.scm}} : some support code that defines a macro ({{private}}) to hide toplevel identifiers (very ugly)
24; {{chicken-more-macros.scm}} : non-standard low-level macro definitions
25; {{chicken-ffi-macros.scm}} : low-level macros for interfacing to foreign code
27==== The "compiler" namespace
29At the start of most compiler files you'll find a funny list of
30symbols of the form {{ (private compiler ...) }}. This uses an
31internal hook to rename the listed toplevel identifiers by prefixing
32them with {{##compiler#}} (these are called ''qualified'' symbols). It
33is a crude way to separate the toplevel definitions of the compiler
34from user code and avoid one to stumble over the other.
36=== Command-line parsing (chicken.scm)
38In {{chicken.scm}} command-line arguments are collected and translated
39into ''canonical'' form by removing the hyphen and filtering run-time
40options (those starting with {{-:...}}). Also any options given in the
41environment variable {{CHICKEN_OPTIONS}} are added and
42{{-optimize-level}} is expanded into distinct, more specialized
43options. What remains is a list of symbols wth optional arguments
44which is then passed to {{compile-source-file}} in
47Note: the processing of command-line parameters can be customized
48by setting the parameter {{user-options-pass}} in the compilation
51=== The compiler driver (batch-driver.scm)
53{{compile-source-file}} initializes global variables used by the
54compiler, default initialization- and termination-code that is to be
55added to the user-supplied source code. All command-line options are
56now processed and are used to set global and local variables that
57control the compilation process. {{compile-source-file}} contains many
58local procedures that are used for printing debugging- and progress
59output, or help processing complex option arguments.  Also, the
60hook-procedure ({{infohook}}) for collecting line-number information
61is defined here.
63Now, compiler extensions are loaded, features are registered and extra
64source code fragments (the ones mentioned above, those that are stored
65in {{postponed-initforms}} and the source-code equivalents of the
66{{-extension}} and {{-require-extension}} options.
68More option processing follows. If profiling is enabled, extra source
69code is prepended to the compiler-generated code ({{initforms}}) that
70initialize the profiling library.
72Next, the actual source file to be compiled is read in and code
73supplied via prelude, postlude, prologue and epilogue options is
74added. Reading in files uses the above mentioned {{infohook}} to
75fill the line-number database.
77The {{user-preprocessor-pass}} is invoked on the source forms.
79Now the source code is ''canonicalized'' ({{canonicalized-expression}}
80in {{compiler.scm}}), i.e. macro-expanded. After the canonicalization
81code for setting hidden variables for complex, immutable literals,
82code for invoking used units and code for collecting
83profile-information is added. So called ''compressed'' literals are
84expanded into code that reads them from a string literal (that simply
85contains the text-representation of the literal) and finally some
86cleanup-code is added.
88The secondary line-number data base ({{line-number-database-2}}) is
89now stored in {{##sys#line-number-database}} to make subsequent
90searches use the updated table (see below for more information about
93If {{-check-syntax}} was given, the compiler terminates
94now. Otherwise, the {{user-pass}} is now applied to all toplevel
97The canonicalized source expressions together with all compiler-
98supplied code is now transformed into a ''node-graph'', an abstract
99syntax tree made from record structures. {{user-pass-2}} has a chance
100to run, if it was supplied, to perform some sort of pre-analysis
101on the code. Here the first invocation of {{analyze-expression}} in
102{{compiler.scm}} may happen.
104If lambda-lifting has been enabled, it is performed now, after doing
105another round of {{analyze-expression}} ({{perform-lambda-lifting!}}
106in {{optimizer.scm}}).
108Note: Since the analyzer may behave differently, depending on whether
109this is the first or a subsequent analysis, the global variable
110{{first-analysis}} is set to false in the preceding two optional
111analysis phases. The first analysis pass is slightly special and
112collects extra information that would be useless in the mentioned
115Some global tables are set to {{#f}} to reduce the amount of
116heap-space used. Then any toplevel assignments that precede any
117side-effecting expressions are collected and marked as being always
118bound (no bound-checks are necessary, since they are guaranteed to be
119bound) ({{scan-toplevel-assignments}} in {{optimizer.scm}}). Now CPS
120conversion takes place ({{perform-cps-conversion}}).
122Here the fundamental compilation process starts: a loop performs first
123an analysis pass ({{analyze-expression}}), checking imports (enabled
124by {{-check-imports}}) if this is the first loop iteration, and then
125an optimization pass by calling {{perform-high-level-optimizations}}.
126If the latter returns true as its second result, then an optimization
127was triggered and the loop continues. If no optimization was triggered,
128and inline-substitutions (rewritings of primitive operations) have
129been performed yet, the enable inline-substitutions for subsequent
130optimization passes and the analysis-optimization loop continues.
131If {{-optimize-leaf-routines}} was given it is done now, preceded
132by yet another analysis pass ({{transform-direct-lambdas!}})
133and the loop continues once more. All these passes build up a new
134node tree or mutate the existing one.
136After the optimization passes, closure conversion is done
137({{perform-closure-conversion}}). The {{user-post-analyis-pass}}
138may run now, if supplied. If {{-analyze-only}} was given, the
139compiler terminates now.
141''Preparation'' takes place, which prepares the optimized and closure
142converted node tree for code-generation
143({{prepare-for-code-generation}}). {{generate-code}} in
144{{c-backend.scm}} is invoked now to emit the C code for the Scheme
145source that was compiled.
147Cleanup stuff is done, if necessary ({{compiler-cleanup-hook}} in
150=== The compiler core (compiler.scm)
152Nearly all global variables and constants used in the compiler are
153defined here. Some of these are set through the command line (in
154{{batch-driver.scm}}), but most are initialized at toplevel in this
155file. The procedure {{initialize-compiler}} initializes global
156tables and vectors to their default values.
158==== Canonicalization
160{{canonicalize-expression}} is the first compiler pass: it first
161invokes the hook {{##sys#compiler-toplevel-macroexpand-hook}} on each
162toplevel expression - this is the main hook used for external macro
163expanders like {{syntax-case}} to expand toplevel forms
164completely. Before that any "pending canonicalizations" (simply a list
165of toplevel forms) are prepended to the proper source code, needed for
166extensions and compile time code that does funky stuff. Now each
167toplevel form is recursively processed, and (low-level) macros are
168expanded. Non-global identifiers are alpha-converted (renamed) and
169special forms are specially handled.  Another notable thing is that
170the line-number database is updated here - the reader is invoked in a
171special way by the compiler to record the line-numbers of each list
172that begins with a symbol. After macro-expansion of a local form, each
173symbol-prefixed list is re-recorded with the line-number of the
174original form. Inline functions and constant are resolved.
175Foreign-function special forms are processed here too and store C code
176to be included by the backend and global information of foreign
177function wrappers that are to be generated later.
179{{process-declaration}} parses {{declare}} forms and sets various
180global variables to reflect those declarations.
182==== Macroexpansion
184Usually, macros are expanded while walking the source s-expressions
185during canonicalization. Every list expression that begins with a
186symbol results in a lookup of the symbol in {{##sys#macro-environment}}
187(a low-level hash table, see below). This hash-table maps symbols
188to single-argument procedures that (if the name matches) will be called
189with the complete form. The result of this ''expander'' procedure
190will be further processed (and possibly expanded again, if the
191result of the first expansion is another macro invocation).
193As mentioned above, before a top-level form is canonicalized,
194{{##sys#compiler-toplevel-macroexpand-hook}} is called for the
195complete toplevel form.
197Line number information is stored in the ''line number database'', yet
198another low-level hash table that maps symbols to a association list
199of s-expressions and line-numbers: reading a source expression is done
200in a special mode, where the reader is invoked with an ''infohook'', a
201procedure that can do special processing for particular forms. The
202internal procedure {{infohoo}} in {{batch-driver.scm}} fills the
203line-number database with s-expression and the current line number.
204Later stages (for example when errors are detected during canonicalization)
205will try to find line-number information to give more meaningful error messages.
206When a form is macroexpanded during canonicalization (but not in
207{{##sys#compiler-toplevel-macroexpand-hook}}), the new form is re-entered
208into the line-number database (mapped to the same line-number as the
209previous, unexpanded expression) (see {{update-line-number-database!}}
210in {{support.scm}}).
212Note that this line-number mapping is only partially useful - complex
213macro-forms often are heavily transformed, so line-number information
214gets blurry after several expansions.
216==== CPS conversion
218{{perform-cps-conversion}} transforms the canonicalized code (which
219has already been converted into a node tree) into continuation passing
220style: continuations are made explicit by adding an additional
221argument to each procedure and procedure invocation and by inserting
222additional {{lambda}} nodes. The algorithm is relatively naive and
223taken more or less directly from Appel[2].
225==== Analysis
227{{analyze-expression}} does a static analysis on the node tree of the
228complete program. The information gained by recursively traversing the
229tree is stored in the ''analysis database'', a hash-table that maps
230symbols (identifiers and {{lambda}}-ids) to a property list. Also,
231various global statistics are kept up to date (total program size for
232example). See [[compiler-database|here]] for a description of the
233properties. The exact meaning of the properties is subtle and the
234dependency among them subtle. After walking the node tree, the
235analysis database (called ''db'' from now on) is iterated over and the
236information collected during the walking refined by setting additional
237properties. The information available here is also used to trigger
238various warning messages. Most information here will control
239optimizations done at later stages. Note that this analysis pass will
240be performed many times.
242==== Closure conversion
244{{perform-closure-conversion}} does another general program
245transformation: closures are made explicit, that is, free-variable
246information is gathered and references to free non-global variables
247are converted into data-structure operations. The free variables which
248are refered in closed over procedures are created in explicitly
249managed data structures (closure records). This pass does both
250decorate entries in the db with additional information and rewrites
251the program.  Closure conversion involves ''boxing'': free variables
252that are assigned to are turned into 1-element data structures to
253allow sharing (strictly speaking this is only necessary for closures
254that are shared, but the analysis is not clever enough to figure this
255out). Boxed closure variables are referenced and assigned differently
256and the code is modified to invoke special compiler primitives to do
257these operations. Again, the algorithm to gather free-variable
258information is non-linear and pretty dumb.
260==== Preparation
262{{prepare-for-code-generation}} walks once again the node tree and
263performs various re-writings: variable references are turned into
264low-level forms with different forms for the different types of
265variable access (global or local, lexical variable access has by now
266already been converted into closure record operations). Allocation
267information is collected as well in this pass, which is quite
268important since the generated code must keep track of allocation
269counts to clean up the stack once it is exhausted. The allocation is
270counted in words and represents a rough estimate of the storage
271allocated in a procedure or whether a procedure allocated at all (this
272may trigger additional optimizations). This pass builds the list of
273procedures which are later turned into actual code - the whole program
274is just a list of functions with the toplevel forms outside of
275procedures put into a special "toplevel" procedure. The procedure list
276contains so-called ''lambda-literals'', each holding quite a lot of
277information used by the backend. Also, the number of temporary
278variables needed by a generated C function is counted here and
279literals are specially marked.
281=== The Optimizer (optimizer.scm)
283This file contains the code to perform some high-level optimizations
284like inlining and rewriting complex forms into simpler or more low-level
287==== Top-level assignment simplification
289{{scan-toplevel-assignments}}: All toplevel variables that are assigned
290before any side-effecting code is executed can be considered "safe" and
291will never need to be checked for being bound.
293==== High-level-optimization
295{{perform-high-level-optimizations}} does the following optimizations:
297Optimize tail calls by replacing trivial continuation-procedures
298that only call their own continuation.
300Perform beta-contraction (inline procedures called only once). This quite
301important since it removes many "administrative" continuation procedures
302introduced during CPS conversion.
304Remove empty {{let}} nodes.
306Evaluate constant expressions, i.e. do ''constant folding''. This
307constant folding is quite general by calling {{eval}} on a form that
308contains only literals and known constant identifiers. Errors during
309evaluation are caught and trigger a compilation warning (and disable
310the constant folding by just compiling the expression as it is).
312Substitute variables bound to constants with their value.
314Remove variable-bindings which are never used (and which are not bound
315to side-effecting expressions).
317Perform simple copy-propagation by replacing references to variables
318that are bound to other variables with the other one, in some cases.
320Remove assignments to unused variables if the assigned value is free
321of side-effects and the variable is not global.
323Remove unused formal parameters from known functions and change all
324call-sites accordingly.
326Rewrite calls to standard bindings into more efficient forms
327("Simplification") by consulting the ''rewrite-table'', a table
328of standard and primitive system procedures.
330Rewrite calls to known non-escaping procedures (procedures that are
331called but not returned from a function or assigned to lexical or
332global variables) with rest parameter to cons up the rest-list at
333the call-site, also: change procedure's lambda-list. This simplifies
334the processing and may trigger further optimizations (for example
335to remove the rest-parameter altogether if it is never used).
337Remove calls to procedures that are declared as being "constant"
338(having no side effects), if their results are never used.
340Perform general inlining (beta-reduction) if the called procedure
341is known (refers directly to a {{lambda}} or to a variable that
342has a known value) and "simple" (only does certain inexpensive
343operations and is not bigger than a certain threshold).
345This procedure also invokes another optimization sub-pass called
346''pre-optimization'' that simplifies {{if}} expressions that have
347certain known procedueres as their first argument.
349==== Simplification
351{{register-simplification}} registers simplification-rules for certain
352program nodes, namely those for procedure call ({{##core#call}}) and
353binding ({{let}}). The call simplification in turn consults the
354''substitution-table'' which maps known library functions to simpler
355forms (or procedures testing for particular properties of the
356arguments to the known procedure). The {{let}} optimizations performs
357some more optimizations related to forms which are not directly
358connected to {{let}} but appear in such expressions:
360Chained {{if}} expressions that do {{eq?}} comparisons on literlas are
361re-written to an internal ''switch'' form (that can later be turned
362into a real C {{switch}}). Note that the type of literal may an
363optimization of calls to {{eqv?}} into {{eq?}} and since {{case}}
364constructs expand into chained {{if}} forms, {{case}} with simple,
365immediate literals can often be compiled to C {{switch}} forms.
367Certain nested {{let}} forms that are the result of {{letrec}}
368expansions are simplified.
370Also, {{if}} nodes are sometimes optimmized to an internal
371conditional operator that maps to C's {{?:}} operator.
373==== "letrec" optimization
375{{reorganize-recursive-bindings}} performs a dependency analysis
376of {{letrec}} forms (actually the code that is the result of
377their expansion) and re-orders the bindings if the meaning is
378preserved to reduce interdependency (and thus reduce the number
379of assignments that are needed).
381==== The substitution table
383In {{simplify-named-call}} the information obtained from the
384substitution table (built up using {{rewrite}}) is used to run a set
385of hardcoded optimization rules with variable parameters, so called
386''substitution classes''. There are classes for many situations,
387like replacing a procedure call with a primitive operation, or folding
388multi-argument calls into nested two-argument calls. The classes are
391==== Direct lambda transformation
393{{transform-direct-lambdas!}} processes the node tree and walks
394lambdas that meet the following constraints: a) the procedure is only
395''external'' (has no CPS redexes), b) all calls are either to the
396direct continuation or (tail-) recursive calls, c) no allocation takes
397place an d no rest parameter is used, d) the procedure has a known
398''container'' (a named and known procedure) and all it's call-sites
399are known. These procedures are turned into ''direct'' lambdas:
400lambdas that do not need to be CPS converted. A back-transformation
401into direct style is performed here which generates faster code for
402simple expressions. This includes re-writing all call-sites since the
403calling conventions are differently for direct procedures.
405==== Lambda lifting
407{{perform-lambda-lifting!}} does so called ''lambda lifting'', which
408means "lifting" local procedures that do not refer to any surrrounding
409lexical variables to top-level. If all call sites are known and the
410free variables are not assigned, then free variables can actually be
411passeds as extra arguments. The algorithm used here is currently quite
412conservative and is not really worth all the trouble we go through.
413It works like this:
415The set of possible liftable lambdas is generated out of stored
416variables in the db that refer to known procedures, together with a
417name->lambda map. Next a call-graph is generated from the set of
418liftable lambdas, also free variable information is stored in the call
419graph. Liftables that have free variables that are assigned to (and
420which itself are not refering to liftables) or which have more than a
421certain number of arguments are eliminated. Accessible variables for
422each liftable are collected into yet another a-list (map). Liftables
423that have unknown call-sites (call sites that itself are not contained
424in "known" lambdas) are eliminated, if the call-sites do not have
425access to all free variables of the liftable. Next liftables that call
426other eliminated liftables are eliminated. The latter process is
427performed iteratively until no more liftables can be eliminated.
428Extra arguments (former free variables) are now computed and all
429call-sites are updated accordingly. Then the remaining liftables
430are moved to toplevel (by modifying the program node tree).
432=== Support routines (support.scm)
434This file contains a multitude of helper procedures that process the db
435or node trees or s-expression trees.
437=== C generation (c-backend.scm)
439Here C code is generated from the optimized and prepared node tree,
440given in the list of lambda literals and decorated with all sorts of
441information to ease this process. {{generate-code}} does most of the
442work by once again walking the body (node-tree) of each lambda-literal
443and generating one or more C functions from the code. The previous
444passes have transformed the code into a relatively low-level form
445which makes the code generation quite straightforward, even if
446tedious. Complication arise only due to specific optimizations - here
447the introduction of more backend-specific special forms would have
448helped. Generation of code is split into sections, for code,
449trampolines, declarations, function prototypes, code included
450verbatim, prototypes for callbacks (externals) and the ''ptable''
451which maps function id's to code-pointers (used for
454The toplevel lambda is treated specially, as it must create all
455non-immediate literal data and define global variables (which are
456first class in CHICKEN).
458The second job is generating the stubs and wrappers for foreign
459procedures, which can get quite involved as argument-translation form
460Scheme to C and back is partially done here (whatever is done on the C
461level - procedures in {{support.scm}} add yet another layer of
462transformation on the Scheme level).
464=== C-specific parameters and substitution rules (c-platform.scm)
466This file contains a bunch of constants and parameter values for various
467uses, for example a list of valid command-line options and the names
468of builtin procedures that have specific properties that can be used
469during optimization. In addition, the rewrite-rules for substitution
470(rewriting calls to known standard and non-standard library procedures
471to simpler or more efficient forms) are defined here, by invoking
472{{rewrite}} with the substitution class and class-specific parameters
473(the number of required arguments, is the rewriting only valid in
474unsafe mode, etc.).
476The name of the file is somewhat misleading, as it was once intended
477to put all C-backend specific things into one file to ease the porting
478of the compiler to other backends. Since then all sorts of global
479parameters have moved in here.
481=== Other Files
483==== tweaks.scm
485This file contains inline-definitions for node-access operations to
486speed up the frequent use of taking apart thhe node tree.
488==== version.scm
490The current version is contained here as a constant definition.
492==== banner.scm
494The banner shown when the {{-version}} option is given and the
495copyright notice, also as constants.
497==== chicken-more-macros.scm
499All non-standard macros are defined in this file.
501==== chicken-ffi-macros.scm
503All macros for interfacing to foreign code. The interpreter doesn't
504need FFI macros, so these are put into a separate file (instead of
505merging them into {{chicken-more-macros.scm}}). These files are
506included in the compiler and {{run-time-macros}} is declared, so the
507expanders are compiled into the executable.
509=== The analysis database
511During analysis a database is filled with information about global and
512local variables. The database is passed from one compiler pass to the
513next and completely rebuilt during each optimization iteration (and a
514few times more). The internal format is that of a hash table (a
515low-level hash table specialized for symbols), which is accessible
516using the primitives {{##sys#hash-table-ref}},
517{{##sys#hash-table-set}} and {{##sys#hash-table-for-each}}. In this
518hash table symbols are mapped to association lists that themselves map
519property indicators (symbols) to values of various types.  The
520compiler options {{-debug 0}}, {{-debug 4}} and {{-debug 8}} show the
521most interesting entries in the db at various points in the
522compilation process, in a compressed format.  See
523{{display-analysis-database}} in {{support.scm}} for more details.
525=== The node tree
527During analysis and optimization, the program is represented as
528an abstract syntax tree consisting of {{node}} records
529(see {{support.scm}}). Note that the accessors for node slots
530are not qualified with a {{##compiler#}} prefix (originally for
531making it more convenient for user passes, but in the end probably
532a mistake, since it is easy for compiler-extensions or code
533loaded at compile-time to overwrite these but since the accessors
534are inlined ({{tweaks.scm}}), this is a minor problem).
535Each node has three slots: the ''class'' (a symbol like {{if}},
536{{set!}} or {{lambda}}), the ''parameters'' (a list of arbitrary
537values, holding parameters that are specific to a node's class)
538and the ''subnodes'', a list of nodes that hold nested program
539fragments (for example the body of a {{lambda}} or an application).
541=== User passes
543There are some parameters that can be filled with user-defined
544procedures to customize the compilation process. All of these
545are accessed unqualified (no {{##compiler#}} prefix). See
546the [[/manual/Using the compiler|user's manual]] for more information.
548=== Hacking
550Use the {{-extend}} compiler option to load compiled or interpreted
551extensions (or re-definitions) into the compiler - this is much more
552convenient than recompiling the compiler all the time.
554You should also take a look at the [[/egg/peep|peep]] extension: it allows
555you to interactively explore the compiler database and the node tree
556of the compiled program.
558=== References
560[1] "The MULTICS MacLisp Compiler - the Basic Hackery", Bernard Greenberg
562[2] "Compiling with Continuations", Andrew Appel
Note: See TracBrowser for help on using the repository browser.