Regenerate.

[oota-llvm.git] / lib / Analysis / ScalarEvolutionExpander.cpp

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 3d985ab88525bd4e3c1fb7b059c38a9ef5db046c..fc52fb70ff7baa90e450ce1a555aea80c60c322b 100644 (file)
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -68,23 +68,52 @@ 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) {
+  // Fold a binop with constant operands.
+  if (Constant *CLHS = dyn_cast<Constant>(LHS))
+    if (Constant *CRHS = dyn_cast<Constant>(RHS))
+      return ConstantExpr::get(Opcode, CLHS, CRHS);
+
+  // 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) {
+        // If we found the instruction *at* the insert point, insert later
+        // instructions after it.
+        if (BinOp == InsertPt)
+          InsertPt = ++IP;
+        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.
   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
     if (SC->getValue()->isAllOnesValue())
       FirstOp = 1;
 
   int i = S->getNumOperands()-2;
-  Value *V = expandInTy(S->getOperand(i+1), Ty);
+  Value *V = expand(S->getOperand(i+1));
 
   // 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, expand(S->getOperand(i)),
+                    InsertPt);
   // -1 * ...  --->  0 - ...
   if (FirstOp == 1)
-    V = BinaryOperator::createNeg(V, "tmp.", InsertPt);
+    V = InsertBinop(Instruction::Sub, Constant::getNullValue(V->getType()), V,
+                    InsertPt);
   return V;
 }
 
@@ -96,14 +125,14 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
 
   // {X,+,F} --> X + {0,+,F}
   if (!isa<SCEVConstant>(S->getStart()) ||
-      !cast<SCEVConstant>(S->getStart())->getValue()->isNullValue()) {
-    Value *Start = expandInTy(S->getStart(), Ty);
+      !cast<SCEVConstant>(S->getStart())->getValue()->isZero()) {
+    Value *Start = expand(S->getStart());
     std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
     NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty);
-    Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty);
+    Value *Rest = expand(SCEVAddRecExpr::get(NewOps, L));
 
     // 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!
@@ -139,11 +168,11 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
 
   // If this is a simple linear addrec, emit it now as a special case.
   if (S->getNumOperands() == 2) {   // {0,+,F} --> i*F
-    Value *F = expandInTy(S->getOperand(1), Ty);
+    Value *F = expand(S->getOperand(1));
     
     // IF the step is by one, just return the inserted IV.
     if (ConstantInt *CI = dyn_cast<ConstantInt>(F))
-      if (CI->getZExtValue() == 1)
+      if (CI->getValue() == 1)
         return I;
     
     // If the insert point is directly inside of the loop, emit the multiply at
@@ -164,7 +193,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
@@ -176,5 +205,17 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
   SCEVHandle V = S->evaluateAtIteration(IH);
   //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
 
-  return expandInTy(V, Ty);
+  return expand(V);
 }
+
+Value *SCEVExpander::expand(SCEV *S) {
+  // Check to see if we already expanded this.
+  std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S);
+  if (I != InsertedExpressions.end())
+    return I->second;
+  
+  Value *V = visit(S);
+  InsertedExpressions[S] = V;
+  return V;
+}
+