clisp-devel — closed list for developers and testers

Re: gsoc: Loop invariant hoisting

[<don...@is...>]

Charles Zhang writes:

 > If I understand what your 'model' of a program's behavior is, then
 > all optimizations are off the table.

No, I argue that the applicable optimizations depend on the purpose 
of the code which cannot be derived from the code itself.  Though
adding some declarations would allow the compiler to understand this
purpose well enough to do the right thing.

 > If you want an evaluator that doesn't do any optimizations, switch
 > on the interpreter.

That would not satisfy my needs in this case.  I'd find out how long
it takes to run the interpreted code which might also be of interest,
but is a different question.

 > CLISP's compiler already violate the behavior you seem to want...

Wow, I didn't even know that.  I wonder whether this was also the case
when I ran those tests (about 20 years ago).
In particular, if I call your function on a non-array, there will be
no error, even though there would be one if I ran it interpreted.

 > As you can see, CLISP's compiler deletes the call to AREF. So the
 > compiler in CLISP already doesn't care about your definition of
 > intent of program behavior.

This does surprise me, and I have to say, also worries me.
I can't see how anyone would consider the behavior of the 
interpreted and compiled code to be equivalent in that case.

 > There is a framework in the compiler I am working on which can do a
 > little bit of what you want, that is, writing declarations to
 > inhibit certain optimizations like this one.

It now occurs to me that it would be useful to be able to turn on
warnings to tell the programmer when certain optimizations are made,
such as removing the aref or moving code out of a loop.  These are not
only useful for cases like those I've been describing where the
purpose of the code differs from the normal purpose assumed by the
compiler, but also because such optimizations suggest that the
programmer might not have intended what he wrote to begin with,
similar to other warnings that the compiler already emits.
These are often useful, and a good reason to compile code even
if you want to run it interpreted.

 > I think you misunderstood what I meant by hoisting conditions. I am
 > saying that that is necessary to keep the number of errors the
 > same. I agree with you that raising a different number of errors is
 > unacceptable. However, non-continuable errors can only signal zero
 > times or once in a function. That's what I meant by hoisting the
 > condition.

So if A is not an array, (aref A x) is not a non-continuable error.
I don't see why you think it can only signal once in a function.
Certainly if the function were interpreted and you found yourself in 
the debugger because the object was not an array, you could continue
past the error, e.g., return nil from aref, and then get the same 
error again, and then continue again.  

But even if the error could only signal once, one signal is different
from zero, which is what the compiled version would give.

 > My definition (not even my definition, basically of all compiler
 > writers) of behavioral equivalence is based on the notion of
 > preserving the operational semantics of a program. In the context
 > of ANSI CL, that means keeping the program as conforming to the
 > ANSI spec.

Doesn't the spec include signals?  Does it say that if aref is
given a non-array then the result is undefined?  That's certainly
not be the way I'd want either interpreted or compiled code to act.

 > It does not mean making sure the amount of time it takes for a
 > program to run remains the same. That does mean keeping the number
 > of program conditions (so, for example, not heap overflow
 > conditions which are raised by the system, not the program) the
 > same etc, which I am trying to do. The compiler's job is to make
 > the program run faster while making sure the code never deviates
 > from what is allowed by the spec.

I agree that if you want the time and space used by a computation to
be the same as when it's interpreted, then you should interpret it,
not compile it.  And to the extent that these things affect other
behavior, such as errors resulting from running out of space, or the
reading of the clock at various points in the computation, those are
also allowed to be affected by compilation.

I think that other changes in behavior are also SOMETIMES acceptable
and when they are, the compiler should be allowed to make changes that
cause those differences.  Not doing something that might cause a
signal, but would otherwise (if doing it did not cause the signal)
would have the same result, could be acceptable in some situations and
in those situations the removal of the call to aref seems ok.
Programmers should be able to control whether such changes are
allowed.  Similarly, I might be able to say that the compiler is
allowed to assume that no other code will run concurrently with a
piece of code to be compiled (including the debugger), in which case
my example of setting the element type of a stream multiple times
without using the stream in the mean while could be optimized to only
do the last change.

 > ... Two flow graphs have the same runtime behavior if, given the
 > same outputs of enter-instruction (the entry point of a function),
 > the same exceptions are raised and the same inputs are received to
 > the return-instruction associated with an enter-instruction.

Why does this not include the exception to aref when the first
argument is not an array?

I notice that the hyperspec says, on the page for aref,
   Exceptional Situations: None. 
I don't understand why.  Isn't a non-array passed as the first argument
an exceptional situation?  What am I missing?
Perhaps this is the root of my problem.

 > For the record, I did not make up this loop invariant hoisting
 > optimization. It is taken for granted in all major compilers, for both
 > unsafe and safe languages (GCC, LLVM, MLTon, GHC, CMUCL, SBCL, etc.)
 > There is a lot of literature on this subject, where care to preserve
 > the correctness of a program is documented.
 > 
 > Here is the wikipedia link:
 > https://en.wikipedia.org/wiki/Loop-invariant_code_motion.

Thanks for that ref.  But it doesn't seem to address the issues here.

Re: gsoc: Loop invariant hoisting

[Christopher S. <cs...@dt...>]

Measuring / timing or relying on the delay of code is naturally an 
implementation dependent thing, and it's also something that is useful 
and that programs are known to do.

We have the OPTIMIZE declarations, which are ignorable and allow 
implementation dependent qualities; sometimes documented (which 
programmers are tempted to view as guarantees).

I don't think this hoisting feature should necessarily respect the SPEED 
quality either way: you shouldn't have to make a declaration to get 
ordinary optimizations like this, especially ones that don't argue 
against SAFETY in whatever strategy calculus is in the mind of the 
implementor.  Note that there are no negative values allowed for 
optimize qualities.

When someone writes timing code like this, it is for a special purpose, 
so they should have to make a more specific declaration of their weird 
intent. The most conservative approach, and coincidentally perhaps the 
easiest to implement, would be a very specific "negative quality" called 
NO-HOIST that given any value other than 0 means not to do this 
particular optimization. This would also flag the source code for 
humans; for third-party tools, it would be flagged as an unknown 
optimization (which is about as meaningful as it can really be at that 
level, anyway).

Re: gsoc: Loop invariant hoisting

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

If I understand what your 'model' of a program's behavior is, then all
optimizations are off the table. The intent of this project is to add
a new compiler that can do more optimizations than CLISP's compiler
can at the moment. If you want an evaluator that doesn't do any
optimizations, switch on the interpreter. CLISP's compiler already
violate the behavior you seem to want. For example, with CLISP's
compiler

(compile nil '(lambda (array)
                                  (dotimes (i 5)
                                    (dotimes (j 7)
                                      (aref array (+ i 2) (+ j 4))))))
#<COMPILED-FUNCTION NIL>
NIL
NIL
> (disassemble *)

Disassembly of function NIL
(CONST 0) = 0
(CONST 1) = 5
(CONST 2) = 7
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
19 byte-code instructions:
0     (CONST&PUSH 0)                      ; 0
1     (JMP L18)
3     L3
3     (CONST&PUSH 0)                      ; 0
4     (JMP L8)
6     L6
6     (LOAD&INC&STORE 0)
8     L8
8     (LOAD&PUSH 0)
9     (CONST&PUSH 2)                      ; 7
10    (CALLSR&JMPIFNOT 1 52 L6)           ; >=
14    (SKIP 1)
16    (LOAD&INC&STORE 0)
18    L18
18    (LOAD&PUSH 0)
19    (CONST&PUSH 1)                      ; 5
20    (CALLSR&JMPIFNOT 1 52 L3)           ; >=
24    (NIL)
25    (SKIP&RET 3)

As you can see, CLISP's compiler deletes the call to AREF. So the
compiler in CLISP already doesn't care about your definition of intent
of program behavior.

There is a framework in the compiler I am working on which can do a
little bit of what you want, that is, writing declarations to inhibit
certain optimizations like this one.

>  > Applying hoisting clearly gives different behavior. The solution,
>  > which I am currently implementing, is to also hoist out the
>  > condition, so that the hoisted computation runs only 0, or 1 times,
>
> By most definitions of computational "behavior" (which I'm arguing
> above are actually inadequate), generating different numbers of
> errors, which could potentially involve user interaction, would be
> viewed as different behavior.  Do you even have a real definition of
> what behaviors are considered equivalent by particular optimizations?

I think you misunderstood what I meant by hoisting conditions. I am
saying that that is necessary to keep the number of errors the same. I
agree with you that raising a different number of errors is
unacceptable. However, non-continuable errors can only signal zero
times or once in a function. That's what I meant by hoisting the
condition.

My definition (not even my definition, basically of all compiler
writers) of behavioral equivalence is based on the notion of
preserving the operational semantics of a program. In the context of
ANSI CL, that means keeping the program as conforming to the ANSI
spec. It does not mean making sure the amount of time it takes for a
program to run remains the same. That does mean keeping the number of
program conditions (so, for example, not heap overflow conditions
which are raised by the system, not the program) the same etc, which I
am trying to do. The compiler's job is to make the program run faster
while making sure the code never deviates from what is allowed by the
spec.

Since you doubt whether I have a real model of runtime behavior, let
me explain how the compiler I am working on operates. The new compiler
produces a flow graph intermediate representation representing low
level instructions modelling ANSI CL. Optimizations are done on this
flow graph. Things like the compile time and macroexpansion
environment have all been eliminated in this flow graph
representation. Two flow graphs have the same runtime behavior if,
given the same outputs of enter-instruction (the entry point of a
function), the same exceptions are raised and the same inputs are
received to the return-instruction associated with an
enter-instruction. Side effects which could have an effect on any
future computations must be preserved between two flow graphs.
However, the machine is assumed to have an infinite amount of memory,
so that tail call optimization is not considered an illegal
optimization. (which CLISP also already does). Consequences of this
are that side effects like consing or not consing when doing
multiple-value-bind is leagl both ways, whereas optimizing an infinite
loop away is illegal. (since an infinite amount of memory doesn't
affect whether a computation halts or not.)

For the record, I did not make up this loop invariant hoisting
optimization. It is taken for granted in all major compilers, for both
unsafe and safe languages (GCC, LLVM, MLTon, GHC, CMUCL, SBCL, etc.)
There is a lot of literature on this subject, where care to preserve
the correctness of a program is documented.

Here is the wikipedia link:
https://en.wikipedia.org/wiki/Loop-invariant_code_motion.

Charles

