Debian Codegraph @

src/compile-5.scm

raw
1 ;;;
2 ;;; compile-5.scm - The compiler: Pass 5
3 ;;;
4 ;;; Copyright (c) 2004-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;;===============================================================
35 ;; Pass 5. Code generation
36 ;;
37
38 ;; This pass passes down a runtime environment, renv. It is
39 ;; a nested list of lvars, and used to generate LREF/LSET instructions.
40 ;;
41 ;; The context, ctx, is either one of the following symbols.
42 ;;
43 ;; normal/bottom : the FORM is evaluated in the context that the
44 ;; stack has no pending arguments (i.e. a continuation
45 ;; frame is just pushed).
46 ;; normal/top : the FORM is evaluated, while there are pending
47 ;; arguments in the stack top. Such premature argument frame
48 ;; should be protected if VM calls something that may
49 ;; capture the continuation.
50 ;; stmt/bottom : Like normal/bottom, but the result of FORM won't
51 ;; be used.
52 ;; stmt/top : Like normal/top, but the result of FORM won't be used.
53 ;; tail : FORM is evaluated in the tail context. It is always
54 ;; bottom.
55 ;;
56 ;; Each IForm node handler generates the code by side-effects. Besides
57 ;; the code generation, each handler returns the maximum stack depth.
58 ;;
59 ;; The return value of pass5 entry is a <compiled-code>.
60 ;; The pass5 main entry may be called recursively from $LAMBDA node;
61 ;; the CLOSURE instruction takes <compiled-code> of the body of the lambda
62 ;; as an operand.
63
64 ;; predicates
65 (define-inline (normal-context? ctx)
66 (or (eq? ctx 'normal/bottom) (eq? ctx 'normal/top)))
67 (define-inline (stmt-context? ctx)
68 (or (eq? ctx 'stmt/bottom) (eq? ctx 'stmt/top)))
69 (define-inline (tail-context? ctx)
70 (eq? ctx 'tail))
71 (define-inline (bottom-context? ctx)
72 (or (eq? ctx 'normal/bottom) (eq? ctx 'stmt/bottom) (eq? ctx 'tail)))
73 (define-inline (top-context? ctx)
74 (or (eq? ctx 'normal/top) (eq? ctx 'stmt/top)))
75
76 ;; context switch
77 (define-inline (normal-context prev-ctx)
78 (if (bottom-context? prev-ctx) 'normal/bottom 'normal/top))
79 (define-inline (stmt-context prev-ctx)
80 (if (bottom-context? prev-ctx) 'stmt/bottom 'stmt/top))
81 (define-inline (tail-context prev-ctx) 'tail)
82
83 ;; whether we can use LREF/LSET
84 (define-inline (small-env? depth offset)
85 (and (<= 0 depth (- (ash 1 VM_INSN_ARG0_BITS) 1))
86 (<= 0 offset (- (ash 1 VM_INSN_ARG1_BITS) 1))))
87
88 ;; For brevity, these macro assumes variable 'target'.
89 (define-macro (cont-frame-size)
90 '(ctarget-cont-frame-size target))
91 (define-macro (env-header-size)
92 '(ctarget-env-header-size target))
93
94
95 ;; Dispatch pass5 handler.
96 ;; *pass5-dispatch-table* is defined below, after all handlers are defined.
97 (define-inline (pass5/rec iform target renv ctx)
98 ((vector-ref *pass5-dispatch-table* (vector-ref iform 0))
99 iform target renv ctx))
100
101 ;;
102 ;; Pass 5 main entry. Returns <compiled-code>
103 ;;
104 (define (pass5 iform target initial-renv ctx)
105 (let1 maxstack (pass5/rec iform target initial-renv ctx)
106 (rlet1 ccb (ctarget-ccb target)
107 (compiled-code-emit-RET! ccb)
108 (compiled-code-finish-builder ccb maxstack))))
109
110 ;;
111 ;; Pass 5 intermediate tree handlers
112 ;;
113
114 (define (pass5/$DEFINE iform target renv ctx)
115 (let ([d (pass5/rec ($define-expr iform) target renv 'normal/bottom)]
116 [f (cond [(memq 'const ($define-flags iform)) SCM_BINDING_CONST]
117 [(memq 'inlinable ($define-flags iform)) SCM_BINDING_INLINABLE]
118 [else 0])])
119 (compiled-code-emit1oi! (ctarget-ccb target) DEFINE f
120 ($define-id iform) ($*-src iform))
121 d))
122
123 (define (pass5/$LREF iform target renv ctx)
124 (receive (depth offset) (renv-lookup renv ($lref-lvar iform))
125 (if (small-env? depth offset)
126 (compiled-code-emit2i! (ctarget-ccb target) LREF depth offset
127 (lvar-name ($lref-lvar iform)))
128 (compiled-code-emit1oi! (ctarget-ccb target) XLREF offset depth
129 (lvar-name ($lref-lvar iform))))
130 (unless (lvar-immutable? ($lref-lvar iform))
131 (compiled-code-emit0! (ctarget-ccb target) UNBOX))
132 0))
133
134 (define (pass5/$LSET iform target renv ctx)
135 (receive (depth offset) (renv-lookup renv ($lset-lvar iform))
136 (rlet1 d (pass5/rec ($lset-expr iform) target renv (normal-context ctx))
137 (if (small-env? depth offset)
138 (compiled-code-emit2i! (ctarget-ccb target) LSET depth offset
139 (lvar-name ($lset-lvar iform)))
140 (compiled-code-emit1oi! (ctarget-ccb target) XLSET offset depth
141 (lvar-name ($lset-lvar iform)))))))
142
143 (define (pass5/$GREF iform target renv ctx)
144 (let1 id ($gref-id iform)
145 (compiled-code-emit0oi! (ctarget-ccb target) GREF id id)
146 0))
147
148 (define (pass5/$GSET iform target renv ctx)
149 (rlet1 d (pass5/rec ($gset-expr iform) target renv (normal-context ctx))
150 (let1 id ($gset-id iform)
151 (compiled-code-emit0oi! (ctarget-ccb target) GSET id id))))
152
153 (define (pass5/$CONST iform target renv ctx)
154 ;; if the context is stmt-context, value won't be used so we drop it.
155 (unless (stmt-context? ctx)
156 (compiled-code-emit0o! (ctarget-ccb target) CONST ($const-value iform)))
157 0)
158
159 ;; Branch peephole optimization
160 ;; We have variations of conditional branch instructions for typical
161 ;; cases. In this handler we select an appropriate instructions.
162 ;;
163 ;; Sometimes we want to inverse the test, swapping then and else,
164 ;; if we can strip extra NOT operation. Note that it is only possible
165 ;; if the result of test isn't used directly (that is, neither then nor
166 ;; else clause is ($IT)), thus we treat such a case specially.
167 (define (pass5/$IF iform target renv ctx)
168 (cond
169 [(and (not ($it? ($if-then iform)))
170 (not ($it? ($if-else iform)))
171 (has-tag? ($if-test iform) $ASM)
172 (eqv? (car ($asm-insn ($if-test iform))) NOT))
173 (pass5/$IF ($if ($*-src iform)
174 (car ($asm-args ($if-test iform)))
175 ($if-else iform)
176 ($if-then iform))
177 target renv ctx)]
178 [else
179 (pass5/branch-core iform target renv ctx)]))
180
181 (define (pass5/branch-core iform target renv ctx)
182 (let1 test ($if-test iform)
183 ;; Select an appropriate branch instruction
184 (cond
185 [(has-tag? test $ASM)
186 (let ([code (car ($asm-insn test))]; ASM code
187 [args ($asm-args test)])
188 (cond
189 [(eqv? code NULLP)
190 (pass5/if-final iform (car args) BNNULL 0 0
191 ($*-src test) target renv ctx)]
192 [(eqv? code EQ)
193 (pass5/if-eq iform (car args) (cadr args)
194 ($*-src test) target renv ctx)]
195 [(eqv? code EQV)
196 (pass5/if-eqv iform (car args) (cadr args)
197 ($*-src test) target renv ctx)]
198 [(eqv? code NUMEQ2)
199 (pass5/if-numeq iform (car args) (cadr args)
200 ($*-src test) target renv ctx)]
201 [(eqv? code NUMLE2)
202 (pass5/if-numcmp iform (car args) (cadr args)
203 BNLE ($*-src test) target renv ctx)]
204 [(eqv? code NUMLT2)
205 (pass5/if-numcmp iform (car args) (cadr args)
206 BNLT ($*-src test) target renv ctx)]
207 [(eqv? code NUMGE2)
208 (pass5/if-numcmp iform (car args) (cadr args)
209 BNGE ($*-src test) target renv ctx)]
210 [(eqv? code NUMGT2)
211 (pass5/if-numcmp iform (car args) (cadr args)
212 BNGT ($*-src test) target renv ctx)]
213 [else
214 (pass5/if-final iform test BF 0 0 ($*-src iform) target renv ctx)]
215 ))]
216 [(has-tag? test $EQ?)
217 (pass5/if-eq iform ($*-arg0 test) ($*-arg1 test)
218 ($*-src iform) target renv ctx)]
219 [(has-tag? test $EQV?)
220 (pass5/if-eqv iform ($*-arg0 test) ($*-arg1 test)
221 ($*-src iform) target renv ctx)]
222 [($const? test) ; this may occur as a result of macro expansion
223 (pass5/rec (if ($const-value test)
224 (if ($it? ($if-then iform)) test ($if-then iform))
225 (if ($it? ($if-else iform)) test ($if-else iform)))
226 target renv ctx)]
227 [else
228 (pass5/if-final iform test BF 0 0 ($*-src iform) target renv ctx)]
229 )))
230
231 ;;
232 (define (pass5/if-eq iform x y info target renv ctx)
233 (cond
234 [($const? x) (pass5/if-final iform y BNEQC ($const-value x)
235 0 info target renv ctx)]
236 [($const? y) (pass5/if-final iform x BNEQC ($const-value y)
237 0 info target renv ctx)]
238 [else
239 (let1 depth (imax (pass5/rec x target renv (normal-context ctx)) 1)
240 (compiled-code-emit-PUSH! (ctarget-ccb target))
241 (pass5/if-final iform #f BNEQ 0
242 (imax (pass5/rec y target renv 'normal/top) depth)
243 info target renv ctx))]))
244
245 (define (pass5/if-eqv iform x y info target renv ctx)
246 (cond
247 [($const? x) (pass5/if-final iform y BNEQVC ($const-value x)
248 0 info target renv ctx)]
249 [($const? y) (pass5/if-final iform x BNEQVC ($const-value y)
250 0 info target renv ctx)]
251 [else
252 (let1 depth (imax (pass5/rec x target renv (normal-context ctx)) 1)
253 (compiled-code-emit-PUSH! (ctarget-ccb target))
254 (pass5/if-final iform #f BNEQV 0
255 (imax (pass5/rec y target renv 'normal/top) depth)
256 info target renv ctx))]))
257
258 (define (pass5/if-numeq iform x y info target renv ctx)
259 (or (and ($const? x)
260 (integer-fits-insn-arg? ($const-value x))
261 (pass5/if-final iform y BNUMNEI ($const-value x)
262 0
263 info target renv ctx))
264 (and ($const? y)
265 (integer-fits-insn-arg? ($const-value y))
266 (pass5/if-final iform x BNUMNEI ($const-value y)
267 0
268 info target renv ctx))
269 (and ($lref? x)
270 (lvar-immutable? ($lref-lvar x))
271 (receive (depth offset) (renv-lookup renv ($lref-lvar x))
272 (and (small-env? depth offset)
273 (pass5/if-final iform #f LREF-VAL0-BNUMNE
274 (pass5/if-numcmp-lrefarg x renv)
275 (pass5/rec y target renv (normal-context ctx))
276 info target renv ctx))))
277 (and ($lref? y)
278 (lvar-immutable? ($lref-lvar y))
279 (receive (depth offset) (renv-lookup renv ($lref-lvar y))
280 (and (small-env? depth offset)
281 (pass5/if-final iform #f LREF-VAL0-BNUMNE
282 (pass5/if-numcmp-lrefarg y renv)
283 (pass5/rec x target renv (normal-context ctx))
284 info target renv ctx))))
285 (let1 depth (imax (pass5/rec x target renv (normal-context ctx)) 1)
286 (compiled-code-emit-PUSH! (ctarget-ccb target))
287 (pass5/if-final iform #f BNUMNE 0
288 (imax (pass5/rec y target renv 'normal/top) depth)
289 info target renv ctx))))
290
291 (define (pass5/if-numcmp iform x y insn info target renv ctx)
292 (define .fwd. `((,BNLT . ,LREF-VAL0-BNLT) (,BNLE . ,LREF-VAL0-BNLE)
293 (,BNGT . ,LREF-VAL0-BNGT) (,BNGE . ,LREF-VAL0-BNGE)))
294 (define .rev. `((,BNLT . ,LREF-VAL0-BNGT) (,BNLE . ,LREF-VAL0-BNGE)
295 (,BNGT . ,LREF-VAL0-BNLT) (,BNGE . ,LREF-VAL0-BNLE)))
296 (or (and ($lref? x)
297 (lvar-immutable? ($lref-lvar x))
298 (receive (depth offset) (renv-lookup renv ($lref-lvar x))
299 (and (small-env? depth offset)
300 (pass5/if-final iform #f (cdr (assv insn .fwd.))
301 (pass5/if-numcmp-lrefarg x renv)
302 (pass5/rec y target renv (normal-context ctx))
303 info target renv ctx))))
304 (and ($lref? y)
305 (lvar-immutable? ($lref-lvar y))
306 (receive (depth offset) (renv-lookup renv ($lref-lvar y))
307 (and (small-env? depth offset)
308 (pass5/if-final iform #f (cdr (assv insn .rev.))
309 (pass5/if-numcmp-lrefarg y renv)
310 (pass5/rec x target renv (normal-context ctx))
311 info target renv ctx))))
312 (let1 depth (imax (pass5/rec x target renv (normal-context ctx)) 1)
313 (compiled-code-emit-PUSH! (ctarget-ccb target))
314 (pass5/if-final iform #f insn 0
315 (imax (pass5/rec y target renv 'normal/top) depth)
316 info target renv ctx))))
317
318 ;; helper fn
319 (define (pass5/if-numcmp-lrefarg lref renv)
320 (receive (dep off) (renv-lookup renv ($lref-lvar lref))
321 (+ (ash off 10) dep)))
322
323
324 ;; pass5/if-final: Final stage of emitting branch instruction.
325 ;;
326 ;; Optimization
327 ;; - tail context
328 ;; - if insn is (BF)
329 ;; - then part is ($IT) => use RT
330 ;; - else part is ($IT) => use RF
331 ;; - then part is jump back to labeled closure
332 ;; => use BT, and use the destination of the label. (*)
333 ;; - otherwise, place RET after then clause
334 ;; - otherwise
335 ;; - else part is ($IT) => we can omit a jump after then clause
336 ;; - otherwise, merge the control after this node.
337 ;;
338 ;; (*) This converts the left asm output to the right one. This type of
339 ;; code appears as the result of the first pattern of $if optimization
340 ;; in pass3.
341 ;;
342 ;; L0: L0:
343 ;; ... ...
344 ;; BF L1 BT L0
345 ;; JUMP L0 xxx
346 ;; L1: xxx ...
347 ;; ...
348 ;;
349 ;; We have many variations of branch instrucitons, and the combination
350 ;; of arguments reflects them.
351 ;;
352 ;; iform - original IForm of this if expression.
353 ;; test - the iform for the test expression. the result of this expression
354 ;; would trigger the conditional branch. This can be #f when we use
355 ;; operate-and-branch instructions such as BNLT.
356 ;; code - an instruciton code.
357 ;; arg0/opr - If the instruction is one of those that take an extra operand
358 ;; (like BNEQC), this is the operand. Otherwise, this is the ARG0
359 ;; of the instruction.
360 ;; depth - calculated maximum stack depth at this point.
361 ;; info - source info
362 ;; ccb - code buffer
363 ;; renv - runtime env
364 ;; ctx - compile context
365
366 (define-constant .branch-insn-extra-operand.
367 `(,BNEQC ,BNEQVC))
368
369 (define (pass5/if-final iform test code arg0/opr depth info target renv ctx)
370 (let ([depth (if test
371 (imax (pass5/rec test target renv (normal-context ctx)) depth)
372 depth)]
373 [then-form ($if-then iform)]
374 [else-form ($if-else iform)])
375 (cond
376 [(tail-context? ctx)
377 (or (and (eqv? code BF)
378 (cond
379 [($it? then-form)
380 (compiled-code-emit0i! (ctarget-ccb target) RT info)
381 (imax (pass5/rec else-form target renv ctx) depth)]
382 [($it? else-form)
383 (compiled-code-emit0i! (ctarget-ccb target) RF info)
384 (imax (pass5/rec then-form target renv ctx) depth)]
385 [(and (has-tag? then-form $LABEL)
386 ($label-label then-form))
387 => (^[label]
388 (compiled-code-emit0o! (ctarget-ccb target) BT label)
389 (imax (pass5/rec else-form target renv ctx) depth))]
390 [else #f]))
391 (let* ([ccb (ctarget-ccb target)]
392 [elselabel (compiled-code-new-label ccb)])
393 (if (memv code .branch-insn-extra-operand.)
394 (compiled-code-emit0oi! ccb code (list arg0/opr elselabel) info)
395 (compiled-code-emit1oi! ccb code arg0/opr elselabel info))
396 (set! depth (imax (pass5/rec then-form target renv ctx) depth))
397 (compiled-code-emit-RET! ccb)
398 (compiled-code-set-label! ccb elselabel)
399 (imax (pass5/rec else-form target renv ctx) depth)))]
400 [else
401 (let* ([ccb (ctarget-ccb target)]
402 [elselabel (compiled-code-new-label ccb)]
403 [mergelabel (compiled-code-new-label ccb)])
404 (if (memv code .branch-insn-extra-operand.)
405 (compiled-code-emit0oi! ccb code (list arg0/opr elselabel) info)
406 (compiled-code-emit1oi! ccb code arg0/opr elselabel info))
407 (set! depth (imax (pass5/rec then-form target renv ctx) depth))
408 (unless ($it? else-form)
409 (compiled-code-emit0o! ccb JUMP mergelabel))
410 (compiled-code-set-label! ccb elselabel)
411 (unless ($it? else-form)
412 (set! depth (imax (pass5/rec else-form target renv ctx) depth)))
413 (compiled-code-set-label! ccb mergelabel)
414 depth)])))
415
416 (define (pass5/$IT iform target renv ctx) 0)
417
418 ;; $LET stack estimate
419 ;; normal let: Each init clause is evaluated while preceding results
420 ;; of inits are on the stack. Pass5/prepare-args returns the maximum
421 ;; stack depth from the initial position of the stack (i.e. it considers
422 ;; accumulating values). After all inits are evaluated, we complete
423 ;; the env frame and run the body.
424 ;;
425 ;; letrec: We create the env frame before evaluating inits, so the max
426 ;; stack is: total env frame size + max of stack depth consumed by
427 ;; one of inits or the body.
428 ;;
429 (define (pass5/$LET iform target renv ctx)
430 (when (and (has-tag? ($let-body iform) $LET)
431 (eq? ($let-type iform) 'let))
432 (pass5/flatten-let*! iform))
433 (let ([info ($*-src iform)]
434 [lvars ($let-lvars iform)]
435 [inits ($let-inits iform)]
436 [body ($let-body iform)]
437 [merge-label (if (bottom-context? ctx)
438 #f
439 (compiled-code-new-label (ctarget-ccb target)))])
440 (when (> (length lvars) (- (ash 1 VM_INSN_ARG_BITS) 1))
441 (errorf "[internal] Local frame size (~a) exceeded compiler limitation (~a)."
442 (length lvars) (- (ash 1 VM_INSN_ARG_BITS) 1)))
443 (let ([nlocals (length lvars)]
444 [ccb (ctarget-ccb target)])
445 (case ($let-type iform)
446 [(let)
447 (cond
448 [(bottom-context? ctx)
449 (let1 dinit (pass5/prepare-args inits target renv ctx)
450 (compiled-code-emit1i! ccb LOCAL-ENV nlocals info)
451 (pass5/box-mutable-lvars lvars ccb)
452 (let1 dbody (pass5/rec body target (cons lvars renv) ctx)
453 (unless (tail-context? ctx)
454 (compiled-code-emit0! ccb POP-LOCAL-ENV))
455 (imax dinit (+ dbody (env-header-size) nlocals))))]
456 [else
457 (compiled-code-emit1oi! ccb PRE-CALL nlocals merge-label info)
458 (let1 dinit (pass5/prepare-args inits target renv ctx)
459 (compiled-code-emit1i! ccb LOCAL-ENV nlocals info)
460 (pass5/box-mutable-lvars lvars ccb)
461 (let1 dbody (pass5/rec body target (cons lvars renv) 'tail)
462 (compiled-code-emit-RET! ccb)
463 (compiled-code-set-label! ccb merge-label)
464 (imax dinit
465 (+ dbody (cont-frame-size) (env-header-size) nlocals))))])]
466 [(rec rec*)
467 (receive (closures others)
468 (partition-letrec-inits inits target (cons lvars renv) 0 '() '())
469 (cond
470 [(bottom-context? ctx)
471 (compiled-code-emit1oi! ccb LOCAL-ENV-CLOSURES nlocals
472 closures info)
473 (emit-letrec-boxers ccb lvars nlocals)
474 (let* ([dinit (emit-letrec-inits others lvars nlocals target
475 (cons lvars renv) 0)]
476 [dbody (pass5/rec body target (cons lvars renv) ctx)])
477 (unless (tail-context? ctx)
478 (compiled-code-emit0! ccb POP-LOCAL-ENV))
479 (+ (env-header-size) nlocals (imax dinit dbody)))]
480 [else
481 (compiled-code-emit1oi! ccb PRE-CALL nlocals merge-label info)
482 (compiled-code-emit1oi! ccb LOCAL-ENV-CLOSURES nlocals
483 closures info)
484 (emit-letrec-boxers ccb lvars nlocals)
485 (let* ([dinit (emit-letrec-inits others lvars nlocals target
486 (cons lvars renv) 0)]
487 [dbody (pass5/rec body target (cons lvars renv) 'tail)])
488 (compiled-code-emit-RET! ccb)
489 (compiled-code-set-label! ccb merge-label)
490 (+ (cont-frame-size) (env-header-size) nlocals
491 (imax dinit dbody)))]))]
492 [else
493 (error "[internal error]: pass5/$LET got unknown let type:"
494 ($let-type iform))]
495 ))))
496
497 ;; Nested let can be flattened if the initexpr of inner local vars
498 ;; does not depend on the values of the local vars of the current frame,
499 ;; and they don't possibly capture environments/continuations.
500 ;; $const and $lref to outer frames are certainly safe.
501 ;; $gref also won't capture frames, but we have to be careful if we ever
502 ;; provide a mechanism to restart from undefined variable error.
503 (define (pass5/flatten-let*! iform)
504 (let loop ([lvars (reverse ($let-lvars iform))]
505 [inits (reverse ($let-inits iform))]
506 [node ($let-body iform)])
507 (let1 ins ($let-inits node)
508 (cond [(everyc safe-lvar-initval-for-flatten? ins lvars)
509 (let ([lvars (reverse ($let-lvars node) lvars)]
510 [inits (reverse ins inits)])
511 (if (and (has-tag? ($let-body node) $LET)
512 (eq? ($let-type node) 'let))
513 (loop lvars inits ($let-body node))
514 (begin ($let-lvars-set! iform (reverse! lvars))
515 ($let-inits-set! iform (reverse! inits))
516 ($let-body-set! iform ($let-body node)))))]
517 [(eq? node ($let-body iform))] ; we didn't do anything
518 [else ($let-lvars-set! iform (reverse! lvars))
519 ($let-inits-set! iform (reverse! inits))
520 ($let-body-set! iform node)]))))
521
522 (define (safe-lvar-initval-for-flatten? init existing-lvars)
523 (and (or ($const? init)
524 (and ($lref? init)
525 (not (memq ($lref-lvar init) existing-lvars))))))
526
527 ;; classify init values into closures/constants and non-closure expressions.
528 ;; returns two lists: a list of init values (closures or #under values)
529 ;; corresponding to lvar list, and non-closure init iforms, each
530 ;; paired with an lvar count.
531 (define (partition-letrec-inits inits target renv cnt closures others)
532 (if (null? inits)
533 (values (reverse closures) (reverse others))
534 (let1 init (car inits)
535 (cond
536 [(has-tag? init $LAMBDA)
537 (partition-letrec-inits (cdr inits) target renv (+ cnt 1)
538 (cons (pass5/lambda init target renv) closures)
539 others)]
540 [($const? init)
541 (partition-letrec-inits (cdr inits) target renv (+ cnt 1)
542 (cons ($const-value init) closures)
543 others)]
544 [else
545 (partition-letrec-inits (cdr inits) target renv (+ cnt 1)
546 (cons (undefined) closures)
547 (acons cnt init others))]))))
548
549 ;; box set!-able slots in the ENV at stack top. used in letrec and
550 ;; receive frame setup.
551 (define (emit-letrec-boxers ccb lvars nlocals)
552 (let loop ([lvars lvars] [cnt nlocals])
553 (unless (null? lvars)
554 (unless (lvar-immutable? (car lvars))
555 (compiled-code-emit1! ccb BOX cnt))
556 (loop (cdr lvars) (- cnt 1)))))
557
558 ;; emit LSET or ENV-SET insn to initialize lvars that aren't closures or
559 ;; constants. init-alist is the second value partition-letrec-inits
560 ;; returned, which is a list of (<lvar-count> <init-iform>).
561 (define (emit-letrec-inits init-alist lvars nlocals target renv depth)
562 (if (null? init-alist)
563 depth
564 (let* ([off&expr (car init-alist)]
565 [d (pass5/rec (cdr off&expr) target renv 'normal/bottom)]
566 [lvar (list-ref lvars (car off&expr))]
567 [ccb (ctarget-ccb target)])
568 (if (lvar-immutable? lvar)
569 (compiled-code-emit1! ccb ENV-SET (- nlocals 1 (car off&expr)))
570 (compiled-code-emit2! ccb LSET 0 (- nlocals 1 (car off&expr))))
571 (emit-letrec-inits (cdr init-alist) lvars nlocals target renv
572 (imax depth d)))))
573
574 (define (pass5/$RECEIVE iform target renv ctx)
575 (let ([nargs ($receive-reqargs iform)]
576 [optarg ($receive-optarg iform)]
577 [lvars ($receive-lvars iform)]
578 [expr ($receive-expr iform)]
579 [body ($receive-body iform)]
580 [ccb (ctarget-ccb target)])
581 (cond
582 [(bottom-context? ctx)
583 (let1 dinit (pass5/rec expr target renv (normal-context ctx))
584 (compiled-code-emit2i! ccb TAIL-RECEIVE nargs optarg ($*-src iform))
585 (emit-letrec-boxers ccb lvars (length lvars))
586 (let1 dbody (pass5/rec body target (cons lvars renv) ctx)
587 (unless (tail-context? ctx)
588 (compiled-code-emit0! ccb POP-LOCAL-ENV))
589 (imax dinit (+ nargs optarg (env-header-size) dbody))))]
590 [else
591 (let ([merge-label (compiled-code-new-label ccb)]
592 [dinit (pass5/rec expr target renv (normal-context ctx))])
593 (compiled-code-emit2oi! ccb RECEIVE nargs optarg
594 merge-label ($*-src iform))
595 (emit-letrec-boxers ccb lvars (length lvars))
596 (let1 dbody (pass5/rec body target (cons lvars renv) 'tail)
597 (compiled-code-emit-RET! ccb)
598 (compiled-code-set-label! ccb merge-label)
599 (imax dinit (+ nargs optarg (cont-frame-size) (env-header-size) dbody))))]
600 )))
601
602 (define (pass5/$LAMBDA iform target renv ctx)
603 (let ([code (pass5/lambda iform target renv)]
604 [info ($*-src iform)])
605 (compiled-code-emit0oi! (ctarget-ccb target) CLOSURE code info))
606 0)
607
608 (define (pass5/lambda iform target renv)
609 (let* ([ccb (make-compiled-code-builder ($lambda-reqargs iform)
610 ($lambda-optarg iform)
611 ($lambda-name iform)
612 (ctarget-ccb target) ; parent
613 ($lambda-inliner iform))]
614 [ntarget (make-child-compile-target ccb target)])
615 (compiled-code-attach-source-info! ccb ($lambda-src iform) ($lambda-type iform))
616
617 ;; If any of procedure parameters are set!, we should box it
618 ;; upon entering the procedure.
619 (let loop ([lvs ($lambda-lvars iform)]
620 [k (length ($lambda-lvars iform))])
621 (unless (null? lvs)
622 (unless (lvar-immutable? (car lvs))
623 (compiled-code-emit1i! ccb BOX k (lvar-name (car lvs))))
624 (loop (cdr lvs) (- k 1))))
625 ;; Save list of unused arguments in the attributes of (car signature-info).
626 (let1 uargs (filter-map (^[lv] (and (zero? (lvar-ref-count lv))
627 (lvar-name lv)))
628 ($lambda-lvars iform))
629 (unless (null? uargs)
630 (pair-attribute-set! (car (slot-ref ccb 'signature-info))
631 'unused-args uargs)))
632 ;; Run pass5 on body
633 (pass5 ($lambda-body iform)
634 ntarget
635 (if (null? ($lambda-lvars iform))
636 renv
637 (cons ($lambda-lvars iform) renv))
638 'tail)))
639
640 (define (pass5/$CLAMBDA iform target renv ctx)
641 (define (reqargs-min-max argcounts)
642 (let loop ([counts argcounts] [mi #f] [mx 0])
643 (match counts
644 [() (values mi mx)]
645 [((req . _) . rest) (loop rest (if mi (min mi req) req) (max mx req))])))
646 (let*-values ([(cs) ($clambda-closures iform)]
647 [(ccb) (ctarget-ccb target)]
648 [(minarg maxarg) (reqargs-min-max ($clambda-argcounts iform))]
649 [merger (if (bottom-context? ctx)
650 #f
651 (compiled-code-new-label ccb))])
652 (when merger
653 (compiled-code-emit1oi! ccb PRE-CALL 4 merger ($*-src iform)))
654 (compiled-code-emit0o! ccb CONST minarg)
655 (compiled-code-emit-PUSH! ccb)
656 (compiled-code-emit0o! ccb CONST maxarg)
657 (compiled-code-emit-PUSH! ccb)
658 (compiled-code-emit0o! ccb CONST #f)
659 (let loop ([xs cs] [depth 0] [cnt 0])
660 (cond
661 [(null? xs)
662 (compiled-code-emit1! ccb LIST (length cs))
663 (compiled-code-emit-PUSH! ccb)
664 (compiled-code-emit0o! ccb CONST ($clambda-name iform))
665 (compiled-code-emit-PUSH! ccb)
666 (compiled-code-emit0oi! ccb GREF make-case-lambda. make-case-lambda.)
667 (compiled-code-emit1i! ccb CALL 4 ($*-src iform))
668 (when merger
669 (compiled-code-set-label! ccb merger))
670 (+ depth 3)]
671 [else
672 (compiled-code-emit-PUSH! ccb)
673 (let1 d (pass5/rec (car xs) target renv 'normal/top)
674 (loop (cdr xs) (imax depth (+ d cnt 1)) (+ cnt 1)))]))))
675
676 (define (pass5/$LABEL iform target renv ctx)
677 (let ([label ($label-label iform)]
678 [ccb (ctarget-ccb target)])
679 ;; NB: $LABEL node in the PROC position of $CALL node is handled by $CALL.
680 (cond
681 [label (compiled-code-emit0oi! ccb JUMP label ($*-src iform))
682 0]
683 [else (compiled-code-set-label! ccb (pass5/ensure-label ccb iform))
684 (pass5/rec ($label-body iform) target renv ctx)])))
685
686 (define (pass5/$SEQ iform target renv ctx)
687 (let1 exprs ($seq-body iform)
688 (cond
689 [(null? exprs) 0]
690 [(null? (cdr exprs)) (pass5/rec (car exprs) target renv ctx)]
691 [else
692 (let loop ([exprs exprs] [depth 0])
693 (if (null? (cdr exprs))
694 (imax (pass5/rec (car exprs) target renv ctx) depth)
695 (loop (cdr exprs)
696 (imax (pass5/rec (car exprs) target renv (stmt-context ctx))
697 depth))))])))
698
699 ;; $CALL.
700 ;; There are several variations in $CALL node. Each variation may also
701 ;; have tail-call version and non-tail-call version.
702 ;;
703 ;; 1. Local call: a $CALL node that has 'local' flag is a call to known
704 ;; local procedure. Its arguments are already adjusted to match the
705 ;; signature of the procedure. PROC slot contains an LREF node that
706 ;; points to the local procedure.
707 ;;
708 ;; 2. Embedded call: a $CALL node that has 'embed' flag is a control
709 ;; transfer to an inlined local procedure, whose entry point may be
710 ;; called from more than one place (Cf. an inlined procedure that is
711 ;; called only once becomes $LET node, so we don't need to consider it).
712 ;; Its arguments are already adjusted to match the signature of the
713 ;; procedure. Its PROC slot contains the embedded $LAMBDA node, whose
714 ;; body is $LABEL node.
715 ;; The generated code is almost the same as $LET node, except that a
716 ;; label is placed just after LOCAL-ENV.
717 ;;
718 ;; We also record the RENV in this node, which is later used by
719 ;; jump call node to determine the number of environment frames the
720 ;; LOCAL-ENV-JUMP should discard. (Here we assume an embed node always
721 ;; goes through pass5 before related jump nodes.)
722 ;;
723 ;; 3. Jump call: a $CALL node that has 'jump' flag is a control transfer
724 ;; to an inlined local procedure, and whose body is embedded in somewhere
725 ;; else (by an 'embedded call' node). The PROC slot contains the embed
726 ;; $CALL node. We emit LOCAL-ENV-JUMP instruction for this type of node.
727 ;;
728 ;; 4. Head-heavy call: a $CALL node without any flag, and all the
729 ;; arguments are simple expressions (e.g. const or lref), but the
730 ;; operator expression has $LET. The normal calling sequence evaluates
731 ;; the operator expression after pushing arguments. That causes the
732 ;; $LET be evaluated in 'top' context, which requires pushing
733 ;; extra continuation. If all the arguments are simple, we can evaluate
734 ;; the operator expression first, and keeping it in VAL0 while pushing
735 ;; the arguments.
736 ;; Notably, a named let expression tends to become a head-heavy call,
737 ;; so it is worth to treat it specially.
738 ;; Note that this head-heavy call optimization relies on the arguments
739 ;; to use combined instructions such as CONST-PUSH or LREF-PUSH. If
740 ;; the instruction combination is turned off, we can't use this since
741 ;; VAL0 is overwritten by arguments.
742 ;;
743 ;; 5. Other call node generates the standard calling sequence.
744 ;;
745
746 ;; stack depth of $CALL nodes:
747 ;; - if nargs >= 1, we need (# of args) + (env header) slots
748 ;; - if generic call, +2 for possible object-apply hack and next-method.
749 ;; - if non-tail call, + (cont-frame-size).
750
751 (define (pass5/$CALL iform target renv ctx)
752 (case ($call-flag iform)
753 [(local) (pass5/local-call iform target renv ctx)]
754 [(embed) (pass5/embed-call iform target renv ctx)]
755 [(jump) (pass5/jump-call iform target renv ctx)]
756 [else
757 (if (and (bottom-context? ctx)
758 (has-tag? ($call-proc iform) $LET)
759 (all-args-simple? ($call-args iform))
760 (not (vm-compiler-flag-is-set? SCM_COMPILE_NOCOMBINE)))
761 (pass5/head-heavy-call iform target renv ctx)
762 (pass5/normal-call iform target renv ctx))]))
763
764 ;; Local call
765 ;; PROC is always $LREF.
766 (define (pass5/local-call iform target renv ctx)
767 (let* ([args ($call-args iform)]
768 [nargs (length args)]
769 [ccb (ctarget-ccb target)])
770 (if (tail-context? ctx)
771 (let1 dinit (pass5/prepare-args args target renv ctx)
772 (pass5/rec ($call-proc iform) target renv 'normal/top)
773 (compiled-code-emit1i! ccb LOCAL-ENV-TAIL-CALL nargs ($*-src iform))
774 (if (= nargs 0) 0 (imax dinit (+ nargs (env-header-size)))))
775 (let1 merge-label (compiled-code-new-label ccb)
776 (compiled-code-emit1oi! ccb PRE-CALL nargs merge-label ($*-src iform))
777 (let1 dinit (pass5/prepare-args args target renv ctx)
778 (pass5/rec ($call-proc iform) target renv 'normal/top)
779 (compiled-code-emit1i! ccb LOCAL-ENV-CALL nargs ($*-src iform))
780 (compiled-code-set-label! ccb merge-label)
781 (if (= nargs 0)
782 (cont-frame-size)
783 (imax dinit (+ nargs (env-header-size) (cont-frame-size)))))))))
784
785 ;; Embedded call
786 ;; $call-proc has $lambda node. We inline its body.
787 ;; We also record the RENV to the current node, so that the jump calls
788 ;; to the inlined body can adjust env frame properly.
789 (define (pass5/embed-call iform target renv ctx)
790 (let* ([proc ($call-proc iform)]
791 [args ($call-args iform)]
792 [nargs (length args)]
793 [label ($lambda-body proc)]
794 [lvars ($lambda-lvars proc)]
795 [newenv (if (= nargs 0) renv (cons lvars renv))]
796 [ccb (ctarget-ccb target)]
797 [merge-label (compiled-code-new-label ccb)])
798 ($call-renv-set! iform (reverse renv))
799 (unless (tail-context? ctx)
800 (compiled-code-emit1oi! ccb PRE-CALL nargs merge-label ($*-src iform)))
801 (let1 dinit (if (> nargs 0)
802 (rlet1 d (pass5/prepare-args args target renv ctx)
803 (compiled-code-emit1i! ccb LOCAL-ENV nargs ($*-src iform))
804 (pass5/box-mutable-lvars lvars ccb))
805 0)
806 (compiled-code-set-label! ccb (pass5/ensure-label ccb label))
807 (let1 dbody (pass5/rec ($label-body label) target newenv 'tail)
808 (compiled-code-emit-RET! ccb)
809 (compiled-code-set-label! ccb merge-label)
810 (if (= nargs 0)
811 (+ (cont-frame-size) dbody)
812 (imax dinit (+ nargs (env-header-size) (cont-frame-size) dbody)))))
813 ))
814
815 ;; Jump call
816 ;; $call-proc has a $call[embed] node, whose proc slot has $lambda
817 ;; node, whose proc slot has $label node.
818 ;; NB: we're not sure whether we'll have non-tail jump call yet.
819 (define (pass5/jump-call iform target renv ctx)
820 (let ([args ($call-args iform)]
821 [embed-node ($call-proc iform)]
822 [ccb (ctarget-ccb target)])
823 (let ([nargs (length args)]
824 [label ($lambda-body ($call-proc embed-node))]
825 [lvars ($lambda-lvars ($call-proc embed-node))]
826 [renv-diff (list-remove-prefix ($call-renv embed-node)
827 (reverse renv))])
828 (unless renv-diff
829 (errorf "[internal error] $call[jump] appeared out of context of related $call[embed] (~s vs ~s)"
830 ($call-renv embed-node) renv))
831 (if (tail-context? ctx)
832 (let1 dinit (pass5/prepare-args args target renv ctx)
833 (pass5/emit-local-env-jump ccb lvars (length renv-diff)
834 (pass5/ensure-label ccb label)
835 ($*-src iform))
836 (if (= nargs 0) 0 (imax dinit (+ nargs (env-header-size)))))
837 (let1 merge-label (compiled-code-new-label ccb)
838 (compiled-code-emit1oi! ccb PRE-CALL nargs merge-label ($*-src iform))
839 (let1 dinit (pass5/prepare-args args target renv ctx)
840 (pass5/emit-local-env-jump ccb lvars (length renv-diff)
841 (pass5/ensure-label ccb label)
842 ($*-src iform))
843 (compiled-code-set-label! ccb merge-label)
844 (if (= nargs 0)
845 (cont-frame-size)
846 (imax dinit (+ nargs (env-header-size) (cont-frame-size))))))
847 ))))
848
849 (define (pass5/emit-local-env-jump ccb lvars env-depth label src)
850 (let loop ([lvs lvars])
851 (cond [(null? lvs) ; no need of boxing.
852 (compiled-code-emit1oi! ccb LOCAL-ENV-JUMP env-depth label src)]
853 [(not (lvar-immutable? (car lvs))) ; need boxing
854 (compiled-code-emit1i! ccb LOCAL-ENV-SHIFT env-depth src)
855 (pass5/box-mutable-lvars lvars ccb)
856 (compiled-code-emit0oi! ccb JUMP label src)]
857 [else
858 (loop (cdr lvs))])))
859
860 ;; Head-heavy call
861 (define (pass5/head-heavy-call iform target renv ctx)
862 (let* ([args ($call-args iform)]
863 [nargs (length args)]
864 [ccb (ctarget-ccb target)])
865 (if (tail-context? ctx)
866 (let* ([dproc (pass5/rec ($call-proc iform)
867 target renv (normal-context ctx))]
868 [dinit (pass5/prepare-args args target renv 'normal/top)])
869 (compiled-code-emit1i! ccb TAIL-CALL nargs ($*-src iform))
870 (imax dinit (+ nargs dproc (env-header-size))))
871 (let1 merge-label (compiled-code-new-label ccb)
872 (compiled-code-emit1oi! ccb PRE-CALL nargs merge-label ($*-src iform))
873 (let* ([dproc (pass5/rec ($call-proc iform)
874 target renv (normal-context ctx))]
875 [dinit (pass5/prepare-args args target renv 'normal/top)])
876 (compiled-code-emit1i! ccb CALL nargs ($*-src iform))
877 (compiled-code-set-label! ccb merge-label)
878 (+ (cont-frame-size) (imax dinit (+ nargs dproc (env-header-size))))))
879 )))
880
881 ;; Normal call
882 (define (pass5/normal-call iform target renv ctx)
883 (let* ([args ($call-args iform)]
884 [nargs (length args)]
885 [ccb (ctarget-ccb target)])
886 (if (tail-context? ctx)
887 (let* ([dinit (pass5/prepare-args args target renv ctx)]
888 [dproc (pass5/rec ($call-proc iform) target renv 'normal/top)])
889 (compiled-code-emit1i! ccb TAIL-CALL nargs ($*-src iform))
890 (imax dinit (+ nargs dproc (env-header-size))))
891 (let1 merge-label (compiled-code-new-label ccb)
892 (compiled-code-emit1oi! ccb PRE-CALL nargs merge-label ($*-src iform))
893 (let* ([dinit (pass5/prepare-args args target renv ctx)]
894 [dproc (pass5/rec ($call-proc iform) target renv 'normal/top)])
895 (compiled-code-emit1i! ccb CALL nargs ($*-src iform))
896 (compiled-code-set-label! ccb merge-label)
897 (+ (cont-frame-size) (imax dinit (+ nargs dproc (env-header-size))))))
898 )))
899
900 (define (all-args-simple? args)
901 (cond [(null? args) #t]
902 [(memv (iform-tag (car args)) `(,$LREF ,$CONST))
903 (all-args-simple? (cdr args))]
904 [else #f]))
905
906 ;; Returns a part of lis whose head is removed. If HEAD is not a prefix
907 ;; of LIS, returns #f.
908 (define (list-remove-prefix head lis)
909 (let loop ((head head) (lis lis))
910 (cond [(null? head) lis]
911 [(null? lis) #f]
912 [(eq? (car head) (car lis)) (loop (cdr head) (cdr lis))]
913 [else #f])))
914
915 (define (pass5/ensure-label ccb label-node)
916 (or ($label-label label-node)
917 (rlet1 lab (compiled-code-new-label ccb)
918 ($label-label-set! label-node lab))))
919
920 ;; $DYNENV
921 (define (pass5/$DYNENV iform target renv ctx)
922 (let* ([ccb (ctarget-ccb target)]
923 [merge-label (and (not (tail-context? ctx))
924 (compiled-code-new-label ccb))]
925 [dcont (if (tail-context? ctx)
926 0
927 (begin
928 (compiled-code-emit1oi! ccb PRE-CALL 0 merge-label
929 ($*-src iform))
930 (cont-frame-size)))]
931 [dkey (pass5/rec ($dynenv-key iform) target renv 'normal/bottom)]
932 [flag (if (memq 'push ($dynenv-flags iform)) 1 0)])
933 (compiled-code-emit-PUSH! ccb)
934 (let* ([dval (pass5/rec ($dynenv-value iform) target renv 'normal/top)]
935 [dkv (imax dkey (+ dval 1))])
936 (compiled-code-emit1i! ccb TAIL-EXTEND-DENV flag ($*-src iform))
937 (let1 dbody (pass5/rec ($dynenv-body iform) target renv 'tail)
938 (unless (tail-context? ctx)
939 (compiled-code-emit-RET! ccb)
940 (compiled-code-set-label! ccb merge-label))
941 (+ dcont (imax dkv dbody))))))
942
943 ;; $ASMs. For some instructions, we may pick more specialized one
944 ;; depending on its arguments.
945
946 (define (pass5/$ASM iform target renv ctx)
947 (let ([info ($*-src iform)]
948 [insn ($asm-insn iform)]
949 [args ($asm-args iform)])
950 (case/unquote
951 (car insn)
952 [(EQ)
953 (pass5/asm-eq info (car args) (cadr args) target renv ctx)]
954 [(EQV)
955 (pass5/asm-eqv info (car args) (cadr args) target renv ctx)]
956 [(NUMEQ2)
957 (pass5/asm-numeq2 info (car args) (cadr args) target renv ctx)]
958 [(NUMLT2 NUMLE2 NUMGT2 NUMGE2)
959 (pass5/asm-numcmp info (car insn) (car args) (cadr args) target renv ctx)]
960 [(NUMADD2)
961 (pass5/asm-numadd2 info (car args) (cadr args) target renv ctx)]
962 [(NUMSUB2)
963 (pass5/asm-numsub2 info (car args) (cadr args) target renv ctx)]
964 [(NUMMUL2)
965 (pass5/asm-nummul2 info (car args) (cadr args) target renv ctx)]
966 [(NUMDIV2)
967 (pass5/asm-numdiv2 info (car args) (cadr args) target renv ctx)]
968 [(LOGAND LOGIOR LOGXOR)
969 (pass5/asm-bitwise info (car insn) (car args) (cadr args) target renv ctx)]
970 [(VEC-REF)
971 (pass5/asm-vec-ref info (car args) (cadr args) target renv ctx)]
972 [(VEC-SET)
973 (pass5/asm-vec-set info (car args) (cadr args) (caddr args) target renv ctx)]
974 [(SLOT-REF)
975 (pass5/asm-slot-ref info (car args) (cadr args) target renv ctx)]
976 [(SLOT-SET)
977 (pass5/asm-slot-set info (car args) (cadr args) (caddr args) target renv ctx)]
978 [(TAIL-APPLY)
979 ;; TAIL-APPLY pushes restarg onto stack, thus +1.
980 (if (tail-context? ctx)
981 (+ 1 (pass5/asm-generic target insn args info renv))
982 (let* ([ccb (ctarget-ccb target)]
983 [merge-label (compiled-code-new-label ccb)])
984 (compiled-code-emit0oi! ccb PRE-CALL merge-label info)
985 (let1 d (pass5/asm-generic target insn args info renv)
986 (compiled-code-set-label! ccb merge-label)
987 (+ (cont-frame-size) d 1))))]
988 [else
989 (pass5/asm-generic target insn args info renv)])))
990
991 (define (pass5/asm-generic target insn args info renv)
992 ;; general case
993 (let1 ccb (ctarget-ccb target)
994 (case (length args)
995 [(0) (pass5/emit-asm! ccb insn info) 0]
996 [(1) (rlet1 d (pass5/rec (car args) target renv 'normal/top)
997 (pass5/emit-asm! ccb insn info))]
998 [(2) (let1 d0 (pass5/rec (car args) target renv 'normal/top)
999 (compiled-code-emit-PUSH! ccb)
1000 (let1 d1 (pass5/rec (cadr args) target renv 'normal/top)
1001 (pass5/emit-asm! ccb insn info)
1002 (imax d0 (+ d1 1))))]
1003 [else
1004 (let loop ([args args] [depth 0] [cnt 0])
1005 (cond [(null? (cdr args))
1006 (let1 d (pass5/rec (car args) target renv 'normal/top)
1007 (pass5/emit-asm! ccb insn info)
1008 (imax depth (+ cnt d)))]
1009 [else
1010 (let1 d (pass5/rec (car args) target renv 'normal/top)
1011 (compiled-code-emit-PUSH! ccb)
1012 (loop (cdr args) (imax depth (+ d cnt)) (+ cnt 1)))]))]
1013 )))
1014
1015 (define (pass5/emit-asm! ccb insn info)
1016 (match insn
1017 [(code) (compiled-code-emit0i! ccb code info)]
1018 [(code arg0) (compiled-code-emit1i! ccb code arg0 info)]
1019 [(code arg0 arg1) (compiled-code-emit2i! ccb code arg0 arg1 info)]))
1020
1021 ;; Utility macros. Assumes target, renv and ctx are visible.
1022
1023 (define-macro (pass5/builtin-twoargs info code param arg0 arg1)
1024 (let ([d0 (gensym)]
1025 [d1 (gensym)])
1026 `(let1 ,d0 (pass5/rec ,arg0 target renv (normal-context ctx))
1027 (compiled-code-emit-PUSH! (ctarget-ccb target))
1028 (let1 ,d1 (pass5/rec ,arg1 target renv 'normal/top)
1029 ,(if (equal? param 0)
1030 `(compiled-code-emit0i! (ctarget-ccb target) ,code ,info)
1031 `(compiled-code-emit1i! (ctarget-ccb target) ,code ,param ,info))
1032 (imax ,d0 (+ ,d1 1))))))
1033
1034 (define-macro (pass5/builtin-onearg info code param arg0)
1035 (let1 d (gensym)
1036 `(rlet1 ,d (pass5/rec ,arg0 target renv (normal-context ctx))
1037 ,(if (equal? param 0)
1038 `(compiled-code-emit0i! (ctarget-ccb target) ,code ,info)
1039 `(compiled-code-emit1i! (ctarget-ccb target) ,code ,param ,info)))))
1040
1041 (define-macro (pass5/builtin-onearg+operand info code param operand arg0)
1042 (let1 d (gensym)
1043 `(rlet1 ,d (pass5/rec ,arg0 target renv (normal-context ctx))
1044 ,(if (equal? param 0)
1045 `(compiled-code-emit0oi! (ctarget-ccb target) ,code ,operand ,info)
1046 `(compiled-code-emit1oi! (ctarget-ccb target) ,code ,param ,operand ,info)))))
1047
1048 (define-macro (pass5/builtin-nargs info code args)
1049 `(%pass5/builtin-nargs target ,info ,code ,args (ctarget-ccb target) renv))
1050
1051 (define (%pass5/builtin-nargs target info code args ccb renv)
1052 (if (null? args)
1053 (begin (compiled-code-emit0i! ccb code info) 0)
1054 (let loop ([as args] [depth 0] [cnt 0])
1055 (cond [(null? (cdr as))
1056 (let1 d (pass5/rec (car as) target renv 'normal/top)
1057 (compiled-code-emit1i! ccb code (length args) info)
1058 (imax (+ d cnt) depth))]
1059 [else
1060 (let1 d (pass5/rec (car as) target renv 'normal/top)
1061 (compiled-code-emit-PUSH! ccb)
1062 (loop (cdr as) (imax (+ d cnt) depth) (+ cnt 1)))]))))
1063
1064 (define (pass5/$CONS iform target renv ctx)
1065 (pass5/builtin-twoargs ($*-src iform)
1066 CONS 0 ($*-arg0 iform) ($*-arg1 iform)))
1067
1068 (define (pass5/$APPEND iform target renv ctx)
1069 (pass5/builtin-twoargs ($*-src iform) APPEND 2 ($*-arg0 iform) ($*-arg1 iform)))
1070
1071 (define (pass5/$LIST iform target renv ctx)
1072 (pass5/builtin-nargs ($*-src iform) LIST ($*-args iform)))
1073
1074 (define (pass5/$LIST* iform target renv ctx)
1075 (pass5/builtin-nargs ($*-src iform) LIST-STAR ($*-args iform)))
1076
1077 (define (pass5/$VECTOR iform target renv ctx)
1078 (pass5/builtin-nargs ($*-src iform) VEC ($*-args iform)))
1079
1080 (define (pass5/$LIST->VECTOR iform target renv ctx)
1081 (pass5/builtin-onearg ($*-src iform) LIST2VEC 0 ($*-arg0 iform)))
1082
1083 (define (pass5/$MEMV iform target renv ctx)
1084 (pass5/builtin-twoargs ($*-src iform) MEMV 0 ($*-arg0 iform) ($*-arg1 iform)))
1085
1086 (define (pass5/$EQ? iform target renv ctx)
1087 (pass5/asm-eq ($*-src iform) ($*-arg0 iform) ($*-arg1 iform) target renv ctx))
1088
1089 (define (pass5/$EQV? iform target renv ctx)
1090 (pass5/asm-eqv ($*-src iform) ($*-arg0 iform) ($*-arg1 iform) target renv ctx))
1091
1092 ;; handlers to emit specialized instruction when applicable
1093
1094 (define (pass5/asm-eq info x y target renv ctx)
1095 (pass5/builtin-twoargs info EQ 0 x y))
1096
1097 (define (pass5/asm-eqv info x y target renv ctx)
1098 (pass5/builtin-twoargs info EQV 0 x y))
1099
1100 (define (pass5/asm-numeq2 info x y target renv ctx)
1101 (pass5/builtin-twoargs info NUMEQ2 0 x y))
1102
1103 (define (pass5/asm-numcmp info code x y target renv ctx)
1104 (pass5/builtin-twoargs info code 0 x y))
1105
1106 (define (pass5/asm-numadd2 info x y target renv ctx)
1107 (or (and ($const? x)
1108 (integer-fits-insn-arg? ($const-value x))
1109 (pass5/builtin-onearg info NUMADDI ($const-value x) y))
1110 (and ($const? y)
1111 (integer-fits-insn-arg? ($const-value y))
1112 (pass5/builtin-onearg info NUMADDI ($const-value y) x))
1113 (and ($lref? y)
1114 (lvar-immutable? ($lref-lvar y))
1115 (receive (depth offset) (renv-lookup renv ($lref-lvar y))
1116 (and (small-env? depth offset)
1117 (pass5/builtin-onearg info LREF-VAL0-NUMADD2
1118 (+ (ash offset 10) depth) x))))
1119 (and ($lref? x)
1120 (lvar-immutable? ($lref-lvar x))
1121 (receive (depth offset) (renv-lookup renv ($lref-lvar x))
1122 (and (small-env? depth offset)
1123 (pass5/builtin-onearg info LREF-VAL0-NUMADD2
1124 (+ (ash offset 10) depth) y))))
1125 (pass5/builtin-twoargs info NUMADD2 0 x y)))
1126
1127 (define (pass5/asm-numsub2 info x y target renv ctx)
1128 (or (and ($const? x)
1129 (integer-fits-insn-arg? ($const-value x))
1130 (pass5/builtin-onearg info NUMSUBI ($const-value x) y))
1131 (and ($const? y)
1132 (integer-fits-insn-arg? ($const-value y))
1133 (pass5/builtin-onearg info NUMADDI (- ($const-value y)) x))
1134 (pass5/builtin-twoargs info NUMSUB2 0 x y)))
1135
1136 (define (pass5/asm-nummul2 info x y target renv ctx)
1137 (pass5/builtin-twoargs info NUMMUL2 0 x y))
1138
1139 (define (pass5/asm-numdiv2 info x y target renv ctx)
1140 (pass5/builtin-twoargs info NUMDIV2 0 x y))
1141
1142 ;; if one of arg is constant, it's always x. see builtin-inline-bitwise below.
1143 (define (pass5/asm-bitwise info insn x y target renv ctx)
1144 (define lookup `((,LOGAND . ,LOGANDC)
1145 (,LOGIOR . ,LOGIORC)
1146 (,LOGXOR . ,LOGXORC)))
1147 (if ($const? x)
1148 (pass5/builtin-onearg+operand info (assv-ref lookup insn)
1149 0 ($const-value x) y)
1150 (pass5/builtin-twoargs info insn 0 x y)))
1151
1152 (define (pass5/asm-vec-ref info vec k target renv ctx)
1153 (cond [(and ($const? k)
1154 (unsigned-integer-fits-insn-arg? ($const-value k)))
1155 (pass5/builtin-onearg info VEC-REFI ($const-value k) vec)]
1156 [else
1157 (pass5/builtin-twoargs info VEC-REF 0 vec k)]))
1158
1159 (define (pass5/asm-vec-set info vec k obj target renv ctx)
1160 (cond [(and ($const? k)
1161 (unsigned-integer-fits-insn-arg? ($const-value k)))
1162 (pass5/builtin-twoargs info VEC-SETI ($const-value k) vec obj)]
1163 [else
1164 (let1 d0 (pass5/rec vec target renv (normal-context ctx))
1165 (compiled-code-emit-PUSH! (ctarget-ccb target))
1166 (let1 d1 (pass5/rec k target renv 'normal/top)
1167 (compiled-code-emit-PUSH! (ctarget-ccb target))
1168 (let1 d2 (pass5/rec obj target renv 'normal/top)
1169 (compiled-code-emit0i! (ctarget-ccb target) VEC-SET info)
1170 (imax d0 (+ d1 1) (+ d2 2)))))]))
1171
1172 (define (pass5/asm-slot-ref info obj slot target renv ctx)
1173 (cond [($const? slot)
1174 (rlet1 d (pass5/rec obj target renv (normal-context ctx))
1175 (compiled-code-emit0oi! (ctarget-ccb target)
1176 SLOT-REFC ($const-value slot) info))]
1177 [else
1178 (pass5/builtin-twoargs info SLOT-REF 0 obj slot)]))
1179
1180 (define (pass5/asm-slot-set info obj slot val target renv ctx)
1181 (cond [($const? slot)
1182 (let1 d0 (pass5/rec obj target renv (normal-context ctx))
1183 (compiled-code-emit-PUSH! (ctarget-ccb target))
1184 (let1 d1 (pass5/rec val target renv 'normal/top)
1185 (compiled-code-emit0oi! (ctarget-ccb target)
1186 SLOT-SETC ($const-value slot) info)
1187 (imax d0 (+ d1 1))))]
1188 [else
1189 (let1 d0 (pass5/rec obj target renv (normal-context ctx))
1190 (compiled-code-emit-PUSH! (ctarget-ccb target))
1191 (let1 d1 (pass5/rec slot target renv 'normal/top)
1192 (compiled-code-emit-PUSH! (ctarget-ccb target))
1193 (let1 d2 (pass5/rec val target renv 'normal/top)
1194 (compiled-code-emit0i! (ctarget-ccb target) SLOT-SET info)
1195 (imax d0 (+ d1 1) (+ d2 2)))))]))
1196
1197 ;; Dispatch table.
1198 (define *pass5-dispatch-table* (generate-dispatch-table pass5))
1199
1200 ;; Returns depth and offset of local variable reference.
1201 ;; renv-lookup : [[Lvar]], Lvar -> Int, Int
1202 ;;
1203 (inline-stub
1204 (define-cproc renv-lookup (renv lvar)
1205 (let* ([depth::int 0])
1206 (dolist [fp renv]
1207 (let* ([count::int 1])
1208 (dolist [lp fp]
1209 (when (SCM_EQ lp lvar)
1210 (return (values (SCM_MAKE_INT depth)
1211 (SCM_MAKE_INT (- (Scm_Length fp) count)))))
1212 (pre++ count)))
1213 (pre++ depth)))
1214 (Scm_Error "[internal error] stray local variable: %S" lvar)
1215 (return SCM_UNDEFINED)) ; dummy
1216 )
1217
1218 ;; Emit code to evaluate expressions in args and push its result
1219 ;; into the stack one by one. Returns the maximum depth of the stack.
1220 ;; lvars is #f for regular call sequence, or a list of lvars of the same
1221 ;; length of args for $LET or local calls.
1222 (define (pass5/prepare-args args target renv ctx)
1223 (if (null? args)
1224 0
1225 (let1 d (pass5/rec (car args) target renv (normal-context ctx))
1226 (compiled-code-emit-PUSH! (ctarget-ccb target))
1227 ;; NB: We check termination condition here. This routine is called
1228 ;; lots of times, and (length args) is usually small (<=2 covers almost
1229 ;; half of the cases, and <=3 covers over 80%). Check termination
1230 ;; condition before entering loop saves extra calculation of loop
1231 ;; arguments, and it is not negligible in this case.
1232 (if (null? (cdr args))
1233 d
1234 (let loop ([args (cdr args)]
1235 [depth (+ d 1)]
1236 [cnt 1])
1237 (let1 d (pass5/rec (car args) target renv 'normal/top)
1238 (compiled-code-emit-PUSH! (ctarget-ccb target))
1239 (if (null? (cdr args))
1240 (imax depth d)
1241 (loop (cdr args) (imax depth (+ d cnt 1)) (+ cnt 1)))))))))
1242
1243 ;; In case of $LET
1244 (define (pass5/box-mutable-lvars lvars ccb)
1245 (let1 envsize (length lvars)
1246 (let loop ([lvars lvars]
1247 [k 0])
1248 (unless (null? lvars)
1249 (unless (lvar-immutable? (car lvars))
1250 (compiled-code-emit1i! ccb BOX (- envsize k) (lvar-name (car lvars))))
1251 (loop (cdr lvars) (+ k 1))))))