CSE simple binary expressions when they are inserted. This makes LSR produce

less huge code that needs to be cleaned up by sdisel.

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

diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index fad2da9b9b6ab0f562aefc4e45c1a846218d9d68..664c9d397ff9263214af5efe4536d31fe6b0e288 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -89,7 +89,10 @@ namespace llvm {
     /// we can to share the casts.
     static Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V, 
                                  const Type *Ty);
-    
+    /// InsertBinop - Insert the specified binary operator, doing a small amount
+    /// of work to avoid inserting an obviously redundant operation.
+    static Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
+                              Value *RHS, Instruction *InsertPt);
   protected:
     Value *expand(SCEV *S) {
       // Check to see if we already expanded this.
@@ -141,8 +144,8 @@ namespace llvm {
 
       // Emit a bunch of add instructions
       for (int i = S->getNumOperands()-2; i >= 0; --i)
-        V = BinaryOperator::createAdd(V, expandInTy(S->getOperand(i), Ty),
-                                      "tmp.", InsertPt);
+        V = InsertBinop(Instruction::Add, V, expandInTy(S->getOperand(i), Ty),
+                        InsertPt);
       return V;
     }
 
@@ -152,7 +155,7 @@ namespace llvm {
       const Type *Ty = S->getType();
       Value *LHS = expandInTy(S->getLHS(), Ty);
       Value *RHS = expandInTy(S->getRHS(), Ty);
-      return BinaryOperator::createSDiv(LHS, RHS, "tmp.", InsertPt);
+      return InsertBinop(Instruction::SDiv, LHS, RHS, InsertPt);
     }
 
     Value *visitAddRecExpr(SCEVAddRecExpr *S);

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index a50d572f68a0b238beee43a429b451df21f86ddf..a9b88c1155e8bbde9d46a0e33a74a749c7a03ea4 100644 (file)
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -68,6 +68,25 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
   return CastInst::create(opcode, V, Ty, V->getName(), IP);
 }
 
+/// InsertBinop - Insert the specified binary operator, doing a small amount
+/// of work to avoid inserting an obviously redundant operation.
+Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
+                                 Value *RHS, Instruction *InsertPt) {
+  // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
+  unsigned ScanLimit = 6;
+  for (BasicBlock::iterator IP = InsertPt, E = InsertPt->getParent()->begin();
+       ScanLimit; --IP, --ScanLimit) {
+    if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(IP))
+      if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS &&
+          BinOp->getOperand(1) == RHS)
+        return BinOp;
+    if (IP == E) break;
+  }
+
+  // If we don't have 
+  return BinaryOperator::create(Opcode, LHS, RHS, "tmp.", InsertPt);
+}
+
 Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
   const Type *Ty = S->getType();
   int FirstOp = 0;  // Set if we should emit a subtract.
@@ -80,11 +99,12 @@ Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
 
   // Emit a bunch of multiply instructions
   for (; i >= FirstOp; --i)
-    V = BinaryOperator::createMul(V, expandInTy(S->getOperand(i), Ty),
-                                  "tmp.", InsertPt);
+    V = InsertBinop(Instruction::Mul, V, expandInTy(S->getOperand(i), Ty),
+                    InsertPt);
   // -1 * ...  --->  0 - ...
   if (FirstOp == 1)
-    V = BinaryOperator::createNeg(V, "tmp.", InsertPt);
+    V = InsertBinop(Instruction::Sub, Constant::getNullValue(V->getType()), V,
+                    InsertPt);
   return V;
 }
 
@@ -103,7 +123,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
     Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty);
 
     // FIXME: look for an existing add to use.
-    return BinaryOperator::createAdd(Rest, Start, "tmp.", InsertPt);
+    return InsertBinop(Instruction::Add, Rest, Start, InsertPt);
   }
 
   // {0,+,1} --> Insert a canonical induction variable into the loop!
@@ -164,7 +184,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
       }
     }
     
-    return BinaryOperator::createMul(I, F, "tmp.", MulInsertPt);
+    return InsertBinop(Instruction::Mul, I, F, MulInsertPt);
   }
 
   // If this is a chain of recurrences, turn it into a closed form, using the