Fix a bug w/inbounds invalidation in LFTR (was: Strengthen LFTR's ability to replace IVs)

[reames]

Summary

This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no dynamically live uses, and case 2 is when doing pre-to-post conversion on the same pointer type IV.

As was pointed out in the review thread by Nikita, this is defending against a separate issue from the hasConcreteDef case. This is about poison, that's about undef. Unfortunately, the two are different, see Nikita's comment for a fuller explanation, he explains it well.

[nikic]

lib/Transforms/Scalar/IndVarSimplify.cpp

2106 ↗

(On Diff #203272)

nit: Return true if ... provably

2109 ↗

(On Diff #203272)

nit: s/LoopExisting BB/ExitingBB

2128 ↗

(On Diff #203272)

I feel like there's some confusion here between instructions that have a poison operand and instructions that produce poison. As you're inserting into Visited before doing the propagation test, Visited holds instructions that have a poison operand. However, in the Visited.count(NotPoison) check below you are assuming that Visited instructions return poison.

2143 ↗

(On Diff #203272)

Why is this condition separate? This seems wrong for a) non-dominating store and b) poison being on the value operand, not the pointer operand.

2145 ↗

(On Diff #203272)

I think this isn't right as documented (branching on poison is not UB and there may be abnormal exits), though it seems okay for the purpose we need this.

[nikic]

I think overall doing something like this makes sense: For pointer IVs, we'll pretty much always have either a load or store on it.

[reames]

Cleanup code and fix a couple of bugs in the process.

[reames]

Address a few of Nikita's comment. I ended up heavily revising the structure, so the line locations got a bit confusing.

lib/Transforms/Scalar/IndVarSimplify.cpp

2128 ↗

(On Diff #203272)

See the revised code. It should be a lot more clear on this.

2143 ↗

(On Diff #203272)

That's specifically why it's separate. The LangRef specifically gives an example of a poison value operand to a store being UB.

2145 ↗

(On Diff #203272)

wait, wait. No. Branching on posion is *definitely* UB. Or at least I believe it is! What makes you think otherwise?

[reames]

Revise comments per Nikita's suggestions and some further word smithing of my own.

[nikic]

lib/Transforms/Scalar/IndVarSimplify.cpp

2143 ↗

(On Diff #203272)

Storing poison is not UB for a normal store. Langref seems to say that it is UB for a volatile store, because volatile is externally observable. It only says that in an example though, and it's not clear how that follows from the preceding definitions.

The langref description of poison semantics is really quite bad. It describes the dependence behavior, but does not explain when exactly a dependence on poison triggers immediate UB.

2145 ↗

(On Diff #203272)

I used to think that as well, but unfortunately it's not the case. Branching on poison is not UB itself, you need a side-effect that is control dependent on the poisoned branch. There is a proposal to make branching on poison immediate UB (http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf and https://lists.llvm.org/pipermail/llvm-dev/2016-October/106182.html), but I don't think this went anywhere.

[reames]

lib/Transforms/Scalar/IndVarSimplify.cpp

2143 ↗

(On Diff #203272)

I want to debate this point further, but for the moment, I'll simply remove the special store case. As you point out, even without this it's really useful for pointer IVs, and we can separate that discussion into a separate patch/step.

2145 ↗

(On Diff #203272)

Gah, you're correct. I'd forgotten the unswitching case.

For the moment, I'll remove the branch handling from the current patch, and then come back to figure out how to handle it separately.

That does mean we probably have another bug in LFTR though. We treat a comparison used in the exit test as being concrete which per this discussion seems not guaranteed if the loop contains no side effects.

[reames]

Remove the two cases Nikita noted.

Nikita, do you see any other problems with this? If it looks okay conceptually, my next step will be to write a bunch of tests. I'd like to check this in to IndVarSimplify, and then in a separate reviewed NFC change move it into ValueTracking and common with the existing version as much as possible. Does that seem like a reasonable plan?

I'm not entirely comfortable trying to test this exclusively through LFTR. Any ideas on how to better expose it? (I'm not saying I think testing through LFTR isn't a reasonable starting point to get it committed, just that long term, I think the final code in ValueTracking will be too important to only test through one transform.)

[nikic]

lib/Transforms/Scalar/IndVarSimplify.cpp

2111 ↗

(On Diff #203416)

Rename PoisonI to I and Visited to KnownPoison? PoisonI is a bit odd in that it needn't be itself poison. Can also drop DT argument.

2131 ↗

(On Diff #203416)

I don't understand the phi logic here. If you have

x1 = poison
if (...)
  x2 = not poison
x3 = phi(x1, x2)

then x3 is not guaranteed poison, even though x1 dominates the phi.

2162 ↗

(On Diff #203416)

Should probably swap these conditions.

[nikic]

Regarding testing, if this code is in ValueTracking it would be possible to unit test it: https://github.com/llvm-mirror/llvm/blob/master/unittests/Analysis/ValueTrackingTest.cpp That is provide a bit of IR and then check an instruction with some defined name.

[reames]

Remove the buggy phi code Nikita pointed out and otherwise address last round of comments from Nikita.

[reames]

lib/Transforms/Scalar/IndVarSimplify.cpp

2162 ↗

(On Diff #203416)

Out of curiosity, why? This seems natural to me and seems to fit the existing idiom in ValueTracking.

[nikic]

lib/Transforms/Scalar/IndVarSimplify.cpp

2162 ↗

(On Diff #203416)

That was just a perf consideration. Instruction dominance without OBB is a linear scan.

[reames]

lib/Transforms/Scalar/IndVarSimplify.cpp

2162 ↗

(On Diff #203416)

Oh! The comment ended up shifting lines on the new patch. Yeah, that makes perfect sense!

[reames]

Rebase on top of newly added tests.

After staring at the test diffs, I think we may have to recombine this back into D62936. The problem is that by being willing to switch IVs for pointers (correctly now), we *also* expose more pre-to-post conversion opportunities on the new IVs. So, despite getting the logic about dead IVs right, we're still miscompiling these in the end.

[nikic]

lib/Transforms/Scalar/IndVarSimplify.cpp

2098 ↗

(On Diff #203879)

wit -> with

2106 ↗

(On Diff #203879)

out -> our, though given the generalized formulation used here now, we shouldn't mention "exit block" anymore.

2265 ↗

(On Diff #203879)

Unfortunately, I don't think this is right :( The problem is that hasConcreteDef() deals with a similar but distinct issue: an undef IV, not a poison one.

Consider an IV of the form {undef,+,1} (without nuw/nsw, so never poison). In theory there is nothing wrong with using such an IV. However, due to LLVMs broken implementation of undef, it is generally illegal to add a new use to a value that is potentially undef, because the fact that two uses of undef must be the same will not be preserved. This is why the hasConcreteDef() check is necessary.

Now, the mustExecuteUBIfPoisonOnPathTo() check is correct if we assume that Phi is poison, but not if it is undef, because they have different propagation semantics. For example:

%iv = {undef,+,1}
%or = or %iv, 1
%div = udiv -1, %or
br -> exit

Here, if %iv were poison, then the udiv would trigger UB and it would be safe to add a new use. However, it is only undef here, in which case the udiv will *not* trigger UB. But because the check is performed under the assumption of poison, we'll incorrectly switch to this IV.

[reames]

Minor rebase. As pointed out by previous comments both from myself and Nikita, the entire approach here is broken. This doesn't actually appear to be separable from D62936. Given all the meaningful review has happened here, I'm going to repurpose this review for the bug fix and close that one.

For the moment though, this patch is known stale and needs reworked.

[reames]

First iteration on a combined patch. The tests need updated to reflect the poison/undef split. I'll do that, then rebase on top.

[reames]

Rebase over tweaked tests and address comments from Nikita.

[nikic]

I was going to suggest that we only perform the poison/UB check if the GEP actually is inbounds... but I guess that wouldn't be quite right, as the poison can also come from the start value rather than the increment.

Let me try to summarize all the problems we can run into and how they will be handled as of this patch. Thankfully, our IV always has the simple form IV = {S,+,1}. Then, there are the following cases:

1. S may be undef. Handled by hasConcreteDef().
2. S may be poison. For pointers: Poison/UB check or prevent LFTR. For integers: Not handled.
3. IV may become poison due to nowrap/inbounds on last iteration. For pointers: Poison/UB check or use pre-inc. For integers: Recompute nowrap flags.
4. IV may become poison due to nowrap/inbounds on arbitrary iteration. For pointers: Poison/UB check or prevent LFTR. For integers: Recompute nowrap flags, but recomputation is not fully correct right now.

Notably, we don't handle case 2 for integers. We could drop the pointer type check. Probably better would be to instead handle cases 1&2 together by turning hasConcreteDef() into isNeverUndefOrPoison(). This would be similar to hasConcreteDef(), but also returning false for instructions with poison flags (I think that hasConcreteDef() should be doing that even when checking for undef, because ultimately we'll end up relaxing poison to undef anyway, due to lack of poison representation in IR.) An important case where isNeverUndefOrPoison() returns true is a constant start value, which many of the test cases have, I believe.

Then, we could split handling as follows. First, determine whether an IV can be used at all:

• If pre-inc IV (or a poison-propagating dependent value, including the post-inc IV) is used in current loop condition: Can use IV.
• Otherwise, if S is may be undef or poison: Don't use IV.
• Otherwise, if integer IV or pointer IV without inbounds: Can use IV.
• Otherwise, if UB check on pre-inc IV succeeds: Can use IV.
• Otherwise, don't use IV.

Second, determine what to do about post-inc IV. For integers are recompute flags. For pointers:

• If post-inc IV (or a poison-propagating dependent value) is used in current loop condition: Can use post-inc.
• Otherwise, if UB check on post-inc IV succeeds: Can use post-inc.
• Otherwise, use pre-inc.

I think that this should be close to the best we can do, though things are getting quite complicated here.

(Not saying we should do this in this revision, I'm just trying to sort out my thoughts.)

[reames]

In D62939#1538744, @nikic wrote:

Let me try to summarize all the problems we can run into and how they will be handled as of this patch. Thankfully, our IV always has the simple form IV = {S,+,1}. Then, there are the following cases:
....

2. S may be poison. For pointers: Poison/UB check or prevent LFTR. For integers: Not handled.

...

Actually, think 'S' being poisoned is almost fully handled or maybe even fully handled. If 'S' is poison, then IV must be poison on at least the first iteration. Given that, if we find a side effect which must execute on the path to our exit block, then we've proven we must have executed UB. As such, the program is undefined and we have no further obligations.

The only case where this line of reasoning doesn't work is a) our exit itself isn't evaluated on the first iteration and b) there's some operation within the IV computation which 1) strips poison from a poison input and 2) contributes to the next iteration of the IV.

Do there even exist operations which perform (b)? That would seem to be a contradiction.

If there aren't, then we're fully covered. If there are, then we'd need to find a UB operation on the path to the backedge to ensure poison on a prefix of the iteration space (only) is covered. This would be easy to implement, though I'd prefer to do so in a separate change for sanity at this point. :)

[nikic]

In D62939#1538984, @reames wrote:

Actually, think 'S' being poisoned is almost fully handled or maybe even fully handled. If 'S' is poison, then IV must be poison on at least the first iteration. Given that, if we find a side effect which must execute on the path to our exit block, then we've proven we must have executed UB. As such, the program is undefined and we have no further obligations.

The only case where this line of reasoning doesn't work is a) our exit itself isn't evaluated on the first iteration and b) there's some operation within the IV computation which 1) strips poison from a poison input and 2) contributes to the next iteration of the IV.

Do there even exist operations which perform (b)? That would seem to be a contradiction.

If there aren't, then we're fully covered. If there are, then we'd need to find a UB operation on the path to the backedge to ensure poison on a prefix of the iteration space (only) is covered. This would be easy to implement, though I'd prefer to do so in a separate change for sanity at this point. :)

If the mustExecuteUBIfPoisonOnPathTo() check is performed, then, as you argue, we do handle S being poison properly. It's just that the check is only performed on pointers, but not integers (in this patch).

In any case, let's defer that one, this patch is about pointers. There's one last tweak I'd like to see here: If the condition already depends on the post-inc IV, then we can safely use it. Going through the test cases this is actually the case for most of the regressions in existing tests (I've left comments), so I think it would be very worthwhile to check this case.

lib/Transforms/Scalar/IndVarSimplify.cpp

2080 ↗

(On Diff #203929)

posion -> poison

2092 ↗

(On Diff #203929)

Given the now more general formulation of the function, the mention of "exiting block" should probably be dropped.

test/Transforms/IndVarSimplify/2011-11-01-lftrptr.ll

345 ↗

(On Diff #203929)

Condition already depends on post-inc IV.

test/Transforms/IndVarSimplify/lftr-address-space-pointers.ll

47 ↗

(On Diff #203929)

Condition already depends on post-inc IV.

97 ↗

(On Diff #203929)

Condition already depends on post-inc IV.

test/Transforms/IndVarSimplify/lftr-reuse.ll

56 ↗

(On Diff #203929)

Condition already depends on post-inc IV.

331 ↗

(On Diff #203929)

Condition already depends on post-inc IV.

[reames]

In D62939#1540490, @nikic wrote:

If the mustExecuteUBIfPoisonOnPathTo() check is performed, then, as you argue, we do handle S being poison properly. It's just that the check is only performed on pointers, but not integers (in this patch).

Ah, agreed.

In any case, let's defer that one, this patch is about pointers. There's one last tweak I'd like to see here: If the condition already depends on the post-inc IV, then we can safely use it. Going through the test cases this is actually the case for most of the regressions in existing tests (I've left comments), so I think it would be very worthwhile to check this case.

Very nice observation! Will incorporate and update shortly.

[reames]

Incorporate Nikita's suggestion about IVs which are already post-increment, and just need their formed changed.

[nikic]

LGTM

lib/Transforms/Scalar/IndVarSimplify.cpp

2405 ↗

(On Diff #204364)

We could move IncVar declared below to the top of the function, use it here and also change the CmpIndVar assignment below to CmpIndVar = IncVar. As is, we're accessing this value three times in this function...

[mstorsjo]

This caused a regression, where compilation now crashes. See https://bugs.llvm.org/show_bug.cgi?id=42279 for details.

llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp

 #include "llvm/Transforms/Scalar/IndVarSimplify.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
static bool needsLFTR(Loop *L, BasicBlock *ExitingBB) {
   if (Idx < 0)
     return true;
 
   // Do LFTR if the exit condition's IV is *not* a simple counter.
   Value *IncV = Phi->getIncomingValue(Idx);
   return Phi != getLoopPhiForCounter(IncV, L);
 }
 
+/// Return true if undefined behavior would provable be executed on the path to
+/// OnPathTo if Root produced a posion result.  Note that this doesn't say
+/// anything about whether OnPathTo is actually executed or whether Root is
+/// actually poison.  This can be used to assess whether a new use of Root can
+/// be added at a location which is control equivalent with OnPathTo (such as
+/// immediately before it) without introducing UB which didn't previously
+/// exist.  Note that a false result conveys no information.  
+static bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root,
+                                          Instruction *OnPathTo, 
+                                          DominatorTree *DT) {
+  // Basic approach is to assume Root is poison, propagate poison forward
+  // through all users we can easily track, and then check whether any of those
+  // users are provable UB and must execute before out exiting block might
+  // exit.
+
+  // The set of all recursive users we've visited (which are assumed to all be
+  // poison because of said visit)
+  SmallSet<const Value *, 16> KnownPoison;
+  SmallVector<const Instruction*, 16> Worklist;
+  Worklist.push_back(Root);
+  while (!Worklist.empty()) {
+    const Instruction *I = Worklist.pop_back_val();
+
+    // If we know this must trigger UB on a path leading our target.
+    if (mustTriggerUB(I, KnownPoison) && DT->dominates(I, OnPathTo))
+      return true;
+    
+    // If we can't analyze propagation through this instruction, just skip it
+    // and transitive users.  Safe as false is a conservative result.
+    if (!propagatesFullPoison(I) && I != Root)
+      continue;
+
+    if (KnownPoison.insert(I).second)
+      for (const User *User : I->users())
+        Worklist.push_back(cast<Instruction>(User));
+  }
+
+  // Might be non-UB, or might have a path we couldn't prove must execute on
+  // way to exiting bb. 
+  return false;
+}
+
 /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils
 /// down to checking that all operands are constant and listing instructions
 /// that may hide undef.
 static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited,
                                unsigned Depth) {
   if (isa<Constant>(V))
     return !isa<UndefValue>(V);
 

 /// Search the loop header for a loop counter (anadd rec w/step of one)
 /// suitable for use by LFTR.  If multiple counters are available, select the
 /// "best" one based profitable heuristics.
 ///
 /// BECount may be an i8* pointer type. The pointer difference is already
 /// valid count without scaling the address stride, so it remains a pointer
 /// expression as far as SCEV is concerned.
 static PHINode *FindLoopCounter(Loop *L, BasicBlock *ExitingBB,
-                                const SCEV *BECount, ScalarEvolution *SE) {
+                                const SCEV *BECount,
+                                ScalarEvolution *SE, DominatorTree *DT) {
   uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType());
 
   Value *Cond = cast<BranchInst>(ExitingBB->getTerminator())->getCondition();
 
   // Loop over all of the PHI nodes, looking for a simple counter.
   PHINode *BestPhi = nullptr;
   const SCEV *BestInit = nullptr;
   BasicBlock *LatchBlock = L->getLoopLatch();
if (!hasConcreteDef(Phi)) {
       // execute on each iteration
       if (L->getExitingBlock())
         if (ICmpInst *Cond = getLoopTest(L, ExitingBB))
           if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L) &&
               Phi != getLoopPhiForCounter(Cond->getOperand(1), L))
             continue;
     }
 
+    // Avoid introducing undefined behavior due to poison which didn't exist in
+    // the original program.  (Annoyingly, the rules for poison and undef
+    // propagation are distinct, so this does NOT cover the undef case above.)
+    // We have to ensure that we don't introduce UB by introducing a use on an
+    // iteration where said IV produces poison.  Our strategy here differs for
+    // pointers and integer IVs.  For integers, we strip and reinfer as needed,
+    // see code in linearFunctionTestReplace.  For pointers, we restrict
+    // transforms as there is no good way to reinfer inbounds once lost.
+    if (!Phi->getType()->isIntegerTy() &&
+        !mustExecuteUBIfPoisonOnPathTo(Phi, ExitingBB->getTerminator(), DT))
+      continue;
+    
     const SCEV *Init = AR->getStart();
 
     if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) {
       // Don't force a live loop counter if another IV can be used.
       if (AlmostDeadIV(Phi, LatchBlock, Cond))
         continue;
 
       // Prefer to count-from-zero. This is a more "canonical" counter form. It
linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
   const SCEV *IVCount = BackedgeTakenCount;
 
   assert(L->getLoopLatch() && "Loop no longer in simplified form?");
 
   // If the exiting block is the same as the backedge block, we prefer to
   // compare against the post-incremented value, otherwise we must compare
   // against the preincremented value.
   if (ExitingBB == L->getLoopLatch()) {
+    bool SafeToPostInc = IndVar->getType()->isIntegerTy();
+    if (!SafeToPostInc) {
+      // For pointer IVs, we chose to not strip inbounds which requires us not
+      // to add a potentially UB introducing use.  We need to either a) show
+      // the loop test we're modifying is already in post-inc form, or b) show
+      // that adding a use must not introduce UB.
+      Instruction *Inc =
+        cast<Instruction>(IndVar->getIncomingValueForBlock(L->getLoopLatch()));
+      ICmpInst *LoopTest = getLoopTest(L, ExitingBB);
+      SafeToPostInc = LoopTest->getOperand(0) == Inc ||
+        LoopTest->getOperand(1) == Inc ||
+        mustExecuteUBIfPoisonOnPathTo(Inc, ExitingBB->getTerminator(), DT);
+    }
+    if (SafeToPostInc) {
       // Add one to the "backedge-taken" count to get the trip count.
-    // This addition may overflow, which is valid as long as the comparison is
-    // truncated to BackedgeTakenCount->getType().
+      // This addition may overflow, which is valid as long as the comparison
+      // is truncated to BackedgeTakenCount->getType().
       IVCount = SE->getAddExpr(BackedgeTakenCount,
                                SE->getOne(BackedgeTakenCount->getType()));
       // The BackedgeTaken expression contains the number of times that the
       // backedge branches to the loop header.  This is one less than the
       // number of times the loop executes, so use the incremented indvar.
       CmpIndVar = IndVar->getIncomingValueForBlock(ExitingBB);
     }
+  }
 
   // It may be necessary to drop nowrap flags on the incrementing instruction
   // if either LFTR moves from a pre-inc check to a post-inc check (in which
   // case the increment might have previously been poison on the last iteration
   // only) or if LFTR switches to a different IV that was previously dynamically
   // dead (and as such may be arbitrarily poison). We remove any nowrap flags
   // that SCEV didn't infer for the post-inc addrec (even if we use a pre-inc
   // check), because the pre-inc addrec flags may be adopted from the original
for (BasicBlock *ExitingBB : ExitingBlocks) {
       const SCEV *BETakenCount = SE->getExitCount(L, ExitingBB);
       if (isa<SCEVCouldNotCompute>(BETakenCount))
         continue;
 
       // Better to fold to true (TODO: do so!)
       if (BETakenCount->isZero())
         continue;
       
-      PHINode *IndVar = FindLoopCounter(L, ExitingBB, BETakenCount, SE);
+      PHINode *IndVar = FindLoopCounter(L, ExitingBB, BETakenCount, SE, DT);
       if (!IndVar)
         continue;
       
       // Avoid high cost expansions.  Note: This heuristic is questionable in
       // that our definition of "high cost" is not exactly principled.  
       if (Rewriter.isHighCostExpansion(BETakenCount, L))
         continue;
       

llvm/trunk/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll

 ; CHECK-NEXT:    br label [[FOR_BODY_I86:%.*]]
 ; CHECK:       for.body.i86:
 ; CHECK-NEXT:    [[CMP196_I:%.*]] = icmp ult i32 0, undef
 ; CHECK-NEXT:    br i1 [[CMP196_I]], label [[FOR_BODY21_LR_PH_I:%.*]], label [[FOR_END_I129:%.*]]
 ; CHECK:       for.body21.lr.ph.i:
 ; CHECK-NEXT:    br label [[FOR_BODY21_I:%.*]]
 ; CHECK:       for.body21.i:
 ; CHECK-NEXT:    [[DESTYPIXELPTR_010_I:%.*]] = phi i8* [ null, [[FOR_BODY21_LR_PH_I]] ], [ [[INCDEC_PTR_I:%.*]], [[IF_END_I126:%.*]] ]
+; CHECK-NEXT:    [[X_09_I:%.*]] = phi i32 [ 0, [[FOR_BODY21_LR_PH_I]] ], [ [[INC_I125:%.*]], [[IF_END_I126]] ]
 ; CHECK-NEXT:    br i1 undef, label [[IF_END_I126]], label [[IF_ELSE_I124:%.*]]
 ; CHECK:       if.else.i124:
 ; CHECK-NEXT:    store i8 undef, i8* [[DESTYPIXELPTR_010_I]], align 1
 ; CHECK-NEXT:    br label [[IF_END_I126]]
 ; CHECK:       if.end.i126:
 ; CHECK-NEXT:    [[INCDEC_PTR_I]] = getelementptr inbounds i8, i8* [[DESTYPIXELPTR_010_I]], i32 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[INCDEC_PTR_I]], null
+; CHECK-NEXT:    [[INC_I125]] = add nuw i32 [[X_09_I]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[INC_I125]], undef
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY21_I]], label [[FOR_END_I129_LOOPEXIT:%.*]]
 ; CHECK:       for.end.i129.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END_I129]]
 ; CHECK:       for.end.i129:
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY_I86]], label [[WHILE_COND_LOOPEXIT:%.*]]
 ; CHECK:       while.end:
 ; CHECK-NEXT:    br label [[BAIL:%.*]]
 ; CHECK:       bail:

llvm/trunk/test/Transforms/IndVarSimplify/2011-11-01-lftrptr.ll

 ; PTR64-LABEL: @testnullptr(
 ; PTR64-NEXT:  entry:
 ; PTR64-NEXT:    [[ADD_PTR1603:%.*]] = getelementptr [512 x i8], [512 x i8]* [[BASE:%.*]], i64 0, i64 512
 ; PTR64-NEXT:    br label [[PREHEADER:%.*]]
 ; PTR64:       preheader:
 ; PTR64-NEXT:    [[CMP1604192:%.*]] = icmp ult i8* undef, [[ADD_PTR1603]]
 ; PTR64-NEXT:    br i1 [[CMP1604192]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END1609:%.*]]
 ; PTR64:       for.body.preheader:
-; PTR64-NEXT:    [[SCEVGEP:%.*]] = getelementptr [512 x i8], [512 x i8]* [[BASE]], i64 1, i64 0
 ; PTR64-NEXT:    br label [[FOR_BODY:%.*]]
 ; PTR64:       for.body:
 ; PTR64-NEXT:    [[R_17193:%.*]] = phi i8* [ [[INCDEC_PTR1608:%.*]], [[FOR_BODY]] ], [ null, [[FOR_BODY_PREHEADER]] ]
 ; PTR64-NEXT:    [[INCDEC_PTR1608]] = getelementptr i8, i8* [[R_17193]], i64 1
-; PTR64-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[INCDEC_PTR1608]], [[SCEVGEP]]
-; PTR64-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END1609_LOOPEXIT:%.*]]
+; PTR64-NEXT:    [[CMP1604:%.*]] = icmp ult i8* [[INCDEC_PTR1608]], [[ADD_PTR1603]]
+; PTR64-NEXT:    br i1 [[CMP1604]], label [[FOR_BODY]], label [[FOR_END1609_LOOPEXIT:%.*]]
 ; PTR64:       for.end1609.loopexit:
 ; PTR64-NEXT:    br label [[FOR_END1609]]
 ; PTR64:       for.end1609:
 ; PTR64-NEXT:    unreachable
 ;
 ; PTR32-LABEL: @testnullptr(
 ; PTR32-NEXT:  entry:
 ; PTR32-NEXT:    [[ADD_PTR1603:%.*]] = getelementptr [512 x i8], [512 x i8]* [[BASE:%.*]], i64 0, i64 512
 ; PTR32-NEXT:    br label [[PREHEADER:%.*]]
 ; PTR32:       preheader:
 ; PTR32-NEXT:    [[CMP1604192:%.*]] = icmp ult i8* undef, [[ADD_PTR1603]]
 ; PTR32-NEXT:    br i1 [[CMP1604192]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END1609:%.*]]
 ; PTR32:       for.body.preheader:
-; PTR32-NEXT:    [[SCEVGEP:%.*]] = getelementptr [512 x i8], [512 x i8]* [[BASE]], i32 1, i32 0
 ; PTR32-NEXT:    br label [[FOR_BODY:%.*]]
 ; PTR32:       for.body:
 ; PTR32-NEXT:    [[R_17193:%.*]] = phi i8* [ [[INCDEC_PTR1608:%.*]], [[FOR_BODY]] ], [ null, [[FOR_BODY_PREHEADER]] ]
 ; PTR32-NEXT:    [[INCDEC_PTR1608]] = getelementptr i8, i8* [[R_17193]], i64 1
-; PTR32-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[INCDEC_PTR1608]], [[SCEVGEP]]
-; PTR32-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END1609_LOOPEXIT:%.*]]
+; PTR32-NEXT:    [[CMP1604:%.*]] = icmp ult i8* [[INCDEC_PTR1608]], [[ADD_PTR1603]]
+; PTR32-NEXT:    br i1 [[CMP1604]], label [[FOR_BODY]], label [[FOR_END1609_LOOPEXIT:%.*]]
 ; PTR32:       for.end1609.loopexit:
 ; PTR32-NEXT:    br label [[FOR_END1609]]
 ; PTR32:       for.end1609:
 ; PTR32-NEXT:    unreachable
 ;
 entry:
   %add.ptr1603 = getelementptr [512 x i8], [512 x i8]* %base, i64 0, i64 512
   br label %preheader

llvm/trunk/test/Transforms/IndVarSimplify/lftr-dead-ivs.ll

 ;; IV which dependends on that poison computation in a manner which might
 ;; trigger UB would be incorrect.
 ;; FIXME: This currently shows a miscompile!
 define void @neg_dynamically_dead_inbounds(i1 %always_false) #0 {
 ; CHECK-LABEL: @neg_dynamically_dead_inbounds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[CONT:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[TMP4:%.*]], [[CONT:%.*]] ]
+; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY]] ], [ [[TMP3:%.*]], [[CONT]] ]
 ; CHECK-NEXT:    [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
 ; CHECK-NEXT:    br i1 [[ALWAYS_FALSE:%.*]], label [[NEVER_EXECUTED:%.*]], label [[CONT]]
 ; CHECK:       never_executed:
 ; CHECK-NEXT:    store volatile i8 0, i8* [[TMP3]]
 ; CHECK-NEXT:    br label [[CONT]]
 ; CHECK:       cont:
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[TMP3]], getelementptr (i8, i8* getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), i64 246)
+; CHECK-NEXT:    [[TMP4]] = add nuw i8 [[I_0]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8 [[TMP4]], -10
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:

 define void @dom_store_preinc() #0 {
 ; CHECK-LABEL: @dom_store_preinc(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    store volatile i8 0, i8* [[P_0]]
 ; CHECK-NEXT:    [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[TMP3]], getelementptr (i8, i8* getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), i64 246)
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[P_0]], getelementptr (i8, i8* getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), i64 245)
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:

llvm/trunk/test/Transforms/IndVarSimplify/lftr.ll

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[DOT0:%.*]] = phi i8* [ [[A:%.*]], [[ENTRY]] ], [ [[TMP:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[TMP]] = getelementptr inbounds i8, i8* [[DOT0]], i64 1
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i8, i8* [[DOT0]], align 1
 ; CHECK-NEXT:    [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
 ; CHECK-NEXT:    store i8 [[TMP2]], i8* [[P_0]], align 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[TMP3]], getelementptr (i8, i8* getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 0), i64 240)
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[P_0]], getelementptr inbounds ([240 x i8], [240 x i8]* @data, i64 0, i64 239)
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop: