Constify a bunch of SCEV-using code.

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

diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 89429b6731db0e3eba2a951b5d56548ce77e8167..50603d975785802c44059ee8e021ef48642838b3 100644 (file)
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -32,6 +32,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ValueHandle.h"
 #include "llvm/Target/TargetLowering.h"
 #include <algorithm>
 using namespace llvm;
@@ -157,7 +158,7 @@ namespace {
       AU.addPreserved<ScalarEvolution>();
     }
 
-private:
+  private:
     bool AddUsersIfInteresting(Instruction *I, Loop *L,
                                SmallPtrSet<Instruction*,16> &Processed);
     ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond,
@@ -320,7 +321,7 @@ static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L,
   // for a nested AddRecExpr.
   if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(SH)) {
     for (unsigned i = 0, e = AE->getNumOperands(); i != e; ++i)
-      if (SCEVAddRecExpr *AddRec =
+      if (const SCEVAddRecExpr *AddRec =
              dyn_cast<SCEVAddRecExpr>(AE->getOperand(i))) {
         if (AddRec->getLoop() == L)
           TheAddRec = SE->getAddExpr(AddRec, TheAddRec);
@@ -406,20 +407,7 @@ static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
     }
 
   // Okay, all uses of IV by PN are in predecessor blocks that really are
-  // dominated by the latch block.  Split the critical edges and use the
-  // post-incremented value.
-  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
-    if (PN->getIncomingValue(i) == IV) {
-      SplitCriticalEdge(PN->getIncomingBlock(i), PN->getParent(), P, false);
-      // Splitting the critical edge can reduce the number of entries in this
-      // PHI.
-      e = PN->getNumIncomingValues();
-      if (--NumUses == 0) break;
-    }
-
-  // PHI node might have become a constant value after SplitCriticalEdge.
-  DeadInsts.push_back(User);
-  
+  // dominated by the latch block.  Use the post-incremented value.
   return true;
 }
 
@@ -1170,7 +1158,9 @@ bool LoopStrengthReduce::RequiresTypeConversion(const Type *Ty1,
                                                 const Type *Ty2) {
   if (Ty1 == Ty2)
     return false;
-  if (SE->getEffectiveSCEVType(Ty1) == SE->getEffectiveSCEVType(Ty2))
+  Ty1 = SE->getEffectiveSCEVType(Ty1);
+  Ty2 = SE->getEffectiveSCEVType(Ty2);
+  if (Ty1 == Ty2)
     return false;
   if (Ty1->canLosslesslyBitCastTo(Ty2))
     return false;
@@ -1410,8 +1400,8 @@ bool LoopStrengthReduce::ShouldUseFullStrengthReductionMode(
   // Iterate through the uses to find conditions that automatically rule out
   // full-lsr mode.
   for (unsigned i = 0, e = UsersToProcess.size(); i != e; ) {
-    SCEV *Base = UsersToProcess[i].Base;
-    SCEV *Imm = UsersToProcess[i].Imm;
+    const SCEV *Base = UsersToProcess[i].Base;
+    const SCEV *Imm = UsersToProcess[i].Imm;
     // If any users have a loop-variant component, they can't be fully
     // strength-reduced.
     if (Imm && !Imm->isLoopInvariant(L))
@@ -1420,7 +1410,7 @@ bool LoopStrengthReduce::ShouldUseFullStrengthReductionMode(
     // the two Imm values can't be folded into the address, full
     // strength reduction would increase register pressure.
     do {
-      SCEV *CurImm = UsersToProcess[i].Imm;
+      const SCEV *CurImm = UsersToProcess[i].Imm;
       if ((CurImm || Imm) && CurImm != Imm) {
         if (!CurImm) CurImm = SE->getIntegerSCEV(0, Stride->getType());
         if (!Imm)       Imm = SE->getIntegerSCEV(0, Stride->getType());
@@ -2149,6 +2139,7 @@ ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond,
     CondUse = &IVUsesByStride[*NewStride].Users.back();
     CondStride = NewStride;
     ++NumEliminated;
+    Changed = true;
   }
 
   return Cond;
@@ -2512,44 +2503,21 @@ bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) {
   StrideOrder.clear();
 
   // Clean up after ourselves
-  if (!DeadInsts.empty()) {
+  if (!DeadInsts.empty())
     DeleteTriviallyDeadInstructions();
 
-    BasicBlock::iterator I = L->getHeader()->begin();
-    while (PHINode *PN = dyn_cast<PHINode>(I++)) {
-      // At this point, we know that we have killed one or more IV users.
-      // It is worth checking to see if the cannonical indvar is also
-      // dead, so that we can remove it as well.
-      //
-      // We can remove a PHI if it is on a cycle in the def-use graph
-      // where each node in the cycle has degree one, i.e. only one use,
-      // and is an instruction with no side effects.
-      //
-      // FIXME: this needs to eliminate an induction variable even if it's being
-      // compared against some value to decide loop termination.
-      if (!PN->hasOneUse())
-        continue;
-      
-      SmallPtrSet<PHINode *, 4> PHIs;
-      for (Instruction *J = dyn_cast<Instruction>(*PN->use_begin());
-           J && J->hasOneUse() && !J->mayWriteToMemory();
-           J = dyn_cast<Instruction>(*J->use_begin())) {
-        // If we find the original PHI, we've discovered a cycle.
-        if (J == PN) {
-          // Break the cycle and mark the PHI for deletion.
-          SE->deleteValueFromRecords(PN);
-          PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
-          DeadInsts.push_back(PN);
-          Changed = true;
-          break;
-        }
-        // If we find a PHI more than once, we're on a cycle that
-        // won't prove fruitful.
-        if (isa<PHINode>(J) && !PHIs.insert(cast<PHINode>(J)))
-          break;
-      }
+  // At this point, it is worth checking to see if any recurrence PHIs are also
+  // dead, so that we can remove them as well. To keep ScalarEvolution
+  // current, use a ValueDeletionListener class.
+  struct LSRListener : public ValueDeletionListener {
+    ScalarEvolution &SE;
+    explicit LSRListener(ScalarEvolution &se) : SE(se) {}
+
+    virtual void ValueWillBeDeleted(Value *V) {
+      SE.deleteValueFromRecords(V);
     }
-    DeleteTriviallyDeadInstructions();
-  }
+  } VDL(*SE);
+  DeleteDeadPHIs(L->getHeader(), &VDL);
+
   return Changed;
 }