[LLVMbugs] Reassociation Transform

[Chris Lattner]

>   I'm working on PRE for the cs426 project, and I noticed that
> reassociation seems to be broken.

Very true, it is close to working, but is doesn't really even attempt to
get the dominance properties right yet.  It was on my "post-pldi" todo
list.  :)

> Since I think reassociation will be necessary for PRE to achieve
> impressive results on real programs, I decided to fix it.  I think I
> have it pretty much working, and it passes all of the regressions.

Very nice.  That is pretty cool.  :)

If you want a nice set of stress tests (which I recommend trying out), I
put a bunch of bytecode files into the http://llvm.cs.uiuc.edu/LLVMPrograms
directory.  Note that these files are only for internal use, so please do
not redistribute them.

Some of these bytecode files don't work (because they are miscompiled by
an LLVM transformation or there is an FE bug), but you can at least use
them to see if your reassociate pass produces legal LLVM code.  You can
also use the '-time-passes' option to see how fast your transformation is.
Some of these bytecode files are nice large testcases (especially in the
SPEC directory).

> Some issues of interest:
>
>    1. Contrary to the comment in Reassociate.cpp, floating point
>       addition and multiplication _are_ commutative, although they are

Are you sure of that?  I was intentionally trying to be very conservative
W.R.T IEEE conformance.  Is (+0)*(-0) == (-0)*(+0)?  What about all of the
other bad cases?  Can you point me to anything somewhat official that
agrees with this?

>       not associative.  Associative operators are Add, Mul, And, Or,
>       Xor, when not applied to floating point types.  Commutative
>       operators the associative operators plus SetEQ and SetNE, when
>       applied to any type.

This sounds right.

>    2. For consistency, I added two methods to the Instruction class --
>       "bool isAssociative() const" and "bool isCommutative() const" so
>       that there is a single location where knowledge about
>       commutativity and associativity lives.  I changed Reassociate.cpp,
>       ValueNumbering.cpp, and swapOperands in iOperators.cpp to use
>       these new methods.

Ok, sounds great!  In general it would be best to add a comment above the
method in the header file to explain what it does, but I can take care of
that:

http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021028/001168.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021028/001169.html

I'll take a look at the reassociate patches next.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/