[SCEV] Re-enable "Cache results of computeExitLimit"

[mkazantsev]

Summary

The patch rL309080 was reverted because it did not clean up the cache on "forgetValue"
method call. This patch re-enables this change, adds the missing check and introduces
two new unit tests that make sure that the cache is cleaned properly.

[mkazantsev]

I just realized that the attached IR test takes unreasonably long time with this fix, what makes the entire patch pointless.

[mkazantsev]

Needs update to pass its own test within reasonable time.

[mkazantsev]

Now we don't throw away the exit limit for sake of a more optimistic future estimation every time we calculate getBackedgeTakenInfo. It doesn't look like estimation of Exit Limit for a particular exit block may be improved from what we have there.

[sanjoy]

lgtm

I've also verified that this does not break on the internal test case we had.

include/llvm/Analysis/ScalarEvolution.h

1133 ↗

(On Diff #108923)

Please add a comment on EraseExitLimit. While the name is pretty self explanatory in terms of what it does, it isn't obvious in what situations it can safely be set to false.

lib/Analysis/ScalarEvolution.cpp

10858 ↗

(On Diff #108923)

You don't have to fix this in this patch, I think we only need to do this if S has a SCEVUnknown somewhere in it. Can you please add a TODO?

10862 ↗

(On Diff #108923)

Use braces to avoid the dangling else here.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

public:
   unsigned getComplexity() const override { return Preds.size(); }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEVPredicate *P) {
     return P->getKind() == P_Union;
   }
 };
 
+struct ExitLimitQuery {
+  ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates)
+      : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {}
+
+  const Loop *L;
+  BasicBlock *ExitingBlock;
+  bool AllowPredicates;
+};
+
+template <> struct DenseMapInfo<ExitLimitQuery> {
+  static inline ExitLimitQuery getEmptyKey() {
+    return ExitLimitQuery(nullptr, nullptr, true);
+  }
+  static inline ExitLimitQuery getTombstoneKey() {
+    return ExitLimitQuery(nullptr, nullptr, false);
+  }
+  static unsigned getHashValue(ExitLimitQuery Val) {
+    return hash_combine(hash_combine(Val.L, Val.ExitingBlock),
+                        Val.AllowPredicates);
+  }
+  static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) {
+    return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock &&
+           LHS.AllowPredicates == RHS.AllowPredicates;
+  }
+};
+
 /// The main scalar evolution driver. Because client code (intentionally)
 /// can't do much with the SCEV objects directly, they must ask this class
 /// for services.
 class ScalarEvolution {
 public:
   /// An enum describing the relationship between a SCEV and a loop.
   enum LoopDisposition {
     LoopVariant,   ///< The SCEV is loop-variant (unknown).
struct ExitLimit {
 
     /// Test whether this ExitLimit contains any computed information, or
     /// whether it's all SCEVCouldNotCompute values.
     bool hasAnyInfo() const {
       return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
              !isa<SCEVCouldNotCompute>(MaxNotTaken);
     }
 
+    bool hasOperand(const SCEV *S) const;
+
     /// Test whether this ExitLimit contains all information.
     bool hasFullInfo() const {
       return !isa<SCEVCouldNotCompute>(ExactNotTaken);
     }
   };
 
   /// Information about the number of times a particular loop exit may be
   /// reached before exiting the loop.
private:
   /// Cache the backedge-taken count of the loops for this function as they
   /// are computed.
   DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
 
   /// Cache the predicated backedge-taken count of the loops for this
   /// function as they are computed.
   DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
 
+  // Cache the calculated exit limits for the loops.
+  DenseMap<ExitLimitQuery, ExitLimit> ExitLimits;
+
   /// This map contains entries for all of the PHI instructions that we
   /// attempt to compute constant evolutions for.  This allows us to avoid
   /// potentially expensive recomputation of these properties.  An instruction
   /// maps to null if we are unable to compute its exit value.
   DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
 
   /// This map contains entries for all the expressions that we attempt to
   /// compute getSCEVAtScope information for, which can be expensive in
private:
 
   /// Compute the number of times the backedge of the specified loop will
   /// execute if it exits via the specified block. If AllowPredicates is set,
   /// this call will try to use a minimal set of SCEV predicates in order to
   /// return an exact answer.
   ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
                              bool AllowPredicates = false);
 
+  ExitLimit computeExitLimitImpl(const Loop *L, BasicBlock *ExitingBlock,
+                                 bool AllowPredicates = false);
+
   /// Compute the number of times the backedge of the specified loop will
   /// execute if its exit condition were a conditional branch of ExitCond,
   /// TBB, and FBB.
   ///
   /// \p ControlsExit is true if ExitCond directly controls the exit
   /// branch. In this case, we can assume that the loop exits only if the
   /// condition is true and can infer that failing to meet the condition prior
   /// to integer wraparound results in undefined behavior.
private:
   /// constant, and None if it isn't.
   ///
   /// This is intended to be a cheaper version of getMinusSCEV.  We can be
   /// frugal here since we just bail out of actually constructing and
   /// canonicalizing an expression in the cases where the result isn't going
   /// to be a constant.
   Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
 
-  /// Drop memoized information computed for S.
-  void forgetMemoizedResults(const SCEV *S);
+  /// Drop memoized information computed for S. Only erase Exit Limits info if
+  /// we expect that the operation we have made is going to change it.
+  void forgetMemoizedResults(const SCEV *S, bool EraseExitLimit = true);
 
   /// Return an existing SCEV for V if there is one, otherwise return nullptr.
   const SCEV *getExistingSCEV(Value *V);
 
   /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
   /// pointer.
   bool checkValidity(const SCEV *S) const;
 

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

while (!Worklist.empty()) {
         // SCEVUnknown for a PHI either means that it has an unrecognized
         // structure, or it's a PHI that's in the progress of being computed
         // by createNodeForPHI.  In the former case, additional loop trip
         // count information isn't going to change anything. In the later
         // case, createNodeForPHI will perform the necessary updates on its
         // own when it gets to that point.
         if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
           eraseValueFromMap(It->first);
-          forgetMemoizedResults(Old);
+          forgetMemoizedResults(Old, false);
         }
         if (PHINode *PN = dyn_cast<PHINode>(I))
           ConstantEvolutionLoopExitValue.erase(PN);
       }
 
       PushDefUseChildren(I, Worklist);
     }
   }
