| 1 |
;;; |
| 2 |
;;; compile-4.scm - The compiler: Pass 4 |
| 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 4. Lambda lifting |
| 36 |
;; |
| 37 |
|
| 38 |
;; First we traverse down the IForm and find free local variables |
| 39 |
;; for each lambda node. Within this traversal, found $lambda nodes |
| 40 |
;; are chained into the first element of label-dic. |
| 41 |
;; |
| 42 |
;; Once all free lvars are sorted out, we look at the list of $lambda |
| 43 |
;; nodes and determine the ones that doesn't need to form a closure. |
| 44 |
;; They are to be bound to a freshly created global identifier. If other |
| 45 |
;; $lambda nodes have a reference to the lifted lambda node through |
| 46 |
;; local variables, they are substituted to the reference to this global |
| 47 |
;; identifier. |
| 48 |
;; |
| 49 |
;; Note for the reader of this code: The term "lambda lifting" usually |
| 50 |
;; includes a transformation that substitutes closed variables for |
| 51 |
;; arguments. We don't do such transformation so far. It trades the |
| 52 |
;; cost of closure allocation for pushing extra arguments. It may be |
| 53 |
;; a win if the closure is allocated lots of times. OTOH, if the closure |
| 54 |
;; is created only a few times, but called lots of times, the overhead of |
| 55 |
;; extra arguments may exceed the gain by not allocating the closure. |
| 56 |
;; |
| 57 |
;; Pass4 is done in three steps. |
| 58 |
;; |
| 59 |
;; - The first step, pass4/scan, recursively descends the IForm and determine |
| 60 |
;; a set of free variables for each $LAMBDA nodes. It also collects lambda |
| 61 |
;; nodes inside the iform into label-dic-info. |
| 62 |
;; In this pass, we mark the toplevel lambda node by setting |
| 63 |
;; $lambda-lifted-var to #t. All other lambda nodes have #f at this moment. |
| 64 |
;; |
| 65 |
;; - The second step, pass4/lift, takes a set of $LAMBDA nodes in the IForm |
| 66 |
;; and finds which $LAMBDA nodes can be lifted. When lifted, we set |
| 67 |
;; its $lambda-lifted-var with the variable that bound to the lifted lambda. |
| 68 |
;; |
| 69 |
;; - The third step, pass4/subst, walks the IForm again, and replaces the |
| 70 |
;; occurence of $LAMBDA nodes to be lifted for $LREFs. Then wraps the |
| 71 |
;; entire iform with $LET to save the lifted lambdas. |
| 72 |
;; |
| 73 |
;; This pass introduces CL-like toplevel environment, e.g. |
| 74 |
;; |
| 75 |
;; ($let rec (<lvar> ...) |
| 76 |
;; (($lambda ...) ...) ; lifted lambdas |
| 77 |
;; ($define ...) ; toplevel definition |
| 78 |
;; ) |
| 79 |
;; |
| 80 |
;; This works, since we already dissolved internal defines, and the $DEFINE |
| 81 |
;; we have is all toplevel defines, and the toplevel variable to be bound |
| 82 |
;; is already resolved to the identifier. |
| 83 |
;; NB: Whether we use 'rec' or not in this outermost lambda doesn't matter, |
| 84 |
;; for we directly refer to <lvar>s. We just use 'rec' to remind it is |
| 85 |
;; conceptually a letrec. |
| 86 |
|
| 87 |
(define-inline (pass4/add-lvar lvar bound free) |
| 88 |
(if (or (memq lvar bound) (memq lvar free)) free (cons lvar free))) |
| 89 |
|
| 90 |
;; Pass 4 entry point. Returns IForm and list of lifted lvars |
| 91 |
;; NB: If the toplevel iform is $seq, we process each form of its body |
| 92 |
;; separately. Sometimes such toplevel $seq is a result of macro expansion, |
| 93 |
;; and can have large number of $define nodes. If we process such $seq |
| 94 |
;; at once, it may yield a huge environment frame to hold all lifted closures. |
| 95 |
|
| 96 |
(define (pass4 iform module) |
| 97 |
(if (vm-compiler-flag-no-lifting?) |
| 98 |
iform |
| 99 |
(pass4/top iform module))) |
| 100 |
|
| 101 |
(define (pass4/top iform module) |
| 102 |
(if (has-tag? iform $SEQ) |
| 103 |
($seq (imap (cut pass4/top <> module) ($seq-body iform))) |
| 104 |
(let1 dic (make-label-dic '()) |
| 105 |
(pass4/scan iform '() '() #t dic) ; Mark free variables |
| 106 |
(let1 lambda-nodes (label-dic-info dic) |
| 107 |
(if (or (null? lambda-nodes) |
| 108 |
(and (null? (cdr lambda-nodes)) ; iform has only a toplevel lambda |
| 109 |
($lambda-lifted-var (car lambda-nodes)))) |
| 110 |
iform ;shortcut |
| 111 |
(let1 lifted (pass4/lift lambda-nodes module) |
| 112 |
(if (null? lifted) |
| 113 |
iform ;shortcut |
| 114 |
(let1 iform. (pass4/subst iform (make-label-dic '())) |
| 115 |
($let #f 'rec |
| 116 |
(imap (^[x] ($lambda-lifted-var x)) lifted) |
| 117 |
lifted |
| 118 |
iform.))))))))) |
| 119 |
|
| 120 |
;; Pass4 step1 - scan |
| 121 |
;; bs - List of lvars whose binding is introduced in the current scope. |
| 122 |
;; fs - List of free lvars found so far in the current scope. |
| 123 |
;; t? - #t in toplevel expression, not inside another $lambda or $let. |
| 124 |
;; $lambda node appears in this context doesn't need to be lifted, |
| 125 |
;; for they're created at the time the entire toplevel expression |
| 126 |
;; is created anyway. |
| 127 |
;; labels - label-dic. the info field is used to hold $LAMBDA nodes. |
| 128 |
;; Eacl call returns a list of free lvars. |
| 129 |
|
| 130 |
(define-macro (pass4/scan* iforms bs fs t? labels) |
| 131 |
(let1 iforms. (gensym) |
| 132 |
`(let1 ,iforms. ,iforms |
| 133 |
(cond [(null? ,iforms.) ,fs] |
| 134 |
[(null? (cdr ,iforms.)) |
| 135 |
(pass4/scan (car ,iforms.) ,bs ,fs ,t? ,labels)] |
| 136 |
[else |
| 137 |
(let loop ([,iforms. ,iforms.] [,fs ,fs]) |
| 138 |
(if (null? ,iforms.) |
| 139 |
,fs |
| 140 |
(loop (cdr ,iforms.) |
| 141 |
(pass4/scan (car ,iforms.) ,bs ,fs ,t? ,labels))))])))) |
| 142 |
|
| 143 |
(define/case (pass4/scan iform bs fs t? labels) |
| 144 |
(iform-tag iform) |
| 145 |
[($DEFINE) (unless t? |
| 146 |
(warn "define appears in non-top-level expression: ~s" |
| 147 |
(unravel-syntax ($define-src iform)))) |
| 148 |
(pass4/scan ($define-expr iform) bs fs t? labels)] |
| 149 |
[($LREF) (pass4/add-lvar ($lref-lvar iform) bs fs)] |
| 150 |
[($LSET) (let1 fs (pass4/scan ($lset-expr iform) bs fs t? labels) |
| 151 |
(pass4/add-lvar ($lset-lvar iform) bs fs))] |
| 152 |
[($GSET) (pass4/scan ($gset-expr iform) bs fs t? labels)] |
| 153 |
[($IF) (let* ([fs (pass4/scan ($if-test iform) bs fs t? labels)] |
| 154 |
[fs (pass4/scan ($if-then iform) bs fs t? labels)]) |
| 155 |
(pass4/scan ($if-else iform) bs fs t? labels))] |
| 156 |
[($LET) (let* ([new-bs (append ($let-lvars iform) bs)] |
| 157 |
[bs (if (memv ($let-type iform) '(rec rec*)) new-bs bs)] |
| 158 |
[fs (pass4/scan* ($let-inits iform) bs fs #f labels)]) |
| 159 |
(pass4/scan ($let-body iform) new-bs fs #f labels))] |
| 160 |
[($RECEIVE)(let ([fs (pass4/scan ($receive-expr iform) bs fs #f labels)] |
| 161 |
[bs (append ($receive-lvars iform) bs)]) |
| 162 |
(pass4/scan ($receive-body iform) bs fs #f labels))] |
| 163 |
[($LAMBDA) (let1 inner-fs (pass4/scan ($lambda-body iform) |
| 164 |
($lambda-lvars iform) '() #f labels) |
| 165 |
;; If this $LAMBDA is outermost in the original expression, |
| 166 |
;; we don't need to lift it, nor need to set free-lvars. |
| 167 |
;; We just mark it by setting lifted-var to #t so that |
| 168 |
;; pass4/lift phase can treat it specially. |
| 169 |
(unless ($lambda-dissolved? iform) |
| 170 |
(label-dic-info-push! labels iform) ;save the lambda node |
| 171 |
(when t? ;mark this is toplevel |
| 172 |
($lambda-lifted-var-set! iform #t))) |
| 173 |
(cond [t? '()] |
| 174 |
[else ($lambda-free-lvars-set! iform inner-fs) |
| 175 |
(let loop ([inner-fs inner-fs] [fs fs]) |
| 176 |
(if (null? inner-fs) |
| 177 |
fs |
| 178 |
(loop (cdr inner-fs) |
| 179 |
(pass4/add-lvar (car inner-fs) bs fs))))]))] |
| 180 |
[($CLAMBDA) (pass4/scan* ($clambda-closures iform) bs fs t? labels)] |
| 181 |
[($LABEL) (cond [(label-seen? labels iform) fs] |
| 182 |
[else (label-push! labels iform) |
| 183 |
(pass4/scan ($label-body iform) bs fs t? labels)])] |
| 184 |
[($SEQ) (pass4/scan* ($seq-body iform) bs fs t? labels)] |
| 185 |
[($CALL) (let1 fs (if (eq? ($call-flag iform) 'jump) |
| 186 |
fs |
| 187 |
(pass4/scan ($call-proc iform) bs fs t? labels)) |
| 188 |
(pass4/scan* ($call-args iform) bs fs t? labels))] |
| 189 |
[($ASM) (pass4/scan* ($asm-args iform) bs fs t? labels)] |
| 190 |
[($CONS $APPEND $MEMV $EQ? $EQV?) (pass4/scan2 iform bs fs t? labels)] |
| 191 |
[($VECTOR $LIST $LIST*) (pass4/scan* ($*-args iform) bs fs t? labels)] |
| 192 |
[($LIST->VECTOR) (pass4/scan ($*-arg0 iform) bs fs t? labels)] |
| 193 |
[($DYNENV) (let* ([fs (pass4/scan ($dynenv-key iform) bs fs #f labels)] |
| 194 |
[fs (pass4/scan ($dynenv-value iform) bs fs #f labels)]) |
| 195 |
(pass4/scan ($dynenv-body iform) bs fs t? labels))] |
| 196 |
[else fs]) |
| 197 |
|
| 198 |
(define (pass4/scan2 iform bs fs t? labels) |
| 199 |
(let1 fs (pass4/scan ($*-arg0 iform) bs fs t? labels) |
| 200 |
(pass4/scan ($*-arg1 iform) bs fs t? labels))) |
| 201 |
|
| 202 |
;; Sort out the liftable lambda nodes. |
| 203 |
;; Returns a list of lambda nodes, in each of which $lambda-lifted-var |
| 204 |
;; contains an identifier. |
| 205 |
;; |
| 206 |
;; At this moment, we only detect closures without free variables, |
| 207 |
;; or self-recursive closures. |
| 208 |
;; |
| 209 |
;; Eventually we want to detect mutual recursive case like this: |
| 210 |
;; |
| 211 |
;; (define (foo ...) |
| 212 |
;; (define (a x) ... (b ...) ...) |
| 213 |
;; (define (b y) ... (a ...) ...) |
| 214 |
;; ...) |
| 215 |
;; |
| 216 |
;; If a's only free variable is b, and b's only free variable is a, |
| 217 |
;; then we can lift both nodes to the toplevel. |
| 218 |
;; |
| 219 |
;; Tentative algorithm: |
| 220 |
;; - Create a directed graph consists of free lvars and lambda nodes. |
| 221 |
;; An edge from an lvar to a lambda node if the lvar is free in |
| 222 |
;; the lambda node. An edge from lambda node to an lvar if the lambda |
| 223 |
;; node is bound to the lvar. |
| 224 |
;; - Find lvars without incoming edge, and remove them and all reachable |
| 225 |
;; nodes from them. |
| 226 |
;; - The lambda nodes in the remaining graph are the ones we can lift. |
| 227 |
;; |
| 228 |
|
| 229 |
(define (pass4/lift lambda-nodes module) |
| 230 |
(let1 top-name #f |
| 231 |
;; Find a toplevel $lambda node (marked by #t in lifted-var). |
| 232 |
;; Its name can be used to generate names for lifted lambdas. |
| 233 |
(let loop ([lms lambda-nodes]) |
| 234 |
(when (pair? lms) |
| 235 |
(or (and-let* ([ ($lambda-lifted-var (car lms)) ] |
| 236 |
[n ($lambda-name (car lms))]) |
| 237 |
(set! top-name (identifier->symbol n)) |
| 238 |
#t) |
| 239 |
(loop (cdr lms))))) |
| 240 |
;; Loop over liftable lambda candidates. Lifting one lambda node |
| 241 |
;; can turn another lambda nodes liftable, so we repeat the pass until |
| 242 |
;; we can't find liftable ones. |
| 243 |
(rlet1 lifted '() |
| 244 |
(let loop ([lms lambda-nodes] |
| 245 |
[lifted? #f] |
| 246 |
[remaining '()]) |
| 247 |
(cond [(null? lms) (when lifted? (loop remaining #f '()))] ;repeat |
| 248 |
[($lambda-lifted-var (car lms)) ; this is toplevel node |
| 249 |
($lambda-lifted-var-set! (car lms) #f) |
| 250 |
(loop (cdr lms) lifted? remaining)] |
| 251 |
[else |
| 252 |
(let* ([lm (car lms)] |
| 253 |
[fvs ($lambda-free-lvars lm)]) |
| 254 |
(if (or (null? fvs) |
| 255 |
(and (null? (cdr fvs)) |
| 256 |
(lvar-immutable? (car fvs)) |
| 257 |
(memq (lvar-initval (car fvs)) lifted))) |
| 258 |
(let1 lvar (make-lvar (gensym)) |
| 259 |
($lambda-name-set! lm (list top-name |
| 260 |
(or ($lambda-name lm) |
| 261 |
(lvar-name lvar)))) |
| 262 |
($lambda-lifted-var-set! lm lvar) |
| 263 |
(push! lifted lm) |
| 264 |
(loop (cdr lms) #t remaining)) |
| 265 |
(loop (cdr lms) lifted? (cons lm remaining))))]))))) |
| 266 |
|
| 267 |
;; Final touch of pass4 - replace lifted lambda nodes to the reference of |
| 268 |
;; pre-bound lvars. |
| 269 |
;; Returns (possibly modified) IForm. |
| 270 |
(define-macro (pass4/subst! access-form labels) |
| 271 |
(match-let1 (accessor expr) access-form |
| 272 |
(let ([orig (gensym)] |
| 273 |
[result (gensym)] |
| 274 |
[setter (if (eq? accessor 'car) |
| 275 |
'set-car! |
| 276 |
(string->symbol #"~|accessor|-set!"))]) |
| 277 |
`(let* ([,orig (,accessor ,expr)] |
| 278 |
[,result (pass4/subst ,orig ,labels)]) |
| 279 |
(unless (eq? ,orig ,result) |
| 280 |
(,setter ,expr ,result)) |
| 281 |
,expr)))) |
| 282 |
|
| 283 |
(define-macro (pass4/subst*! iforms labels) |
| 284 |
(let1 iforms. (gensym) |
| 285 |
`(let1 ,iforms. ,iforms |
| 286 |
(cond [(null? ,iforms.)] |
| 287 |
[(null? (cdr ,iforms.)) (pass4/subst! (car ,iforms.) ,labels)] |
| 288 |
[else |
| 289 |
(let loop ([,iforms. ,iforms.]) |
| 290 |
(unless (null? ,iforms.) |
| 291 |
(pass4/subst! (car ,iforms.) ,labels) |
| 292 |
(loop (cdr ,iforms.))))])))) |
| 293 |
|
| 294 |
(define/case (pass4/subst iform labels) |
| 295 |
(iform-tag iform) |
| 296 |
[($DEFINE) (pass4/subst! ($define-expr iform) labels)] |
| 297 |
[($LREF) (or (and-let* ([ (lvar-immutable? ($lref-lvar iform)) ] |
| 298 |
[init (lvar-initval ($lref-lvar iform))] |
| 299 |
[ (vector? init) ] |
| 300 |
[ (has-tag? init $LAMBDA) ] |
| 301 |
[lifted ($lambda-lifted-var init)]) |
| 302 |
(lvar-ref--! ($lref-lvar iform)) |
| 303 |
($lref-lvar-set! iform lifted) |
| 304 |
(lvar-ref++! lifted) |
| 305 |
iform) |
| 306 |
iform)] |
| 307 |
[($LSET) (pass4/subst! ($lset-expr iform) labels)] |
| 308 |
[($GSET) (pass4/subst! ($gset-expr iform) labels)] |
| 309 |
[($IF) (pass4/subst! ($if-test iform) labels) |
| 310 |
(pass4/subst! ($if-then iform) labels) |
| 311 |
(pass4/subst! ($if-else iform) labels)] |
| 312 |
[($LET) (pass4/subst*! ($let-inits iform) labels) |
| 313 |
(pass4/subst! ($let-body iform) labels)] |
| 314 |
[($RECEIVE)(pass4/subst! ($receive-expr iform) labels) |
| 315 |
(pass4/subst! ($receive-body iform) labels)] |
| 316 |
[($LAMBDA) (pass4/subst! ($lambda-body iform) labels) |
| 317 |
(or (and-let* ([lifted ($lambda-lifted-var iform)]) |
| 318 |
($lref lifted)) |
| 319 |
iform)] |
| 320 |
[($CLAMBDA) (pass4/subst*! ($clambda-closures iform) labels) iform] |
| 321 |
[($LABEL) (unless (label-seen? labels iform) |
| 322 |
(label-push! labels iform) |
| 323 |
(pass4/subst! ($label-body iform) labels)) |
| 324 |
iform] |
| 325 |
[($SEQ) (pass4/subst*! ($seq-body iform) labels) iform] |
| 326 |
[($CALL) (pass4/subst*! ($call-args iform) labels) |
| 327 |
(pass4/subst! ($call-proc iform) labels)] |
| 328 |
[($ASM) (pass4/subst*! ($asm-args iform) labels) iform] |
| 329 |
[($CONS $APPEND $MEMV $EQ? $EQV?) (pass4/subst! ($*-arg0 iform) labels) |
| 330 |
(pass4/subst! ($*-arg1 iform) labels)] |
| 331 |
[($VECTOR $LIST $LIST*) (pass4/subst*! ($*-args iform) labels) iform] |
| 332 |
[($LIST->VECTOR) (pass4/subst! ($*-arg0 iform) labels)] |
| 333 |
[($DYNENV) (pass4/subst! (car ($dynenv-kvs iform)) labels) |
| 334 |
(pass4/subst! (car (cdr ($dynenv-kvs iform))) labels) |
| 335 |
(pass4/subst! ($dynenv-body iform) labels) |
| 336 |
iform] |
| 337 |
[else iform]) |