Menu
▾
▴
gsoc: Improved code generation
|
From: Charles Z. <ka...@be...> - 2018-06-26 21:51:43
|
Hello clisp, Bruno, Sam,
I have spent some time optimizing bytecode generation, including:
- using all the various specialized CALL instructions more effectively
- inlining VALUES, MULTIPLE-VALUE-SETQ/BIND
- a very bad basic block scheduler
- reduce LOAD/STOREs (without peephole optimizing)
Together with data flow optimizations, the new compiler is usually
able to generate better code than the existing compiler.
For example, (from cl-ansi-test-suite)
> (cleavir-compile '(lambda ()
(let* ((x (list 'a 'b 'c 'd 'e))
(y (list 'f 'g 'h 'i 'j))
(p1 1) (p2 2) (len 3)
(z '(10 11 12)))
(rotatef (subseq x p1 (+ p1 len))
(subseq y p2 (+ p2 len))
z)
(values x y z))))
Disassembly of function NIL
(CONST 0) = A
(CONST 1) = B
(CONST 2) = C
(CONST 3) = D
(CONST 4) = E
(CONST 5) = F
(CONST 6) = G
(CONST 7) = H
(CONST 8) = I
(CONST 9) = J
(CONST 10) = 1
(CONST 11) = 4
(CONST 12) = 2
(CONST 13) = 5
(CONST 14) = (10 11 12)
(CONST 15) = :START1
(CONST 16) = :END1
(CONST 17) = :START1
(CONST 18) = :END1
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
42 byte-code instructions:
0 (CONST&PUSH 0) ; A
1 (CONST&PUSH 1) ; B
2 (CONST&PUSH 2) ; C
3 (CONST&PUSH 3) ; D
4 (CONST&PUSH 4) ; E
5 (LIST&PUSH 5)
7 (CONST&PUSH 5) ; F
8 (CONST&PUSH 6) ; G
9 (CONST&PUSH 7) ; H
10 (CONST&PUSH 8) ; I
11 (CONST&PUSH 9) ; J
12 (LIST&PUSH 5)
14 (LOAD&PUSH 1)
15 (CONST&PUSH 10) ; 1
16 (CONST&PUSH 11) ; 4
17 (CALLS2&PUSH 96) ; SUBSEQ
19 (LOAD&PUSH 1)
20 (CONST&PUSH 12) ; 2
21 (CONST&PUSH 13) ; 5
22 (CALLS2&PUSH 96) ; SUBSEQ
24 (CONST&PUSH 14) ; (10 11 12)
25 (LOAD&PUSH 4)
26 (LOAD&PUSH 2)
27 (PUSH-UNBOUND 4)
29 (CONST 10) ; 1
30 (STORE 3)
31 (CONST 11) ; 4
32 (STORE 2)
33 (CALLS2 104) ; REPLACE
35 (LOAD&PUSH 3)
36 (LOAD&PUSH 1)
37 (PUSH-UNBOUND 4)
39 (CONST 12) ; 2
40 (STORE 3)
41 (CONST 13) ; 5
42 (STORE 2)
43 (CALLS2 104) ; REPLACE
45 (LOAD&PUSH 4)
46 (LOAD&PUSH 4)
47 (LOAD&PUSH 4)
48 (STACK-TO-MV 3)
50 (SKIP&RET 6)
vs CLISP's
Disassembly of function NIL
(CONST 0) = A
(CONST 1) = B
(CONST 2) = C
(CONST 3) = D
(CONST 4) = E
(CONST 5) = F
(CONST 6) = G
(CONST 7) = H
(CONST 8) = I
(CONST 9) = J
(CONST 10) = (10 11 12)
(CONST 11) = 1
(CONST 12) = 3
(CONST 13) = 2
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
48 byte-code instructions:
0 (CONST&PUSH 0) ; A
1 (CONST&PUSH 1) ; B
2 (CONST&PUSH 2) ; C
3 (CONST&PUSH 3) ; D
4 (CONST&PUSH 4) ; E
5 (LIST&PUSH 5)
7 (CONST&PUSH 5) ; F
8 (CONST&PUSH 6) ; G
9 (CONST&PUSH 7) ; H
10 (CONST&PUSH 8) ; I
11 (CONST&PUSH 9) ; J
12 (LIST&PUSH 5)
14 (CONST&PUSH 10) ; (10 11 12)
15 (CONST&PUSH 11) ; 1
16 (CONST&PUSH 12) ; 3
17 (CALLSR&PUSH 2 55) ; +
20 (CONST&PUSH 13) ; 2
21 (CONST&PUSH 12) ; 3
22 (CALLSR&PUSH 2 55) ; +
25 (LOAD&PUSH 4)
26 (CONST&PUSH 11) ; 1
27 (LOAD&PUSH 3)
28 (CALLS2&PUSH 96) ; SUBSEQ
30 (LOAD&PUSH 4)
31 (CONST&PUSH 13) ; 2
32 (LOAD&PUSH 3)
33 (CALLS2&PUSH 96) ; SUBSEQ
35 (LOAD&PUSH 4)
36 (LOAD&PUSH 7)
37 (LOAD&PUSH 2)
38 (CONST&PUSH 11) ; 1
39 (LOAD&PUSH 7)
40 (PUSH-UNBOUND 2)
42 (CALLS2 104) ; REPLACE
44 (LOAD&PUSH 6)
45 (LOAD&PUSH 1)
46 (CONST&PUSH 13) ; 2
47 (LOAD&PUSH 6)
48 (PUSH-UNBOUND 2)
50 (CALLS2 104) ; REPLACE
52 (LOAD 2)
53 (STORE 5)
54 (SKIP 5)
56 (LOAD&PUSH 2)
57 (LOAD&PUSH 2)
58 (LOAD&PUSH 2)
59 (STACK-TO-MV 3)
61 (SKIP&RET 4)
An example of the suboptimal basic block scheduler:
CLEAVIR-CLISP> (cleavir-compile '(lambda (n) (dotimes (i n) (print i))))
#<COMPILED-FUNCTION NIL>
CLEAVIR-CLISP> (disassemble *)
Disassembly of function NIL
(CONST 0) = 0
(CONST 1) = NIL
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
15 byte-code instructions:
0 (CONST&PUSH 0) ; 0
1 L1
1 (LOAD&PUSH 0)
2 (LOAD&PUSH 3)
3 (CALLSR&PUSH 1 52) ; >=
6 (LOAD&JMPIF 0 L20)
9 (LOAD&PUSH 1)
10 (PUSH-UNBOUND 1)
12 (CALLS1 142) ; PRINT
14 (LOAD&INC&STORE 1)
16 (SKIP 1)
18 (JMP L1)
20 L20
20 (CONST 1) ; NIL
21 (SKIP&RET 4)
Recursive functions don't use JSR in the new compiler, but rather
close over themselves.
CLEAVIR-CLISP> (cleavir-compile '(lambda ()
(labels ((fact (n)
(if (zerop n)
1
(* n (fact (1- n))))))
#'fact)))
#<COMPILED-FUNCTION NIL>
CLEAVIR-CLISP> (funcall * )
#<COMPILED-FUNCTION NIL>
CLEAVIR-CLISP> (disassemble *)
Disassembly of function NIL
(CONST 0) = #(NIL #<COMPILED-FUNCTION NIL>)
(CONST 1) = 1
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
13 byte-code instructions:
0 (LOAD&PUSH 1)
1 (CALLS2&PUSH 172) ; ZEROP
3 (LOAD&JMPIF 0 L20)
6 (LOADV&PUSH 0 1)
9 (LOAD&DEC&PUSH 3)
11 (FUNCALL&PUSH 1)
13 (LOAD&PUSH 3)
14 (LOAD&PUSH 1)
15 (CALLSR 2 57) ; *
18 (SKIP&RET 4)
20 L20
20 (CONST 1) ; 1
21 (SKIP&RET 3)
Charles
|