if (It != ValueExprMap.end()) {
       forgetMemoizedResults(It->second);
       if (PHINode *PN = dyn_cast<PHINode>(I))
         ConstantEvolutionLoopExitValue.erase(PN);
     }
 
     PushDefUseChildren(I, Worklist);
   }
 
+  for (auto I = ExitLimits.begin(); I != ExitLimits.end(); ++I) {
+    auto &Query = I->first;
+    if (Query.L == L)
+      ExitLimits.erase(I);
+  }
+
   // Forget all contained loops too, to avoid dangling entries in the
   // ValuesAtScopes map.
   for (Loop *I : *L)
     forgetLoop(I);
 
   LoopPropertiesCache.erase(L);
 }
 
ScalarEvolution::computeBackedgeTakenCount(const Loop *L,
   bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
   return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
                            MaxBECount, MaxOrZero);
 }
 
 ScalarEvolution::ExitLimit
 ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
                                   bool AllowPredicates) {
+  ExitLimitQuery Query(L, ExitingBlock, AllowPredicates);
+  auto MaybeEL = ExitLimits.find(Query);
+  if (MaybeEL != ExitLimits.end())
+    return MaybeEL->second;
+  ExitLimit EL = computeExitLimitImpl(L, ExitingBlock, AllowPredicates);
+  ExitLimits.insert({Query, EL});
+  return EL;
+}
+
+ScalarEvolution::ExitLimit
+ScalarEvolution::computeExitLimitImpl(const Loop *L, BasicBlock *ExitingBlock,
+                                      bool AllowPredicates) {
 
   // Okay, we've chosen an exiting block.  See what condition causes us to exit
   // at this block and remember the exit block and whether all other targets
   // lead to the loop header.
   bool MustExecuteLoopHeader = true;
   BasicBlock *Exit = nullptr;
   for (auto *SBB : successors(ExitingBlock))
     if (!L->contains(SBB)) {
: F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
       LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
       PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
       WalkingBEDominatingConds(false), ProvingSplitPredicate(false),
       MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
+      ExitLimits(std::move(Arg.ExitLimits)),
       ConstantEvolutionLoopExitValue(
           std::move(Arg.ConstantEvolutionLoopExitValue)),
       ValuesAtScopes(std::move(Arg.ValuesAtScopes)),
       LoopDispositions(std::move(Arg.LoopDispositions)),
       LoopPropertiesCache(std::move(Arg.LoopPropertiesCache)),
       BlockDispositions(std::move(Arg.BlockDispositions)),
       UnsignedRanges(std::move(Arg.UnsignedRanges)),
       SignedRanges(std::move(Arg.SignedRanges)),

 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
   return getBlockDisposition(S, BB) == ProperlyDominatesBlock;
 }
 
 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
   return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; });
 }
 
