module/language/cps/compile-bytecode.scm

   1 ;;; Continuation-passing style (CPS) intermediate language (IL)
   2
   3 ;; Copyright (C) 2013, 2014 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 ;;; Compiling CPS to bytecode.  The result is in the bytecode language,
  22 ;;; which happens to be an ELF image as a bytecode.
  23 ;;;
  24 ;;; Code:
  25
  26 (define-module (language cps compile-bytecode)
  27   #:use-module (ice-9 match)
  28   #:use-module (srfi srfi-1)
  29   #:use-module (language cps)
  30   #:use-module (language cps arities)
  31   #:use-module (language cps closure-conversion)
  32   #:use-module (language cps contification)
  33   #:use-module (language cps constructors)
  34   #:use-module (language cps dce)
  35   #:use-module (language cps dfg)
  36   #:use-module (language cps elide-values)
  37   #:use-module (language cps primitives)
  38   #:use-module (language cps prune-top-level-scopes)
  39   #:use-module (language cps reify-primitives)
  40   #:use-module (language cps renumber)
  41   #:use-module (language cps simplify)
  42   #:use-module (language cps slot-allocation)
  43   #:use-module (language cps specialize-primcalls)
  44   #:use-module (system vm assembler)
  45   #:export (compile-bytecode))
  46
  47 ;; TODO: Local var names.
  48
  49 (define (kw-arg-ref args kw default)
  50   (match (memq kw args)
  51     ((_ val . _) val)
  52     (_ default)))
  53
  54 (define (optimize exp opts)
  55   (define (run-pass exp pass kw default)
  56     (if (kw-arg-ref opts kw default)
  57         (pass exp)
  58         exp))
  59
  60   ;; The first DCE pass is mainly to eliminate functions that aren't
  61   ;; called.  The last is mainly to eliminate rest parameters that
  62   ;; aren't used, and thus shouldn't be consed.
  63
  64   (let* ((exp (run-pass exp eliminate-dead-code #:eliminate-dead-code? #t))
  65          (exp (run-pass exp prune-top-level-scopes #:prune-top-level-scopes? #t))
  66          (exp (run-pass exp simplify #:simplify? #t))
  67          (exp (run-pass exp contify #:contify? #t))
  68          (exp (run-pass exp inline-constructors #:inline-constructors? #t))
  69          (exp (run-pass exp specialize-primcalls #:specialize-primcalls? #t))
  70          (exp (run-pass exp elide-values #:elide-values? #t))
  71          (exp (run-pass exp eliminate-dead-code #:eliminate-dead-code? #t))
  72          (exp (run-pass exp simplify #:simplify? #t)))
  73     ;; Passes that are needed:
  74     ;;
  75     ;;  * Abort contification: turning abort primcalls into continuation
  76     ;;    calls, and eliding prompts if possible.
  77     ;;
  78     ;;  * Common subexpression elimination.  Desperately needed.
  79     ;;
  80     ;;  * Loop peeling.  Unrolls the first round through a loop if the
  81     ;;    loop has effects that CSE can work on.  Requires effects
  82     ;;    analysis.  When run before CSE, loop peeling is the equivalent
  83     ;;    of loop-invariant code motion (LICM).
  84
  85     exp))
  86
  87 (define (compile-fun f asm)
  88   (let* ((dfg (compute-dfg f #:global? #f))
  89          (allocation (allocate-slots f dfg)))
  90     (define (maybe-slot sym)
  91       (lookup-maybe-slot sym allocation))
  92
  93     (define (slot sym)
  94       (lookup-slot sym allocation))
  95
  96     (define (constant sym)
  97       (lookup-constant-value sym allocation))
  98
  99     (define (maybe-mov dst src)
 100       (unless (= dst src)
 101         (emit-mov asm dst src)))
 102
 103     (define (maybe-load-constant slot src)
 104       (call-with-values (lambda ()
 105                           (lookup-maybe-constant-value src allocation))
 106         (lambda (has-const? val)
 107           (and has-const?
 108                (begin
 109                  (emit-load-constant asm slot val)
 110                  #t)))))
 111
 112     (define (compile-entry meta)
 113       (let ((label (dfg-min-label dfg)))
 114         (match (lookup-cont label dfg)
 115           (($ $kentry self tail clause)
 116            (emit-begin-program asm label meta)
 117            (compile-clause (1+ label))
 118            (emit-end-program asm)))))
 119
 120     (define (compile-clause label)
 121       (match (lookup-cont label dfg)
 122         (($ $kclause ($ $arity req opt rest kw allow-other-keys?)
 123             body alternate)
 124          (let* ((kw-indices (map (match-lambda
 125                                   ((key name sym)
 126                                    (cons key (lookup-slot sym allocation))))
 127                                  kw))
 128                 (nlocals (lookup-nlocals label allocation)))
 129            (emit-label asm label)
 130            (emit-begin-kw-arity asm req opt rest kw-indices allow-other-keys?
 131                                 nlocals
 132                                 (match alternate (#f #f) (($ $cont alt) alt)))
 133            (let ((next (compile-body (1+ label) nlocals)))
 134              (emit-end-arity asm)
 135              (match alternate
 136                (($ $cont alt)
 137                 (unless (eq? next alt)
 138                   (error "unexpected k" alt))
 139                 (compile-clause next))
 140                (#f
 141                 (unless (= next (+ (dfg-min-label dfg) (dfg-label-count dfg)))
 142                   (error "unexpected end of clauses")))))))))
 143
 144     (define (compile-body label nlocals)
 145       (let compile-cont ((label label))
 146         (if (eq? label (+ (dfg-min-label dfg) (dfg-label-count dfg)))
 147             label
 148             (match (lookup-cont label dfg)
 149               (($ $kclause) label)
 150               (($ $kargs _ _ term)
 151                (emit-label asm label)
 152                (let find-exp ((term term))
 153                  (match term
 154                    (($ $letk conts term)
 155                     (find-exp term))
 156                    (($ $continue k src exp)
 157                     (when src
 158                       (emit-source asm src))
 159                     (compile-expression label k exp nlocals)
 160                     (compile-cont (1+ label))))))
 161               (_
 162                (emit-label asm label)
 163                (compile-cont (1+ label)))))))
 164
 165     (define (compile-expression label k exp nlocals)
 166       (let* ((fallthrough? (= k (1+ label))))
 167         (define (maybe-emit-jump)
 168           (unless fallthrough?
 169             (emit-br asm k)))
 170         (match (lookup-cont k dfg)
 171           (($ $ktail)
 172            (compile-tail label exp))
 173           (($ $kargs (name) (sym))
 174            (let ((dst (maybe-slot sym)))
 175              (when dst
 176                (compile-value label exp dst nlocals)))
 177            (maybe-emit-jump))
 178           (($ $kargs () ())
 179            (compile-effect label exp k nlocals)
 180            (maybe-emit-jump))
 181           (($ $kargs names syms)
 182            (compile-values label exp syms)
 183            (maybe-emit-jump))
 184           (($ $kif kt kf)
 185            (compile-test label exp kt kf (and fallthrough? (1+ k))))
 186           (($ $kreceive ($ $arity req () rest () #f) kargs)
 187            (compile-trunc label k exp (length req)
 188                           (and rest
 189                                (match (lookup-cont kargs dfg)
 190                                  (($ $kargs names (_ ... rest)) rest)))
 191                           nlocals)
 192            (unless (and fallthrough? (= kargs (1+ k)))
 193              (emit-br asm kargs))))))
 194
 195     (define (compile-tail label exp)
 196       ;; There are only three kinds of expressions in tail position:
 197       ;; tail calls, multiple-value returns, and single-value returns.
 198       (match exp
 199         (($ $call proc args)
 200          (for-each (match-lambda
 201                     ((src . dst) (emit-mov asm dst src)))
 202                    (lookup-parallel-moves label allocation))
 203          (let ((tail-slots (cdr (iota (1+ (length args))))))
 204            (for-each maybe-load-constant tail-slots args))
 205          (emit-tail-call asm (1+ (length args))))
 206         (($ $callk k proc args)
 207          (for-each (match-lambda
 208                     ((src . dst) (emit-mov asm dst src)))
 209                    (lookup-parallel-moves label allocation))
 210          (let ((tail-slots (cdr (iota (1+ (length args))))))
 211            (for-each maybe-load-constant tail-slots args))
 212          (emit-tail-call-label asm (1+ (length args)) k))
 213         (($ $values ())
 214          (emit-reset-frame asm 1)
 215          (emit-return-values asm))
 216         (($ $values (arg))
 217          (if (maybe-slot arg)
 218              (emit-return asm (slot arg))
 219              (begin
 220                (emit-load-constant asm 1 (constant arg))
 221                (emit-return asm 1))))
 222         (($ $values args)
 223          (for-each (match-lambda
 224                     ((src . dst) (emit-mov asm dst src)))
 225                    (lookup-parallel-moves label allocation))
 226          (let ((tail-slots (cdr (iota (1+ (length args))))))
 227            (for-each maybe-load-constant tail-slots args))
 228          (emit-reset-frame asm (1+ (length args)))
 229          (emit-return-values asm))
 230         (($ $primcall 'return (arg))
 231          (emit-return asm (slot arg)))))
 232
 233     (define (compile-value label exp dst nlocals)
 234       (match exp
 235         (($ $values (arg))
 236          (or (maybe-load-constant dst arg)
 237              (maybe-mov dst (slot arg))))
 238         (($ $void)
 239          (emit-load-constant asm dst *unspecified*))
 240         (($ $const exp)
 241          (emit-load-constant asm dst exp))
 242         (($ $fun src meta () ($ $cont k))
 243          (emit-load-static-procedure asm dst k))
 244         (($ $fun src meta free ($ $cont k))
 245          (emit-make-closure asm dst k (length free)))
 246         (($ $primcall 'current-module)
 247          (emit-current-module asm dst))
 248         (($ $primcall 'cached-toplevel-box (scope name bound?))
 249          (emit-cached-toplevel-box asm dst (constant scope) (constant name)
 250                                    (constant bound?)))
 251         (($ $primcall 'cached-module-box (mod name public? bound?))
 252          (emit-cached-module-box asm dst (constant mod) (constant name)
 253                                  (constant public?) (constant bound?)))
 254         (($ $primcall 'resolve (name bound?))
 255          (emit-resolve asm dst (constant bound?) (slot name)))
 256         (($ $primcall 'free-ref (closure idx))
 257          (emit-free-ref asm dst (slot closure) (constant idx)))
 258         (($ $primcall 'vector-ref (vector index))
 259          (emit-vector-ref asm dst (slot vector) (slot index)))
 260         (($ $primcall 'make-vector/immediate (length init))
 261          (emit-make-vector/immediate asm dst (constant length) (slot init)))
 262         (($ $primcall 'vector-ref/immediate (vector index))
 263          (emit-vector-ref/immediate asm dst (slot vector) (constant index)))
 264         (($ $primcall 'allocate-struct/immediate (vtable nfields))
 265          (emit-allocate-struct/immediate asm dst (slot vtable) (constant nfields)))
 266         (($ $primcall 'struct-ref/immediate (struct n))
 267          (emit-struct-ref/immediate asm dst (slot struct) (constant n)))
 268         (($ $primcall 'builtin-ref (name))
 269          (emit-builtin-ref asm dst (constant name)))
 270         (($ $primcall 'bv-u8-ref (bv idx))
 271          (emit-bv-u8-ref asm dst (slot bv) (slot idx)))
 272         (($ $primcall 'bv-s8-ref (bv idx))
 273          (emit-bv-s8-ref asm dst (slot bv) (slot idx)))
 274         (($ $primcall 'bv-u16-ref (bv idx))
 275          (emit-bv-u16-ref asm dst (slot bv) (slot idx)))
 276         (($ $primcall 'bv-s16-ref (bv idx))
 277          (emit-bv-s16-ref asm dst (slot bv) (slot idx)))
 278         (($ $primcall 'bv-u32-ref (bv idx val))
 279          (emit-bv-u32-ref asm dst (slot bv) (slot idx)))
 280         (($ $primcall 'bv-s32-ref (bv idx val))
 281          (emit-bv-s32-ref asm dst (slot bv) (slot idx)))
 282         (($ $primcall 'bv-u64-ref (bv idx val))
 283          (emit-bv-u64-ref asm dst (slot bv) (slot idx)))
 284         (($ $primcall 'bv-s64-ref (bv idx val))
 285          (emit-bv-s64-ref asm dst (slot bv) (slot idx)))
 286         (($ $primcall 'bv-f32-ref (bv idx val))
 287          (emit-bv-f32-ref asm dst (slot bv) (slot idx)))
 288         (($ $primcall 'bv-f64-ref (bv idx val))
 289          (emit-bv-f64-ref asm dst (slot bv) (slot idx)))
 290         (($ $primcall name args)
 291          ;; FIXME: Inline all the cases.
 292          (let ((inst (prim-instruction name)))
 293            (emit-text asm `((,inst ,dst ,@(map slot args))))))))
 294
 295     (define (compile-effect label exp k nlocals)
 296       (match exp
 297         (($ $values ()) #f)
 298         (($ $prompt escape? tag handler)
 299          (match (lookup-cont handler dfg)
 300            (($ $kreceive ($ $arity req () rest () #f) khandler-body)
 301             (let ((receive-args (gensym "handler"))
 302                   (nreq (length req))
 303                   (proc-slot (lookup-call-proc-slot handler allocation)))
 304               (emit-prompt asm (slot tag) escape? proc-slot receive-args)
 305               (emit-br asm k)
 306               (emit-label asm receive-args)
 307               (unless (and rest (zero? nreq))
 308                 (emit-receive-values asm proc-slot (->bool rest) nreq))
 309               (when (and rest
 310                          (match (lookup-cont khandler-body dfg)
 311                            (($ $kargs names (_ ... rest))
 312                             (maybe-slot rest))))
 313                 (emit-bind-rest asm (+ proc-slot 1 nreq)))
 314               (for-each (match-lambda
 315                          ((src . dst) (emit-mov asm dst src)))
 316                         (lookup-parallel-moves handler allocation))
 317               (emit-reset-frame asm nlocals)
 318               (emit-br asm khandler-body)))))
 319         (($ $primcall 'cache-current-module! (sym scope))
 320          (emit-cache-current-module! asm (slot sym) (constant scope)))
 321         (($ $primcall 'free-set! (closure idx value))
 322          (emit-free-set! asm (slot closure) (slot value) (constant idx)))
 323         (($ $primcall 'box-set! (box value))
 324          (emit-box-set! asm (slot box) (slot value)))
 325         (($ $primcall 'struct-set!/immediate (struct index value))
 326          (emit-struct-set!/immediate asm (slot struct) (constant index) (slot value)))
 327         (($ $primcall 'vector-set! (vector index value))
 328          (emit-vector-set! asm (slot vector) (slot index) (slot value)))
 329         (($ $primcall 'vector-set!/immediate (vector index value))
 330          (emit-vector-set!/immediate asm (slot vector) (constant index)
 331                                      (slot value)))
 332         (($ $primcall 'set-car! (pair value))
 333          (emit-set-car! asm (slot pair) (slot value)))
 334         (($ $primcall 'set-cdr! (pair value))
 335          (emit-set-cdr! asm (slot pair) (slot value)))
 336         (($ $primcall 'define! (sym value))
 337          (emit-define! asm (slot sym) (slot value)))
 338         (($ $primcall 'push-fluid (fluid val))
 339          (emit-push-fluid asm (slot fluid) (slot val)))
 340         (($ $primcall 'pop-fluid ())
 341          (emit-pop-fluid asm))
 342         (($ $primcall 'wind (winder unwinder))
 343          (emit-wind asm (slot winder) (slot unwinder)))
 344         (($ $primcall 'bv-u8-set! (bv idx val))
 345          (emit-bv-u8-set! asm (slot bv) (slot idx) (slot val)))
 346         (($ $primcall 'bv-s8-set! (bv idx val))
 347          (emit-bv-s8-set! asm (slot bv) (slot idx) (slot val)))
 348         (($ $primcall 'bv-u16-set! (bv idx val))
 349          (emit-bv-u16-set! asm (slot bv) (slot idx) (slot val)))
 350         (($ $primcall 'bv-s16-set! (bv idx val))
 351          (emit-bv-s16-set! asm (slot bv) (slot idx) (slot val)))
 352         (($ $primcall 'bv-u32-set! (bv idx val))
 353          (emit-bv-u32-set! asm (slot bv) (slot idx) (slot val)))
 354         (($ $primcall 'bv-s32-set! (bv idx val))
 355          (emit-bv-s32-set! asm (slot bv) (slot idx) (slot val)))
 356         (($ $primcall 'bv-u64-set! (bv idx val))
 357          (emit-bv-u64-set! asm (slot bv) (slot idx) (slot val)))
 358         (($ $primcall 'bv-s64-set! (bv idx val))
 359          (emit-bv-s64-set! asm (slot bv) (slot idx) (slot val)))
 360         (($ $primcall 'bv-f32-set! (bv idx val))
 361          (emit-bv-f32-set! asm (slot bv) (slot idx) (slot val)))
 362         (($ $primcall 'bv-f64-set! (bv idx val))
 363          (emit-bv-f64-set! asm (slot bv) (slot idx) (slot val)))
 364         (($ $primcall 'unwind ())
 365          (emit-unwind asm))))
 366
 367     (define (compile-values label exp syms)
 368       (match exp
 369         (($ $values args)
 370          (for-each (match-lambda
 371                     ((src . dst) (emit-mov asm dst src)))
 372                    (lookup-parallel-moves label allocation))
 373          (for-each maybe-load-constant (map slot syms) args))))
 374
 375     (define (compile-test label exp kt kf next-label)
 376       (define (unary op sym)
 377         (cond
 378          ((eq? kt next-label)
 379           (op asm (slot sym) #t kf))
 380          (else
 381           (op asm (slot sym) #f kt)
 382           (unless (eq? kf next-label)
 383             (emit-br asm kf)))))
 384       (define (binary op a b)
 385         (cond
 386          ((eq? kt next-label)
 387           (op asm (slot a) (slot b) #t kf))
 388          (else
 389           (op asm (slot a) (slot b) #f kt)
 390           (unless (eq? kf next-label)
 391             (emit-br asm kf)))))
 392       (match exp
 393         (($ $values (sym))
 394          (call-with-values (lambda ()
 395                              (lookup-maybe-constant-value sym allocation))
 396            (lambda (has-const? val)
 397              (if has-const?
 398                  (if val
 399                      (unless (eq? kt next-label)
 400                        (emit-br asm kt))
 401                      (unless (eq? kf next-label)
 402                        (emit-br asm kf)))
 403                  (unary emit-br-if-true sym)))))
 404         (($ $primcall 'null? (a)) (unary emit-br-if-null a))
 405         (($ $primcall 'nil? (a)) (unary emit-br-if-nil a))
 406         (($ $primcall 'pair? (a)) (unary emit-br-if-pair a))
 407         (($ $primcall 'struct? (a)) (unary emit-br-if-struct a))
 408         (($ $primcall 'char? (a)) (unary emit-br-if-char a))
 409         (($ $primcall 'symbol? (a)) (unary emit-br-if-symbol a))
 410         (($ $primcall 'variable? (a)) (unary emit-br-if-variable a))
 411         (($ $primcall 'vector? (a)) (unary emit-br-if-vector a))
 412         (($ $primcall 'string? (a)) (unary emit-br-if-string a))
 413         (($ $primcall 'bytevector? (a)) (unary emit-br-if-bytevector a))
 414         ;; Add more TC7 tests here.  Keep in sync with
 415         ;; *branching-primcall-arities* in (language cps primitives) and
 416         ;; the set of macro-instructions in assembly.scm.
 417         (($ $primcall 'eq? (a b)) (binary emit-br-if-eq a b))
 418         (($ $primcall 'eqv? (a b)) (binary emit-br-if-eqv a b))
 419         (($ $primcall 'equal? (a b)) (binary emit-br-if-equal a b))
 420         (($ $primcall '< (a b)) (binary emit-br-if-< a b))
 421         (($ $primcall '<= (a b)) (binary emit-br-if-<= a b))
 422         (($ $primcall '= (a b)) (binary emit-br-if-= a b))
 423         (($ $primcall '>= (a b)) (binary emit-br-if-<= b a))
 424         (($ $primcall '> (a b)) (binary emit-br-if-< b a))))
 425
 426     (define (compile-trunc label k exp nreq rest-var nlocals)
 427       (define (do-call proc args emit-call)
 428         (let* ((proc-slot (lookup-call-proc-slot label allocation))
 429                (nargs (1+ (length args)))
 430                (arg-slots (map (lambda (x) (+ x proc-slot)) (iota nargs))))
 431           (for-each (match-lambda
 432                      ((src . dst) (emit-mov asm dst src)))
 433                     (lookup-parallel-moves label allocation))
 434           (for-each maybe-load-constant arg-slots (cons proc args))
 435           (emit-call asm proc-slot nargs)
 436           (emit-dead-slot-map asm proc-slot
 437                               (lookup-dead-slot-map label allocation))
 438           (cond
 439            ((and (= 1 nreq) (and rest-var) (not (maybe-slot rest-var))
 440                  (match (lookup-parallel-moves k allocation)
 441                    ((((? (lambda (src) (= src (1+ proc-slot))) src)
 442                       . dst)) dst)
 443                    (_ #f)))
 444             ;; The usual case: one required live return value, ignoring
 445             ;; any additional values.
 446             => (lambda (dst)
 447                  (emit-receive asm dst proc-slot nlocals)))
 448            (else
 449             (unless (and (zero? nreq) rest-var)
 450               (emit-receive-values asm proc-slot (->bool rest-var) nreq))
 451             (when (and rest-var (maybe-slot rest-var))
 452               (emit-bind-rest asm (+ proc-slot 1 nreq)))
 453             (for-each (match-lambda
 454                        ((src . dst) (emit-mov asm dst src)))
 455                       (lookup-parallel-moves k allocation))
 456             (emit-reset-frame asm nlocals)))))
 457       (match exp
 458         (($ $call proc args)
 459          (do-call proc args
 460                   (lambda (asm proc-slot nargs)
 461                     (emit-call asm proc-slot nargs))))
 462         (($ $callk k proc args)
 463          (do-call proc args
 464                   (lambda (asm proc-slot nargs)
 465                     (emit-call-label asm proc-slot nargs k))))))
 466
 467     (match f
 468       (($ $fun src meta free ($ $cont k ($ $kentry self tail clause)))
 469        ;; FIXME: src on kentry instead?
 470        (when src
 471          (emit-source asm src))
 472        (compile-entry (or meta '()))))))
 473
 474 (define (visit-funs proc exp)
 475   (match exp
 476     (($ $continue _ _ exp)
 477      (visit-funs proc exp))
 478
 479     (($ $fun src meta free body)
 480      (proc exp)
 481      (visit-funs proc body))
 482
 483     (($ $letk conts body)
 484      (visit-funs proc body)
 485      (for-each (lambda (cont) (visit-funs proc cont)) conts))
 486
 487     (($ $cont sym ($ $kargs names syms body))
 488      (visit-funs proc body))
 489
 490     (($ $cont sym ($ $kclause arity body alternate))
 491      (visit-funs proc body)
 492      (when alternate
 493        (visit-funs proc alternate)))
 494
 495     (($ $cont sym ($ $kentry self tail clause))
 496      (when clause
 497        (visit-funs proc clause)))
 498
 499     (_ (values))))
 500
 501 (define (compile-bytecode exp env opts)
 502   (let* ((exp (fix-arities exp))
 503          (exp (optimize exp opts))
 504          (exp (convert-closures exp))
 505          (exp (reify-primitives exp))
 506          (exp (renumber exp))
 507          (asm (make-assembler)))
 508     (visit-funs (lambda (fun)
 509                   (compile-fun fun asm))
 510                 exp)
 511     (values (link-assembly asm #:page-aligned? (kw-arg-ref opts #:to-file? #f))
 512             env
 513             env)))