| 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)) |