module/language/tree-il/compile-cps.scm

   1 ;;; Continuation-passing style (CPS) intermediate language (IL)
   2
   3 ;; Copyright (C) 2013, 2014, 2015 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)
  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 (define scope-counter (make-parameter #f))
  79
  80 (define (fresh-scope-id)
  81   (let ((scope-id (scope-counter)))
  82     (scope-counter (1+ scope-id))
  83     scope-id))
  84
  85 (define (toplevel-box src name bound? val-proc)
  86   (let-fresh (kbox) (name-sym bound?-sym box)
  87     (build-cps-term
  88       ($letconst (('name name-sym name)
  89                   ('bound? bound?-sym bound?))
  90         ($letk ((kbox ($kargs ('box) (box) ,(val-proc box))))
  91           ,(match (current-topbox-scope)
  92              (#f
  93               (build-cps-term
  94                 ($continue kbox src
  95                   ($primcall 'resolve
  96                              (name-sym bound?-sym)))))
  97              (scope-id
  98               (let-fresh () (scope-sym)
  99                 (build-cps-term
 100                   ($letconst (('scope scope-sym scope-id))
 101                     ($continue kbox src
 102                       ($primcall 'cached-toplevel-box
 103                                  (scope-sym name-sym bound?-sym)))))))))))))
 104
 105 (define (module-box src module name public? bound? val-proc)
 106   (let-fresh (kbox) (module-sym name-sym public?-sym bound?-sym box)
 107     (build-cps-term
 108       ($letconst (('module module-sym module)
 109                   ('name name-sym name)
 110                   ('public? public?-sym public?)
 111                   ('bound? bound?-sym bound?))
 112         ($letk ((kbox ($kargs ('box) (box) ,(val-proc box))))
 113           ($continue kbox src
 114             ($primcall 'cached-module-box
 115                        (module-sym name-sym public?-sym bound?-sym))))))))
 116
 117 (define (capture-toplevel-scope src scope-id k)
 118   (let-fresh (kmodule) (module scope-sym)
 119     (build-cps-term
 120       ($letconst (('scope scope-sym scope-id))
 121         ($letk ((kmodule ($kargs ('module) (module)
 122                            ($continue k src
 123                              ($primcall 'cache-current-module!
 124                                         (module scope-sym))))))
 125           ($continue kmodule src
 126             ($primcall 'current-module ())))))))
 127
 128 (define (fold-formals proc seed arity gensyms inits)
 129   (match arity
 130     (($ $arity req opt rest kw allow-other-keys?)
 131      (let ()
 132        (define (fold-req names gensyms seed)
 133          (match names
 134            (() (fold-opt opt gensyms inits seed))
 135            ((name . names)
 136             (proc name (car gensyms) #f
 137                   (fold-req names (cdr gensyms) seed)))))
 138        (define (fold-opt names gensyms inits seed)
 139          (match names
 140            (() (fold-rest rest gensyms inits seed))
 141            ((name . names)
 142             (proc name (car gensyms) (car inits)
 143                   (fold-opt names (cdr gensyms) (cdr inits) seed)))))
 144        (define (fold-rest rest gensyms inits seed)
 145          (match rest
 146            (#f (fold-kw kw gensyms inits seed))
 147            (name (proc name (car gensyms) #f
 148                        (fold-kw kw (cdr gensyms) inits seed)))))
 149        (define (fold-kw kw gensyms inits seed)
 150          (match kw
 151            (()
 152             (unless (null? gensyms)
 153               (error "too many gensyms"))
 154             (unless (null? inits)
 155               (error "too many inits"))
 156             seed)
 157            (((key name var) . kw)
 158             ;; Could be that var is not a gensym any more.
 159             (when (symbol? var)
 160               (unless (eq? var (car gensyms))
 161                 (error "unexpected keyword arg order")))
 162             (proc name (car gensyms) (car inits)
 163                   (fold-kw kw (cdr gensyms) (cdr inits) seed)))))
 164        (fold-req req gensyms seed)))))
 165
 166 (define (unbound? src var kt kf)
 167   (define tc8-iflag 4)
 168   (define unbound-val 9)
 169   (define unbound-bits (logior (ash unbound-val 8) tc8-iflag))
 170   (let-fresh () (unbound)
 171     (build-cps-term
 172       ($letconst (('unbound unbound
 173                             (pointer->scm (make-pointer unbound-bits))))
 174         ($continue kf src
 175           ($branch kt ($primcall 'eq? (var unbound))))))))
 176
 177 (define (init-default-value name sym subst init body)
 178   (match (hashq-ref subst sym)
 179     ((orig-var subst-var box?)
 180      (let ((src (tree-il-src init)))
 181        (define (maybe-box k make-body)
 182          (if box?
 183              (let-fresh (kbox) (phi)
 184                (build-cps-term
 185                  ($letk ((kbox ($kargs (name) (phi)
 186                                  ($continue k src ($primcall 'box (phi))))))
 187                    ,(make-body kbox))))
 188              (make-body k)))
 189        (let-fresh (knext kbound kunbound kreceive krest) (val rest)
 190          (build-cps-term
 191            ($letk ((knext ($kargs (name) (subst-var) ,body)))
 192              ,(maybe-box
 193                knext
 194                (lambda (k)
 195                  (build-cps-term
 196                    ($letk ((kbound ($kargs () () ($continue k src
 197                                                    ($values (orig-var)))))
 198                            (krest ($kargs (name 'rest) (val rest)
 199                                     ($continue k src ($values (val)))))
 200                            (kreceive ($kreceive (list name) 'rest krest))
 201                            (kunbound ($kargs () ()
 202                                        ,(convert init kreceive subst))))
 203                      ,(unbound? src orig-var kunbound kbound))))))))))))
 204
 205 ;; exp k-name alist -> term
 206 (define (convert exp k subst)
 207   ;; exp (v-name -> term) -> term
 208   (define (convert-arg exp k)
 209     (match exp
 210       (($ <lexical-ref> src name sym)
 211        (match (hashq-ref subst sym)
 212          ((orig-var box #t)
 213           (let-fresh (kunboxed) (unboxed)
 214             (build-cps-term
 215               ($letk ((kunboxed ($kargs ('unboxed) (unboxed) ,(k unboxed))))
 216                 ($continue kunboxed src ($primcall 'box-ref (box)))))))
 217          ((orig-var subst-var #f) (k subst-var))
 218          (var (k var))))
 219       (else
 220        (let-fresh (kreceive karg) (arg rest)
 221          (build-cps-term
 222            ($letk ((karg ($kargs ('arg 'rest) (arg rest) ,(k arg)))
 223                    (kreceive ($kreceive '(arg) 'rest karg)))
 224              ,(convert exp kreceive subst)))))))
 225   ;; (exp ...) ((v-name ...) -> term) -> term
 226   (define (convert-args exps k)
 227     (match exps
 228       (() (k '()))
 229       ((exp . exps)
 230        (convert-arg exp
 231          (lambda (name)
 232            (convert-args exps
 233              (lambda (names)
 234                (k (cons name names)))))))))
 235   (define (box-bound-var name sym body)
 236     (match (hashq-ref subst sym)
 237       ((orig-var subst-var #t)
 238        (let-fresh (k) ()
 239          (build-cps-term
 240            ($letk ((k ($kargs (name) (subst-var) ,body)))
 241              ($continue k #f ($primcall 'box (orig-var)))))))
 242       (else body)))
 243   (define (bound-var sym)
 244     (match (hashq-ref subst sym)
 245       ((var . _) var)
 246       ((? exact-integer? var) var)))
 247
 248   (match exp
 249     (($ <lexical-ref> src name sym)
 250      (rewrite-cps-term (hashq-ref subst sym)
 251        ((orig-var box #t) ($continue k src ($primcall 'box-ref (box))))
 252        ((orig-var subst-var #f) ($continue k src ($values (subst-var))))
 253        (var ($continue k src ($values (var))))))
 254
 255     (($ <void> src)
 256      (build-cps-term ($continue k src ($const *unspecified*))))
 257
 258     (($ <const> src exp)
 259      (build-cps-term ($continue k src ($const exp))))
 260
 261     (($ <primitive-ref> src name)
 262      (build-cps-term ($continue k src ($prim name))))
 263
 264     (($ <lambda> fun-src meta body)
 265      (let ()
 266        (define (convert-clauses body ktail)
 267          (match body
 268            (#f #f)
 269            (($ <lambda-case> src req opt rest kw inits gensyms body alternate)
 270             (let* ((arity (make-$arity req (or opt '()) rest
 271                                        (map (match-lambda
 272                                              ((kw name sym)
 273                                               (list kw name (bound-var sym))))
 274                                             (if kw (cdr kw) '()))
 275                                        (and kw (car kw))))
 276                    (names (fold-formals (lambda (name sym init names)
 277                                           (cons name names))
 278                                         '()
 279                                         arity gensyms inits)))
 280               (let ((bound-vars (map bound-var gensyms)))
 281                 (let-fresh (kclause kargs) ()
 282                   (build-cps-cont
 283                     (kclause
 284                      ($kclause ,arity
 285                        (kargs
 286                         ($kargs names bound-vars
 287                           ,(fold-formals
 288                             (lambda (name sym init body)
 289                               (if init
 290                                   (init-default-value name sym subst init body)
 291                                   (box-bound-var name sym body)))
 292                             (convert body ktail subst)
 293                             arity gensyms inits)))
 294                        ,(convert-clauses alternate ktail))))))))))
 295        (if (current-topbox-scope)
 296            (let-fresh (kfun ktail) (self)
 297              (build-cps-term
 298                ($continue k fun-src
 299                  ($fun '()
 300                    (kfun ($kfun fun-src meta self (ktail ($ktail))
 301                              ,(convert-clauses body ktail)))))))
 302            (let ((scope-id (fresh-scope-id)))
 303              (let-fresh (kscope) ()
 304                (build-cps-term
 305                  ($letk ((kscope
 306                           ($kargs () ()
 307                             ,(parameterize ((current-topbox-scope scope-id))
 308                                (convert exp k subst)))))
 309                    ,(capture-toplevel-scope fun-src scope-id kscope))))))))
 310
 311     (($ <module-ref> src mod name public?)
 312      (module-box
 313       src mod name public? #t
 314       (lambda (box)
 315         (build-cps-term ($continue k src ($primcall 'box-ref (box)))))))
 316
 317     (($ <module-set> src mod name public? exp)
 318      (convert-arg exp
 319        (lambda (val)
 320          (module-box
 321           src mod name public? #f
 322           (lambda (box)
 323             (build-cps-term
 324               ($continue k src ($primcall 'box-set! (box val)))))))))
 325
 326     (($ <toplevel-ref> src name)
 327      (toplevel-box
 328       src name #t
 329       (lambda (box)
 330         (build-cps-term ($continue k src ($primcall 'box-ref (box)))))))
 331
 332     (($ <toplevel-set> src name exp)
 333      (convert-arg exp
 334        (lambda (val)
 335          (toplevel-box
 336           src name #f
 337           (lambda (box)
 338             (build-cps-term
 339               ($continue k src ($primcall 'box-set! (box val)))))))))
 340
 341     (($ <toplevel-define> src name exp)
 342      (convert-arg exp
 343        (lambda (val)
 344          (let-fresh (kname) (name-sym)
 345            (build-cps-term
 346              ($letconst (('name name-sym name))
 347                ($continue k src ($primcall 'define! (name-sym val)))))))))
 348
 349     (($ <call> src proc args)
 350      (convert-args (cons proc args)
 351        (match-lambda
 352         ((proc . args)
 353          (build-cps-term ($continue k src ($call proc args)))))))
 354
 355     (($ <primcall> src name args)
 356      (cond
 357       ((branching-primitive? name)
 358        (convert-args args
 359          (lambda (args)
 360            (let-fresh (kt kf) ()
 361              (build-cps-term
 362                ($letk ((kt ($kargs () () ($continue k src ($const #t))))
 363                        (kf ($kargs () () ($continue k src ($const #f)))))
 364                  ($continue kf src
 365                    ($branch kt ($primcall name args)))))))))
 366       ((and (eq? name 'not) (match args ((_) #t) (_ #f)))
 367        (convert-args args
 368          (lambda (args)
 369            (let-fresh (kt kf) ()
 370              (build-cps-term
 371                ($letk ((kt ($kargs () () ($continue k src ($const #f))))
 372                        (kf ($kargs () () ($continue k src ($const #t)))))
 373                  ($continue kf src
 374                    ($branch kt ($values args)))))))))
 375       ((and (eq? name 'list)
 376             (and-map (match-lambda
 377                       ((or ($ <const>)
 378                            ($ <void>)
 379                            ($ <lambda>)
 380                            ($ <lexical-ref>)) #t)
 381                       (_ #f))
 382                      args))
 383        ;; See note below in `canonicalize' about `vector'.  The same
 384        ;; thing applies to `list'.
 385        (let lp ((args args) (k k))
 386          (match args
 387            (()
 388             (build-cps-term
 389               ($continue k src ($const '()))))
 390            ((arg . args)
 391             (let-fresh (ktail) (tail)
 392               (build-cps-term
 393                 ($letk ((ktail ($kargs ('tail) (tail)
 394                                  ,(convert-arg arg
 395                                     (lambda (head)
 396                                       (build-cps-term
 397                                         ($continue k src
 398                                           ($primcall 'cons (head tail)))))))))
 399                   ,(lp args ktail))))))))
 400       (else
 401        (convert-args args
 402          (lambda (args)
 403            (build-cps-term ($continue k src ($primcall name args))))))))
 404
 405     ;; Prompts with inline handlers.
 406     (($ <prompt> src escape-only? tag body
 407         ($ <lambda> hsrc hmeta
 408            ($ <lambda-case> _ hreq #f hrest #f () hsyms hbody #f)))
 409      ;; Handler:
 410      ;;   khargs: check args returned to handler, -> khbody
 411      ;;   khbody: the handler, -> k
 412      ;;
 413      ;; Post-body:
 414      ;;   krest: collect return vals from body to list, -> kpop
 415      ;;   kpop: pop the prompt, -> kprim
 416      ;;   kprim: load the values primitive, -> kret
 417      ;;   kret: (apply values rvals), -> k
 418      ;;
 419      ;; Escape prompts evaluate the body with the continuation of krest.
 420      ;; Otherwise we do a no-inline call to body, continuing to krest.
 421      (convert-arg tag
 422        (lambda (tag)
 423          (let ((hnames (append hreq (if hrest (list hrest) '())))
 424                (bound-vars (map bound-var hsyms)))
 425            (let-fresh (khargs khbody kret kprim kpop krest kbody) (prim vals)
 426              (build-cps-term
 427                ;; FIXME: Attach hsrc to $kreceive.
 428                ($letk* ((khbody ($kargs hnames bound-vars
 429                                   ,(fold box-bound-var
 430                                          (convert hbody k subst)
 431                                          hnames hsyms)))
 432                         (khargs ($kreceive hreq hrest khbody))
 433                         (kpop ($kargs ('rest) (vals)
 434                                 ($letk ((kret
 435                                          ($kargs () ()
 436                                            ($letk ((kprim
 437                                                     ($kargs ('prim) (prim)
 438                                                       ($continue k src
 439                                                         ($primcall 'apply
 440                                                                    (prim vals))))))
 441                                              ($continue kprim src
 442                                                ($prim 'values))))))
 443                                   ($continue kret src
 444                                     ($primcall 'unwind ())))))
 445                         (krest ($kreceive '() 'rest kpop)))
 446                  ,(if escape-only?
 447                       (build-cps-term
 448                         ($letk ((kbody ($kargs () ()
 449                                          ,(convert body krest subst))))
 450                           ($continue kbody src ($prompt #t tag khargs))))
 451                       (convert-arg body
 452                         (lambda (thunk)
 453                           (build-cps-term
 454                             ($letk ((kbody ($kargs () ()
 455                                              ($continue krest (tree-il-src body)
 456                                                ($primcall 'call-thunk/no-inline
 457                                                           (thunk))))))
 458                               ($continue kbody (tree-il-src body)
 459                                 ($prompt #f tag khargs))))))))))))))
 460
 461     (($ <abort> src tag args ($ <const> _ ()))
 462      (convert-args (cons tag args)
 463        (lambda (args*)
 464          (build-cps-term
 465            ($continue k src
 466              ($primcall 'abort-to-prompt args*))))))
 467
 468     (($ <abort> src tag args tail)
 469      (convert-args (append (list (make-primitive-ref #f 'abort-to-prompt)
 470                                  tag)
 471                            args
 472                            (list tail))
 473        (lambda (args*)
 474          (build-cps-term
 475            ($continue k src ($primcall 'apply args*))))))
 476
 477     (($ <conditional> src test consequent alternate)
 478      (let-fresh (kt kf) ()
 479        (build-cps-term
 480          ($letk* ((kt ($kargs () () ,(convert consequent k subst)))
 481                   (kf ($kargs () () ,(convert alternate k subst))))
 482            ,(match test
 483               (($ <primcall> src (? branching-primitive? name) args)
 484                (convert-args args
 485                  (lambda (args)
 486                    (build-cps-term
 487                      ($continue kf src
 488                        ($branch kt ($primcall name args)))))))
 489               (_ (convert-arg test
 490                    (lambda (test)
 491                      (build-cps-term
 492                        ($continue kf src
 493                          ($branch kt ($values (test)))))))))))))
 494
 495     (($ <lexical-set> src name gensym exp)
 496      (convert-arg exp
 497        (lambda (exp)
 498          (match (hashq-ref subst gensym)
 499            ((orig-var box #t)
 500             (build-cps-term
 501               ($continue k src ($primcall 'box-set! (box exp)))))))))
 502
 503     (($ <seq> src head tail)
 504      (let-fresh (kreceive kseq) (vals)
 505        (build-cps-term
 506          ($letk* ((kseq ($kargs ('vals) (vals)
 507                           ,(convert tail k subst)))
 508                   (kreceive ($kreceive '() 'vals kseq)))
 509            ,(convert head kreceive subst)))))
 510
 511     (($ <let> src names syms vals body)
 512      (let lp ((names names) (syms syms) (vals vals))
 513        (match (list names syms vals)
 514          ((() () ()) (convert body k subst))
 515          (((name . names) (sym . syms) (val . vals))
 516           (let-fresh (kreceive klet) (rest)
 517             (build-cps-term
 518               ($letk* ((klet ($kargs (name 'rest) ((bound-var sym) rest)
 519                                ,(box-bound-var name sym
 520                                                (lp names syms vals))))
 521                        (kreceive ($kreceive (list name) 'rest klet)))
 522                 ,(convert val kreceive subst))))))))
 523
 524     (($ <fix> src names gensyms funs body)
 525      ;; Some letrecs can be contified; that happens later.
 526      (if (current-topbox-scope)
 527          (let-fresh () (self)
 528            (build-cps-term
 529              ($letrec names
 530                       (map bound-var gensyms)
 531                       (map (lambda (fun)
 532                              (match (convert fun k subst)
 533                                (($ $continue _ _ (and fun ($ $fun)))
 534                                 fun)))
 535                            funs)
 536                       ,(convert body k subst))))
 537          (let ((scope-id (fresh-scope-id)))
 538            (let-fresh (kscope) ()
 539              (build-cps-term
 540                ($letk ((kscope
 541                         ($kargs () ()
 542                           ,(parameterize ((current-topbox-scope scope-id))
 543                              (convert exp k subst)))))
 544                  ,(capture-toplevel-scope src scope-id kscope)))))))
 545
 546     (($ <let-values> src exp
 547         ($ <lambda-case> lsrc req #f rest #f () syms body #f))
 548      (let ((names (append req (if rest (list rest) '())))
 549            (bound-vars (map bound-var syms)))
 550        (let-fresh (kreceive kargs) ()
 551          (build-cps-term
 552            ($letk* ((kargs ($kargs names bound-vars
 553                              ,(fold box-bound-var
 554                                     (convert body k subst)
 555                                     names syms)))
 556                     (kreceive ($kreceive req rest kargs)))
 557              ,(convert exp kreceive subst))))))))
 558
 559 (define (build-subst exp)
 560   "Compute a mapping from lexical gensyms to CPS variable indexes.  CPS
 561 uses small integers to identify variables, instead of gensyms.
 562
 563 This subst table serves an additional purpose of mapping variables to
 564 replacements.  The usual reason to replace one variable by another is
 565 assignment conversion.  Default argument values is the other reason.
 566
 567 The result is a hash table mapping symbols to substitutions (in the case
 568 that a variable is substituted) or to indexes.  A substitution is a list
 569 of the form:
 570
 571   (ORIG-INDEX SUBST-INDEX BOXED?)
 572
 573 A true value for BOXED?  indicates that the replacement variable is in a
 574 box.  If a variable is not substituted, the mapped value is a small
 575 integer."
 576   (let ((table (make-hash-table)))
 577     (define (down exp)
 578       (match exp
 579         (($ <lexical-set> src name sym exp)
 580          (match (hashq-ref table sym)
 581            ((orig subst #t) #t)
 582            ((orig subst #f) (hashq-set! table sym (list orig subst #t)))
 583            ((? number? idx) (hashq-set! table sym (list idx (fresh-var) #t)))))
 584         (($ <lambda-case> src req opt rest kw inits gensyms body alternate)
 585          (fold-formals (lambda (name sym init seed)
 586                          (hashq-set! table sym
 587                                      (if init
 588                                          (list (fresh-var) (fresh-var) #f)
 589                                          (fresh-var))))
 590                        #f
 591                        (make-$arity req (or opt '()) rest
 592                                     (if kw (cdr kw) '()) (and kw (car kw)))
 593                        gensyms
 594                        inits))
 595         (($ <let> src names gensyms vals body)
 596          (for-each (lambda (sym)
 597                      (hashq-set! table sym (fresh-var)))
 598                    gensyms))
 599         (($ <fix> src names gensyms vals body)
 600          (for-each (lambda (sym)
 601                      (hashq-set! table sym (fresh-var)))
 602                    gensyms))
 603         (_ #t))
 604       (values))
 605     (define (up exp) (values))
 606     ((make-tree-il-folder) exp down up)
 607     table))
 608
 609 (define (cps-convert/thunk exp)
 610   (parameterize ((label-counter 0)
 611                  (var-counter 0)
 612                  (scope-counter 0))
 613     (let ((src (tree-il-src exp)))
 614       (let-fresh (kinit ktail kclause kbody) (init)
 615         (build-cps-cont
 616           (kinit ($kfun src '() init (ktail ($ktail))
 617                    (kclause
 618                     ($kclause ('() '() #f '() #f)
 619                       (kbody ($kargs () ()
 620                                ,(convert exp ktail
 621                                          (build-subst exp))))
 622                       ,#f)))))))))
 623
 624 (define *comp-module* (make-fluid))
 625
 626 (define %warning-passes
 627   `((unused-variable     . ,unused-variable-analysis)
 628     (unused-toplevel     . ,unused-toplevel-analysis)
 629     (unbound-variable    . ,unbound-variable-analysis)
 630     (arity-mismatch      . ,arity-analysis)
 631     (format              . ,format-analysis)))
 632
 633 (define (optimize-tree-il x e opts)
 634   (define warnings
 635     (or (and=> (memq #:warnings opts) cadr)
 636         '()))
 637
 638   ;; Go through the warning passes.
 639   (let ((analyses (filter-map (lambda (kind)
 640                                 (assoc-ref %warning-passes kind))
 641                               warnings)))
 642     (analyze-tree analyses x e))
 643
 644   (optimize x e opts))
 645
 646 (define (canonicalize exp)
 647   (post-order
 648    (lambda (exp)
 649      (match exp
 650        (($ <primcall> src 'vector
 651            (and args
 652                 ((or ($ <const>) ($ <void>) ($ <lambda>) ($ <lexical-ref>))
 653                  ...)))
 654         ;; Some macros generate calls to "vector" with like 300
 655         ;; arguments.  Since we eventually compile to make-vector and
 656         ;; vector-set!, it reduces live variable pressure to allocate the
 657         ;; vector first, then set values as they are produced, if we can
 658         ;; prove that no value can capture the continuation.  (More on
 659         ;; that caveat here:
 660         ;; http://wingolog.org/archives/2013/11/02/scheme-quiz-time).
 661         ;;
 662         ;; Normally we would do this transformation in the compiler, but
 663         ;; it's quite tricky there and quite easy here, so hold your nose
 664         ;; while we drop some smelly code.
 665         (let ((len (length args))
 666               (v (gensym "v ")))
 667           (make-let src
 668                     (list 'v)
 669                     (list v)
 670                     (list (make-primcall src 'make-vector
 671                                          (list (make-const #f len)
 672                                                (make-const #f #f))))
 673                     (fold (lambda (arg n tail)
 674                             (make-seq
 675                              src
 676                              (make-primcall
 677                               src 'vector-set!
 678                               (list (make-lexical-ref src 'v v)
 679                                     (make-const #f n)
 680                                     arg))
 681                              tail))
 682                           (make-lexical-ref src 'v v)
 683                           (reverse args) (reverse (iota len))))))
 684
 685        (($ <primcall> src 'struct-set! (struct index value))
 686         ;; Unhappily, and undocumentedly, struct-set! returns the value
 687         ;; that was set.  There is code that relies on this.  Hackety
 688         ;; hack...
 689         (let ((v (gensym "v ")))
 690           (make-let src
 691                     (list 'v)
 692                     (list v)
 693                     (list value)
 694                     (make-seq src
 695                               (make-primcall src 'struct-set!
 696                                              (list struct
 697                                                    index
 698                                                    (make-lexical-ref src 'v v)))
 699                               (make-lexical-ref src 'v v)))))
 700
 701        (($ <prompt> src escape-only? tag body
 702            ($ <lambda> hsrc hmeta
 703               ($ <lambda-case> _ hreq #f hrest #f () hsyms hbody #f)))
 704         exp)
 705
 706        ;; Eta-convert prompts without inline handlers.
 707        (($ <prompt> src escape-only? tag body handler)
 708         (let ((h (gensym "h "))
 709               (args (gensym "args ")))
 710           (make-let
 711            src (list 'h) (list h) (list handler)
 712            (make-seq
 713             src
 714             (make-conditional
 715              src
 716              (make-primcall src 'procedure? (list (make-lexical-ref #f 'h h)))
 717              (make-void src)
 718              (make-primcall
 719               src 'scm-error
 720               (list
 721                (make-const #f 'wrong-type-arg)
 722                (make-const #f "call-with-prompt")
 723                (make-const #f "Wrong type (expecting procedure): ~S")
 724                (make-primcall #f 'list (list (make-lexical-ref #f 'h h)))
 725                (make-primcall #f 'list (list (make-lexical-ref #f 'h h))))))
 726             (make-prompt
 727              src escape-only? tag body
 728              (make-lambda
 729               src '()
 730               (make-lambda-case
 731                src '() #f 'args #f '() (list args)
 732                (make-primcall
 733                 src 'apply
 734                 (list (make-lexical-ref #f 'h h)
 735                       (make-lexical-ref #f 'args args)))
 736                #f)))))))
 737        (_ exp)))
 738    exp))
 739
 740 (define (compile-cps exp env opts)
 741   (values (cps-convert/thunk
 742            (canonicalize (optimize-tree-il exp env opts)))
 743           env
 744           env))
 745
 746 ;;; Local Variables:
 747 ;;; eval: (put 'convert-arg 'scheme-indent-function 1)
 748 ;;; eval: (put 'convert-args 'scheme-indent-function 1)
 749 ;;; End: