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?