Commit | Line | Data |
---|---|---|
17e90c5e KN |
1 | ;;; GHIL -> GLIL compiler |
2 | ||
3 | ;; Copyright (C) 2001 Free Software Foundation, Inc. | |
4 | ||
5 | ;; This program is free software; you can redistribute it and/or modify | |
6 | ;; it under the terms of the GNU General Public License as published by | |
7 | ;; the Free Software Foundation; either version 2, or (at your option) | |
8 | ;; any later version. | |
9 | ;; | |
10 | ;; This program 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 | |
13 | ;; GNU General Public License for more details. | |
14 | ;; | |
15 | ;; You should have received a copy of the GNU General Public License | |
16 | ;; along with this program; see the file COPYING. If not, write to | |
17 | ;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
18 | ;; Boston, MA 02111-1307, USA. | |
19 | ||
20 | ;;; Code: | |
21 | ||
d9042285 | 22 | (define-module (language ghil compile-glil) |
1a1a10d3 | 23 | #:use-syntax (system base syntax) |
9ff56d9e AW |
24 | #:use-module (language glil) |
25 | #:use-module (language ghil) | |
1a1a10d3 | 26 | #:use-module (ice-9 common-list) |
d9042285 | 27 | #:export (compile-glil)) |
17e90c5e | 28 | |
d9042285 | 29 | (define (compile-glil x e opts) |
1a1a10d3 | 30 | (if (memq #:O opts) (set! x (optimize x))) |
b0b180d5 AW |
31 | (values (codegen x) |
32 | (and e (cons (car e) (cddr e))))) | |
17e90c5e KN |
33 | |
34 | \f | |
35 | ;;; | |
36 | ;;; Stage 2: Optimization | |
37 | ;;; | |
38 | ||
d51406fe AW |
39 | (define (lift-variables! env) |
40 | (let ((parent-env (ghil-env-parent env))) | |
41 | (for-each (lambda (v) | |
42 | (case (ghil-var-kind v) | |
43 | ((argument) (set! (ghil-var-kind v) 'local))) | |
44 | (set! (ghil-var-env v) parent-env) | |
45 | (ghil-env-add! parent-env v)) | |
46 | (ghil-env-variables env)))) | |
47 | ||
17e90c5e | 48 | (define (optimize x) |
67169b29 | 49 | (record-case x |
61dc81d9 | 50 | ((<ghil-set> env loc var val) |
849cefac | 51 | (make-ghil-set env var (optimize val))) |
3616e9e9 | 52 | |
d51406fe AW |
53 | ((<ghil-define> env loc var val) |
54 | (make-ghil-define env var (optimize val))) | |
55 | ||
61dc81d9 | 56 | ((<ghil-if> env loc test then else) |
22bcbe8c | 57 | (make-ghil-if env loc (optimize test) (optimize then) (optimize else))) |
3616e9e9 | 58 | |
d51406fe AW |
59 | ((<ghil-and> env loc exps) |
60 | (make-ghil-and env loc (map optimize exps))) | |
61 | ||
62 | ((<ghil-or> env loc exps) | |
63 | (make-ghil-or env loc (map optimize exps))) | |
64 | ||
61dc81d9 | 65 | ((<ghil-begin> env loc exps) |
22bcbe8c | 66 | (make-ghil-begin env loc (map optimize exps))) |
3616e9e9 | 67 | |
61dc81d9 | 68 | ((<ghil-bind> env loc vars vals body) |
22bcbe8c | 69 | (make-ghil-bind env loc vars (map optimize vals) (optimize body))) |
3616e9e9 | 70 | |
fbde2b91 AW |
71 | ((<ghil-lambda> env loc vars rest meta body) |
72 | (make-ghil-lambda env loc vars rest meta (optimize body))) | |
3616e9e9 | 73 | |
22bcbe8c AW |
74 | ((<ghil-inline> env loc instruction args) |
75 | (make-ghil-inline env loc instruction (map optimize args))) | |
3616e9e9 | 76 | |
61dc81d9 AW |
77 | ((<ghil-call> env loc proc args) |
78 | (let ((parent-env env)) | |
79 | (record-case proc | |
80 | ;; ((@lambda (VAR...) BODY...) ARG...) => | |
81 | ;; (@let ((VAR ARG) ...) BODY...) | |
fbde2b91 | 82 | ((<ghil-lambda> env loc vars rest meta body) |
61dc81d9 AW |
83 | (cond |
84 | ((not rest) | |
d51406fe AW |
85 | (lift-variables! env) |
86 | (make-ghil-bind parent-env loc (map optimize args))) | |
61dc81d9 | 87 | (else |
22bcbe8c | 88 | (make-ghil-call parent-env loc (optimize proc) (map optimize args))))) |
61dc81d9 | 89 | (else |
22bcbe8c | 90 | (make-ghil-call parent-env loc (optimize proc) (map optimize args)))))) |
61dc81d9 | 91 | |
d51406fe AW |
92 | ((<ghil-mv-call> env loc producer consumer) |
93 | (record-case consumer | |
94 | ;; (mv-call PRODUCER (lambda ARGS BODY...)) => | |
95 | ;; (mv-let PRODUCER ARGS BODY...) | |
96 | ((<ghil-lambda> env loc vars rest meta body) | |
97 | (lift-variables! env) | |
98 | (make-ghil-mv-bind producer vars rest body)) | |
99 | (else | |
100 | (make-ghil-mv-call env loc (optimize producer) (optimize consumer))))) | |
101 | ||
17e90c5e KN |
102 | (else x))) |
103 | ||
104 | \f | |
105 | ;;; | |
106 | ;;; Stage 3: Code generation | |
107 | ;;; | |
108 | ||
849cefac | 109 | (define *ia-void* (make-glil-void)) |
131f7d6c AW |
110 | (define *ia-drop* (make-glil-call 'drop 1)) |
111 | (define *ia-return* (make-glil-call 'return 1)) | |
17e90c5e KN |
112 | |
113 | (define (make-label) (gensym ":L")) | |
114 | ||
115 | (define (make-glil-var op env var) | |
aa0a011b | 116 | (case (ghil-var-kind var) |
17e90c5e | 117 | ((argument) |
aa0a011b | 118 | (make-glil-argument op (ghil-var-index var))) |
17e90c5e | 119 | ((local) |
aa0a011b | 120 | (make-glil-local op (ghil-var-index var))) |
17e90c5e KN |
121 | ((external) |
122 | (do ((depth 0 (1+ depth)) | |
aa0a011b AW |
123 | (e env (ghil-env-parent e))) |
124 | ((eq? e (ghil-var-env var)) | |
125 | (make-glil-external op depth (ghil-var-index var))))) | |
a1122f8c AW |
126 | ((toplevel) |
127 | (make-glil-toplevel op (ghil-var-name var))) | |
fd358575 AW |
128 | ((public private) |
129 | (make-glil-module op (ghil-var-env var) (ghil-var-name var) | |
130 | (eq? (ghil-var-kind var) 'public))) | |
17e90c5e KN |
131 | (else (error "Unknown kind of variable:" var)))) |
132 | ||
1b79210a AW |
133 | (define (constant? x) |
134 | (cond ((or (number? x) (string? x) (symbol? x) (keyword? x) (boolean? x)) #t) | |
135 | ((pair? x) (and (constant? (car x)) | |
136 | (constant? (cdr x)))) | |
137 | ((vector? x) (let lp ((i (vector-length x))) | |
138 | (or (zero? i) | |
139 | (and (constant? (vector-ref x (1- i))) | |
140 | (lp (1- i)))))))) | |
141 | ||
17e90c5e KN |
142 | (define (codegen ghil) |
143 | (let ((stack '())) | |
96969dc1 | 144 | (define (push-code! loc code) |
d0168f3d AW |
145 | (set! stack (cons code stack)) |
146 | (if loc (set! stack (cons (make-glil-source loc) stack)))) | |
d51406fe AW |
147 | (define (var->binding var) |
148 | (list (ghil-var-name var) (ghil-var-kind var) (ghil-var-index var))) | |
96969dc1 | 149 | (define (push-bindings! loc vars) |
aa0a011b | 150 | (if (not (null? vars)) |
d51406fe | 151 | (push-code! loc (make-glil-bind (map var->binding vars))))) |
17e90c5e | 152 | (define (comp tree tail drop) |
cb4cca12 | 153 | (define (push-label! label) |
96969dc1 AW |
154 | (push-code! #f (make-glil-label label))) |
155 | (define (push-branch! loc inst label) | |
156 | (push-code! loc (make-glil-branch inst label))) | |
ac99cb0c | 157 | (define (push-call! loc inst args) |
cb4cca12 | 158 | (for-each comp-push args) |
96969dc1 | 159 | (push-code! loc (make-glil-call inst (length args)))) |
17e90c5e KN |
160 | ;; possible tail position |
161 | (define (comp-tail tree) (comp tree tail drop)) | |
162 | ;; push the result | |
163 | (define (comp-push tree) (comp tree #f #f)) | |
164 | ;; drop the result | |
165 | (define (comp-drop tree) (comp tree #f #t)) | |
cb4cca12 KN |
166 | ;; drop the result if unnecessary |
167 | (define (maybe-drop) | |
96969dc1 | 168 | (if drop (push-code! #f *ia-drop*))) |
cb4cca12 KN |
169 | ;; return here if necessary |
170 | (define (maybe-return) | |
96969dc1 | 171 | (if tail (push-code! #f *ia-return*))) |
17e90c5e | 172 | ;; return this code if necessary |
96969dc1 AW |
173 | (define (return-code! loc code) |
174 | (if (not drop) (push-code! loc code)) | |
cb4cca12 | 175 | (maybe-return)) |
17e90c5e | 176 | ;; return void if necessary |
cb4cca12 | 177 | (define (return-void!) |
96969dc1 | 178 | (return-code! #f *ia-void*)) |
cb4cca12 | 179 | ;; return object if necessary |
96969dc1 | 180 | (define (return-object! loc obj) |
d9d671f7 | 181 | (return-code! loc (make-glil-const obj))) |
17e90c5e KN |
182 | ;; |
183 | ;; dispatch | |
67169b29 AW |
184 | (record-case tree |
185 | ((<ghil-void>) | |
17e90c5e KN |
186 | (return-void!)) |
187 | ||
67169b29 | 188 | ((<ghil-quote> env loc obj) |
96969dc1 | 189 | (return-object! loc obj)) |
cb4cca12 | 190 | |
67169b29 | 191 | ((<ghil-quasiquote> env loc exp) |
2bd859c8 | 192 | (let loop ((x exp) (in-car? #f)) |
67169b29 AW |
193 | (cond |
194 | ((list? x) | |
195 | (push-call! #f 'mark '()) | |
2bd859c8 | 196 | (for-each (lambda (x) (loop x #t)) x) |
67169b29 AW |
197 | (push-call! #f 'list-mark '())) |
198 | ((pair? x) | |
2bd859c8 AW |
199 | (push-call! #f 'mark '()) |
200 | (loop (car x) #t) | |
201 | (loop (cdr x) #f) | |
202 | (push-call! #f 'cons-mark '())) | |
67169b29 AW |
203 | ((record? x) |
204 | (record-case x | |
205 | ((<ghil-unquote> env loc exp) | |
206 | (comp-push exp)) | |
207 | ((<ghil-unquote-splicing> env loc exp) | |
2bd859c8 AW |
208 | (if (not in-car?) |
209 | (error "unquote-splicing in the cdr of a pair" exp)) | |
67169b29 AW |
210 | (comp-push exp) |
211 | (push-call! #f 'list-break '())))) | |
1b79210a | 212 | ((constant? x) |
d9d671f7 | 213 | (push-code! #f (make-glil-const x))) |
67169b29 | 214 | (else |
1b79210a | 215 | (error "element of quasiquote can't be compiled" x)))) |
cb4cca12 KN |
216 | (maybe-drop) |
217 | (maybe-return)) | |
17e90c5e | 218 | |
c2c82b62 AW |
219 | ((<ghil-unquote> env loc exp) |
220 | (error "unquote outside of quasiquote" exp)) | |
221 | ||
222 | ((<ghil-unquote-splicing> env loc exp) | |
223 | (error "unquote-splicing outside of quasiquote" exp)) | |
224 | ||
67169b29 | 225 | ((<ghil-ref> env loc var) |
96969dc1 | 226 | (return-code! loc (make-glil-var 'ref env var))) |
17e90c5e | 227 | |
67169b29 | 228 | ((<ghil-set> env loc var val) |
ac99cb0c | 229 | (comp-push val) |
96969dc1 | 230 | (push-code! loc (make-glil-var 'set env var)) |
ac99cb0c KN |
231 | (return-void!)) |
232 | ||
67169b29 | 233 | ((<ghil-define> env loc var val) |
17e90c5e | 234 | (comp-push val) |
96969dc1 | 235 | (push-code! loc (make-glil-var 'define env var)) |
17e90c5e KN |
236 | (return-void!)) |
237 | ||
67169b29 | 238 | ((<ghil-if> env loc test then else) |
17e90c5e KN |
239 | ;; TEST |
240 | ;; (br-if-not L1) | |
241 | ;; THEN | |
41f248a8 | 242 | ;; (br L2) |
17e90c5e KN |
243 | ;; L1: ELSE |
244 | ;; L2: | |
245 | (let ((L1 (make-label)) (L2 (make-label))) | |
246 | (comp-push test) | |
96969dc1 | 247 | (push-branch! loc 'br-if-not L1) |
17e90c5e | 248 | (comp-tail then) |
96969dc1 | 249 | (if (not tail) (push-branch! #f 'br L2)) |
cb4cca12 | 250 | (push-label! L1) |
17e90c5e | 251 | (comp-tail else) |
cb4cca12 KN |
252 | (if (not tail) (push-label! L2)))) |
253 | ||
67169b29 | 254 | ((<ghil-and> env loc exps) |
cb4cca12 KN |
255 | ;; EXP |
256 | ;; (br-if-not L1) | |
257 | ;; ... | |
258 | ;; TAIL | |
259 | ;; (br L2) | |
260 | ;; L1: (const #f) | |
261 | ;; L2: | |
7e4760e4 AW |
262 | (cond ((null? exps) (return-object! loc #t)) |
263 | ((null? (cdr exps)) (comp-tail (car exps))) | |
264 | (else | |
265 | (let ((L1 (make-label)) (L2 (make-label))) | |
266 | (let lp ((exps exps)) | |
267 | (cond ((null? (cdr exps)) | |
268 | (comp-tail (car exps)) | |
269 | (push-branch! #f 'br L2) | |
270 | (push-label! L1) | |
271 | (return-object! #f #f) | |
272 | (push-label! L2) | |
273 | (maybe-return)) | |
274 | (else | |
275 | (comp-push (car exps)) | |
276 | (push-branch! #f 'br-if-not L1) | |
277 | (lp (cdr exps))))))))) | |
cb4cca12 | 278 | |
67169b29 | 279 | ((<ghil-or> env loc exps) |
cb4cca12 KN |
280 | ;; EXP |
281 | ;; (dup) | |
282 | ;; (br-if L1) | |
283 | ;; (drop) | |
284 | ;; ... | |
285 | ;; TAIL | |
286 | ;; L1: | |
7e4760e4 AW |
287 | (cond ((null? exps) (return-object! loc #f)) |
288 | ((null? (cdr exps)) (comp-tail (car exps))) | |
289 | (else | |
290 | (let ((L1 (make-label))) | |
291 | (let lp ((exps exps)) | |
292 | (cond ((null? (cdr exps)) | |
293 | (comp-tail (car exps)) | |
294 | (push-label! L1) | |
295 | (maybe-return)) | |
296 | (else | |
297 | (comp-push (car exps)) | |
535ed4d0 AW |
298 | (if (not drop) |
299 | (push-call! #f 'dup '())) | |
7e4760e4 | 300 | (push-branch! #f 'br-if L1) |
535ed4d0 | 301 | (if (not drop) |
131f7d6c | 302 | (push-code! loc (make-glil-call 'drop 1))) |
7e4760e4 | 303 | (lp (cdr exps))))))))) |
17e90c5e | 304 | |
67169b29 | 305 | ((<ghil-begin> env loc exps) |
17e90c5e KN |
306 | ;; EXPS... |
307 | ;; TAIL | |
308 | (if (null? exps) | |
309 | (return-void!) | |
310 | (do ((exps exps (cdr exps))) | |
311 | ((null? (cdr exps)) | |
312 | (comp-tail (car exps))) | |
313 | (comp-drop (car exps))))) | |
314 | ||
67169b29 | 315 | ((<ghil-bind> env loc vars vals body) |
17e90c5e KN |
316 | ;; VALS... |
317 | ;; (set VARS)... | |
318 | ;; BODY | |
319 | (for-each comp-push vals) | |
96969dc1 AW |
320 | (push-bindings! loc vars) |
321 | (for-each (lambda (var) (push-code! #f (make-glil-var 'set env var))) | |
a6df585a | 322 | (reverse vars)) |
ac99cb0c | 323 | (comp-tail body) |
96969dc1 | 324 | (push-code! #f (make-glil-unbind))) |
17e90c5e | 325 | |
d51406fe AW |
326 | ((<ghil-mv-bind> env loc producer vars rest body) |
327 | ;; VALS... | |
328 | ;; (set VARS)... | |
329 | ;; BODY | |
330 | (let ((MV (make-label))) | |
331 | (comp-push producer) | |
332 | (push-code! loc (make-glil-mv-call 0 MV)) | |
d9d671f7 | 333 | (push-code! #f (make-glil-const 1)) |
d51406fe AW |
334 | (push-label! MV) |
335 | (push-code! #f (make-glil-mv-bind (map var->binding vars) rest)) | |
336 | (for-each (lambda (var) (push-code! #f (make-glil-var 'set env var))) | |
337 | (reverse vars))) | |
338 | (comp-tail body) | |
339 | (push-code! #f (make-glil-unbind))) | |
340 | ||
fbde2b91 | 341 | ((<ghil-lambda> env loc vars rest meta body) |
96969dc1 | 342 | (return-code! loc (codegen tree))) |
17e90c5e | 343 | |
f540e327 | 344 | ((<ghil-inline> env loc inline args) |
46cd9a34 KN |
345 | ;; ARGS... |
346 | ;; (INST NARGS) | |
76282387 AW |
347 | (let ((tail-table '((call . goto/args) |
348 | (apply . goto/apply) | |
349 | (call/cc . goto/cc)))) | |
350 | (cond ((and tail (assq-ref tail-table inline)) | |
351 | => (lambda (tail-inst) | |
352 | (push-call! loc tail-inst args))) | |
353 | (else | |
354 | (push-call! loc inline args) | |
355 | (maybe-drop) | |
356 | (maybe-return))))) | |
46cd9a34 | 357 | |
a222b0fa AW |
358 | ((<ghil-values> env loc values) |
359 | (cond (tail ;; (lambda () (values 1 2)) | |
360 | (push-call! loc 'return/values values)) | |
361 | (drop ;; (lambda () (values 1 2) 3) | |
362 | (for-each comp-drop values)) | |
363 | (else ;; (lambda () (list (values 10 12) 1)) | |
d9d671f7 AW |
364 | (push-code! #f (make-glil-const 'values)) |
365 | (push-code! #f (make-glil-call 'link-now 1)) | |
366 | (push-code! #f (make-glil-call 'variable-ref 0)) | |
a222b0fa AW |
367 | (push-call! loc 'call values)))) |
368 | ||
ef24c01b AW |
369 | ((<ghil-values*> env loc values) |
370 | (cond (tail ;; (lambda () (apply values '(1 2))) | |
371 | (push-call! loc 'return/values* values)) | |
372 | (drop ;; (lambda () (apply values '(1 2)) 3) | |
373 | (for-each comp-drop values)) | |
374 | (else ;; (lambda () (list (apply values '(10 12)) 1)) | |
d9d671f7 AW |
375 | (push-code! #f (make-glil-const 'values)) |
376 | (push-code! #f (make-glil-call 'link-now 1)) | |
377 | (push-code! #f (make-glil-call 'variable-ref 0)) | |
ef24c01b AW |
378 | (push-call! loc 'apply values)))) |
379 | ||
67169b29 | 380 | ((<ghil-call> env loc proc args) |
17e90c5e | 381 | ;; PROC |
3616e9e9 | 382 | ;; ARGS... |
17e90c5e | 383 | ;; ([tail-]call NARGS) |
17e90c5e | 384 | (comp-push proc) |
f03c31db | 385 | (push-call! loc (if tail 'goto/args 'call) args) |
efbd5892 AW |
386 | (maybe-drop)) |
387 | ||
388 | ((<ghil-mv-call> env loc producer consumer) | |
389 | ;; CONSUMER | |
390 | ;; PRODUCER | |
391 | ;; (mv-call MV) | |
392 | ;; ([tail]-call 1) | |
393 | ;; goto POST | |
394 | ;; MV: [tail-]call/nargs | |
395 | ;; POST: (maybe-drop) | |
396 | (let ((MV (make-label)) (POST (make-label))) | |
397 | (comp-push consumer) | |
398 | (comp-push producer) | |
399 | (push-code! loc (make-glil-mv-call 0 MV)) | |
400 | (push-code! loc (make-glil-call (if tail 'goto/args 'call) 1)) | |
401 | (cond ((not tail) | |
402 | (push-branch! #f 'br POST))) | |
403 | (push-label! MV) | |
404 | (push-code! loc (make-glil-call (if tail 'goto/nargs 'call/nargs) 0)) | |
405 | (cond ((not tail) | |
406 | (push-label! POST) | |
20bdc710 AW |
407 | (maybe-drop))))) |
408 | ||
409 | ((<ghil-reified-env> env loc) | |
410 | (return-object! loc (ghil-env-reify env))))) | |
411 | ||
17e90c5e KN |
412 | ;; |
413 | ;; main | |
67169b29 | 414 | (record-case ghil |
fbde2b91 | 415 | ((<ghil-lambda> env loc vars rest meta body) |
f540e327 AW |
416 | (let* ((evars (ghil-env-variables env)) |
417 | (locs (pick (lambda (v) (eq? (ghil-var-kind v) 'local)) evars)) | |
418 | (exts (pick (lambda (v) (eq? (ghil-var-kind v) 'external)) evars))) | |
17e90c5e | 419 | ;; initialize variable indexes |
f540e327 | 420 | (finalize-index! vars) |
17e90c5e KN |
421 | (finalize-index! locs) |
422 | (finalize-index! exts) | |
ac99cb0c | 423 | ;; meta bindings |
96969dc1 | 424 | (push-bindings! #f vars) |
17e90c5e | 425 | ;; export arguments |
061f7fae | 426 | (do ((n 0 (1+ n)) |
f540e327 | 427 | (l vars (cdr l))) |
17e90c5e KN |
428 | ((null? l)) |
429 | (let ((v (car l))) | |
aa0a011b AW |
430 | (case (ghil-var-kind v) |
431 | ((external) | |
96969dc1 AW |
432 | (push-code! #f (make-glil-argument 'ref n)) |
433 | (push-code! #f (make-glil-external 'set 0 (ghil-var-index v))))))) | |
028e3d06 AW |
434 | ;; push on definition source location |
435 | (if loc (set! stack (cons (make-glil-source loc) stack))) | |
17e90c5e KN |
436 | ;; compile body |
437 | (comp body #t #f) | |
438 | ;; create GLIL | |
c850030f | 439 | (make-glil-program |
c2c82b62 AW |
440 | (length vars) (if rest 1 0) (length locs) (length exts) |
441 | meta (reverse! stack))))))) | |
17e90c5e KN |
442 | |
443 | (define (finalize-index! list) | |
444 | (do ((n 0 (1+ n)) | |
445 | (l list (cdr l))) | |
446 | ((null? l)) | |
aa0a011b | 447 | (let ((v (car l))) (set! (ghil-var-index v) n)))) |