[LLVMbugs] Reassociation Transform

[Casey Carter]

  I'm working on PRE for the cs426 project, and I noticed that 
reassociation seems to be broken.  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.

Some issues of interest:

   1. Contrary to the comment in Reassociate.cpp, floating point
      addition and multiplication _are_ commutative, although they are
      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.
   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.  
   3. ReassociateExpr was changing (a+b)+c into a+(b+c), which is a
      problem of the definition of c does not dominate (b+c).  I fixed
      this by creating a new instruction for (b+c) and inserting it just
      before the instruction that calculates a+(b+c).  I'm confident
      that this approach is correct, but may increase register pressure
      since it may extend the live ranges of b&c.
   4. I wiggled the main loop in ReassociateBB around a bit to try and
      preserve instruction names.  Placing the Sub test before the
      reassociate test makes the iterator manipulation simpler.

Let me know what you think.


-- 
Casey Carter
Casey at Carter.net
ccarter at uiuc.edu
AIM: cartec69

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: reassociate.patch
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20021030/d8134846/attachment.ksh>