clisp-devel

gsoc: first steps, how to do more stuff with LAPs

[Charles Z. <ka...@be...>]

Hello clisp,

I managed to get clisp bytecode compiled for forms like (lambda (x y)
(if (= x y) (1+ x) (+ x y)) correctly with Cleavir. So far the
bytecode format produced is just a code listing like the following:

((CONST 0 #S(CONST :VALUE = :FORM NIL :LTV-FORM NIL :HORIZON NIL))
(PUSH)
(CALLS1 86)
(PUSH)
(LOAD 3)
(PUSH)
(LOAD 3)
(PUSH)
(FUNCALL 2)
(PUSH)
(CONST 1 #S(CONST :VALUE NIL :FORM NIL :LTV-FORM NIL :HORIZON NIL))
(JMPIFEQ G178973)
(JMP G178975)
G178973
(CONST 2 #S(CONST :VALUE + :FORM NIL :LTV-FORM NIL :HORIZON NIL))
(PUSH)
(CALLS1 86)
(PUSH)
(LOAD 3)
(PUSH)
(LOAD 3)
(PUSH)
(FUNCALL 2)
(JMP G178974)
G178974
(SKIP 3)
(RET)
G178975
(LOAD 2)
(PUSH)
(CALLS2 177)
(JMP G178974))

I know I can call insert-combined-LAPs on such a code listing to get
the abbreviated LAP that disassemble normally produces. However, I
couldn't figure out a way to actually make this into an executable
function. It seems that I have to somehow lift the code constants up
into a constant vector, first of all. Would I have to resort to
hacking the top level COMPILE function with all the other machinery
like FNODEs and various special vars bound just to get plug into the
rest of the compilation pipeline (finishing from
insert-combined-LAPs)?

In addition, I can compile a nested function into LAP as well while
compiling the parent function, but it's not clear to me how to combine
the two into an executable object. For example,

(disassemble (lambda () (lambda ())))

Disassembly of function :LAMBDA
(CONST 0) = #<COMPILED-FUNCTION :LAMBDA-1>
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
2 byte-code instructions:
0     (CONST 0)                           ; #<COMPILED-FUNCTION :LAMBDA-1>
1     (SKIP&RET 1)

just skips straight to packaging up the function, already compiled. as
a CONST.  Is it simply as straightforward as compiling the inner
function's LAP first, and then saving it to the codevec somehow? it
didn't seem like function constants were treated the same way in the
pre insert-combined-LAPs code listings as constants like 2, for
example, which usually have some form like

(CONST 2 #S(CONST :VALUE 2 :FORM NIL :LTV-FORM NIL :HORIZON NIL))

embedded inside, whereas inner functions (which are referred to as
CONSTs as well) do not appear in the listing.

Anyway, my main question is how to finish off compiling something like
the first LAP I gave, into a function with separated bytevec, codevec
and all, which would also shed light onto the nested functions issue.

Charles

Re: gsoc: first steps, how to do more stuff with LAPs

[Charles Z. <ka...@be...>]

Quick update on the previous example: I cleaned up and added support
for using more of CLISP's call ops, instead of just punting to the
computed funcall routine.

So now the form
(lambda (x y) (if (= x y) (1+ x) (+ x y)))
compiles to
(LOAD 2)
(PUSH)
(LOAD 2)
(PUSH)
(CALLSR 1 47)
(PUSH)
(CONST 0 #S(CONST :VALUE NIL :FORM NIL :LTV-FORM NIL :HORIZON NIL))
(JMPIFEQ G271531)
(JMP G271533)
G271531
(LOAD 2)
(PUSH)
(LOAD 2)
(PUSH)
(CALLSR 2 55)
(JMP G271532)
G271532
(SKIP 3)
(RET)
G271533
(LOAD 2)
(PUSH)
(CALLS2 177)
(JMP G271532)
Compare with CLISP's actual current disassembly. (It's pretty close!
At least pre insert-combined-LAPs)

Charles

On Wed, May 16, 2018 at 12:51 AM, Charles Zhang <ka...@be...> wrote:
> Hello clisp,
>
> I managed to get clisp bytecode compiled for forms like (lambda (x y)
> (if (= x y) (1+ x) (+ x y)) correctly with Cleavir. So far the
> bytecode format produced is just a code listing like the following:
>
> ((CONST 0 #S(CONST :VALUE = :FORM NIL :LTV-FORM NIL :HORIZON NIL))
> (PUSH)
> (CALLS1 86)
> (PUSH)
> (LOAD 3)
> (PUSH)
> (LOAD 3)
> (PUSH)
> (FUNCALL 2)
> (PUSH)
> (CONST 1 #S(CONST :VALUE NIL :FORM NIL :LTV-FORM NIL :HORIZON NIL))
> (JMPIFEQ G178973)
> (JMP G178975)
> G178973
> (CONST 2 #S(CONST :VALUE + :FORM NIL :LTV-FORM NIL :HORIZON NIL))
> (PUSH)
> (CALLS1 86)
> (PUSH)
> (LOAD 3)
> (PUSH)
> (LOAD 3)
> (PUSH)
> (FUNCALL 2)
> (JMP G178974)
> G178974
> (SKIP 3)
> (RET)
> G178975
> (LOAD 2)
> (PUSH)
> (CALLS2 177)
> (JMP G178974))
>
> I know I can call insert-combined-LAPs on such a code listing to get
> the abbreviated LAP that disassemble normally produces. However, I
> couldn't figure out a way to actually make this into an executable
> function. It seems that I have to somehow lift the code constants up
> into a constant vector, first of all. Would I have to resort to
> hacking the top level COMPILE function with all the other machinery
> like FNODEs and various special vars bound just to get plug into the
> rest of the compilation pipeline (finishing from
> insert-combined-LAPs)?
>
> In addition, I can compile a nested function into LAP as well while
> compiling the parent function, but it's not clear to me how to combine
> the two into an executable object. For example,
>
> (disassemble (lambda () (lambda ())))
>
> Disassembly of function :LAMBDA
> (CONST 0) = #<COMPILED-FUNCTION :LAMBDA-1>
> 0 required arguments
> 0 optional arguments
> No rest parameter
> No keyword parameters
> 2 byte-code instructions:
> 0     (CONST 0)                           ; #<COMPILED-FUNCTION :LAMBDA-1>
> 1     (SKIP&RET 1)
>
> just skips straight to packaging up the function, already compiled. as
> a CONST.  Is it simply as straightforward as compiling the inner
> function's LAP first, and then saving it to the codevec somehow? it
> didn't seem like function constants were treated the same way in the
> pre insert-combined-LAPs code listings as constants like 2, for
> example, which usually have some form like
>
> (CONST 2 #S(CONST :VALUE 2 :FORM NIL :LTV-FORM NIL :HORIZON NIL))
>
> embedded inside, whereas inner functions (which are referred to as
> CONSTs as well) do not appear in the listing.
>
> Anyway, my main question is how to finish off compiling something like
> the first LAP I gave, into a function with separated bytevec, codevec
> and all, which would also shed light onto the nested functions issue.
>
> Charles

Re: gsoc: first steps, how to do more stuff with LAPs

[Bruno H. <br...@cl...>]

Hi Charles,

> I managed to get clisp bytecode compiled for forms like (lambda (x y)
> (if (= x y) (1+ x) (+ x y)) correctly with Cleavir. So far the
> bytecode format produced is just a code listing like the following:
> 
> ((CONST 0 #S(CONST :VALUE = :FORM NIL :LTV-FORM NIL :HORIZON NIL))
> (PUSH)
> (CALLS1 86)    ; FDEFINITION
> (PUSH)         ; #'=
> (LOAD 3)
> (PUSH)
> (LOAD 3)
> (PUSH)
> (FUNCALL 2)
> (PUSH)
> (CONST 1 #S(CONST :VALUE NIL :FORM NIL :LTV-FORM NIL :HORIZON NIL))
> (JMPIFEQ G178973)
> (JMP G178975)
> G178973
> (CONST 2 #S(CONST :VALUE + :FORM NIL :LTV-FORM NIL :HORIZON NIL))
> (PUSH)
> (CALLS1 86)    ; FDEFINITION
> (PUSH)         ; #'+
> (LOAD 3)
> (PUSH)
> (LOAD 3)
> (PUSH)
> (FUNCALL 2)
> (JMP G178974)
> G178974
> (SKIP 3)
> (RET)
> G178975
> (LOAD 2)
> (PUSH)
> (CALLS2 177)   ; 1+
> (JMP G178974))

Wow! This is more than remarkable, this is terrific!!

The FDEFINITION calls will be optimized away in a later step, I guess?

> I know I can call insert-combined-LAPs on such a code listing to get
> the abbreviated LAP that disassemble normally produces. However, I
> couldn't figure out a way to actually make this into an executable
> function.

Take a look at pass2 in compiler.lisp. This function currently takes
an FNODE as argument. What is the internal representation for an
entire function that is being compiled, in SICL? You'll probably need
a separate, workalike pass2 function, or extend the pass2 function
to allow the SICL function node as argument.

On top of pass2, there is pass3 and compile-lambdabody which modify
the created function object so that it becomes actually usable (by
eliminating reference to FNODEs).

> It seems that I have to somehow lift the code constants up
> into a constant vector, first of all. Would I have to resort to
> hacking the top level COMPILE function with all the other machinery
> like FNODEs and various special vars bound just to get plug into the
> rest of the compilation pipeline (finishing from
> insert-combined-LAPs)?

For this task, I think compile-lambdabody is the better place.

Recall the hierarchy: The compiler has several entry points,
  compile-lambda
  compile-form
  compile
  compile-file
All of them dispatch to compile-lambdabody, so this is the place to
touch for common things.

Whereas when it comes to e.g. bookkeeping of errors and warnings seen in
a file, then compile-file is the place to look for.

> In addition, I can compile a nested function into LAP as well while
> compiling the parent function, but it's not clear to me how to combine
> the two into an executable object.

Yup, this is a hairy part: how to these compilations interact with each
other. The way it's done is through *fnode-list* and *fnode-fixup-table*.
This is not pretty code; it took the current state after lots of small
changes.

> For example,
> 
> (disassemble (lambda () (lambda ())))
> 
> Disassembly of function :LAMBDA
> (CONST 0) = #<COMPILED-FUNCTION :LAMBDA-1>
> 0 required arguments
> 0 optional arguments
> No rest parameter
> No keyword parameters
> 2 byte-code instructions:
> 0     (CONST 0)                           ; #<COMPILED-FUNCTION :LAMBDA-1>
> 1     (SKIP&RET 1)
> 
> just skips straight to packaging up the function, already compiled. as
> a CONST.  Is it simply as straightforward as compiling the inner
> function's LAP first, and then saving it to the codevec somehow?

Take a deep look at compile-lambdabody.

> Anyway, my main question is how to finish off compiling something like
> the first LAP I gave, into a function with separated bytevec, codevec
> and all, which would also shed light onto the nested functions issue.

This is the area of pass2, pass3, compile-lambdabody (and create-fun-obj,
of course).

Bruno

Re: gsoc: first steps, how to do more stuff with LAPs

[Bruno H. <br...@cl...>]

Charles Zhang wrote:
> Quick update on the previous example: I cleaned up and added support
> for using more of CLISP's call ops, instead of just punting to the
> computed funcall routine.
> 
> So now the form
> (lambda (x y) (if (= x y) (1+ x) (+ x y)))
> compiles to
> (LOAD 2)
> (PUSH)
> (LOAD 2)
> (PUSH)
> (CALLSR 1 47)

Ah, cool, the FDEFINITION is optimized out! Nice.

Bruno

Re: gsoc: first steps, how to do more stuff with LAPs

[Charles Z. <ka...@be...>]

Hi Bruno,

Good news!
I had done exactly that this past week and I managed to hack enough to
get closures and nested functions working. There wasn't a need to
directly modify the clisp functions themselves; I could just rip out
enough of the functionality from compile/pass2 into a separate
function so I could finish compiling everything. The trick was filling
in just enough of fnode to get it to act as a surrogate to the LAP
generated by Cleavir. Now I am able to get, for example, (lambda (n)
(dotimes (i n) (print n)) compiled all the way to an executable
function.

CLEAVIR-CLISP> (funcall (cleavir-compile '(lambda (n) (dotimes (i n)
(print i)))) 5)

0
1
2
3
4
NIL

and even '(lambda (x z) (cons (lambda (y) (+ y z))
                                                  (lambda (w) (lambda
(y) (+ x y w)))))
now compiles and executes correctly.

I found that SICL produces a graph structure that models enclosed
function allocation, while CLISP prefers enclosing function allocation
(so hence, for example, the two inner lambdas share the outer lambda
closure vector). I wonder if there's a specific rationale for doing so
in CLISP. The sharing can save on allocation, but there's a
possibility of some garbage remaining.

Also, I am keeping track of my branch here:
https://gitlab.com/karlosz/clisp

You can test it by having SICL in a quicklisp aware place and loading
clisp/src/cleavir/load.lisp and testing the examples above with
(cleavir-clisp:cleavir-compile form). If you are curious, the way I
managed to hack the closures together and finish the compilation
pipeline is listed in tools.lisp and the translate-simple-instruction
-- enclose-instruction method.

There are still some silly miscompilations with nested function calls,
so not quite there yet!

Charles



On Mon, May 21, 2018 at 8:28 PM, Bruno Haible <br...@cl...> wrote:
> Charles Zhang wrote:
>> Quick update on the previous example: I cleaned up and added support
>> for using more of CLISP's call ops, instead of just punting to the
>> computed funcall routine.
>>
>> So now the form
>> (lambda (x y) (if (= x y) (1+ x) (+ x y)))
>> compiles to
>> (LOAD 2)
>> (PUSH)
>> (LOAD 2)
>> (PUSH)
>> (CALLSR 1 47)
>
> Ah, cool, the FDEFINITION is optimized out! Nice.
>
> Bruno
>



-- 
Class of 2021