Debian Codegraph @

src/geninsn

raw
1 ;;;
2 ;;; geninsn - generate VM instruction related files
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 ;; Generate the following VM instruction related files from vminsn.scm
35 ;; vminsn.c
36 ;; gauche/vminsn.h
37 ;; ../lib/gauche/vm/insn.scm
38
39 (use file.util)
40 (use gauche.cgen)
41 (use gauche.mop.instance-pool)
42 (use gauche.parseopt)
43 (use gauche.sequence)
44 (use gauche.vm.insn-core)
45 (use srfi.13)
46 (use text.tr)
47 (use util.match)
48
49 (define (c-insn-name name)
50 (string-append "SCM_VM_" (string-tr (x->string name) "-" "_")))
51
52 (define *preamble*
53 (list "/* Generated automatically from vminsn.scm */"
54 "/* DO NOT EDIT */"))
55
56 (define *unit*
57 (make <cgen-unit>
58 :name "vminsn"
59 :preamble *preamble*
60 :c-file "vminsn.c"
61 :h-file "gauche/vminsn.h"
62 :init-prologue ""
63 :init-epilogue ""
64 ))
65
66 ;; Instructon information
67 (define (find-insn name insns)
68 (find (^_ (eq? name (~ _'name))) insns))
69
70 ;; LREF shortcuts.
71 (define-constant .lrefx.
72 '(LREF0 LREF1 LREF2 LREF3 LREF10 LREF11 LREF12 LREF20 LREF21 LREF30))
73
74 ;;=============================================================
75 ;; Generate gauche.vm.insn
76 ;; We have a header in ../lib/gauche/vm/insn.scm.src.
77 ;;
78
79 (define (gen-gauche.vm.insn insns)
80 (define (write-header)
81 (format #t ";; Generated from vminsn.scm. DO NOT EDIT\n")
82 (write '(define-module gauche.vm.insn (extend gauche.vm.insn-core)))
83 (newline)
84 (write '(select-module gauche.vm.insn))
85 (newline))
86 (define (write-insn insn)
87 (format #t ";; #x~3,'0x ~a\n" (~ insn'code) (~ insn'name))
88 (format #t "(make <vm-insn-info> :name '~a :code ~a\n"
89 (~ insn'name) (~ insn'code))
90 (format #t " :num-params ~a :alt-num-params '~a\n"
91 (~ insn'num-params) (~ insn'alt-num-params))
92 (format #t " :operand-type '~a\n" (~ insn'operand-type))
93 (format #t " :obsoleted ~s\n" (~ insn'obsoleted))
94 (format #t " :multi-value ~s\n" (~ insn'multi-value))
95 (format #t " :fold-lref ~s\n" (~ insn'fold-lref))
96 (format #t " :combined '~s\n" (~ insn'combined))
97 (format #t " :body '~s)\n\n" (~ insn'body)))
98 (make-directory* "../lib/gauche/vm")
99 (with-output-to-file "../lib/gauche/vm/insn.scm"
100 (^[]
101 (write-header)
102 (for-each write-insn insns)
103 (newline))
104 :if-exists :supersede)
105 )
106
107 ;;=============================================================
108 ;; Generate VM inner loop
109 ;;
110
111 ;; These parameters are used by the cise expander defined in
112 ;; vminsn.scm.
113 (define result-type (make-parameter 'reg)) ;reg, push, call or ret
114 (define arg-source (make-parameter #f)) ;#f, pop, reg, lref,
115 ; or (lref DEPTH OFFSET)
116 (define insn-alist (make-parameter '())) ;target insn alist, used to
117 ; communicate to cise expander.
118
119 (define (construct-vmbody insns)
120 (define (case-label insn)
121 (cgen-body (format "\nlabel_~a~:*:\nCASE(SCM_VM_~a) "
122 (cgen-safe-name-friendly (x->string (~ insn'name))))))
123 (define (base-cise base)
124 (and-let* [(base-insn (find-insn base insns))]
125 (~ base-insn'body)))
126 (define (symbol-join syms)
127 ($ string->symbol $ string-join (map x->string syms) "-"))
128 (define (cise->string cise)
129 (call-with-output-string (cut cise-render cise <>)))
130 (define (lrefx->lref lrefx)
131 (rxmatch-let (#/LREF(\d)?(\d)/ (x->string lrefx))
132 (#f dep off)
133 `(lref ,(x->integer dep) ,(x->integer off))))
134 (define (render cise) (cgen-body #"{~(cise->string cise)}") #t)
135 (define (do-combined orig comb)
136 (match comb
137 [(base 'PUSH)
138 (and-let* ([cise (base-cise base)])
139 (parameterize ([result-type 'push]) (render cise)))]
140 [(base 'RET)
141 (and-let* ([cise (base-cise base)])
142 (parameterize ([result-type 'ret]) (render cise)))]
143 [(base (and (or 'CALL 'TAIL-CALL) next))
144 (and-let* ([cise (base-cise base)])
145 (parameterize ([result-type 'call]) (render cise))
146 (render `($goto-insn ,next)))]
147 [('PUSH . next)
148 (render `(PUSH-ARG VAL0))
149 (render `($goto-insn ,(symbol-join next)))]
150 [('LREF0 'PUSH . next)
151 (render `(let* ((v (ENV-DATA ENV 0))) (PUSH-ARG v)))
152 (render `($goto-insn ,(symbol-join next)))]
153 [((and (? (cut memq <> .lrefx.)) lrefx) . next)
154 (parameterize ([arg-source (lrefx->lref lrefx)])
155 (do-combined-rec orig next))]
156 [('LREF . next)
157 (parameterize ([arg-source 'lref]) (do-combined-rec orig next))]
158 [_ #f]))
159 (define (do-combined-rec orig comb)
160 (or (and-let* ([insn (find-insn (symbol-join comb) insns)]) (render1 insn))
161 (do-combined orig comb)
162 (warn "Don't know how to generate combined insn ~a" (~ orig'name))))
163 (define (render1 insn)
164 (or (and-let* ([cise (~ insn'body)]) (render cise))
165 (and-let* ([comb (~ insn'combined)]) (do-combined insn comb))
166 (warn "Don't know how to generate ~a" (~ insn'name))))
167
168 ;; main body of construct-vmbody
169 (parameterize ([insn-alist (map (^_(cons (~ _'name) _)) insns)])
170 (dolist [insn insns]
171 (case-label insn)
172 (render1 insn))))
173
174 ;;==============================================================
175 ;; Emit state-transition table for instruction combiner
176 ;; The state transition table is basically a DFA, but we have some
177 ;; tweaks to keep the size of the tables small.
178 ;;
179 ;; Each state is represented by a table, keyed by input insn codes.
180 ;; Each value indicates an action and the next state.
181 ;;
182 ;; In the following description, we denote a table as [something],
183 ;; and the input code as (something), and the output as {something}.
184 ;;
185 ;; Actions:
186 ;; NEXT - output nothing, merely replaces the current state to the
187 ;; next state.
188 ;; EMIT - emit the specified insn(s), consuming the input, return
189 ;; to the state 0.
190 ;; KEEP - emit the specified insn, keep other pending insns and
191 ;; input, then run DFA on the pending input.
192
193 (define-class <state> (<instance-pool-mixin>)
194 ((name :init-keyword :name)
195 (transitions :init-value '()) ;; alist of (insn-name . <arc>)
196 (index) ;; table #
197 (entry-index) ;; an index of the entry array
198 ;; that indicates the first entry
199 ;; of this state.
200 (index-count :allocation :class :init-value 0)
201 ))
202
203 (define-method write-object ((s <state>) out)
204 (format out "#<state ~a ~a>" (~ s'index) (~ s'name)))
205
206 ;; A transitional arc. stop-insn is used to hold intermediate value
207 ;; during STN creation.
208 (define-class <arc> ()
209 ((input :init-keyword :input)
210 (next-state :init-keyword :next-state :init-value #f)
211 (stop-insn :init-keyword :stop-insn :init-value #f)
212 (command :init-keyword :command :init-value #f)))
213
214 (define-method initialize ((s <state>) initargs)
215 (next-method)
216 (set! (~ s'index) (~ s'index-count))
217 (inc! (~ s'index-count)))
218
219 (define (make-state name) (make <state> :name name))
220
221 (define (state-lookup state insn-name)
222 (assq-ref (~ state'transitions) insn-name))
223
224 (define (state-set-insn! state insn-name stop-insn)
225 (if-let1 arc (state-lookup state insn-name)
226 (set! (~ arc'stop-insn) stop-insn)
227 (push! (~ state'transitions)
228 (cons insn-name
229 (make <arc> :input insn-name :stop-insn stop-insn)))))
230
231 (define (state-set-state! state insn-name next-state)
232 (if-let1 arc (state-lookup state insn-name)
233 (set! (~ arc'next-state) next-state)
234 (push! (~ state'transitions)
235 (cons insn-name
236 (make <arc> :input insn-name :next-state next-state)))))
237
238 ;; Add one insn to a state network.
239 ;; If an insn is marked 'obsoleted', we add it to the root insn anyway but
240 ;; do not process combinations. Addition for the root is ncessary since
241 ;; the initial lookup of the state transition table is done by insn code,
242 ;; so we need a placeholder for obsoleted insns.
243 ;; Note: We assume that combined insn is always added after the base
244 ;; insn is added (e.g. LREF_something should be added after LREF). It
245 ;; keeps the invariance that the root node has insns in the same order
246 ;; as defined.
247 ;; TODO: Would help if we have a mechanism to report an error if such
248 ;; placeholder insn is actually kicked.
249 (define (add-insn-to-state! root-state insn)
250
251 (define (substate state name)
252 (or (and-let* ([arc (state-lookup state name)])
253 (~ arc'next-state))
254 (rlet1 newstate (make-state `(,@(~ state'name) ,name))
255 (state-set-state! state name newstate))))
256
257 (state-set-insn! root-state (~ insn'name) insn)
258 (when (and (pair? (~ insn'combined))
259 (not (~ insn'obsoleted)))
260 (let loop ([combined (~ insn'combined)]
261 [state root-state])
262 (cond [(null? (cdr combined))
263 (state-set-insn! state (car combined) insn)]
264 [(and (~ insn'fold-lref) (eq? (car combined) 'LREF))
265 (loop (cdr combined) (substate state 'LREF))
266 (dolist [lref .lrefx.]
267 (loop (cdr combined) (substate state lref)))]
268 [else
269 (loop (cdr combined) (substate state (car combined)))]))))
270
271 ;; The second path to fixup the STN. Assign each arc a command.
272 (define (fixup-states! root-state)
273 (define state-entry-index 0)
274
275 (define (fixup1 state pending)
276 (unless (eq? state root-state)
277 (push! (~ state'transitions) (cons #f (make <arc> :input #f))))
278 (set! (~ state'entry-index) state-entry-index)
279 (inc! state-entry-index (length (~ state'transitions)))
280 (dolist [transition (~ state'transitions)]
281 (let* ([arc (cdr transition)]
282 [si (~ arc'stop-insn)]
283 [ns (~ arc'next-state)])
284 (cond
285 [(and si (not ns))
286 (set! (~ arc'command) `(reset ,(~ si'name)))
287 (set! (~ arc'next-state) root-state)]
288 [(and si ns)
289 (set! (~ arc'command) `(next ,ns))
290 (fixup1 ns (list (~ si'name)))]
291 [(and (not si) ns)
292 (set! (~ arc'command) `(next ,ns))
293 (fixup1 ns (cons (~ arc'input) pending))]
294 [else
295 (set! (~ arc'command) `(keep ,@(reverse pending)))
296 (set! (~ arc'next-state) root-state)])))
297 (update! (~ state'transitions) reverse!))
298
299 (fixup1 root-state '()))
300
301 ;; Emit the state table.
302 (define (emit-states states)
303
304 (define entry-count 0)
305
306 (dolist [s (sort-by states (cut ref <> 'entry-index) <)]
307 (cgen-body #"/* State #~(~ s'index) ~(~ s'name) [~(~ s'entry-index)] */")
308 (dolist [t (~ s'transitions)]
309 (match-let1 (op . args) (~ (cdr t)'command)
310 (receive (action operand)
311 (case op
312 [(next) (values 'NEXT (~ (car args)'entry-index))]
313 [(reset) (values 'EMIT (c-insn-name (car args)))]
314 [(keep) (if (null? (cdr args))
315 (values 'KEEP (c-insn-name (car args)))
316 (error "huh?"))])
317 (cgen-body
318 (format " /*~3d*/ { ~a, ~a, ~a },"
319 entry-count
320 (cond [(~ (cdr t)'input) => c-insn-name] [else -1])
321 action
322 operand))))
323 (inc! entry-count)))
324 )
325
326 (define (construct-state-table insns)
327 (let1 root (make-state '())
328 (for-each (cut add-insn-to-state! root <>) insns)
329 (fixup-states! root)
330 (emit-states (instance-pool->list <state>))))
331
332 ;;==============================================================
333 ;; Parse vminsn.scm and returns the define-insn form in order.
334 ;; CISE definitions are evaluated within the current context.
335 ;;
336 (define (expand-toplevels file)
337 (define (lref-replace form lrefx)
338 (match form
339 [(syms ...) (map (cut lref-replace <> lrefx) syms)]
340 [symbol ($ string->symbol
341 $ regexp-replace #/\bLREF\b/ (x->string symbol)
342 $ x->string lrefx)]))
343 (define (generate-lrefx insn nparams operand comb seed)
344 (fold (^[lrefx seed]
345 `((define-insn ,(lref-replace insn lrefx) ,nparams ,operand
346 ,(lref-replace comb lrefx))
347 ,@seed))
348 seed .lrefx.))
349 (fold (^[form seed]
350 (match form
351 [('define-insn . _) (cons form seed)]
352 ;; Special expansion for LREF shortcuts.
353 ;; define-insn-lref* generates all variations of LREFn
354 ;; from the insn, plus the generic LREF version.
355 ;; define-insn-lref+ generates all variations of LREFn
356 ;; but not the generic LREF version (if the combined insn
357 ;; uses insn parameters, we can't use generic LREF that also
358 ;; uses insn parameters.)
359 [('define-insn-lref* insn nparams operand comb)
360 (generate-lrefx insn 0 operand comb
361 `((define-insn ,insn 2 ,operand ,comb)
362 ,@seed))]
363 [('define-insn-lref+ insn nparams operand comb)
364 (generate-lrefx insn nparams operand comb seed)]
365 [('define-cise-stmt . _) (eval form (current-module)) seed]
366 [else (error "Invalid form in vm instruction definition:"form)]))
367 '()
368 (file->sexp-list file)))
369
370 ;;
371 ;; Parse a single define-insn form
372 ;;
373 (define (parse-define-insn definsn)
374 (match definsn
375 [(_ name num-params operand-type . opts)
376 (let-optionals* opts ([combined #f]
377 [body #f]
378 . flags)
379 (make <vm-insn-info>
380 :name name
381 :num-params (if (pair? num-params) (car num-params) num-params)
382 :alt-num-params (if (pair? num-params) (cdr num-params) '())
383 :operand-type operand-type :combined combined
384 :body body
385 :obsoleted (boolean (memq :obsoleted flags))
386 :multi-value (boolean (memq :multi-value flags))
387 :fold-lref (boolean (memq :fold-lref flags))))]
388 [else (errorf "unrecognized define-insn form: ~s" definsn)]))
389
390 ;; opcmap :: ((NAME . CODE) ...)
391 (define (assign-opcode! insns opcmap)
392 (define code (find-max (map cdr opcmap) :default -1))
393 (dolist [insn insns]
394 (if-let1 c (assq-ref opcmap (~ insn'name))
395 (set! (~ insn'code) c)
396 (begin
397 (inc! code)
398 (set! (~ insn'code) code)))))
399
400 ;;
401 ;; From S-expr of define-insns, create <vm-insn-info> instances
402 ;; and make necessary wiring.
403 ;;
404 (define (populate-insn-info definsns opcmap)
405 (let1 insns (map parse-define-insn definsns)
406 (assign-opcode! insns opcmap)
407 ;; Set up insn relationships
408 (dolist [insn insns]
409 (and-let* ([comb (~ insn'combined)])
410 (define (wire suffix slot)
411 (let* ([basename (string->symbol
412 (rxmatch->string (string->regexp #"^(.*)-~suffix")
413 (x->string (~ insn'name))))]
414 [baseinsn (find (^_ (eq? (~ _'name) basename)) insns)])
415 (set! (~ baseinsn slot) insn)
416 (set! (~ insn'base-variant) baseinsn)))
417
418 (case (car (last-pair comb))
419 [(PUSH) (wire "PUSH" 'push-variant)]
420 [(RET) (wire "RET" 'ret-variant)])))
421 (sort-by insns (cut ~ <> 'code))))
422
423 ;;
424 ;; opcode map
425 ;;
426 (define (read-opcmap opcmap)
427 (if-let1 p (and opcmap (open-input-file opcmap :if-does-not-exist #f))
428 (begin0 (port->sexp-list p) (close-port p))
429 '()))
430
431 (define (gen-opcmap insns)
432 (print ";; VM instruction name to opcode map")
433 (print ";; To regenerate this, run 'make generate-opcode-map'")
434 (print)
435 (dolist [insn insns]
436 (format #t "(~s . ~s)\n" (~ insn'name) (~ insn'code)))
437 )
438
439 ;;
440 ;; Operations
441 ;;
442 (define (generate vminsn.scm opcmap.scm opcmap.out)
443 (parameterize ([cgen-current-unit *unit*])
444 (let1 insns (populate-insn-info (reverse (expand-toplevels vminsn.scm))
445 (read-opcmap opcmap.scm))
446 ;; Generate insn names and DEFINSN macros
447 (cgen-extern "enum {")
448 (cgen-body "#ifdef DEFINSN")
449 (dolist [insn insns]
450 (cgen-extern #" ~(c-insn-name (~ insn'name)) = ~(~ insn'code),")
451 (cgen-body (format "DEFINSN(~a, \"~a\", ~a, ~a, ~a)"
452 (c-insn-name (~ insn'name)) (~ insn'name)
453 (~ insn'num-params)
454 (string-tr (x->string (~ insn'operand-type))
455 "a-z+-" "A-Z__")
456 (string-join
457 (cond-list
458 [(~ insn'obsoleted) "SCM_VM_INSN_OBSOLETED"]
459 [(~ insn'fold-lref) "SCM_VM_INSN_FOLD_LREF"]
460 [#t "0"])
461 "|")
462 )))
463 (cgen-extern " SCM_VM_NUM_INSNS" "};")
464 (cgen-body "#endif /*DEFINSN*/")
465
466 ;; Generate insn combination state table
467 (cgen-body "#ifdef STATE_TABLE")
468 (construct-state-table insns)
469 (cgen-body "#endif /*STATE_TABLE*/")
470
471 ;; Generate vmloop body
472 (cgen-body "#ifdef VMLOOP")
473 (construct-vmbody insns)
474 (cgen-body "#endif /*VMLOOP*/")
475
476 ;; Write files
477 (cgen-emit-h (cgen-current-unit))
478 (cgen-emit-c (cgen-current-unit))
479 (gen-gauche.vm.insn insns)
480 (when opcmap.out
481 (with-output-to-file opcmap.out
482 (cut gen-opcmap insns)))
483 )))
484
485 ;;
486 ;; Main
487 ;;
488 (define (main args)
489 (let-args (cdr args) ([vminsn.scm "vminsn=s" "vminsn.scm"]
490 [opcmap.scm "opcode-map=s" #f]
491 [opcmap.out "gen-opcode-map=s" #f])
492 (generate vminsn.scm opcmap.scm opcmap.out))
493 0)
494
495 ;; Local variables:
496 ;; mode: scheme
497 ;; end: