1 ;;; TREE-IL -> GLIL compiler
3 ;; Copyright (C) 2001,2008,2009 Free Software Foundation, Inc.
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.
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.
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
21 (define-module (language tree-il compile-glil)
22 #:use-module (system base syntax)
23 #:use-module (system base pmatch)
24 #:use-module (system base message)
25 #:use-module (ice-9 receive)
26 #:use-module (language glil)
27 #:use-module (system vm instruction)
28 #:use-module (language tree-il)
29 #:use-module (language tree-il optimize)
30 #:use-module (language tree-il analyze)
31 #:export (compile-glil))
35 ;; call-with-values -> mv-bind
36 ;; basic degenerate-case reduction
39 ;; sym -> {lambda -> address}
40 ;; lambda -> (nlocs . closure-vars)
42 ;; address := (local? boxed? . index)
43 ;; free-locs ::= ((sym0 . address0) (sym1 . address1) ...)
44 ;; free variable addresses are relative to parent proc.
46 (define *comp-module* (make-fluid))
48 (define %warning-passes
49 `((unused-variable . ,report-unused-variables)))
51 (define (compile-glil x e opts)
53 (or (and=> (memq #:warnings opts) cadr)
56 (let* ((x (make-lambda (tree-il-src x) '() '() '() x))
57 (x (optimize! x e opts))
58 (allocation (analyze-lexicals x)))
60 ;; Go throught the warning passes.
61 (for-each (lambda (kind)
62 (let ((warn (assoc-ref %warning-passes kind)))
63 (and (procedure? warn)
67 (with-fluid* *comp-module* (or (and e (car e)) (current-module))
69 (values (flatten-lambda x allocation)
70 (and e (cons (car e) (cddr e)))
75 (define *primcall-ops* (make-hash-table))
77 (lambda (x) (hash-set! *primcall-ops* (car x) (cdr x)))
80 ((equal? . 2) . equal?)
92 ((quotient . 2) . quo)
93 ((remainder . 2) . rem)
100 ((set-car! . 2) . set-car!)
101 ((set-cdr! . 2) . set-cdr!)
102 ((null? . 1) . null?)
103 ((list? . 1) . list?)
106 ((@slot-ref . 2) . slot-ref)
107 ((@slot-set! . 3) . slot-set)
108 ((vector-ref . 2) . vector-ref)
109 ((vector-set! . 3) . vector-set)
111 ((bytevector-u8-ref . 2) . bv-u8-ref)
112 ((bytevector-u8-set! . 3) . bv-u8-set)
113 ((bytevector-s8-ref . 2) . bv-s8-ref)
114 ((bytevector-s8-set! . 3) . bv-s8-set)
116 ((bytevector-u16-ref . 3) . bv-u16-ref)
117 ((bytevector-u16-set! . 4) . bv-u16-set)
118 ((bytevector-u16-native-ref . 2) . bv-u16-native-ref)
119 ((bytevector-u16-native-set! . 3) . bv-u16-native-set)
120 ((bytevector-s16-ref . 3) . bv-s16-ref)
121 ((bytevector-s16-set! . 4) . bv-s16-set)
122 ((bytevector-s16-native-ref . 2) . bv-s16-native-ref)
123 ((bytevector-s16-native-set! . 3) . bv-s16-native-set)
125 ((bytevector-u32-ref . 3) . bv-u32-ref)
126 ((bytevector-u32-set! . 4) . bv-u32-set)
127 ((bytevector-u32-native-ref . 2) . bv-u32-native-ref)
128 ((bytevector-u32-native-set! . 3) . bv-u32-native-set)
129 ((bytevector-s32-ref . 3) . bv-s32-ref)
130 ((bytevector-s32-set! . 4) . bv-s32-set)
131 ((bytevector-s32-native-ref . 2) . bv-s32-native-ref)
132 ((bytevector-s32-native-set! . 3) . bv-s32-native-set)
134 ((bytevector-u64-ref . 3) . bv-u64-ref)
135 ((bytevector-u64-set! . 4) . bv-u64-set)
136 ((bytevector-u64-native-ref . 2) . bv-u64-native-ref)
137 ((bytevector-u64-native-set! . 3) . bv-u64-native-set)
138 ((bytevector-s64-ref . 3) . bv-s64-ref)
139 ((bytevector-s64-set! . 4) . bv-s64-set)
140 ((bytevector-s64-native-ref . 2) . bv-s64-native-ref)
141 ((bytevector-s64-native-set! . 3) . bv-s64-native-set)
143 ((bytevector-ieee-single-ref . 3) . bv-f32-ref)
144 ((bytevector-ieee-single-set! . 4) . bv-f32-set)
145 ((bytevector-ieee-single-native-ref . 2) . bv-f32-native-ref)
146 ((bytevector-ieee-single-native-set! . 3) . bv-f32-native-set)
147 ((bytevector-ieee-double-ref . 3) . bv-f64-ref)
148 ((bytevector-ieee-double-set! . 4) . bv-f64-set)
149 ((bytevector-ieee-double-native-ref . 2) . bv-f64-native-ref)
150 ((bytevector-ieee-double-native-set! . 3) . bv-f64-native-set)))
155 (define (make-label) (gensym ":L"))
157 (define (vars->bind-list ids vars allocation proc)
159 (pmatch (hashq-ref (hashq-ref allocation v) proc)
162 (,x (error "badness" x))))
166 (define (emit-bindings src ids vars allocation proc emit-code)
168 (emit-code src (make-glil-bind
169 (vars->bind-list ids vars allocation proc)))))
171 (define (with-output-to-code proc)
173 (define (emit-code src x)
174 (set! out (cons x out))
176 (set! out (cons (make-glil-source src) out))))
180 (define (flatten-lambda x allocation)
181 (receive (ids vars nargs nrest)
182 (let lp ((ids (lambda-names x)) (vars (lambda-vars x))
183 (oids '()) (ovars '()) (n 0))
184 (cond ((null? vars) (values (reverse oids) (reverse ovars) n 0))
185 ((pair? vars) (lp (cdr ids) (cdr vars)
186 (cons (car ids) oids) (cons (car vars) ovars)
188 (else (values (reverse (cons ids oids))
189 (reverse (cons vars ovars))
191 (let ((nlocs (car (hashq-ref allocation x))))
193 nargs nrest nlocs (lambda-meta x)
196 ;; write bindings and source debugging info
197 (emit-bindings #f ids vars allocation x emit-code)
199 (emit-code #f (make-glil-source (lambda-src x))))
200 ;; box args if necessary
203 (pmatch (hashq-ref (hashq-ref allocation v) x)
205 (emit-code #f (make-glil-lexical #t #f 'ref n))
206 (emit-code #f (make-glil-lexical #t #t 'box n)))))
208 ;; and here, here, dear reader: we compile.
209 (flatten (lambda-body x) allocation x emit-code)))))))
211 (define (flatten x allocation proc emit-code)
212 (define (emit-label label)
213 (emit-code #f (make-glil-label label)))
214 (define (emit-branch src inst label)
215 (emit-code src (make-glil-branch inst label)))
217 ;; LMVRA == "let-values MV return address"
218 (let comp ((x x) (context 'tail) (LMVRA #f))
219 (define (comp-tail tree) (comp tree context LMVRA))
220 (define (comp-push tree) (comp tree 'push #f))
221 (define (comp-drop tree) (comp tree 'drop #f))
222 (define (comp-vals tree LMVRA) (comp tree 'vals LMVRA))
227 ((push vals) (emit-code #f (make-glil-void)))
229 (emit-code #f (make-glil-void))
230 (emit-code #f (make-glil-call 'return 1)))))
234 ((push vals) (emit-code src (make-glil-const exp)))
236 (emit-code src (make-glil-const exp))
237 (emit-code #f (make-glil-call 'return 1)))))
239 ;; FIXME: should represent sequence as exps tail
240 ((<sequence> src exps)
241 (let lp ((exps exps))
242 (if (null? (cdr exps))
243 (comp-tail (car exps))
245 (comp-drop (car exps))
248 ((<application> src proc args)
249 ;; FIXME: need a better pattern-matcher here
251 ((and (primitive-ref? proc)
252 (eq? (primitive-ref-name proc) '@apply)
253 (>= (length args) 1))
254 (let ((proc (car args))
257 ((and (primitive-ref? proc) (eq? (primitive-ref-name proc) 'values)
258 (not (eq? context 'push)) (not (eq? context 'vals)))
259 ;; tail: (lambda () (apply values '(1 2)))
260 ;; drop: (lambda () (apply values '(1 2)) 3)
261 ;; push: (lambda () (list (apply values '(10 12)) 1))
263 ((drop) (for-each comp-drop args))
265 (for-each comp-push args)
266 (emit-code src (make-glil-call 'return/values* (length args))))))
272 (for-each comp-push args)
273 (emit-code src (make-glil-call 'goto/apply (1+ (length args)))))
276 (for-each comp-push args)
277 (emit-code src (make-glil-call 'apply (1+ (length args)))))
280 (make-application src (make-primitive-ref #f 'apply)
284 ;; Well, shit. The proc might return any number of
285 ;; values (including 0), since it's in a drop context,
286 ;; yet apply does not create a MV continuation. So we
287 ;; mv-call out to our trampoline instead.
289 (make-application src (make-primitive-ref #f 'apply)
290 (cons proc args)))))))))
292 ((and (primitive-ref? proc) (eq? (primitive-ref-name proc) 'values)
293 (not (eq? context 'push)))
294 ;; tail: (lambda () (values '(1 2)))
295 ;; drop: (lambda () (values '(1 2)) 3)
296 ;; push: (lambda () (list (values '(10 12)) 1))
297 ;; vals: (let-values (((a b ...) (values 1 2 ...))) ...)
299 ((drop) (for-each comp-drop args))
301 (for-each comp-push args)
302 (emit-code #f (make-glil-const (length args)))
303 (emit-branch src 'br LMVRA))
305 (for-each comp-push args)
306 (emit-code src (make-glil-call 'return/values (length args))))))
308 ((and (primitive-ref? proc)
309 (eq? (primitive-ref-name proc) '@call-with-values)
316 ;; MV: [tail-]call/nargs
317 ;; POST: (maybe-drop)
322 (make-application src (make-primitive-ref #f 'call-with-values)
326 (let ((MV (make-label)) (POST (make-label))
327 (producer (car args)) (consumer (cadr args)))
330 (emit-code src (make-glil-mv-call 0 MV))
332 ((tail) (emit-code src (make-glil-call 'goto/args 1)))
333 (else (emit-code src (make-glil-call 'call 1))
334 (emit-branch #f 'br POST)))
337 ((tail) (emit-code src (make-glil-call 'goto/nargs 0)))
338 (else (emit-code src (make-glil-call 'call/nargs 0))
340 (if (eq? context 'drop)
341 (emit-code #f (make-glil-call 'drop 1)))))))))
343 ((and (primitive-ref? proc)
344 (eq? (primitive-ref-name proc) '@call-with-current-continuation)
348 (comp-push (car args))
349 (emit-code src (make-glil-call 'goto/cc 1)))
353 src (make-primitive-ref #f 'call-with-current-continuation)
357 (comp-push (car args))
358 (emit-code src (make-glil-call 'call/cc 1)))
360 ;; Crap. Just like `apply' in drop context.
363 src (make-primitive-ref #f 'call-with-current-continuation)
366 ((and (primitive-ref? proc)
367 (or (hash-ref *primcall-ops*
368 (cons (primitive-ref-name proc) (length args)))
369 (hash-ref *primcall-ops* (primitive-ref-name proc))))
371 (for-each comp-push args)
372 (emit-code src (make-glil-call op (length args)))
373 (case (instruction-pushes op)
376 ((tail) (emit-code #f (make-glil-void))
377 (emit-code #f (make-glil-call 'return 1)))
378 ((push vals) (emit-code #f (make-glil-void)))))
381 ((tail) (emit-code #f (make-glil-call 'return 1)))
382 ((drop) (emit-code #f (make-glil-call 'drop 1)))))
384 (error "bad primitive op: too many pushes"
385 op (instruction-pushes op))))))
389 (for-each comp-push args)
390 (let ((len (length args)))
392 ((tail) (emit-code src (make-glil-call 'goto/args len)))
393 ((push) (emit-code src (make-glil-call 'call len)))
394 ((vals) (emit-code src (make-glil-call 'mv-call len LMVRA)))
396 (let ((MV (make-label)) (POST (make-label)))
397 (emit-code src (make-glil-mv-call len MV))
398 (emit-code #f (make-glil-call 'drop 1))
399 (emit-branch #f 'br POST)
401 (emit-code #f (make-glil-mv-bind '() #f))
402 (emit-code #f (make-glil-unbind))
403 (emit-label POST))))))))
405 ((<conditional> src test then else)
412 (let ((L1 (make-label)) (L2 (make-label)))
414 (emit-branch src 'br-if-not L1)
416 (if (not (eq? context 'tail))
417 (emit-branch #f 'br L2))
420 (if (not (eq? context 'tail))
423 ((<primitive-ref> src name)
425 ((eq? (module-variable (fluid-ref *comp-module*) name)
426 (module-variable the-root-module name))
429 (emit-code src (make-glil-toplevel 'ref name)))
431 (emit-code src (make-glil-toplevel 'ref name))
432 (emit-code #f (make-glil-call 'return 1)))))
434 (pk 'ew-the-badness x (current-module) (fluid-ref *comp-module*))
437 (emit-code src (make-glil-module 'ref '(guile) name #f)))
439 (emit-code src (make-glil-module 'ref '(guile) name #f))
440 (emit-code #f (make-glil-call 'return 1)))))))
442 ((<lexical-ref> src name gensym)
445 (pmatch (hashq-ref (hashq-ref allocation gensym) proc)
446 ((,local? ,boxed? . ,index)
447 (emit-code src (make-glil-lexical local? boxed? 'ref index)))
449 (error "badness" x loc)))))
451 ((tail) (emit-code #f (make-glil-call 'return 1)))))
453 ((<lexical-set> src name gensym exp)
455 (pmatch (hashq-ref (hashq-ref allocation gensym) proc)
456 ((,local? ,boxed? . ,index)
457 (emit-code src (make-glil-lexical local? boxed? 'set index)))
459 (error "badness" x loc)))
462 (emit-code #f (make-glil-void)))
464 (emit-code #f (make-glil-void))
465 (emit-code #f (make-glil-call 'return 1)))))
467 ((<module-ref> src mod name public?)
468 (emit-code src (make-glil-module 'ref mod name public?))
470 ((drop) (emit-code #f (make-glil-call 'drop 1)))
471 ((tail) (emit-code #f (make-glil-call 'return 1)))))
473 ((<module-set> src mod name public? exp)
475 (emit-code src (make-glil-module 'set mod name public?))
478 (emit-code #f (make-glil-void)))
480 (emit-code #f (make-glil-void))
481 (emit-code #f (make-glil-call 'return 1)))))
483 ((<toplevel-ref> src name)
484 (emit-code src (make-glil-toplevel 'ref name))
486 ((drop) (emit-code #f (make-glil-call 'drop 1)))
487 ((tail) (emit-code #f (make-glil-call 'return 1)))))
489 ((<toplevel-set> src name exp)
491 (emit-code src (make-glil-toplevel 'set name))
494 (emit-code #f (make-glil-void)))
496 (emit-code #f (make-glil-void))
497 (emit-code #f (make-glil-call 'return 1)))))
499 ((<toplevel-define> src name exp)
501 (emit-code src (make-glil-toplevel 'define name))
504 (emit-code #f (make-glil-void)))
506 (emit-code #f (make-glil-void))
507 (emit-code #f (make-glil-call 'return 1)))))
510 (let ((free-locs (cdr (hashq-ref allocation x))))
513 (emit-code #f (flatten-lambda x allocation))
514 (if (not (null? free-locs))
519 ((,local? ,boxed? . ,n)
520 (emit-code #f (make-glil-lexical local? #f 'ref n)))
521 (else (error "what" x loc))))
523 (emit-code #f (make-glil-call 'vector (length free-locs)))
524 (emit-code #f (make-glil-call 'make-closure 2))))
525 (if (eq? context 'tail)
526 (emit-code #f (make-glil-call 'return 1)))))))
528 ((<let> src names vars vals body)
529 (for-each comp-push vals)
530 (emit-bindings src names vars allocation proc emit-code)
531 (for-each (lambda (v)
532 (pmatch (hashq-ref (hashq-ref allocation v) proc)
534 (emit-code src (make-glil-lexical #t #f 'set n)))
536 (emit-code src (make-glil-lexical #t #t 'box n)))
537 (,loc (error "badness" x loc))))
540 (emit-code #f (make-glil-unbind)))
542 ((<letrec> src names vars vals body)
543 (for-each (lambda (v)
544 (pmatch (hashq-ref (hashq-ref allocation v) proc)
546 (emit-code src (make-glil-lexical #t #t 'empty-box n)))
547 (,loc (error "badness" x loc))))
549 (for-each comp-push vals)
550 (emit-bindings src names vars allocation proc emit-code)
551 (for-each (lambda (v)
552 (pmatch (hashq-ref (hashq-ref allocation v) proc)
554 (emit-code src (make-glil-lexical #t #t 'set n)))
555 (,loc (error "badness" x loc))))
558 (emit-code #f (make-glil-unbind)))
560 ((<let-values> src names vars exp body)
561 (let lp ((names '()) (vars '()) (inames names) (ivars vars) (rest? #f))
564 (lp (cons (car inames) names) (cons (car ivars) vars)
565 (cdr inames) (cdr ivars) #f))
566 ((not (null? inames))
567 (lp (cons inames names) (cons ivars vars) '() '() #t))
569 (let ((names (reverse! names))
570 (vars (reverse! vars))
573 (emit-code #f (make-glil-const 1))
575 (emit-code src (make-glil-mv-bind
576 (vars->bind-list names vars allocation proc)
578 (for-each (lambda (v)
579 (pmatch (hashq-ref (hashq-ref allocation v) proc)
581 (emit-code src (make-glil-lexical #t #f 'set n)))
583 (emit-code src (make-glil-lexical #t #t 'box n)))
584 (,loc (error "badness" x loc))))
587 (emit-code #f (make-glil-unbind))))))))))