836f10e8e0ab334f2baca564dec36bc97afd5d38
[bpt/guile.git] / module / language / tree-il / compile-cps.scm
1 ;;; Continuation-passing style (CPS) intermediate language (IL)
2
3 ;; Copyright (C) 2013 Free Software Foundation, Inc.
4
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
18
19 ;;; Commentary:
20 ;;;
21 ;;; This pass converts Tree-IL to the continuation-passing style (CPS)
22 ;;; language.
23 ;;;
24 ;;; CPS is a lower-level representation than Tree-IL. Converting to
25 ;;; CPS, beyond adding names for all control points and all values,
26 ;;; simplifies expressions in the following ways, among others:
27 ;;;
28 ;;; * Fixing the order of evaluation.
29 ;;;
30 ;;; * Converting assigned variables to boxed variables.
31 ;;;
32 ;;; * Requiring that Scheme's <letrec> has already been lowered to
33 ;;; <fix>.
34 ;;;
35 ;;; * Inlining default-value initializers into lambda-case
36 ;;; expressions.
37 ;;;
38 ;;; * Inlining prompt bodies.
39 ;;;
40 ;;; * Turning toplevel and module references into primcalls. This
41 ;;; involves explicitly modelling the "scope" of toplevel lookups
42 ;;; (indicating the module with respect to which toplevel bindings
43 ;;; are resolved).
44 ;;;
45 ;;; The utility of CPS is that it gives a name to everything: every
46 ;;; intermediate value, and every control point (continuation). As such
47 ;;; it is more verbose than Tree-IL, but at the same time more simple as
48 ;;; the number of concepts is reduced.
49 ;;;
50 ;;; Code:
51
52 (define-module (language tree-il compile-cps)
53 #:use-module (ice-9 match)
54 #:use-module ((srfi srfi-1) #:select (fold fold-right filter-map))
55 #:use-module (srfi srfi-26)
56 #:use-module ((system foreign) #:select (make-pointer pointer->scm))
57 #:use-module (language cps)
58 #:use-module (language cps primitives)
59 #:use-module (language tree-il analyze)
60 #:use-module (language tree-il optimize)
61 #:use-module ((language tree-il) #:hide (let-gensyms))
62 #:export (compile-cps))
63
64 ;;; Guile's semantics are that a toplevel lambda captures a reference on
65 ;;; the current module, and that all contained lambdas use that module
66 ;;; to resolve toplevel variables. This parameter tracks whether or not
67 ;;; we are in a toplevel lambda. If we are in a lambda, the parameter
68 ;;; is bound to a fresh name identifying the module that was current
69 ;;; when the toplevel lambda is defined.
70 ;;;
71 ;;; This is more complicated than it need be. Ideally we should resolve
72 ;;; all toplevel bindings to bindings from specific modules, unless the
73 ;;; binding is unbound. This is always valid if the compilation unit
74 ;;; sets the module explicitly, as when compiling a module, but it
75 ;;; doesn't work for files auto-compiled for use with `load'.
76 ;;;
77 (define current-topbox-scope (make-parameter #f))
78
79 (define (toplevel-box src name bound? val-proc)
80 (let-gensyms (name-sym bound?-sym kbox box)
81 (build-cps-term
82 ($letconst (('name name-sym name)
83 ('bound? bound?-sym bound?))
84 ($letk ((kbox src ($kargs ('box) (box) ,(val-proc box))))
85 ,(match (current-topbox-scope)
86 (#f
87 (build-cps-term
88 ($continue kbox
89 ($primcall 'resolve
90 (name-sym bound?-sym)))))
91 (scope
92 (let-gensyms (scope-sym)
93 (build-cps-term
94 ($letconst (('scope scope-sym scope))
95 ($continue kbox
96 ($primcall 'cached-toplevel-box
97 (scope-sym name-sym bound?-sym)))))))))))))
98
99 (define (module-box src module name public? bound? val-proc)
100 (let-gensyms (module-sym name-sym public?-sym bound?-sym kbox box)
101 (build-cps-term
102 ($letconst (('module module-sym module)
103 ('name name-sym name)
104 ('public? public?-sym public?)
105 ('bound? bound?-sym bound?))
106 ($letk ((kbox src ($kargs ('box) (box) ,(val-proc box))))
107 ($continue kbox
108 ($primcall 'cached-module-box
109 (module-sym name-sym public?-sym bound?-sym))))))))
110
111 (define (capture-toplevel-scope src scope k)
112 (let-gensyms (module scope-sym kmodule)
113 (build-cps-term
114 ($letconst (('scope scope-sym scope))
115 ($letk ((kmodule src ($kargs ('module) (module)
116 ($continue k
117 ($primcall 'cache-current-module!
118 (module scope-sym))))))
119 ($continue kmodule
120 ($primcall 'current-module ())))))))
121
122 (define (fold-formals proc seed arity gensyms inits)
123 (match arity
124 (($ $arity req opt rest kw allow-other-keys?)
125 (let ()
126 (define (fold-req names gensyms seed)
127 (match names
128 (() (fold-opt opt gensyms inits seed))
129 ((name . names)
130 (proc name (car gensyms) #f
131 (fold-req names (cdr gensyms) seed)))))
132 (define (fold-opt names gensyms inits seed)
133 (match names
134 (() (fold-rest rest gensyms inits seed))
135 ((name . names)
136 (proc name (car gensyms) (car inits)
137 (fold-opt names (cdr gensyms) (cdr inits) seed)))))
138 (define (fold-rest rest gensyms inits seed)
139 (match rest
140 (#f (fold-kw kw gensyms inits seed))
141 (name (proc name (car gensyms) #f
142 (fold-kw kw (cdr gensyms) inits seed)))))
143 (define (fold-kw kw gensyms inits seed)
144 (match kw
145 (()
146 (unless (null? gensyms)
147 (error "too many gensyms"))
148 (unless (null? inits)
149 (error "too many inits"))
150 seed)
151 (((key name var) . kw)
152 (unless (eq? var (car gensyms))
153 (error "unexpected keyword arg order"))
154 (proc name var (car inits)
155 (fold-kw kw (cdr gensyms) (cdr inits) seed)))))
156 (fold-req req gensyms seed)))))
157
158 (define (unbound? src sym kt kf)
159 (define tc8-iflag 4)
160 (define unbound-val 9)
161 (define unbound-bits (logior (ash unbound-val 8) tc8-iflag))
162 (let-gensyms (unbound ktest)
163 (build-cps-term
164 ($letconst (('unbound unbound (pointer->scm (make-pointer unbound-bits))))
165 ($letk ((ktest src ($kif kt kf)))
166 ($continue ktest
167 ($primcall 'eq? (sym unbound))))))))
168
169 (define (init-default-value name sym subst init body)
170 (match (assq-ref subst sym)
171 ((subst-sym box?)
172 (let ((src (tree-il-src init)))
173 (define (maybe-box k make-body)
174 (if box?
175 (let-gensyms (kbox phi)
176 (build-cps-term
177 ($letk ((kbox src ($kargs (name) (phi)
178 ($continue k ($primcall 'box (phi))))))
179 ,(make-body kbox))))
180 (make-body k)))
181 (let-gensyms (knext kbound kunbound)
182 (build-cps-term
183 ($letk ((knext src ($kargs (name) (subst-sym) ,body)))
184 ,(maybe-box
185 knext
186 (lambda (k)
187 (build-cps-term
188 ($letk ((kbound src ($kargs () () ($continue k ($var sym))))
189 (kunbound src ($kargs () () ,(convert init k subst))))
190 ,(unbound? src sym kunbound kbound))))))))))))
191
192 ;; exp k-name alist -> term
193 (define (convert exp k subst)
194 ;; exp (v-name -> term) -> term
195 (define (convert-arg exp k)
196 (match exp
197 (($ <lexical-ref> src name sym)
198 (match (assq-ref subst sym)
199 ((box #t)
200 (let-gensyms (kunboxed unboxed)
201 (build-cps-term
202 ($letk ((kunboxed src ($kargs ('unboxed) (unboxed) ,(k unboxed))))
203 ($continue kunboxed ($primcall 'box-ref (box)))))))
204 ((subst #f) (k subst))
205 (#f (k sym))))
206 (else
207 (let ((src (tree-il-src exp)))
208 (let-gensyms (karg arg)
209 (build-cps-term
210 ($letk ((karg src ($kargs ('arg) (arg) ,(k arg))))
211 ,(convert exp karg subst))))))))
212 ;; (exp ...) ((v-name ...) -> term) -> term
213 (define (convert-args exps k)
214 (match exps
215 (() (k '()))
216 ((exp . exps)
217 (convert-arg exp
218 (lambda (name)
219 (convert-args exps
220 (lambda (names)
221 (k (cons name names)))))))))
222 (define (box-bound-var name sym body)
223 (match (assq-ref subst sym)
224 ((box #t)
225 (let-gensyms (k)
226 (build-cps-term
227 ($letk ((k #f ($kargs (name) (box) ,body)))
228 ($continue k ($primcall 'box (sym)))))))
229 (else body)))
230
231 (match exp
232 (($ <lexical-ref> src name sym)
233 (match (assq-ref subst sym)
234 ((box #t) (build-cps-term ($continue k ($primcall 'box-ref (box)))))
235 ((subst #f) (build-cps-term ($continue k ($var subst))))
236 (#f (build-cps-term ($continue k ($var sym))))))
237
238 (($ <void> src)
239 (build-cps-term ($continue k ($void))))
240
241 (($ <const> src exp)
242 (build-cps-term ($continue k ($const exp))))
243
244 (($ <primitive-ref> src name)
245 (build-cps-term ($continue k ($prim name))))
246
247 (($ <lambda> fun-src meta body)
248 (let ()
249 (define (convert-clauses body ktail)
250 (match body
251 (#f '())
252 (($ <lambda-case> src req opt rest kw inits gensyms body alternate)
253 (let* ((arity (make-$arity req (or opt '()) rest
254 (if kw (cdr kw) '()) (and kw (car kw))))
255 (names (fold-formals (lambda (name sym init names)
256 (cons name names))
257 '()
258 arity gensyms inits)))
259 (cons
260 (let-gensyms (kclause kargs)
261 (build-cps-cont
262 (kclause
263 src
264 ($kclause ,arity
265 (kargs
266 src
267 ($kargs names gensyms
268 ,(fold-formals
269 (lambda (name sym init body)
270 (if init
271 (init-default-value name sym subst init body)
272 (box-bound-var name sym body)))
273 (convert body ktail subst)
274 arity gensyms inits)))))))
275 (convert-clauses alternate ktail))))))
276 (if (current-topbox-scope)
277 (let-gensyms (kentry self ktail)
278 (build-cps-term
279 ($continue k
280 ($fun meta '()
281 (kentry fun-src
282 ($kentry self (ktail #f ($ktail))
283 ,(convert-clauses body ktail)))))))
284 (let-gensyms (scope kscope)
285 (build-cps-term
286 ($letk ((kscope fun-src
287 ($kargs () ()
288 ,(parameterize ((current-topbox-scope scope))
289 (convert exp k subst)))))
290 ,(capture-toplevel-scope fun-src scope kscope)))))))
291
292 (($ <module-ref> src mod name public?)
293 (module-box
294 src mod name public? #t
295 (lambda (box)
296 (build-cps-term ($continue k ($primcall 'box-ref (box)))))))
297
298 (($ <module-set> src mod name public? exp)
299 (convert-arg exp
300 (lambda (val)
301 (module-box
302 src mod name public? #f
303 (lambda (box)
304 (build-cps-term ($continue k ($primcall 'box-set! (box val)))))))))
305
306 (($ <toplevel-ref> src name)
307 (toplevel-box
308 src name #t
309 (lambda (box)
310 (build-cps-term ($continue k ($primcall 'box-ref (box)))))))
311
312 (($ <toplevel-set> src name exp)
313 (convert-arg exp
314 (lambda (val)
315 (toplevel-box
316 src name #f
317 (lambda (box)
318 (build-cps-term ($continue k ($primcall 'box-set! (box val)))))))))
319
320 (($ <toplevel-define> src name exp)
321 (convert-arg exp
322 (lambda (val)
323 (let-gensyms (kname name-sym)
324 (build-cps-term
325 ($letconst (('name name-sym name))
326 ($continue k ($primcall 'define! (name-sym val)))))))))
327
328 (($ <call> src proc args)
329 (convert-args (cons proc args)
330 (match-lambda
331 ((proc . args)
332 (build-cps-term ($continue k ($call proc args)))))))
333
334 (($ <primcall> src name args)
335 (case name
336 ((list)
337 (convert (fold-right (lambda (elem tail)
338 (make-primcall src 'cons
339 (list elem tail)))
340 (make-const src '())
341 args)
342 k subst))
343 (else
344 (if (branching-primitive? name)
345 (convert (make-conditional src exp (make-const #f #t)
346 (make-const #f #f))
347 k subst)
348 (convert-args args
349 (lambda (args)
350 (if (eq? name 'values)
351 (build-cps-term ($continue k ($values args)))
352 (build-cps-term ($continue k ($primcall name args))))))))))
353
354 ;; Prompts with inline handlers.
355 (($ <prompt> src escape-only? tag body
356 ($ <lambda> hsrc hmeta
357 ($ <lambda-case> _ hreq #f hrest #f () hsyms hbody #f)))
358 ;; Handler:
359 ;; khargs: check args returned to handler, -> khbody
360 ;; khbody: the handler, -> k
361 ;;
362 ;; Post-body:
363 ;; krest: collect return vals from body to list, -> kpop
364 ;; kpop: pop the prompt, -> kprim
365 ;; kprim: load the values primitive, -> kret
366 ;; kret: (apply values rvals), -> k
367 ;;
368 ;; Escape prompts evaluate the body with the continuation of krest.
369 ;; Otherwise we do a no-inline call to body, continuing to krest.
370 (convert-arg tag
371 (lambda (tag)
372 (let ((hnames (append hreq (if hrest (list hrest) '()))))
373 (let-gensyms (khargs khbody kret kprim prim kpop krest vals kbody)
374 (build-cps-term
375 ($letk* ((khbody hsrc ($kargs hnames hsyms
376 ,(fold box-bound-var
377 (convert hbody k subst)
378 hnames hsyms)))
379 (khargs hsrc ($ktrunc hreq hrest khbody))
380 (kpop src
381 ($kargs ('rest) (vals)
382 ($letk ((kret
383 src
384 ($kargs () ()
385 ($letk ((kprim
386 src
387 ($kargs ('prim) (prim)
388 ($continue k
389 ($primcall 'apply
390 (prim vals))))))
391 ($continue kprim
392 ($prim 'values))))))
393 ($continue kret
394 ($primcall 'pop-prompt ())))))
395 (krest src ($ktrunc '() 'rest kpop)))
396 ,(if escape-only?
397 (build-cps-term
398 ($letk ((kbody (tree-il-src body)
399 ($kargs () ()
400 ,(convert body krest subst))))
401 ($continue kbody ($prompt #t tag khargs))))
402 (convert-arg body
403 (lambda (thunk)
404 (build-cps-term
405 ($letk ((kbody (tree-il-src body)
406 ($kargs () ()
407 ($continue krest
408 ($primcall 'call-thunk/no-inline
409 (thunk))))))
410 ($continue kbody
411 ($prompt #f tag khargs))))))))))))))
412
413 ;; Eta-convert prompts without inline handlers.
414 (($ <prompt> src escape-only? tag body handler)
415 (let-gensyms (h args)
416 (convert
417 (make-let
418 src (list 'h) (list h) (list handler)
419 (make-seq
420 src
421 (make-conditional
422 src
423 (make-primcall src 'procedure? (list (make-lexical-ref #f 'h h)))
424 (make-void src)
425 (make-primcall
426 src 'scm-error
427 (list
428 (make-const #f 'wrong-type-arg)
429 (make-const #f "call-with-prompt")
430 (make-const #f "Wrong type (expecting procedure): ~S")
431 (make-primcall #f 'list (list (make-lexical-ref #f 'h h)))
432 (make-primcall #f 'list (list (make-lexical-ref #f 'h h))))))
433 (make-prompt
434 src escape-only? tag body
435 (make-lambda
436 src '()
437 (make-lambda-case
438 src '() #f 'args #f '() (list args)
439 (make-primcall
440 src 'apply
441 (list (make-lexical-ref #f 'h h)
442 (make-lexical-ref #f 'args args)))
443 #f)))))
444 k
445 subst)))
446
447 (($ <abort> src tag args tail)
448 (convert-args (append (list tag) args (list tail))
449 (lambda (args*)
450 (build-cps-term ($continue k ($primcall 'abort args*))))))
451
452 (($ <conditional> src test consequent alternate)
453 (let-gensyms (kif kt kf)
454 (build-cps-term
455 ($letk* ((kt (tree-il-src consequent) ($kargs () ()
456 ,(convert consequent k subst)))
457 (kf (tree-il-src alternate) ($kargs () ()
458 ,(convert alternate k subst)))
459 (kif src ($kif kt kf)))
460 ,(match test
461 (($ <primcall> src (? branching-primitive? name) args)
462 (convert-args args
463 (lambda (args)
464 (build-cps-term ($continue kif ($primcall name args))))))
465 (_ (convert-arg test
466 (lambda (test)
467 (build-cps-term ($continue kif ($var test)))))))))))
468
469 (($ <lexical-set> src name gensym exp)
470 (convert-arg exp
471 (lambda (exp)
472 (match (assq-ref subst gensym)
473 ((box #t)
474 (build-cps-term
475 ($continue k ($primcall 'box-set! (box exp)))))))))
476
477 (($ <seq> src head tail)
478 (let-gensyms (ktrunc kseq)
479 (build-cps-term
480 ($letk* ((kseq (tree-il-src tail) ($kargs () ()
481 ,(convert tail k subst)))
482 (ktrunc src ($ktrunc '() #f kseq)))
483 ,(convert head ktrunc subst)))))
484
485 (($ <let> src names syms vals body)
486 (let lp ((names names) (syms syms) (vals vals))
487 (match (list names syms vals)
488 ((() () ()) (convert body k subst))
489 (((name . names) (sym . syms) (val . vals))
490 (let-gensyms (klet)
491 (build-cps-term
492 ($letk ((klet src ($kargs (name) (sym)
493 ,(box-bound-var name sym
494 (lp names syms vals)))))
495 ,(convert val klet subst))))))))
496
497 (($ <fix> src names gensyms funs body)
498 ;; Some letrecs can be contified; that happens later.
499 (if (current-topbox-scope)
500 (let-gensyms (self)
501 (build-cps-term
502 ($letrec names
503 gensyms
504 (map (lambda (fun)
505 (match (convert fun k subst)
506 (($ $continue _ (and fun ($ $fun)))
507 fun)))
508 funs)
509 ,(convert body k subst))))
510 (let-gensyms (scope kscope)
511 (build-cps-term
512 ($letk ((kscope src ($kargs () ()
513 ,(parameterize ((current-topbox-scope scope))
514 (convert exp k subst)))))
515 ,(capture-toplevel-scope src scope kscope))))))
516
517 (($ <let-values> src exp
518 ($ <lambda-case> lsrc req #f rest #f () syms body #f))
519 (let ((names (append req (if rest (list rest) '()))))
520 (let-gensyms (ktrunc kargs)
521 (build-cps-term
522 ($letk* ((kargs src ($kargs names syms
523 ,(fold box-bound-var
524 (convert body k subst)
525 names syms)))
526 (ktrunc src ($ktrunc req rest kargs)))
527 ,(convert exp ktrunc subst))))))))
528
529 (define (build-subst exp)
530 "Compute a mapping from lexical gensyms to substituted gensyms. The
531 usual reason to replace one variable by another is assignment
532 conversion. Default argument values is the other reason.
533
534 Returns a list of (ORIG-SYM SUBST-SYM BOXED?). A true value for BOXED?
535 indicates that the replacement variable is in a box."
536 (define (box-set-vars exp subst)
537 (match exp
538 (($ <lexical-set> src name sym exp)
539 (if (assq sym subst)
540 subst
541 (cons (list sym (gensym "b") #t) subst)))
542 (_ subst)))
543 (define (default-args exp subst)
544 (match exp
545 (($ <lambda-case> src req opt rest kw inits gensyms body alternate)
546 (fold-formals (lambda (name sym init subst)
547 (if init
548 (let ((box? (match (assq-ref subst sym)
549 ((box #t) #t)
550 (#f #f)))
551 (subst-sym (gensym (symbol->string name))))
552 (cons (list sym subst-sym box?) subst))
553 subst))
554 subst
555 (make-$arity req (or opt '()) rest
556 (if kw (cdr kw) '()) (and kw (car kw)))
557 gensyms
558 inits))
559 (_ subst)))
560 (tree-il-fold box-set-vars default-args '() exp))
561
562 (define (cps-convert/thunk exp)
563 (let ((src (tree-il-src exp)))
564 (let-gensyms (kinit init ktail kclause kbody)
565 (build-cps-exp
566 ($fun '() '()
567 (kinit src
568 ($kentry init
569 (ktail #f ($ktail))
570 ((kclause src
571 ($kclause ('() '() #f '() #f)
572 (kbody src
573 ($kargs () ()
574 ,(convert exp ktail
575 (build-subst exp))))))))))))))
576
577 (define *comp-module* (make-fluid))
578
579 (define %warning-passes
580 `((unused-variable . ,unused-variable-analysis)
581 (unused-toplevel . ,unused-toplevel-analysis)
582 (unbound-variable . ,unbound-variable-analysis)
583 (arity-mismatch . ,arity-analysis)
584 (format . ,format-analysis)))
585
586 (define (optimize-tree-il x e opts)
587 (define warnings
588 (or (and=> (memq #:warnings opts) cadr)
589 '()))
590
591 ;; Go through the warning passes.
592 (let ((analyses (filter-map (lambda (kind)
593 (assoc-ref %warning-passes kind))
594 warnings)))
595 (analyze-tree analyses x e))
596
597 (optimize x e opts))
598
599 (define (compile-cps exp env opts)
600 (values (cps-convert/thunk (optimize-tree-il exp env opts))
601 env
602 env))
603
604 ;;; Local Variables:
605 ;;; eval: (put 'convert-arg 'scheme-indent-function 1)
606 ;;; eval: (put 'convert-args 'scheme-indent-function 1)
607 ;;; End: