Debian Codegraph @

test/optimize.scm

raw
1 ;; Test compiler's optimizing routines
2
3 (use gauche.test)
4 (use gauche.vm.insn)
5 (use scheme.list)
6 (use gauche.uvector)
7 (use util.match)
8
9 (define (proc->insn/split proc)
10 (let loop ([code ((with-module gauche.internal vm-code->list)
11 (closure-code proc))]
12 [acc '()])
13 (match code
14 [() (reverse acc)]
15 [((and (opcode . params) insn) . rest)
16 (let1 info (vm-find-insn-info opcode)
17 (ecase (~ info'operand-type)
18 [(none) (loop rest `((,insn) ,@acc))]
19 [(obj code codes label)
20 (loop (cdr rest) `((,insn ,(car rest)) ,@acc))]
21 [(obj+label obj+native)
22 (loop (cddr rest) `((,insn ,(car rest) ,(cadr rest)) ,@acc))]))])))
23
24 (define (filter-insn proc opcode)
25 (filter (^i (match i
26 [(([? (cut eq? <> opcode)] . _) . _) #t]
27 [_ #f]))
28 (proc->insn/split proc)))
29
30 (test-start "optimizer")
31
32 (test-section "inlining")
33
34 ;; Simple inlining
35 (define-inline (const4) 4)
36 (test* "inlining const4 + constant folding" '(((CONSTI 8)) ((RET)))
37 (proc->insn/split (^[] (+ (const4) (const4)))))
38
39 ;; Closed env (pass1/check-inlinable-lambda $LET branch)
40 (define-inline lambda-with-closed-env
41 (let ((h (make-hash-table 'eq?)))
42 (^k (hash-table-ref h k #f))))
43 (test* "inlining lambda with closed env" '(((GREF-PUSH) |transient id|)
44 ((CONST-PUSH) a)
45 ((CONSTF-PUSH))
46 ((GREF-TAIL-CALL 3) hash-table-ref)
47 ((RET)))
48 (map (^[insn]
49 (match insn
50 [(op (? wrapped-identifier? id))
51 (let1 name (unwrap-syntax id)
52 (if (symbol-interned? name)
53 `(,op ,name)
54 `(,op |transient id|)))]
55 [_ insn]))
56 (proc->insn/split (^[] (lambda-with-closed-env 'a)))))
57
58 ;; Combinatorial
59 (define-inline (make-adder n) (^m (+ n m)))
60 (define-inline add4 (make-adder 4))
61 (test* "inlining add4 + constant folding" '(((CONSTI 9)) ((RET)))
62 (proc->insn/split (^[] (+ (add4 2) 3))))
63
64 ;; pass1 setter inlining
65 (test* "inlining setter" '(((LREF1-PUSH)) ((LREF0)) ((VEC-SETI 0)) ((RET)))
66 (proc->insn/split (^[a b] (set! (vector-ref a 0) b))))
67 (test* "inlining setter" #t
68 (let1 xs (proc->insn/split (^[a b] (set! (car a) b)))
69 (or (any (^x (equal? (car x) '(GREF-TAIL-CALL 2))) xs)
70 xs))) ;return xs in case of failure for easier diag
71
72 ;; pass2/inline-tail-apply
73 (test* "inlining apply" '(((LREF0-PUSH)) ((LREF1)) ((CONS)) ((RET)))
74 (proc->insn/split (^[a b] (let1 xs `(,b ,a) (apply cons xs)))))
75 (test* "inlining apply" '(((LREF0-NUMADDI 1)) ((RET)))
76 (proc->insn/split (^[a] (let1 xs `(,a) (apply + 1 xs)))))
77 (test* "inlining apply" '(((CONSTI-PUSH 1)) ((CONSTI 2)) ((CONS)) ((RET)))
78 (proc->insn/split (^[] (let1 xs '(1 2) (apply cons xs)))))
79 (test* "inlining apply" '(((CONST-PUSH) :a) ((CONSTI 2)) ((CONS)) ((RET)))
80 (proc->insn/split (^[] (let1 xs '(2) (apply cons :a xs)))))
81
82 ;; This should give up apply inlining, for the content of xs may be
83 ;; altered when passed to a global function.
84 (test* "inlining apply (give up)"
85 '(((CONSTI 2)) ((LIST 1)) ((PUSH-LOCAL-ENV 1)) ((PRE-CALL 1) 8)
86 ((LREF0-PUSH)) ((GREF-CALL 1) foo)
87 ((GREF-PUSH) cons) ((CONSTI-PUSH 1)) ((LREF0)) ((TAIL-APPLY 3))
88 ((RET)))
89 (unwrap-syntax
90 (proc->insn/split
91 (^[] (let1 xs (list 2) (foo xs) (apply cons 1 xs))))))
92 ;; Similar to above, but if xs is constant, so we don't worry about mutation.
93 (test* "inlining apply (ok)"
94 '(((PRE-CALL 1) 6) ((CONST-PUSH) (2)) ((GREF-CALL 1) foo)
95 ((CONSTI-PUSH 1)) ((CONSTI 2)) ((CONS))
96 ((RET)))
97 (unwrap-syntax
98 (proc->insn/split
99 (^[] (let1 xs '(2) (foo xs) (apply cons 1 xs))))))
100 ;; This is the one that exhibits the bug in the issue
101 ;; https://github.com/shirok/Gauche/issues/685
102 (test* "inlining apply (give up)"
103 '(((CONST) a) ((LIST 1)) ((PUSH-LOCAL-ENV 1))
104 ((PRE-CALL 2) 10) ((LREF0-PUSH)) ((LREF0-PUSH))
105 ((GREF-CALL 2) set-cdr!)
106 ((GREF-PUSH) list) ((LREF0)) ((TAIL-APPLY 2)) ((RET)))
107 (unwrap-syntax
108 (proc->insn/split
109 (^[] (let ((x (list 'a)))
110 (set-cdr! x x)
111 (apply list x))))))
112
113 (define-inline (apply-inline-1 . args) (apply + 3 args))
114
115 (test* "inlining apply" '(((LREF2-NUMADDI 3))
116 ((LREF-VAL0-NUMADD2 0 1))
117 ((LREF-VAL0-NUMADD2 0 0))
118 ((RET)))
119 (proc->insn/split (^[a b c] (apply-inline-1 a b c))))
120
121 (test* "inlining apply (later stage)" '(((CONSTI-PUSH 5))
122 ((LREF2))
123 ((NUMMUL2))
124 ((PUSH))
125 ((LREF1))
126 ((NUMMUL2))
127 ((PUSH))
128 ((LREF0))
129 ((NUMMUL2))
130 ((RET)))
131 (proc->insn/split (^[a b c]
132 (define (f . args) (apply * 5 args))
133 (define xs (list a b c))
134 (apply f xs))))
135
136 ;; pass3/late-inline
137 (define-inline (late-inline-test-1 ref) (cut ref <> 0))
138
139 (test* "pass3/late-inline"
140 '(((LREF0)) ((VEC-REFI 0)) ((RET)))
141 (proc->insn/split (late-inline-test-1 vector-ref)))
142
143 (test* "pass3/late-inline"
144 '(((LREF0-PUSH)) ((CONSTI 0)) ((UVEC-REF 1)) ((RET)))
145 (proc->insn/split (late-inline-test-1 u8vector-ref)))
146
147
148 ;; pass3/receive
149 (test* "inlining receive-apply-values pattern" '(((LREF0-CAR))
150 ((PUSH-LOCAL-ENV 1))
151 ((PRE-CALL 1) 8)
152 ((CONST-PUSH) "foo")
153 ((GREF-CALL 1) print)
154 ((LREF0-RET)))
155 (unwrap-syntax (proc->insn/split (^x (begin0 (car x) (print "foo"))))))
156
157 ;; case-lambda inlining
158
159 (define-inline case-lambda-inline-test-1
160 (case-lambda
161 [(a) `(one ,a)]
162 [(a b) `(two ,a ,b)]
163 [(a b c d) `(four ,a ,b ,c ,d)]
164 [(a . as) 'other]))
165
166 (test* "inlining case-lambda 0" `(((GREF-TAIL-CALL 0) case-lambda-inline-test-1)
167 ((RET)))
168 (unwrap-syntax (proc->insn/split (^[] (case-lambda-inline-test-1)))))
169
170 (test* "inlining case-lambda 1" `(((CONST-PUSH) one)
171 ((CONST) x)
172 ((LIST 2))
173 ((RET)))
174 (proc->insn/split (^[] (case-lambda-inline-test-1 'x))))
175
176 (test* "inlining case-lambda 2" `(((CONST-PUSH) two)
177 ((CONST-PUSH) x)
178 ((CONST) y)
179 ((LIST 2))
180 ((CONS))
181 ((RET)))
182 (proc->insn/split (^[] (case-lambda-inline-test-1 'x 'y))))
183
184 (test* "inlining case-lambda 3" `(((CONST-RET) other))
185 (proc->insn/split (^[] (case-lambda-inline-test-1 'x 'y 'z))))
186
187 (test* "inlining case-lambda 4" `(((CONST-PUSH) four)
188 ((CONST-PUSH) x)
189 ((CONST-PUSH) y)
190 ((CONST-PUSH) z)
191 ((CONST) w)
192 ((LIST 2))
193 ((LIST-STAR 3))
194 ((CONS))
195 ((RET)))
196 (proc->insn/split (^[] (case-lambda-inline-test-1 'x 'y 'z 'w))))
197
198 (test* "inlining case-lambda many" `(((CONST-RET) other))
199 (proc->insn/split (^[] (case-lambda-inline-test-1 'x 'y 'z
200 'x 'y 'z
201 'x 'y 'z))))
202
203 (define-inline case-lambda-inline-test-2
204 (case-lambda
205 [() 'zero]
206 [(a) 'one]))
207
208 (test* "inlining case-lambda 2-1" `(((CONST-RET) one))
209 (proc->insn/split (^[] (case-lambda-inline-test-2 'x))))
210
211 (test* "inlining case-lambda 2-2" `(((CONST-PUSH) x)
212 ((CONST-PUSH) y)
213 ((GREF-TAIL-CALL 2) case-lambda-inline-test-2)
214 ((RET)))
215 (unwrap-syntax
216 (proc->insn/split (^[] (case-lambda-inline-test-2 'x 'y)))))
217
218 ;; This tests pass2 case-lambda inlining
219 (define (case-lambda-pass2-inline-1)
220 ((case-lambda [(x) (+ x x)] [(x y) (+ x y)]) 1))
221 (test* "inlining case-lambda in pass2 1-1" `(((CONSTI 2))
222 ((RET)))
223 (proc->insn/split case-lambda-pass2-inline-1))
224
225 (define (case-lambda-pass2-inline-2)
226 ((case-lambda [(x) (+ x x)] [(x y) (+ x y)]) 1 5))
227 (test* "inlining case-lambda in pass2 1-2" `(((CONSTI 6))
228 ((RET)))
229 (proc->insn/split case-lambda-pass2-inline-2))
230
231 (define (case-lambda-pass2-inline-0)
232 ((case-lambda [(x) (+ x x)] [(x y) (+ x y)])))
233 (test* "inlining case-lambda in pass2 1-0" 'make-case-lambda
234 (any (^[insn] (match insn
235 [(_ (? identifier? z)) (unwrap-syntax z)]
236 [_ #f]))
237 (proc->insn/split case-lambda-pass2-inline-0)))
238
239 (define (case-lambda-pass2-inline-3)
240 ((case-lambda [(x) (+ x x)] [(x y) (+ x y)]) 1 5 9))
241 (test* "inlining case-lambda in pass2 1-3" 'make-case-lambda
242 (any (^[insn] (match insn
243 [(_ (? identifier? z)) (unwrap-syntax z)]
244 [_ #f]))
245 (proc->insn/split case-lambda-pass2-inline-3)))
246
247 ;; getter-with-setter inlining
248 (define-inline (getter-setter-inline-1 x) (car x))
249 (define-inline (getter-setter-inline-1-set! x v) (set-car! x v))
250 (define-inline getter-setter-inline-2
251 (getter-with-setter getter-setter-inline-1 getter-setter-inline-1-set!))
252 (test* "inlining getter-with-setter-ed proc, global def, named, get"
253 '(((LREF0-CAR)) ((RET)))
254 (proc->insn/split (^x (getter-setter-inline-2 x))))
255 (test* "inlining getter-with-setter-ed proc, global def, named, set"
256 '(((LREF0-PUSH)) ((CONSTI-PUSH 2)) ((GREF-TAIL-CALL 2) set-car!) ((RET)))
257 (unwrap-syntax
258 (proc->insn/split (^x (set! (getter-setter-inline-2 x) 2)))))
259
260 (define-inline getter-setter-inline-3
261 (getter-with-setter (^x (cdr x))
262 (^[x v] (set-cdr! x v))))
263 (test* "inlining getter-with-setter-ed proc, global def, anon lambda, get"
264 '(((LREF0-CDR)) ((RET)))
265 (proc->insn/split (^x (getter-setter-inline-3 x))))
266 (test* "inlining getter-with-setter-ed proc, global def, anon-lambda, set"
267 '(((LREF0-PUSH)) ((CONSTI-PUSH 2)) ((GREF-TAIL-CALL 2) set-cdr!) ((RET)))
268 (unwrap-syntax
269 (proc->insn/split (^x (set! (getter-setter-inline-3 x) 2)))))
270
271
272
273 (test-section "lambda lifting")
274
275 ;; bug reported by teppey
276 (test* "pass4 lambda marking bug" #t
277 (begin ((with-module gauche.internal compile)
278 '(let loop () (values (^[] #f)) (loop))
279 (current-module))
280 #t))
281
282 ;; See if constant lambda won't make closures.
283 ;; The internal (^k (* k k)) should be lifted to the toplevel, so that
284 ;; there shouldn't be CLOSURE instruction.
285 (test* "lifting constant lambda" '()
286 (filter-insn (^(xs) (map (^k (* k k)) xs)) 'CLOSURE))
287
288 (test* "lifting constant lambda 2" '()
289 (filter-insn (^[] (let ([a (^[x r] (* x r))])
290 (let ([b (^[xs] (fold a '() xs))])
291 (f b))))
292 'CLOSURE))
293
294 ;; https://github.com/shirok/Gauche/issues/826
295 (test* "lifting with clambda" #t
296 (procedure?
297 (eval '(letrec
298 ((f (lambda (a.7 . rest.8)
299 (lambda rest.9
300 (apply (letrec ((h (case-lambda
301 (() h)
302 ((b.12 . rest.13)
303 (lambda rest.14
304 (apply (+ a.7 b.12)
305 rest.14))))))
306 h)
307 rest.9)))))
308 f)
309 (current-module))))
310
311 ;; See if constant lambda keeps identity.
312 ;; NB: This isn't a guaranteed behavior, but it holds in the
313 ;; current compiler, and there's no reason to lose it.
314 (define (make-constant-closure) (^[] #t))
315
316 (test* "constant closure identity" #t
317 (eq? (make-constant-closure) (make-constant-closure)))
318
319 (test-section "transformation")
320
321 ;; pass2 intermediate lref elimination
322 (test* "intermediate lref elimination 1" '()
323 (filter-insn (^[x] (let1 p (f a) (g x p 0))) 'PUSH-LOCAL-ENV))
324 (test* "intermediate lref elimination 2" '()
325 (filter-insn (^[x] (let ([p (f x a)] [q (g x b)]) (h p x q)))
326 'PUSH-LOCAL-ENV))
327 (test* "intermediate lref elimination 3" '(((PUSH-LOCAL-ENV 1)))
328 (filter-insn (^[x] (let1 p (f a) (g z p 0))) 'PUSH-LOCAL-ENV))
329 (test* "intermediate lref elimination 4" '(((PUSH-LOCAL-ENV 1)))
330 (filter-insn (^[x] (let1 p (f a) (g p (z) 0))) 'PUSH-LOCAL-ENV))
331 (test* "intermediate lref elimination 5" '(((PUSH-LOCAL-ENV 2)))
332 (filter-insn (^[x] (let ([p (f x a)] [q (g x b)]) (h p (r q))))
333 'PUSH-LOCAL-ENV))
334 (test* "intermediate lref elimination 6" '()
335 (filter-insn (^[x] (let* ([p (f x a)] [q (g x p)]) (h x q)))
336 'PUSH-LOCAL-ENV))
337 (test* "intermediate lref elimination 7" '(((PUSH-LOCAL-ENV 1)))
338 (filter-insn (^[x] (let* ([p (f x a)] [q (g x p)]) (h p q)))
339 'PUSH-LOCAL-ENV))
340 (test* "intermediate lref elimination 8" '()
341 (filter-insn (^(x) (let* ([p (f x a)] [q (g x p)] [r (h x q)]) (y r)))
342 'PUSH-LOCAL-ENV))
343
344 ;; Tests for optimizer bug fixed in 2546f82
345 (define-inline (foo p xs . xss)
346 (if (null? xss)
347 (let loop ([xs xs])
348 (unless (null? xs) (p (car xs)) (loop (cdr xs))))
349 (let loop ([xss (cons xs xss)])
350 (receive (cars cdrs) (extract-cars+cdrs xss)
351 (when cars
352 (apply p cars)
353 (loop cdrs))))))
354
355 (test* "make sure define-inline'd procs be optimized" '()
356 (filter-insn foo 'LOCAL-ENV-CLOSURES))
357
358 (test-section "eta reduction")
359
360 ;; This is actually to check when eta reductino isn't done
361 ;; when there's a hazard (side effects). 0.9.3.3 fails this.
362
363 (define (hoop f a) (f a))
364 (define (hoop2 x y) (list x y))
365
366 (test* "eta conversion hazard" '(9 3)
367 (let ((a 1))
368 (let ((b (hoop (^c (set! a 9) (+ c 1)) 2)))
369 (hoop2 a b))))
370
371 ;; This test exhibits a bug on inlining local function more than once.
372 ;; Fixed by commit dd7a023.
373 (test* "copy&inline local function" 'bam
374 (let ()
375 (define (call object message . args)
376 (unless (list? args)
377 (error "Strange arguments: "
378 `(call (object ,object) (message ,message) (args ,args))))
379 (and-let* ((it (object message)))
380 (apply it object args)))
381
382 (define (foo)
383 (define (bar) (lambda _ (lambda _2 'bam)))
384
385 (define (baz x) (call x 'baz))
386 (define (baz2 x) (call x 'baz))
387
388 (define (test x) (baz x))
389 (define (test2 x) (baz x))
390 (test (bar)))
391 (foo)))
392
393 ;; This test exhibits a bug on inlining a procedure within the same
394 ;; compilation unit. Fixed by commit 43b479fb0.
395 (test* "inlining procedure in the same compilation unit"
396 #f
397 (let ((m (make-module #f)))
398 ;; If foo is inline-expanded, gref to foo won't remain.
399 (define (reference-to-foo? opcode)
400 (and (wrapped-identifier? opcode)
401 (eq? (identifier->symbol opcode) 'foo)))
402
403 (eval '(begin
404 (define-inline (foo x) (pair? x))
405 (define (bar y) (foo (car y))))
406 m)
407 (find
408 (^[insn]
409 (match insn
410 [(_ (? reference-to-foo? x)) #t]
411 [_ #f]))
412 (proc->insn/split (module-binding-ref m 'bar)))))
413
414 ;; generic function pre-dispatch
415 ;; NB: We're still not sure how to expose this feature in general.
416 ;; For the time being, we test the inlining logic (it's in pass 3)
417 ;; with the hand-wired setting. Don't copy this way to your production code.
418 (define-inline static-gf (make <generic> :name 'static-gf))
419 (define-method static-gf :locked ((x <string>)) 'string)
420 (define-method static-gf :locked ((x <number>)) 'number)
421 ((with-module gauche.object generic-seal!) static-gf)
422
423 (test* "generic function pre-dispatch"
424 '(((CONST-RET) string))
425 (proc->insn/split (^[] (static-gf "abc"))))
426 (test* "generic function pre-dispatch"
427 '(((CONST-RET) number))
428 (proc->insn/split (^[] (static-gf 123))))
429
430 (test-end)