Debian Codegraph @

src/compile-2.scm

raw
1 ;;;
2 ;;; compile-2.scm - The compiler: Pass 2
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 2. Optimization stage 1
36 ;;
37
38 ;; Walk down IForm and perform optimizations.
39 ;; The main focus is to lift or inline closures, and eliminate
40 ;; local frames by beta reduction.
41 ;; This pass may modify the tree by changing IForm nodes destructively.
42
43 ;; Dispatch pass2 handler.
44 ;; Each handler is called with three arguments: the IForm, Penv, and Tail?
45 ;; Penv is a list of $LAMBDA nodes that we're compiling. It is used to
46 ;; detect self-recursive local calls. Tail? is a flag to indicate whether
47 ;; the expression is tail position or not.
48 ;; Each handler returns IForm.
49 ;; *pass2-dispatch-table* is defined below, after all handlers are defined.
50 (define-inline (pass2/rec iform penv tail?)
51 ((vector-ref *pass2-dispatch-table* (iform-tag iform))
52 iform penv tail?))
53
54 ;;
55 ;; Pass 2 entry point.
56 ;;
57 (define (pass2 iform) (pass2/rec iform '() #t))
58
59 ;;
60 ;; Pass 2 handlers
61 ;;
62
63 (define (pass2/$DEFINE iform penv tail?)
64 ($define-expr-set! iform (pass2/rec ($define-expr iform) penv #f))
65 iform)
66
67 ;; LREF optimization.
68 ;; Check if we can replace the $lref to its initial value.
69 ;; - If the lvar is never set!
70 ;; - if its init value is $const, just replace it
71 ;; - if its init value is $lref, replace it iff it is not set!,
72 ;; then repeat.
73 ;;
74 ;; There's a special LREF optimization when it appears in the operator
75 ;; position. If it is bound to $LAMBDA, we may be able to inline the
76 ;; lambda. It is dealt by pass2/head-lref, which is called by pass2/$CALL.
77
78 (define (pass2/$LREF iform penv tail?) (pass2/lref-eliminate iform))
79
80 (define (pass2/lref-eliminate iform)
81 (let1 lvar ($lref-lvar iform)
82 (if (lvar-immutable? lvar)
83 (let1 initval (lvar-initval lvar)
84 (cond [(not (vector? initval)) iform]
85 [($const? initval)
86 (lvar-ref--! lvar)
87 (vector-set! iform 0 $CONST)
88 ($const-value-set! iform ($const-value initval))
89 iform]
90 [(and ($lref? initval)
91 (lvar-immutable? ($lref-lvar initval)))
92 (when (eq? iform initval)
93 (error "circular reference appeared in letrec bindings:"
94 (lvar-name lvar)))
95 (lvar-ref--! lvar)
96 (lvar-ref++! ($lref-lvar initval))
97 ($lref-lvar-set! iform ($lref-lvar initval))
98 (pass2/lref-eliminate iform)]
99 ;; Generally we can't reorder $GREF, since it may change
100 ;; the semantics (the value of the variable may be altered,
101 ;; or it raises an unbound error). However, if $GREF refers to
102 ;; an inlinable binding, we can assume it is bound and its
103 ;; value won't be changed. NB: Constant bindings are already
104 ;; dissolved in pass1, so we don't need to consider it.
105 [(and (has-tag? initval $GREF)
106 (gref-inlinable-gloc initval))
107 (lvar-ref--! lvar)
108 (vector-set! iform 0 $GREF)
109 ($gref-id-set! iform ($gref-id initval))
110 iform]
111 [else iform]))
112 iform)))
113
114 (define (pass2/$LSET iform penv tail?)
115 ($lset-expr-set! iform (pass2/rec ($lset-expr iform) penv #f))
116 iform)
117
118 (define (pass2/$GREF iform penv tail?) iform)
119
120 (define (pass2/$GSET iform penv tail?)
121 ($gset-expr-set! iform (pass2/rec ($gset-expr iform) penv #f))
122 iform)
123
124 (define (pass2/$CONST iform penv tail?) iform)
125
126 (define (pass2/$IT iform penv tail?) iform)
127
128 (define (pass2/$IF iform penv tail?)
129 (let ([test-form (pass2/rec ($if-test iform) penv #f)]
130 [then-form (pass2/rec ($if-then iform) penv tail?)]
131 [else-form (pass2/rec ($if-else iform) penv tail?)])
132 (or (pass2/branch-cut iform test-form then-form else-form)
133 (pass2/update-if iform test-form then-form else-form))))
134
135 ;; NB: pass2/branch-cut and pass2/update-if are also called in pass3/$IF.
136 (define (pass2/branch-cut iform test-form then-form else-form)
137 (and ($const? test-form)
138 (let1 val-form (if ($const-value test-form) then-form else-form)
139 (if ($it? val-form) test-form val-form))))
140
141 (define (pass2/update-if iform new-test new-then new-else)
142 (if (eq? new-then new-else)
143 ($seq (list new-test new-then)) ;this case happens after pass3.
144 (begin ($if-test-set! iform new-test)
145 ($if-then-set! iform new-then)
146 ($if-else-set! iform new-else)
147 iform)))
148
149 ;; Let optimization:
150 ;;
151 ;; - Unused variable elimination: if the bound lvars becomes unused by
152 ;; the result of $lref optimization, we eliminate it from the frame,
153 ;; and move its 'init' expression to the body. if we're lucky, all
154 ;; the lvars introduced by this let are eliminated, and we can change
155 ;; this iform into a simple $seq.
156 ;;
157 ;; -- Special case: If the lvars are immediately "consumed" as the
158 ;; arguments to a function calls in the first expression of let,
159 ;; and the rest of the argument of the first expression is side-effect
160 ;; free, we can eliminate lvars. This case often occurs after macro
161 ;; expansion.
162 ;; (let ([p (f a)] [q (g b)]) (h p q) (foo))
163 ;; => (begin (h (f a) (g b)) (foo))
164 ;;
165 ;; NB: In the following pattern, we can't do the conversion unless p is
166 ;; constant or unmodified $LREF, for (g b) might modify p.
167 ;;
168 ;; (let ([q (g b)]) (h p q) (foo))
169 ;;
170 ;; NB: We don't need to consider the possibility that (g b) modifies h,
171 ;; since h is evaluated after all the arguments are evaluated, even
172 ;; in the form of (h p (g b)).
173 ;;
174 ;; - Closure optimization: when an lvar is bound to a $LAMBDA node, we
175 ;; may be able to optimize the calls to it. It is done here since
176 ;; we need to run pass2 for all the call sites of the lvar to analyze
177 ;; its usage.
178 ;;
179 ;; CAVEAT: When we go through pass2 on ($let-inits iform), it may inline expand
180 ;; lvars that appear later in the bindings, e.g.:
181 ;;
182 ;; (letrec ((foo (lambda () (bar x)))
183 ;; (bar (lambda (a) (baz a))))
184 ;; ...)
185 ;;
186 ;; In this case, while we're at pass2[(lambda () (bar x))], pass2/$CALL
187 ;; inlines the call of bar to make it (lambda () (let ((a x)) (baz a))).
188 ;; The important thing is that the IForm of original (lambda (a) (baz a))
189 ;; is directly used to inline the call, so we shouldn't rescan it.
190 ;; pass2/$CALL marks the inlined lambda node as 'used, so that we can skip
191 ;; it here.
192
193 (define (pass2/$LET iform penv tail?)
194 ;; Run pass2 on let-inits, returns new lvars and inits
195 (define (process-inits lvars inits)
196 (let loop ([lvars lvars] [inits inits]
197 [new-lvars '()] [new-inits '()])
198 (cond [(null? lvars) (values (reverse! new-lvars) (reverse! new-inits))]
199 [(let1 lv (car lvars)
200 (and (= (lvar-ref-count lv) 0)
201 (lvar-immutable? lv)
202 (has-tag? (car inits) $LAMBDA)
203 ($lambda-used? (car inits))))
204 ;; This lambda node has already been inlinded, so we can skip.
205 (loop (cdr lvars) (cdr inits) new-lvars new-inits)]
206 [(has-tag? (car inits) $CLAMBDA)
207 ;; We lift component closures of case-lamdba into local bindings,
208 ;; for easier closure optimization. The lifted local bindings
209 ;; are referred by the $CLAMBDA constructure, we force this
210 ;; $LET type to letrec, if it is not.
211 (receive (lifted-lvars lifted-lambdas)
212 (pass2/lift-clambda-closures (car inits) (car lvars))
213 (when (eq? ($let-type iform) 'let)
214 ($let-type-set! iform 'rec))
215 (loop (cdr lvars) (cdr inits)
216 (append (cons (car lvars) lifted-lvars) new-lvars)
217 (append (cons (pass2/rec (car inits) penv #f)
218 (imap (cut pass2/rec <> penv #f)
219 lifted-lambdas))
220 new-inits)))]
221 [else
222 (loop (cdr lvars) (cdr inits)
223 (cons (car lvars) new-lvars)
224 (cons (pass2/rec (car inits) penv #f) new-inits))])))
225
226 (receive (lvars inits) (process-inits ($let-lvars iform) ($let-inits iform))
227 (ifor-each2 (^[lv in] (lvar-initval-set! lv in)) lvars inits)
228 (let1 obody (pass2/rec ($let-body iform) penv tail?)
229 ;; NB: We have to run optimize-closure after pass2 of body.
230 (for-each pass2/optimize-closure lvars inits)
231 (pass2/shrink-let-frame iform lvars obody))))
232
233 ;; Called from pass2/$LET, when a local variable LVAR is bound to
234 ;; $CLAMBDA node. IFORM is the $CLAMBDA node.
235 ;; In this case, we lift its component closures to local varaibles,
236 ;; which allows furthre optimization.
237 ;; IForm is modified to refer to the LREFS instead of $LAMBDAs.
238 ;; Returns a list of newly introduced lvars and $LAMBDA nodes.
239 ;; NB: LVAR is only used to create names for generated lvars.
240 (define (pass2/lift-clambda-closures iform lvar)
241 (define prefix (symbol-append (lvar-name lvar) '-))
242 (define orig-lambdas ($clambda-closures iform))
243 (let loop ([i 0] [lvars '()] [lambdas orig-lambdas])
244 (if (null? lambdas)
245 (let1 lvars (reverse lvars)
246 ($clambda-closures-set! iform (imap $lref lvars))
247 (values lvars orig-lambdas))
248 (let1 new-lvar (make-lvar (symbol-append prefix i) (car lambdas))
249 (loop (+ i 1) (cons new-lvar lvars) (cdr lambdas))))))
250
251 (define (pass2/shrink-let-frame iform lvars obody)
252 (pass2/intermediate-lref-removal lvars obody)
253 (receive (new-lvars new-inits removed-inits)
254 (pass2/remove-unused-lvars lvars ($let-type iform))
255 (cond [(null? new-lvars)
256 (if (null? removed-inits)
257 obody
258 ($seq (append! removed-inits (list obody))))]
259 [else
260 ($let-lvars-set! iform new-lvars)
261 ($let-inits-set! iform new-inits)
262 ($let-body-set! iform obody)
263 (unless (null? removed-inits)
264 (if (has-tag? obody $SEQ)
265 ($seq-body-set! obody
266 (append! removed-inits ($seq-body obody)))
267 ($let-body-set! iform
268 ($seq (append removed-inits (list obody))))))
269 iform])))
270
271 ;; handle the special case in the above comment
272 (define (pass2/intermediate-lref-removal lvars body)
273 ;; returns the call node who has replacable intermediate lrefs, or #f if
274 ;; we can't do this transformation.
275 (define (intermediate-lrefs node lvars)
276 (let loop ([args ($call-args node)] [ilrefs '()] [subcall-node #f])
277 (match args
278 [() (if subcall-node
279 (and (null? ilrefs) (intermediate-lrefs subcall-node lvars))
280 (and (not (null? ilrefs)) node))]
281 [((? $const? n) . args) (loop args ilrefs subcall-node)]
282 [((? $lref? n) . args)
283 (let1 lv ($lref-lvar n)
284 (if (memq lv lvars)
285 (and (= (lvar-ref-count lv) 1)
286 (lvar-immutable? lv)
287 (loop args (cons n ilrefs) subcall-node))
288 (and (lvar-immutable? lv)
289 (loop args ilrefs subcall-node))))]
290 [((? $call? n) . args) (if subcall-node
291 #f
292 (loop args ilrefs n))]
293 [_ #f])))
294
295 (and-let* ([first-expr (if (has-tag? body $SEQ)
296 (and (not (null? ($seq-body body)))
297 (car ($seq-body body)))
298 body)]
299 [ (has-tag? first-expr $CALL) ]
300 [node (intermediate-lrefs first-expr lvars)])
301 ($call-args-set! node
302 (imap (^[arg] (if (and ($lref? arg)
303 (memq ($lref-lvar arg) lvars))
304 (rlet1 v (lvar-initval ($lref-lvar arg))
305 (lvar-ref--! ($lref-lvar arg))
306 (lvar-initval-set! ($lref-lvar arg)
307 ($const-undef)))
308 arg))
309 ($call-args node)))))
310
311 ;; Scan LVARS and returns three values:
312 ;; - List of needed lvars
313 ;; - List of init expressions, corresponding to the first return value.
314 ;; - List of non-transparent init expressions for removed lvars---they
315 ;; need to be executed at the top of the body of the binding construct.
316 ;;
317 ;; We have to be careful optimizing letrec* - we can't reorder init
318 ;; when it can have side effects. However, we still have to remove lambda
319 ;; form that is no longer used---that means the lambda form is inlined
320 ;; elsewhere, and its body has been modified to suit the inlined environment,
321 ;; so we can no longer compile the $lambda node safely.
322
323 ;; NB: By eliminating unused init expressions that contains LREF/LSET, the
324 ;; lvar reference count may change. However, traversing entire tree could
325 ;; be costly, so we only do adjustment for some trival cases---pass3 runs
326 ;; 'reset-lvars' which correctly sets lref count after pass2-3 optimizations.
327 ;; This is kludge, still, and it may turn out that we should do proper
328 ;; refcount adjustment here. We'll see.
329 (define (pass2/remove-unused-lvars lvars type)
330 (let loop ([lvars lvars] [rl '()] [ri '()] [rr '()])
331 (cond [(null? lvars)
332 (values (reverse rl) (reverse ri) (reverse rr))]
333 [(and (zero? (lvar-ref-count (car lvars)))
334 (lvar-immutable? (car lvars)))
335 (let1 init (lvar-initval (car lvars))
336 (if (and (eq? type 'rec*)
337 (not (transparent? init)))
338 (loop (cdr lvars) (cons (car lvars) rl) (cons init ri) rr)
339 (loop (cdr lvars) rl ri
340 (cond [($lref? init)
341 (lvar-ref--! ($lref-lvar init))
342 rr]
343 [(has-tag? init $CLAMBDA)
344 (ifor-each (lambda (c)
345 (when ($lref? c)
346 (lvar-ref--! ($lref-lvar c))))
347 ($clambda-closures init))]
348 [(transparent? init) rr]
349 [else (cons init rr)]))))]
350 [else
351 (loop (cdr lvars)
352 (cons (car lvars) rl)
353 (cons (lvar-initval (car lvars)) ri)
354 rr)])))
355
356 ;; Closure optimization (called from pass2/$LET)
357 ;;
358 ;; Determine the strategy to optimize each closure, and modify the nodes
359 ;; accordingly. We can't afford time to run iterative algorithm to find
360 ;; optimal strategy, so we take a rather simple-minded path to optimize
361 ;; common cases.
362 ;;
363 ;; By now, we have the information of all call sites of the statically
364 ;; bound closures. Each call site is marked as either REC, TAIL-REC
365 ;; or LOCAL. See explanation of pass2/$CALL below.
366 ;;
367 ;; Our objective is to categorize each call site to one of the following
368 ;; four options:
369 ;;
370 ;; LOCAL: when we can't avoid creating a closure, calls to it are marked
371 ;; as "local". The call to the local closure becomes a LOCAL-ENV-CALL
372 ;; instruction, which is faster than generic CALL/TAIL-CALL instructions.
373 ;;
374 ;; EMBED: the lambda body is inlined at the call site. It differs from
375 ;; the normal inlining in a way that we don't run beta-conversion of
376 ;; lrefs, since the body can be entered from other 'jump' call sites.
377 ;;
378 ;; JUMP: the call becomes a LOCAL-ENV-JUMP instruction, i.e. a jump
379 ;; to the lambda body which is generated by the 'embed' call.
380 ;;
381 ;; We can inline $LAMBDA if the following conditions are met:
382 ;;
383 ;; 1. The reference count of LVAR is equal to the number of call
384 ;; sites. This means all use of this $LAMBDA is first-order,
385 ;; so we know the closure won't "leak out".
386 ;;
387 ;; 2. It doesn't have any REC call sites, i.e. non-tail self recursive
388 ;; calls. (We may be able to convert non-tail self recursive calls
389 ;; to jump with environment adjustment, but it would complicates
390 ;; stack handling a lot.)
391 ;;
392 ;; 3. It doesn't have any TAIL-REC calls across closure boundary.
393 ;;
394 ;; (letrec ((foo (lambda (...)
395 ;; ..... (foo ...)) ;; ok
396 ;; ...
397 ;;
398 ;; (letrec ((foo (lambda (...) ....
399 ;; (lambda () ... (foo ...)) ;; not ok
400 ;; ...
401 ;;
402 ;; 4. Either:
403 ;; - It has only one LOCAL call, or
404 ;; - It doesn't have TAIL-REC calls and the body of $LAMBDA is
405 ;; small enough to duplicate.
406 ;;
407 ;; If we determine $LAMBDA to be inlined, all LOCAL calls become EMBED
408 ;; calls, and TAIL-RECs become JUMP.
409 ;;
410 ;; Otherwise, if the first condition is met, we can lift $LAMBDA to
411 ;; the toplevel by...
412 ;;
413 ;; a. Scan the lambda body to find free lvars. If there's any,
414 ;; transform free lvars to bound lvars by adding new arguments
415 ;; to the $LAMBDA node, and modifies all the call sites
416 ;; accordingly.
417 ;;
418 ;; Otherwise, all calls become LOCAL calls.
419 ;;
420
421 (define (pass2/optimize-closure lvar lambda-node)
422 (when (and (lvar-immutable? lvar)
423 (> (lvar-ref-count lvar) 0)
424 (has-tag? lambda-node $LAMBDA))
425 (or (and (= (lvar-ref-count lvar) (length ($lambda-calls lambda-node)))
426 (receive (locals recs tail-recs)
427 (pass2/classify-calls ($lambda-calls lambda-node) lambda-node)
428 (and (null? recs)
429 (pair? locals)
430 (or (and (null? (cdr locals))
431 (pass2/local-call-embedder lvar lambda-node
432 (car locals)
433 tail-recs))
434 (and (null? tail-recs)
435 (< (iform-count-size-upto lambda-node
436 SMALL_LAMBDA_SIZE)
437 SMALL_LAMBDA_SIZE)
438 (pass2/local-call-inliner lvar lambda-node
439 locals))))))
440 (pass2/local-call-optimizer lvar lambda-node))))
441
442 ;; Classify the calls into categories. TAIL-REC call is classified as
443 ;; REC if the call is across the closure boundary.
444 (define (pass2/classify-calls call&envs lambda-node)
445 (define (direct-call? env)
446 (let loop ([env env])
447 (cond [(null? env) #t]
448 [(eq? (car env) lambda-node) #t]
449 [($lambda-dissolved? (car env))
450 (loop (cdr env))] ;; skip dissolved (inlined) lambdas
451 [else #f])))
452 (let loop ([call&envs call&envs]
453 [local '()]
454 [rec '()]
455 [trec '()])
456 (match call&envs
457 [() (values local rec trec)]
458 [((call . env) . more)
459 (case ($call-flag call)
460 [(tail-rec) (if (direct-call? env)
461 (loop more local rec (cons call trec))
462 (loop more local (cons call rec) trec))]
463 [(rec) (loop more local (cons call rec) trec)]
464 [else (loop more (cons call local) rec trec)])])))
465
466 ;; Set up local calls to LAMBDA-NODE. Marking $call node as 'local
467 ;; lets pass5 to generate LOCAL-ENV-CALL instruction.
468 (define (pass2/local-call-optimizer lvar lambda-node)
469 (let ([nreqs ($lambda-reqargs lambda-node)]
470 [nopts ($lambda-optarg lambda-node)]
471 [name ($lambda-name lambda-node)]
472 [calls ($lambda-calls lambda-node)])
473 (dolist [call calls]
474 ($call-args-set! (car call) (adjust-arglist nreqs nopts
475 ($call-args (car call))
476 name))
477 ($call-flag-set! (car call) 'local))
478 ;; We clear the calls list, just in case if the lambda-node is
479 ;; traversed more than once.
480 ($lambda-calls-set! lambda-node '())
481 #t))
482
483 ;; Called when the local function (lambda-node) isn't needed to be a closure
484 ;; and can be embedded.
485 ;; NB: this operation introduces a shared/circular structure in the IForm.
486 (define (pass2/local-call-embedder lvar lambda-node call rec-calls)
487 (let ([nreqs ($lambda-reqargs lambda-node)]
488 [nopts ($lambda-optarg lambda-node)]
489 [name ($lambda-name lambda-node)])
490 ($call-args-set! call (adjust-arglist nreqs nopts ($call-args call) name))
491 (lvar-ref--! lvar)
492 ($call-flag-set! call 'embed)
493 ($call-proc-set! call lambda-node)
494 ($lambda-dissolved-set! lambda-node)
495 ($lambda-body-set! lambda-node ($label ($lambda-src lambda-node) #f
496 ($lambda-body lambda-node)))
497 (unless (null? rec-calls)
498 (dolist [jcall rec-calls]
499 (lvar-ref--! lvar)
500 ($call-args-set! jcall (adjust-arglist nreqs nopts ($call-args jcall)
501 name))
502 ($call-proc-set! jcall call)
503 ($call-flag-set! jcall 'jump)))
504 #t))
505
506 ;; Called when the local function (lambda-node) doesn't have recursive
507 ;; calls, can be inlined, and called from multiple places.
508 ;; NB: Here we destructively modify $call node to change it to $seq,
509 ;; in order to hold the $LET node. It breaks the invariance that $seq
510 ;; contains zero or two or more nodes---this may prevent Pass 5 from
511 ;; doing some optimization.
512 (define (pass2/local-call-inliner lvar lambda-node calls)
513 (define (inline-it call-node lambda-node)
514 (let1 inlined (expand-inlined-procedure ($*-src lambda-node) lambda-node
515 ($call-args call-node))
516 (vector-set! call-node 0 $SEQ)
517 (if (has-tag? inlined $SEQ)
518 ($seq-body-set! call-node ($seq-body inlined))
519 ($seq-body-set! call-node (list inlined)))))
520
521 (lvar-ref-count-set! lvar 0)
522 ($lambda-dissolved-set! lambda-node)
523 (let loop ([calls calls])
524 (cond [(null? (cdr calls))
525 (inline-it (car calls) lambda-node)
526 #t]
527 [else
528 (inline-it (car calls) (iform-copy lambda-node '()))
529 (loop (cdr calls))])))
530
531 (define (pass2/$RECEIVE iform penv tail?)
532 ($receive-expr-set! iform (pass2/rec ($receive-expr iform) penv #f))
533 ($receive-body-set! iform (pass2/rec ($receive-body iform) penv tail?))
534 iform)
535
536 (define (pass2/$LAMBDA iform penv tail?)
537 ($lambda-body-set! iform (pass2/rec ($lambda-body iform)
538 (cons iform penv) #t))
539 iform)
540
541 (define (pass2/$CLAMBDA iform penv tail?)
542 (let loop ([cs ($clambda-closures iform)] [r '()])
543 (if (null? cs)
544 (begin
545 ($clambda-closures-set! iform (reverse r))
546 iform)
547 (loop (cdr cs) (cons (pass2/rec (car cs) iform #f) r)))))
548
549 (define (pass2/$LABEL iform penv tail?)
550 ;; $LABEL's body should already be processed by pass2, so we don't need
551 ;; to do it again.
552 iform)
553
554 (define (pass2/$SEQ iform penv tail?)
555 (if (null? ($seq-body iform))
556 iform
557 (let loop ([body ($seq-body iform)]
558 [r '()])
559 (cond [(null? (cdr body))
560 ($seq-body-set! iform
561 (reverse (cons (pass2/rec (car body) penv tail?)
562 r)))
563 iform]
564 [else
565 (loop (cdr body)
566 (cons (pass2/rec (car body) penv #f) r))]))))
567
568 ;; Call optimization
569 ;; We try to inline the call whenever possible.
570 ;;
571 ;; 1. If proc is $LAMBDA or $CLAMBDA, we turn the whole struct into $LET.
572 ;;
573 ;; ($call ($lambda .. (LVar ...) Body) Arg ...)
574 ;; => ($let (LVar ...) (Arg ...) Body)
575 ;;
576 ;; 2. If proc is $LREF which is statically bound to a $LAMBDA,
577 ;; call pass2/head-lref to see if we can safely inline it.
578 ;;
579 ;; The second case has several subcases.
580 ;; 2a. Some $LAMBDA nodes can be directly inlined, e.g. the whole
581 ;; $CALL node can be turned into $LET node. The original $LAMBDA
582 ;; node vanishes if all the calls to the $LAMBDA node are first-order.
583 ;;
584 ;; ($call ($lref lvar0) Arg ...)
585 ;; where lvar0 => ($lambda .... (LVar ...) Body)
586 ;;
587 ;; => ($let (LVar ...) (Arg ...) Body)
588 ;;
589 ;; 2b. When $LAMBDA node is recursively called, or is called multiple
590 ;; times, we need more information to determine how to optimize it.
591 ;; So at this moment we just mark the $CALL node, and pushes
592 ;; it and the current penv to the 'calls' slot of the $LAMBDA node.
593 ;; After we finish Pass 2 of the scope of lvar0, we can know how to
594 ;; optimize the $LAMBDA node, and those $CALL nodes are revisited
595 ;; and modified accordingly.
596 ;;
597 ;; If the $CALL node is a non-recursive local call, the $CALL node
598 ;; is marked as 'local'. If it is a recursive call, it is marked
599 ;; as 'rec'.
600
601 (define (pass2/$CALL iform penv tail?)
602 (define (try-inline iform penv tail?) ;iform is $CALL node, proc already pass2'ed.
603 (let ([proc ($call-proc iform)]
604 [args ($call-args iform)])
605 (cond
606 [(has-tag? proc $LAMBDA) ; ((lambda (...) ...) arg ...)
607 (pass2/rec (expand-inlined-procedure ($*-src iform) proc args)
608 penv tail?)]
609 [(has-tag? proc $CLAMBDA) ; ((case-lambda ...) arg ...)
610 (and-let1 body (select-clambda-body proc args)
611 ($call-proc-set! iform body))
612 iform]
613 [(and ($lref? proc)
614 (lvar-const-value ($lref-lvar proc)))
615 => (^[initval]
616 (cond
617 [(has-tag? initval $LAMBDA)
618 ;; Calling $LREF bound constantly to $LAMBDA.
619 ;; If this is the only reference of $LAMBDA and
620 ;; not self-recursive, we can inline it.
621 (if-let1 call-flag (cond [(pass2/self-recursing? initval penv)
622 (if tail? 'tail-rec 'rec)]
623 [(= (lvar-ref-count ($lref-lvar proc)) 1)
624 #f]
625 [else 'local])
626 (begin
627 ($call-flag-set! iform call-flag)
628 ($lambda-calls-set! initval
629 (acons iform penv
630 ($lambda-calls initval)))
631 (pass2-args iform args penv))
632 (begin
633 (lvar-ref--! ($lref-lvar proc))
634 ($lambda-used-set! initval) ; let pass2/$LET skip this
635 ($call-proc-set! iform initval)
636 (try-inline iform penv tail?)))]
637 [else (pass2-args iform args penv)]))]
638 [else (pass2-args iform args penv)])))
639 (define (pass2-args iform args penv)
640 ($call-args-set! iform (imap (cut pass2/rec <> penv #f) args))
641 iform)
642
643 (if ($call-flag iform)
644 iform ;; this node has already been visited.
645 (begin
646 ;; scan OP first to give an opportunity of variable renaming
647 ($call-proc-set! iform (pass2/rec ($call-proc iform) penv #f))
648 (if (vm-compiler-flag-noinline-locals?)
649 (pass2-args iform ($call-args iform) penv) ; don't try to inline.
650 (try-inline iform penv tail?)))))
651
652 (define (pass2/self-recursing? node penv)
653 (find (cut eq? node <>) penv))
654
655 ;;
656 ;; DYNENV
657 ;;
658 (define (pass2/$DYNENV iform penv tail?)
659 (let ([key (pass2/rec ($dynenv-key iform) penv #f)]
660 [val (pass2/rec ($dynenv-value iform) penv #f)]
661 ;; We always evaluate EXPR as tail expr. EXTEND-DENV instruction
662 ;; pushes extra continuation.
663 [expr (pass2/rec ($dynenv-body iform) penv #t)])
664 (unless (and (eq? key ($dynenv-key iform))
665 (eq? val ($dynenv-value iform)))
666 ($dynenv-kvs-set! iform `(,key ,val ,@($dynenv-opts iform))))
667 ($dynenv-body-set! iform expr)
668 iform))
669
670 ;; Recognize the pattern like:
671 ;; ($let ([args ($LIST x y z ...)])
672 ;; ...
673 ;; ($asm (TAIL-APPLY n) proc ... a ... args))
674 ;; We can replace $asm node with a simple $CALL:
675 ;; ($call proc a ... x y z ...)
676 ;; This pattern typically appears after inline expansion.
677 ;;
678 ;; We only do this transformation if every x y z ... is either $lref
679 ;; or $const. If there's more complex expression, we can't change the order
680 ;; of evaluation, so we'd have to modify the outer $let form---which isn't
681 ;; trivial, so we just give up such a case.
682 ;;
683 ;; If the argument list is constructed (as opposed to be a constant),
684 ;; we also need to consider the possibility that the list can be mutated
685 ;; before passed to apply. We check if the intermediate variables are
686 ;; used elsewhere, and give up if they are passed to other procedures.
687 ;;
688 ;; IForm must be an $ASM node.
689 ;; Returns (potentially updated) iform.
690 (define (pass2/dissolve-apply iform penv tail?)
691 ;; Returns a list of arguments as list of IForms, or #f if the arguments
692 ;; isn't a proper list. We follow immutable local bindings.
693 (define (expand-restarg rarg)
694 (cond [($const? rarg)
695 (and (list? ($const-value rarg))
696 (imap (^v ($const v)) ($const-value rarg)))]
697 [($lref? rarg)
698 (and-let* ([lvar ($lref-lvar rarg)]
699 [val (lvar-const-value lvar)]
700 [r (expand-restarg val)])
701 ;; Record lvar. If we decide to dissolve, we need to adjust
702 ;; refcount of lvar later. (We can't do it now, for we may abandon
703 ;; inlining later.
704 (push! freed-lvars lvar)
705 r)]
706 [(has-tag? rarg $LIST) (check-safe ($list-args rarg))]
707 [(has-tag? rarg $CONS)
708 (and-let* ([ (safe? ($cons-arg0 rarg)) ]
709 [z (expand-restarg ($cons-arg1 rarg))])
710 (cons ($cons-arg0 rarg) z))]
711 [(has-tag? rarg $LIST*)
712 (and-let* ([z (expand-restarg (last ($list*-args rarg)))]
713 [y (check-safe (drop-right ($list*-args rarg) 1))])
714 (append y z))]
715 [(has-tag? rarg $ASM)
716 (case/unquote
717 (car ($asm-insn rarg))
718 [(LIST) (check-safe ($asm-args rarg))]
719 [(LIST-STAR)
720 (and-let* ([z (expand-restarg (last ($asm-args rarg)))]
721 [y (check-safe (drop-right ($asm-args rarg) 1))])
722 (append y z))]
723 [else #f])]
724 [else #f]))
725 (define freed-lvars '())
726 (define (safe? x) (or ($lref? x) ($const? x)))
727 (define (check-safe xs) ;; returns xs or #f
728 (cond [(null? xs) xs]
729 [(safe? (car xs)) (and-let1 z (check-safe (cdr xs))
730 (cons (car xs) z))]
731 [else #f]))
732 (define args ($asm-args iform))
733 (assume (length>=? args 2))
734 (if (vm-compiler-flag-is-set? SCM_COMPILE_NODISSOLVE_APPLY)
735 iform
736 (or (and-let* ([iargs (expand-restarg (last args))]
737 [ (every (^v (= (lvar-ref-count v) 1)) freed-lvars) ])
738 (ifor-each lvar-ref--! freed-lvars)
739 (ifor-each (^x (when ($lref? x) (lvar-ref++! ($lref-lvar x)))) iargs)
740 (pass2/rec ($call ($*-src iform) (car args)
741 (append (drop-right (cdr args) 1) iargs))
742 penv tail?))
743 iform)))
744
745 (define (pass2/$ASM iform penv tail?)
746 (define (do-asm)
747 ($ pass2/check-constant-asm iform
748 (imap (cut pass2/rec <> penv #f) ($asm-args iform))))
749 (if (eqv? (car ($asm-insn iform)) TAIL-APPLY)
750 (let1 iform2 (pass2/dissolve-apply iform penv tail?)
751 (if (eq? iform iform2) ; didn't resolve
752 (do-asm)
753 iform2))
754 (do-asm)))
755
756 (define (pass2/check-constant-asm iform args)
757 (or (and (every $const? args)
758 (case/unquote
759 (car ($asm-insn iform))
760 [(NOT) (pass2/const-pred not args)]
761 [(NULLP) (pass2/const-pred null? args)]
762 [(PAIRP) (pass2/const-pred pair? args)]
763 [(CHARP) (pass2/const-pred char? args)]
764 [(STRINGP) (pass2/const-pred string? args)]
765 [(VECTORP) (pass2/const-pred vector? args)]
766 [(NUMBERP) (pass2/const-pred number? args)]
767 [(REALP) (pass2/const-pred real? args)]
768 [(CAR) (pass2/const-cxr car args)]
769 [(CDR) (pass2/const-cxr cdr args)]
770 [(CAAR) (pass2/const-cxxr car caar args)]
771 [(CADR) (pass2/const-cxxr cdr cadr args)]
772 [(CDAR) (pass2/const-cxxr car cdar args)]
773 [(CDDR) (pass2/const-cxxr cdr cddr args)]
774 [(MEMQ) (pass2/const-memx memq args)]
775 [(MEMV) (pass2/const-memx memv args)]
776 [(ASSQ) (pass2/const-memx assq args)]
777 [(ASSV) (pass2/const-memx assv args)]
778 [(VEC-REF) (pass2/const-vecref args)]
779 [(VEC-LEN) (pass2/const-veclen args)]
780 [(EQ) (pass2/const-op2 eq? args)]
781 [(EQV) (pass2/const-op2 eqv? args)]
782 [(NUMEQ2) (pass2/const-numop2 = args)]
783 [(NUMADD2) (pass2/const-numop2 + args)]
784 [(NUMSUB2) (pass2/const-numop2 - args)]
785 [(NUMMUL2) (pass2/const-numop2 * args)]
786 [(NUMDIV2) (pass2/const-numop2 / args)]
787 [(NEGATE) (pass2/const-numop1 - args)]
788 [else #f]))
789 (and-let* ([ (pair? args) ]
790 [ (null? (cdr args)) ]
791 [ ($lref? (car args)) ]
792 [lvar ($lref-lvar (car args))]
793 [initval (lvar-const-value lvar)])
794 (case/unquote
795 (car ($asm-insn iform))
796 [(NULLP) (and (initval-never-null? initval)
797 (begin (lvar-ref--! lvar) ($const-f)))]
798 [(NOT) (and (initval-never-false? initval)
799 (begin (lvar-ref--! lvar) ($const-f)))]
800 [(PAIRP) (and (initval-always-pair? initval)
801 (begin (lvar-ref--! lvar) ($const-t)))]
802 [else #f]))
803 (begin ($asm-args-set! iform args) iform)))
804
805 (define (pass2/const-pred pred args)
806 (if (pred ($const-value (car args))) ($const-t) ($const-f)))
807
808 (define (pass2/const-cxr proc args)
809 (let1 v ($const-value (car args))
810 (and (pair? v) ($const (proc v)))))
811
812 (define (pass2/const-cxxr proc0 proc args)
813 (let1 v ($const-value (car args))
814 (and (pair? v) (pair? (proc0 v)) ($const (proc v)))))
815
816 (define (pass2/const-memx proc args)
817 (let ([item ($const-value (car args))]
818 [lis ($const-value (cadr args))])
819 (and (list? lis) ($const (proc item lis)))))
820
821 (define (pass2/const-op2 proc args)
822 ($const (proc ($const-value (car args)) ($const-value (cadr args)))))
823
824 (define (pass2/const-numop1 proc args)
825 (let1 n ($const-value (car args))
826 (and (number? n)
827 (not (and (eq? proc /) (eqv? y 0))) ; don't fold zero-division case
828 ($const (proc n)))))
829
830 (define (pass2/const-numop2 proc args)
831 (let ([x ($const-value (car args))]
832 [y ($const-value (cadr args))])
833 (and (number? x) (number? y)
834 (not (and (eq? proc /) (exact? x) (eqv? y 0))) ; ditto
835 ($const (proc x y)))))
836
837 (define (pass2/const-vecref args) ;args has always 2 elements
838 (let ([v ($const-value (car args))]
839 [i ($const-value (cadr args))])
840 (and (vector? v) (exact? i) (integer? i) (< -1 i (vector-length v))
841 ($const (vector-ref v i)))))
842
843 (define (pass2/const-veclen args)
844 (let1 v ($const-value (car args))
845 (and (vector? v) ($const (vector-length v)))))
846
847 (define (initval-never-null? val)
848 (and (vector? val)
849 (let1 tag (iform-tag val)
850 (or (and (eqv? tag $LIST) (not (null? ($*-args val))))
851 (and (eqv? tag $LIST*) (not (null? ($*-args val))))
852 (memv tag `(,$LAMBDA ,$CONS ,$EQ? ,$EQV?
853 ,$VECTOR ,$LIST->VECTOR))))))
854
855 (define (initval-never-false? val)
856 (and (vector? val)
857 (let1 tag (iform-tag val)
858 (memv tag `(,$LAMBDA ,$CONS ,$VECTOR
859 ,$LIST->VECTOR ,$LIST)))))
860
861 (define (initval-always-pair? val)
862 (and (vector? val)
863 (or (has-tag? val $CONS)
864 (and (has-tag? val $LIST)
865 (pair? ($*-args val)))
866 (and (has-tag? val $LIST*)
867 (pair? ($*-args val))
868 (pair? (cdr ($*-args val)))))))
869
870 (define (initval-always-procedure? val)
871 (and (vector? val) (has-tag? val $LAMBDA)))
872
873 (define (pass2/onearg-inliner iform penv tail?)
874 ($*-arg0-set! iform (pass2/rec ($*-arg0 iform) penv #f))
875 iform)
876
877 (define pass2/$LIST->VECTOR pass2/onearg-inliner)
878
879 (define (pass2/twoarg-inliner iform penv tail?)
880 ($*-arg0-set! iform (pass2/rec ($*-arg0 iform) penv #f))
881 ($*-arg1-set! iform (pass2/rec ($*-arg1 iform) penv #f))
882 iform)
883
884 (define pass2/$CONS pass2/twoarg-inliner)
885 (define pass2/$APPEND pass2/twoarg-inliner)
886 (define pass2/$MEMV pass2/twoarg-inliner)
887 (define pass2/$EQ? pass2/twoarg-inliner)
888 (define pass2/$EQV? pass2/twoarg-inliner)
889
890 (define (pass2/narg-inliner iform penv tail?)
891 ($*-args-set! iform (imap (cut pass2/rec <> penv #f) ($*-args iform)))
892 iform)
893
894 (define pass2/$LIST pass2/narg-inliner)
895 (define pass2/$LIST* pass2/narg-inliner)
896 (define pass2/$VECTOR pass2/narg-inliner)
897
898 ;; Dispatch table.
899 (define *pass2-dispatch-table* (generate-dispatch-table pass2))