| 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 |
) |