Debian Codegraph @

src/compile-4.scm

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