allow -1 strides to reuse "1" strides.

[oota-llvm.git] / lib / Transforms / Scalar / LoopStrengthReduce.cpp

diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 4353134093867c2ad84a00b722751da0b135dc06..db8ab485e394c428ae1b60e83ab27864e3f17893 100644 (file)
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -235,6 +235,16 @@ DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
 /// GetExpressionSCEV - Compute and return the SCEV for the specified
 /// instruction.
 SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp, Loop *L) {
+  // Pointer to pointer bitcast instructions return the same value as their
+  // operand.
+  if (BitCastInst *BCI = dyn_cast<BitCastInst>(Exp)) {
+    if (SE->hasSCEV(BCI) || !isa<Instruction>(BCI->getOperand(0)))
+      return SE->getSCEV(BCI);
+    SCEVHandle R = GetExpressionSCEV(cast<Instruction>(BCI->getOperand(0)), L);
+    SE->setSCEV(BCI, R);
+    return R;
+  }
+
   // Scalar Evolutions doesn't know how to compute SCEV's for GEP instructions.
   // If this is a GEP that SE doesn't know about, compute it now and insert it.
   // If this is not a GEP, or if we have already done this computation, just let
@@ -883,9 +893,23 @@ static bool isZero(SCEVHandle &V) {
 ///
 bool LoopStrengthReduce::ValidStride(int64_t Scale, 
                                const std::vector<BasedUser>& UsersToProcess) {
-  for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i)
-    if (!TLI->isLegalAddressScale(Scale, UsersToProcess[i].Inst->getType()))
+  int64_t Imm;
+  for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
+    if (SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm))
+      Imm = SC->getValue()->getSExtValue();
+    else
+      Imm = 0;
+    
+    // If this is a load or other access, pass the type of the access in.
+    const Type *AccessTy = Type::VoidTy;
+    if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst))
+      AccessTy = SI->getOperand(0)->getType();
+    else if (LoadInst *LI = dyn_cast<LoadInst>(UsersToProcess[i].Inst))
+      AccessTy = LI->getType();
+    
+    if (!TLI->isLegalAddressScaleAndImm(Scale, Imm, AccessTy))
       return false;
+  }
   return true;
 }
 
@@ -905,7 +929,8 @@ unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle &Stride,
     for (std::map<SCEVHandle, IVsOfOneStride>::iterator SI= IVsByStride.begin(),
            SE = IVsByStride.end(); SI != SE; ++SI) {
       int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
-      if (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0)
+      if (SInt != -SSInt &&
+          (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0))
         continue;
       int64_t Scale = SInt / SSInt;
       // Check that this stride is valid for all the types used for loads and
@@ -968,22 +993,6 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
   SCEVHandle CommonExprs =
     RemoveCommonExpressionsFromUseBases(UsersToProcess);
   
-  // Check if it is possible to reuse a IV with stride that is factor of this
-  // stride. And the multiple is a number that can be encoded in the scale
-  // field of the target addressing mode.
-  PHINode *NewPHI = NULL;
-  Value   *IncV   = NULL;
-  IVExpr   ReuseIV;
-  unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
-                                           CommonExprs->getType(),
-                                           UsersToProcess);
-  if (RewriteFactor != 0) {
-    DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride
-         << " and BASE " << *ReuseIV.Base << " :\n";
-    NewPHI = ReuseIV.PHI;
-    IncV   = ReuseIV.IncV;
-  }
-
   // Next, figure out what we can represent in the immediate fields of
   // instructions.  If we can represent anything there, move it to the imm
   // fields of the BasedUsers.  We do this so that it increases the commonality
@@ -1011,10 +1020,29 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
     }
   }
 
+  // Check if it is possible to reuse a IV with stride that is factor of this
+  // stride. And the multiple is a number that can be encoded in the scale
+  // field of the target addressing mode.  And we will have a valid
+  // instruction after this substition, including the immediate field, if any.
+  PHINode *NewPHI = NULL;
+  Value   *IncV   = NULL;
+  IVExpr   ReuseIV;
+  unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
+                                           CommonExprs->getType(),
+                                           UsersToProcess);
+  if (RewriteFactor != 0) {
+    DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride
+         << " and BASE " << *ReuseIV.Base << " :\n";
+    NewPHI = ReuseIV.PHI;
+    IncV   = ReuseIV.IncV;
+  }
+
+  const Type *ReplacedTy = CommonExprs->getType();
+  
   // Now that we know what we need to do, insert the PHI node itself.
   //
-  DOUT << "INSERTING IV of STRIDE " << *Stride << " and BASE "
-       << *CommonExprs << " :\n";
+  DOUT << "INSERTING IV of TYPE " << *ReplacedTy << " of STRIDE "
+       << *Stride << " and BASE " << *CommonExprs << " :\n";
 
   SCEVExpander Rewriter(*SE, *LI);
   SCEVExpander PreheaderRewriter(*SE, *LI);
@@ -1025,7 +1053,6 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
   
   BasicBlock *LatchBlock = L->getLoopLatch();
 
-  const Type *ReplacedTy = CommonExprs->getType();
 
   // Emit the initial base value into the loop preheader.
   Value *CommonBaseV