1 ;;;; tree-il.test --- test suite for compiling tree-il -*- scheme -*-
2 ;;;; Andy Wingo <wingo@pobox.com> --- May 2009
4 ;;;; Copyright (C) 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
6 ;;;; This library is free software; you can redistribute it and/or
7 ;;;; modify it under the terms of the GNU Lesser General Public
8 ;;;; License as published by the Free Software Foundation; either
9 ;;;; version 3 of the License, or (at your option) any later version.
11 ;;;; This library is distributed in the hope that it will be useful,
12 ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ;;;; Lesser General Public License for more details.
16 ;;;; You should have received a copy of the GNU Lesser General Public
17 ;;;; License along with this library; if not, write to the Free Software
18 ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 (define-module (test-suite tree-il)
21 #:use-module (test-suite lib)
22 #:use-module (system base compile)
23 #:use-module (system base pmatch)
24 #:use-module (system base message)
25 #:use-module (language tree-il)
26 #:use-module (language tree-il primitives)
27 #:use-module (language glil)
28 #:use-module (srfi srfi-13))
31 ;; The partial evaluator.
32 (@@ (language tree-il optimize) peval))
34 (define-syntax pass-if-peval
35 (syntax-rules (resolve-primitives)
40 (compile 'in #:from 'scheme #:to 'tree-il)
44 (let ((evaled (unparse-tree-il (peval code))))
47 (_ (pk 'peval-mismatch)
48 ((@ (ice-9 pretty-print) pretty-print)
51 ((@ (ice-9 pretty-print) pretty-print)
54 ((@ (ice-9 pretty-print) pretty-print)
60 (with-test-prefix "partial evaluation"
63 ;; First order, primitive.
64 (let ((x 1) (y 2)) (+ x y))
68 ;; First order, thunk.
70 (let ((f (lambda () (+ x y))))
75 ;; First order, let-values (requires primitive expansion for
76 ;; `call-with-values'.)
79 (lambda () (if (zero? x) (values 1 2) (values 3 4)))
85 ;; First order, multiple values.
88 (primcall values (const 1) (const 2)))
91 ;; First order, multiple values truncated.
92 (let ((x (values 1 'a)) (y 2))
94 (primcall values (const 1) (const 2)))
97 ;; First order, multiple values truncated.
102 ;; First order, coalesced, mutability preserved.
103 (cons 0 (cons 1 (cons 2 (list 3 4 5))))
105 (const 0) (const 1) (const 2) (const 3) (const 4) (const 5)))
108 ;; First order, coalesced, immutability preserved.
109 (cons 0 (cons 1 (cons 2 '(3 4 5))))
110 (primcall cons (const 0)
111 (primcall cons (const 1)
112 (primcall cons (const 2)
115 ;; These two tests doesn't work any more because we changed the way we
116 ;; deal with constants -- now the algorithm will see a construction as
117 ;; being bound to the lexical, so it won't propagate it. It can't
118 ;; even propagate it in the case that it is only referenced once,
121 ;; (let ((x (cons 1 2))) (lambda () x))
123 ;; is not the same as
125 ;; (lambda () (cons 1 2))
127 ;; Perhaps if we determined that not only was it only referenced once,
128 ;; it was not closed over by a lambda, then we could propagate it, and
129 ;; re-enable these two tests.
133 ;; First order, mutability preserved.
134 (let loop ((i 3) (r '()))
137 (loop (1- i) (cons (cons i i) r))))
139 (primcall cons (const 1) (const 1))
140 (primcall cons (const 2) (const 2))
141 (primcall cons (const 3) (const 3))))
146 ;; First order, evaluated.
151 (loop (1- i) (cons i r))))
154 ;; Instead here are tests for what happens for the above cases: they
155 ;; unroll but they don't fold.
157 (let loop ((i 3) (r '()))
160 (loop (1- i) (cons (cons i i) r))))
163 (primcall cons (const 3) (const 3))))
166 (primcall cons (const 2) (const 2))
169 (primcall cons (const 1) (const 1))
178 (loop (1- i) (cons i r))))
180 ((primcall list (const 4)))
198 (let loop ((l '(1 2 3 4)) (sum 0))
201 (loop (cdr l) (+ sum (car l)))))
216 (string->chars "yo"))
217 (primcall list (const #\y) (const #\o)))
220 ;; Primitives in module-refs are resolved (the expansion of `pmatch'
221 ;; below leads to calls to (@@ (system base pmatch) car) and
222 ;; similar, which is what we want to be inlined.)
224 (use-modules (system base pmatch))
232 ;; Mutability preserved.
233 ((lambda (x y z) (list x y z)) 1 2 3)
234 (primcall list (const 1) (const 2) (const 3)))
237 ;; Don't propagate effect-free expressions that operate on mutable
243 (let (x) (_) ((primcall list (const 1)))
244 (let (y) (_) ((primcall car (lexical x _)))
246 (primcall set-car! (lexical x _) (const 0))
250 ;; Don't propagate effect-free expressions that operate on objects we
255 (let (y) (_) ((primcall car (toplevel x)))
257 (primcall set-car! (toplevel x) (const 0))
261 ;; Infinite recursion
262 ((lambda (x) (x x)) (lambda (x) (x x)))
267 (call (lexical x _) (lexical x _))))))
268 (call (lexical x _) (lexical x _))))
271 ;; First order, aliased primitive.
272 (let* ((x *) (y (x 1 2))) y)
276 ;; First order, shadowed primitive.
278 (define (+ x y) (pk x y))
284 (((x y) #f #f #f () (_ _))
285 (call (toplevel pk) (lexical x _) (lexical y _))))))
286 (call (toplevel +) (const 1) (const 2))))
289 ;; First-order, effects preserved.
294 (call (toplevel do-something!))
298 ;; First order, residual bindings removed.
301 (primcall * (const 5) (toplevel z)))
304 ;; First order, with lambda.
306 (define (bar z) (* z z))
311 (((x) #f #f #f () (_))
312 (primcall + (lexical x _) (const 9)))))))
315 ;; First order, with lambda inlined & specialized twice.
316 (let ((f (lambda (x y)
325 (primcall + ; (f 2 3)
330 (let (x) (_) ((toplevel something)) ; (f something 2)
331 ;; `something' is not const, so preserve order of
332 ;; effects with a lexical binding.
340 ;; First order, with lambda inlined & specialized 3 times.
341 (let ((f (lambda (x y) (if (> x 0) y x))))
349 (const -1) ; (f -1 0)
355 (seq (toplevel y) (const -1)) ; (f -1 y)
358 (toplevel y) ; (f 2 y)
359 (let (x y) (_ _) ((toplevel z) (toplevel y)) ; (f z y)
360 (if (primcall > (lexical x _) (const 0))
365 ;; First order, conditional.
373 (((x) #f #f #f () (_))
374 (call (toplevel display) (lexical x _))))))
377 ;; First order, recursive procedure.
378 (letrec ((fibo (lambda (n)
387 ;; Don't propagate toplevel references, as intervening expressions
388 ;; could alter their bindings.
392 (let (x) (_) ((toplevel top))
394 (call (toplevel foo))
400 (f (* (car x) (cadr x))))
407 ;; Higher order with optional argument (default value).
408 ((lambda* (f x #:optional (y 0))
409 (+ y (f (* (car x) (cadr x)))))
416 ;; Higher order with optional argument (caller-supplied value).
417 ((lambda* (f x #:optional (y 0))
418 (+ y (f (* (car x) (cadr x)))))
426 ;; Higher order with optional argument (side-effecting default
428 ((lambda* (f x #:optional (y (foo)))
429 (+ y (f (* (car x) (cadr x)))))
433 (let (y) (_) ((call (toplevel foo)))
434 (primcall + (lexical y _) (const 7))))
437 ;; Higher order with optional argument (caller-supplied value).
438 ((lambda* (f x #:optional (y (foo)))
439 (+ y (f (* (car x) (cadr x)))))
448 ((lambda (f) (f x)) (lambda (x) x))
453 ;; <https://lists.gnu.org/archive/html/bug-guile/2011-09/msg00019.html>.
454 (let ((fold (lambda (f g) (f (g top)))))
455 (fold 1+ (lambda (x) x)))
456 (primcall 1+ (toplevel top)))
459 ;; Procedure not inlined when residual code contains recursive calls.
460 ;; <http://debbugs.gnu.org/9542>
461 (letrec ((fold (lambda (f x3 b null? car cdr)
464 (f (car x3) (fold f (cdr x3) b null? car cdr))))))
465 (fold * x 1 zero? (lambda (x1) x1) (lambda (x2) (- x2 1))))
466 (letrec (fold) (_) (_)
467 (call (lexical fold _)
474 (((x1) #f #f #f () (_))
478 (((x2) #f #f #f () (_))
479 (primcall 1- (lexical x2 _))))))))
481 (pass-if "inlined lambdas are alpha-renamed"
482 ;; In this example, `make-adder' is inlined more than once; thus,
483 ;; they should use different gensyms for their arguments, because
484 ;; the various optimization passes assume uniquely-named variables.
487 ;; <https://lists.gnu.org/archive/html/bug-guile/2011-09/msg00019.html> and
488 ;; <https://lists.gnu.org/archive/html/bug-guile/2011-09/msg00029.html>.
489 (pmatch (unparse-tree-il
490 (peval (expand-primitives!
494 (lambda (x) (lambda (y) (+ x y)))))
495 (cons (make-adder 1) (make-adder 2)))
501 (((y) #f #f #f () (,gensym1))
504 (lexical y ,ref1)))))
507 (((y) #f #f #f () (,gensym2))
510 (lexical y ,ref2))))))
511 (and (eq? gensym1 ref1)
513 (not (eq? gensym1 gensym2))))
517 ;; Unused letrec bindings are pruned.
518 (letrec ((a (lambda () (b)))
525 ;; Unused letrec bindings are pruned.
530 (seq (call (toplevel foo!))
534 ;; Higher order, mutually recursive procedures.
535 (letrec ((even? (lambda (x)
540 (and (even? 4) (odd? 7)))
544 ;; Memv with constants.
549 ;; Memv with non-constant list. It could fold but doesn't
551 (memv 1 (list 3 2 1))
554 (primcall list (const 3) (const 2) (const 1))))
557 ;; Memv with non-constant key, constant list, test context
561 (let (key) (_) ((toplevel foo))
562 (if (if (primcall eqv? (lexical key _) (const 3))
564 (if (primcall eqv? (lexical key _) (const 2))
566 (primcall eqv? (lexical key _) (const 1))))
571 ;; Memv with non-constant key, empty list, test context.
575 (seq (toplevel foo) (const 'b)))
578 ;; Below are cases where constant propagation should bail out.
582 ;; Non-constant lexical is not propagated.
583 (let ((v (make-vector 6 #f)))
585 (vector-set! v n n)))
587 ((call (toplevel make-vector) (const 6) (const #f)))
590 (((n) #f #f #f () (_))
591 (primcall vector-set!
592 (lexical v _) (lexical n _) (lexical n _)))))))
595 ;; Mutable lexical is not propagated.
596 (let ((v (vector 1 2 3)))
600 ((primcall vector (const 1) (const 2) (const 3)))
607 ;; Lexical that is not provably pure is not inlined nor propagated.
608 (let* ((x (if (> p q) (frob!) (display 'chbouib)))
611 (let (x) (_) ((if (primcall > (toplevel p) (toplevel q))
612 (call (toplevel frob!))
613 (call (toplevel display) (const chbouib))))
614 (let (y) (_) ((primcall * (lexical x _) (const 2)))
617 (primcall + (lexical x _) (lexical y _))))))
620 ;; Non-constant arguments not propagated to lambdas.
629 ((primcall vector (const 1) (const 2) (const 3))
630 (call (toplevel make-list) (const 10))
631 (primcall list (const 1) (const 2) (const 3)))
633 (primcall vector-set!
634 (lexical x _) (const 0) (const 0))
635 (seq (primcall set-car!
636 (lexical y _) (const 0))
638 (lexical z _) (const ()))))))
641 (let ((foo top-foo) (bar top-bar))
642 (let* ((g (lambda (x y) (+ x y)))
643 (f (lambda (g x) (g x x))))
644 (+ (f g foo) (f g bar))))
645 (let (foo bar) (_ _) ((toplevel top-foo) (toplevel top-bar))
647 (primcall + (lexical foo _) (lexical foo _))
648 (primcall + (lexical bar _) (lexical bar _)))))
651 ;; Fresh objects are not turned into constants, nor are constants
652 ;; turned into fresh objects.
657 (let (x) (_) ((primcall cons (const 1) (const (2 3))))
658 (primcall cons (const 0) (lexical x _))))
665 (let (x) (_) ((const 2))
667 (set! (lexical x _) (const 3))
676 (frob f) ; may mutate `x'
678 (letrec (x) (_) ((const 0))
680 (call (toplevel frob) (lambda _ _))
685 (letrec ((f (lambda (x)
686 (set! f (lambda (_) x))
692 ;; Bindings possibly mutated.
693 (let ((x (make-foo)))
694 (frob! x) ; may mutate `x'
696 (let (x) (_) ((call (toplevel make-foo)))
698 (call (toplevel frob!) (lexical x _))
702 ;; Inlining stops at recursive calls with dynamic arguments.
704 (if (< x 0) x (loop (1- x))))
705 (letrec (loop) (_) ((lambda (_)
707 (((x) #f #f #f () (_))
709 (call (lexical loop _)
712 (call (lexical loop _) (toplevel x))))
715 ;; Recursion on the 2nd argument is fully evaluated.
717 (let loop ((x x) (y 10))
721 (let (x) (_) ((call (toplevel top)))
722 (call (toplevel foo) (lexical x _) (const 0))))
725 ;; Inlining aborted when residual code contains recursive calls.
727 ;; <http://debbugs.gnu.org/9542>
728 (let loop ((x x) (y 0))
733 (loop (1+ x) (1+ y)))))
734 (letrec (loop) (_) ((lambda (_)
736 (((x y) #f #f #f () (_ _))
738 (lexical y _) (const 0))
740 (call (lexical loop _) (toplevel x) (const 0))))
743 ;; Infinite recursion: `peval' gives up and leaves it as is.
744 (letrec ((f (lambda (x) (g (1- x))))
745 (g (lambda (x) (h (1+ x))))
746 (h (lambda (x) (f x))))
751 ;; Infinite recursion: all the arguments to `loop' are static, but
752 ;; unrolling it would lead `peval' to enter an infinite loop.
756 (letrec (loop) (_) ((lambda . _))
757 (call (lexical loop _) (const 0))))
760 ;; This test checks that the `start' binding is indeed residualized.
761 ;; See the `referenced?' procedure in peval's `prune-bindings'.
763 (let ((here (let ((start pos)) (lambda () start))))
764 (set! pos 1) ;; Cause references to `pos' to residualize.
766 (let (pos) (_) ((const 0))
769 (set! (lexical pos _) (const 1))
770 (call (lexical here _))))))
773 ;; FIXME: should this one residualize the binding?
779 ;; This is a fun one for peval to handle.
782 (letrec (a) (_) ((lexical a _))
786 ;; Another interesting recursive case.
787 (letrec ((a b) (b a))
789 (letrec (a) (_) ((lexical a _))
793 ;; Another pruning case, that `a' is residualized.
794 (letrec ((a (lambda () (a)))
800 ;; "b c a" is the current order that we get with unordered letrec,
801 ;; but it's not important to this test, so if it changes, just adapt
803 (letrec (b c a) (_ _ _)
807 (call (lexical a _)))))
810 (((x) #f #f #f () (_))
815 (call (lexical a _))))))
818 ((call (toplevel foo) (lexical b _)))
819 (call (lexical c _) (lexical d _)))))
822 ;; In this case, we can prune the bindings. `a' ends up being copied
823 ;; because it is only referenced once in the source program. Oh
825 (letrec* ((a (lambda (x) (top x)))
831 (((x) #f #f #f () (_))
832 (call (toplevel top) (lexical x _)))))
835 (((x) #f #f #f () (_))
836 (call (toplevel top) (lexical x _)))))))
839 ;; Constant folding: cons of #nil does not make list
841 (primcall cons (const 1) (const '#nil)))
844 ;; Constant folding: cons
845 (begin (cons 1 2) #f)
849 ;; Constant folding: cons
850 (begin (cons (foo) 2) #f)
851 (seq (call (toplevel foo)) (const #f)))
854 ;; Constant folding: cons
859 ;; Constant folding: car+cons
864 ;; Constant folding: cdr+cons
869 ;; Constant folding: car+cons, impure
871 (seq (call (toplevel bar)) (const 1)))
874 ;; Constant folding: cdr+cons, impure
876 (seq (call (toplevel bar)) (const 0)))
879 ;; Constant folding: car+list
884 ;; Constant folding: cdr+list
886 (primcall list (const 0)))
889 ;; Constant folding: car+list, impure
891 (seq (call (toplevel bar)) (const 1)))
894 ;; Constant folding: cdr+list, impure
896 (seq (call (toplevel bar)) (primcall list (const 0))))
899 ;; Equality primitive: same lexical
900 (let ((x (random))) (eq? x x))
901 (seq (call (toplevel random)) (const #t)))
904 ;; Equality primitive: merge lexical identities
905 (let* ((x (random)) (y x)) (eq? x y))
906 (seq (call (toplevel random)) (const #t)))
909 ;; Non-constant guards get lexical bindings.
910 (dynamic-wind foo (lambda () bar) baz)
911 (let (w u) (_ _) ((toplevel foo) (toplevel baz))
912 (dynwind (lexical w _)
919 ;; Constant guards don't need lexical bindings.
920 (dynamic-wind (lambda () foo) (lambda () bar) (lambda () baz))
924 ((() #f #f #f () ()) (toplevel foo))))
930 ((() #f #f #f () ()) (toplevel baz))))))
933 ;; Prompt is removed if tag is unreferenced
934 (let ((tag (make-prompt-tag)))
935 (call-with-prompt tag
941 ;; Prompt is removed if tag is unreferenced, with explicit stem
942 (let ((tag (make-prompt-tag "foo")))
943 (call-with-prompt tag
948 ;; Handler lambda inlined
950 (call-with-prompt tag
953 (prompt (toplevel tag)
956 (((k x) #f #f #f () (_ _))
959 ;; Handler toplevel not inlined
961 (call-with-prompt tag
964 (let (handler) (_) ((toplevel handler))
965 (prompt (toplevel tag)
968 ((() #f args #f () (_))
971 (lexical args _)))))))
974 ;; `while' without `break' or `continue' has no prompts and gets its
975 ;; condition folded. Unfortunately the outer `lp' does not yet get
986 (call (lexical loop _))))))
987 (call (lexical loop _)))))))
988 (call (lexical lp _))))
992 (apply (lambda (x y) (+ x y))
996 (((x y) #f #f #f () (_ _))
1003 ;; If we bail out when inlining an identifier because it's too big,
1004 ;; but the identifier simply aliases some other identifier, then avoid
1005 ;; residualizing a reference to the leaf identifier. The bailout is
1006 ;; driven by the recursive-effort-limit, which is currently 100. We
1007 ;; make sure to trip it with this recursive sum thing.
1009 (let ((x (let sum ((n 0) (out 0))
1011 (sum (1+ n) (+ out n))
1013 ((lambda (y) (list y)) x))
1015 (primcall list (lexical x _)))))