On Sat, Jun 23, 2018 at 12:10 PM, Don Cohen
<don...@is...> wrote:
> Charles Zhang writes:
>  > You make a good point, but the optimization definitely doesn't apply
>  > in this case.
>
> I understand, but this case is not really the point.
> There are similar cases, e.g., measuring the time to do
> various arithmetic operations, that would be affected.
> For instance one of the results recorded in the comment
> above the code I sent reports the time taken by code-char,
> which if it isn't already recognized as side effect free,
> certainly could be.  For that matter my test program
> never even used the result, which is another excuse to
> optimize out the computation.
>
> And even if my example isn't affected YET, this optimization
> is just one step along a path that seems likely to affect
> that example and pretty much all the other similar ones,
> which I argue have legitimate uses.
>
> The more general point is that "optimization" is based on a
> model of the purpose of the code that is not always correct.
> If the purpose of the code is to measure the time it takes to
> add two numbers, perhaps of specific types and sizes, when those
> types and sizes cannot be determined at compile time, then the
> programmer may have to understand the compiler very well in order
> to generate a sample test program to answer that question, and
> even with that understanding, generating that test program might
> take significant effort.
>
> For the foreseeable future the best solution might be some way
> to control the optimizations, perhaps declarations indicating
> which individual optimization mechanisms to use or not.
> I can also imagine trying to search the space of optimization
> settings to see what different versions of the compiled code
> can be generated, and running them to measure performance.
>
> If the compiler were smart enough, the programmer could convey
> the purpose of the code and the compiler would then know not
> to apply certain "optimizations" because they are really not
> optimizations for that particular purpose.  But if he could
> really explain his intent in some natural way, as opposed to
> specifically turning off specific optimizations, then the
> program that tries to understand this more natural description
> of intent would probably be able to answer his question in
> some more direct manner.
>
>  > (lambda (n)
>  >   (dotimes (i n)
>  >     (/ n 0)))
>  >
>  > Applying hoisting clearly gives different behavior. The solution,
>  > which I am currently implementing, is to also hoist out the
>  > condition, so that the hoisted computation runs only 0, or 1 times,
>
> By most definitions of computational "behavior" (which I'm arguing
> above are actually inadequate), generating different numbers of
> errors, which could potentially involve user interaction, would be
> viewed as different behavior.  Do you even have a real definition of
> what behaviors are considered equivalent by particular optimizations?

Re: gsoc: Loop invariant hoisting

[<don...@is...>]

Charles Zhang writes:
 > You make a good point, but the optimization definitely doesn't apply
 > in this case.

I understand, but this case is not really the point.
There are similar cases, e.g., measuring the time to do
various arithmetic operations, that would be affected.
For instance one of the results recorded in the comment
above the code I sent reports the time taken by code-char,
which if it isn't already recognized as side effect free,
certainly could be.  For that matter my test program
never even used the result, which is another excuse to
optimize out the computation.

And even if my example isn't affected YET, this optimization 
is just one step along a path that seems likely to affect
that example and pretty much all the other similar ones,
which I argue have legitimate uses.

The more general point is that "optimization" is based on a
model of the purpose of the code that is not always correct.
If the purpose of the code is to measure the time it takes to
add two numbers, perhaps of specific types and sizes, when those
types and sizes cannot be determined at compile time, then the
programmer may have to understand the compiler very well in order
to generate a sample test program to answer that question, and 
even with that understanding, generating that test program might
take significant effort.

For the foreseeable future the best solution might be some way
to control the optimizations, perhaps declarations indicating
which individual optimization mechanisms to use or not.  
I can also imagine trying to search the space of optimization 
settings to see what different versions of the compiled code 
can be generated, and running them to measure performance.

If the compiler were smart enough, the programmer could convey
the purpose of the code and the compiler would then know not
to apply certain "optimizations" because they are really not
optimizations for that particular purpose.  But if he could
really explain his intent in some natural way, as opposed to
specifically turning off specific optimizations, then the 
program that tries to understand this more natural description
of intent would probably be able to answer his question in 
some more direct manner.

 > (lambda (n)
 >   (dotimes (i n)
 >     (/ n 0)))
 > 
 > Applying hoisting clearly gives different behavior. The solution,
 > which I am currently implementing, is to also hoist out the
 > condition, so that the hoisted computation runs only 0, or 1 times,

By most definitions of computational "behavior" (which I'm arguing
above are actually inadequate), generating different numbers of
errors, which could potentially involve user interaction, would be
viewed as different behavior.  Do you even have a real definition of
what behaviors are considered equivalent by particular optimizations?

Re: gsoc: Loop invariant hoisting

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

You make a good point, but the optimization definitely doesn't apply
in this case.

System function calls are only deemed 'hoistable' when they are deemed
constant foldable by CLISP. (i.e. no side effects, pure function in
terms of its inputs) I hooked into the CLISP function
SYS::FUNCTION-SIDE-EFFECTS to access this information. This limits the
hoisting to arithmetic operations +, -, *, /, and others (IDENTITY
etc.) So this mostly benefits numeric code, where the optimization is
safe to apply.

One can also argue about the following:

(lambda (n)
  (dotimes (i n)
    (/ n 0)))

Applying hoisting clearly gives different behavior. The solution,
which I am currently implementing, is to also hoist out the condition,
so that the hoisted computation runs only 0, or 1 times, as opposed to
N times. This, along with checking that operations cannot give
ddifferent results and cannot side effect (i.e. constant foldable),.
should be enough to guarantee no changed behavior.

Charles

gsoc: Loop invariant hoisting

[<don...@is...>]

A possibly unintended consequence:

Here's an excerpt from a very old source file that I still use.

