;;; ;;; compile.scm - The compiler ;;; ;;; Copyright (c) 2004-2024 Shiro Kawai ;;; ;;; Redistribution and use in source and binary forms, with or without ;;; modification, are permitted provided that the following conditions ;;; are met: ;;; ;;; 1. Redistributions of source code must retain the above copyright ;;; notice, this list of conditions and the following disclaimer. ;;; ;;; 2. Redistributions in binary form must reproduce the above copyright ;;; notice, this list of conditions and the following disclaimer in the ;;; documentation and/or other materials provided with the distribution. ;;; ;;; 3. Neither the name of the authors nor the names of its contributors ;;; may be used to endorse or promote products derived from this ;;; software without specific prior written permission. ;;; ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ;;; (declare) ;; a dummy form to suppress generation of "sci" file (define-module gauche.internal (use util.match) ) (select-module gauche.internal) (inline-stub (.include "gauche/priv/configP.h" "gauche/code.h" "gauche/vminsn.h" "gauche/priv/builtin-syms.h" "gauche/priv/glocP.h" "gauche/priv/identifierP.h" "gauche/priv/macroP.h" "gauche/priv/moduleP.h")) ;;; THE COMPILER ;;; ;;; The main entry point is COMPILE, defined under "Entry point" section. ;;; ;;; compile :: Sexpr, Module -> CompiledCode ;;; ;;; Gauche compiles programs at runtime, so we don't want to spend too ;;; much time in compilation, while we still want to generate as efficient ;;; code as possible. ;;; ;;; Structure of the compiler ;;; ;;; We have several passes, outlined here. See the header of each ;;; section for the details. ;;; ;;; Note: Source of each pass is in a separate file compile-P.scm, where ;;; P is the pass number. ;;; ;;; Pass 1 (Parsing): ;;; - Converts Sexpr into an intermediate form (IForm). ;;; - Macros and global inlinable functions are expanded. ;;; - Global constant variables are substituted to its value. ;;; - Variable bindings are resolved. Local variables are marked ;;; according to its usage (# of reference count and set count). ;;; - Constant expressions are folded. ;;; ;;; Pass 2 (Variable and closure optimization): ;;; - Traverses IForm and modify the tree to optimize it. ;;; - Limited beta-substitution (local variable substitution and ;;; inline local functions for the obvious cases). ;;; - Analyze local function usage and optimize away closures whenever ;;; possible. For example, local tail recursions are converted to ;;; loops here. ;;; - NB: This pass can make IForm a directed graph, possibly contains ;;; cycles. ;;; ;;; Pass 3 (Constant folding and branch & call optimization): ;;; - Precompute compile-time constants. This is here because Pass2's ;;; inlining and substitution allow further precomputation. ;;; - Certain $IF nodes are modified for less jump instructions ;;; (see pass3/$IF) ;;; - Eliminates redundant $LET and $SEQs introduced by constant folding. ;;; - Look into $CALL nodes for further optimization; the above ;;; optimizations may allow further inlining. ;;; ;;; Pass 4 (Lambda lifting) ;;; - At this point, remaining $LAMBDA nodes are the ones we absolutely ;;; needed. For every $LAMBDA node we find free local variables; ;;; the lvars introduced outside of the $LAMBDA. The result is set ;;; in $lambda-free-lvars slot. Then we determine $LAMBDA nodes ;;; that does not need to form a closure. We introduce a toplevel ;;; letrec that binds those lifted lambdas. ;;; ;;; Pass 5 (Code generation): ;;; - Traverses IForm and generate VM instructions. ;;; - Perform instruction combining. ;;; - Perform simple-minded jump optimization. ;;; - Some final constant foldings are done here, too. ;;; - NB: This pass modifies $LABEL node while traversing IForm: ;;; $label-label is set to the label number. (include "compile-0") ; common macros ;;===================================================================== ;; Compile-time constants ;; ;; A local frame is marked as either LEXICAL or SYNTAX in its car. (eval-when (:compile-toplevel) (define-constant LEXICAL 0) (define-constant SYNTAX 1)) ;; Max # of argument passed *literally*. This is limited by ;; VM stack size, for we need to expand args into stack. ;; Note that if arguments are 'apply'ed, usually we don't have ;; this limit since most of those args are not expanded but passed ;; to the function as the rest parameter. ;; The number is related to SCM_VM_STACK_SIZE but we can't directly ;; link to it because of cross compilation. In future maybe we can ;; make it customizable by command line args or something. (define-constant MAX_LITERAL_ARG_COUNT 8192) ;; used by pass5/$DEFINE. ;; This should match the values in src/gauche/module.h. We intentionally ;; avoid referring to the C value, ;; via (inline-stub (define-enum SCM_BINDING_CONST) ...), since doing so ;; would complicate the compilation process in case we need to change those ;; constants. (Compile.scm is compiled by the host gauche which refers to ;; the old value.) (define-constant SCM_BINDING_CONST 2) (define-constant SCM_BINDING_INLINABLE 4) ;; IForm tags (define-enum .intermediate-tags. $DEFINE $LREF $LSET $GREF $GSET $CONST $IF $LET $RECEIVE $LAMBDA $CLAMBDA $LABEL $SEQ $CALL $ASM $CONS $APPEND $VECTOR $LIST->VECTOR $LIST $LIST* $MEMV $EQ? $EQV? $IT $DYNENV ) ;; Define constants for VM instructions. ;; The 'eval-when' trick is to let the host compiler (that is compiling this ;; compiler) know those constants. (eval-when (:compile-toplevel) (use gauche.vm.insn) (define-macro (define-insn-constants) (let ([name&codes (map (^[insn] (cons (car insn) (ref (cdr insn)'code))) (class-slot-ref 'all-insns))] [mv-insn-codes (filter-map (^[insn] (and (~ (cdr insn)'multi-value) (~ (cdr insn)'code))) (class-slot-ref 'all-insns))]) `(begin ,@(map (^[n&c] `(define-constant ,(car n&c) ,(cdr n&c))) name&codes) (define-constant .insn-alist. ',name&codes) (define-constant .insn-multi-value-codes. ',mv-insn-codes) ))) (define-insn-constants) ) ;; Maximum size of $LAMBDA node we allow to duplicate and inline. (define-constant SMALL_LAMBDA_SIZE 12) ;; In case keyword is disjoint from symbols (define-inline (variable-or-keyword? arg) (or (identifier? arg) (keyword? arg))) ;;============================================================ ;; Data structures ;; ;; Local variables (lvar) ;; ;; Slots: ;; name - name of the variable (symbol) ;; initval - initialized value (Maybe IForm) ;; ref-count - in how many places this variable is referenced? ;; set-count - in how many places this variable is set! ;; (define-simple-struct lvar 'lvar make-lvar (name (initval #f) (ref-count 0) (set-count 0))) (define (make-lvar+ name) ;; procedure version of constructor, for mapping (make-lvar name)) (define-inline (lvar? obj) (and (vector? obj) (eq? (vector-ref obj 0) 'lvar))) (define (lvar-reset lvar) (lvar-ref-count-set! lvar 0) (lvar-set-count-set! lvar 0)) (define-inline (lvar-immutable? lvar) (= (lvar-set-count lvar) 0)) ;; Returns IForm if this lvar has initval and it never changes. Only valid ;; after lvar reference counting is done (that is, after pass1, and after ;; each reset-lvars call. (define (lvar-const-value lvar) (and (lvar-immutable? lvar) (vector? (lvar-initval lvar)) (lvar-initval lvar))) ;; implemented in C for better performance. (inline-stub (.define LVAR_OFFSET_TAG 0) (.define LVAR_OFFSET_NAME (lvar-name-offset)) (.define LVAR_OFFSET_INITVAL (lvar-initval-offset)) (.define LVAR_OFFSET_REF_COUNT (lvar-ref-count-offset)) (.define LVAR_OFFSET_SET_COUNT (lvar-set-count-offset)) (.define LVAR_SIZE (lvar-size)) ;; Specialized routine for (map (lambda (name) (make-lvar name)) objs) (define-cproc %map-make-lvar (names) (let* ((h SCM_NIL) (t SCM_NIL)) (dolist [name names] (let* ([v (Scm_MakeVector LVAR_SIZE '0)]) (set! (SCM_VECTOR_ELEMENT v LVAR_OFFSET_TAG) 'lvar (SCM_VECTOR_ELEMENT v LVAR_OFFSET_NAME) name (SCM_VECTOR_ELEMENT v LVAR_OFFSET_INITVAL) SCM_FALSE) (SCM_APPEND1 h t v))) (return h))) (define-cise-stmt update! [(_ offset delta) `(let* ([i::int (SCM_INT_VALUE (SCM_VECTOR_ELEMENT lvar ,offset))]) (set! (SCM_VECTOR_ELEMENT lvar ,offset) (SCM_MAKE_INT (+ i ,delta))))]) (define-cproc lvar-ref++! (lvar) :: (update! LVAR_OFFSET_REF_COUNT +1)) (define-cproc lvar-ref--! (lvar) :: (update! LVAR_OFFSET_REF_COUNT -1)) (define-cproc lvar-set++! (lvar) :: (update! LVAR_OFFSET_SET_COUNT +1)) ) ;; Compile-time environment (cenv) ;; ;; Slots: ;; module - The 'current-module' to resolve global binding. ;; frames - List of local frames. Each local frame has a form: ;; ( ( . ) ...) ;; ;; ;; ---------------------------------------------- ;; LEXICAL ;; lexical binding ;; SYNTAX ;; syntactic binding ;; ;; exp-name - The "name" of the current expression, that is, the ;; name of the variable the result of the current ;; expression is to be bound. This slot may contain ;; an identifier (for global binding) or a lvar (for ;; local binding). This slot may be #f. ;; ;; current-proc - Holds the information of the current ;; compiling procedure. It accumulates information needed ;; in later stages for the optimization. This slot may ;; be #f. ;; ;; source-path - While processing included file, this slot is set to ;; the full path of the included filename. (define-simple-struct cenv #f %make-cenv (module frames exp-name current-proc (source-path (current-load-path)))) (define (make-cenv module :optional (frames '()) (exp-name #f)) (%make-cenv module frames exp-name)) ;; Some cenv-related procedures are in C for better performance. (inline-stub ;; env-lookup-int :: Name, Module, [Frame] -> Var ;; where Var = Lvar | Identifier | Macro ;; ;; PERFORMANCE KLUDGE: ;; - We assume the frame structure is well-formed, so skip some tests. ;; (define-cfn env-lookup-int (name module::ScmModule* frames) :static (let* ([y name]) (while 1 (dopairs [fp1 frames] ;; inline assq here to squeeze performance. (dolist [vp (SCM_CDAR fp1)] (when (SCM_EQ y (SCM_CAR vp)) (return (SCM_CDR vp))))) ;; No match. We strip identifier wrapping and retry (if (SCM_IDENTIFIERP y) (let* ([inner (-> (SCM_IDENTIFIER y) name)]) (unless (SCM_IDENTIFIERP inner) (set! frames (Scm_IdentifierEnv (SCM_IDENTIFIER y)))) (set! y inner)) (break)))) ;; No local bindings. Return an identifier. (if (SCM_SYMBOLP name) (return (Scm_MakeIdentifier name module '())) (begin (SCM_ASSERT (SCM_IDENTIFIERP name)) (return name)))) ;; Internal API - used while macro expansion (define-cproc env-lookup (name module frames) (return (env-lookup-int name (SCM_MODULE module) frames))) ;; Internal API - for faster CENV lookup (define-cproc cenv-lookup (cenv name) (return (env-lookup-int name (SCM_MODULE (SCM_VECTOR_ELEMENT cenv 0)) ; module (SCM_VECTOR_ELEMENT cenv 1)))) ; frames ;; Check if Cenv is toplevel or not. ;; Since R7RS let{rec}-syntax delimits scope, its body can't contain toplevel ;; definitions. Hence existence of any frame, LEXICAL or SYNTAX, makes ;; CENV non-toplevel. ;; ;; (define (cenv-toplevel? cenv) ;; (null? (cenv-frames cenv))) ;; (define-cproc cenv-toplevel? (cenv) :: (SCM_ASSERT (SCM_VECTORP cenv)) (return (SCM_NULLP (SCM_VECTOR_ELEMENT cenv 1)))) ) (define-macro (cenv-copy-except cenv . kvs) `(%make-cenv ,(get-keyword :module kvs `(cenv-module ,cenv)) ,(get-keyword :frames kvs `(cenv-frames ,cenv)) ,(get-keyword :exp-name kvs `(cenv-exp-name ,cenv)) ,(get-keyword :current-proc kvs `(cenv-current-proc ,cenv)) ,(get-keyword :source-path kvs `(cenv-source-path ,cenv)))) (define-inline (make-bottom-cenv . maybe-module) (if (null? maybe-module) (%make-cenv (vm-current-module) '()) (%make-cenv (car maybe-module) '()))) (define-inline (cenv-swap-module cenv mod) (cenv-copy-except cenv :module mod)) (define-inline (cenv-extend cenv frame type) (cenv-copy-except cenv :frames (acons type frame (cenv-frames cenv)))) (define-inline (cenv-extend/proc cenv frame type proc) (cenv-copy-except cenv :frames (acons type frame (cenv-frames cenv)) :current-proc proc)) (define-inline (cenv-add-name cenv name) (cenv-copy-except cenv :exp-name name)) (define-inline (cenv-add-name/source cenv name source) (cenv-copy-except cenv :exp-name name :source-path source)) (define-inline (cenv-sans-name cenv) (if (cenv-exp-name cenv) (cenv-copy-except cenv :exp-name #f) cenv)) (define-inline (cenv-extend/name cenv frame type name) (cenv-copy-except cenv :frames (acons type frame (cenv-frames cenv)) :exp-name name)) (define-inline (cenv-swap-source cenv source) (cenv-copy-except cenv :source-path source)) ;; Intermediate tree form (IForm) ;; ;; We first convert the program into an intermediate tree form (IForm), ;; which is in principle similar to A-normal form, but has more ;; convenience node types specific to our VM. IForm is represented ;; by a nested vectors, whose first element shows the type of the node. ;; ;; The following table is an overview of the structure. See ;; [IForm Definitions] section below for the detailed specification. ;; ;; := ;; ;; #($define ) ;; ;; := ;; #($lref ) ;; local variable reference ;; #($lset ) ;; local variable modification ;; #($gref ) ;; global variable reference ;; #($gset ) ;; global variable modification ;; #($const ) ;; constant literal ;; #($if ) ;; branch ;; #($let ( ...) ( ...) ) ;; local binding ;; #($receive ( ...) ) ;; ;; local binding (mv) ;; #($lambda ( ...) ) ;; ;; closure ;; #($clambda ...) ;; #($label