Debian Codegraph @

src/compile-3.scm

raw
1 ;;;
2 ;;; compile-3.scm - The compiler: Pass 3
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 3. Optimization stage 2
36 ;;
37
38 ;; Closure optimization can introduce superfluous $LET, which can
39 ;; be optimized further. (In fact, pass2 and pass3 can be repeated
40 ;; until no further optimization can be possible. However, compilation
41 ;; speed is also important for Gauche, so we just run this pass once.)
42
43 ;; Dispatch pass3 handler.
44 ;; Each handler is called with IForm and a list of label nodes.
45 ;; Returns IForm.
46 ;; *pass3-dispatch-table* is defined below, after all handlers are defined.
47 (define-inline (pass3/rec iform labels)
48 ((vector-ref *pass3-dispatch-table* (iform-tag iform)) iform labels))
49
50 ;; Pass 3 entry point
51 ;; This pass may prune the subtree of iform because of constant
52 ;; folding. It may further allow pruning of other subtrees. So, when
53 ;; pruning occurs, pass3 records the fact by setting label-dic-info to #t.
54 ;; We repeat the pass then.
55
56 (define (pass3 iform show?)
57 (if (vm-compiler-flag-no-post-inline?)
58 iform
59 (let loop ([iform iform] [count 0])
60 (when show? (pass3-dump iform count))
61 (let* ([label-dic (make-label-dic #f)]
62 [iform. (pass3/rec (reset-lvars iform) label-dic)])
63 (if (label-dic-info label-dic)
64 (loop iform. (+ count 1))
65 iform.)))))
66
67 (define (pass3-dump iform count)
68 (format #t "~78,,,'=a\n" #"pass3 #~count ")
69 (pp-iform iform))
70
71 ;;
72 ;; Pass 3 handlers
73 ;;
74
75 (define (pass3/$DEFINE iform labels)
76 ($define-expr-set! iform (pass3/rec ($define-expr iform) labels))
77 iform)
78
79 (define (pass3/$LREF iform labels) (pass2/lref-eliminate iform))
80
81 (define (pass3/$LSET iform labels)
82 ($lset-expr-set! iform (pass3/rec ($lset-expr iform) labels))
83 iform)
84
85 (define (pass3/$GREF iform labels) iform)
86
87 (define (pass3/$GSET iform labels)
88 ($gset-expr-set! iform (pass3/rec ($gset-expr iform) labels))
89 iform)
90
91 (define (pass3/$CONST iform labels) iform)
92 (define (pass3/$IT iform labels) iform)
93
94 (define (pass3/$DYNENV iform labels)
95 (let ([key (pass3/rec ($dynenv-key iform) labels)]
96 [val (pass3/rec ($dynenv-value iform) labels)]
97 [expr (pass3/rec ($dynenv-body iform) labels)])
98 (unless (and (eq? key ($dynenv-key iform))
99 (eq? val ($dynenv-value iform)))
100 ($dynenv-kvs-set! iform `(,key ,val ,@($dynenv-opts iform))))
101 ($dynenv-body-set! iform expr)
102 iform))
103
104 ;; If optimization:
105 ;;
106 ;; If the 'test' clause of $IF node contains another $IF that has $IT in
107 ;; either then or else clause, the straightforward code generation emits
108 ;; redundant jump/branch instructions. We translate the tree into
109 ;; an acyclic directed graph:
110 ;;
111 ;; ($if ($if <t0> ($it) <e0>) <then> <else>)
112 ;; => ($if <t0> #0=($label L0 <then>) ($if <e0> #0# <else>))
113 ;;
114 ;; ($if ($if <t0> <e0> ($it)) <then> <else>)
115 ;; ($if ($if <t0> <e0> ($const #f)) <then> <else>)
116 ;; => ($if <t0> ($if <e0> <then> #0=($label L0 <else>)) #0#)
117 ;;
118 ;; ($if ($if <t0> ($const #f) <e0>) <then> <else>)
119 ;; => ($if <t0> #0=($label L0 <else>) ($if <e0> <then> #0#))
120 ;; iff <else> != ($it)
121 ;; => ($if <t0> ($const #f) ($if <e0> <then> ($it)))
122 ;; iff <else> == ($it)
123 ;;
124 ;; NB: If <then> or <else> clause is simple enough, we just duplicate
125 ;; it instead of creating $label node. It is not only for optimization,
126 ;; but crucial when the clause is ($IT), since it affects the Pass5
127 ;; code generation stage.
128 ;;
129 ;; NB: The latter two patterns may seem contrived, but it appears
130 ;; naturally in the 'cond' clause, e.g. (cond ((some-condition?) #f) ...)
131 ;; or (cond .... (else #f)).
132 ;;
133 ;; ($if <t0> #0=($label ...) #0#)
134 ;; => ($seq <t0> ($label ...))
135 ;;
136 ;; This form may appear as the result of if optimization.
137
138 (define (pass3/$IF iform labels)
139 (let ([test-form (pass3/rec ($if-test iform) labels)]
140 [then-form (pass3/rec ($if-then iform) labels)]
141 [else-form (pass3/rec ($if-else iform) labels)])
142 (or (and-let* ([r (pass2/branch-cut iform test-form then-form else-form)])
143 (label-dic-info-set! labels #t) ; mark that we cut a branch
144 r)
145 (and
146 (has-tag? test-form $IF)
147 (let ([test-then ($if-then test-form)]
148 [test-else ($if-else test-form)])
149 (cond [($it? test-then)
150 (receive (l0 l1) (pass3/label-or-dup then-form)
151 (pass2/update-if iform ($if-test test-form)
152 l0
153 (pass3/rec ($if #f test-else l1 else-form)
154 labels)))]
155 [(or ($it? test-else)
156 (and ($const? test-else)
157 (not ($const-value test-else))))
158 (receive (l0 l1) (pass3/label-or-dup else-form)
159 (pass2/update-if iform ($if-test test-form)
160 (pass3/rec ($if #f test-then then-form l0)
161 labels)
162 l1))]
163 [(and ($const? test-then)
164 (not ($const-value test-then)))
165 (receive (l0 l1) (pass3/label-or-dup else-form)
166 (pass2/update-if iform ($if-test test-form)
167 (if ($it? l0) ($const-f) l0)
168 (pass3/rec ($if #f test-else then-form l1)
169 labels)))]
170 [else #f])))
171 ;; default case
172 (pass2/update-if iform test-form then-form else-form))))
173
174 (define (pass3/label-or-dup iform)
175 (if (memv (iform-tag iform) `(,$LREF ,$CONST ,$IT))
176 (values iform (iform-copy iform '()))
177 (let1 lab ($label #f #f iform)
178 (values lab lab))))
179
180 (define (pass3/$LET iform labels)
181 (let ([lvars ($let-lvars iform)]
182 [inits (imap (cut pass3/rec <> labels) ($let-inits iform))])
183 (ifor-each2 (^[lv in] (lvar-initval-set! lv in)) lvars inits)
184 (pass2/shrink-let-frame iform lvars (pass3/rec ($let-body iform) labels))))
185
186 (define (pass3/$RECEIVE iform labels)
187 ;; There's a common idiom of "save the result, do something, then return
188 ;; the result." Considering that the result may be more than one value,
189 ;; it takes this pattern, frequently generated by macros:
190 ;;
191 ;; (receive var expr
192 ;; .... do something without var
193 ;; (apply values var))
194 ;;
195 ;; This incurs overhead of packing and unpacking multiple values, especially
196 ;; if expr yields only one value, which is majority of the case.
197 ;; If we know expr can only yield single value, we can simplify it with
198 ;; the following:
199 ;;
200 ;; (let ((var expr))
201 ;; .... do something without var...
202 ;; var)
203 ;;
204
205 ;; #t iff we definitely know iform yields a single value.
206 (define (single-value-iform? iform)
207 (or (memv (iform-tag iform)
208 `(,$CONST ,$LREF ,$GREF ,$LAMBDA ,$CONS ,$APPEND ,$VECTOR
209 ,$LIST->VECTOR ,$LIST ,$LIST* ,$MEMV ,$EQ? ,$EQV?))
210 (and (has-tag? iform $IF)
211 (single-value-iform? ($if-then iform))
212 (single-value-iform? ($if-else iform)))
213 (and (has-tag? iform $ASM)
214 (not (insn-multi-value? (car ($asm-insn iform)))))
215 ))
216
217 ;; first, do the business in the subtree.
218 ($receive-expr-set! iform (pass3/rec ($receive-expr iform) labels))
219 ($receive-body-set! iform (pass3/rec ($receive-body iform) labels))
220 ;; see if we can optimize
221 (or (and-let* ([ (= ($receive-reqargs iform) 0) ]
222 [ (= ($receive-optarg iform) 1) ]
223 [lvar (car ($receive-lvars iform))]
224 [ (= (lvar-ref-count lvar) 1) ]
225 [ (single-value-iform? ($receive-expr iform)) ]
226 [body ($receive-body iform)]
227 [ (has-tag? body $SEQ) ]
228 [last-expr (last ($seq-body body))]
229 [ (has-tag? last-expr $ASM) ]
230 [ (eq? (car ($asm-insn last-expr)) TAIL-APPLY) ]
231 [last-args ($asm-args last-expr)]
232 [ (length=? last-args 2) ]
233 [ (has-tag? (car last-args) $GREF) ]
234 [ (free-identifier=? ($gref-id (car last-args)) values.)]
235 [ ($lref? (cadr last-args)) ]
236 [ (eq? ($lref-lvar (cadr last-args)) lvar) ]
237 )
238 ;; OK, we can.
239 (let ([newbody ($seq (append (drop-right ($seq-body body) 1)
240 (cdr last-args)))]) ;; $LREF
241 (pass3/rec ($let ($receive-src iform)
242 'let
243 (list lvar)
244 (list ($receive-expr iform))
245 newbody)
246 labels)))
247 iform))
248
249 (define (pass3/$LAMBDA iform labels)
250 ($lambda-body-set! iform (pass3/rec ($lambda-body iform) labels))
251 iform)
252
253 (define (pass3/$CLAMBDA iform labels)
254 (let loop ([cs ($clambda-closures iform)] [r '()])
255 (if (null? cs)
256 (begin
257 ($clambda-closures-set! iform (reverse r))
258 iform)
259 (loop (cdr cs) (cons (pass3/rec (car cs) labels) r)))))
260
261 (define (pass3/$LABEL iform labels)
262 (unless (label-seen? labels iform)
263 (label-push! labels iform)
264 ($label-body-set! iform (pass3/rec ($label-body iform) labels)))
265 iform)
266
267 ;; We may have a dead code in $SEQ as the result of pass2 main.
268 ;; We eliminate if the value of subtree is not used, and it is
269 ;; referentially transparent.
270 (define (pass3/$SEQ iform labels)
271 (let1 xs ($seq-body iform)
272 (if (null? xs)
273 iform
274 (let loop ([r '()] [xs xs])
275 (match xs
276 [(x) (cond [(null? r) (pass3/rec x labels)]
277 [else
278 ($seq-body-set! iform
279 (reverse! (cons (pass3/rec x labels) r)))
280 iform])]
281 [(x . (and (y . ys) xs))
282 ;; Skip empty $seq if it immediately follows x.
283 ;; This prevents the constant expression followed by empty $seq as
284 ;; the last expression from being removed as the dead code.
285 (if (and (has-tag? y $SEQ) (null? ($seq-body y)))
286 (loop r (cons x ys))
287 (let1 x. (pass3/rec x labels)
288 (loop (if (transparent? x.) r (cons x. r)) xs)))])))))
289
290 ;; Some extra optimization on $CALL. We need to run this here, since
291 ;; $CALL classifications needs to be done by the surrounding $LET.
292 ;; That is:
293 ;; pass2 root -> leaf : gather call sites
294 ;; pass2 leaf -> root : classify calls and dissolve some closures
295 ;; pass3 root -> leaf : call optimization; *we are here*
296
297 (define (pass3/$CALL iform labels)
298 ($call-args-set! iform (imap (cut pass3/rec <> labels) ($call-args iform)))
299 (case ($call-flag iform)
300 [(jump) iform]
301 [(embed) ($call-proc-set! iform (pass3/rec ($call-proc iform) labels))
302 iform]
303 [else (pass3/optimize-call iform labels)]))
304
305 (define (pass3/optimize-call iform labels)
306 (let ([proc (pass3/rec ($call-proc iform) labels)]
307 [args ($call-args iform)])
308 (cond [;; If we get ($call ($let (...) body) args ...), we transform it
309 ;; to ($let (...) ($call body args...)). This may allow further
310 ;; optimization.
311 (has-tag? proc $LET)
312 (let loop ([node proc]
313 [body ($let-body proc)])
314 (cond [(has-tag? body $LET) (loop body ($let-body body))]
315 [else ($call-proc-set! iform body)
316 ($let-body-set! node iform)
317 (pass3/$LET proc labels)]))]
318 [;; As the result of above opration, we may get a direct lambda
319 ;; call ($call ($lambda ...) args ...)
320 (has-tag? proc $LAMBDA)
321 (pass3/inline-call iform proc args labels)]
322 [;; Similar to above, but ($call ($seq ... ($lambda ..)) args ...)
323 ;; We can convert it ot ($seq ... ($call ($lamba ...) args...))
324 (and (has-tag? proc $SEQ)
325 (has-tag? (last ($seq-body proc)) $LAMBDA))
326 (pass3/$SEQ ($seq `(,@(drop-right ($seq-body proc) 1)
327 ,($call ($*-src iform)
328 (last ($seq-body proc)) ;$lambda
329 ($call-args iform)
330 ($call-flag iform))))
331 labels)]
332 [;; If we get ($call ($gref proc) args ...) and proc is inlinable,
333 ;; we can inline the call.
334 (and-let* ([ (has-tag? proc $GREF) ]
335 [p (gref-inlinable-proc proc)])
336 (or (and (%procedure-inliner p)
337 (pass3/late-inline iform proc p labels))
338 (and-let* ([ (procedure-constant? p) ]
339 [constargs (pass3/constant-arguments args)])
340 (pass3/precompute-constant p constargs))))]
341 [(and-let* ([ (has-tag? proc $GREF) ]
342 [ (pair? args) ]
343 [ (null? (cdr args)) ]
344 [val (if ($lref? (car args))
345 (lvar-const-value ($lref-lvar (car args)))
346 (car args))])
347 (pass3/deduce-predicate-result proc val))]
348 [;; Like above, but we follow $LREFs.
349 ;; NB: We tempted to inline calls if the $lref is bound to $lambda
350 ;; node and it has reference count 1---in a non-redundant program,
351 ;; it means the $lambda is no recursive call. Unfortunately it
352 ;; breaks when $lambda does have recursive call to itself, and
353 ;; the whole $lambda node isn't referenced from anywhere else.
354 ;; Such unused $lambda node would be removed later, but it
355 ;; introduces loop in the graph which confuses this pass.
356 (and-let* ([ ($lref? proc) ]
357 [lvar ($lref-lvar proc)]
358 [val (lvar-const-value lvar)]
359 [ (has-tag? val $GREF) ]
360 [p (gref-inlinable-proc val)]
361 [ (%procedure-inliner p) ])
362 (rlet1 iform. (pass3/late-inline iform val p labels)
363 (when iform. (lvar-ref--! lvar))))]
364 [else ($call-proc-set! iform proc) iform])))
365
366 ;; Returns GLOC if gref refers to an inlinable binding
367 (define (gref-inlinable-gloc gref)
368 (and-let* ([gloc (id->bound-gloc ($gref-id gref))]
369 [ (gloc-inlinable? gloc) ])
370 gloc))
371
372 ;; Get the value of GREF if it is bound and inlinable procedure
373 (define (gref-inlinable-proc gref)
374 (and-let* ([gloc (gref-inlinable-gloc gref)]
375 [val (gloc-ref gloc)]
376 [ (procedure? val) ])
377 val))
378
379 ;; Get the constant or inlinable value for each iform in the list; if
380 ;; we can't get such value from any one, returns #f.
381 (define (pass3/constant-arguments iforms)
382 (let loop ([iforms iforms] [args '()])
383 (cond
384 [(null? iforms) (reverse args)]
385 [($const? (car iforms))
386 (loop (cdr iforms) (cons ($const-value (car iforms)) args))]
387 [(has-tag? (car iforms) $GREF)
388 (and-let1 gloc (gref-inlinable-gloc (car iforms))
389 (loop (cdr iforms) (cons (gloc-ref gloc) args)))]
390 [else #f])))
391
392 ;; An ad-hoc table of builtin predicates that we can deduce its value
393 ;; from what we know about its argument at compile-time. Even the argument
394 ;; is not a constant, we sometimes know its type and thus we know how
395 ;; the predicate responds. Ideally, this information should be attached
396 ;; to individual procedures, instead of keeping it in the compiler. For now,
397 ;; however, we don't know how to show our internal information to such
398 ;; custom handlers.
399
400 (define (pass3/pred:null? val)
401 (and (initval-never-null? val) ($const-f)))
402 (define (pass3/pred:not val)
403 (and (initval-never-false? val) ($const-f)))
404 (define (pass3/pred:pair? val)
405 (and (initval-always-pair? val) ($const-t)))
406 (define (pass3/pred:procedure? val)
407 (and (initval-always-procedure? val) ($const-t)))
408 (define (pass3/pred:fallback val) #f)
409
410 (define *pass3/pred-table*
411 `((,(global-id 'null?) . ,pass3/pred:null?)
412 (,(global-id 'not) . ,pass3/pred:not)
413 (,(global-id 'pair?) . ,pass3/pred:pair?)
414 (,(global-id 'procedure?) . ,pass3/pred:procedure?)))
415
416 (define (pass3/find-deducible-predicate id)
417 (let loop ([tab *pass3/pred-table*])
418 (cond [(null? tab) pass3/pred:fallback]
419 [(global-identifier=? id (caar tab)) (cdar tab)]
420 [else (loop (cdr tab))])))
421
422 (define (pass3/deduce-predicate-result gref arg)
423 ((pass3/find-deducible-predicate ($gref-id gref)) arg))
424
425 (define (pass3/inline-call call-node proc args labels)
426 ;; This inlining may enable further inlining by post pass again.
427 (label-dic-info-set! labels #t)
428 (expand-inlined-procedure ($call-src call-node) proc args))
429
430 ;; TODO: This is similar to pass1/expand-inliner. Call for refactoring.
431 (define (pass3/late-inline call-node gref-node proc labels)
432 (let ([inliner (%procedure-inliner proc)]
433 [src ($call-src call-node)])
434 (match inliner
435 [(? integer?) ; VM instruction
436 (let ([nargs (length ($call-args call-node))]
437 [opt? (slot-ref proc 'optional)])
438 (unless (argcount-ok? ($call-args call-node)
439 (slot-ref proc 'required) opt?)
440 (errorf "wrong number of arguments: ~a requires ~a, but got ~a"
441 (variable-name ($gref-id gref-node))
442 (slot-ref proc 'required) nargs))
443 ($asm src (if opt? `(,inliner ,nargs) `(,inliner))
444 ($call-args call-node)))]
445 [(? vector?)
446 (pass3/inline-call call-node (unpack-iform inliner)
447 ($call-args call-node) labels)]
448 [(? procedure?)
449 (let1 r (inliner src ($call-args call-node))
450 (and (not (undefined? r)) r))]
451 [_ #f])))
452
453 ;; PROC is inlinable, constant procedure, and args-node is all $const node.
454 ;; So we can precompute the value and replace the $call node to a single
455 ;; $const node. One caveat: the application may yield an error, but if
456 ;; we let the compiler fail, it will be confusing since even a call in
457 ;; a dead code can be the cause. So if we get an error, we give up this
458 ;; optimization and let the runtime fail.
459 (define (pass3/precompute-constant proc args)
460 (guard (e [else #f]) ; give up optimization
461 (receive r (apply proc args)
462 (match r
463 [() ($const-undef)]
464 [(r) ($const r)]
465 [_ #f])))) ;for now, don't support multivalue const
466
467 (define (pass3/$ASM iform labels)
468 (let1 args (imap (cut pass3/rec <> labels) ($asm-args iform))
469 (pass2/check-constant-asm iform args)))
470
471 (define (pass3/onearg-inliner iform labels)
472 ($*-arg0-set! iform (pass3/rec ($*-arg0 iform) labels))
473 iform)
474 (define pass3/$LIST->VECTOR pass3/onearg-inliner)
475
476 (define (pass3/twoarg-inliner iform labels)
477 ($*-arg0-set! iform (pass3/rec ($*-arg0 iform) labels))
478 ($*-arg1-set! iform (pass3/rec ($*-arg1 iform) labels))
479 iform)
480 (define pass3/$CONS pass3/twoarg-inliner)
481 (define pass3/$APPEND pass3/twoarg-inliner)
482 (define pass3/$MEMV pass3/twoarg-inliner)
483 (define pass3/$EQ? pass3/twoarg-inliner)
484 (define pass3/$EQV? pass3/twoarg-inliner)
485
486 (define (pass3/narg-inliner iform labels)
487 ($*-args-set! iform (imap (cut pass3/rec <> labels) ($*-args iform)))
488 iform)
489 (define pass3/$LIST pass3/narg-inliner)
490 (define pass3/$LIST* pass3/narg-inliner)
491 (define pass3/$VECTOR pass3/narg-inliner)
492
493 ;; Dispatch table.
494 (define *pass3-dispatch-table* (generate-dispatch-table pass3))