1 files changed, 185 insertions, 103 deletions

diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp
index d00423edf5..341cac64c7 100644
--- a/lib/Transforms/Scalar/Reassociate.cpp
+++ b/lib/Transforms/Scalar/Reassociate.cpp
@@ -31,6 +31,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/Statistic.h"
+#include <algorithm>
 using namespace llvm;
 
 namespace {
@@ -38,9 +39,19 @@ namespace {
   Statistic<> NumChanged("reassociate","Number of insts reassociated");
   Statistic<> NumSwapped("reassociate","Number of insts with operands swapped");
 
+  struct ValueEntry {
+    unsigned Rank;
+    Value *Op;
+    ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
+  };
+  inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
+    return LHS.Rank > RHS.Rank;   // Sort so that highest rank goes to start.
+  }
+
   class Reassociate : public FunctionPass {
     std::map<BasicBlock*, unsigned> RankMap;
     std::map<Value*, unsigned> ValueRankMap;
+    bool MadeChange;
   public:
     bool runOnFunction(Function &F);
 
@@ -50,8 +61,11 @@ namespace {
   private:
     void BuildRankMap(Function &F);
     unsigned getRank(Value *V);
-    bool ReassociateExpr(BinaryOperator *I);
-    bool ReassociateBB(BasicBlock *BB);
+    void RewriteExprTree(BinaryOperator *I, unsigned Idx,
+                         std::vector<ValueEntry> &Ops);
+    void LinearizeExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops);
+    void LinearizeExpr(BinaryOperator *I);
+    void ReassociateBB(BasicBlock *BB);
   };
 
   RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions");
@@ -105,67 +119,135 @@ unsigned Reassociate::getRank(Value *V) {
   return CachedRank = Rank+1;
 }
 
+/// isReassociableOp - Return true if V is an instruction of the specified
+/// opcode and if it only has one use.
+static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) {
+  if (V->hasOneUse() && isa<Instruction>(V) &&
+      cast<Instruction>(V)->getOpcode() == Opcode)
+    return cast<BinaryOperator>(V);
+  return 0;
+}
 
-bool Reassociate::ReassociateExpr(BinaryOperator *I) {
-  Value *LHS = I->getOperand(0);
-  Value *RHS = I->getOperand(1);
-  unsigned LHSRank = getRank(LHS);
-  unsigned RHSRank = getRank(RHS);
+// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'.
+// Note that if D is also part of the expression tree that we recurse to
+// linearize it as well.  Besides that case, this does not recurse into A,B, or
+// C.
+void Reassociate::LinearizeExpr(BinaryOperator *I) {
+  BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0));
+  BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1));
+  assert(isReassociableOp(LHS, I->getOpcode()) && 
+         isReassociableOp(RHS, I->getOpcode()) &&
+         "Not an expression that needs linearization?");
+
+  DEBUG(std::cerr << "Linear" << *LHS << *RHS << *I);
+
+  // Move the RHS instruction to live immediately before I, avoiding breaking
+  // dominator properties.
+  I->getParent()->getInstList().splice(I, RHS->getParent()->getInstList(), RHS);
+
+  // Move operands around to do the linearization.
+  I->setOperand(1, RHS->getOperand(0));
+  RHS->setOperand(0, LHS);
+  I->setOperand(0, RHS);
+  
+  ++NumLinear;
+  MadeChange = true;
+  DEBUG(std::cerr << "Linearized: " << *I);
 
-  bool Changed = false;
+  // If D is part of this expression tree, tail recurse.
+  if (isReassociableOp(I->getOperand(1), I->getOpcode()))
+    LinearizeExpr(I);
+}
 
-  // Make sure the LHS of the operand always has the greater rank...
-  if (LHSRank < RHSRank) {
-    bool Success = !I->swapOperands();
-    assert(Success && "swapOperands failed");
 
-    std::swap(LHS, RHS);
-    std::swap(LHSRank, RHSRank);
-    Changed = true;
-    ++NumSwapped;
-    DEBUG(std::cerr << "Transposed: " << *I
-          /* << " Result BB: " << I->getParent()*/);
+/// LinearizeExprTree - Given an associative binary expression tree, traverse
+/// all of the uses putting it into canonical form.  This forces a left-linear
+/// form of the the expression (((a+b)+c)+d), and collects information about the
+/// rank of the non-tree operands.
+///
+/// This returns the rank of the RHS operand, which is known to be the highest
+/// rank value in the expression tree.
+///
+void Reassociate::LinearizeExprTree(BinaryOperator *I,
+                                    std::vector<ValueEntry> &Ops) {
+  Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
+  unsigned Opcode = I->getOpcode();
+
+  // First step, linearize the expression if it is in ((A+B)+(C+D)) form.
+  BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode);
+  BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode);
+
+  if (!LHSBO) {
+    if (!RHSBO) {
+      // Neither the LHS or RHS as part of the tree, thus this is a leaf.  As
+      // such, just remember these operands and their rank.
+      Ops.push_back(ValueEntry(getRank(LHS), LHS));
+      Ops.push_back(ValueEntry(getRank(RHS), RHS));
+      return;
+    } else {
+      // Turn X+(Y+Z) -> (Y+Z)+X
+      std::swap(LHSBO, RHSBO);
+      std::swap(LHS, RHS);
+      bool Success = !I->swapOperands();
+      assert(Success && "swapOperands failed");
+      MadeChange = true;
+    }
+  } else if (RHSBO) {
+    // Turn (A+B)+(C+D) -> (((A+B)+C)+D).  This guarantees the the RHS is not
+    // part of the expression tree.
+    LinearizeExpr(I);
+    LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0));
+    RHS = I->getOperand(1);
+    RHSBO = 0;
   }
 
-  // If the LHS is the same operator as the current one is, and if we are the
-  // only expression using it...
-  //
-  if (BinaryOperator *LHSI = dyn_cast<BinaryOperator>(LHS))
-    if (LHSI->getOpcode() == I->getOpcode() && LHSI->hasOneUse()) {
-      // If the rank of our current RHS is less than the rank of the LHS's LHS,
-      // then we reassociate the two instructions...
-
-      unsigned TakeOp = 0;
-      if (BinaryOperator *IOp = dyn_cast<BinaryOperator>(LHSI->getOperand(0)))
-        if (IOp->getOpcode() == LHSI->getOpcode())
-          TakeOp = 1;   // Hoist out non-tree portion
-
-      if (RHSRank < getRank(LHSI->getOperand(TakeOp))) {
-        // Convert ((a + 12) + 10) into (a + (12 + 10))
-        I->setOperand(0, LHSI->getOperand(TakeOp));
-        LHSI->setOperand(TakeOp, RHS);
-        I->setOperand(1, LHSI);
-
-        // Move the LHS expression forward, to ensure that it is dominated by
-        // its operands.
-        LHSI->getParent()->getInstList().remove(LHSI);
-        I->getParent()->getInstList().insert(I, LHSI);
-
-        ++NumChanged;
-        DEBUG(std::cerr << "Reassociated: " << *I/* << " Result BB: "
-                                                   << I->getParent()*/);
-
-        // Since we modified the RHS instruction, make sure that we recheck it.
-        ReassociateExpr(LHSI);
-        ReassociateExpr(I);
-        return true;
-      }
-    }
+  // Okay, now we know that the LHS is a nested expression and that the RHS is
+  // not.  Perform reassociation.
+  assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!");
 
-  return Changed;
+  // Move LHS right before I to make sure that the tree expression dominates all
+  // values.
+  I->getParent()->getInstList().splice(I,
+                                      LHSBO->getParent()->getInstList(), LHSBO);
+
+  // Linearize the expression tree on the LHS.
+  LinearizeExprTree(LHSBO, Ops);
+
+  // Remember the RHS operand and its rank.
+  Ops.push_back(ValueEntry(getRank(RHS), RHS));
+}
+
+// RewriteExprTree - Now that the operands for this expression tree are
+// linearized and optimized, emit them in-order.  This function is written to be
+// tail recursive.
+void Reassociate::RewriteExprTree(BinaryOperator *I, unsigned i,
+                                  std::vector<ValueEntry> &Ops) {
+  if (i+2 == Ops.size()) {
+    if (I->getOperand(0) != Ops[i].Op ||
+        I->getOperand(1) != Ops[i+1].Op) {
+      DEBUG(std::cerr << "RA: " << *I);
+      I->setOperand(0, Ops[i].Op);
+      I->setOperand(1, Ops[i+1].Op);
+      DEBUG(std::cerr << "TO: " << *I);
+      MadeChange = true;
+      ++NumChanged;
+    }
+    return;
+  }
+  assert(i+2 < Ops.size() && "Ops index out of range!");
+
+  if (I->getOperand(1) != Ops[i].Op) {
+    DEBUG(std::cerr << "RA: " << *I);
+    I->setOperand(1, Ops[i].Op);
+    DEBUG(std::cerr << "TO: " << *I);
+    MadeChange = true;
+    ++NumChanged;
+  }
+  RewriteExprTree(cast<BinaryOperator>(I->getOperand(0)), i+1, Ops);
 }
 
 
+
 // NegateValue - Insert instructions before the instruction pointed to by BI,
 // that computes the negative version of the value specified.  The negative
 // version of the value is returned, and BI is left pointing at the instruction
@@ -201,13 +283,6 @@ static Value *NegateValue(Value *V, Instruction *BI) {
   return BinaryOperator::createNeg(V, V->getName() + ".neg", BI);
 }
 
-/// isReassociableOp - Return true if V is an instruction of the specified
-/// opcode and if it only has one use.
-static bool isReassociableOp(Value *V, unsigned Opcode) {
-  return V->hasOneUse() && isa<Instruction>(V) &&
-         cast<Instruction>(V)->getOpcode() == Opcode;
-}
-
 /// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is
 /// only used by an add, transform this into (X+(0-Y)) to promote better
 /// reassociation.
