Debian Codegraph @

src/compile-0.scm

raw
1 ;;;
2 ;;; compile-0.scm - Utility macros for 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 ;;;
35 ;;; Utility macros used in the main compiler.
36 ;;;
37
38 (declare (keep-private-macro case/unquote generate-dispatch-table))
39
40 ;; NB: This file may be included from more than one file, so be careful
41 ;; to put only macro definitions.
42
43 ;; Defines a bunch of constants, and the alist to map name to value.
44 (define-macro (define-enum name . syms)
45 (let1 alist '()
46 `(begin
47 ,@(let loop ((syms syms) (i 0))
48 (if (null? syms)
49 '()
50 (begin
51 (push! alist (cons (car syms) i))
52 (cons `(define-constant ,(car syms) ,i)
53 (loop (cdr syms) (+ i 1))))))
54 (define-constant ,name ',(reverse alist)))))
55
56 ;; We use integers, instead of symbols, as tags, for it allows
57 ;; us to use jump table rather than 'case'.
58 ;; This macro allows us to use symbolic constants instead of
59 ;; the actual integers.
60 (define-macro (case/unquote obj . clauses)
61 (let1 tmp (gensym)
62 (define (expand-clause clause)
63 (match clause
64 [((item) . body)
65 `((eqv? ,tmp ,item) ,@body)]
66 [((item ...) . body)
67 (let1 ilist (list 'quasiquote
68 (map (cut list 'unquote <>) item))
69 `((memv ,tmp ,ilist) ,@body))]
70 [('else . body)
71 `(else ,@body)]))
72 `(let ((,tmp ,obj))
73 (cond ,@(map expand-clause clauses)))))
74
75 ;; Similar to case/unquote, but this turns each clause into a
76 ;; toplevel procedure and use jump vector, which is more efficient.
77 ;; TODO: In future, we might want to compile case into jump vector
78 ;; if the range of values are close together. Once we have it,
79 ;; we may no longer need this hack.
80 ;;
81 ;; ex. (define/case (foo iform y z)
82 ;; (iform-tag iform)
83 ;; [($DEFINE) expr ...]
84 ;; ...)
85 ;; =>
86 ;; (define-inline (foo iform y z)
87 ;; ((vector-ref *foo-dispatch-table* (iform-tag iform)) iform y z))
88 ;;
89 ;; (define (foo/$DEFINE iform y z) expr ...)
90 ;; ...
91 ;; (define *foo-dispatch-table* (generate-dispatch-table foo))
92 (define-macro (define/case proc dispatch-expr . clauses)
93 (define (generate-handler key clause)
94 (let1 name (string->symbol #"~(car proc)/~key")
95 `(define (,name ,@(cdr proc)) ,@clause)))
96 (define (find-clause key)
97 (if-let1 c (find (^c (memq key (car c))) clauses)
98 (cdr c)
99 (if-let1 c (assq 'else clauses)
100 (cdr c)
101 (errorf "No dispatch clause for ~a found during expanding ~a"
102 key proc))))
103 (define dispatch-table (string->symbol #"*~(car proc)-dispatch-table*"))
104
105 `(begin
106 (define-inline ,proc
107 ((vector-ref ,dispatch-table ,dispatch-expr) ,@(cdr proc)))
108 ,@(map (^t (generate-handler (car t) (find-clause (car t))))
109 .intermediate-tags.)
110 (define ,dispatch-table
111 (vector ,@(map (^t (string->symbol #"~(car proc)/~(car t)"))
112 .intermediate-tags.)))))
113
114 ;; Inlining map. Combined with closure optimization, we can avoid
115 ;; closure creation if we inline map call.
116 ;; We once tried inlining map calls automatically, and found the
117 ;; performance gain in general wasn't significant to justify the
118 ;; amount of increase of the code.
119 ;; However, it is worth to do in performance critical path.
120 ;; NB: proc is evaluated every iteration. Intended it to be a lambda form,
121 ;; so that its call is inlined.
122
123 (define-macro (imap proc lis)
124 (match proc
125 [('cut p '<> c) `(%map1c ,p ,lis ,c)]
126 [('cut p '<> c1 c2) `(%map1cc ,p ,lis ,c1 ,c2)]
127 ['make-lvar+ `(%map-make-lvar ,lis)]
128 [((or 'lambda '^) . _)
129 (let ([p (gensym)] [r (gensym)] [loop (gensym)])
130 `(let ,loop ((,r '()) (,p ,lis))
131 (if (null? ,p)
132 (reverse ,r)
133 (,loop (cons (,proc (car ,p)) ,r) (cdr ,p)))))]
134 [else `(map ,proc ,lis)]))
135
136 (define-macro (imap2 proc lis1 lis2)
137 (let ([p1 (gensym)] [p2 (gensym)] [r (gensym)] [loop (gensym)])
138 `(let ,loop ((,r '()) (,p1 ,lis1) (,p2 ,lis2))
139 (if (null? ,p1)
140 (reverse ,r)
141 (,loop (cons (,proc (car ,p1) (car ,p2)) ,r) (cdr ,p1) (cdr ,p2))))))
142
143 (define-macro (ifor-each proc lis)
144 (let ([p (gensym)] [loop (gensym)])
145 `(let ,loop ((,p ,lis))
146 (unless (null? ,p) (,proc (car ,p)) (,loop (cdr ,p))))))
147
148 (define-macro (ifor-each2 proc lis1 lis2)
149 (let ([p1 (gensym)] [p2 (gensym)] [loop (gensym)])
150 `(let ,loop ((,p1 ,lis1) (,p2 ,lis2))
151 (unless (null? ,p1)
152 (,proc (car ,p1) (car ,p2))
153 (,loop (cdr ,p1) (cdr ,p2))))))
154
155 ;; Inlining max
156 ;; We only compare unsigned integers (in Pass 5), so we use the specialized
157 ;; version of max.
158 (define-macro (imax x y . more)
159 (if (null? more)
160 `(%imax ,x ,y)
161 `(%imax ,x (imax ,y ,@more))))
162
163 ;; Generate dispatch table
164 (define-macro (generate-dispatch-table prefix)
165 `(vector ,@(map (lambda (p) (string->symbol #"~|prefix|/~(car p)"))
166 .intermediate-tags.)))
167
168
169 ;; Vector-as-struct
170 ;;
171 ;; We use a simple vector and manually defined accessors/modifiers,
172 ;; since vector-{ref|set!} is very fast in Gauche. We will rewrite
173 ;; the simple-minded define-simple-struct macro with gauche.record
174 ;; once we can compile vector-backed record efficiently.
175
176 ;; Macro define-simple-struct creates a bunch of functions and macros
177 ;; to emulate a structure by a vector.
178 ;; NAME is a symbol to name the structure type. TAG is some value
179 ;; (usually a symbol or an integer) to indicate the type of the
180 ;; structure.
181 ;;
182 ;; (define-simple-struct <name> <tag> <constructor> [(<slot-spec>*)])
183 ;;
184 ;; <constructor> : <symbol> | #f
185 ;; <slot-spec> : <slot-name> | (<slot-name> [<init-value>])
186 ;;
187 ;; For each <slot-spec>, the following accessor/modifier are automatically
188 ;; generated.
189 ;;
190 ;; NAME-SLOT - accessor (macro)
191 ;; NAME-SLOT-set! - modifier (macro)
192 ;; NAME-SLOT-offset - a macro that expands into the offset of the slot
193 ;;
194 ;; The following two CiSE expression is also defined.
195 ;;
196 ;; NAME-SLOT-offset - expands into the integer offset of the slot
197 ;; NAME-size - expands into the integer size of the offset.
198 ;;
199 ;; The *-offset and *-size macros/cise-exprs takes the tag into account.
200 ;;
201 ;; If a symbol is given as <constructor>, it becomes a macro to construct
202 ;; the structure. It can take zero to as many arguments as the # of slots.
203 ;; The arguments to the constructor initializes the slots in the order of
204 ;; their appearance in define-simple-struct. If not enough arguments are
205 ;; given to the constructor, the rest of slots are initialized by each
206 ;; <init-value> (or #f if <init-value> is omitted).
207
208 (define-macro (define-simple-struct name tag constructor :optional (slot-defs '()))
209 (define (take l n) ; we can't use SRFI-1 take, so here it is.
210 (if (zero? n) '() (cons (car l) (take (cdr l) (- n 1)))))
211 (define (make-constructor)
212 (let ([args (gensym)]
213 [num-slots (length slot-defs)]
214 [slot-names (map (^[s] (if (symbol? s) s (car s))) slot-defs)]
215 [init-vals (map (^[s] (if (symbol? s) #f (cadr s))) slot-defs)])
216 `(define-macro (,constructor . ,args)
217 (match ,args
218 ,@(let loop ((n 0)
219 (r '()))
220 (if (> n num-slots)
221 r
222 (let1 carg (take slot-names n)
223 (loop (+ n 1)
224 (cons
225 `(,carg
226 (list 'vector
227 ,@(if tag `(',tag) '())
228 ,@carg
229 ,@(map (cut list 'quote <>)
230 (list-tail init-vals n))))
231 r)))
232 ))))
233 ))
234 `(begin
235 ,@(if constructor
236 `((declare (keep-private-macro ,constructor))
237 ,(make-constructor))
238 '())
239 ,@(let loop ((s slot-defs) (i (if tag 1 0)) (r '()))
240 (if (null? s)
241 (reverse r `((inline-stub
242 (define-cise-expr ,(string->symbol #"~|name|-size")
243 [(_) ,i]))))
244 (let* ([slot-name (if (pair? (car s)) (caar s) (car s))]
245 [acc (string->symbol #"~|name|-~|slot-name|")]
246 [mod (string->symbol #"~|name|-~|slot-name|-set!")]
247 [off (string->symbol #"~|name|-~|slot-name|-offset")])
248 (loop (cdr s)
249 (+ i 1)
250 (list*
251 `(define-macro (,acc obj)
252 `(vector-ref ,obj ,,i))
253 `(define-macro (,mod obj val)
254 `(vector-set! ,obj ,,i ,val))
255 `(define-macro (,off) ,i)
256 `(inline-stub
257 (define-cise-expr ,off
258 [(_) ,i]))
259 `(declare (keep-private-macro ,acc ,mod ,off))
260 r))))))
261 )