Debian Codegraph @

src/compile.scm

raw
1 ;;;
2 ;;; compile.scm - The compiler
3 ;;;
4 ;;; Copyright (c) 2004-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (declare) ;; a dummy form to suppress generation of "sci" file
35
36 (define-module gauche.internal
37 (use util.match)
38 )
39 (select-module gauche.internal)
40
41 (inline-stub
42 (.include "gauche/priv/configP.h"
43 "gauche/code.h"
44 "gauche/vminsn.h"
45 "gauche/priv/builtin-syms.h"
46 "gauche/priv/glocP.h"
47 "gauche/priv/identifierP.h"
48 "gauche/priv/macroP.h"
49 "gauche/priv/moduleP.h"))
50
51 ;;; THE COMPILER
52 ;;;
53 ;;; The main entry point is COMPILE, defined under "Entry point" section.
54 ;;;
55 ;;; compile :: Sexpr, Module -> CompiledCode
56 ;;;
57 ;;; Gauche compiles programs at runtime, so we don't want to spend too
58 ;;; much time in compilation, while we still want to generate as efficient
59 ;;; code as possible.
60 ;;;
61 ;;; Structure of the compiler
62 ;;;
63 ;;; We have several passes, outlined here. See the header of each
64 ;;; section for the details.
65 ;;;
66 ;;; Note: Source of each pass is in a separate file compile-P.scm, where
67 ;;; P is the pass number.
68 ;;;
69 ;;; Pass 1 (Parsing):
70 ;;; - Converts Sexpr into an intermediate form (IForm).
71 ;;; - Macros and global inlinable functions are expanded.
72 ;;; - Global constant variables are substituted to its value.
73 ;;; - Variable bindings are resolved. Local variables are marked
74 ;;; according to its usage (# of reference count and set count).
75 ;;; - Constant expressions are folded.
76 ;;;
77 ;;; Pass 2 (Variable and closure optimization):
78 ;;; - Traverses IForm and modify the tree to optimize it.
79 ;;; - Limited beta-substitution (local variable substitution and
80 ;;; inline local functions for the obvious cases).
81 ;;; - Analyze local function usage and optimize away closures whenever
82 ;;; possible. For example, local tail recursions are converted to
83 ;;; loops here.
84 ;;; - NB: This pass can make IForm a directed graph, possibly contains
85 ;;; cycles.
86 ;;;
87 ;;; Pass 3 (Constant folding and branch & call optimization):
88 ;;; - Precompute compile-time constants. This is here because Pass2's
89 ;;; inlining and substitution allow further precomputation.
90 ;;; - Certain $IF nodes are modified for less jump instructions
91 ;;; (see pass3/$IF)
92 ;;; - Eliminates redundant $LET and $SEQs introduced by constant folding.
93 ;;; - Look into $CALL nodes for further optimization; the above
94 ;;; optimizations may allow further inlining.
95 ;;;
96 ;;; Pass 4 (Lambda lifting)
97 ;;; - At this point, remaining $LAMBDA nodes are the ones we absolutely
98 ;;; needed. For every $LAMBDA node we find free local variables;
99 ;;; the lvars introduced outside of the $LAMBDA. The result is set
100 ;;; in $lambda-free-lvars slot. Then we determine $LAMBDA nodes
101 ;;; that does not need to form a closure. We introduce a toplevel
102 ;;; letrec that binds those lifted lambdas.
103 ;;;
104 ;;; Pass 5 (Code generation):
105 ;;; - Traverses IForm and generate VM instructions.
106 ;;; - Perform instruction combining.
107 ;;; - Perform simple-minded jump optimization.
108 ;;; - Some final constant foldings are done here, too.
109 ;;; - NB: This pass modifies $LABEL node while traversing IForm:
110 ;;; $label-label is set to the label number.
111
112 (include "compile-0") ; common macros
113
114 ;;=====================================================================
115 ;; Compile-time constants
116 ;;
117
118 ;; A local frame is marked as either LEXICAL or SYNTAX in its car.
119 (eval-when (:compile-toplevel)
120 (define-constant LEXICAL 0)
121 (define-constant SYNTAX 1))
122
123 ;; Max # of argument passed *literally*. This is limited by
124 ;; VM stack size, for we need to expand args into stack.
125 ;; Note that if arguments are 'apply'ed, usually we don't have
126 ;; this limit since most of those args are not expanded but passed
127 ;; to the function as the rest parameter.
128 ;; The number is related to SCM_VM_STACK_SIZE but we can't directly
129 ;; link to it because of cross compilation. In future maybe we can
130 ;; make it customizable by command line args or something.
131 (define-constant MAX_LITERAL_ARG_COUNT 8192)
132
133 ;; used by pass5/$DEFINE.
134 ;; This should match the values in src/gauche/module.h. We intentionally
135 ;; avoid referring to the C value,
136 ;; via (inline-stub (define-enum SCM_BINDING_CONST) ...), since doing so
137 ;; would complicate the compilation process in case we need to change those
138 ;; constants. (Compile.scm is compiled by the host gauche which refers to
139 ;; the old value.)
140 (define-constant SCM_BINDING_CONST 2)
141 (define-constant SCM_BINDING_INLINABLE 4)
142
143 ;; IForm tags
144 (define-enum .intermediate-tags.
145 $DEFINE
146 $LREF
147 $LSET
148 $GREF
149 $GSET
150 $CONST
151 $IF
152 $LET
153 $RECEIVE
154 $LAMBDA
155 $CLAMBDA
156 $LABEL
157 $SEQ
158 $CALL
159 $ASM
160 $CONS
161 $APPEND
162 $VECTOR
163 $LIST->VECTOR
164 $LIST
165 $LIST*
166 $MEMV
167 $EQ?
168 $EQV?
169 $IT
170 $DYNENV
171 )
172
173 ;; Define constants for VM instructions.
174 ;; The 'eval-when' trick is to let the host compiler (that is compiling this
175 ;; compiler) know those constants.
176 (eval-when (:compile-toplevel)
177 (use gauche.vm.insn)
178 (define-macro (define-insn-constants)
179 (let ([name&codes
180 (map (^[insn] (cons (car insn) (ref (cdr insn)'code)))
181 (class-slot-ref <vm-insn-info> 'all-insns))]
182 [mv-insn-codes
183 (filter-map (^[insn] (and (~ (cdr insn)'multi-value)
184 (~ (cdr insn)'code)))
185 (class-slot-ref <vm-insn-info> 'all-insns))])
186 `(begin
187 ,@(map (^[n&c] `(define-constant ,(car n&c) ,(cdr n&c)))
188 name&codes)
189 (define-constant .insn-alist. ',name&codes)
190 (define-constant .insn-multi-value-codes. ',mv-insn-codes)
191 )))
192 (define-insn-constants)
193 )
194
195 ;; Maximum size of $LAMBDA node we allow to duplicate and inline.
196 (define-constant SMALL_LAMBDA_SIZE 12)
197
198 ;; In case keyword is disjoint from symbols
199 (define-inline (variable-or-keyword? arg)
200 (or (identifier? arg) (keyword? arg)))
201
202 ;;============================================================
203 ;; Data structures
204 ;;
205
206 ;; Local variables (lvar)
207 ;;
208 ;; Slots:
209 ;; name - name of the variable (symbol)
210 ;; initval - initialized value (Maybe IForm)
211 ;; ref-count - in how many places this variable is referenced?
212 ;; set-count - in how many places this variable is set!
213 ;;
214
215 (define-simple-struct lvar 'lvar make-lvar
216 (name
217 (initval #f)
218 (ref-count 0)
219 (set-count 0)))
220
221 (define (make-lvar+ name) ;; procedure version of constructor, for mapping
222 (make-lvar name))
223
224 (define-inline (lvar? obj) (and (vector? obj) (eq? (vector-ref obj 0) 'lvar)))
225 (define (lvar-reset lvar)
226 (lvar-ref-count-set! lvar 0)
227 (lvar-set-count-set! lvar 0))
228
229 (define-inline (lvar-immutable? lvar)
230 (= (lvar-set-count lvar) 0))
231
232 ;; Returns IForm if this lvar has initval and it never changes. Only valid
233 ;; after lvar reference counting is done (that is, after pass1, and after
234 ;; each reset-lvars call.
235 (define (lvar-const-value lvar)
236 (and (lvar-immutable? lvar)
237 (vector? (lvar-initval lvar))
238 (lvar-initval lvar)))
239
240 ;; implemented in C for better performance.
241 (inline-stub
242 (.define LVAR_OFFSET_TAG 0)
243 (.define LVAR_OFFSET_NAME (lvar-name-offset))
244 (.define LVAR_OFFSET_INITVAL (lvar-initval-offset))
245 (.define LVAR_OFFSET_REF_COUNT (lvar-ref-count-offset))
246 (.define LVAR_OFFSET_SET_COUNT (lvar-set-count-offset))
247 (.define LVAR_SIZE (lvar-size))
248
249 ;; Specialized routine for (map (lambda (name) (make-lvar name)) objs)
250 (define-cproc %map-make-lvar (names)
251 (let* ((h SCM_NIL) (t SCM_NIL))
252 (dolist [name names]
253 (let* ([v (Scm_MakeVector LVAR_SIZE '0)])
254 (set! (SCM_VECTOR_ELEMENT v LVAR_OFFSET_TAG) 'lvar
255 (SCM_VECTOR_ELEMENT v LVAR_OFFSET_NAME) name
256 (SCM_VECTOR_ELEMENT v LVAR_OFFSET_INITVAL) SCM_FALSE)
257 (SCM_APPEND1 h t v)))
258 (return h)))
259
260 (define-cise-stmt update!
261 [(_ offset delta)
262 `(let* ([i::int (SCM_INT_VALUE (SCM_VECTOR_ELEMENT lvar ,offset))])
263 (set! (SCM_VECTOR_ELEMENT lvar ,offset) (SCM_MAKE_INT (+ i ,delta))))])
264
265 (define-cproc lvar-ref++! (lvar) ::<void> (update! LVAR_OFFSET_REF_COUNT +1))
266 (define-cproc lvar-ref--! (lvar) ::<void> (update! LVAR_OFFSET_REF_COUNT -1))
267 (define-cproc lvar-set++! (lvar) ::<void> (update! LVAR_OFFSET_SET_COUNT +1))
268 )
269
270 ;; Compile-time environment (cenv)
271 ;;
272 ;; Slots:
273 ;; module - The 'current-module' to resolve global binding.
274 ;; frames - List of local frames. Each local frame has a form:
275 ;; (<type> (<name> . <obj>) ...)
276 ;;
277 ;; <type> <obj>
278 ;; ----------------------------------------------
279 ;; LEXICAL <lvar> ;; lexical binding
280 ;; SYNTAX <macro> ;; syntactic binding
281 ;;
282 ;; exp-name - The "name" of the current expression, that is, the
283 ;; name of the variable the result of the current
284 ;; expression is to be bound. This slot may contain
285 ;; an identifier (for global binding) or a lvar (for
286 ;; local binding). This slot may be #f.
287 ;;
288 ;; current-proc - Holds the information of the current
289 ;; compiling procedure. It accumulates information needed
290 ;; in later stages for the optimization. This slot may
291 ;; be #f.
292 ;;
293 ;; source-path - While processing included file, this slot is set to
294 ;; the full path of the included filename.
295 (define-simple-struct cenv #f %make-cenv
296 (module frames exp-name current-proc (source-path (current-load-path))))
297
298 (define (make-cenv module :optional (frames '()) (exp-name #f))
299 (%make-cenv module frames exp-name))
300
301 ;; Some cenv-related procedures are in C for better performance.
302 (inline-stub
303 ;; env-lookup-int :: Name, Module, [Frame] -> Var
304 ;; where Var = Lvar | Identifier | Macro
305 ;;
306 ;; PERFORMANCE KLUDGE:
307 ;; - We assume the frame structure is well-formed, so skip some tests.
308 ;;
309 (define-cfn env-lookup-int (name module::ScmModule* frames) :static
310 (let* ([y name])
311 (while 1
312 (dopairs [fp1 frames]
313 ;; inline assq here to squeeze performance.
314 (dolist [vp (SCM_CDAR fp1)]
315 (when (SCM_EQ y (SCM_CAR vp)) (return (SCM_CDR vp)))))
316 ;; No match. We strip identifier wrapping and retry
317 (if (SCM_IDENTIFIERP y)
318 (let* ([inner (-> (SCM_IDENTIFIER y) name)])
319 (unless (SCM_IDENTIFIERP inner)
320 (set! frames (Scm_IdentifierEnv (SCM_IDENTIFIER y))))
321 (set! y inner))
322 (break))))
323 ;; No local bindings. Return an identifier.
324 (if (SCM_SYMBOLP name)
325 (return (Scm_MakeIdentifier name module '()))
326 (begin
327 (SCM_ASSERT (SCM_IDENTIFIERP name))
328 (return name))))
329
330 ;; Internal API - used while macro expansion
331 (define-cproc env-lookup (name module frames)
332 (return (env-lookup-int name (SCM_MODULE module) frames)))
333 ;; Internal API - for faster CENV lookup
334 (define-cproc cenv-lookup (cenv name)
335 (return
336 (env-lookup-int name
337 (SCM_MODULE (SCM_VECTOR_ELEMENT cenv 0)) ; module
338 (SCM_VECTOR_ELEMENT cenv 1)))) ; frames
339
340 ;; Check if Cenv is toplevel or not.
341 ;; Since R7RS let{rec}-syntax delimits scope, its body can't contain toplevel
342 ;; definitions. Hence existence of any frame, LEXICAL or SYNTAX, makes
343 ;; CENV non-toplevel.
344 ;;
345 ;; (define (cenv-toplevel? cenv)
346 ;; (null? (cenv-frames cenv)))
347 ;;
348 (define-cproc cenv-toplevel? (cenv) ::<boolean>
349 (SCM_ASSERT (SCM_VECTORP cenv))
350 (return (SCM_NULLP (SCM_VECTOR_ELEMENT cenv 1))))
351 )
352
353 (define-macro (cenv-copy-except cenv . kvs)
354 `(%make-cenv ,(get-keyword :module kvs `(cenv-module ,cenv))
355 ,(get-keyword :frames kvs `(cenv-frames ,cenv))
356 ,(get-keyword :exp-name kvs `(cenv-exp-name ,cenv))
357 ,(get-keyword :current-proc kvs `(cenv-current-proc ,cenv))
358 ,(get-keyword :source-path kvs `(cenv-source-path ,cenv))))
359
360 (define-inline (make-bottom-cenv . maybe-module)
361 (if (null? maybe-module)
362 (%make-cenv (vm-current-module) '())
363 (%make-cenv (car maybe-module) '())))
364
365 (define-inline (cenv-swap-module cenv mod)
366 (cenv-copy-except cenv :module mod))
367
368 (define-inline (cenv-extend cenv frame type)
369 (cenv-copy-except cenv :frames (acons type frame (cenv-frames cenv))))
370
371 (define-inline (cenv-extend/proc cenv frame type proc)
372 (cenv-copy-except cenv :frames (acons type frame (cenv-frames cenv))
373 :current-proc proc))
374
375 (define-inline (cenv-add-name cenv name)
376 (cenv-copy-except cenv :exp-name name))
377
378 (define-inline (cenv-add-name/source cenv name source)
379 (cenv-copy-except cenv :exp-name name :source-path source))
380
381 (define-inline (cenv-sans-name cenv)
382 (if (cenv-exp-name cenv)
383 (cenv-copy-except cenv :exp-name #f)
384 cenv))
385
386 (define-inline (cenv-extend/name cenv frame type name)
387 (cenv-copy-except cenv :frames (acons type frame (cenv-frames cenv))
388 :exp-name name))
389
390 (define-inline (cenv-swap-source cenv source)
391 (cenv-copy-except cenv :source-path source))
392
393 ;; Intermediate tree form (IForm)
394 ;;
395 ;; We first convert the program into an intermediate tree form (IForm),
396 ;; which is in principle similar to A-normal form, but has more
397 ;; convenience node types specific to our VM. IForm is represented
398 ;; by a nested vectors, whose first element shows the type of the node.
399 ;;
400 ;; The following table is an overview of the structure. See
401 ;; [IForm Definitions] section below for the detailed specification.
402 ;;
403 ;; <top-iform> :=
404 ;; <iform>
405 ;; #($define <src> <flags> <id> <iform>)
406 ;;
407 ;; <iform> :=
408 ;; #($lref <lvar>) ;; local variable reference
409 ;; #($lset <lvar> <iform>) ;; local variable modification
410 ;; #($gref <id>) ;; global variable reference
411 ;; #($gset <id> <iform>) ;; global variable modification
412 ;; #($const <obj>) ;; constant literal
413 ;; #($if <src> <iform> <iform+> <iform+>) ;; branch
414 ;; #($let <src> <type> (<lvar> ...) (<iform> ...) <iform>) ;; local binding
415 ;; #($receive <src> <reqarg> <optarg> (<lvar> ...) <iform> <iform>)
416 ;; ;; local binding (mv)
417 ;; #($lambda <src> <name> <reqarg> <optarg> (<lvar> ...) <iform> <flag>)
418 ;; ;; closure
419 ;; #($clambda <src> <name> <lambda-node> ...)
420 ;; #($label <src> <label> <iform>) ;; merge point of local call. see below.
421 ;; #($seq (<iform> ...)) ;; sequencing
422 ;; #($call <src> <proc-expr> (<arg-expr> ...) <flag>) ;; procedure call
423 ;; #($asm <src> <insn> (<arg> ...)) ;; inline assembler
424 ;; #($cons <src> <ca> <cd>) ;; used in quasiquote
425 ;; #($append <src> <ca> <cd>) ;; ditto
426 ;; #($vector <src> (<elt> ...)) ;; ditto
427 ;; #($list->vector <src> <list>) ;; ditto
428 ;; #($list <src> (<elt> ...)) ;; ditto
429 ;; #($list* <src> (<elt> ...)) ;; ditto
430 ;; #($memv <src> <obj> <list>) ;; used in case
431 ;; #($eq? <src> <x> <y>) ;; ditto
432 ;; #($eqv? <src> <x> <y>) ;; ditto
433 ;;
434 ;; <iform+> :=
435 ;; <iform>
436 ;; #($it) ;; refer to the value in the last test clause.
437 ;;
438 ;; NB: <src> slot keeps the information of the original source, and
439 ;; will be used to generate debug info. Normally it holds the
440 ;; relevant source code, or #f if there's no relevant code.
441 ;;
442 ;; NB: the actual value of the first element is an integer instead of
443 ;; a symbol, which allows us to use vector dispatch instead
444 ;; of case expressions.
445 ;;
446 ;; NB: The nodes are destructively modified during compilation, in order
447 ;; to keep allocations minimal. Nodes shouldn't be shared, for
448 ;; side-effects may vary depends on the path to the node. The only
449 ;; exception is $label node.
450
451 (define-inline (iform-tag iform) (vector-ref iform 0))
452
453 ;; check intermediate tag
454 (define-inline (has-tag? iform tag) (eqv? (vector-ref iform 0) tag))
455
456 ;; [IForm Definitions]
457
458 ;; $define <src> <flags> <id> <expr>
459 ;; Global definition. Binds the result of <expr> to the global
460 ;; identifier <id>.
461 (define-simple-struct $define $DEFINE $define
462 (src ; original source for debugging
463 flags ; a list of flags. Currently, only the following flag
464 ; is supported:
465 ; const : the binding is constant.
466 id ; global identifier
467 expr ; expression IForm
468 ))
469
470 ;; $lref <lvar>
471 ;; Local variable reference.
472 (define-simple-struct $lref $LREF #f
473 (lvar ; lvar struct.
474 ))
475 (define-inline ($lref lvar) (lvar-ref++! lvar) (vector $LREF lvar))
476 (define-inline ($lref? iform) (has-tag? iform $LREF))
477
478 ;; $lset <lvar> <expr>
479 ;; Local variable assignment. The result of <expr> is set to <lvar>.
480 (define-simple-struct $lset $LSET #f
481 (lvar ; lvar struct
482 expr ; IForm
483 ))
484 (define-inline ($lset lvar expr)
485 (lvar-set++! lvar) (vector $LSET lvar expr))
486
487 ;; $gref <id>
488 ;; Global variable reference.
489 (define-simple-struct $gref $GREF $gref
490 (id ; identifier
491 ))
492
493 ;; $gset <id> <iform>
494 ;; Global variable assignment.
495 (define-simple-struct $gset $GSET $gset
496 (id ; identifier
497 expr ; IForm
498 ))
499
500 ;; $const <value>
501 ;; Constant.
502 (define-simple-struct $const $CONST $const
503 (value ; Scheme value
504 ))
505 (define-inline ($const? x) (has-tag? x $CONST))
506 ;; common cases
507 (define $const-undef (let1 x ($const (undefined)) (^[] x)))
508 (define $const-nil (let1 x ($const '()) (^[] x)))
509 (define $const-f (let1 x ($const #f) (^[] x)))
510 (define $const-t (let1 x ($const #t) (^[] x)))
511
512 ;; $if <src> <test> <then> <else>
513 ;; Conditional.
514 ;; A special IForm, $it, can appear in either <then> or <else>
515 ;; clause; it is no-op and indicates that the result(s) of <test>
516 ;; should be carried over.
517 (define-simple-struct $if $IF $if
518 (src ; original source for debugging
519 test ; IForm for test expression
520 then ; IForm for then expression
521 else ; IForm for else expression
522 ))
523
524 ;; $let <src> <type> <lvars> <inits> <body>
525 ;; Binding construct. let, letrec, and inlined closure is represented
526 ;; by this node (let* is expanded to the nested $let in pass 1).
527 (define-simple-struct $let $LET $let
528 (src ; original source for debugging
529 type ; indicates scope: 'let for normal let, 'rec[*] for letrec[*],
530 lvars ; list of lvars
531 inits ; list of IForms to initialize lvars
532 body ; IForm for the body
533 ))
534
535 ;; $receive <src> <reqargs> <optarg> <lvars> <expr> <body>
536 ;; Multiple value binding construct.
537 (define-simple-struct $receive $RECEIVE $receive
538 (src ; original source for debugging
539 reqargs ; # of required args
540 optarg ; 0 or 1, # of optional arg
541 lvars ; list of lvars
542 expr ; IForm for the expr to yield multiple values
543 body ; IForm for the body
544 ))
545
546 ;; $lambda <src> <name> <reqargs> <optarg> <lvars> <body> [<flag>]
547 ;; Closure.
548 ;; $lambda has a couple of transient slots, which are used only
549 ;; during the optimization paths and not be saved by pack-iform.
550 (define-simple-struct $lambda $LAMBDA $lambda
551 (src ; original source for debugging
552 name ; inferred name of this closure
553 reqargs ; # of required args
554 optarg ; 0 or 1, # of optional arg
555 lvars ; list of lvars
556 body ; IForm for the body
557 meta ; List of meta information of the nature of this lambda
558 ; node (*1)
559 ; Members can be:
560 ; 'dissolved: indicates that this lambda has been
561 ; inline expanded.
562 ; 'used: indicates that this lambda has been already dealt
563 ; with, and need to be eliminated. This one is
564 ; specifically used for communication between
565 ; pass2/$CALL and pass2/$LET.
566 ; <packed-iform> : inlinable lambda
567 ; 'constant: This lambda form is constant, meaning
568 ; it yields the same result if all the arguments
569 ; are constant.
570 ;; The following slots are used temporarily during pass2-5, and
571 ;; need not be saved when packed.
572 (calls '()) ; list of call sites
573 (free-lvars '()) ; list of free local variables
574 (lifted-var #f) ; if this $LAMBDA is lifted to the toplevel, this slot
575 ; contains an lvar to which the toplevel closure
576 ; is to be bound. See pass 4.
577 ))
578
579 ;; (*1) Up to 0.9.14, this slot contains a symbol or a packed-iform, not a
580 ;; list. This slot is embedded in the precompiled files, so we need to
581 ;; deal with such a case. Because of this, $lambda-meta slot must
582 ;; be accessed with the following utillities.
583
584 ;; TRANSIENT: Cover the case for code precompiled with older versions.
585 ;; Ensure that we always return a list.
586 (define-inline ($lambda-metas iform)
587 (let1 f ($lambda-meta iform)
588 (if (or (null? f) (pair? f))
589 f
590 (list f))))
591
592 (define-inline ($lambda-dissolved? iform)
593 (let1 f ($lambda-meta iform)
594 (or (eq? f 'dissolved) (memq 'dissolved f))))
595 (define-inline ($lambda-used? iform)
596 (let1 f ($lambda-meta iform)
597 (or (eq? f 'used) (memq 'used f))))
598 (define-inline ($lambda-constant? iform)
599 (let1 f ($lambda-meta iform)
600 (or (eq? f 'used) (memq 'used f))))
601 (define-inline ($lambda-inlinable? iform)
602 (let1 f ($lambda-meta iform)
603 (or (vector? f) (and (pair? f) (any vector? f)))))
604
605 (define-inline ($lambda-inliner iform)
606 (let1 f ($lambda-meta iform)
607 (if (vector? f) f (and (pair? f) (find vector? f)))))
608 (define ($lambda-inliner-set! iform packed-inliner)
609 (let* ([fs ($lambda-metas iform)]
610 [fs. (if (any vector? fs)
611 (cons packed-inliner (remove vector? fs))
612 (cons packed-inliner fs))])
613 ($lambda-meta-set! iform fs.)))
614
615 ;; used and dissolved are mutually exclusive
616 (define ($lambda-dissolved-set! iform)
617 (let* ([fs ($lambda-metas iform)]
618 [fs. (cond [(memq 'dissolved fs) fs]
619 [(memq 'used fs) (cons 'dissolved (delete 'used fs))]
620 [else (cons 'dissolved fs)])])
621 ($lambda-meta-set! iform fs.)))
622 (define ($lambda-used-set! iform)
623 (let* ([fs ($lambda-metas iform)]
624 [fs. (cond [(memq 'used fs) fs]
625 [(memq 'dissolved fs) (cons 'used (delete 'dissolved fs))]
626 [else (cons 'used fs)])])
627 ($lambda-meta-set! iform fs.)))
628
629 (define ($lambda-type iform)
630 ;; We avoid (find type? ($lambda-metas iform)), for it may allocate
631 ;; unnecessarily. With the old compiler, $lambda-meta never directly
632 ;; contains type object.
633 (let1 f ($lambda-meta iform)
634 (and (pair? f) (find type? f))))
635 (define ($lambda-type-set! iform type)
636 ;; we assume this is done at most once
637 ($lambda-meta-set! iform (cons type ($lambda-metas iform))))
638
639 ;; $clambda <src> <name> <lambda-node> ...
640 ;; Case-lambda.
641 ;; Closures slot contains two or more IForms. They're initially $LAMBDA
642 ;; nodes, but may be replaced with $LREF nodes by lambda-lifting pass.
643 ;; The argcounts slot is computed when this node is constructed, and
644 ;; unpacked.
645 (define-simple-struct $clambda $CLAMBDA $clambda
646 (src ; original source for debugging
647 name ; inferred name of this closure
648 closures ; list of IForms
649 ;; The following slots are transient, not saved when packed.
650 (argcounts '()) ; ((#reqargs . #optargs) ...)
651 ))
652
653 ;; $label <src> <label> <body>
654 ;; This kind of IForm node is introduced in Pass2 to record a shared
655 ;; node. It marks the destination of LOCAL-ENV-JUMP, and also is
656 ;; created during $if optimization.
657 (define-simple-struct $label $LABEL $label
658 (src ; original source for debugging
659 label ; label. #f in Pass 2. Assigned in Pass 5.
660 body ; IForm for the body
661 ))
662
663 ;; $seq <body>
664 ;; Sequencing. <body> is a list of IForms.
665 ;; The compile tries to avoid creating $seq node if <body> has only
666 ;; one expression, but optimization paths may introduce such a $seq node.
667 ;; There can also be an empty $seq node, ($seq '()).
668 (define-simple-struct $seq $SEQ #f
669 (body ; list of IForms
670 ))
671
672 (define-inline ($seq exprs)
673 (if (and (pair? exprs) (null? (cdr exprs)))
674 (car exprs)
675 (vector $SEQ exprs)))
676
677 ;; $call <src> <proc> <args> [<flag>]
678 ;; Call a procedure.
679 ;; See the "Closure optimization" section in Pass 2 for the detailed
680 ;; description.
681 (define-simple-struct $call $CALL $call
682 (src ; original source for debugging
683 proc ; IForm for the procedure to call.
684 args ; list of IForms for arguments.
685 flag ; #f, 'local, 'embed, 'jump, 'rec or 'tail-rec.
686 ;; Transient slots
687 (renv '()) ; runtime env. used in embed calls to record depth of env
688 ; in Pass 5.
689 ))
690
691 (define-inline ($call? iform) (has-tag? iform $CALL))
692
693 ;; $asm <src> <insn> <args>
694 ;; Inlined assembly code.
695 (define-simple-struct $asm $ASM $asm
696 (src ; original source for debugging
697 insn ; instruction (<code> [<param> ...])
698 args ; list of IForms
699 ))
700
701 ;; $it
702 ;; A special node. See the explanation of $if above.
703 (define $it (let ((c `#(,$IT))) (^[] c)))
704 (define-inline ($it? x) (has-tag? x $IT))
705
706 ;; $dynenv <src> (<key> <value> [<flags>]) <expr>
707 ;; Extend the dynamic environment and evaluate <expr>.
708 ;; If this is at the tail context, the dynenv of the current
709 ;; continuation is extended. Otherwise, a new continuation frame is
710 ;; pushed, dynenv is extended and <expr> is evalutaed in a tail
711 ;; context.
712 ;; FLAGS - a list of symbols. Currently supported symbols is only 'push,
713 ;; which specifies that the value is consed to the current value
714 ;; instead of replacing it.
715 ;; NB: We leave a room for future extention of multiple key-value
716 ;; pairs. It would be (<k1> <v1> <flags1> <k2> <v2> <flags2> ...).
717 (define-simple-struct $dynenv $DYNENV $dynenv
718 (src ; original source for debugging
719 kvs ; (key-iform value-iform [flags])
720 body ; body expression
721 ))
722
723 (define-inline ($dynenv-key iform) (car ($dynenv-kvs iform)))
724 (define-inline ($dynenv-value iform) (cadr ($dynenv-kvs iform)))
725 (define-inline ($dynenv-opts iform) (cddr ($dynenv-kvs iform)))
726 (define-inline ($dynenv-flags iform) (if (null? ($dynenv-opts iform))
727 '()
728 (car ($dynenv-opts iform))))
729
730 ;; The followings are builtin version of standard procedures.
731 ;;
732 (define-simple-struct $cons $CONS #f (src arg0 arg1))
733
734 ;; quasiquote tends to generate nested $cons, which can be
735 ;; packed to $list or $list*.
736 (define ($cons o x y)
737 (if (has-tag? y $CONS)
738 (receive (type elts) ($cons-pack y)
739 (vector type o (cons x elts)))
740 (vector $CONS o x y)))
741
742 (define ($cons-pack elt)
743 (cond
744 [(equal? elt ($const-nil)) (values $LIST '())]
745 [(has-tag? elt $CONS)
746 (receive (type elts) ($cons-pack (vector-ref elt 3))
747 (values type (cons (vector-ref elt 2) elts)))]
748 [else (values $LIST* (list elt))]))
749
750 (define-simple-struct $append $APPEND $append (src arg0 arg1))
751 (define-simple-struct $memv $MEMV $memv (src arg0 arg1))
752 (define-simple-struct $eq? $EQ? $eq? (src arg0 arg1))
753 (define-simple-struct $eqv? $EQV? $eqv? (src arg0 arg1))
754 (define-simple-struct $vector $VECTOR $vector (src args))
755 (define-simple-struct $list $LIST $list (src args))
756 (define-simple-struct $list* $LIST* $list* (src args))
757 (define-simple-struct $list->vector $LIST->VECTOR $list->vector (src arg0))
758
759 ;; Common accessors
760 ;; NB: These slots are not universal. Make sure you have proper IForm type
761 ;; before using them.
762 (define-inline ($*-src iform) (vector-ref iform 1))
763 (define-inline ($*-args iform) (vector-ref iform 2))
764 (define-inline ($*-arg0 iform) (vector-ref iform 2))
765 (define-inline ($*-arg1 iform) (vector-ref iform 3))
766 (define-inline ($*-args-set! iform val) (vector-set! iform 2 val))
767 (define-inline ($*-arg0-set! iform val) (vector-set! iform 2 val))
768 (define-inline ($*-arg1-set! iform val) (vector-set! iform 3 val))
769
770 ;; Extract src info from iform. Most of the time, source extraction
771 ;; is done after handlers are dispatched by iform types, so you can
772 ;; use $*-src instead (b/c you already know the type of the iform).
773 ;; You want this only in the custom inlininer that generates iforms.
774 (define (iform-src iform)
775 (case/unquote
776 (iform-tag iform)
777 [($LREF) (lvar-name ($lref-lvar iform))]
778 [($LSET) (lvar-name ($lset-lvar iform))]
779 [($GREF) ($gref-id iform)]
780 [($GSET) ($gset-id iform)]
781 [($CONST) ($const-value iform)]
782 [else ($*-src iform)]))
783
784 ;; look up symbolic name of iform tag (for debugging)
785 (define (iform-tag-name tag)
786 (let loop ((p .intermediate-tags.))
787 (cond [(null? p) #f]
788 [(eqv? (cdar p) tag) (caar p)]
789 [else (loop (cdr p))])))
790
791 ;; look up symbolic name of VM instruction (for debugging)
792 ;; (The proper way to realize this is using gauche.vm.insn, but we can't
793 ;; use it from comp.scm)
794 (define (insn-name code)
795 (let loop ((p .insn-alist.))
796 (cond [(null? p) #f]
797 [(eqv? (cdar p) code) (caar p)]
798 [else (loop (cdr p))])))
799
800 (define (insn-multi-value? code)
801 (memv code .insn-multi-value-codes.))
802
803 ;; prettyprinter of intermediate form
804 (define (pp-iform iform :optional (lines +inf.0))
805 (let/cc return
806 (define labels '()) ;; alist of label node and count
807 (define (indent count) (dotimes [i count] (write-char #\space)))
808 (define (id->string id)
809 (format "~a#~a" (module-name (slot-ref id'module)) (slot-ref id'name)))
810 (define (lvar->string lvar)
811 (format "~a.~a~a" (variable-name (lvar-name lvar))
812 (lvar-ref-count lvar)
813 (make-string (lvar-set-count lvar) #\!)))
814 (define (nl ind)
815 (newline) (dec! lines) (when (zero? lines) (return)) (indent ind))
816
817 (let rec ([ind 0] [iform iform])
818 (case/unquote
819 (iform-tag iform)
820 [($DEFINE) (format #t "($define ~a ~a" ($define-flags iform)
821 (id->string ($define-id iform)))
822 (nl (+ ind 2))
823 (rec (+ ind 2) ($define-expr iform)) (display ")")]
824 [($LREF) (format #t "($lref ~a)" (lvar->string ($lref-lvar iform)))]
825 [($LSET) (format #t "($lset ~a" (lvar->string ($lset-lvar iform)))
826 (nl (+ ind 2))
827 (rec (+ ind 2) ($lset-expr iform)) (display ")")]
828 [($GREF) (format #t "($gref ~a)" (id->string ($gref-id iform)))]
829 [($GSET) (format #t "($gset ~a" (id->string ($gset-id iform)))
830 (nl (+ ind 2))
831 (rec (+ ind 2) ($gset-expr iform)) (display ")")]
832 [($CONST) (format #t "($const ~s)" ($const-value iform))]
833 [($IF) (display "($if ")
834 (rec (+ ind 5) ($if-test iform)) (nl (+ ind 2))
835 (rec (+ ind 2) ($if-then iform)) (nl (+ ind 2))
836 (rec (+ ind 2) ($if-else iform)) (display ")")]
837 [($LET)
838 (let* ([hdr (format "($let~a ("
839 (case ($let-type iform)
840 [(let) ""] [(rec) "rec"] [(rec*) "rec*"]))]
841 [xind (+ ind (string-length hdr))]
842 [first #t])
843 (display hdr)
844 (for-each (^[var init]
845 (if first (set! first #f) (nl xind))
846 (let1 z (format "[~a " (lvar->string var))
847 (display z)
848 (rec (+ xind (string-length z)) init)
849 (display "]")))
850 ($let-lvars iform) ($let-inits iform))
851 (display ")") (nl (+ ind 2))
852 (rec (+ ind 2) ($let-body iform)) (display ")"))]
853 [($RECEIVE)
854 (format #t "($receive ~a" (map lvar->string ($receive-lvars iform)))
855 (nl (+ ind 4))
856 (rec (+ ind 4) ($receive-expr iform)) (nl (+ ind 2))
857 (rec (+ ind 2) ($receive-body iform)) (display ")")]
858 [($LAMBDA) (format #t "($lambda[~a.~a~a~a] ~a" ($lambda-name iform)
859 (length ($lambda-calls iform))
860 (if (null? ($lambda-free-lvars iform)) "" "c")
861 (if ($lambda-inlinable? iform) " inlinable" "")
862 (map lvar->string ($lambda-lvars iform)))
863 (nl (+ ind 2))
864 (rec (+ ind 2) ($lambda-body iform)) (display ")")]
865 [($CLAMBDA) (format #t "($clambda ~a" ($clambda-name iform))
866 (for-each (^l (nl (+ ind 2)) (rec (+ ind 2) l))
867 ($clambda-closures iform))
868 (display ")")]
869 [($LABEL) (if-let1 p (assq iform labels)
870 (format #t "label#~a" (cdr p))
871 (let1 num (length labels)
872 (push! labels (cons iform num))
873 (format #t "($label #~a" num)
874 (nl (+ ind 2))
875 (rec (+ ind 2) ($label-body iform)) (display ")")))]
876 [($SEQ) (format #t "($seq")
877 (for-each (^n (nl (+ ind 2)) (rec (+ ind 2) n)) ($seq-body iform))
878 (display ")")]
879 [($CALL) (let1 pre (if-let1 flag ($call-flag iform)
880 (format "($call[~a] " flag)
881 "($call ")
882 (format #t pre)
883 (rec (+ ind (string-length pre)) ($call-proc iform))
884 (for-each (^n (nl (+ ind 2)) (rec (+ ind 2) n))
885 ($call-args iform))
886 (display ")"))]
887 [($ASM)
888 (let* ([insn ($asm-insn iform)]
889 [args ($asm-args iform)]
890 [hdr (format "($asm ~a" (cons (insn-name (car insn))
891 (cdr insn)))])
892 (display hdr)
893 (case (length args)
894 [(0)]
895 [(1) (display " ") (rec (+ ind (string-length hdr) 1) (car args))]
896 [else (for-each (^n (nl (+ ind 2)) (rec (+ ind 2) n))
897 ($asm-args iform))])
898 (display ")"))]
899 [($IT) (display "($it)")]
900 [($CONS $APPEND $MEMV $EQ? $EQV?)
901 (let* ([s (format "(~a " (iform-tag-name (iform-tag iform)))]
902 [ind (+ ind (string-length s))])
903 (display s)
904 (rec ind (vector-ref iform 2)) (nl ind)
905 (rec ind (vector-ref iform 3)) (display ")"))]
906 [($LIST $LIST* $VECTOR)
907 (display (format "(~a " (iform-tag-name (iform-tag iform))))
908 (dolist [elt (vector-ref iform 2)] (nl (+ ind 2)) (rec (+ ind 2) elt))
909 (display ")")]
910 [($LIST->VECTOR)
911 (display "($LIST->VECTOR ")
912 (rec (+ ind 14) (vector-ref iform 2))
913 (display ")")]
914 [($DYNENV)
915 (display "($DYNENV (")
916 (rec (+ ind 10) ($dynenv-key iform))
917 (nl (+ ind 10))
918 (rec (+ ind 10) ($dynenv-value iform))
919 (when (pair? ($dynenv-flags iform))
920 (nl (+ ind 10))
921 (display ". ")
922 (write ($dynenv-flags iform)))
923 (display ")")
924 (nl (+ ind 2))
925 (rec (+ ind 2) ($dynenv-body iform))
926 (display ")")]
927 [else (error "pp-iform: unknown tag:" (iform-tag iform))]))
928 (newline)))
929
930 ;; Sometimes we need to save IForm for later use (e.g. procedure inlining)
931 ;; We pack an IForm into a vector, instead of keeping it as is, since:
932 ;; - For separate compilation, the saved form has to become a static
933 ;; literal, keeping it's topology. The compiler unifies equal?-literals,
934 ;; so we can't just rely on it. We also need to traverse the IForm to
935 ;; make sure everything is serializable, anyway.
936 ;; - IForm is destructively modified by pass 2, so we need to copy it
937 ;; every time it is used.
938 ;;
939 ;; Packed IForm is a vector, with the references are represented by indices.
940 ;;
941 ;; We also replace numeric tags of IForm for symbols. The numeric value
942 ;; may change across Gauche versions, while the packed IForms are recorded
943 ;; in the precompiled source and survive across versions.
944 (define (pack-iform iform)
945
946 (define dict (make-hash-table 'eq?))
947 (define r '())
948 (define c 1)
949
950 (define (put! iform . objs)
951 (rlet1 head c
952 (hash-table-put! dict iform head)
953 (dolist [obj objs] (push! r obj) (inc! c))))
954
955 (define (put!-2ary iform tag-symbol) ; $CONS $APPEND $MEMV $EQ? $EQV?
956 (put! iform tag-symbol
957 ($*-src iform)
958 (get-ref ($*-arg0 iform))
959 (get-ref ($*-arg1 iform))))
960
961 (define (put!-nary iform tag-symbol) ; $VECTOR $LIST $LIST*
962 (put! iform tag-symbol
963 ($*-src iform)
964 (map get-ref ($*-args iform))))
965
966 (define (get-ref iform)
967 (or (hash-table-get dict iform #f) (pack-iform-rec iform)))
968
969 (define (pack-iform-rec iform)
970 (case/unquote
971 (iform-tag iform)
972 [($DEFINE) (put! iform '$DEFINE ($*-src iform)
973 ($define-flags iform) ($define-id iform)
974 (get-ref ($define-expr iform)))]
975 [($LREF) (put! iform '$LREF (get-ref ($lref-lvar iform)))]
976 [($LSET) (put! iform '$LSET
977 (get-ref ($lset-lvar iform)) (get-ref ($lset-expr iform)))]
978 [($GREF) (put! iform '$GREF ($gref-id iform))]
979 [($GSET) (put! iform '$GSET ($gset-id iform) (get-ref ($gset-expr iform)))]
980 [($CONST)(put! iform '$CONST ($const-value iform))]
981 [($IF) (put! iform '$IF ($*-src iform)
982 (get-ref ($if-test iform))
983 (get-ref ($if-then iform))
984 (get-ref ($if-else iform)))]
985 [($LET) (put! iform '$LET ($*-src iform) ($let-type iform)
986 (map get-ref ($let-lvars iform))
987 (map get-ref ($let-inits iform))
988 (get-ref ($let-body iform)))]
989 [($RECEIVE) (put! iform '$RECEIVE ($*-src iform)
990 ($receive-reqargs iform) ($receive-optarg iform)
991 (map get-ref ($receive-lvars iform))
992 (get-ref ($receive-expr iform))
993 (get-ref ($receive-body iform)))]
994 [($LAMBDA) (put! iform '$LAMBDA ($*-src iform)
995 ($lambda-name iform) ($lambda-reqargs iform)
996 ($lambda-optarg iform)
997 (map get-ref ($lambda-lvars iform))
998 (get-ref ($lambda-body iform))
999 ($lambda-metas iform))]
1000 [($CLAMBDA) (put! iform '$CLAMBDA ($*-src iform)
1001 ($clambda-name iform)
1002 (map get-ref ($clambda-closures iform)))]
1003 [($LABEL) (put! iform '$LABEL ($*-src iform) #f
1004 (get-ref ($label-body iform)))]
1005 [($SEQ) (put! iform '$SEQ (map get-ref ($seq-body iform)))]
1006 [($CALL) (put! iform '$CALL ($*-src iform)
1007 (get-ref ($call-proc iform))
1008 (map get-ref ($call-args iform))
1009 ($call-flag iform))]
1010 [($ASM) (put! iform '$ASM ($*-src iform)
1011 ($asm-insn iform)
1012 (map get-ref ($asm-args iform)))]
1013 [($IT) (put! iform '$IT)]
1014 [($CONS) (put!-2ary iform '$CONS)]
1015 [($APPEND) (put!-2ary iform '$APPEND)]
1016 [($MEMV) (put!-2ary iform '$MEMV)]
1017 [($EQ?) (put!-2ary iform '$EQ?)]
1018 [($EQV?) (put!-2ary iform '$EQV?)]
1019 [($VECTOR) (put!-nary iform '$VECTOR)]
1020 [($LIST) (put!-nary iform '$LIST)]
1021 [($LIST*) (put!-nary iform '$LIST*)]
1022 [($LIST->VECTOR) (put! iform '$LIST->VECTOR ($*-src iform)
1023 (get-ref ($*-arg0 iform)))]
1024 [($DYNENV) (put! iform '$DYNENV ($*-src iform)
1025 (list* (get-ref ($dynenv-key iform))
1026 (get-ref ($dynenv-value iform))
1027 ($dynenv-opts iform))
1028 (get-ref ($dynenv-body iform)))]
1029 [('lvar) (put! iform 'lvar (lvar-name iform))]
1030 [else (errorf "[internal-error] unknown IForm in pack-iform: ~S" iform)]
1031 ))
1032
1033 ;; main body of pack-iform
1034 (let* ([start (pack-iform-rec iform)]
1035 [vec (make-vector c)])
1036 (do ([i (- c 1) (- i 1)]
1037 [r r (cdr r)])
1038 [(null? r)]
1039 (vector-set! vec i (car r)))
1040 (vector-set! vec 0 start)
1041 vec))
1042
1043 ;; Recover IForm from a vector.
1044 (define (unpack-iform ivec)
1045 (let-syntax ([V (syntax-rules ()
1046 [(V ix) (vector-ref ivec ix)]
1047 [(V ix off) (vector-ref ivec (+ ix off))])])
1048 (define dict (make-hash-table 'eqv?))
1049 (define (unpack-rec ref)
1050 (cond [(hash-table-get dict ref #f)]
1051 [else (rlet1 body (unpack-body ref)
1052 (hash-table-put! dict ref body))]))
1053 (define (unpack-body i)
1054 (case (V i)
1055 [($DEFINE) ($define (V i 1) (V i 2) (V i 3) (unpack-rec (V i 4)))]
1056 [($LREF) ($lref (unpack-rec (V i 1)))]
1057 [($LSET) ($lset (unpack-rec (V i 1)) (unpack-rec (V i 2)))]
1058 [($GREF) ($gref (V i 1))]
1059 [($GSET) ($gset (V i 1) (unpack-rec (V i 2)))]
1060 [($CONST) ($const (V i 1))]
1061 [($IF) ($if (V i 1) (unpack-rec (V i 2))
1062 (unpack-rec (V i 3)) (unpack-rec (V i 4)))]
1063 [($LET) (rlet1 unpacked
1064 ($let (V i 1) (V i 2)
1065 (map unpack-rec (V i 3)) (map unpack-rec (V i 4))
1066 (unpack-rec (V i 5)))
1067 (ifor-each2 (^(lv in) (lvar-initval-set! lv in))
1068 ($let-lvars unpacked) ($let-inits unpacked)))]
1069 [($RECEIVE) ($receive (V i 1) (V i 2) (V i 3)
1070 (map unpack-rec (V i 4)) (unpack-rec (V i 5))
1071 (unpack-rec (V i 6)))]
1072 [($LAMBDA) ($lambda (V i 1) (V i 2) (V i 3) (V i 4)
1073 (map unpack-rec (V i 5))
1074 (unpack-rec (V i 6)) (V i 7))]
1075 [($CLAMBDA) (let1 lambda-nodes (map unpack-rec (V i 3))
1076 ($clambda (V i 1) (V i 2) lambda-nodes
1077 (compute-clambda-argcounts lambda-nodes)))]
1078 [($LABEL) ($label (V i 1) (V i 2) (unpack-rec (V i 3)))]
1079 [($SEQ) ($seq (map unpack-rec (V i 1)))]
1080 [($CALL) ($call (V i 1) (unpack-rec (V i 2))
1081 (map unpack-rec (V i 3)) (V i 4))]
1082 [($ASM) ($asm (V i 1) (V i 2) (map unpack-rec (V i 3)))]
1083 [($IT) ($it)]
1084 [($CONS) ($cons (V i 1) (unpack-rec (V i 2)) (unpack-rec (V i 3)))]
1085 [($APPEND) ($append (V i 1) (unpack-rec (V i 2)) (unpack-rec (V i 3)))]
1086 [($MEMV) ($memv (V i 1) (unpack-rec (V i 2)) (unpack-rec (V i 3)))]
1087 [($EQ?) ($eq? (V i 1) (unpack-rec (V i 2)) (unpack-rec (V i 3)))]
1088 [($EQV?) ($eqv? (V i 1) (unpack-rec (V i 2)) (unpack-rec (V i 3)))]
1089 [($VECTOR) ($vector (V i 1) (map unpack-rec (V i 2)))]
1090 [($LIST) ($list (V i 1) (map unpack-rec (V i 2)))]
1091 [($LIST*) ($list* (V i 1) (map unpack-rec (V i 2)))]
1092 [($LIST->VECTOR) ($list->vector (V i 1) (unpack-rec (V i 2)))]
1093 [($DYNENV) ($dynenv (V i 1)
1094 (list* (unpack-rec (car (V i 2)))
1095 (unpack-rec (cadr (V i 2)))
1096 (cddr (V i 2)))
1097 (unpack-rec (V i 3)))]
1098 [(lvar) (make-lvar (V i 1))]
1099 [else
1100 (errorf "[internal error] unpack-iform: ivec broken at ~a (tag=~s): ~S"
1101 i (V i) ivec)]))
1102
1103 (unpack-rec (V 0))))
1104
1105 ;; Counts the size (approx # of nodes) of the iform.
1106 (define (iform-count-size-upto iform limit)
1107 (define (rec iform cnt)
1108 (letrec-syntax ([sum-items
1109 (syntax-rules (*)
1110 [(_ cnt) cnt]
1111 [(_ cnt (* item1) item2 ...)
1112 (let1 s1 (rec-list item1 cnt)
1113 (if (>= s1 limit) limit (sum-items s1 item2 ...)))]
1114 [(_ cnt item1 item2 ...)
1115 (let1 s1 (rec item1 cnt)
1116 (if (>= s1 limit) limit (sum-items s1 item2 ...)))])])
1117 (case/unquote
1118 (iform-tag iform)
1119 [($DEFINE) (sum-items (+ cnt 1) ($define-expr iform))]
1120 [($LREF $GREF $CONST) (+ cnt 1)]
1121 [($LSET) (sum-items (+ cnt 1) ($lset-expr iform))]
1122 [($GSET) (sum-items (+ cnt 1) ($gset-expr iform))]
1123 [($IF) (sum-items (+ cnt 1) ($if-test iform)
1124 ($if-then iform) ($if-else iform))]
1125 [($LET) (sum-items (+ cnt 1) (* ($let-inits iform)) ($let-body iform))]
1126 [($RECEIVE)
1127 (sum-items (+ cnt 1) ($receive-expr iform) ($receive-body iform))]
1128 [($LAMBDA) (sum-items (+ cnt 1) ($lambda-body iform))]
1129 [($CLAMBDA) (sum-items (+ cnt 1) (* ($clambda-closures iform)))]
1130 [($LABEL) (sum-items cnt ($label-body iform))]
1131 [($SEQ) (sum-items cnt (* ($seq-body iform)))]
1132 [($CALL) (sum-items (+ cnt 1) ($call-proc iform) (* ($call-args iform)))]
1133 [($ASM) (sum-items (+ cnt 1) (* ($asm-args iform)))]
1134 [($CONS $APPEND $MEMV $EQ? $EQV?)
1135 (sum-items (+ cnt 1) ($*-arg0 iform) ($*-arg1 iform))]
1136 [($VECTOR $LIST $LIST*) (sum-items (+ cnt 1) (* ($*-args iform)))]
1137 [($LIST->VECTOR) (sum-items (+ cnt 1) ($*-arg0 iform))]
1138 [($DYNENV) (sum-items (+ cnt 1) ($dynenv-key iform) ($dynenv-value iform)
1139 ($dynenv-body iform))]
1140 [($IT) cnt]
1141 [else
1142 (error "[internal error] iform-count-size-upto: unknown iform tag:"
1143 (iform-tag iform))]
1144 )))
1145 (define (rec-list iform-list cnt)
1146 (cond [(null? iform-list) cnt]
1147 [(>= cnt limit) limit]
1148 [else (rec-list (cdr iform-list) (rec (car iform-list) cnt))]))
1149 (rec iform 0))
1150
1151 ;; Copy iform.
1152 ;; Lvars that are bound within iform should be copied. Other lvars
1153 ;; (free in iform, bound outside iform) should be shared and their
1154 ;; refcount should be adjusted. lv-alist keeps assoc list of
1155 ;; old lvar to copied lvar.
1156 ;; $CALL nodes need special treatment; if it is a call to local proc,
1157 ;; the target $lambda node may have a list of call sites. We need to
1158 ;; add copied $CALL node as a new call site to the target.
1159
1160 (define (iform-copy iform lv-alist)
1161 (case/unquote
1162 (iform-tag iform)
1163 [($DEFINE) ($define ($*-src iform) ($define-flags iform) ($define-id iform)
1164 (iform-copy ($define-expr iform) lv-alist))]
1165 [($LREF) ($lref (iform-copy-lvar ($lref-lvar iform) lv-alist))]
1166 [($LSET) ($lset (iform-copy-lvar ($lset-lvar iform) lv-alist)
1167 (iform-copy ($lset-expr iform) lv-alist))]
1168 [($GREF) ($gref ($gref-id iform))]
1169 [($GSET) ($gset ($gset-id iform) (iform-copy ($gset-expr iform) lv-alist))]
1170 [($CONST)($const ($const-value iform))]
1171 [($IF) ($if ($*-src iform)
1172 (iform-copy ($if-test iform) lv-alist)
1173 (iform-copy ($if-then iform) lv-alist)
1174 (iform-copy ($if-else iform) lv-alist))]
1175 [($LET) (receive (newlvs newalist)
1176 (iform-copy-zip-lvs ($let-lvars iform) lv-alist)
1177 ($let ($*-src iform) ($let-type iform)
1178 newlvs
1179 (imap (cute iform-copy <> (case ($let-type iform)
1180 [(let) lv-alist]
1181 [(rec rec*) newalist]))
1182 ($let-inits iform))
1183 (iform-copy ($let-body iform) newalist)))]
1184 [($RECEIVE) (receive (newlvs newalist)
1185 (iform-copy-zip-lvs ($receive-lvars iform) lv-alist)
1186 ($receive ($*-src iform)
1187 ($receive-reqargs iform) ($receive-optarg iform)
1188 newlvs (iform-copy ($receive-expr iform) lv-alist)
1189 (iform-copy ($receive-body iform) newalist)))]
1190 [($LAMBDA) (receive (newlvs newalist)
1191 (iform-copy-zip-lvs ($lambda-lvars iform) lv-alist)
1192 ($lambda ($*-src iform) ($lambda-name iform)
1193 ($lambda-reqargs iform) ($lambda-optarg iform)
1194 newlvs
1195 (iform-copy ($lambda-body iform) newalist)
1196 ($lambda-meta iform)))]
1197 [($CLAMBDA) ($clambda ($*-src iform) ($clambda-name iform)
1198 (imap (cut iform-copy <> lv-alist)
1199 ($clambda-closures iform)))]
1200 [($LABEL)
1201 (cond [(assq iform lv-alist) => (^p (cdr p))]
1202 [else
1203 (rlet1 newnode
1204 ($label ($label-src iform) ($label-label iform) #f)
1205 ($label-body-set! newnode
1206 (iform-copy ($label-body iform)
1207 (acons iform newnode lv-alist))))])]
1208 [($SEQ) ($seq (imap (cut iform-copy <> lv-alist) ($seq-body iform)))]
1209 [($CALL) (rlet1 copy ($call ($*-src iform)
1210 (iform-copy ($call-proc iform) lv-alist)
1211 (imap (cut iform-copy <> lv-alist)
1212 ($call-args iform))
1213 ($call-flag iform))
1214 (and-let* ([proc ($call-proc iform)]
1215 [ ($lref? proc) ]
1216 [ (lvar-immutable? ($lref-lvar proc)) ]
1217 [target (lvar-initval ($lref-lvar proc))]
1218 [ (vector? target) ]
1219 [ (has-tag? target $LAMBDA) ]
1220 [old (assq iform ($lambda-calls target))])
1221 ($lambda-calls-set! target
1222 (acons copy (cdr old)
1223 ($lambda-calls target)))))]
1224 [($ASM) ($asm ($*-src iform) ($asm-insn iform)
1225 (imap (cut iform-copy <> lv-alist) ($asm-args iform)))]
1226 [($CONS) ($cons ($*-src iform)
1227 (iform-copy ($*-arg0 iform) lv-alist)
1228 (iform-copy ($*-arg1 iform) lv-alist))]
1229 [($APPEND) ($append ($*-src iform)
1230 (iform-copy ($*-arg0 iform) lv-alist)
1231 (iform-copy ($*-arg1 iform) lv-alist))]
1232 [($VECTOR) ($vector ($*-src iform)
1233 (imap (cut iform-copy <> lv-alist) ($*-args iform)))]
1234 [($LIST->VECTOR)
1235 ($list->vector ($*-src iform) (iform-copy ($*-arg0 iform) lv-alist))]
1236 [($LIST) ($list ($*-src iform)
1237 (imap (cut iform-copy <> lv-alist) ($*-args iform)))]
1238 [($LIST*) ($list* ($*-src iform)
1239 (imap (cut iform-copy <> lv-alist) ($*-args iform)))]
1240 [($MEMV) ($memv ($*-src iform)
1241 (iform-copy ($*-arg0 iform) lv-alist)
1242 (iform-copy ($*-arg1 iform) lv-alist))]
1243 [($EQ?) ($eq? ($*-src iform)
1244 (iform-copy ($*-arg0 iform) lv-alist)
1245 (iform-copy ($*-arg1 iform) lv-alist))]
1246 [($EQV?) ($eqv? ($*-src iform)
1247 (iform-copy ($*-arg0 iform) lv-alist)
1248 (iform-copy ($*-arg1 iform) lv-alist))]
1249 [($IT) ($it)]
1250 [($DYNENV) ($dynenv ($*-src iform)
1251 (list* (iform-copy ($dynenv-key iform) lv-alist)
1252 (iform-copy ($dynenv-value iform) lv-alist)
1253 ($dynenv-opts iform))
1254 (iform-copy ($dynenv-body iform)))]
1255 [else iform]))
1256
1257 (define (iform-copy-zip-lvs orig-lvars lv-alist)
1258 (let1 new-lvars (imap (^v (make-lvar (lvar-name v))) orig-lvars)
1259 (values new-lvars (fold-right acons lv-alist orig-lvars new-lvars))))
1260
1261 (define (iform-copy-lvar lvar lv-alist)
1262 (cond [(assq lvar lv-alist) => cdr]
1263 [else lvar]))
1264
1265 ;; Translate instruction code embedded in $ASM node. This isn't directly
1266 ;; used within the compiler, but called from the pre-compiler (precomp).
1267 ;; This is necessary to compile gauche core (compile.scm, scmlib.scm, ...)
1268 ;; after the instruction set has been changed.
1269 ;; SRC is a packed iform, TARGET-INSN-ALIST is a list of (insn-name . insn)
1270 ;; of the _target_ VM. Returns translated packed iform. We don't need
1271 ;; speed here, so we keep it simple.
1272 (define (translate-packed-iform src target-insn-alist)
1273 (define (rec iform)
1274 (case/unquote
1275 (iform-tag iform)
1276 [($DEFINE)
1277 ($define ($*-src iform) ($define-flags iform) ($define-id iform)
1278 (rec ($define-expr iform)))]
1279 [($LREF) iform]
1280 [($LSET) ($lset ($lset-lvar iform) (rec ($lset-expr iform)))]
1281 [($GREF) iform]
1282 [($GSET) ($gset ($gset-id iform) (rec ($gset-expr iform)))]
1283 [($CONST) iform]
1284 [($IF) ($if ($*-src iform)
1285 (rec ($if-test iform))
1286 (rec ($if-then iform))
1287 (rec ($if-else iform)))]
1288 [($LET) ($let ($*-src iform) ($let-type iform) ($let-lvars iform)
1289 (imap rec ($let-inits iform))
1290 (rec ($let-body iform)))]
1291 [($RECEIVE) ($receive ($*-src iform)
1292 ($receive-reqargs iform) ($receive-optarg iform)
1293 ($receive-lvars iform) (rec ($receive-expr iform))
1294 (rec ($receive-body iform)))]
1295 [($LAMBDA) ($lambda ($*-src iform) ($lambda-name iform)
1296 ($lambda-reqargs iform) ($lambda-optarg iform)
1297 ($lambda-lvars iform)
1298 (rec ($lambda-body iform))
1299 ($lambda-meta iform))]
1300 [($CLAMBDA) ($clambda ($*-src iform) ($clambda-name iform)
1301 (imap rec ($clambda-closures iform)))]
1302 [($LABEL) (error "[compiler internal] $LABEL node shouldn't appear \
1303 in the packed IForm")]
1304 [($SEQ) ($seq (imap rec ($seq-body iform)))]
1305 [($CALL) ($call ($*-src iform)
1306 (rec ($call-proc iform))
1307 (imap rec ($call-args iform))
1308 #f)]
1309 [($ASM) (let* ((host-insn ($asm-insn iform))
1310 (target-insn-info (assq (insn-name (car host-insn))
1311 target-insn-alist)))
1312 (unless target-insn-info
1313 (errorf "[compiler internal] insn ~s doesn't exist \
1314 in the target VM" (insn-name (car host-insn))))
1315 ($asm ($*-src iform)
1316 (cons (ref (cdr target-insn-info)'code)
1317 (cdr host-insn))
1318 (imap rec ($asm-args iform))))]
1319 [($CONS) ($cons ($*-src iform)
1320 (rec ($*-arg0 iform))
1321 (rec ($*-arg1 iform)))]
1322 [($APPEND) ($append ($*-src iform)
1323 (rec ($*-arg0 iform))
1324 (rec ($*-arg1 iform)))]
1325 [($VECTOR) ($vector ($*-src iform) (imap rec ($*-args iform)))]
1326 [($LIST->VECTOR) ($list->vector ($*-src iform) (rec ($*-arg0 iform)))]
1327 [($LIST) ($list ($*-src iform) (imap rec ($*-args iform)))]
1328 [($LIST*) ($list* ($*-src iform) (imap rec ($*-args iform)))]
1329 [($MEMV) ($memv ($*-src iform)
1330 (rec ($*-arg0 iform))
1331 (rec ($*-arg1 iform)))]
1332 [($EQ?) ($eq? ($*-src iform)
1333 (rec ($*-arg0 iform))
1334 (rec ($*-arg1 iform)))]
1335 [($EQV?) ($eqv? ($*-src iform)
1336 (rec ($*-arg0 iform))
1337 (rec ($*-arg1 iform)))]
1338 [($IT) ($it)]
1339 [($DYNENV) ($dynenv ($*-src iform)
1340 (list* (rec ($dynenv-key iform))
1341 (rec ($dynenv-value iform))
1342 ($dynenv-opts iform))
1343 (rec ($dynenv-body iform)))]
1344 [else iform]))
1345
1346 (pack-iform (rec (unpack-iform src))))
1347
1348 ;; See if the given iform is referentially transparent. That is,
1349 ;; the iform is side-effect free, and also the value of iform
1350 ;; won't change even if we move iform to a different place in the subtree.
1351 ;; NB: This may be called after pass2, so $LABEL node may have circular
1352 ;; reference. We have to be careful not to diverge.
1353 (define (transparent? iform)
1354 (define (side-effect-free-proc? iform) #f) ;for now
1355
1356 ;; This is used when eliminating dead $ASM node. We don't need to consider
1357 ;; combined insns, which won't be introduced until pass5.
1358 (define (side-effect-free-insn? insn)
1359 (memq (car insn) `(,EQ ,EQV ,CONS ,LIST ,LIST-STAR
1360 ,NULLP ,PAIRP ,CHARP ,EOFP ,STRINGP ,SYMBOLP
1361 ,VECTORP ,IDENTIFIERP ,NUMBERP ,REALP
1362 ,VEC)))
1363
1364 (define (rec iform labels)
1365 (case/unquote
1366 (iform-tag iform)
1367 [($LREF) (lvar-immutable? ($lref-lvar iform))]
1368 [($GREF) (gref-inlinable-gloc iform)]
1369 [($CONST) #t]
1370 [($IF) (and (rec ($if-test iform) labels)
1371 (rec ($if-then iform) labels)
1372 (rec ($if-else iform) labels))]
1373 [($LET) (and (everyc rec ($let-inits iform) labels)
1374 (rec ($let-body iform) labels))]
1375 [($RECEIVE)(and (rec ($receive-expr iform) labels)
1376 (rec ($receive-body iform) labels))]
1377 [($LAMBDA) #t]
1378 [($CLAMBDA) #t]
1379 [($LABEL) (or (label-seen? labels iform)
1380 (begin (label-push! labels iform)
1381 (rec ($label-body iform) labels)))]
1382 [($SEQ) (everyc rec ($seq-body iform) labels)]
1383 [($CALL) (and (side-effect-free-proc? ($call-proc iform))
1384 (everyc rec ($call-args iform) labels))]
1385 [($ASM) (and (side-effect-free-insn? ($asm-insn iform))
1386 (everyc rec ($asm-args iform) labels))]
1387 [($CONS $APPEND $MEMV $EQ? $EQV?)
1388 (and (rec ($*-arg0 iform) labels)
1389 (rec ($*-arg1 iform) labels))]
1390 [($VECTOR $LIST $LIST*) (everyc rec ($*-args iform) labels)]
1391 [($LIST->VECTOR) (rec ($*-arg0 iform) labels)]
1392 [($IT) #t] ; this branch is only executed when $if-test of the parent is
1393 ; transparent, thus this node is also transparent.
1394 [($DYNENV) (and (rec ($dynenv-key iform) labels)
1395 (rec ($dynenv-value iform) labels)
1396 (rec ($dynenv-body iform) labels))]
1397 [else #f]))
1398 (rec iform (make-label-dic #f)))
1399
1400 ;; Reset lvar reference count. This is called in pass3,
1401 ;; when a subgraph of IForm is eliminated.
1402 (define (reset-lvars iform) (reset-lvars/rec iform (make-label-dic #f)) iform)
1403
1404 (define-macro (reset-lvars/rec* iforms labels)
1405 `(ifor-each (^[x] (reset-lvars/rec x ,labels)) ,iforms))
1406
1407 (define/case (reset-lvars/rec iform labels)
1408 (iform-tag iform)
1409 [($DEFINE) (reset-lvars/rec ($define-expr iform) labels)]
1410 [($LREF) (lvar-ref++! ($lref-lvar iform))]
1411 [($LSET) (lvar-set++! ($lset-lvar iform))
1412 (reset-lvars/rec ($lset-expr iform) labels)]
1413 [($GSET) (reset-lvars/rec ($gset-expr iform) labels)]
1414 [($IF) (reset-lvars/rec ($if-test iform) labels)
1415 (reset-lvars/rec ($if-then iform) labels)
1416 (reset-lvars/rec ($if-else iform) labels)]
1417 [($LET) (for-each lvar-reset ($let-lvars iform))
1418 (reset-lvars/rec* ($let-inits iform) labels)
1419 (reset-lvars/rec ($let-body iform) labels)]
1420 [($RECEIVE)(for-each lvar-reset ($receive-lvars iform))
1421 (reset-lvars/rec ($receive-expr iform) labels)
1422 (reset-lvars/rec ($receive-body iform) labels)]
1423 [($LAMBDA) (for-each lvar-reset ($lambda-lvars iform))
1424 (reset-lvars/rec ($lambda-body iform) labels)]
1425 [($CLAMBDA) (reset-lvars/rec* ($clambda-closures iform) labels)]
1426 [($LABEL) (unless (label-seen? labels iform)
1427 (label-push! labels iform)
1428 (reset-lvars/rec ($label-body iform) labels))]
1429 [($SEQ) (reset-lvars/rec* ($seq-body iform) labels)]
1430 [($CALL) (unless (eq? ($call-flag iform) 'jump)
1431 (reset-lvars/rec ($call-proc iform) labels))
1432 (reset-lvars/rec* ($call-args iform) labels)]
1433 [($ASM) (reset-lvars/rec* ($asm-args iform) labels)]
1434 [($CONS $APPEND $MEMV $EQ? $EQV?)
1435 (reset-lvars/rec ($*-arg0 iform) labels)
1436 (reset-lvars/rec ($*-arg1 iform) labels)]
1437 [($VECTOR $LIST $LIST*) (reset-lvars/rec* ($*-args iform) labels)]
1438 [($LIST->VECTOR) (reset-lvars/rec ($*-arg0 iform) labels)]
1439 [($DYNENV) (reset-lvars/rec ($dynenv-key iform) labels)
1440 (reset-lvars/rec ($dynenv-value iform) labels)
1441 (reset-lvars/rec ($dynenv-body iform) labels)]
1442 [else #f])
1443
1444 ;; Replaces $LREF of matching lvar with given expression.
1445 ;; Used in the transformation of inlined procedure with closed environment.
1446 ;;
1447 ;; Example: Suppose we have the following source:
1448 ;; (define-inline (f x y) (lambda (z) (* x (+ y z))))
1449 ;; (define-inline h (f (g) 4))
1450 ;; We want to make the closure bound to 'h' inlinable. That is, when we
1451 ;; see (h 5), we want it to be expanded into something like
1452 ;; (* *g-save* (+ 4 5)), where *g-save* is the result of (g) at the time
1453 ;; h is defined. A straight transplantation of IForm wouldn't work, since
1454 ;; the $LAMBDA node for the closure bound to 'h' refers to the outer
1455 ;; environment.
1456 ;; What we do is to eliminate the reference to the outer environment by
1457 ;; beta-substitution at the time of definition of 'h', as follows:
1458 ;;
1459 ;; (define-inline h (f (g) 4))
1460 ;; v inline f
1461 ;; (define-inline h ((lambda (x y) (lambda (z) (* x (+ y z)))) (g) 4)
1462 ;; v immediate lambda expansion
1463 ;; (define-inline h (let ((x (g)) (y 4)) (lambda (z) (* x (+ y z)))))
1464 ;; v we only evaluate (g) once, so bound it to a dummy variable
1465 ;; (define-inline *h$x.1* (g))
1466 ;; (define-inline h (let ((x *h$x.1*) (y 4)) (lambda (z) (* x (+ y z)))))
1467 ;; | beta-substitution. It is always safe to substitute y for 4, since
1468 ;; | it's constant. And we know nobody else touches *h$x.1* other than
1469 ;; v 'h, so it is also safe to substitute x.
1470 ;; (define-inline *h$x.1* (g))
1471 ;; (define-inline h (lambda (z) (* *h$x.1* (+ 4 z))))
1472 ;;
1473 ;; subst-lvars does the last step; the MAPPING argument contains alist
1474 ;; of (lvar . expr), and we traverse down the IForm to replace $LREF and
1475 ;; $LSET to lvar to corresponding expr.
1476 ;; NB: We assume this happens in pass1; that is, IForm is a tree, not a DG.
1477
1478 (define (subst-lvars iform mapping)
1479 (define (subst iform mapping dict)
1480 (or (hash-table-get dict iform #f)
1481 (rlet1 r (subst-body iform mapping dict)
1482 (unless (eq? iform r) (hash-table-put! dict iform r)))))
1483 (define (subst-body iform mapping dict)
1484 (case/unquote
1485 (iform-tag iform)
1486 [($LREF) (cond [(assq ($lref-lvar iform) mapping) => cdr]
1487 [else iform])]
1488 [($LSET) (cond [(assq ($lset-lvar iform) mapping) =>
1489 (^p (unless (has-tag? (cdr p) $GREF)
1490 (error "[internal] subst-lvars: $LSET can only \
1491 subst with $GREF but got:" (cdr p)))
1492 ($gset ($gref-id (cdr p))
1493 (subst ($lset-expr iform) mapping dict)))]
1494 [else iform])]
1495 [($GSET) (let1 z (subst ($gset-expr iform) mapping dict)
1496 (if (eq? z ($gset-expr iform))
1497 iform
1498 ($gset ($gset-id iform) z)))]
1499 [($IF) (let ([test (subst ($if-test iform) mapping dict)]
1500 [then (subst ($if-then iform) mapping dict)]
1501 [else (subst ($if-else iform) mapping dict)])
1502 (if (and (eq? test ($if-test iform))
1503 (eq? then ($if-then iform))
1504 (eq? else ($if-else iform)))
1505 iform
1506 ($if ($*-src iform) test then else)))]
1507 [($LET) (let ([is (imap (cut subst <> mapping dict) ($let-inits iform))]
1508 [vs ($let-lvars iform)]
1509 [b (subst ($let-body iform) mapping dict)])
1510 (ifor-each2 (^[v i] (lvar-initval-set! v i)) vs is)
1511 ($let ($*-src iform) ($let-type iform) vs is b))]
1512 [($RECEIVE)(let ([x (subst ($receive-expr iform) mapping dict)]
1513 [b (subst ($receive-body iform) mapping dict)])
1514 (if (and (eq? x ($receive-expr iform))
1515 (eq? b ($receive-body iform)))
1516 iform
1517 ($receive ($*-src iform)
1518 ($receive-reqargs iform)
1519 ($receive-optarg iform)
1520 ($receive-lvars iform) x b)))]
1521 [($LAMBDA) (let1 b (subst ($lambda-body iform) mapping dict)
1522 (if (eq? b ($lambda-body iform))
1523 iform
1524 ($lambda ($*-src iform) ($lambda-name iform)
1525 ($lambda-reqargs iform) ($lambda-optarg iform)
1526 ($lambda-lvars iform) b ($lambda-meta iform))))]
1527 [($CLAMBDA) ($clambda ($*-src iform) ($clambda-name iform)
1528 (imap (cut subst <> mapping dict)
1529 ($clambda-closures iform)))]
1530 [($SEQ) ($seq (imap (cut subst <> mapping dict) ($seq-body iform)))]
1531 [($CALL) ($call ($*-src iform)
1532 (subst ($call-proc iform) mapping dict)
1533 (imap (cut subst <> mapping dict) ($call-args iform))
1534 ($call-flag iform))]
1535 [($ASM) ($asm ($*-src iform) ($asm-insn iform)
1536 (imap (cut subst <> mapping dict) ($asm-args iform)))]
1537 [($CONS $APPEND $MEMV $EQ? $EQV?) (subst/2 iform mapping dict)]
1538 [($VECTOR $LIST $LIST*) (subst/* iform mapping dict)]
1539 [($LIST->VECTOR) ($list->vector ($*-src iform)
1540 (subst ($*-arg0 iform) mapping dict))]
1541 [($DYNENV) ($dynenv ($*-src iform)
1542 (list* (subst ($dynenv-key iform) mapping dict)
1543 (subst ($dynenv-value iform) mapping dict)
1544 ($dynenv-opts iform))
1545 (subst ($dynenv-body iform) mapping dict))]
1546 [else iform]))
1547 (define (subst/2 iform mapping dict)
1548 (vector (vector-ref iform 0) ($*-src iform)
1549 (subst ($*-arg0 iform) mapping dict)
1550 (subst ($*-arg1 iform) mapping dict)))
1551 (define (subst/* iform mapping dict)
1552 (vector (vector-ref iform 0) ($*-src iform)
1553 (imap (cut subst <> mapping dict) ($*-args iform))))
1554 (subst iform mapping (make-hash-table 'eq?)))
1555
1556 ;; Convert IForm back to S-expr.
1557 ;; This is used by macroexpand-all. Note that pass2 can make IForm DG, and
1558 ;; it's not generally possible to convert it back to S-expr. You can only
1559 ;; pass the IForm immediately after pass1.
1560 (define (iform->sexpr iform)
1561 (define lvar-dict (make-hash-table 'eq?)) ;; lvar -> symbol
1562 (define (get-lvar lvar)
1563 (or (hash-table-get lvar-dict lvar #f)
1564 (let* ([name (lvar-name lvar)]
1565 [name (identifier->symbol name)])
1566 (rlet1 s ($ string->symbol $ format "~a.~d" name
1567 $ hash-table-num-entries lvar-dict)
1568 (hash-table-put! lvar-dict lvar s)))))
1569 (define (rec iform)
1570 (case/unquote
1571 (iform-tag iform)
1572 [($DEFINE) `(define ,($define-id iform) ,(rec ($define-expr iform)))]
1573 [($LREF) (get-lvar ($lref-lvar iform))]
1574 [($LSET) `(set! ,(get-lvar ($lset-lvar iform))
1575 ,(rec ($lset-expr iform)))]
1576 [($GREF) ($gref-id iform)]
1577 [($GSET) `(set! ,($gset-id iform) ,(rec ($gset-expr iform)))]
1578 [($CONST) (let1 v ($const-value iform)
1579 ;; This is just for better readability
1580 (if (or (number? v) (string? v) (char? v) (boolean? v)
1581 (undefined? v) (port? v) (procedure? v))
1582 v
1583 `',v))]
1584 [($IF) (cond [(has-tag? ($if-then iform) $IT)
1585 `(or ,(rec ($if-test iform))
1586 ,(rec ($if-else iform)))]
1587 [(has-tag? ($if-else iform) $IT)
1588 `(and ,(rec ($if-test iform))
1589 ,(rec ($if-then iform)))]
1590 [else
1591 `(if ,(rec ($if-test iform))
1592 ,(rec ($if-then iform))
1593 ,(rec ($if-else iform)))])]
1594 [($LET) (let ([is (map rec ($let-inits iform))]
1595 [vs (map get-lvar ($let-lvars iform))])
1596 `(letrec ,(map list vs is)
1597 ,(rec ($let-body iform))))]
1598 [($RECEIVE) (let* ([vars (map get-lvar ($receive-lvars iform))]
1599 [binds (if (zero? ($receive-optarg iform))
1600 vars
1601 (apply list* vars))])
1602 `(receive ,binds ,(rec ($receive-expr iform))
1603 ,(rec ($receive-body iform))))]
1604 [($LAMBDA) (let* ([vars (map get-lvar ($lambda-lvars iform))]
1605 [formals (if (zero? ($lambda-optarg iform))
1606 vars
1607 (apply list* vars))])
1608 `(lambda ,formals ,(rec ($lambda-body iform))))]
1609 [($CLAMBDA) (let1 cs (map rec ($clambda-closures iform))
1610 `(case-lambda ,@(map cdr cs)))]
1611 [($SEQ) `(begin ,@(map rec ($seq-body iform)))]
1612 [($CALL) `(,(rec ($call-proc iform)) ,@(map rec ($call-args iform)))]
1613 [($ASM) `(asm ,($asm-insn iform)
1614 ,@(map rec ($asm-args iform)))]
1615 [($CONS) `(cons ,(rec ($*-arg0 iform)) ,(rec ($*-arg1 iform)))]
1616 [($APPEND) `(append ,(rec ($*-arg0 iform)) ,(rec ($*-arg1 iform)))]
1617 [($MEMV) `(memv ,(rec ($*-arg0 iform)) ,(rec ($*-arg1 iform)))]
1618 [($EQ?) `(eq? ,(rec ($*-arg0 iform)) ,(rec ($*-arg1 iform)))]
1619 [($EQV?) `(eqv? ,(rec ($*-arg0 iform)) ,(rec ($*-arg1 iform)))]
1620 [($VECTOR) `(vector ,@(map rec ($*-args iform)))]
1621 [($LIST) `(list ,@(map rec ($*-args iform)))]
1622 [($LIST*) `(list* ,@(map rec ($*-args iform)))]
1623 [($LIST->VECTOR) `(list->vector ,(rec ($*-arg0 iform)))]
1624 [($IT) ; ($IT) node must have been handled by $IF
1625 (error "[internal] Stray $IT node.")]
1626 [($DYNENV) `(,(if (memq 'push ($dynenv-flags iform))
1627 'with-continuation-mark/push ;temporary
1628 'with-continuation-mark)
1629 ,(rec ($dynenv-key iform))
1630 ,(rec ($dynenv-value iform))
1631 ,(rec ($dynenv-body iform)))]
1632 [else (error "Cannot convert IForm:" (iform-tag-name (iform-tag iform)))]))
1633 (rec iform))
1634
1635 ;; Some inline stuff
1636 (define-inline (pass2-4 iform module) (pass4 (pass3 (pass2 iform) #f) module))
1637
1638 ;; Compile target. Used in pass5 to represent
1639
1640 (define-simple-struct ctarget #f %make-compile-target
1641 (ccb ;compiled code builder
1642 env-header-size
1643 cont-frame-size))
1644
1645 (define (make-compile-target :optional
1646 (env-header-size #f)
1647 (cont-frame-size #f))
1648 (%make-compile-target
1649 (make-compiled-code-builder 0 0 '%toplevel #f #f)
1650 (or env-header-size ENV_HEADER_SIZE)
1651 (or cont-frame-size CONT_FRAME_SIZE)))
1652
1653 (define (make-child-compile-target new-ccb parent-target)
1654 (%make-compile-target
1655 new-ccb
1656 (ctarget-env-header-size parent-target)
1657 (ctarget-cont-frame-size parent-target)))
1658
1659 ;;============================================================
1660 ;; Entry points
1661 ;;
1662
1663 ;; compile:: Sexpr, Env -> CompiledCode
1664 ;; Env can be:
1665 ;; #f, #<unbound> - compile on bottom env of the current module
1666 ;; module - compile on bottom env of the given module
1667 ;; cenv - compile on the given cenv
1668 ;;
1669 ;; target-params is an key-value list, with the following keys
1670 ;; recognized.
1671 ;; :env-header-size - size of environment frame header
1672 ;; :cont-frame-size - size of continuation frame
1673 (define (compile program env :key (target-params '()))
1674 (let1 cenv (cond [(module? env) (make-bottom-cenv env)]
1675 [(vector? env) env] ; assumes env is cenv
1676 [else (make-bottom-cenv)]) ; use default module
1677 (receive (env-header-size cont-frame-size)
1678 (parse-target-params target-params)
1679 (guard (e [else
1680 ;; Attach the source with <compile-error-mixin>, if it is
1681 ;; not alrady attached.
1682 ;; TODO: check if e is an expected error (such as syntax error)
1683 ;; or an unexpected error (compiler bug).
1684 (if (and (is-a? e <compound-condition>)
1685 (find (^c (and (is-a? c <compile-error-mixin>)
1686 (eq? (~ c'expr) program)))
1687 (~ e '%conditions)))
1688 (raise e)
1689 ($ raise $ make-compound-condition e
1690 $ make <compile-error-mixin> :expr program))])
1691 (pass5 (pass2-4 (pass1 program cenv) (cenv-module cenv))
1692 (make-compile-target env-header-size cont-frame-size)
1693 '() 'tail)))))
1694
1695 ;; stub for future extension
1696 (define (compile-partial program module) #f)
1697 (define (compile-finish cc) #f)
1698
1699 (define (parse-target-params target-params)
1700 (let-keywords target-params ((env-header-size #f)
1701 (cont-frame-size #f)
1702 . other-keys)
1703 (unless (null? other-keys)
1704 (error "Unrecognized compiler target parameter key:" other-keys))
1705 (values env-header-size cont-frame-size)))
1706
1707 ;; For testing
1708 (define (compile-p1 program :optional (env (vm-current-module)))
1709 (pp-iform (pass1 program (make-bottom-cenv env))))
1710
1711 (define (compile-p2 program :optional (env (vm-current-module)))
1712 (pp-iform (pass2 (pass1 program (make-bottom-cenv env)))))
1713
1714 (define (compile-p3 program :optional (show? #f) (env (vm-current-module)))
1715 (pp-iform (pass3 (pass2 (pass1 program (make-bottom-cenv env))) show?)))
1716
1717 (define (compile-p4 program :optional (env (vm-current-module)))
1718 (let1 cenv (make-bottom-cenv env)
1719 (pp-iform (pass2-4 (pass1 program cenv) (cenv-module cenv)))))
1720
1721 (define (compile-p5 program :optional (env (vm-current-module)))
1722 (let1 cenv (make-bottom-cenv env)
1723 (vm-dump-code (pass5 (pass2-4 (pass1 program cenv) (cenv-module cenv))
1724 (make-compile-target)
1725 '() 'tail))))
1726
1727 (include "compile-1")
1728 (include "compile-2")
1729 (include "compile-3")
1730 (include "compile-4")
1731 (include "compile-5")
1732 (include "compile-i")
1733 (include "compile-t")
1734
1735 ;;============================================================
1736 ;; Macro support basis
1737 ;;
1738
1739 ;; free-identifier=? id1 id2
1740 ;; Returns #t iff id1 and id2 would resolve to the same binding
1741 ;; (or both are free).
1742
1743 (select-module gauche)
1744 (inline-stub
1745 (define-cfn %free-identifier=? (id1 id2) ::int :static
1746 ;; Eliminate trivial cases first
1747 (unless (and (SCM_IDENTIFIERP id1) (SCM_IDENTIFIERP id2)) (return FALSE))
1748 (when (SCM_EQ id1 id2) (return TRUE))
1749 ;; Look at their binidngs
1750 (let* ([b1 (env-lookup-int id1
1751 (-> (SCM_IDENTIFIER id1) module)
1752 (Scm_IdentifierEnv (SCM_IDENTIFIER id1)))]
1753 [b2 (env-lookup-int id2
1754 (-> (SCM_IDENTIFIER id2) module)
1755 (Scm_IdentifierEnv (SCM_IDENTIFIER id2)))])
1756 (if (and (SCM_IDENTIFIERP b1) (SCM_IDENTIFIERP b2))
1757 (let* ([g1::ScmGloc* (Scm__IdentifierToBoundGloc (SCM_IDENTIFIER id1))]
1758 [g2::ScmGloc* (Scm__IdentifierToBoundGloc (SCM_IDENTIFIER id2))])
1759 ;; If both has bound in toplevel, they must refer to the
1760 ;; same binding, hence (eq? g1 g2). The name may differ,
1761 ;; because of renaming on export/import.
1762 ;; If at least either one is unbound, we just compare their names.
1763 (if (and g1 g2)
1764 (return (SCM_EQ g1 g2))
1765 (return (SCM_EQ (Scm_UnwrapSyntax2 id1 FALSE)
1766 (Scm_UnwrapSyntax2 id2 FALSE)))))
1767 ;; At least one of id1 and id2 is lvar or macro.
1768 (return (SCM_EQ b1 b2)))))
1769
1770 (define-cproc free-identifier=? (id1 id2) ::<boolean>
1771 %free-identifier=?)
1772 )
1773
1774 (select-module gauche.internal)
1775
1776 ;; er-rename :: (Form, [Id]) -> (Form, [Id])
1777 ;; Where symbol or identifiers in the Form will be replaced with
1778 ;; fresh identifiers. If Form has more than one occurence of a
1779 ;; specific symbol-or-id, the resulting Form has the same (eq?)
1780 ;; identifier for those occurrences.
1781 (define (er-rename form dict module env)
1782 (cond
1783 [(identifier? form)
1784 (if-let1 id (assq-ref dict form)
1785 (values id dict)
1786 (let1 id (make-identifier form module env)
1787 (values id (acons form id dict))))]
1788 [(pair? form)
1789 (receive (a dict) (er-rename (car form) dict module env)
1790 (receive (d dict) (er-rename (cdr form) dict module env)
1791 (if (and (eq? a (car form)) (eq? d (cdr form)))
1792 (values form dict)
1793 (values (cons a d) dict))))]
1794 [(vector? form)
1795 (let loop ([i 0] [vec #f] [dict dict])
1796 (if (= i (vector-length form))
1797 (values (or vec form) dict)
1798 (receive (e dict) (er-rename (vector-ref form i) dict module env)
1799 (if (eq? e (vector-ref form i))
1800 (loop (+ i 1) vec dict)
1801 (let1 vec (or vec (vector-copy form))
1802 (vector-set! vec i e)
1803 (loop (+ i 1) vec dict))))))]
1804 [else (values form dict)]))
1805
1806 ;; er-compare :: (Obj, Obj, Module, Env) -> Bool
1807 ;; Used for the 'compare' procedure in ER macro. If two Objs refer
1808 ;; to the same identifiers, return #t.
1809 ;; We implement it in C for speed; it is also called from syntax-rules
1810 ;; expander.
1811 (inline-stub
1812 (define-cfn Scm__ERCompare (a b module::ScmModule* frames) ::int
1813 (cond [(and (or (SCM_SYMBOLP a) (SCM_IDENTIFIERP a))
1814 (or (SCM_SYMBOLP b) (SCM_IDENTIFIERP b)))
1815 (let* [(a1 (env-lookup-int a module frames))
1816 (b1 (env-lookup-int b module frames))]
1817 (when (SCM_EQ a1 b1) (return TRUE))
1818 (unless (and (SCM_IDENTIFIERP a1) (SCM_IDENTIFIERP b1)) (return FALSE))
1819 (return (%free-identifier=? a1 b1)))]
1820 [(and (SCM_KEYWORDP a) (SCM_KEYWORDP b))
1821 (return (SCM_EQ a b))]
1822 [else (return FALSE)]))
1823
1824 (define-cproc er-compare (a b use-module::<module> use-frames) ::<boolean>
1825 Scm__ERCompare)
1826 )
1827
1828 ;; xformer :: (Sexpr, (Sym -> Sym), (Sym, Sym -> Bool)) -> Sexpr
1829 ;; xformer+ :: (Sexpr, (Sym -> Sym), (Sym, Sym -> Bool), (Sym -> Sym)) -> Sexpr
1830 (define (%make-er-transformer xformer def-env
1831 :key (has-inject? #f)
1832 (info-alist '())
1833 (identifier-macro? #f));deprecated
1834 (define def-module (cenv-module def-env))
1835 (define def-frames (cenv-frames def-env))
1836 (define (expand form use-env)
1837 (define use-module (cenv-module use-env))
1838 (define use-frames (cenv-frames use-env))
1839 (let1 dict '()
1840 (define %rename
1841 ;; NB: We attach macro input in a procedure tag value (not the SRFI-229
1842 ;; tag, but using the native alist tag.) Quasirename retrieves this
1843 ;; info and attach it to the output.
1844 ;; For now, we don't have lambda/tags-alist, so we have to copy
1845 ;; the procedure.
1846 (%procedure-copy
1847 (lambda (sym)
1848 (receive [id dict_] (er-rename sym dict def-module def-frames)
1849 (set! dict dict_)
1850 id))
1851 `((macro-input . ,(unwrap-syntax form)))))
1852 (define (%compare a b) (er-compare a b use-module use-frames))
1853 (define (%inject sym)
1854 (receive [id dict_] (er-rename sym dict use-module use-frames)
1855 (set! dict dict_)
1856 id))
1857 (if has-inject?
1858 (xformer form %rename %compare %inject)
1859 (xformer form %rename %compare))))
1860 (%make-macro-transformer (cenv-exp-name def-env) expand info-alist
1861 (if identifier-macro?
1862 '(identifier-macro)
1863 '())))
1864
1865 ;; Call to this procedure can be inserted in the output of er-macro expander
1866 ;; and emitted in the precompiled file, so do not change this API unless
1867 ;; you're sure no existing precompiled code refers to this.
1868 (define (%make-er-transformer/toplevel xformer def-module def-name
1869 :key (has-inject? #f)
1870 (info-alist '())
1871 (identifier-macro? #f));deprecated
1872 (%make-er-transformer xformer
1873 (%make-cenv def-module '() def-name)
1874 :has-inject? has-inject?
1875 :info-alist info-alist
1876 :identifier-macro? identifier-macro?))
1877
1878 ;; Turn a macro to an id macro.
1879 (define (%make-id-transformer macro name)
1880 (assume-type macro <macro>)
1881 (%make-macro-transformer name
1882 (~ macro'transformer)
1883 (~ macro'info-alist)
1884 (cons 'identifier-macro (~ macro'flags))))
1885
1886 ;; Turn a macro to a parameterizable macro.
1887 (define (%make-parameterizable-transformer macro name)
1888 (assume-type macro <macro>)
1889 (%make-macro-transformer name
1890 (~ macro'transformer)
1891 (~ macro'info-alist)
1892 (cons 'parameterizable (~ macro'flags))))
1893
1894 ;; Returns an S-expr all macros in which are expanded.
1895 ;; The resulting form may not be equivalent to the input form, though,
1896 ;; since we strip off identifier information so toplevel hygiene isn't
1897 ;; kept. (Local variables are renamed so they won't conflict with each
1898 ;; other.)
1899 (define-in-module gauche (macroexpand-all form :optional (env #f))
1900 (let ([flags-save (vm-compiler-flag)]
1901 [env (cond
1902 [(boolean? env) (vm-current-module)]
1903 [(module? env) env]
1904 [else (error "a boolean or a module required but got:" env)])])
1905 (unwind-protect
1906 (begin
1907 ;; Suppress inline expansion to ASM node, for it is useless as
1908 ;; the macro output.
1909 (vm-compiler-flag-set! SCM_COMPILE_NOINLINE_INLINER)
1910 ($ unwrap-syntax $ iform->sexpr
1911 $ pass1 form (make-bottom-cenv env)))
1912 (begin
1913 (vm-compiler-flag-clear! SCM_COMPILE_NOINLINE_INLINER)
1914 (vm-compiler-flag-set! flags-save)))))
1915
1916 ;;--------------------------------------------------------
1917 ;; Customizable inliner interface
1918 ;;
1919
1920 ;; This is invoked from the expansion of define-hybrid-syntax.
1921 (define (%with-inline-transformer proc xformer)
1922 (unless (procedure? proc)
1923 (error "define-hybrid-syntax: expression yields non-procedure value" proc))
1924 (unless (macro? xformer)
1925 (errorf "macro required, but got" xformer))
1926 ;; Copy PROC, in case the given proc refers to already defined global
1927 ;; procedure. We don't want to modify existing procedure instance.
1928 (rlet1 p (%procedure-copy proc)
1929 (set! (%procedure-inliner p) xformer)))
1930
1931
1932 ;;============================================================
1933 ;; Utilities
1934 ;;
1935
1936 ;; Keep track of visited $LABEL node while traversing IForm. The lookup
1937 ;; is only done when we hit $LABEL node, so the performance is not so critical.
1938 ;; The CAR of label-dic isn't used to keep label info, and may be used by
1939 ;; the caller to keep extra info.
1940 (define (make-label-dic init) (list init))
1941 (define (label-seen? label-dic label-node) (memq label-node (cdr label-dic)))
1942 (define (label-push! label-dic label-node) (push! (cdr label-dic) label-node))
1943 (define (label-dic-info label-dic) (car label-dic))
1944 (define (label-dic-info-set! label-dic val) (set-car! label-dic val))
1945 (define (label-dic-info-push! label-dic val) (push! (car label-dic) val))
1946
1947 ;; see if the immediate integer value fits in the insn arg.
1948 (define (integer-fits-insn-arg? obj)
1949 (and (integer? obj)
1950 (exact? obj)
1951 (<= #x-7ffff obj #x7ffff)))
1952
1953 (define (unsigned-integer-fits-insn-arg? obj)
1954 (and (integer? obj)
1955 (exact? obj)
1956 (<= 0 obj #x7ffff)))
1957
1958 (define (variable-name arg)
1959 (cond [(identifier? arg) (identifier->symbol arg)]
1960 [(lvar? arg) (lvar-name arg)]
1961 [else (error "variable required, but got:" arg)]))
1962
1963 ;; When the compiler transforms a source ORIGINAL to CONSTRUCTED,
1964 ;; we attach the original source info to the initial pair of the
1965 ;; constructed source.
1966 (define (with-original-source constructed original)
1967 (if (pair? constructed)
1968 (rlet1 p (if (extended-pair? constructed)
1969 constructed
1970 (extended-cons (car constructed) (cdr constructed)))
1971 (pair-attribute-set! p 'original original))
1972 constructed))
1973
1974 ;; GLOBAL-CALL-TYPE
1975 ;;
1976 ;; This is an aux call to dispatch the function call with global variable
1977 ;; reference in its first position (in pass1/global-call). It checks
1978 ;; up the binding of global identifier, and returns two values.
1979 ;;
1980 ;; The first value is #f if this global call would be a simple call.
1981 ;; Otherwise, the first value is a bound value of the global variable,
1982 ;; and the second value is one of the symbols 'macro, 'syntax, 'inline,
1983 ;; or 'type-ctor.
1984 ;;
1985 ;; We write this in C because it is in critical path of the compiler.
1986 ;;
1987 ;; {Experimental}
1988 ;; If RECORD_DEPENDED_MODULES is defined, this proc also records
1989 ;; modules from which macro/syntax identifiers come. It will be used
1990 ;; in test-module to detect unnecessarily 'use'd modules. For normal
1991 ;; procedure we can scan identifier/glocs embedded in the VM code
1992 ;; vector, but for the case of macros/syntaxes/inlined procedures
1993 ;; the original identifier is lost during expansion, so we need to
1994 ;; record it at compile time.
1995 ;; Although global-call-type is in critical path, my benchmark showed
1996 ;; little impact from this addition.
1997 ;; I still don't feel "right" about having this hack here, though.
1998 ;; Just keep it for now, for the record.
1999 (inline-stub
2000 (.if (defined RECORD_DEPENDED_MODULES)
2001 (begin
2002 "static ScmModule *stdmods[3];"
2003
2004 (initcode
2005 "stdmods[0] = Scm_NullModule();"
2006 "stdmods[1] = Scm_SchemeModule();"
2007 "stdmods[2] = Scm_GaucheModule();")))
2008
2009 (define-cproc global-call-type (id cenv) ::(<top> <top>)
2010 (let* ([mod::ScmModule* (-> (SCM_IDENTIFIER id) module)]
2011 [gloc::ScmGloc* (Scm_IdentifierGlobalBinding (SCM_IDENTIFIER id))])
2012 (set! SCM_RESULT0 '#f SCM_RESULT1 '#f)
2013 (cast void cenv) ; suppress unused var warning
2014 (cast void mod) ; suppress unused var warning
2015 (when gloc
2016 (let* ([gval (SCM_GLOC_GET gloc)])
2017 (cond [(SCM_MACROP gval)
2018 (set! SCM_RESULT0 gval SCM_RESULT1 'macro)]
2019 [(SCM_SYNTAXP gval)
2020 (set! SCM_RESULT0 gval SCM_RESULT1 'syntax)]
2021 [(SCM_PROCEDUREP gval)
2022 (let* ([inl (SCM_PROCEDURE_INLINER gval)])
2023 (if (and inl ; inliner may be NULL
2024 (not (SCM_FALSEP inl))
2025 (Scm_GlocInlinableP gloc)
2026 (not (SCM_VM_COMPILER_FLAG_IS_SET
2027 (Scm_VM) SCM_COMPILE_NOINLINE_GLOBALS))
2028 ;; When SCM_COMPILE_NOINLINE_INLINER is set, we
2029 ;; suppress inliner expansion except inl is a macro
2030 ;; xformer (define-hybrid-syntax creates it).
2031 ;; It is only for macroexpand-all; other inliners
2032 ;; may expand into $asm node, which isn't useful
2033 ;; as the output of macro expansion.
2034 (not (and (SCM_VM_COMPILER_FLAG_IS_SET
2035 (Scm_VM) SCM_COMPILE_NOINLINE_INLINER)
2036 (not (SCM_MACROP inl)))))
2037 (set! SCM_RESULT0 gval SCM_RESULT1 'inline)
2038 (goto normal)))]
2039 [(and (Scm_TypeConstructorP gval)
2040 (Scm_GlocInlinableP gloc))
2041 (set! SCM_RESULT0 gval SCM_RESULT1 'type-ctor)]
2042 [else (goto normal)])
2043 (.if "defined(RECORD_DEPENDED_MODULES)"
2044 (begin
2045 (dotimes [i 3]
2046 (when (SCM_EQ mod (aref stdmods i)) (goto normal)))
2047 (let* ([curmod (SCM_VECTOR_ELEMENT cenv 0)])
2048 (SCM_ASSERT (SCM_MODULEP curmod))
2049 (when (SCM_FALSEP
2050 (Scm_Memq (SCM_OBJ mod)
2051 (-> (SCM_MODULE curmod) depended)))
2052 (set! (-> (SCM_MODULE curmod) depended)
2053 (Scm_Cons (SCM_OBJ mod)
2054 (-> (SCM_MODULE curmod) depended)))))))
2055 ))
2056 (label normal)
2057 ))
2058 )
2059
2060 ;; GLOBAL-REF-TYPE
2061 ;;
2062 ;; Similar to global-call-type, but this is called when ID is used
2063 ;; other than the head of list. Should be called after we know ID is
2064 ;; global reference.
2065 ;;
2066 ;; If ID is globally bound to a macro, returns #<macro>.
2067 ;; Otherwise, returns ID itself.
2068 ;;
2069 ;; We separate this from global-call-type, since we don't need to
2070 ;; handle inlinable function case.
2071 ;;
2072 (inline-stub
2073 (define-cproc global-ref-type (id) ::<top>
2074 (let* ([gloc::ScmGloc* (Scm_IdentifierGlobalBinding (SCM_IDENTIFIER id))])
2075 (if gloc
2076 (let* ([gval (SCM_GLOC_GET gloc)])
2077 (if (SCM_MACROP gval)
2078 (return gval)
2079 (return id)))
2080 (return id))))
2081 )
2082
2083 ;; Returns #t iff z is a keyword, or an identifier made from a keyword.
2084 ;; TODO: We should also check iff k isn't bound to something else!
2085 (define (keyword-like? k)
2086 (or (keyword? k)
2087 (and (wrapped-identifier? k) (keyword? (identifier->symbol k)))))
2088
2089 (define (global-eq? var id cenv) ; like free-identifier=?, used in pass1.
2090 (and (identifier? var)
2091 (let1 v (cenv-lookup cenv var)
2092 (and (wrapped-identifier? v)
2093 (global-identifier=? v id)))))
2094
2095 ;; TRANSIENT: To compare keyword hygienically. We need to treat keywords
2096 ;; specially until we complete keyword-symbol integration.
2097 (define (global-keyword-eq? var key cenv)
2098 (or (eq? var key)
2099 (and (symbol? key)
2100 (wrapped-identifier? var)
2101 (global-eq? var (global-id key) cenv))))
2102
2103 (define (everyc proc lis c) ;avoid closure allocation
2104 (or (null? lis)
2105 (let loop ((lis lis))
2106 (match lis
2107 [(x) (proc x c)]
2108 [(x . xs) (and (proc x c) (loop xs))]))))
2109
2110 ;; Check if iform is a lambda node that has no side effects.
2111 (define (constant-lambda? iform)
2112 (and (vector? iform)
2113 (has-tag? iform $LAMBDA)
2114 (transparent? ($lambda-body iform))))
2115
2116 ;; To compare identifiers w/ hygiene. Returns a predicate that takes
2117 ;; a single argument VAR, which must be a symbol or identifier that
2118 ;; appears in the toplevel environment with a module that are returned by
2119 ;; calling a thunk MODGEN. The predicate returns #t iff VAR represents
2120 ;; the same global binding of SYM within the module SRCMOD.
2121 ;; This is used in precomp.
2122 (define (global-eq?? sym srcmod modgen)
2123 (let1 id-gloc (find-binding (find-module srcmod) sym #f)
2124 (^[var] (eq? id-gloc
2125 (if (wrapped-identifier? var)
2126 (find-binding (slot-ref var'module) (slot-ref var'name) #f)
2127 (find-binding (modgen) var #f))))))
2128
2129 ;; Some C routines called from the expanded macro result.
2130 ;; These procedures are originally implemented in Scheme, but moved
2131 ;; here for efficiency.
2132 (inline-stub
2133 ;; %imax - max for unsigned integer only, unsafe.
2134 (define-cproc %imax (x y)
2135 (if (> (SCM_WORD x) (SCM_WORD y)) (return x) (return y)))
2136
2137 ;; (%map1c proc lis c) = (map (cut proc <> c) lis)
2138 (define-cfn map1c_cc (result data::void**) :static
2139 (let* ([proc (SCM_OBJ (aref data 0))]
2140 [r (SCM_OBJ (aref data 1))]
2141 [lis (SCM_OBJ (aref data 2))]
2142 [c (SCM_OBJ (aref data 3))])
2143 (cond [(SCM_NULLP lis) (return (Scm_ReverseX (Scm_Cons result r)))]
2144 [else
2145 (set! (aref data 1) (Scm_Cons result r)
2146 (aref data 2) (SCM_CDR lis))
2147 (Scm_VMPushCC map1c_cc data 4)
2148 (return (Scm_VMApply2 proc (SCM_CAR lis) c))])))
2149
2150 (define-cproc %map1c (proc lis c)
2151 (let* ([data::(.array void* [4])])
2152 (cond [(SCM_NULLP lis) (return SCM_NIL)]
2153 [else
2154 (set! (aref data 0) proc
2155 (aref data 1) SCM_NIL
2156 (aref data 2) (SCM_CDR lis)
2157 (aref data 3) c)
2158 (Scm_VMPushCC map1c_cc data 4)
2159 (return (Scm_VMApply2 proc (SCM_CAR lis) c))])))
2160
2161 ;; (%map1cc proc lis c1 c2) = (map (cut proc <> c1 c2) lis)
2162 (define-cfn map1cc-cc (result (data :: void**)) :static
2163 (let* ([proc (SCM_OBJ (aref data 0))]
2164 [r (SCM_OBJ (aref data 1))]
2165 [lis (SCM_OBJ (aref data 2))]
2166 [c1 (SCM_OBJ (aref data 3))]
2167 [c2 (SCM_OBJ (aref data 4))])
2168 (cond [(SCM_NULLP lis) (return (Scm_ReverseX (Scm_Cons result r)))]
2169 [else
2170 (set! (aref data 1) (Scm_Cons result r)
2171 (aref data 2) (SCM_CDR lis))
2172 (Scm_VMPushCC map1cc-cc data 5)
2173 (return (Scm_VMApply3 proc (SCM_CAR lis) c1 c2))])))
2174
2175 (define-cproc %map1cc (proc lis c1 c2)
2176 (if (SCM_NULLP lis)
2177 (return SCM_NIL)
2178 (let* ([data::(.array void* [5])])
2179 (set! (aref data 0) proc
2180 (aref data 1) SCM_NIL
2181 (aref data 2) (SCM_CDR lis)
2182 (aref data 3) c1
2183 (aref data 4) c2)
2184 (Scm_VMPushCC map1cc-cc data 5)
2185 (return (Scm_VMApply3 proc (SCM_CAR lis) c1 c2)))))
2186
2187 ;; (%map-cons lis1 lis2) = (map cons lis1 lis2)
2188 (define-cproc %map-cons (lis1 lis2)
2189 (let* ([h SCM_NIL] [t SCM_NIL])
2190 (while (and (SCM_PAIRP lis1) (SCM_PAIRP lis2))
2191 (SCM_APPEND1 h t (Scm_Cons (SCM_CAR lis1) (SCM_CAR lis2)))
2192 (set! lis1 (SCM_CDR lis1) lis2 (SCM_CDR lis2)))
2193 (return h)))
2194 )
2195
2196 ;;============================================================
2197 ;; VM introspection
2198 ;;
2199
2200 (inline-stub
2201 (define-cproc %get-env-frame-size () ::<fixnum>
2202 (return (ENV_SIZE 0)))
2203
2204 (define-cproc %get-cont-frame-size () ::<fixnum>
2205 (return CONT_FRAME_SIZE))
2206
2207 )
2208
2209 ;; These values can be overridden when we cross-compile (including
2210 ;; inter-version compiling).
2211 (define ENV_HEADER_SIZE (%get-env-frame-size))
2212 (define CONT_FRAME_SIZE (%get-cont-frame-size))
2213
2214 (inline-stub
2215 ;; Eval situation flag (for eval-when constrcut)
2216 (define-cproc vm-eval-situation (:optional val) ::<int>
2217 (let* ([vm::ScmVM* (Scm_VM)])
2218 (cond [(SCM_UNBOUNDP val) (return (-> vm evalSituation))]
2219 [else
2220 (unless (SCM_INTP val) (SCM_TYPE_ERROR val "integer"))
2221 (let* ([prev::int (-> vm evalSituation)])
2222 (set! (-> vm evalSituation) (SCM_INT_VALUE val))
2223 (return prev))])))
2224
2225 (define-enum SCM_VM_EXECUTING)
2226 (define-enum SCM_VM_LOADING)
2227 (define-enum SCM_VM_COMPILING)
2228
2229 ;; Compiler flags
2230 (define-cproc vm-compiler-flag-is-set? (flag::<uint>) ::<boolean>
2231 (return (SCM_VM_COMPILER_FLAG_IS_SET (Scm_VM) flag)))
2232 (define-cproc vm-compiler-flag-set! (flag::<uint>) ::<void>
2233 (SCM_VM_COMPILER_FLAG_SET (Scm_VM) flag))
2234 (define-cproc vm-compiler-flag-clear! (flag::<uint>) ::<void>
2235 (SCM_VM_COMPILER_FLAG_CLEAR (Scm_VM) flag))
2236 (define-cproc vm-compiler-flag () ::<uint>
2237 (return (-> (Scm_VM) compilerFlags)))
2238
2239 (define-cproc vm-compiler-flag-noinline-locals? () ::<boolean>
2240 (return (SCM_VM_COMPILER_FLAG_IS_SET (Scm_VM) SCM_COMPILE_NOINLINE_LOCALS)))
2241 (define-cproc vm-compiler-flag-no-post-inline? () ::<boolean>
2242 (return (SCM_VM_COMPILER_FLAG_IS_SET (Scm_VM) SCM_COMPILE_NO_POST_INLINE_OPT)))
2243 (define-cproc vm-compiler-flag-no-lifting? () ::<boolean>
2244 (return (SCM_VM_COMPILER_FLAG_IS_SET (Scm_VM) SCM_COMPILE_NO_LIFTING)))
2245
2246 (define-enum SCM_COMPILE_NOINLINE_GLOBALS)
2247 (define-enum SCM_COMPILE_NOINLINE_LOCALS)
2248 (define-enum SCM_COMPILE_NOINLINE_CONSTS)
2249 (define-enum SCM_COMPILE_NOINLINE_SETTERS)
2250 (define-enum SCM_COMPILE_NOINLINE_INLINER)
2251 (define-enum SCM_COMPILE_NOSOURCE)
2252 (define-enum SCM_COMPILE_SHOWRESULT)
2253 (define-enum SCM_COMPILE_NOCOMBINE)
2254 (define-enum SCM_COMPILE_NO_POST_INLINE_OPT)
2255 (define-enum SCM_COMPILE_NO_LIFTING)
2256 (define-enum SCM_COMPILE_INCLUDE_VERBOSE)
2257 (define-enum SCM_COMPILE_NOINLINE_SETTERS)
2258 (define-enum SCM_COMPILE_NODISSOLVE_APPLY)
2259 (define-enum SCM_COMPILE_LEGACY_DEFINE)
2260 (define-enum SCM_COMPILE_MUTABLE_LITERALS)
2261 (define-enum SCM_COMPILE_SRFI_FEATURE_ID)
2262
2263 ;; Set/get VM's current module info. (temporary)
2264 (define-cproc vm-current-module () (return (SCM_OBJ (-> (Scm_VM) module))))
2265 (define-cproc vm-set-current-module (mod::<module>) ::<void>
2266 (set! (-> (Scm_VM) module) mod))
2267 )
2268
2269 ;;============================================================
2270 ;; Initialization
2271 ;;
2272
2273 ;; This is called after all built-in procedures and compilers are
2274 ;; brought up. Remaining initializations are autoloads and cond-features.
2275 ;; We can put miscellaneous bookkeeping here. Be careful not to trigger
2276 ;; autoloads, for it requires the compiler being functional.
2277 (define (init-compiler)
2278 #f
2279 )
2280
2281 ;;============================================================
2282 ;; Dummy macros
2283 ;;
2284
2285 (select-module gauche)
2286
2287 (define-macro (%precomp-only . names)
2288 `(begin
2289 (declare (keep-private-macro ,@names))
2290 ,@(map (^[name]
2291 `(define-macro (,name . _)
2292 (warn "The ~a form can only be used for Scheme sources \
2293 to be pre-compiled. Since you're loading the file \
2294 ~s without pre-compilation, this form is ignored.\n"
2295 ',name (current-load-path))
2296 (undefined)))
2297 names)))
2298
2299 ;; Some forms are recognized by the AOT compiler (precomp), and
2300 ;; translated to C. They can't be evaluated at runtime, so
2301 ;; we have dummy macros to warn.
2302 (%precomp-only inline-stub
2303 in-module
2304 define-cproc
2305 define-cfn
2306 define-enum
2307 define-enum-conditionally)
2308
2309 ;; The form (declare ...) may be used in wider purpose. For the time
2310 ;; being we use it in limited purposes for compilers. In interpreter
2311 ;; we just ignore it.
2312 (declare (keep-private-macro declare))
2313 (define-macro (declare . _) #f)