@@ -265,63 +340,70 @@ static Instruction *ConvertShiftToMul(Instruction *Shl) {
 
 /// ReassociateBB - Inspect all of the instructions in this basic block,
 /// reassociating them as we go.
-bool Reassociate::ReassociateBB(BasicBlock *BB) {
-  bool Changed = false;
+void Reassociate::ReassociateBB(BasicBlock *BB) {
   for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) {
     // If this is a subtract instruction which is not already in negate form,
     // see if we can convert it to X+-Y.
     if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI))
       if (Instruction *NI = BreakUpSubtract(BI)) {
-        Changed = true;
+        MadeChange = true;
         BI = NI;
       }
     if (BI->getOpcode() == Instruction::Shl &&
         isa<ConstantInt>(BI->getOperand(1)))
       if (Instruction *NI = ConvertShiftToMul(BI)) {
-        Changed = true;
+        MadeChange = true;
         BI = NI;
       }
 
-    // If this instruction is a commutative binary operator, and the ranks of
-    // the two operands are sorted incorrectly, fix it now.
-    //
-    if (BI->isAssociative()) {
-      DEBUG(std::cerr << "Reassociating: " << *BI);
-      BinaryOperator *I = cast<BinaryOperator>(BI);
-      if (!I->use_empty()) {
-        // Make sure that we don't have a tree-shaped computation.  If we do,
-        // linearize it.  Convert (A+B)+(C+D) into ((A+B)+C)+D
-        //
-        Instruction *LHSI = dyn_cast<Instruction>(I->getOperand(0));
-        Instruction *RHSI = dyn_cast<Instruction>(I->getOperand(1));
-        if (LHSI && (int)LHSI->getOpcode() == I->getOpcode() &&
-            RHSI && (int)RHSI->getOpcode() == I->getOpcode() &&
-            RHSI->hasOneUse()) {
-          // Insert a new temporary instruction... (A+B)+C
-          BinaryOperator *Tmp = BinaryOperator::create(I->getOpcode(), LHSI,
-                                                       RHSI->getOperand(0),
-                                                       RHSI->getName()+".ra",
-                                                       BI);
-          BI = Tmp;
-          I->setOperand(0, Tmp);
-          I->setOperand(1, RHSI->getOperand(1));
-
-          // Process the temporary instruction for reassociation now.
-          I = Tmp;
-          ++NumLinear;
-          Changed = true;
-          DEBUG(std::cerr << "Linearized: " << *I/* << " Result BB: " << BB*/);
+    // If this instruction is a commutative binary operator, process it.
+    if (!BI->isAssociative()) continue;
+    BinaryOperator *I = cast<BinaryOperator>(BI);
+    
+    // If this is an interior node of a reassociable tree, ignore it until we
+    // get to the root of the tree, to avoid N^2 analysis.
+    if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode()))
+      continue;
+
+    // First, walk the expression tree, linearizing the tree, collecting 
+    std::vector<ValueEntry> Ops;
+    LinearizeExprTree(I, Ops);
+
+    // Now that we have linearized the tree to a list and have gathered all of
+    // the operands and their ranks, sort the operands by their rank.  Use a
+    // stable_sort so that values with equal ranks will have their relative
+    // positions maintained (and so the compiler is deterministic).  Note that
+    // this sorts so that the highest ranking values end up at the beginning of
+    // the vector.
+    std::stable_sort(Ops.begin(), Ops.end());
+
+    // Now that we have the linearized expression tree, try to optimize it.
+    // Start by folding any constants that we found.
+  FoldConstants:
+    if (Ops.size() > 1)
+      if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op))
+        if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) {
+          Ops.pop_back();
+          Ops.back().Op = ConstantExpr::get(I->getOpcode(), V1, V2);
+          goto FoldConstants;
         }
 
-        // Make sure that this expression is correctly reassociated with respect
-        // to it's used values...
-        //
-        Changed |= ReassociateExpr(I);
-      }
+    // FIXME: Handle destructive annihilation here.  Ensure RANK(neg(x)) ==
+    // RANK(x) [and not].  Handle case when Cst = 0 and op = AND f.e.
+
+    // FIXME: Handle +0,*1,&~0,... at end of the list.
+
+
+    if (Ops.size() == 1) {
+      // This expression tree simplified to something that isn't a tree,
+      // eliminate it.
+      I->replaceAllUsesWith(Ops[0].Op);
+    } else {
+      // Now that we ordered and optimized the expressions, splat them back into
+      // the expression tree, removing any unneeded nodes.
+      RewriteExprTree(I, 0, Ops);
     }
   }
-
-  return Changed;
 }
 
 
@@ -329,13 +411,13 @@ bool Reassociate::runOnFunction(Function &F) {
   // Recalculate the rank map for F
   BuildRankMap(F);
 
-  bool Changed = false;
+  MadeChange = false;
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
-    Changed |= ReassociateBB(FI);
+    ReassociateBB(FI);
 
   // We are done with the rank map...
   RankMap.clear();
   ValueRankMap.clear();
-  return Changed;
+  return MadeChange;
 }