source: project/wiki/compiler-nodes @ 21095

Last change on this file since 21095 was 21095, checked in by Mario Domenech Goulart, 10 years ago

compiler-nodes (wiki): typo and link fixes

  • Property svn:executable set to *
File size: 9.9 KB
Line 
1[[tags: internals]]
2[[toc:]]
3
4== Nodes
5
6The node tree to represent a compiled program is described here. Each
7node has 3 slots: a ''class'' (a symbol that determines what type of
8operation is represented by this node), ''parameters'' (a list of node
9attributes specific to the node's class) and the ''subnodes'' (a list
10of child nodes) of the current node. These slots can directly be
11acccessed in compiler extensions with the following procedures:
12
13  (node? X)
14  (make-node CLASS PARAMETERS SUBNODES)
15  (node-class NODE)
16  (node-parameters NODE)
17  (node-subnodes NODE)
18
19Note that these procedures are not qualified with the {{##compiler#}}
20prefix.
21
22== Core node classes
23
24These node classes are valid in the ''core'' language, the program
25tree right after macro-expansion. In the following descriptions, node
26classes are listed in the format
27
28  [node] <class-name> {<parameter1> ...} <sub-node> ...
29
30where {{ {...} }} represents the list stored in the {{parameters}} slot
31of the node. If the parameters are not used, the braces are omitted.
32Optional parts are enclosed in square backets ({{[...]}}):
33
34=== ##core#variable
35
36  [node] ##core#variable {<variable>}
37
38A global or lexical variable reference. The parameter is a symbol naming the
39variable, possibly alpha-converted (renamed).
40
41=== if
42
43  [node] if <exp> <exp> <exp>
44
45The usual {{if}} conditional, with the test, consequent and alternative parts
46as subnodes.
47
48=== quote
49
50  [node] quote {<literal>}
51
52Any literal. Unquoted literals in the program code are automatically converted
53to {{quote}} nodes.
54
55=== let
56
57  [node] let {<variable>} <exp-v> <exp>
58
59A lexical binding, always for a single variable only. Multiple bindings are
60transformed into nested {{let}} nodes (alpha-conversion will have taken care
61of re-bindings). {{<exp-v>}} is the value to which the variable is bound,
62{{<exp>}} is the body of the binding.
63
64=== ##core#lambda
65
66  [node] ##core#lambda {<id> <mode> (<variable>... [. <variable>]) <size>} <exp>
67
68A procedure. The parameter list holds the procedure id, the ''mode'' (a flag indicating
69whether this is an ''internal'' lambda, i.e. a procedure introduced via CPS conversion),
70the argument list (or signature) and the size (a simplistically computed number giving
71an estimate of a procedures size). The subnode holds the body of the procedure.
72
73=== set!
74
75  [node] set! {<variable>} <exp>
76
77An assignment. Note that {{letrec}} is transformed by the compiler into {{let}} and
78{{set!}} forms.
79
80=== ##core#undefined
81
82  [node] ##core#undefined {}
83
84An undefined value. Not {{void}}, but really ''undefined'' as in "has no value (yet)",
85but this means {{void}} in most cases (but not in all).
86
87=== ##core#global-ref
88
89  [node] ##core#global-ref {<variable>}
90
91A global variable reference. This is used internally by [[/egg/tinyclos|tinyclos]].
92
93=== ##core#primitive
94
95  [node] ##core#primitive {<name>}
96
97A primitive procedure. {{<name>}} is a string (or symbol) naming a C function
98with CPS calling convention.
99
100=== ##core#inline
101
102  [node] ##core#inline {<op>} <exp>...
103
104Calls the C expression {{<op>}} in operator position (so it may be a C function
105name, or something that can be called) with the given arguments (which are unconverted
106and passed directly to the function). The result should also be a Scheme data object.
107
108=== ##core#inline_allocate
109
110  [node] ##core#inline_allocate {<op> <words>} <exp>...
111
112Identical to {{##core#inline}}, but also adds {{<words>}} (an integer) to the number
113of words that have to be allocated in the procedure that holds this form since all data
114allocations in a single generated C function are coalesced into one allocation
115request).
116
117=== ##core#inline_ref
118
119  [node] ##core#inline_ref {<name> <type>}
120
121Reference to a C variable or rvalue of the given type (which should be a usual
122FFI foreign type specifier).
123
124=== ##core#inline_update
125
126  [node] ##core#inline_update {<name> <type>} <exp>
127
128Assignment to a C variable or lvalue.
129
130=== ##core#inline_loc_ref
131
132  [node] ##core#inline_loc_ref {<type>} <exp>
133
134A reference to a pointer (represented by {{<exp>>}} which is internally a byte-vector)
135to data of the given foreign type.
136
137=== ##core#inline_loc_update
138
139  [node] ##core#inline_loc_update {<type>} <exp> <exp>
140
141An assignment to a typed pointer value.
142
143=== ##core#call
144
145  [node] ##core#call {<safe-flag> [<debug-info>]} <exp-f> <exp>...
146
147Calls a procedure ({{<exp-f>}}) with the given arguments. The parameter
148list holds a flag (wether the operator should be checked for being a procedure)
149and some optional debugging information (which will be used in the trace
150buffer).
151
152=== ##core#callunit
153
154  [node] ##core#callunit {<unitname>} <exp>...
155
156Calls a library ''unit'', which means the library has been used through
157a {{(declare (uses ...))}} declaration. This is basically like a zero-argument
158procedure call (the arguments are not used, in fact).
159
160=== ##core#switch
161
162  [node] ##core#switch {<count>} <exp> <const1> <body1> ... <defaultbody>
163
164A different form of conditional that can be translated into C {{switch}} statement.
165{{<count>}} gives the number of cases, {{<exp>}} is the expression to test, and the subnodes
166consist of alternating pairs of constant s and "case" bodies followed by a final expression
167that is evaluated when no case matched.
168
169=== ##core#cond
170
171  [node] ##core#cond <exp> <exp> <exp>
172
173An alternative conditional that will generate code using the C {{?:}} operator.
174
175=== ##core#recurse
176
177  [node] ##core#recurse {<tail-flag>} <exp1> ...
178
179A self-recursive call to the procedure containing this node, optionally a tail call (determined
180by the tail flag).
181
182=== ##core#return
183
184  [node] ##core#return <exp>
185
186Return from the containing procedure. This is used in procedures that can be
187optimized to ''direct'' leaf routines.
188
189=== ##core#direct_call
190
191  [node] ##core#direct_call {<safe-flag> <debug-info> <call-id> <words>} <exp-f> <exp>...
192
193A "direct" call to a leaf procedure, with parameters specifying whether the call
194is safe (needs no check), debug info, the called procedure-id and the number of words
195allocated (this is needed to pre-allocate storage needed in the direct procedure).
196
197=== ##core#direct_lambda
198
199  [node] ##core#direct_lambda {<id> <mode> (<variable>... [. <variable>]) <size>} <exp>
200
201A "direct" leaf procedure. Otherwise the same as {{##core#lambda}}.
202
203== Backend node classes
204
205The following node classes are finally converted to C by the code
206generator. The compiled program is first translated into the core
207language node tree and then iteratively re-written by optimization-
208and preparation passes, which will introduce occurrences of the node
209classes described here. Note that the transformed program, when passed
210to the code-generator, may only use backend node classes, not core
211language node classes.
212
213The node classes {{if}}, {{##core#undefined}}, {{##core#inline}},
214{{##core#inline}}, {{##core#inline_allocate}}, {{##core#inline_ref}},
215{{##core#inline_update}}, {{##core#inline_loc_ref}},
216{{##core#inline_loc_update}}, {{##core#return}},
217{{##core#direct_call}} and {{##core#callunit}} are identical in their
218meaning as in the core language.
219
220Additional node classes are:
221
222=== ##core#bind
223
224  [node] ##core#bind {<count>} <exp-v>... <exp>
225
226The low-level form of {{lt}}: bind {{<count>}} temporary variables to
227{{<exp-v> ...}} and evaluate {{<exp>}} (at this stage local variables
228have no names anymore).
229
230=== ##core#closure
231
232  [node] ##core#closure {<count>} <exp>...
233
234Creates a closure with {{<count>}} slots, filled with the
235results of evaluating {{<exp>...}}.
236
237=== ##core#box
238
239  [node] ##core#box {} <exp>
240
241Creates a ''box'' (a vector of size 1) holding an assigned lexical variable.
242
243=== ##core#unbox
244
245  [node] ##core#unbox {} <exp>
246
247Extracts the value from a box.
248
249=== ##core#ref
250
251  [node] ##core#ref {<index>} <exp>
252
253Extracts a slot from a vector-like object {{<exp>}} at the given index.
254
255=== ##core#update
256
257  [node] ##core#update {<index>} <exp1> <exp2>
258
259Mutates the slot at the given index of the vector-like object {{<exp1>}}
260with the value of {{<exp2>}}.
261
262=== ##core#updatebox
263
264  [node] ##core#updatebox {} <exp1> <exp2>
265
266Mutates the value stored in the box in {{<exp1>}} with the result of {{<exp2>}}.
267
268=== ##core#update_i
269
270  [node] ##core#update_i {<index>} <exp1> <exp2>
271
272Updates a slot with an immediate value. This is faster than the normal update
273since that doesn't require remembering the mutation to make the generational
274garbage collector work.
275
276=== ##core#updatebox_i
277
278  [node] ##core#updatebox_i {} <exp1> <exp2>
279
280Update a box with an immediate value.
281
282=== ##core#call
283
284  [node] ##core#call {<safe-flag> [<debug-info> [<call-id> <customizable-flag>]]} <exp-f> <exp>...
285
286Call a procedure. This is roughly equivalent to the core language {{##core#call}}, but holds
287additional information obtained from optimization passes.
288
289=== ##core#local
290
291  [node] ##core#local {<index>}
292
293Access the local (temporary) variable at the given index.
294
295=== ##core#setlocal
296
297  [node] ##core#setlocal {<index>} <exp>
298
299Update a local variable.
300
301=== ##core#global
302
303  [node] ##core#global {<literal> <safe-flag> <block-mode> [<name>]}
304
305Access a global variable. Globals are implemented as slots in symbols
306(similar to classical Lisp dialects). Additional flags in the parameter list
307are used for generating faster code by omitting checks.
308
309=== ##core#setglobal
310
311  [node] ##core#setglobal {<literal> <block-mode>} <exp>
312
313Update a global variable.
314
315=== ##core#setglobal_i
316
317  [node] ##core#setglobal_i {<literal> <block-mode>} <exp>
318
319Update a global variable with an immediate value.
320
321=== ##core#literal
322
323  [node] ##core#literal {<literal>}
324
325Access a literal (similar to {{quote}} nodes).
326
327=== ##core#immediate
328
329  [node] ##core#immediate {<type> [<literal>]}]     
330
331Return an immediate literal of the given type (which can be
332one of the symbols {{bool}}, {{fix}}, {{nil}} and {{char}}).
333
334=== ##core#proc
335
336  [node] ##core#proc {<name> [<non-internal>]}
337
338Represents the code-pointer of a procedure (the actual closure
339is created by {{##core#closure}}).
340
341=== ##core#recurse
342
343  [node] ##core#recurse {<tail-flag> <call-id>} <exp1> ...
344
345The same as in the core language, but with the id of the called procedure.
346
Note: See TracBrowser for help on using the repository browser.