-void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
+bool ScalarEvolution::ExitLimit::hasOperand(const SCEV *S) const {
+  auto IsS = [&](const SCEV *X) { return S == X; };
+  auto ContainsS = [&](const SCEV *X) {
+    return !isa<SCEVCouldNotCompute>(X) && SCEVExprContains(X, IsS);
+  };
+  return ContainsS(ExactNotTaken) || ContainsS(MaxNotTaken);
+}
+
+void
+ScalarEvolution::forgetMemoizedResults(const SCEV *S, bool EraseExitLimit) {
   ValuesAtScopes.erase(S);
   LoopDispositions.erase(S);
   BlockDispositions.erase(S);
   UnsignedRanges.erase(S);
   SignedRanges.erase(S);
   ExprValueMap.erase(S);
   HasRecMap.erase(S);
   MinTrailingZerosCache.erase(S);
auto RemoveSCEVFromBackedgeMap =
             Map.erase(I++);
           } else
             ++I;
         }
       };
 
   RemoveSCEVFromBackedgeMap(BackedgeTakenCounts);
   RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts);
+
+  // TODO: There is a suspicion that we only need to do it when there is a
+  // SCEVUnknown somewhere inside S. Need to check this.
+  if (EraseExitLimit)
+    for (auto I = ExitLimits.begin(), E = ExitLimits.end(); I != E; ++I)
+      if (I->second.hasOperand(S))
+        ExitLimits.erase(I);
 }
 
 void ScalarEvolution::verify() const {
   ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
   ScalarEvolution SE2(F, TLI, AC, DT, LI);
 
   SmallVector<Loop *, 8> LoopStack(LI.begin(), LI.end());
 

llvm/trunk/test/Analysis/ScalarEvolution/cache_loop_exit_limit.ll

+; RUN: opt -scalar-evolution-max-arith-depth=4 -scalar-evolution-max-add-rec-size=4 -loop-reduce -S < %s | FileCheck %s
+
+; Check that the test does not hang.
+define void @test_01(i32* nocapture %a) local_unnamed_addr {
+
+; CHECK-LABEL: @test_01(
+
+while.body.outer:
+  %arrayidx2 = getelementptr inbounds i32, i32* %a, i64 96
+  %arrayidx2.promoted50 = load i32, i32* %arrayidx2, align 1
+  %a.promoted = load i32, i32* %a, align 1
+  %add347.peel = xor i32 %arrayidx2.promoted50, -1
+  %tobool48.peel = icmp eq i32 %a.promoted, %add347.peel
+  br i1 %tobool48.peel, label %while.body.preheader, label %while.body4.preheader
+
+while.body.preheader:                             ; preds = %while.body.outer
+  %tobool48 = icmp eq i32 %a.promoted, 1
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.body
+  br i1 %tobool48, label %while.body, label %while.body4.preheader.loopexit
+
+while.body4.preheader.loopexit:                   ; preds = %while.body
+  br label %while.body4.preheader
+
+while.body4.preheader:                            ; preds = %while.body4.preheader.loopexit, %while.body.outer
+  br label %while.body4
+
+while.body4:                                      ; preds = %while.body4.preheader, %while.end.22
+  %0 = phi i32 [ %mul.22, %while.end.22 ], [ %arrayidx2.promoted50, %while.body4.preheader ]
+  %mul = mul nsw i32 %0, %0
+  br label %while.cond17
+
+while.cond17:                                     ; preds = %while.cond17, %while.body4
+  %add22.sink = phi i32 [ %add22, %while.cond17 ], [ %mul, %while.body4 ]
+  %cmp = icmp slt i32 %add22.sink, 0
+  %add22 = add nsw i32 %add22.sink, 1024
+  br i1 %cmp, label %while.cond17, label %while.end
+
+while.end:                                        ; preds = %while.cond17
+  %mul.1 = mul nsw i32 %add22.sink, %add22.sink
+  br label %while.cond17.1
+
+while.cond17.1:                                   ; preds = %while.cond17.1, %while.end
+  %add22.sink.1 = phi i32 [ %add22.1, %while.cond17.1 ], [ %mul.1, %while.end ]
+  %cmp.1 = icmp slt i32 %add22.sink.1, 0
+  %add22.1 = add nsw i32 %add22.sink.1, 2048
+  br i1 %cmp.1, label %while.cond17.1, label %while.end.1
+
+while.end.1:                                      ; preds = %while.cond17.1
+  %mul.2 = mul nsw i32 %add22.sink.1, %add22.sink.1
+  br label %while.cond17.2
+
+while.cond17.2:                                   ; preds = %while.cond17.2, %while.end.1
+  %add22.sink.2 = phi i32 [ %add22.2, %while.cond17.2 ], [ %mul.2, %while.end.1 ]
+  %cmp.2 = icmp slt i32 %add22.sink.2, 0
+  %add22.2 = add nsw i32 %add22.sink.2, 4096
+  br i1 %cmp.2, label %while.cond17.2, label %while.end.2
+
+while.end.2:                                      ; preds = %while.cond17.2
+  %mul.3 = mul nsw i32 %add22.sink.2, %add22.sink.2
+  br label %while.cond17.3
+
+while.cond17.3:                                   ; preds = %while.cond17.3, %while.end.2
+  %add22.sink.3 = phi i32 [ %add22.3, %while.cond17.3 ], [ %mul.3, %while.end.2 ]
+  %cmp.3 = icmp slt i32 %add22.sink.3, 0
+  %add22.3 = add nsw i32 %add22.sink.3, 8192
+  br i1 %cmp.3, label %while.cond17.3, label %while.end.3
+
+while.end.3:                                      ; preds = %while.cond17.3
+  %mul.4 = mul nsw i32 %add22.sink.3, %add22.sink.3
+  br label %while.cond17.4
+
+while.cond17.4:                                   ; preds = %while.cond17.4, %while.end.3
+  %add22.sink.4 = phi i32 [ %add22.4, %while.cond17.4 ], [ %mul.4, %while.end.3 ]
+  %cmp.4 = icmp slt i32 %add22.sink.4, 0
+  %add22.4 = add nsw i32 %add22.sink.4, 16384
+  br i1 %cmp.4, label %while.cond17.4, label %while.end.4
+
+while.end.4:                                      ; preds = %while.cond17.4
+  %mul.5 = mul nsw i32 %add22.sink.4, %add22.sink.4
+  br label %while.cond17.5
+
+while.cond17.5:                                   ; preds = %while.cond17.5, %while.end.4
+  %add22.sink.5 = phi i32 [ %add22.5, %while.cond17.5 ], [ %mul.5, %while.end.4 ]
+  %cmp.5 = icmp slt i32 %add22.sink.5, 0
+  %add22.5 = add nsw i32 %add22.sink.5, 32768
+  br i1 %cmp.5, label %while.cond17.5, label %while.end.5
+
+while.end.5:                                      ; preds = %while.cond17.5
+  %mul.6 = mul nsw i32 %add22.sink.5, %add22.sink.5
+  br label %while.cond17.6
+
+while.cond17.6:                                   ; preds = %while.cond17.6, %while.end.5
+  %add22.sink.6 = phi i32 [ %add22.6, %while.cond17.6 ], [ %mul.6, %while.end.5 ]
+  %cmp.6 = icmp slt i32 %add22.sink.6, 0
+  %add22.6 = add nsw i32 %add22.sink.6, 65536
+  br i1 %cmp.6, label %while.cond17.6, label %while.end.6
+
+while.end.6:                                      ; preds = %while.cond17.6
+  %mul.7 = mul nsw i32 %add22.sink.6, %add22.sink.6
+  br label %while.cond17.7
+
+while.cond17.7:                                   ; preds = %while.cond17.7, %while.end.6
+  %add22.sink.7 = phi i32 [ %add22.7, %while.cond17.7 ], [ %mul.7, %while.end.6 ]
+  %cmp.7 = icmp slt i32 %add22.sink.7, 0
+  %add22.7 = add nsw i32 %add22.sink.7, 131072
+  br i1 %cmp.7, label %while.cond17.7, label %while.end.7
+
+while.end.7:                                      ; preds = %while.cond17.7
+  %mul.8 = mul nsw i32 %add22.sink.7, %add22.sink.7
+  br label %while.cond17.8
+
+while.cond17.8:                                   ; preds = %while.cond17.8, %while.end.7
+  %add22.sink.8 = phi i32 [ %add22.8, %while.cond17.8 ], [ %mul.8, %while.end.7 ]
+  %cmp.8 = icmp slt i32 %add22.sink.8, 0
+  %add22.8 = add nsw i32 %add22.sink.8, 262144
+  br i1 %cmp.8, label %while.cond17.8, label %while.end.8
+
+while.end.8:                                      ; preds = %while.cond17.8
+  %mul.9 = mul nsw i32 %add22.sink.8, %add22.sink.8
+  br label %while.cond17.9
+
+while.cond17.9:                                   ; preds = %while.cond17.9, %while.end.8
+  %add22.sink.9 = phi i32 [ %add22.9, %while.cond17.9 ], [ %mul.9, %while.end.8 ]
+  %cmp.9 = icmp slt i32 %add22.sink.9, 0
+  %add22.9 = add nsw i32 %add22.sink.9, 524288
+  br i1 %cmp.9, label %while.cond17.9, label %while.end.9
+
+while.end.9:                                      ; preds = %while.cond17.9
+  %mul.10 = mul nsw i32 %add22.sink.9, %add22.sink.9
+  br label %while.cond17.10
+
+while.cond17.10:                                  ; preds = %while.cond17.10, %while.end.9
+  %add22.sink.10 = phi i32 [ %add22.10, %while.cond17.10 ], [ %mul.10, %while.end.9 ]
+  %cmp.10 = icmp slt i32 %add22.sink.10, 0
+  %add22.10 = add nsw i32 %add22.sink.10, 1048576
+  br i1 %cmp.10, label %while.cond17.10, label %while.end.10
+
+while.end.10:                                     ; preds = %while.cond17.10
+  %mul.11 = mul nsw i32 %add22.sink.10, %add22.sink.10
+  br label %while.cond17.11
+
+while.cond17.11:                                  ; preds = %while.cond17.11, %while.end.10
+  %add22.sink.11 = phi i32 [ %add22.11, %while.cond17.11 ], [ %mul.11, %while.end.10 ]
+  %cmp.11 = icmp slt i32 %add22.sink.11, 0
+  %add22.11 = add nsw i32 %add22.sink.11, 2097152
+  br i1 %cmp.11, label %while.cond17.11, label %while.end.11
+
+while.end.11:                                     ; preds = %while.cond17.11
+  %mul.12 = mul nsw i32 %add22.sink.11, %add22.sink.11
+  br label %while.cond17.12
+
+while.cond17.12:                                  ; preds = %while.cond17.12, %while.end.11
+  %add22.sink.12 = phi i32 [ %add22.12, %while.cond17.12 ], [ %mul.12, %while.end.11 ]
+  %cmp.12 = icmp slt i32 %add22.sink.12, 0
+  %add22.12 = add nsw i32 %add22.sink.12, 4194304
+  br i1 %cmp.12, label %while.cond17.12, label %while.end.12
+
+while.end.12:                                     ; preds = %while.cond17.12
+  %mul.13 = mul nsw i32 %add22.sink.12, %add22.sink.12
+  br label %while.cond17.13
+
+while.cond17.13:                                  ; preds = %while.cond17.13, %while.end.12
+  %add22.sink.13 = phi i32 [ %add22.13, %while.cond17.13 ], [ %mul.13, %while.end.12 ]
+  %cmp.13 = icmp slt i32 %add22.sink.13, 0
+  %add22.13 = add nsw i32 %add22.sink.13, 8388608
+  br i1 %cmp.13, label %while.cond17.13, label %while.end.13
+
+while.end.13:                                     ; preds = %while.cond17.13
+  %mul.14 = mul nsw i32 %add22.sink.13, %add22.sink.13
+  br label %while.cond17.14
+
+while.cond17.14:                                  ; preds = %while.cond17.14, %while.end.13
+  %add22.sink.14 = phi i32 [ %add22.14, %while.cond17.14 ], [ %mul.14, %while.end.13 ]
+  %cmp.14 = icmp slt i32 %add22.sink.14, 0
+  %add22.14 = add nsw i32 %add22.sink.14, 16777216
+  br i1 %cmp.14, label %while.cond17.14, label %while.end.14
+
+while.end.14:                                     ; preds = %while.cond17.14
+  %mul.15 = mul nsw i32 %add22.sink.14, %add22.sink.14
+  br label %while.cond17.15
+
+while.cond17.15:                                  ; preds = %while.cond17.15, %while.end.14
+  %add22.sink.15 = phi i32 [ %add22.15, %while.cond17.15 ], [ %mul.15, %while.end.14 ]
+  %cmp.15 = icmp slt i32 %add22.sink.15, 0
+  %add22.15 = add nsw i32 %add22.sink.15, 33554432
+  br i1 %cmp.15, label %while.cond17.15, label %while.end.15
+
+while.end.15:                                     ; preds = %while.cond17.15
+  %mul.16 = mul nsw i32 %add22.sink.15, %add22.sink.15
+  br label %while.cond17.16
+
+while.cond17.16:                                  ; preds = %while.cond17.16, %while.end.15
+  %add22.sink.16 = phi i32 [ %add22.16, %while.cond17.16 ], [ %mul.16, %while.end.15 ]
+  %cmp.16 = icmp slt i32 %add22.sink.16, 0
+  %add22.16 = add nsw i32 %add22.sink.16, 67108864
+  br i1 %cmp.16, label %while.cond17.16, label %while.end.16
+
+while.end.16:                                     ; preds = %while.cond17.16
+  %mul.17 = mul nsw i32 %add22.sink.16, %add22.sink.16
+  br label %while.cond17.17
+
+while.cond17.17:                                  ; preds = %while.cond17.17, %while.end.16
+  %add22.sink.17 = phi i32 [ %add22.17, %while.cond17.17 ], [ %mul.17, %while.end.16 ]
+  %cmp.17 = icmp slt i32 %add22.sink.17, 0
+  %add22.17 = add nsw i32 %add22.sink.17, 134217728
+  br i1 %cmp.17, label %while.cond17.17, label %while.end.17
+
+while.end.17:                                     ; preds = %while.cond17.17
+  %mul.18 = mul nsw i32 %add22.sink.17, %add22.sink.17
+  br label %while.cond17.18
+
+while.cond17.18:                                  ; preds = %while.cond17.18, %while.end.17
+  %add22.sink.18 = phi i32 [ %add22.18, %while.cond17.18 ], [ %mul.18, %while.end.17 ]
+  %cmp.18 = icmp slt i32 %add22.sink.18, 0
+  %add22.18 = add nsw i32 %add22.sink.18, 268435456
+  br i1 %cmp.18, label %while.cond17.18, label %while.end.18
+
+while.end.18:                                     ; preds = %while.cond17.18
+  %mul.19 = mul nsw i32 %add22.sink.18, %add22.sink.18
+  br label %while.cond17.19
+
+while.cond17.19:                                  ; preds = %while.cond17.19, %while.end.18
+  %add22.sink.19 = phi i32 [ %add22.19, %while.cond17.19 ], [ %mul.19, %while.end.18 ]
+  %cmp.19 = icmp slt i32 %add22.sink.19, 0
+  %add22.19 = add nsw i32 %add22.sink.19, 536870912
+  br i1 %cmp.19, label %while.cond17.19, label %while.end.19
+
+while.end.19:                                     ; preds = %while.cond17.19
+  %mul.20 = mul nsw i32 %add22.sink.19, %add22.sink.19
+  br label %while.cond17.20
+
+while.cond17.20:                                  ; preds = %while.cond17.20, %while.end.19
+  %add22.sink.20 = phi i32 [ %add22.20, %while.cond17.20 ], [ %mul.20, %while.end.19 ]
+  %cmp.20 = icmp slt i32 %add22.sink.20, 0
+  %add22.20 = add nsw i32 %add22.sink.20, 1073741824
+  br i1 %cmp.20, label %while.cond17.20, label %while.end.20
+
+while.end.20:                                     ; preds = %while.cond17.20
+  %mul.21 = mul nsw i32 %add22.sink.20, %add22.sink.20
+  br label %while.cond17.21
+
+while.cond17.21:                                  ; preds = %while.cond17.21, %while.end.20
+  %add22.sink.21 = phi i32 [ %add22.21, %while.cond17.21 ], [ %mul.21, %while.end.20 ]
+  %cmp.21 = icmp slt i32 %add22.sink.21, 0
+  %add22.21 = or i32 %add22.sink.21, -2147483648
+  br i1 %cmp.21, label %while.cond17.21, label %while.end.22
+
+while.end.22:                                     ; preds = %while.cond17.21
+  %mul.22 = mul nsw i32 %add22.sink.21, %add22.sink.21
+  br label %while.body4
+}

llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExprNonIntegral) {
   Exp.disableCanonicalMode();
   Exp.expandCodeFor(AddRec, T_pint64, Ret);
 
   // Make sure none of the instructions inserted were inttoptr/ptrtoint.
   // The verifier will check this.
   EXPECT_FALSE(verifyFunction(*F, &errs()));
 }
 
+// Make sure that SCEV invalidates exit limits after invalidating the values it
+// depends on when we forget a loop.
+TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) {
+  /*
+   * Create the following code:
+   * func(i64 addrspace(10)* %arg)
+   * top:
+   *  br label %L.ph
+   * L.ph:
+   *  br label %L
+   * L:
+   *  %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
+   *  %add = add i64 %phi2, 1
+   *  %cond = icmp slt i64 %add, 1000; then becomes 2000.
+   *  br i1 %cond, label %post, label %L2
+   * post:
+   *  ret void
+   *
+   */
+
+  // Create a module with non-integral pointers in it's datalayout
+  Module NIM("nonintegral", Context);
+  std::string DataLayout = M.getDataLayoutStr();
+  if (!DataLayout.empty())
+    DataLayout += "-";
+  DataLayout += "ni:10";
+  NIM.setDataLayout(DataLayout);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+  Type *T_pint64 = T_int64->getPointerTo(10);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
+  Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
+
+  Argument *Arg = &*F->arg_begin();
+
+  BasicBlock *Top = BasicBlock::Create(Context, "top", F);
+  BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
+  BasicBlock *L = BasicBlock::Create(Context, "L", F);
+  BasicBlock *Post = BasicBlock::Create(Context, "post", F);
+
+  IRBuilder<> Builder(Top);
+  Builder.CreateBr(LPh);
+
+  Builder.SetInsertPoint(LPh);
+  Builder.CreateBr(L);
+
+  Builder.SetInsertPoint(L);
+  PHINode *Phi = Builder.CreatePHI(T_int64, 2);
+  auto *Add = cast<Instruction>(
+      Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
+  auto *Limit = ConstantInt::get(T_int64, 1000);
+  auto *Cond = cast<Instruction>(
+      Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));
+  auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));
+  Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
+  Phi->addIncoming(Add, L);
+
+  Builder.SetInsertPoint(Post);
+  Builder.CreateRetVoid();
+
+  ScalarEvolution SE = buildSE(*F);
+  auto *Loop = LI->getLoopFor(L);
+  const SCEV *EC = SE.getBackedgeTakenCount(Loop);
+  EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
+
+  SE.forgetLoop(Loop);
+  Br->eraseFromParent();
+  Cond->eraseFromParent();
+
+  Builder.SetInsertPoint(L);
+  Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000),
+                     "new.cond");
+  Builder.CreateCondBr(Cond, L, Post);
+  const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);
+  EXPECT_NE(EC, NewEC);
+}
+
+// Make sure that SCEV invalidates exit limits after invalidating the values it
+// depends on when we forget a value.
+TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) {
+  /*
+   * Create the following code:
+   * func(i64 addrspace(10)* %arg)
+   * top:
+   *  br label %L.ph
+   * L.ph:
+   *  %load = load i64 addrspace(10)* %arg
+   *  br label %L
+   * L:
+   *  %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
+   *  %add = add i64 %phi2, 1
+   *  %cond = icmp slt i64 %add, %load ; then becomes 2000.
+   *  br i1 %cond, label %post, label %L2
+   * post:
+   *  ret void
+   *
+   */
+
+  // Create a module with non-integral pointers in it's datalayout
+  Module NIM("nonintegral", Context);
+  std::string DataLayout = M.getDataLayoutStr();
+  if (!DataLayout.empty())
+    DataLayout += "-";
+  DataLayout += "ni:10";
+  NIM.setDataLayout(DataLayout);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+  Type *T_pint64 = T_int64->getPointerTo(10);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
+  Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
+
+  Argument *Arg = &*F->arg_begin();
+
+  BasicBlock *Top = BasicBlock::Create(Context, "top", F);
+  BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
+  BasicBlock *L = BasicBlock::Create(Context, "L", F);
+  BasicBlock *Post = BasicBlock::Create(Context, "post", F);
+
+  IRBuilder<> Builder(Top);
+  Builder.CreateBr(LPh);
+
+  Builder.SetInsertPoint(LPh);
+  auto *Load = cast<Instruction>(Builder.CreateLoad(T_int64, Arg, "load"));
+  Builder.CreateBr(L);
+
+  Builder.SetInsertPoint(L);
+  PHINode *Phi = Builder.CreatePHI(T_int64, 2);
+  auto *Add = cast<Instruction>(
+      Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));
+  auto *Cond = cast<Instruction>(
+      Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond"));
+  auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));
+  Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
+  Phi->addIncoming(Add, L);
+
+  Builder.SetInsertPoint(Post);
+  Builder.CreateRetVoid();
+
+  ScalarEvolution SE = buildSE(*F);
+  auto *Loop = LI->getLoopFor(L);
+  const SCEV *EC = SE.getBackedgeTakenCount(Loop);
+  EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));
+
+  SE.forgetValue(Load);
+  Br->eraseFromParent();
+  Cond->eraseFromParent();
+  Load->eraseFromParent();
+
+  Builder.SetInsertPoint(L);
+  Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000),
+                     "new.cond");
+  Builder.CreateCondBr(Cond, L, Post);
+  const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);
+  EXPECT_NE(EC, NewEC);
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm