#:export (peval))
;;;
-;;; Partial evaluation.
+;;; Partial evaluation is Guile's most important source-to-source
+;;; optimization pass. It performs copy propagation, dead code
+;;; elimination, inlining, and constant folding, all while preserving
+;;; the order of effects in the residual program.
+;;;
+;;; For more on partial evaluation, see William Cook’s excellent
+;;; tutorial on partial evaluation at DSL 2011, called “Build your own
+;;; partial evaluator in 90 minutes”[0].
+;;;
+;;; Our implementation of this algorithm was heavily influenced by
+;;; Waddell and Dybvig's paper, "Fast and Effective Procedure Inlining",
+;;; IU CS Dept. TR 484.
+;;;
+;;; [0] http://www.cs.utexas.edu/~wcook/tutorial/.
;;;
-(define (fresh-gensyms syms)
- (map (lambda (x) (gensym (string-append (symbol->string x) " ")))
- syms))
-
-(define (alpha-rename exp)
- "Alpha-rename EXP. For any lambda in EXP, generate new symbols and
-replace all lexical references to the former symbols with lexical
-references to the new symbols."
- ;; XXX: This should be factorized somehow.
- (let loop ((exp exp)
- (mapping vlist-null)) ; maps old to new gensyms
- (match exp
- (($ <lambda-case> src req opt rest kw inits gensyms body alt)
- ;; Create new symbols to replace GENSYMS and propagate them down
- ;; in BODY and ALT.
- (let* ((new (fresh-gensyms
- (append req
- (or opt '())
- (if rest (list rest) '())
- (match kw
- ((aok? (_ name _) ...) name)
- (_ '())))))
- (mapping (fold vhash-consq mapping gensyms new)))
- (make-lambda-case src req opt rest
- (match kw
- ((aok? (kw name old) ...)
- (cons aok? (map list
- kw
- name
- (take-right new (length old)))))
- (_ #f))
- (map (cut loop <> mapping) inits)
- new
- (loop body mapping)
- (and alt (loop alt mapping)))))
- (($ <lexical-ref> src name gensym)
- ;; Possibly replace GENSYM by the new gensym defined in MAPPING.
- (let ((val (vhash-assq gensym mapping)))
- (if val
- (make-lexical-ref src name (cdr val))
- exp)))
- (($ <lexical-set> src name gensym exp)
- (let ((val (vhash-assq gensym mapping)))
- (make-lexical-set src name (if val (cdr val) gensym)
- (loop exp mapping))))
- (($ <lambda> src meta body)
- (make-lambda src meta (loop body mapping)))
- (($ <let> src names gensyms vals body)
- ;; As for `lambda-case' rename GENSYMS to avoid any collision.
- (let* ((new (fresh-gensyms names))
- (mapping (fold vhash-consq mapping gensyms new))
- (vals (map (cut loop <> mapping) vals))
- (body (loop body mapping)))
- (make-let src names new vals body)))
- (($ <letrec> src in-order? names gensyms vals body)
- ;; Likewise.
- (let* ((new (fresh-gensyms names))
- (mapping (fold vhash-consq mapping gensyms new))
- (vals (map (cut loop <> mapping) vals))
- (body (loop body mapping)))
- (make-letrec src in-order? names new vals body)))
- (($ <fix> src names gensyms vals body)
- ;; Likewise.
- (let* ((new (fresh-gensyms names))
- (mapping (fold vhash-consq mapping gensyms new))
- (vals (map (cut loop <> mapping) vals))
- (body (loop body mapping)))
- (make-fix src names new vals body)))
- (($ <let-values> src exp body)
- (make-let-values src (loop exp mapping) (loop body mapping)))
- (($ <const>)
- exp)
- (($ <void>)
- exp)
- (($ <toplevel-ref>)
- exp)
- (($ <module-ref>)
- exp)
- (($ <primitive-ref>)
- exp)
- (($ <toplevel-set> src name exp)
- (make-toplevel-set src name (loop exp mapping)))
- (($ <toplevel-define> src name exp)
- (make-toplevel-define src name (loop exp mapping)))
- (($ <module-set> src mod name public? exp)
- (make-module-set src mod name public? (loop exp mapping)))
- (($ <dynlet> src fluids vals body)
- (make-dynlet src
- (map (cut loop <> mapping) fluids)
- (map (cut loop <> mapping) vals)
- (loop body mapping)))
- (($ <dynwind> src winder body unwinder)
- (make-dynwind src
- (loop winder mapping)
- (loop body mapping)
- (loop unwinder mapping)))
- (($ <dynref> src fluid)
- (make-dynref src (loop fluid mapping)))
- (($ <dynset> src fluid exp)
- (make-dynset src (loop fluid mapping) (loop exp mapping)))
- (($ <conditional> src condition subsequent alternate)
- (make-conditional src
- (loop condition mapping)
- (loop subsequent mapping)
- (loop alternate mapping)))
- (($ <application> src proc args)
- (make-application src (loop proc mapping)
- (map (cut loop <> mapping) args)))
- (($ <sequence> src exps)
- (make-sequence src (map (cut loop <> mapping) exps)))
- (($ <prompt> src tag body handler)
- (make-prompt src (loop tag mapping) (loop body mapping)
- (loop handler mapping)))
- (($ <abort> src tag args tail)
- (make-abort src (loop tag mapping) (map (cut loop <> mapping) args)
- (loop tail mapping))))))
-
+;; First, some helpers.
+;;
(define-syntax-rule (let/ec k e e* ...)
(let ((tag (make-prompt-tag)))
(call-with-prompt
(or (proc (vlist-ref vlist i))
(lp (1+ i)))))))
+;; Peval will do a one-pass analysis on the source program to determine
+;; the set of assigned lexicals, and to identify unreferenced and
+;; singly-referenced lexicals.
+;;
+;; If peval introduces more code, via copy-propagation, it will need to
+;; run `build-var-table' on the new code to add to make sure it can find
+;; a <var> for each gensym bound in the program.
+;;
(define-record-type <var>
(make-var name gensym refcount set?)
var?
(lambda (exp res) res)
table exp))
+;; Counters are data structures used to limit the effort that peval
+;; spends on particular inlining attempts. Each call site in the source
+;; program is allocated some amount of effort. If peval exceeds the
+;; effort counter while attempting to inline a call site, it aborts the
+;; inlining attempt and residualizes a call instead.
+;;
+;; As there is a fixed number of call sites, that makes `peval' O(N) in
+;; the number of call sites in the source program.
+;;
+;; Counters should limit the size of the residual program as well, but
+;; currently this is not implemented.
+;;
+;; At the top level, before seeing any peval call, there is no counter,
+;; because inlining will terminate as there is no recursion. When peval
+;; sees a call at the top level, it will make a new counter, allocating
+;; it some amount of effort and size.
+;;
+;; This top-level effort counter effectively "prints money". Within a
+;; toplevel counter, no more effort is printed ex nihilo; for a nested
+;; inlining attempt to proceed, effort must be transferred from the
+;; toplevel counter to the nested counter.
+;;
+;; Via `data' and `prev', counters form a linked list, terminating in a
+;; toplevel counter. In practice `data' will be the a pointer to the
+;; source expression of the procedure being inlined.
+;;
+;; In this way peval can detect a recursive inlining attempt, by walking
+;; back on the `prev' links looking for matching `data'. Recursive
+;; counters receive a more limited effort allocation, as we don't want
+;; to spend all of the effort for a toplevel inlining site on loops.
+;; Also, recursive counters don't need a prompt at each inlining site:
+;; either the call chain folds entirely, or it will be residualized at
+;; its original call.
+;;
(define-record-type <counter>
(%make-counter effort size continuation recursive? data prev)
counter?
;; FIXME: add more cases?
(else #f)))
+(define (fresh-gensyms syms)
+ (map (lambda (x) (gensym (string-append (symbol->string x) " ")))
+ syms))
+
+;; Copy propagation of terms that bind variables, like `lambda' terms,
+;; will need to bind fresh variables. This procedure renames all the
+;; lexicals in a term.
+;;
+(define (alpha-rename exp)
+ "Alpha-rename EXP. For any lambda in EXP, generate new symbols and
+replace all lexical references to the former symbols with lexical
+references to the new symbols."
+ ;; XXX: This should be factorized somehow.
+ (let loop ((exp exp)
+ (mapping vlist-null)) ; maps old to new gensyms
+ (match exp
+ (($ <lambda-case> src req opt rest kw inits gensyms body alt)
+ ;; Create new symbols to replace GENSYMS and propagate them down
+ ;; in BODY and ALT.
+ (let* ((new (fresh-gensyms
+ (append req
+ (or opt '())
+ (if rest (list rest) '())
+ (match kw
+ ((aok? (_ name _) ...) name)
+ (_ '())))))
+ (mapping (fold vhash-consq mapping gensyms new)))
+ (make-lambda-case src req opt rest
+ (match kw
+ ((aok? (kw name old) ...)
+ (cons aok? (map list
+ kw
+ name
+ (take-right new (length old)))))
+ (_ #f))
+ (map (cut loop <> mapping) inits)
+ new
+ (loop body mapping)
+ (and alt (loop alt mapping)))))
+ (($ <lexical-ref> src name gensym)
+ ;; Possibly replace GENSYM by the new gensym defined in MAPPING.
+ (let ((val (vhash-assq gensym mapping)))
+ (if val
+ (make-lexical-ref src name (cdr val))
+ exp)))
+ (($ <lexical-set> src name gensym exp)
+ (let ((val (vhash-assq gensym mapping)))
+ (make-lexical-set src name (if val (cdr val) gensym)
+ (loop exp mapping))))
+ (($ <lambda> src meta body)
+ (make-lambda src meta (loop body mapping)))
+ (($ <let> src names gensyms vals body)
+ ;; As for `lambda-case' rename GENSYMS to avoid any collision.
+ (let* ((new (fresh-gensyms names))
+ (mapping (fold vhash-consq mapping gensyms new))
+ (vals (map (cut loop <> mapping) vals))
+ (body (loop body mapping)))
+ (make-let src names new vals body)))
+ (($ <letrec> src in-order? names gensyms vals body)
+ ;; Likewise.
+ (let* ((new (fresh-gensyms names))
+ (mapping (fold vhash-consq mapping gensyms new))
+ (vals (map (cut loop <> mapping) vals))
+ (body (loop body mapping)))
+ (make-letrec src in-order? names new vals body)))
+ (($ <fix> src names gensyms vals body)
+ ;; Likewise.
+ (let* ((new (fresh-gensyms names))
+ (mapping (fold vhash-consq mapping gensyms new))
+ (vals (map (cut loop <> mapping) vals))
+ (body (loop body mapping)))
+ (make-fix src names new vals body)))
+ (($ <let-values> src exp body)
+ (make-let-values src (loop exp mapping) (loop body mapping)))
+ (($ <const>)
+ exp)
+ (($ <void>)
+ exp)
+ (($ <toplevel-ref>)
+ exp)
+ (($ <module-ref>)
+ exp)
+ (($ <primitive-ref>)
+ exp)
+ (($ <toplevel-set> src name exp)
+ (make-toplevel-set src name (loop exp mapping)))
+ (($ <toplevel-define> src name exp)
+ (make-toplevel-define src name (loop exp mapping)))
+ (($ <module-set> src mod name public? exp)
+ (make-module-set src mod name public? (loop exp mapping)))
+ (($ <dynlet> src fluids vals body)
+ (make-dynlet src
+ (map (cut loop <> mapping) fluids)
+ (map (cut loop <> mapping) vals)
+ (loop body mapping)))
+ (($ <dynwind> src winder body unwinder)
+ (make-dynwind src
+ (loop winder mapping)
+ (loop body mapping)
+ (loop unwinder mapping)))
+ (($ <dynref> src fluid)
+ (make-dynref src (loop fluid mapping)))
+ (($ <dynset> src fluid exp)
+ (make-dynset src (loop fluid mapping) (loop exp mapping)))
+ (($ <conditional> src condition subsequent alternate)
+ (make-conditional src
+ (loop condition mapping)
+ (loop subsequent mapping)
+ (loop alternate mapping)))
+ (($ <application> src proc args)
+ (make-application src (loop proc mapping)
+ (map (cut loop <> mapping) args)))
+ (($ <sequence> src exps)
+ (make-sequence src (map (cut loop <> mapping) exps)))
+ (($ <prompt> src tag body handler)
+ (make-prompt src (loop tag mapping) (loop body mapping)
+ (loop handler mapping)))
+ (($ <abort> src tag args tail)
+ (make-abort src (loop tag mapping) (map (cut loop <> mapping) args)
+ (loop tail mapping))))))
+
(define* (peval exp #:optional (cenv (current-module)) (env vlist-null)
#:key
(operator-size-limit 40)
(effort-limit 500)
(recursive-effort-limit 100))
"Partially evaluate EXP in compilation environment CENV, with
-top-level bindings from ENV and return the resulting expression. Since
-it does not handle <fix> and <let-values>, it should be called before
-`fix-letrec'."
+top-level bindings from ENV and return the resulting expression."
;; This is a simple partial evaluator. It effectively performs
;; constant folding, copy propagation, dead code elimination, and
- ;; inlining, but not across top-level bindings---there should be a way
- ;; to allow this (TODO).
+ ;; inlining.
+
+ ;; TODO:
+ ;;
+ ;; Propagate copies across toplevel bindings, if we can prove the
+ ;; bindings to be immutable.
;;
- ;; Unlike a full-blown partial evaluator, it does not emit definitions
- ;; of specialized versions of lambdas encountered on its way. Also,
- ;; it's not yet complete: it bails out for `prompt', etc.
+ ;; Specialize lambda expressions with invariant arguments.
(define local-toplevel-env
;; The top-level environment of the module being compiled.
(define (local-toplevel? name)
(vhash-assq name local-toplevel-env))
+ ;; gensym -> <var>
+ ;; renamed-term -> original-term
+ ;;
(define store (build-var-table exp))
(define (assigned-lexical? sym)
(let ((v (vhash-assq sym store)))
(if v (var-refcount (cdr v)) 0)))
+ ;; ORIG has been alpha-renamed to NEW. Analyze NEW and record a link
+ ;; from it to ORIG.
+ ;;
(define (record-source-expression! orig new)
(set! store (vhash-consq new
(source-expression orig)
(build-var-table new store)))
new)
+ ;; Find the source expression corresponding to NEW. Used to detect
+ ;; recursive inlining attempts.
+ ;;
(define (source-expression new)
(let ((x (vhash-assq new store)))
(if x (cdr x) new)))
HCoop / bpt / guile.git / commitdiff