gsoc: New compiler (almost) ANSI conforming, progress report.

Hello clisp, Bruno, Sam

Cleavir + CLISP can now pass almost every test in the
data-and-control-flow portion of cl-ansi-test-suite. The only failing
tests there seem to be issues in CLISP itself. (See some issues I
opened on GitLab.) That means that every special operator, dynamic
variables, closures, non-local exits (both lexical and dynamic) and
function calls *seem* to work correctly now.

So far, I have handled macroexpansion by just calling macroexpanders
with the null macroexpansion environment #(NIL NIL). Since I am trying
to leverage CLISP's macro definitions as much as possible, I'd like to
know for what type of macros this will break down for CLISP. I'm not
quite sure which information I really need to make all macros work.

About the compiler, the code produced currently looks like it is
promising in some ways, and bad in others. For example, since I am
translating an SSA flow graph to byte code directly, the code looks
like it is trying to use the stack as a register machine, and
therefore at times LOADs and and PUSHs a lot. On the other hand, flow
sensitive information is readily apparent and it should be easy to
write previously impossible optimizations. To demonstrate, consider
the following:

(disassemble '(lambda (z)
               (let ((x 'e))
                 (values
                  (case z
                    (1 (setq x 'a) 'w)
                    (2 (setq x 'b) 'y)
                    (t (setq x 'c) 'z))
                  x))))
Disassembly of function :LAMBDA
(CONST 0) = E
(CONST 1) = 1
(CONST 2) = A
(CONST 3) = W
(CONST 4) = 2
(CONST 5) = B
(CONST 6) = Y
(CONST 7) = C
(CONST 8) = Z
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
23 byte-code instructions:
0     (CONST&PUSH 0)                      ; E
1     (LOAD&PUSH 2)
2     (JMPIFEQTO 1 L18)                   ; 1
5     (LOAD&PUSH 2)
6     (JMPIFEQTO 4 L23)                   ; 2
9     (CONST 7)                           ; C
10    (STORE 0)
11    (CONST 8)                           ; Z
12    L12
12    (PUSH)
13    (LOAD&PUSH 1)
14    (STACK-TO-MV 2)
16    (SKIP&RET 3)
18    L18
18    (CONST 2)                           ; A
19    (STORE 0)
20    (CONST 3)                           ; W
21    (JMP L12)
23    L23
23    (CONST 5)                           ; B
24    (STORE 0)
25    (CONST 6)                           ; Y
26    (JMP L12)

vs.
(disassemble (cleavir-compile '(lambda (z)
                                               (let ((x 'e))
                                                 (values
                                                  (case z
                                                    (1 (setq x 'a) 'w)
                                                    (2 (setq x 'b) 'y)
                                                    (t (setq x 'c) 'z))
                                                  x)))))

Disassembly of function NIL
(CONST 0) = 1
(CONST 1) = NIL
(CONST 2) = 2
(CONST 3) = NIL
(CONST 4) = C
(CONST 5) = Z
(CONST 6) = B
(CONST 7) = Y
(CONST 8) = A
(CONST 9) = W
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
32 byte-code instructions:
0     (LOAD&PUSH 1)
1     (CONST&PUSH 0)                      ; 1
2     (CALLS2&PUSH 19)                    ; EQL
4     (LOAD&PUSH 0)
5     (JMPIFEQTO 1 L17)                   ; NIL
8     (JMP L37)
10    L10
10    (LOAD&PUSH 0)
11    (LOAD&PUSH 2)
12    (CALLSR 2 29)                       ; VALUES
15    (SKIP&RET 5)
17    L17
17    (LOAD&PUSH 2)
18    (CONST&PUSH 2)                      ; 2
19    (CALLS2&PUSH 19)                    ; EQL
21    (LOAD&PUSH 0)
22    (JMPIFEQTO 3 L27)                   ; NIL
25    (JMP L32)
27    L27
27    (CONST 4)                           ; C
28    (STORE 0)
29    (CONST&PUSH 5)                      ; Z
30    (JMP L10)
32    L32
32    (CONST 6)                           ; B
33    (STORE 0)
34    (CONST&PUSH 7)                      ; Y
35    (JMP L10)
37    L37
37    (CONST&PUSH 8)                      ; A
38    (CONST&PUSH 9)                      ; W
39    (JMP L10)

It's readily apparent that the Cleavir code is not using the best
choice of branching instructions, duplicating constants, not
minimizing jumps, and PUSHing and LOADing unnecessarily. However, the
Cleavir code does not mention the constant 'e at all, because it's
obvious from the SSA flow graph that 'e is never used, and hence, dead
code elimination kills it. The passes that I've already written myself
are the SSA conversion, dead code elimination, and copy propogation
passes. Adding more dataflow analyses should be straightforward in
this framework, especially with SSA done.

For now, I am still focusing on correctness, before jumping to more
sophisticated optimizations like conditional constant propogation or
fixing some things like special casing for the various branch
instructions. I wonder how I should integrate this new compiler to
toplevel functions like COMPILE-FILE/EVAL. Would it make sense to have
a dynamic variable like *use-cleavir* that switches on the new
compiler, or a keyword parameter to COMPILE/COMPILE-FILE? When I tried
using a dynamic variable, I ran into the issue where CLOS methods
would try and randomly recompile using Cleavir when I had only meant
to compile one form with Cleavir, since it's heavily CLOS based. Still
not quite sure how to tie all this toplevel/frontend stuff together.

Charles

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
clisp-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/clisp-devel