(compile (defun f(n stream)
 (loop for i below n do
  (setf (stream-element-type stream) '(unsigned-byte 8))
  (setf (stream-element-type stream) 'character))))
(time (f 100000 stream))
Real time: 1.487881 sec.
Run time: 1.47 sec.
Space: 2800000 Bytes
GC: 5, GC time: 0.09 sec.

Admittedly, that excerpt is in a comment, but the code and a whole
lot more very similar code has been run, and continues to be run 
in order to guide implementation and optimization decisions.

I suppose you could argue that such tests have always required the
programmer to be smarter than the compiler, but this has never 
been a serious issue - until NOW!

I'm reminded of the old star trek episode in which Mr Spock orders 
the computer to compute the exact value of PI, and imagining the
computer replying "I'm sorry Mr Spock, but you can't fool me with
that old trick..."

gsoc: Loop invariant hoisting

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

Hello clisp,

I wrote a loop hoisting pass, which means that the compiler can now
hoist loop invariant computations out.

For example, in
(cleavir-compile '(lambda (x y) (dotimes (i x)
                                           (print (+ x y)))))
the addition, which is loop invariant, is hoisted out of the loop and
only computed once.

Disassembly of function NIL
(CONST 0) = 0
(CONST 1) = NIL
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
18 byte-code instructions:
0     (LOAD&PUSH 2)
1     (LOAD&PUSH 2)
2     (CALLSR&PUSH 2 55)                  ; +
5     (CONST&PUSH 0)                      ; 0
6     L6
6     (LOAD&PUSH 0)
7     (LOAD&PUSH 5)
8     (CALLSR&PUSH 1 52)                  ; >=
11    (LOAD&JMPIF 0 L25)
14    (LOAD&PUSH 2)
15    (PUSH-UNBOUND 1)
17    (CALLS1 142)                        ; PRINT
19    (LOAD&INC&STORE 1)
21    (SKIP 1)
23    (JMP L6)
25    L25
25    (CONST 1)                           ; NIL
26    (SKIP&RET 6)

vs what CLISP produces:


Disassembly of function NIL
(CONST 0) = 0
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
15 byte-code instructions:
0     (CONST&PUSH 0)                      ; 0
1     (JMP L14)
3     L3
3     (LOAD&PUSH 3)
4     (LOAD&PUSH 3)
5     (CALLSR&PUSH 2 55)                  ; +
8     (PUSH-UNBOUND 1)
10    (CALLS1 142)                        ; PRINT
12    (LOAD&INC&STORE 0)
14    L14
14    (LOAD&PUSH 0)
15    (LOAD&PUSH 4)
16    (CALLSR&JMPIFNOT 1 52 L3)           ; >=
20    (NIL)
21    (SKIP&RET 4)

which computes the addition every loop.

This optimization is especially useful in heavily numeric code which
indexes arrays in multinested loops. For example, in the function

(lambda (array)
   (dotimes (i 5)
      (dotimes (j 7)
         (print (aref array (+ i 2) (+ j 4))))))

the computation (+ i 2) can be hoisted into the outer loop, since the
value doesn't change in the inner loop.

So Cleavir produces:

Disassembly of function NIL
(CONST 0) = 0
(CONST 1) = 5
(CONST 2) = 2
(CONST 3) = 0
(CONST 4) = 7
(CONST 5) = 4
(CONST 6) = NIL
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
35 byte-code instructions:
0     (CONST&PUSH 0)                      ; 0
1     L1
1     (LOAD&PUSH 0)
2     (CONST&PUSH 1)                      ; 5
3     (CALLSR&PUSH 1 52)                  ; >=
6     (LOAD&JMPIF 0 L51)
9     (LOAD&PUSH 1)
10    (CONST&PUSH 2)                      ; 2
11    (CALLSR&PUSH 2 55)                  ; +
14    (CONST&PUSH 3)                      ; 0
15    L15
15    (LOAD&PUSH 0)
16    (CONST&PUSH 4)                      ; 7
17    (CALLSR&PUSH 1 52)                  ; >=
20    (LOAD&JMPIF 0 L45)
23    (LOAD&PUSH 1)
24    (CONST&PUSH 5)                      ; 4
25    (CALLSR&PUSH 2 55)                  ; +
28    (LOAD&PUSH 7)
29    (LOAD&PUSH 4)
30    (LOAD&PUSH 2)
31    (CALLSR&PUSH 2 1)                   ; AREF
34    (LOAD&PUSH 0)
35    (PUSH-UNBOUND 1)
37    (CALLS1 142)                        ; PRINT
39    (LOAD&INC&STORE 3)
41    (SKIP 3)
43    (JMP L15)
45    L45
45    (LOAD&INC&STORE 4)
47    (SKIP 4)
49    (JMP L1)
51    L51
51    (CONST 6)                           ; NIL
52    (SKIP&RET 4)

whereas CLISP must calculate (+i 2) every time and produces:
Disassembly of function NIL
(CONST 0) = 0
(CONST 1) = 5
(CONST 2) = 7
(CONST 3) = 2
(CONST 4) = 4
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
29 byte-code instructions:
0     (CONST&PUSH 0)                      ; 0
1     (JMP L36)
3     L3
3     (CONST&PUSH 0)                      ; 0
4     (JMP L26)
6     L6
6     (LOAD&PUSH 3)
7     (CONST&PUSH 3)                      ; 2
8     (LOAD&PUSH 3)
9     (CALLSR&PUSH 2 55)                  ; +
12    (CONST&PUSH 4)                      ; 4
13    (LOAD&PUSH 3)
14    (CALLSR&PUSH 2 55)                  ; +
17    (CALLSR&PUSH 2 1)                   ; AREF
20    (PUSH-UNBOUND 1)
22    (CALLS1 142)                        ; PRINT
24    (LOAD&INC&STORE 0)
26    L26
26    (LOAD&PUSH 0)
27    (CONST&PUSH 2)                      ; 7
28    (CALLSR&JMPIFNOT 1 52 L6)           ; >=
32    (SKIP 1)
34    (LOAD&INC&STORE 0)
36    L36
36    (LOAD&PUSH 0)
37    (CONST&PUSH 1)                      ; 5
38    (CALLSR&JMPIFNOT 1 52 L3)           ; >=
42    (NIL)
43    (SKIP&RET 3)

As you can see, this transformation is a big improvement for nested
loops, since most time is spent in inner loops.

Charles

gsoc: Cleavir + CLISP is self hosting.

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

Hello clisp, Bruno, Sam,

After squashing lots of correctness issues, Cleavir + CLISP can now
self compile itself, and then do it again, and then do it again... In
fact, Cleavir can compile itself faster than the CLISP interpreted
Cleavir can!

(load "clisp/src/cleavir/load.lisp")
(setf cleavir-clisp::*use-cleavir* t)
(time (let ((sys::*load-compiling* t)) (load "clisp/src/cleavir/load.lisp")))
....
Real time: 71.04431 sec.
Run time: 70.8091 sec.
Space: 5706124304 Bytes
GC: 1264, GC time: 13.956973 sec.
(time (let ((sys::*load-compiling* t)) (load
"/home/charliezhang/clisp/src/cleavir/load.lisp")))
Real time: 52.189316 sec.
Run time: 52.014194 sec.
Space: 3788180744 Bytes
GC: 732, GC time: 9.725193 sec.

Charles

gsoc: Conditional constant propogation

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

Hello,

I wrote a conditional constant propagation flow analysis pass. Now
cleavir can generate code for situations like:

CLEAVIR-CLISP> (cleavir-compile '(lambda ()
                   (let ((x nil))
                     (values
                      (case 2
                        (1 (setq x 'a) 'w)
                        (2 (setq x 'b) 'y)
                        (t (setq x 'c) 'z))
                      x))))
#<COMPILED-FUNCTION NIL>
CLEAVIR-CLISP> (disassemble *)

Disassembly of function NIL
(CONST 0) = Y
(CONST 1) = B
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
4 byte-code instructions:
0     (CONST&PUSH 0)                      ; Y
1     (CONST&PUSH 1)                      ; B
2     (CALLSR 2 29)                       ; VALUES
5     (SKIP&RET 1)
NIL

vs

CLEAVIR-CLISP> (compile nil '(lambda () (declare (optimize speed))
                   (let ((x nil))
                     (values
                      (case 2
                        (1 (setq x 'a) 'w)
                        (2 (setq x 'b) 'y)
                        (t (setq x 'c) 'z))
                      x))))
#<COMPILED-FUNCTION NIL>
NIL
NIL
CLEAVIR-CLISP> (disassemble *)

Disassembly of function NIL
(CONST 0) = 2
(CONST 1) = 1
(CONST 2) = A
(CONST 3) = W
(CONST 4) = B
(CONST 5) = Y
(CONST 6) = C
(CONST 7) = Z
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
23 byte-code instructions:
0     (NIL&PUSH)
1     (CONST&PUSH 0)                      ; 2
2     (JMPIFEQTO 1 L18)                   ; 1
5     (CONST&PUSH 0)                      ; 2
6     (JMPIFEQTO 0 L23)                   ; 2
9     (CONST 6)                           ; C
10    (STORE 0)
11    (CONST 7)                           ; Z
12    L12
12    (PUSH)
13    (LOAD&PUSH 1)
14    (STACK-TO-MV 2)
16    (SKIP&RET 2)
18    L18
18    (CONST 2)                           ; A
19    (STORE 0)
20    (CONST 3)                           ; W
21    (JMP L12)
23    L23
23    (CONST 4)                           ; B
24    (STORE 0)
25    (CONST 5)                           ; Y
26    (JMP L12)

and

CLEAVIR-CLISP> (cleavir-compile '(lambda () (let ((i 0) a b c d)
                          (values
                           (and (setq a (setq i (1+ i)))
                                (setq b (setq i (1+ i)))
                                (setq c (setq i (1+ i)))
                                (setq d (setq i (1+ i))))
                           i a b c d))))
#<COMPILED-FUNCTION NIL>
CLEAVIR-CLISP> (disassemble *)

Disassembly of function NIL
(CONST 0) = 4
(CONST 1) = 4
(CONST 2) = 1
(CONST 3) = 2
(CONST 4) = 3
(CONST 5) = 4
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
8 byte-code instructions:
0     (CONST&PUSH 0)                      ; 4
1     (CONST&PUSH 1)                      ; 4
2     (CONST&PUSH 2)                      ; 1
3     (CONST&PUSH 3)                      ; 2
4     (CONST&PUSH 4)                      ; 3
5     (CONST&PUSH 5)                      ; 4
6     (CALLSR 6 29)                       ; VALUES
9     (SKIP&RET 1)

vs
CLEAVIR-CLISP> (compile nil '(lambda () (declare (optimize speed))
(let ((i 0) a b c d)
                          (values
                           (and (setq a (setq i (1+ i)))
                                (setq b (setq i (1+ i)))
                                (setq c (setq i (1+ i)))
                                (setq d (setq i (1+ i))))
                           i a b c d))))
#<COMPILED-FUNCTION NIL>
NIL
NIL
CLEAVIR-CLISP> (disassemble *)

Disassembly of function NIL
(CONST 0) = 0
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
25 byte-code instructions:
0     (CONST&PUSH 0)                      ; 0
1     (PUSH-NIL 4)
3     (LOAD&INC&STORE 4)
5     (STORE 3)
6     (JMPIFNOT L27)
8     (PUSH)
9     (CALLS2&STORE 177 4)                ; 1+
12    (STORE 2)
13    (JMPIFNOT L27)
15    (PUSH)
16    (CALLS2&STORE 177 4)                ; 1+
19    (STORE 1)
20    (JMPIFNOT L27)
22    (PUSH)
23    (CALLS2&STORE 177 4)                ; 1+
26    (STORE 0)
27    L27
27    (PUSH)
28    (LOAD&PUSH 5)
29    (LOAD&PUSH 5)
30    (LOAD&PUSH 5)
31    (LOAD&PUSH 5)
32    (LOAD&PUSH 5)
33    (STACK-TO-MV 6)
35    (SKIP&RET 6)

This type of optimization is particularly helpful for macro heavy
functions, which might have lots of easily compile time computed
information.

Charles

Possibilities for type inference in CLISP

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

Hello clisp, Bruno, Sam,

What would be an approach to leveraging type inference information
from Cleavir? SICL handles all the front end parsing and actual type
inference, but there are no backend VM instructions that actually
perform raw operations without type checking.

One possible approach would be to add some instructions in the virtual
machine for certain common operations like CAR, CDR, +, etc which
don't do any type checks at runtime. The compiler would have to
guarantee the types of the operands. These raw operations could be
emitted only when the compiler can prove the object is already of the
right type, so code space wouldn't be affected. Maybe there can be
seperate CALL instructions in the VM that turn off a type checking bit
in the runtime.

Thoughts? Would CLISP benefit performance-wise from such an
optimization? Is it feasible at the virtual machine level to add such
opcodes?

Charles

gsoc: 1/3 progress report

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

Hello clisp,

Cleavir on clisp is now integrated fairly well into CLISP. One can now
(setf cleavir-clisp::*use-cleavir* t) to turn on Cleavir. Any
subsequent calls to COMPILE and COMPILE-FILE will use Cleavir instead
of CLISP's compiler. Setting it to nil uses CLISP's compiler again.
Files compiled with Cleavir are fully FASL compatible with CLISP.

Enough is working to compile alexandria.

> (load "clisp/src/cleavir/load.lisp")
> (setf cleavir-clisp::*use-cleavir* t)
> (let ((sys::*load-compiling* t)) (asdf:load-system :alexandria :force t))
....
> (alexandria:ensure-car '(a b))
A

> (disassemble #'alexandria:ensure-car)

Disassembly of function NIL
(CONST 0) = NIL
(CONST 1) = CAR
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
15 byte-code instructions:
0     (LOAD&PUSH 1)
1     (CALLS2&PUSH 22)                    ; CONSP
3     (LOAD&PUSH 0)
4     (JMPIFEQTO 0 L9)                    ; NIL
7     (JMP L12)
9     L9
9     (LOAD 2)
10    (SKIP&RET 3)
12    L12
12    (CONST&PUSH 1)                      ; CAR
13    (CALLS1&PUSH 86)                    ; FDEFINITION
15    (LOAD&PUSH 0)
16    (LOAD&PUSH 4)
17    (FUNCALL 1)
19    (SKIP&RET 4)

Charles

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

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

I figured out the macroexpansion stuff, so now I can do stuff like
(macrolet ((%m (w) `(cadr ,w)))
    (let ((z (list 3 4)))
      (macrolet ((%m (x) `(car ,x)))
        (let ((y (list 1 2)))
          (values
           (%m y) (%m z)
           (setf (%m y) 6)
           (setf (%m z) 'a)
           y z)))))
correctly. I noticed that there is no way to make #<SPECIAL REFERENCE>
objects, as that's only marked in C, unlike SYSTEM::MAKE-MACRO, for
example. It's probably not something macroexpansion needs though.

On Sun, Jun 3, 2018 at 9:52 PM, Charles Zhang <ka...@be...> wrote:
> 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



-- 
Class of 2021

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

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

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

Re: BDB module, Berkeley-DB version support

[<Joe...@t-...>]

Hi,

Sky Hester wrote:
>I’m trying to get up and running with the BDB module, but I’m having trouble.
>Specifically, I’m stuck at the stage of compiling Berkeley-DB <=4.8 on OSX, which appears to be the latest supported release.

>Is the information on this page still valid?
> https://clisp.sourceforge.io/impnotes/berkeley-db.html
I fear not. It mentions 4.8 -- yours specifically -- as latest supported version, however this module's history:

https://gitlab.com/gnu-clisp/clisp/commits/master/modules/berkeley-db

... exhibits "update berkeley-db to 5.1" in 2012:
https://gitlab.com/gnu-clisp/clisp/commit/cd73e9634b729d749b289952a8c4d72224eb184c 

Perhaps that broke compatibility with 4.8 or OSX? It should not, since the commit includes in src/NEWS:
 * Module berkeley-db now supports Berkeley-DB 5.1.
  (Older versions are, of course, still supported).
  See <http://clisp.cons.org/impnotes/berkeley-db.html> for details.

> https://clisp.sourceforge.io/impnotes/berkeley-db.html
That page cannot include the above change, because, as its parent
https://clisp.sourceforge.io/impnotes/index.html
says, it documents clisp 2.49 from 2010 and has not been regenerated/updated yet.

Can you sort of revert that 2012 commit and see if that helps?

>I see recent commits to dev sources in the bdb module directory, but
>it’s not obvious to me whether Berkeley-DB >4.8 is supported.
Which ones? I only saw that 2012 change as specific to Berkeley DB. Others are
About general changes, e.g. configure, gnulib or module initialization.

Regards,
	Jörg

Re: MT crashes

[Blake M. <bl...@mc...>]

It's too bad that there is not more attention paid to the
native multi-threading aspect.  With so much being done over the net these
days, not supporting native threads mostly leaves you in the dust.

Blake McBride



On Thu, May 24, 2018 at 6:50 PM, Don Cohen <
don...@is...> wrote:

>
> I hoped to hear something back from my last post on this subject (Apr 30).
> I don't have a small example, but I think I have a repeatable example.
> It seems that fedora 24 saves a lot of context in addition to the core
> dump, though it wasn't easy to find it all.  One of the files,
> named "exploitable" says:
> Likely crash reason: Jump to an invalid address
> Exploitable rating (0-9 scale): 6
>
> I suppose this is the same info as the fact that the program
> ended with
>  " Segmentation fault (core dumped)
>
> Another, core_backtrace:
> {   "signal": 11
> ,   "executable": "/home/tmp1/ap5-2.49.93+MT%"
> ,   "stacktrace":
>       [ {   "crash_thread": true
>         ,   "frames":
>               [ {   "address": 4854162
>                 ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
>                 ,   "build_id_offset": 659858
>                 ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
>                 } ]
>         }
>       , {   "frames":
>               [ {   "address": 140191862768419
>                 ,   "build_id": "7e7c0136995d74da5288c3f0a0e53dd72e53d7d4"
>                 ,   "build_id_offset": 1020707
>                 ,   "function_name": "__select"
>                 ,   "file_name": "/lib64/libc.so.6"
>                 }
>               , {   "address": 5385773
>                 ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
>                 ,   "build_id_offset": 1191469
>                 ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
>                 } ]
>         }
>       , {   "frames":
>               [ {   "address": 140191865756134
>                 ,   "build_id": "a6b759a4fe570ed140d81151888da045a3db488e"
>                 ,   "build_id_offset": 68070
>                 ,   "function_name": "sigwait"
>                 ,   "file_name": "/lib64/libpthread.so.0"
>                 }
>               , {   "address": 4736398
>                 ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
>                 ,   "build_id_offset": 542094
>                 ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
>                 } ]
>         }
>       , {   "frames":
>               [ {   "address": 140191865753581
>                 ,   "build_id": "a6b759a4fe570ed140d81151888da045a3db488e"
>                 ,   "build_id_offset": 65517
>                 ,   "function_name": "accept"
>                 ,   "file_name": "/lib64/libpthread.so.0"
>                 }
>               , {   "address": 5455784
>                 ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
>                 ,   "build_id_offset": 1261480
>                 ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
>                 } ]
>         }
>       , {   "frames":
>               [ {   "address": 140191862768419
>                 ,   "build_id": "7e7c0136995d74da5288c3f0a0e53dd72e53d7d4"
>                 ,   "build_id_offset": 1020707
>                 ,   "function_name": "__select"
>                 ,   "file_name": "/lib64/libc.so.6"
>                 }
>               , {   "address": 6292742
>                 ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
>                 ,   "build_id_offset": 2098438
>                 ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
>                 } ]
>         } ]
> }
>
>
> I'm hoping someone can give me advice on how to look for the problem,
> or better, how to help some else who understands it all better than I
> do to look for the problem.
>
> ------------------------------------------------------------
> ------------------
> 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
> cli...@li...
> https://lists.sourceforge.net/lists/listinfo/clisp-devel
>

BDB module, Berkeley-DB version support

[Sky H. <sky...@gm...>]

Hello,

I’m trying to get up and running with the BDB module, but I’m having trouble. Specifically, I’m stuck at the stage of compiling Berkeley-DB <=4.8 on OSX, which appears to be the latest supported release. It seems sensible to try to use the latest version which is still compatible with the module.

Is the information on this page still valid?

https://clisp.sourceforge.io/impnotes/berkeley-db.html <https://clisp.sourceforge.io/impnotes/berkeley-db.html>

I see recent commits to dev sources in the bdb module directory, but it’s not obvious to me whether Berkeley-DB >4.8 is supported.

-Sky

MT crashes

[<don...@is...>]

I hoped to hear something back from my last post on this subject (Apr 30).
I don't have a small example, but I think I have a repeatable example.
It seems that fedora 24 saves a lot of context in addition to the core
dump, though it wasn't easy to find it all.  One of the files,
named "exploitable" says:
Likely crash reason: Jump to an invalid address
Exploitable rating (0-9 scale): 6

I suppose this is the same info as the fact that the program
ended with 
 " Segmentation fault (core dumped)

Another, core_backtrace:
{   "signal": 11
,   "executable": "/home/tmp1/ap5-2.49.93+MT%"
,   "stacktrace":
      [ {   "crash_thread": true
        ,   "frames":
              [ {   "address": 4854162
                ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
                ,   "build_id_offset": 659858
                ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
                } ]
        }
      , {   "frames":
              [ {   "address": 140191862768419
                ,   "build_id": "7e7c0136995d74da5288c3f0a0e53dd72e53d7d4"
                ,   "build_id_offset": 1020707
                ,   "function_name": "__select"
                ,   "file_name": "/lib64/libc.so.6"
                }
              , {   "address": 5385773
                ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
                ,   "build_id_offset": 1191469
                ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
                } ]
        }
      , {   "frames":
              [ {   "address": 140191865756134
                ,   "build_id": "a6b759a4fe570ed140d81151888da045a3db488e"
                ,   "build_id_offset": 68070
                ,   "function_name": "sigwait"
                ,   "file_name": "/lib64/libpthread.so.0"
                }
              , {   "address": 4736398
                ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
                ,   "build_id_offset": 542094
                ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
                } ]
        }
      , {   "frames":
              [ {   "address": 140191865753581
                ,   "build_id": "a6b759a4fe570ed140d81151888da045a3db488e"
                ,   "build_id_offset": 65517
                ,   "function_name": "accept"
                ,   "file_name": "/lib64/libpthread.so.0"
                }
              , {   "address": 5455784
                ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
                ,   "build_id_offset": 1261480
                ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
                } ]
        }
      , {   "frames":
              [ {   "address": 140191862768419
                ,   "build_id": "7e7c0136995d74da5288c3f0a0e53dd72e53d7d4"
                ,   "build_id_offset": 1020707
                ,   "function_name": "__select"
                ,   "file_name": "/lib64/libc.so.6"
                }
              , {   "address": 6292742
                ,   "build_id": "76df05a878e27f6ee7cc5ed39793f74585c42684"
                ,   "build_id_offset": 2098438
                ,   "file_name": "/home/tmp1/ap5-2.49.93+MT% (deleted)"
                } ]
        } ]
}


I'm hoping someone can give me advice on how to look for the problem,
or better, how to help some else who understands it all better than I
do to look for the problem.

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

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

[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: grabbing clisp environment info, cltl2

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

Hi Charles,

> 'front-end' compilation needs to take place in a lexical environment
> in order to get variable, function, optimize information etc as well
> as to hook into macroexpanders. However, I have found that CLISP does
> not adhere to the CLtL2 environment interface.

The environment interface is not available as a "modern", "abstract"
interface, only as a data structure with accessors:

  - The concepts of these environments are described in lispbibl.d
    around line 14000.

  - These environments mix lexical and dynamic information; if you
    want to ignore the dynamic information, do so carefully.

  - The variables environment has Lisp code that accesses it in:
    venv-assoc (init.lisp), venv-search (compiler.lisp).

  - The functions/macros environment has Lisp code that accesses it in:
    fenv-assoc (init.lisp), fenv-search (compiler.lisp).

  - The block environment has Lisp code that accesses it in:
    benv-search (compiler.lisp).

  - The tagbody/go environment has Lisp code that accesses it in:
    genv-search (compiler.lisp).

  - The declarations environment has Lisp code that accesses it in:
    declared-notinline, declared-constant-notinline, declared-declaration,
    declared-optimize (all compiler.lisp).

Note: These environment structures are also accessed from the interpreter
(C code in eval.d and control.d). This means that if you extend these
structures to accommodate objects built by SICL, the C code may need an
update as well. This is because the compiler has to access interpreter
environments, as in

  (let ((x 5))
    (declare (special x)) ; This declaration has an effect on the function!
    (locally (declare (compile))
      (lambda () (incf x))))

With the '(declare (special x))':
0     (GETVALUE&PUSH 0)                   ; X
2     (CALLS2 177)                        ; 1+
4     (SETVALUE 0)                        ; X
6     (SKIP&RET 1)

Without the '(declare (special x))':
0     (CONST&PUSH 0)                      ; #(X 5 NIL)
1     (CONST 1)                           ; 1
2     (SVREF)
3     (PUSH)
4     (CALLS2&PUSH 177)                   ; 1+
6     (CONST&PUSH 0)                      ; #(X 5 NIL)
7     (CONST 1)                           ; 1
8     (SVSET)
9     (SKIP&RET 1)

> Additionally,
> (ext:the-environment) does not seem to give compile time lexical
> environment information, only runtime environment information.

Yes, (ext:the-environment) has the same mix between lexical and dynamic
information.

> I couldn't find any interface to tell whether
> symbols were declared special with defvar.

There is SYS::SPECIAL-VARIABLE-P, defined in eval.d, and
CONSTANTP, defined in control.d. Both of these access special bits in
the symbol (cf. constant_var_p, special_var_p in lispbibl.d).

> Any way of getting CLtL2-esque information here? Maybe buried in a codewalker?

It is surely possible to implement the functions from
https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node102.html
- except for augment-environment - in a straightforward manner.

augment-environment, however, is not so adapted for clisp, because it would
be consing more than is desirable.

Note that this interface did not make it into ANSI CL, see
http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Issues/iss343.html

Bruno

Re: #\U<hex> syntax

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

Hi Sam,

> CLISP supports the #\U<hex> read syntax for Unicode characters but does
> not advertise it (instead, the official syntax is #\Code<decimal>).
> 
> Also, the <hex> _must_ be 5 or 9 characters long (padded with 0s if
> necessary), and the syntax is implemented as if it were a character name
> lookup.
> 
> I wonder if you think it might be a good idea to
> 1. Relax the 5/9 length requirement
> 2. Advertise the syntax in
> https://clisp.sourceforge.io/impnotes/sharpsign.html#sharpsign-backslash

Considering that
  * The widespread practice (starting in unicode.org) is to write
      - characters with code points < #x10000 with 4 digits
      - characters with code points >= #x10000 with the minimum possible
        digits (no leading zeroes),
  * For interoperability of data files with Sexprs between CL implementations
    it is necessary that the preferred name printed by one implementation is
    understood by the other implementations,
  * sbcl allows leading zeroes on input

I find that it would be useful if:

  1) When printing a Unicode character that has no explicit name (e.g. #\U061D)
     clisp prints 4 or more digits (with no leading zero digits for codes
     >= #x10000). [This is unlike sbcl, which prints #\U061D as #\U61D.)
     There's no basis for the current behaviour of clisp:
       (code-char 84321) => #\U00014961
     because 32-bit integers are not a primordial type in Lisp.

  2) When parsing a Unicode character, leading zeroes don't matter. (This
     achieves interoperability with SBCL, except for very few specific characters
     such as #\Bell.)

  3) We document this. (This is necessary because this syntax can occur as
     output of PRINT and WRITE.)

Bruno

#\U<hex> syntax

[Sam S. <sd...@gn...>]

Hi Bruno,

My question is inspired by https://stackoverflow.com/q/50413748/850781.

CLISP supports the #\U<hex> read syntax for Unicode characters but does
not advertise it (instead, the official syntax is #\Code<decimal>).

Also, the <hex> _must_ be 5 or 9 characters long (padded with 0s if
necessary), and the syntax is implemented as if it were a character name
lookup.

I wonder if you think it might be a good idea to
1. Relax the 5/9 length requirement
2. Advertise the syntax in
https://clisp.sourceforge.io/impnotes/sharpsign.html#sharpsign-backslash

Thanks.

-- 
Sam Steingold (http://sds.podval.org/) on darwin Ns 10.3.1561
http://childpsy.net http://calmchildstories.com http://steingoldpsychology.com
https://ffii.org http://memri.org http://islamexposedonline.com
Lisp is a language for doing what you've been told is impossible. - Kent Pitman

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

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