Commit | Line | Data |
---|---|---|
cf10678f AW |
1 | ;;; TREE-IL -> GLIL compiler |
2 | ||
3 | ;; Copyright (C) 2001,2008,2009 Free Software Foundation, Inc. | |
4 | ||
53befeb7 NJ |
5 | ;;;; This library is free software; you can redistribute it and/or |
6 | ;;;; modify it under the terms of the GNU Lesser General Public | |
7 | ;;;; License as published by the Free Software Foundation; either | |
8 | ;;;; version 3 of the License, or (at your option) any later version. | |
9 | ;;;; | |
10 | ;;;; This library is distributed in the hope that it will be useful, | |
11 | ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | ;;;; Lesser General Public License for more details. | |
14 | ;;;; | |
15 | ;;;; You should have received a copy of the GNU Lesser General Public | |
16 | ;;;; License along with this library; if not, write to the Free Software | |
17 | ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
cf10678f AW |
18 | |
19 | ;;; Code: | |
20 | ||
21 | (define-module (language tree-il analyze) | |
66d3e9a3 | 22 | #:use-module (srfi srfi-1) |
4b856371 | 23 | #:use-module (srfi srfi-9) |
cf10678f | 24 | #:use-module (system base syntax) |
4b856371 | 25 | #:use-module (system base message) |
af5ed549 | 26 | #:use-module (system vm program) |
cf10678f | 27 | #:use-module (language tree-il) |
99480e11 | 28 | #:use-module (system base pmatch) |
4b856371 | 29 | #:export (analyze-lexicals |
48b1db75 LC |
30 | analyze-tree |
31 | unused-variable-analysis | |
ae03cf1f LC |
32 | unbound-variable-analysis |
33 | arity-analysis)) | |
cf10678f | 34 | |
66d3e9a3 AW |
35 | ;; Allocation is the process of assigning storage locations for lexical |
36 | ;; variables. A lexical variable has a distinct "address", or storage | |
37 | ;; location, for each procedure in which it is referenced. | |
38 | ;; | |
39 | ;; A variable is "local", i.e., allocated on the stack, if it is | |
40 | ;; referenced from within the procedure that defined it. Otherwise it is | |
41 | ;; a "closure" variable. For example: | |
42 | ;; | |
43 | ;; (lambda (a) a) ; a will be local | |
44 | ;; `a' is local to the procedure. | |
45 | ;; | |
46 | ;; (lambda (a) (lambda () a)) | |
47 | ;; `a' is local to the outer procedure, but a closure variable with | |
48 | ;; respect to the inner procedure. | |
49 | ;; | |
50 | ;; If a variable is ever assigned, it needs to be heap-allocated | |
51 | ;; ("boxed"). This is so that closures and continuations capture the | |
52 | ;; variable's identity, not just one of the values it may have over the | |
53 | ;; course of program execution. If the variable is never assigned, there | |
54 | ;; is no distinction between value and identity, so closing over its | |
55 | ;; identity (whether through closures or continuations) can make a copy | |
56 | ;; of its value instead. | |
57 | ;; | |
58 | ;; Local variables are stored on the stack within a procedure's call | |
59 | ;; frame. Their index into the stack is determined from their linear | |
60 | ;; postion within a procedure's binding path: | |
cf10678f AW |
61 | ;; (let (0 1) |
62 | ;; (let (2 3) ...) | |
63 | ;; (let (2) ...)) | |
64 | ;; (let (2 3 4) ...)) | |
65 | ;; etc. | |
66 | ;; | |
5af166bd AW |
67 | ;; This algorithm has the problem that variables are only allocated |
68 | ;; indices at the end of the binding path. If variables bound early in | |
69 | ;; the path are not used in later portions of the path, their indices | |
70 | ;; will not be recycled. This problem is particularly egregious in the | |
71 | ;; expansion of `or': | |
72 | ;; | |
73 | ;; (or x y z) | |
74 | ;; -> (let ((a x)) (if a a (let ((b y)) (if b b z)))) | |
75 | ;; | |
76 | ;; As you can see, the `a' binding is only used in the ephemeral `then' | |
77 | ;; clause of the first `if', but its index would be reserved for the | |
78 | ;; whole of the `or' expansion. So we have a hack for this specific | |
79 | ;; case. A proper solution would be some sort of liveness analysis, and | |
80 | ;; not our linear allocation algorithm. | |
81 | ;; | |
66d3e9a3 AW |
82 | ;; Closure variables are captured when a closure is created, and stored |
83 | ;; in a vector. Each closure variable has a unique index into that | |
84 | ;; vector. | |
85 | ;; | |
9059993f AW |
86 | ;; There is one more complication. Procedures bound by <fix> may, in |
87 | ;; some cases, be rendered inline to their parent procedure. That is to | |
88 | ;; say, | |
89 | ;; | |
90 | ;; (letrec ((lp (lambda () (lp)))) (lp)) | |
91 | ;; => (fix ((lp (lambda () (lp)))) (lp)) | |
92 | ;; => goto FIX-BODY; LP: goto LP; FIX-BODY: goto LP; | |
93 | ;; ^ jump over the loop ^ the fixpoint lp ^ starting off the loop | |
94 | ;; | |
95 | ;; The upshot is that we don't have to allocate any space for the `lp' | |
96 | ;; closure at all, as it can be rendered inline as a loop. So there is | |
97 | ;; another kind of allocation, "label allocation", in which the | |
98 | ;; procedure is simply a label, placed at the start of the lambda body. | |
99 | ;; The label is the gensym under which the lambda expression is bound. | |
100 | ;; | |
101 | ;; The analyzer checks to see that the label is called with the correct | |
102 | ;; number of arguments. Calls to labels compile to rename + goto. | |
103 | ;; Lambda, the ultimate goto! | |
104 | ;; | |
66d3e9a3 AW |
105 | ;; |
106 | ;; The return value of `analyze-lexicals' is a hash table, the | |
107 | ;; "allocation". | |
108 | ;; | |
109 | ;; The allocation maps gensyms -- recall that each lexically bound | |
110 | ;; variable has a unique gensym -- to storage locations ("addresses"). | |
111 | ;; Since one gensym may have many storage locations, if it is referenced | |
112 | ;; in many procedures, it is a two-level map. | |
113 | ;; | |
114 | ;; The allocation also stored information on how many local variables | |
9059993f AW |
115 | ;; need to be allocated for each procedure, lexicals that have been |
116 | ;; translated into labels, and information on what free variables to | |
117 | ;; capture from its lexical parent procedure. | |
66d3e9a3 | 118 | ;; |
8a4ca0ea AW |
119 | ;; In addition, we have a conflation: while we're traversing the code, |
120 | ;; recording information to pass to the compiler, we take the | |
121 | ;; opportunity to generate labels for each lambda-case clause, so that | |
122 | ;; generated code can skip argument checks at runtime if they match at | |
123 | ;; compile-time. | |
124 | ;; | |
66d3e9a3 AW |
125 | ;; That is: |
126 | ;; | |
127 | ;; sym -> {lambda -> address} | |
8a4ca0ea AW |
128 | ;; lambda -> (labels . free-locs) |
129 | ;; lambda-case -> (gensym . nlocs) | |
66d3e9a3 | 130 | ;; |
9059993f | 131 | ;; address ::= (local? boxed? . index) |
8a4ca0ea | 132 | ;; labels ::= ((sym . lambda) ...) |
66d3e9a3 AW |
133 | ;; free-locs ::= ((sym0 . address0) (sym1 . address1) ...) |
134 | ;; free variable addresses are relative to parent proc. | |
135 | ||
136 | (define (make-hashq k v) | |
137 | (let ((res (make-hash-table))) | |
138 | (hashq-set! res k v) | |
139 | res)) | |
cf10678f AW |
140 | |
141 | (define (analyze-lexicals x) | |
66d3e9a3 AW |
142 | ;; bound-vars: lambda -> (sym ...) |
143 | ;; all identifiers bound within a lambda | |
9059993f | 144 | (define bound-vars (make-hash-table)) |
66d3e9a3 AW |
145 | ;; free-vars: lambda -> (sym ...) |
146 | ;; all identifiers referenced in a lambda, but not bound | |
147 | ;; NB, this includes identifiers referenced by contained lambdas | |
9059993f | 148 | (define free-vars (make-hash-table)) |
66d3e9a3 AW |
149 | ;; assigned: sym -> #t |
150 | ;; variables that are assigned | |
d97b69d9 | 151 | (define assigned (make-hash-table)) |
5af166bd | 152 | ;; refcounts: sym -> count |
66d3e9a3 | 153 | ;; allows us to detect the or-expansion in O(1) time |
9059993f | 154 | (define refcounts (make-hash-table)) |
8a4ca0ea | 155 | ;; labels: sym -> lambda |
9059993f | 156 | ;; for determining if fixed-point procedures can be rendered as |
8a4ca0ea | 157 | ;; labels. |
9059993f AW |
158 | (define labels (make-hash-table)) |
159 | ||
66d3e9a3 | 160 | ;; returns variables referenced in expr |
d97b69d9 AW |
161 | (define (analyze! x proc labels-in-proc tail? tail-call-args) |
162 | (define (step y) (analyze! y proc labels-in-proc #f #f)) | |
163 | (define (step-tail y) (analyze! y proc labels-in-proc tail? #f)) | |
164 | (define (step-tail-call y args) (analyze! y proc labels-in-proc #f | |
165 | (and tail? args))) | |
166 | (define (recur/labels x new-proc labels) | |
167 | (analyze! x new-proc (append labels labels-in-proc) #t #f)) | |
168 | (define (recur x new-proc) (analyze! x new-proc '() tail? #f)) | |
cf10678f AW |
169 | (record-case x |
170 | ((<application> proc args) | |
d97b69d9 AW |
171 | (apply lset-union eq? (step-tail-call proc args) |
172 | (map step args))) | |
cf10678f AW |
173 | |
174 | ((<conditional> test then else) | |
d97b69d9 | 175 | (lset-union eq? (step test) (step-tail then) (step-tail else))) |
cf10678f | 176 | |
e5f5113c | 177 | ((<lexical-ref> gensym) |
5af166bd | 178 | (hashq-set! refcounts gensym (1+ (hashq-ref refcounts gensym 0))) |
d97b69d9 AW |
179 | (if (not (and tail-call-args |
180 | (memq gensym labels-in-proc) | |
8a4ca0ea AW |
181 | (let ((p (hashq-ref labels gensym))) |
182 | (and p | |
183 | (let lp ((c (lambda-body p))) | |
184 | (and c (lambda-case? c) | |
185 | (or | |
186 | ;; for now prohibit optional & | |
187 | ;; keyword arguments; can relax this | |
188 | ;; restriction later | |
189 | (and (= (length (lambda-case-req c)) | |
190 | (length tail-call-args)) | |
191 | (not (lambda-case-opt c)) | |
192 | (not (lambda-case-kw c)) | |
193 | (not (lambda-case-rest c)) | |
194 | (not (lambda-case-predicate c))) | |
195 | (lp (lambda-case-else c))))))))) | |
d97b69d9 | 196 | (hashq-set! labels gensym #f)) |
66d3e9a3 | 197 | (list gensym)) |
cf10678f | 198 | |
e5f5113c | 199 | ((<lexical-set> gensym exp) |
66d3e9a3 | 200 | (hashq-set! assigned gensym #t) |
d97b69d9 | 201 | (hashq-set! labels gensym #f) |
66d3e9a3 | 202 | (lset-adjoin eq? (step exp) gensym)) |
cf10678f | 203 | |
e5f5113c | 204 | ((<module-set> exp) |
cf10678f AW |
205 | (step exp)) |
206 | ||
e5f5113c | 207 | ((<toplevel-set> exp) |
cf10678f AW |
208 | (step exp)) |
209 | ||
e5f5113c | 210 | ((<toplevel-define> exp) |
cf10678f AW |
211 | (step exp)) |
212 | ||
213 | ((<sequence> exps) | |
d97b69d9 AW |
214 | (let lp ((exps exps) (ret '())) |
215 | (cond ((null? exps) '()) | |
216 | ((null? (cdr exps)) | |
217 | (lset-union eq? ret (step-tail (car exps)))) | |
218 | (else | |
219 | (lp (cdr exps) (lset-union eq? ret (step (car exps)))))))) | |
cf10678f | 220 | |
8a4ca0ea AW |
221 | ((<lambda> body) |
222 | ;; order is important here | |
223 | (hashq-set! bound-vars x '()) | |
224 | (let ((free (recur body x))) | |
225 | (hashq-set! bound-vars x (reverse! (hashq-ref bound-vars x))) | |
226 | (hashq-set! free-vars x free) | |
227 | free)) | |
228 | ||
b0c8c187 | 229 | ((<lambda-case> opt kw inits vars predicate body else) |
8a4ca0ea AW |
230 | (hashq-set! bound-vars proc |
231 | (append (reverse vars) (hashq-ref bound-vars proc))) | |
232 | (lset-union | |
233 | eq? | |
234 | (lset-difference eq? | |
b0c8c187 AW |
235 | (lset-union eq? |
236 | (apply lset-union eq? (map step inits)) | |
237 | (if predicate (step predicate) '()) | |
8a4ca0ea AW |
238 | (step-tail body)) |
239 | vars) | |
240 | (if else (step-tail else) '()))) | |
66d3e9a3 | 241 | |
f4aa8d53 | 242 | ((<let> vars vals body) |
66d3e9a3 AW |
243 | (hashq-set! bound-vars proc |
244 | (append (reverse vars) (hashq-ref bound-vars proc))) | |
245 | (lset-difference eq? | |
d97b69d9 | 246 | (apply lset-union eq? (step-tail body) (map step vals)) |
66d3e9a3 | 247 | vars)) |
cf10678f | 248 | |
f4aa8d53 | 249 | ((<letrec> vars vals body) |
66d3e9a3 AW |
250 | (hashq-set! bound-vars proc |
251 | (append (reverse vars) (hashq-ref bound-vars proc))) | |
252 | (for-each (lambda (sym) (hashq-set! assigned sym #t)) vars) | |
253 | (lset-difference eq? | |
d97b69d9 | 254 | (apply lset-union eq? (step-tail body) (map step vals)) |
66d3e9a3 AW |
255 | vars)) |
256 | ||
c21c89b1 | 257 | ((<fix> vars vals body) |
d97b69d9 | 258 | ;; Try to allocate these procedures as labels. |
8a4ca0ea | 259 | (for-each (lambda (sym val) (hashq-set! labels sym val)) |
d97b69d9 | 260 | vars vals) |
c21c89b1 AW |
261 | (hashq-set! bound-vars proc |
262 | (append (reverse vars) (hashq-ref bound-vars proc))) | |
d97b69d9 AW |
263 | ;; Step into subexpressions. |
264 | (let* ((var-refs | |
265 | (map | |
266 | ;; Since we're trying to label-allocate the lambda, | |
267 | ;; pretend it's not a closure, and just recurse into its | |
268 | ;; body directly. (Otherwise, recursing on a closure | |
269 | ;; that references one of the fix's bound vars would | |
270 | ;; prevent label allocation.) | |
271 | (lambda (x) | |
272 | (record-case x | |
8a4ca0ea AW |
273 | ((<lambda> body) |
274 | ;; just like the closure case, except here we use | |
275 | ;; recur/labels instead of recur | |
276 | (hashq-set! bound-vars x '()) | |
277 | (let ((free (recur/labels body x vars))) | |
278 | (hashq-set! bound-vars x (reverse! (hashq-ref bound-vars x))) | |
279 | (hashq-set! free-vars x free) | |
280 | free)))) | |
d97b69d9 AW |
281 | vals)) |
282 | (vars-with-refs (map cons vars var-refs)) | |
283 | (body-refs (recur/labels body proc vars))) | |
284 | (define (delabel-dependents! sym) | |
285 | (let ((refs (assq-ref vars-with-refs sym))) | |
286 | (if refs | |
287 | (for-each (lambda (sym) | |
288 | (if (hashq-ref labels sym) | |
289 | (begin | |
290 | (hashq-set! labels sym #f) | |
291 | (delabel-dependents! sym)))) | |
292 | refs)))) | |
293 | ;; Stepping into the lambdas and the body might have made some | |
294 | ;; procedures not label-allocatable -- which might have | |
295 | ;; knock-on effects. For example: | |
296 | ;; (fix ((a (lambda () (b))) | |
297 | ;; (b (lambda () a))) | |
298 | ;; (a)) | |
299 | ;; As far as `a' is concerned, both `a' and `b' are | |
300 | ;; label-allocatable. But `b' references `a' not in a proc-tail | |
301 | ;; position, which makes `a' not label-allocatable. The | |
302 | ;; knock-on effect is that, when back-propagating this | |
303 | ;; information to `a', `b' will also become not | |
304 | ;; label-allocatable, as it is referenced within `a', which is | |
305 | ;; allocated as a closure. This is a transitive relationship. | |
306 | (for-each (lambda (sym) | |
307 | (if (not (hashq-ref labels sym)) | |
308 | (delabel-dependents! sym))) | |
309 | vars) | |
310 | ;; Now lift bound variables with label-allocated lambdas to the | |
311 | ;; parent procedure. | |
312 | (for-each | |
313 | (lambda (sym val) | |
314 | (if (hashq-ref labels sym) | |
315 | ;; Remove traces of the label-bound lambda. The free | |
316 | ;; vars will propagate up via the return val. | |
317 | (begin | |
318 | (hashq-set! bound-vars proc | |
319 | (append (hashq-ref bound-vars val) | |
320 | (hashq-ref bound-vars proc))) | |
321 | (hashq-remove! bound-vars val) | |
322 | (hashq-remove! free-vars val)))) | |
323 | vars vals) | |
324 | (lset-difference eq? | |
325 | (apply lset-union eq? body-refs var-refs) | |
326 | vars))) | |
c21c89b1 | 327 | |
8a4ca0ea AW |
328 | ((<let-values> exp body) |
329 | (lset-union eq? (step exp) (step body))) | |
66d3e9a3 AW |
330 | |
331 | (else '()))) | |
332 | ||
9059993f AW |
333 | ;; allocation: sym -> {lambda -> address} |
334 | ;; lambda -> (nlocs labels . free-locs) | |
335 | (define allocation (make-hash-table)) | |
336 | ||
66d3e9a3 AW |
337 | (define (allocate! x proc n) |
338 | (define (recur y) (allocate! y proc n)) | |
339 | (record-case x | |
340 | ((<application> proc args) | |
341 | (apply max (recur proc) (map recur args))) | |
cf10678f | 342 | |
66d3e9a3 AW |
343 | ((<conditional> test then else) |
344 | (max (recur test) (recur then) (recur else))) | |
cf10678f | 345 | |
e5f5113c | 346 | ((<lexical-set> exp) |
66d3e9a3 AW |
347 | (recur exp)) |
348 | ||
e5f5113c | 349 | ((<module-set> exp) |
66d3e9a3 AW |
350 | (recur exp)) |
351 | ||
e5f5113c | 352 | ((<toplevel-set> exp) |
66d3e9a3 AW |
353 | (recur exp)) |
354 | ||
e5f5113c | 355 | ((<toplevel-define> exp) |
66d3e9a3 AW |
356 | (recur exp)) |
357 | ||
358 | ((<sequence> exps) | |
359 | (apply max (map recur exps))) | |
360 | ||
8a4ca0ea | 361 | ((<lambda> body) |
66d3e9a3 AW |
362 | ;; allocate closure vars in order |
363 | (let lp ((c (hashq-ref free-vars x)) (n 0)) | |
364 | (if (pair? c) | |
365 | (begin | |
366 | (hashq-set! (hashq-ref allocation (car c)) | |
367 | x | |
368 | `(#f ,(hashq-ref assigned (car c)) . ,n)) | |
369 | (lp (cdr c) (1+ n))))) | |
370 | ||
8a4ca0ea | 371 | (let ((nlocs (allocate! body x 0)) |
66d3e9a3 AW |
372 | (free-addresses |
373 | (map (lambda (v) | |
374 | (hashq-ref (hashq-ref allocation v) proc)) | |
9059993f AW |
375 | (hashq-ref free-vars x))) |
376 | (labels (filter cdr | |
377 | (map (lambda (sym) | |
378 | (cons sym (hashq-ref labels sym))) | |
379 | (hashq-ref bound-vars x))))) | |
66d3e9a3 | 380 | ;; set procedure allocations |
8a4ca0ea | 381 | (hashq-set! allocation x (cons labels free-addresses))) |
66d3e9a3 | 382 | n) |
cf10678f | 383 | |
b0c8c187 | 384 | ((<lambda-case> opt kw inits vars predicate body else) |
8a4ca0ea AW |
385 | (max |
386 | (let lp ((vars vars) (n n)) | |
387 | (if (null? vars) | |
b0c8c187 AW |
388 | (let ((nlocs (apply |
389 | max | |
390 | (if predicate (allocate! predicate body n) n) | |
391 | (allocate! body proc n) | |
392 | ;; inits not logically at the end, but they | |
393 | ;; are the list... | |
394 | (map (lambda (x) (allocate! x body n)) inits)))) | |
8a4ca0ea AW |
395 | ;; label and nlocs for the case |
396 | (hashq-set! allocation x (cons (gensym ":LCASE") nlocs)) | |
397 | nlocs) | |
398 | (begin | |
399 | (hashq-set! allocation (car vars) | |
400 | (make-hashq | |
401 | proc `(#t ,(hashq-ref assigned (car vars)) . ,n))) | |
402 | (lp (cdr vars) (1+ n))))) | |
403 | (if else (allocate! else proc n) n))) | |
404 | ||
66d3e9a3 AW |
405 | ((<let> vars vals body) |
406 | (let ((nmax (apply max (map recur vals)))) | |
407 | (cond | |
408 | ;; the `or' hack | |
409 | ((and (conditional? body) | |
410 | (= (length vars) 1) | |
411 | (let ((v (car vars))) | |
412 | (and (not (hashq-ref assigned v)) | |
413 | (= (hashq-ref refcounts v 0) 2) | |
414 | (lexical-ref? (conditional-test body)) | |
415 | (eq? (lexical-ref-gensym (conditional-test body)) v) | |
416 | (lexical-ref? (conditional-then body)) | |
417 | (eq? (lexical-ref-gensym (conditional-then body)) v)))) | |
418 | (hashq-set! allocation (car vars) | |
419 | (make-hashq proc `(#t #f . ,n))) | |
420 | ;; the 1+ for this var | |
421 | (max nmax (1+ n) (allocate! (conditional-else body) proc n))) | |
422 | (else | |
423 | (let lp ((vars vars) (n n)) | |
424 | (if (null? vars) | |
425 | (max nmax (allocate! body proc n)) | |
426 | (let ((v (car vars))) | |
cf10678f AW |
427 | (hashq-set! |
428 | allocation v | |
66d3e9a3 AW |
429 | (make-hashq proc |
430 | `(#t ,(hashq-ref assigned v) . ,n))) | |
431 | (lp (cdr vars) (1+ n))))))))) | |
432 | ||
433 | ((<letrec> vars vals body) | |
434 | (let lp ((vars vars) (n n)) | |
435 | (if (null? vars) | |
436 | (let ((nmax (apply max | |
437 | (map (lambda (x) | |
438 | (allocate! x proc n)) | |
439 | vals)))) | |
440 | (max nmax (allocate! body proc n))) | |
441 | (let ((v (car vars))) | |
442 | (hashq-set! | |
443 | allocation v | |
444 | (make-hashq proc | |
445 | `(#t ,(hashq-ref assigned v) . ,n))) | |
446 | (lp (cdr vars) (1+ n)))))) | |
cf10678f | 447 | |
c21c89b1 | 448 | ((<fix> vars vals body) |
d97b69d9 AW |
449 | (let lp ((in vars) (n n)) |
450 | (if (null? in) | |
451 | (let lp ((vars vars) (vals vals) (nmax n)) | |
452 | (cond | |
453 | ((null? vars) | |
454 | (max nmax (allocate! body proc n))) | |
455 | ((hashq-ref labels (car vars)) | |
8a4ca0ea | 456 | ;; allocate lambda body inline to proc |
d97b69d9 AW |
457 | (lp (cdr vars) |
458 | (cdr vals) | |
459 | (record-case (car vals) | |
8a4ca0ea AW |
460 | ((<lambda> body) |
461 | (max nmax (allocate! body proc n)))))) | |
d97b69d9 AW |
462 | (else |
463 | ;; allocate closure | |
464 | (lp (cdr vars) | |
465 | (cdr vals) | |
466 | (max nmax (allocate! (car vals) proc n)))))) | |
467 | ||
468 | (let ((v (car in))) | |
469 | (cond | |
470 | ((hashq-ref assigned v) | |
471 | (error "fixpoint procedures may not be assigned" x)) | |
472 | ((hashq-ref labels v) | |
473 | ;; no binding, it's a label | |
474 | (lp (cdr in) n)) | |
475 | (else | |
476 | ;; allocate closure binding | |
477 | (hashq-set! allocation v (make-hashq proc `(#t #f . ,n))) | |
478 | (lp (cdr in) (1+ n)))))))) | |
c21c89b1 | 479 | |
8a4ca0ea AW |
480 | ((<let-values> exp body) |
481 | (max (recur exp) (recur body))) | |
66d3e9a3 AW |
482 | |
483 | (else n))) | |
cf10678f | 484 | |
d97b69d9 | 485 | (analyze! x #f '() #t #f) |
66d3e9a3 | 486 | (allocate! x #f 0) |
cf10678f AW |
487 | |
488 | allocation) | |
4b856371 LC |
489 | |
490 | \f | |
48b1db75 LC |
491 | ;;; |
492 | ;;; Tree analyses for warnings. | |
493 | ;;; | |
494 | ||
495 | (define-record-type <tree-analysis> | |
496 | (make-tree-analysis leaf down up post init) | |
497 | tree-analysis? | |
498 | (leaf tree-analysis-leaf) ;; (lambda (x result env) ...) | |
499 | (down tree-analysis-down) ;; (lambda (x result env) ...) | |
500 | (up tree-analysis-up) ;; (lambda (x result env) ...) | |
501 | (post tree-analysis-post) ;; (lambda (result env) ...) | |
502 | (init tree-analysis-init)) ;; arbitrary value | |
503 | ||
504 | (define (analyze-tree analyses tree env) | |
505 | "Run all tree analyses listed in ANALYSES on TREE for ENV, using | |
506 | `tree-il-fold'. Return TREE." | |
507 | (define (traverse proc) | |
508 | (lambda (x results) | |
509 | (map (lambda (analysis result) | |
510 | ((proc analysis) x result env)) | |
511 | analyses | |
512 | results))) | |
513 | ||
514 | (let ((results | |
515 | (tree-il-fold (traverse tree-analysis-leaf) | |
516 | (traverse tree-analysis-down) | |
517 | (traverse tree-analysis-up) | |
518 | (map tree-analysis-init analyses) | |
519 | tree))) | |
520 | ||
521 | (for-each (lambda (analysis result) | |
522 | ((tree-analysis-post analysis) result env)) | |
523 | analyses | |
524 | results)) | |
525 | ||
526 | tree) | |
527 | ||
528 | \f | |
4b856371 LC |
529 | ;;; |
530 | ;;; Unused variable analysis. | |
531 | ;;; | |
532 | ||
533 | ;; <binding-info> records are used during tree traversals in | |
534 | ;; `report-unused-variables'. They contain a list of the local vars | |
535 | ;; currently in scope, a list of locals vars that have been referenced, and a | |
536 | ;; "location stack" (the stack of `tree-il-src' values for each parent tree). | |
537 | (define-record-type <binding-info> | |
538 | (make-binding-info vars refs locs) | |
539 | binding-info? | |
540 | (vars binding-info-vars) ;; ((GENSYM NAME LOCATION) ...) | |
541 | (refs binding-info-refs) ;; (GENSYM ...) | |
542 | (locs binding-info-locs)) ;; (LOCATION ...) | |
543 | ||
48b1db75 | 544 | (define unused-variable-analysis |
ae03cf1f | 545 | ;; Report unused variables in the given tree. |
48b1db75 LC |
546 | (make-tree-analysis |
547 | (lambda (x info env) | |
548 | ;; X is a leaf: extend INFO's refs accordingly. | |
549 | (let ((refs (binding-info-refs info)) | |
550 | (vars (binding-info-vars info)) | |
551 | (locs (binding-info-locs info))) | |
552 | (record-case x | |
553 | ((<lexical-ref> gensym) | |
554 | (make-binding-info vars (cons gensym refs) locs)) | |
555 | (else info)))) | |
556 | ||
557 | (lambda (x info env) | |
558 | ;; Going down into X: extend INFO's variable list | |
559 | ;; accordingly. | |
560 | (let ((refs (binding-info-refs info)) | |
561 | (vars (binding-info-vars info)) | |
562 | (locs (binding-info-locs info)) | |
563 | (src (tree-il-src x))) | |
564 | (define (extend inner-vars inner-names) | |
565 | (append (map (lambda (var name) | |
566 | (list var name src)) | |
567 | inner-vars | |
568 | inner-names) | |
569 | vars)) | |
570 | (record-case x | |
571 | ((<lexical-set> gensym) | |
572 | (make-binding-info vars (cons gensym refs) | |
573 | (cons src locs))) | |
574 | ((<lambda-case> req opt inits rest kw vars) | |
48b1db75 | 575 | (let ((names `(,@req |
632e7c32 | 576 | ,@(or opt '()) |
48b1db75 LC |
577 | ,@(if rest (list rest) '()) |
578 | ,@(if kw (map cadr (cdr kw)) '())))) | |
579 | (make-binding-info (extend vars names) refs | |
580 | (cons src locs)))) | |
581 | ((<let> vars names) | |
582 | (make-binding-info (extend vars names) refs | |
583 | (cons src locs))) | |
584 | ((<letrec> vars names) | |
585 | (make-binding-info (extend vars names) refs | |
586 | (cons src locs))) | |
587 | ((<fix> vars names) | |
588 | (make-binding-info (extend vars names) refs | |
589 | (cons src locs))) | |
590 | (else info)))) | |
591 | ||
592 | (lambda (x info env) | |
593 | ;; Leaving X's scope: shrink INFO's variable list | |
594 | ;; accordingly and reported unused nested variables. | |
595 | (let ((refs (binding-info-refs info)) | |
596 | (vars (binding-info-vars info)) | |
597 | (locs (binding-info-locs info))) | |
598 | (define (shrink inner-vars refs) | |
599 | (for-each (lambda (var) | |
600 | (let ((gensym (car var))) | |
601 | ;; Don't report lambda parameters as | |
602 | ;; unused. | |
603 | (if (and (not (memq gensym refs)) | |
604 | (not (and (lambda-case? x) | |
605 | (memq gensym | |
606 | inner-vars)))) | |
607 | (let ((name (cadr var)) | |
608 | ;; We can get approximate | |
609 | ;; source location by going up | |
610 | ;; the LOCS location stack. | |
611 | (loc (or (caddr var) | |
612 | (find pair? locs)))) | |
613 | (warning 'unused-variable loc name))))) | |
614 | (filter (lambda (var) | |
615 | (memq (car var) inner-vars)) | |
616 | vars)) | |
617 | (fold alist-delete vars inner-vars)) | |
618 | ||
619 | ;; For simplicity, we leave REFS untouched, i.e., with | |
620 | ;; names of variables that are now going out of scope. | |
621 | ;; It doesn't hurt as these are unique names, it just | |
622 | ;; makes REFS unnecessarily fat. | |
623 | (record-case x | |
624 | ((<lambda-case> vars) | |
625 | (make-binding-info (shrink vars refs) refs | |
626 | (cdr locs))) | |
627 | ((<let> vars) | |
628 | (make-binding-info (shrink vars refs) refs | |
629 | (cdr locs))) | |
630 | ((<letrec> vars) | |
631 | (make-binding-info (shrink vars refs) refs | |
632 | (cdr locs))) | |
633 | ((<fix> vars) | |
634 | (make-binding-info (shrink vars refs) refs | |
635 | (cdr locs))) | |
636 | (else info)))) | |
637 | ||
638 | (lambda (result env) #t) | |
639 | (make-binding-info '() '() '()))) | |
f67ddf9d LC |
640 | |
641 | \f | |
642 | ;;; | |
643 | ;;; Unbound variable analysis. | |
644 | ;;; | |
645 | ||
646 | ;; <toplevel-info> records are used during tree traversal in search of | |
647 | ;; possibly unbound variable. They contain a list of references to | |
648 | ;; potentially unbound top-level variables, a list of the top-level defines | |
649 | ;; that have been encountered, and a "location stack" (see above). | |
650 | (define-record-type <toplevel-info> | |
651 | (make-toplevel-info refs defs locs) | |
652 | toplevel-info? | |
653 | (refs toplevel-info-refs) ;; ((VARIABLE-NAME . LOCATION) ...) | |
654 | (defs toplevel-info-defs) ;; (VARIABLE-NAME ...) | |
655 | (locs toplevel-info-locs)) ;; (LOCATION ...) | |
656 | ||
6bb891dc | 657 | (define (goops-toplevel-definition proc args env) |
b6d2306d LC |
658 | ;; If application of PROC to ARGS is a GOOPS top-level definition, return |
659 | ;; the name of the variable being defined; otherwise return #f. This | |
660 | ;; assumes knowledge of the current implementation of `define-class' et al. | |
6bb891dc LC |
661 | (define (toplevel-define-arg args) |
662 | (and (pair? args) (pair? (cdr args)) (null? (cddr args)) | |
663 | (record-case (car args) | |
664 | ((<const> exp) | |
665 | (and (symbol? exp) exp)) | |
666 | (else #f)))) | |
667 | ||
b6d2306d LC |
668 | (record-case proc |
669 | ((<module-ref> mod public? name) | |
670 | (and (equal? mod '(oop goops)) | |
671 | (not public?) | |
672 | (eq? name 'toplevel-define!) | |
6bb891dc LC |
673 | (toplevel-define-arg args))) |
674 | ((<toplevel-ref> name) | |
675 | ;; This may be the result of expanding one of the GOOPS macros within | |
676 | ;; `oop/goops.scm'. | |
677 | (and (eq? name 'toplevel-define!) | |
678 | (eq? env (resolve-module '(oop goops))) | |
679 | (toplevel-define-arg args))) | |
b6d2306d LC |
680 | (else #f))) |
681 | ||
48b1db75 | 682 | (define unbound-variable-analysis |
ae03cf1f | 683 | ;; Report possibly unbound variables in the given tree. |
48b1db75 LC |
684 | (make-tree-analysis |
685 | (lambda (x info env) | |
686 | ;; X is a leaf: extend INFO's refs accordingly. | |
687 | (let ((refs (toplevel-info-refs info)) | |
688 | (defs (toplevel-info-defs info)) | |
689 | (locs (toplevel-info-locs info))) | |
690 | (define (bound? name) | |
691 | (or (and (module? env) | |
692 | (module-variable env name)) | |
693 | (memq name defs))) | |
694 | ||
695 | (record-case x | |
696 | ((<toplevel-ref> name src) | |
697 | (if (bound? name) | |
698 | info | |
699 | (let ((src (or src (find pair? locs)))) | |
700 | (make-toplevel-info (alist-cons name src refs) | |
701 | defs | |
702 | locs)))) | |
703 | (else info)))) | |
704 | ||
705 | (lambda (x info env) | |
706 | ;; Going down into X. | |
707 | (let* ((refs (toplevel-info-refs info)) | |
708 | (defs (toplevel-info-defs info)) | |
709 | (src (tree-il-src x)) | |
710 | (locs (cons src (toplevel-info-locs info)))) | |
711 | (define (bound? name) | |
712 | (or (and (module? env) | |
713 | (module-variable env name)) | |
714 | (memq name defs))) | |
715 | ||
716 | (record-case x | |
717 | ((<toplevel-set> name src) | |
718 | (if (bound? name) | |
719 | (make-toplevel-info refs defs locs) | |
720 | (let ((src (find pair? locs))) | |
721 | (make-toplevel-info (alist-cons name src refs) | |
722 | defs | |
723 | locs)))) | |
724 | ((<toplevel-define> name) | |
725 | (make-toplevel-info (alist-delete name refs eq?) | |
726 | (cons name defs) | |
727 | locs)) | |
728 | ||
729 | ((<application> proc args) | |
730 | ;; Check for a dynamic top-level definition, as is | |
731 | ;; done by code expanded from GOOPS macros. | |
732 | (let ((name (goops-toplevel-definition proc args | |
733 | env))) | |
734 | (if (symbol? name) | |
735 | (make-toplevel-info (alist-delete name refs | |
736 | eq?) | |
737 | (cons name defs) | |
738 | locs) | |
739 | (make-toplevel-info refs defs locs)))) | |
740 | (else | |
741 | (make-toplevel-info refs defs locs))))) | |
742 | ||
743 | (lambda (x info env) | |
744 | ;; Leaving X's scope. | |
745 | (let ((refs (toplevel-info-refs info)) | |
746 | (defs (toplevel-info-defs info)) | |
747 | (locs (toplevel-info-locs info))) | |
748 | (make-toplevel-info refs defs (cdr locs)))) | |
749 | ||
750 | (lambda (toplevel env) | |
751 | ;; Post-process the result. | |
752 | (for-each (lambda (name+loc) | |
753 | (let ((name (car name+loc)) | |
754 | (loc (cdr name+loc))) | |
755 | (warning 'unbound-variable loc name))) | |
756 | (reverse (toplevel-info-refs toplevel)))) | |
757 | ||
758 | (make-toplevel-info '() '() '()))) | |
ae03cf1f LC |
759 | |
760 | \f | |
761 | ;;; | |
762 | ;;; Arity analysis. | |
763 | ;;; | |
764 | ||
af5ed549 | 765 | ;; <arity-info> records contain information about lexical definitions of |
ae03cf1f LC |
766 | ;; procedures currently in scope, top-level procedure definitions that have |
767 | ;; been encountered, and calls to top-level procedures that have been | |
768 | ;; encountered. | |
769 | (define-record-type <arity-info> | |
770 | (make-arity-info toplevel-calls lexical-lambdas toplevel-lambdas) | |
771 | arity-info? | |
772 | (toplevel-calls toplevel-procedure-calls) ;; ((NAME . APPLICATION) ...) | |
773 | (lexical-lambdas lexical-lambdas) ;; ((GENSYM . DEFINITION) ...) | |
774 | (toplevel-lambdas toplevel-lambdas)) ;; ((NAME . DEFINITION) ...) | |
775 | ||
776 | (define (validate-arity proc application lexical?) | |
777 | ;; Validate the argument count of APPLICATION, a tree-il application of | |
778 | ;; PROC, emitting a warning in case of argument count mismatch. | |
779 | ||
af5ed549 LC |
780 | (define (filter-keyword-args keywords allow-other-keys? args) |
781 | ;; Filter keyword arguments from ARGS and return the resulting list. | |
782 | ;; KEYWORDS is the list of allowed keywords, and ALLOW-OTHER-KEYS? | |
783 | ;; specified whethere keywords not listed in KEYWORDS are allowed. | |
784 | (let loop ((args args) | |
785 | (result '())) | |
786 | (if (null? args) | |
787 | (reverse result) | |
788 | (let ((arg (car args))) | |
789 | (if (and (const? arg) | |
790 | (or (memq (const-exp arg) keywords) | |
791 | (and allow-other-keys? | |
792 | (keyword? (const-exp arg))))) | |
793 | (loop (if (pair? (cdr args)) | |
794 | (cddr args) | |
795 | '()) | |
796 | result) | |
797 | (loop (cdr args) | |
798 | (cons arg result))))))) | |
799 | ||
99480e11 LC |
800 | (define (arities proc) |
801 | ;; Return the arities of PROC, which can be either a tree-il or a | |
ae03cf1f LC |
802 | ;; procedure. |
803 | (define (len x) | |
804 | (or (and (or (null? x) (pair? x)) | |
805 | (length x)) | |
806 | 0)) | |
af5ed549 | 807 | (cond ((program? proc) |
99480e11 LC |
808 | (values (program-name proc) |
809 | (map (lambda (a) | |
810 | (list (arity:nreq a) (arity:nopt a) (arity:rest? a) | |
811 | (map car (arity:kw a)) | |
812 | (arity:allow-other-keys? a))) | |
813 | (program-arities proc)))) | |
ae03cf1f LC |
814 | ((procedure? proc) |
815 | (let ((arity (procedure-property proc 'arity))) | |
816 | (values (procedure-name proc) | |
99480e11 LC |
817 | (list (list (car arity) (cadr arity) (caddr arity) |
818 | #f #f))))) | |
ae03cf1f | 819 | (else |
99480e11 LC |
820 | (let loop ((name #f) |
821 | (proc proc) | |
822 | (arities '())) | |
823 | (if (not proc) | |
824 | (values name (reverse arities)) | |
825 | (record-case proc | |
826 | ((<lambda-case> req opt rest kw else) | |
827 | (loop name else | |
828 | (cons (list (len req) (len opt) rest | |
829 | (and (pair? kw) (map car (cdr kw))) | |
830 | (and (pair? kw) (car kw))) | |
831 | arities))) | |
832 | ((<lambda> meta body) | |
833 | (loop (assoc-ref meta 'name) body arities)) | |
834 | (else | |
835 | (values #f #f)))))))) | |
ae03cf1f LC |
836 | |
837 | (let ((args (application-args application)) | |
838 | (src (tree-il-src application))) | |
99480e11 LC |
839 | (call-with-values (lambda () (arities proc)) |
840 | (lambda (name arities) | |
841 | (define matches? | |
842 | (find (lambda (arity) | |
843 | (pmatch arity | |
844 | ((,req ,opt ,rest? ,kw ,aok?) | |
845 | (let ((args (if (pair? kw) | |
846 | (filter-keyword-args kw aok? args) | |
847 | args))) | |
848 | (if (and req opt) | |
849 | (let ((count (length args))) | |
850 | (and (>= count req) | |
851 | (or rest? | |
852 | (<= count (+ req opt))))) | |
853 | #t))) | |
854 | (else #t))) | |
855 | arities)) | |
856 | ||
857 | (if (not matches?) | |
858 | (warning 'arity-mismatch src | |
859 | (or name (with-output-to-string (lambda () (write proc)))) | |
860 | lexical?))))) | |
ae03cf1f LC |
861 | #t) |
862 | ||
863 | (define arity-analysis | |
864 | ;; Report arity mismatches in the given tree. | |
865 | (make-tree-analysis | |
866 | (lambda (x info env) | |
867 | ;; X is a leaf. | |
868 | info) | |
869 | (lambda (x info env) | |
870 | ;; Down into X. | |
871 | (define (extend lexical-name val info) | |
872 | ;; If VAL is a lambda, add NAME to the lexical-lambdas of INFO. | |
873 | (let ((toplevel-calls (toplevel-procedure-calls info)) | |
874 | (lexical-lambdas (lexical-lambdas info)) | |
875 | (toplevel-lambdas (toplevel-lambdas info))) | |
876 | (record-case val | |
877 | ((<lambda> body) | |
878 | (make-arity-info toplevel-calls | |
879 | (alist-cons lexical-name val | |
880 | lexical-lambdas) | |
881 | toplevel-lambdas)) | |
882 | ((<lexical-ref> gensym) | |
883 | ;; lexical alias | |
884 | (let ((val* (assq gensym lexical-lambdas))) | |
885 | (if (pair? val*) | |
886 | (extend lexical-name (cdr val*) info) | |
887 | info))) | |
888 | ((<toplevel-ref> name) | |
889 | ;; top-level alias | |
890 | (make-arity-info toplevel-calls | |
891 | (alist-cons lexical-name val | |
892 | lexical-lambdas) | |
893 | toplevel-lambdas)) | |
894 | (else info)))) | |
895 | ||
896 | (let ((toplevel-calls (toplevel-procedure-calls info)) | |
897 | (lexical-lambdas (lexical-lambdas info)) | |
898 | (toplevel-lambdas (toplevel-lambdas info))) | |
899 | ||
900 | (record-case x | |
901 | ((<toplevel-define> name exp) | |
902 | (record-case exp | |
903 | ((<lambda> body) | |
904 | (make-arity-info toplevel-calls | |
905 | lexical-lambdas | |
906 | (alist-cons name exp toplevel-lambdas))) | |
907 | ((<toplevel-ref> name) | |
908 | ;; alias for another toplevel | |
909 | (let ((proc (assq name toplevel-lambdas))) | |
910 | (make-arity-info toplevel-calls | |
911 | lexical-lambdas | |
912 | (alist-cons (toplevel-define-name x) | |
913 | (if (pair? proc) | |
914 | (cdr proc) | |
915 | exp) | |
916 | toplevel-lambdas)))) | |
917 | (else info))) | |
918 | ((<let> vars vals) | |
919 | (fold extend info vars vals)) | |
920 | ((<letrec> vars vals) | |
921 | (fold extend info vars vals)) | |
922 | ((<fix> vars vals) | |
923 | (fold extend info vars vals)) | |
924 | ||
925 | ((<application> proc args src) | |
926 | (record-case proc | |
927 | ((<lambda> body) | |
928 | (validate-arity proc x #t) | |
929 | info) | |
930 | ((<toplevel-ref> name) | |
931 | (make-arity-info (alist-cons name x toplevel-calls) | |
932 | lexical-lambdas | |
933 | toplevel-lambdas)) | |
934 | ((<lexical-ref> gensym) | |
935 | (let ((proc (assq gensym lexical-lambdas))) | |
936 | (if (pair? proc) | |
937 | (record-case (cdr proc) | |
938 | ((<toplevel-ref> name) | |
939 | ;; alias to toplevel | |
940 | (make-arity-info (alist-cons name x toplevel-calls) | |
941 | lexical-lambdas | |
942 | toplevel-lambdas)) | |
943 | (else | |
944 | (validate-arity (cdr proc) x #t) | |
945 | info)) | |
946 | ||
947 | ;; If GENSYM wasn't found, it may be because it's an | |
948 | ;; argument of the procedure being compiled. | |
949 | info))) | |
950 | (else info))) | |
951 | (else info)))) | |
952 | ||
953 | (lambda (x info env) | |
954 | ;; Up from X. | |
955 | (define (shrink name val info) | |
956 | ;; Remove NAME from the lexical-lambdas of INFO. | |
957 | (let ((toplevel-calls (toplevel-procedure-calls info)) | |
958 | (lexical-lambdas (lexical-lambdas info)) | |
959 | (toplevel-lambdas (toplevel-lambdas info))) | |
960 | (make-arity-info toplevel-calls | |
961 | (alist-delete name lexical-lambdas eq?) | |
962 | toplevel-lambdas))) | |
963 | ||
964 | (let ((toplevel-calls (toplevel-procedure-calls info)) | |
965 | (lexical-lambdas (lexical-lambdas info)) | |
966 | (toplevel-lambdas (toplevel-lambdas info))) | |
967 | (record-case x | |
968 | ((<let> vars vals) | |
969 | (fold shrink info vars vals)) | |
970 | ((<letrec> vars vals) | |
971 | (fold shrink info vars vals)) | |
972 | ((<fix> vars vals) | |
973 | (fold shrink info vars vals)) | |
974 | ||
975 | (else info)))) | |
976 | ||
977 | (lambda (result env) | |
978 | ;; Post-processing: check all top-level procedure calls that have been | |
979 | ;; encountered. | |
980 | (let ((toplevel-calls (toplevel-procedure-calls result)) | |
981 | (toplevel-lambdas (toplevel-lambdas result))) | |
982 | (for-each (lambda (name+application) | |
983 | (let* ((name (car name+application)) | |
984 | (application (cdr name+application)) | |
985 | (proc | |
986 | (or (assoc-ref toplevel-lambdas name) | |
987 | (and (module? env) | |
988 | (false-if-exception | |
989 | (module-ref env name))))) | |
990 | (proc* | |
991 | ;; handle toplevel aliases | |
992 | (if (toplevel-ref? proc) | |
993 | (let ((name (toplevel-ref-name proc))) | |
994 | (and (module? env) | |
995 | (false-if-exception | |
996 | (module-ref env name)))) | |
997 | proc))) | |
998 | ;; (format #t "toplevel-call to ~A (~A) from ~A~%" | |
999 | ;; name proc* application) | |
1000 | (if (or (lambda? proc*) (procedure? proc*)) | |
1001 | (validate-arity proc* application (lambda? proc*))))) | |
1002 | toplevel-calls))) | |
1003 | ||
1004 | (make-arity-info '() '() '()))) |