module/language/tree-il/optimize.scm

   1 ;;; Tree-il optimizer
   2
   3 ;; Copyright (C) 2009 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
  22 (define-module (language tree-il optimize)
  23   #:use-module (system base syntax)
  24   #:use-module (language tree-il)
  25   #:export (resolve-primitives!))
  26
  27 ;; Possible optimizations:
  28 ;; * constant folding, propagation
  29 ;; * procedure inlining
  30 ;;   * always when single call site
  31 ;;   * always for "trivial" procs
  32 ;;   * otherwise who knows
  33 ;; * dead code elimination
  34 ;; * degenerate case optimizations
  35 ;; * "fixing letrec"
  36
  37 (define (post-order! f x)
  38   (let lp ((x x))
  39     (record-case x
  40       ((<application> proc args)
  41        (set! (application-proc x) (lp proc))
  42        (set! (application-args x) (map lp args))
  43        (or (f x) x))
  44
  45       ((<conditional> test then else)
  46        (set! (conditional-test x) (lp test))
  47        (set! (conditional-then x) (lp then))
  48        (set! (conditional-else x) (lp else))
  49        (or (f x) x))
  50
  51       ((<primitive-ref> name)
  52        (or (f x) x))
  53
  54       ((<lexical-ref> name gensym)
  55        (or (f x) x))
  56
  57       ((<lexical-set> name gensym exp)
  58        (set! (lexical-set-exp x) (lp exp))
  59        (or (f x) x))
  60
  61       ((<module-ref> mod name public?)
  62        (or (f x) x))
  63
  64       ((<module-set> mod name public? exp)
  65        (set! (module-set-exp x) (lp exp))
  66        (or (f x) x))
  67
  68       ((<toplevel-ref> name)
  69        (or (f x) x))
  70
  71       ((<toplevel-set> name exp)
  72        (set! (toplevel-set-exp x) (lp exp))
  73        (or (f x) x))
  74
  75       ((<toplevel-define> name exp)
  76        (set! (toplevel-define-exp x) (lp exp))
  77        (or (f x) x))
  78
  79       ((<lambda> vars meta body)
  80        (set! (lambda-body x) (lp body))
  81        (or (f x) x))
  82
  83       ((<const> exp)
  84        (or (f x) x))
  85
  86       ((<sequence> exps)
  87        (set! (sequence-exps x) (map lp exps))
  88        (or (f x) x))
  89
  90       ((<let> vars vals exp)
  91        (set! (let-vals x) (map lp vals))
  92        (set! (let-exp x) (lp exp))
  93        (or (f x) x))
  94
  95       ((<letrec> vars vals exp)
  96        (set! (letrec-vals x) (map lp vals))
  97        (set! (letrec-exp x) (lp exp))
  98        (or (f x) x)))))
  99
 100 (define *interesting-primitive-names*
 101   '(apply @apply
 102     call-with-values @call-with-values
 103     call-with-current-continuation @call-with-current-continuation
 104     values
 105     ;; compile-time-environment
 106     eq? eqv? equal?
 107     = < > <= >= zero?
 108     + * - / 1- 1+ quotient remainder modulo
 109     not
 110     pair? null? list? acons cons cons*
 111
 112     car cdr
 113     set-car! set-cdr!
 114
 115     caar cadr cdar cddr
 116
 117     caaar caadr cadar caddr cdaar cdadr cddar cdddr
 118
 119     caaaar caaadr caadar caaddr cadaar cadadr caddar cadddr
 120     cdaaar cdaadr cdadar cdaddr cddaar cddadr cdddar cddddr))
 121
 122 (define *interesting-primitive-vars*
 123   (let ((h (make-hash-table)))
 124     (for-each (lambda (x)
 125                 (hashq-set! h (module-variable the-root-module x) x))
 126               *interesting-primitive-names*)
 127     h))
 128
 129 (define (resolve-primitives! x mod)
 130   (post-order!
 131    (lambda (x)
 132      (record-case x
 133        ((<toplevel-ref> src name)
 134         (and (hashq-ref *interesting-primitive-vars*
 135                         (module-variable mod name))
 136              (make-primitive-ref src name)))
 137        ((<module-ref> mod name public?)
 138         (let ((m (if public? (resolve-interface mod) (resolve-module mod))))
 139           (and m (hashq-ref *interesting-primitive-vars*
 140                             (module-variable m name))
 141                (make-primitive-ref src name))))
 142        (else #f)))
 143    x))