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

Last change on this file since 36678 was 36678, checked in by megane, 7 months ago

Add page for scrutinizer

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