Revert "Enhance SCEV to compute the trip count for some loops with unknown stride."

This reverts commit r278731. It caused http://crbug.com/638314

llvm-svn: 278853

1 files changed, 4 insertions, 77 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 2317b16..24ac1e3 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -4949,28 +4949,6 @@ bool ScalarEvolution::isAddRecNeverPoison(const Instruction *I, const Loop *L) {
   return LatchControlDependentOnPoison && loopHasNoAbnormalExits(L);
 }
 
-bool ScalarEvolution::loopHasNoSideEffects(const Loop *L) {
-  auto Itr = LoopHasNoSideEffects.find(L);
-  if (Itr == LoopHasNoSideEffects.end()) {
-    auto NoSideEffectsInBB = [&](BasicBlock *BB) {
-      return all_of(*BB, [](Instruction &I) {
-        // Non-atomic, non-volatile stores are ok.
-        if (auto *SI = dyn_cast<StoreInst>(&I)) 
-          return SI->isSimple();
-
-        return !I.mayHaveSideEffects();
-      });
-    };
-
-    auto InsertPair = LoopHasNoSideEffects.insert(
-        {L, all_of(L->getBlocks(), NoSideEffectsInBB)});
-    assert(InsertPair.second && "We just checked!");
-    Itr = InsertPair.first;
-  }
-
-  return Itr->second;
-}
-
 bool ScalarEvolution::loopHasNoAbnormalExits(const Loop *L) {
   auto Itr = LoopHasNoAbnormalExits.find(L);
   if (Itr == LoopHasNoAbnormalExits.end()) {
@@ -5558,7 +5536,6 @@ void ScalarEvolution::forgetLoop(const Loop *L) {
     forgetLoop(I);
 
   LoopHasNoAbnormalExits.erase(L);
-  LoopHasNoSideEffects.erase(L);
 }
 
 void ScalarEvolution::forgetValue(Value *V) {
@@ -8701,15 +8678,11 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
     return getCouldNotCompute();
 
   const SCEVAddRecExpr *IV = dyn_cast<SCEVAddRecExpr>(LHS);
-  bool PredicatedIV = false;
-
-  if (!IV && AllowPredicates) {
+  if (!IV && AllowPredicates)
     // Try to make this an AddRec using runtime tests, in the first X
     // iterations of this loop, where X is the SCEV expression found by the
     // algorithm below.
     IV = convertSCEVToAddRecWithPredicates(LHS, L, P);
-    PredicatedIV = true;
-  }
 
   // Avoid weird loops
   if (!IV || IV->getLoop() != L || !IV->isAffine())
@@ -8720,55 +8693,9 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
 
   const SCEV *Stride = IV->getStepRecurrence(*this);
 
-  bool PositiveStride = isKnownPositive(Stride);
-
-  // Avoid negative or zero stride values.
-  if (!PositiveStride) 
-    // We can compute the correct backedge taken count for loops with unknown
-    // strides if we can prove that the loop is not an infinite loop with side
-    // effects. Here's the loop structure we are trying to handle -
-    // 
-    // i = start
-    // do {
-    //   A[i] = i;
-    //   i += s;
-    // } while (i < end);
-    //
-    // The backedge taken count for such loops is evaluated as -
-    // (max(end, start + stride) - start - 1) /u stride
-    //
-    // The additional preconditions that we need to check to prove correctness
-    // of the above formula is as follows -
-    //
-    // a) IV is either nuw or nsw depending upon signedness (indicated by the
-    //    NoWrap flag).
-    // b) loop is single exit with no side effects.
-    //
-    //
-    // Precondition a) implies that if the stride is negative, this is a single
-    // trip loop. The backedge taken count formula reduces to zero in this case.
-    //
-    // Precondition b) implies that the unknown stride cannot be zero otherwise
-    // we have UB.
-    //
-    // The positive stride case is the same as isKnownPositive(Stride) returning
-    // true (original behavior of the function).
-    //
-    // We want to make sure that the stride is truly unknown as there are edge
-    // cases where ScalarEvolution propagates no wrap flags to the 
-    // post-increment/decrement IV even though the increment/decrement operation
-    // itself is wrapping. The computed backedge taken count may be wrong in
-    // such cases. This is prevented by checking that the stride is not known to
-    // be either positive or non-positive. For example, no wrap flags are 
-    // propagated to the post-increment IV of this loop with a trip count of 2 -
-    //
-    // unsigned char i;
-    // for(i=127; i<128; i+=129) 
-    //   A[i] = i;
-    // 
-    if (PredicatedIV || !NoWrap || isKnownNonPositive(Stride) || 
-        !loopHasNoSideEffects(L))
-      return getCouldNotCompute();
+  // Avoid negative or zero stride values
+  if (!isKnownPositive(Stride))
+    return getCouldNotCompute();
 
   // Avoid proven overflow cases: this will ensure that the backedge taken count
   // will not generate any unsigned overflow. Relaxed no-overflow conditions