Rewrite the guts of the reassociate pass to be more efficient and logical. Instead

of trying to do local reassociation tweaks at each level, only process an expression
tree once (at its root).  This does not improve the reassociation pass in any real way.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21768 91177308-0d34-0410-b5e6-96231b3b80d8

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;
 }