A brief survey of priority_queue usage in the tree turned this up

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

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index a241960b374cc040240d40e0fc98cc472b967908..593e27300d31bcd1377a15ef72c495374ef2129e 100644 (file)
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -73,7 +73,7 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
 /// 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) {
+                                 Value *RHS, Instruction *InsertPt) {
   // Fold a binop with constant operands.
   if (Constant *CLHS = dyn_cast<Constant>(LHS))
     if (Constant *CRHS = dyn_cast<Constant>(RHS))
@@ -81,24 +81,34 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
 
   // 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;
+  BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin();
+  if (InsertPt != BlockBegin) {
+    // Scanning starts from the last instruction before InsertPt.
+    BasicBlock::iterator IP = InsertPt;
+    --IP;
+    for (; 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 == BlockBegin) break;
+    }
   }
-
-  // If we don't have 
+  
+  // If we haven't found this binop, insert it.
   return BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt);
 }
 
+Value *SCEVExpander::visitAddExpr(SCEVAddExpr *S) {
+  Value *V = expand(S->getOperand(S->getNumOperands()-1));
+
+  // Emit a bunch of add instructions
+  for (int i = S->getNumOperands()-2; i >= 0; --i)
+    V = InsertBinop(Instruction::Add, V, expand(S->getOperand(i)),
+                    InsertPt);
+  return V;
+}
+    
 Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
   int FirstOp = 0;  // Set if we should emit a subtract.
   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
@@ -126,8 +136,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
   assert(Ty->isInteger() && "Cannot expand fp recurrences yet!");
 
   // {X,+,F} --> X + {0,+,F}
-  if (!isa<SCEVConstant>(S->getStart()) ||
-      !cast<SCEVConstant>(S->getStart())->getValue()->isZero()) {
+  if (!S->getStart()->isZero()) {
     Value *Start = expand(S->getStart());
     std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
     NewOps[0] = SE.getIntegerSCEV(0, Ty);
@@ -138,7 +147,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
   }
 
   // {0,+,1} --> Insert a canonical induction variable into the loop!
-  if (S->getNumOperands() == 2 &&
+  if (S->isAffine() &&
       S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) {
     // Create and insert the PHI node for the induction variable in the
     // specified loop.
@@ -169,7 +178,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
   Value *I = getOrInsertCanonicalInductionVariable(L, Ty);
 
   // If this is a simple linear addrec, emit it now as a special case.
-  if (S->getNumOperands() == 2) {   // {0,+,F} --> i*F
+  if (S->isAffine()) {   // {0,+,F} --> i*F
     Value *F = expand(S->getOperand(1));
     
     // IF the step is by one, just return the inserted IV.
@@ -217,6 +226,21 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
   return expand(V);
 }
 
+Value *SCEVExpander::visitTruncateExpr(SCEVTruncateExpr *S) {
+  Value *V = expand(S->getOperand());
+  return CastInst::createTruncOrBitCast(V, S->getType(), "tmp.", InsertPt);
+}
+
+Value *SCEVExpander::visitZeroExtendExpr(SCEVZeroExtendExpr *S) {
+  Value *V = expand(S->getOperand());
+  return CastInst::createZExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
+}
+
+Value *SCEVExpander::visitSignExtendExpr(SCEVSignExtendExpr *S) {
+  Value *V = expand(S->getOperand());
+  return CastInst::createSExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
+}
+
 Value *SCEVExpander::visitSMaxExpr(SCEVSMaxExpr *S) {
   Value *LHS = expand(S->getOperand(0));
   for (unsigned i = 1; i < S->getNumOperands(); ++i) {
@@ -237,6 +261,12 @@ Value *SCEVExpander::visitUMaxExpr(SCEVUMaxExpr *S) {
   return LHS;
 }
 
+Value *SCEVExpander::expandCodeFor(SCEVHandle SH, Instruction *IP) {
+  // Expand the code for this SCEV.
+  this->InsertPt = IP;
+  return expand(SH);
+}
+
 Value *SCEVExpander::expand(SCEV *S) {
   // Check to see if we already expanded this.
   std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S);