Re: gsoc: Loop invariant hoisting

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.

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