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

2079

nit: Return true if ... provably

2082

nit: s/LoopExisting BB/ExitingBB

2101

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.

2116

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.

2118

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

2101

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

2116

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

2118

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

2116

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.

2118

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

2116

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.

2118

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

2084

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.

2104

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.

2135

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

2135

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

[nikic]

lib/Transforms/Scalar/IndVarSimplify.cpp

2135

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

[reames]

lib/Transforms/Scalar/IndVarSimplify.cpp

2135

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

wit -> with

2106

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

2265

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

posion -> poison

2092

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

350

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

55

Condition already depends on post-inc IV.

326

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

2411

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.

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 the given instruction must trigger undefined behavior under
+/// the assumption that a) the instructions in Visited are poison, b) at
+/// least one of the instructions operands is in that set, and c) that PoisonI
+/// is assumed to execute. 
+static bool MustTriggerUB(Instruction *I,
+                          const SmallSet<Instruction *, 16>& KnownPoison) {
+  auto *NotPoison =
+    dyn_cast_or_null<Instruction>(getGuaranteedNonFullPoisonOp(I));
+  if (NotPoison != nullptr && KnownPoison.count(NotPoison))
+    return true;
+  return false;
+}
+
+
+
+/// 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 wit 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<Instruction *, 16> KnownPoison;
+  SmallVector<Instruction*, 16> Worklist;
+  Worklist.push_back(Root);
+  while (!Worklist.empty()) {
+    Instruction *I = Worklist.pop_back_val();
+
+    // If we know this must trigger UB on a path leading to our exit...
+    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 (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();
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
     
     // AR may be a pointer type, while BECount is an integer type.
     // AR may be wider than BECount. With eq/ne tests overflow is immaterial.
     // AR may not be a narrower type, or we may never exit.
     uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType());
     if (PhiWidth < BCWidth || !DL.isLegalInteger(PhiWidth))
       continue;
 
-    // Avoid reusing a potentially undef value to compute other values that may
-    // have originally had a concrete definition.
-    if (!hasConcreteDef(Phi)) {
-      // We explicitly allow unknown phis as long as they are already used by
-      // the loop test. In this case we assume that performing LFTR could not
-      // increase the number of undef users.
-      // TODO: Generalize this to allow *any* loop exit which is known to
-      // 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;
-    }
+    // 1) When swiching IVs, we have to ensure that we don't introduce UB which
+    // didn't exist in the original program 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're currently
+    // blatantly incorrect for this cornercase.  See D62936 for context.
+    // 2) Avoid reusing a potentially undef value to compute other values that
+    // may have originally had a concrete definition.
+    auto *ExitTerm = L->getExitingBlock()->getTerminator();
+    if (!mustExecuteUBIfPoisonOnPathTo(Phi, ExitTerm, DT) &&
+        !hasConcreteDef(Phi))
 
     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;
 
if (ExitingBB == L->getLoopLatch()) {
     // 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
   // instruction, while SCEV has to explicitly prove the post-inc nowrap flags.
   // TODO: This handling is inaccurate for one case: If we switch to a
   // dynamically dead IV that wraps on the first loop iteration only, which is
   // not covered by the post-inc addrec. (If the new IV was not dynamically
   // dead, it could not be poison on the first iteration in the first place.)
   Value *IncVar = IndVar->getIncomingValueForBlock(L->getLoopLatch());
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;
       

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

 ; PTR64-NEXT:    br label [[LOOPGUARD:%.*]]
 ; PTR64:       loopguard:
 ; PTR64-NEXT:    [[BI:%.*]] = ptrtoint i8* [[BUF:%.*]] to i32
 ; PTR64-NEXT:    [[EI:%.*]] = ptrtoint i8* [[END:%.*]] to i32
 ; PTR64-NEXT:    [[CNT:%.*]] = sub i32 [[EI]], [[BI]]
 ; PTR64-NEXT:    [[GUARD:%.*]] = icmp ult i32 [[BI]], [[CNT]]
 ; PTR64-NEXT:    br i1 [[GUARD]], label [[PREHEADER:%.*]], label [[EXIT:%.*]]
 ; PTR64:       preheader:
+; PTR64-NEXT:    [[TMP1:%.*]] = shl i32 [[BI]], 1
+; PTR64-NEXT:    [[TMP2:%.*]] = sub i32 [[EI]], [[TMP1]]
+; PTR64-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
+; PTR64-NEXT:    [[LFTR_LIMIT:%.*]] = getelementptr i8, i8* [[BUF]], i64 [[TMP3]]
 ; PTR64-NEXT:    br label [[LOOP:%.*]]
 ; PTR64:       loop:
 ; PTR64-NEXT:    [[P_01_US_US:%.*]] = phi i8* [ [[BUF]], [[PREHEADER]] ], [ [[GEP:%.*]], [[LOOP]] ]
-; PTR64-NEXT:    [[IV:%.*]] = phi i32 [ [[BI]], [[PREHEADER]] ], [ [[IVNEXT:%.*]], [[LOOP]] ]
 ; PTR64-NEXT:    [[GEP]] = getelementptr inbounds i8, i8* [[P_01_US_US]], i64 1
 ; PTR64-NEXT:    [[SNEXT:%.*]] = load i8, i8* [[GEP]]
-; PTR64-NEXT:    [[IVNEXT]] = add nuw i32 [[IV]], 1
-; PTR64-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IVNEXT]], [[CNT]]
+; PTR64-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[GEP]], [[LFTR_LIMIT]]
 ; PTR64-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 ; PTR64:       exit.loopexit:
 ; PTR64-NEXT:    [[SNEXT_LCSSA:%.*]] = phi i8 [ [[SNEXT]], [[LOOP]] ]
 ; PTR64-NEXT:    br label [[EXIT]]
 ; PTR64:       exit:
 ; PTR64-NEXT:    [[RET:%.*]] = phi i8 [ 0, [[LOOPGUARD]] ], [ [[SNEXT_LCSSA]], [[EXIT_LOOPEXIT]] ]
 ; PTR64-NEXT:    ret i8 [[RET]]
 ;
 ; PTR32-LABEL: @testptrint(
 ; PTR32-NEXT:    br label [[LOOPGUARD:%.*]]
 ; PTR32:       loopguard:
 ; PTR32-NEXT:    [[BI:%.*]] = ptrtoint i8* [[BUF:%.*]] to i32
 ; PTR32-NEXT:    [[EI:%.*]] = ptrtoint i8* [[END:%.*]] to i32
 ; PTR32-NEXT:    [[CNT:%.*]] = sub i32 [[EI]], [[BI]]
 ; PTR32-NEXT:    [[GUARD:%.*]] = icmp ult i32 [[BI]], [[CNT]]
 ; PTR32-NEXT:    br i1 [[GUARD]], label [[PREHEADER:%.*]], label [[EXIT:%.*]]
 ; PTR32:       preheader:
+; PTR32-NEXT:    [[TMP1:%.*]] = shl i32 [[BI]], 1
+; PTR32-NEXT:    [[TMP2:%.*]] = sub i32 [[EI]], [[TMP1]]
+; PTR32-NEXT:    [[LFTR_LIMIT:%.*]] = getelementptr i8, i8* [[BUF]], i32 [[TMP2]]
 ; PTR32-NEXT:    br label [[LOOP:%.*]]
 ; PTR32:       loop:
 ; PTR32-NEXT:    [[P_01_US_US:%.*]] = phi i8* [ [[BUF]], [[PREHEADER]] ], [ [[GEP:%.*]], [[LOOP]] ]
-; PTR32-NEXT:    [[IV:%.*]] = phi i32 [ [[BI]], [[PREHEADER]] ], [ [[IVNEXT:%.*]], [[LOOP]] ]
 ; PTR32-NEXT:    [[GEP]] = getelementptr inbounds i8, i8* [[P_01_US_US]], i64 1
 ; PTR32-NEXT:    [[SNEXT:%.*]] = load i8, i8* [[GEP]]
-; PTR32-NEXT:    [[IVNEXT]] = add nuw i32 [[IV]], 1
-; PTR32-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IVNEXT]], [[CNT]]
+; PTR32-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[GEP]], [[LFTR_LIMIT]]
 ; PTR32-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 ; PTR32:       exit.loopexit:
 ; PTR32-NEXT:    [[SNEXT_LCSSA:%.*]] = phi i8 [ [[SNEXT]], [[LOOP]] ]
 ; PTR32-NEXT:    br label [[EXIT]]
 ; PTR32:       exit:
 ; PTR32-NEXT:    [[RET:%.*]] = phi i8 [ 0, [[LOOPGUARD]] ], [ [[SNEXT_LCSSA]], [[EXIT_LOOPEXIT]] ]
 ; PTR32-NEXT:    ret i8 [[RET]]
 ;

 
 preheader:
   %cmp1604192 = icmp ult i8* undef, %add.ptr1603
   br i1 %cmp1604192, label %for.body, label %for.end1609
 
 for.body:
   %r.17193 = phi i8* [ %incdec.ptr1608, %for.body ], [ null, %preheader ]
   %incdec.ptr1608 = getelementptr i8, i8* %r.17193, i64 1
   %cmp1604 = icmp ult i8* %incdec.ptr1608, %add.ptr1603
   br i1 %cmp1604, label %for.body, label %for.end1609
 
 for.end1609:
   unreachable
 }

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

 
 exit:
   ret void
 }
 
 define void @dom_store(i8* %a) #0 {
 ; CHECK-LABEL: @dom_store(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LFTR_LIMIT:%.*]] = getelementptr i8, i8* [[A:%.*]], i64 246
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[TMP4:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ [[A:%.*]], [[ENTRY]] ], [ [[TMP3:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ [[A]], [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
 ; CHECK-NEXT:    store volatile i8 0, i8* [[TMP3]]
-; CHECK-NEXT:    [[TMP4]] = add nuw i8 [[I_0]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8 [[TMP4]], -10
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[TMP3]], [[LFTR_LIMIT]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   %i.0 = phi i8 [ 0, %entry ], [ %tmp4, %loop ]
   %p.0 = phi i8* [ %a, %entry ], [ %tmp3, %loop ]
   %tmp3 = getelementptr inbounds i8, i8* %p.0, i64 1
   store volatile i8 0, i8* %tmp3
   %tmp4 = add i8 %i.0, 1
   %tmp5 = icmp ult i8 %tmp4, -10
   br i1 %tmp5, label %loop, label %exit
 
 exit:
   ret void
 }
 
 define i8 @dom_load(i8* %a) #0 {
 ; CHECK-LABEL: @dom_load(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LFTR_LIMIT:%.*]] = getelementptr i8, i8* [[A:%.*]], i64 246
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[TMP4:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ [[A:%.*]], [[ENTRY]] ], [ [[TMP3:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[P_0:%.*]] = phi i8* [ [[A]], [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[TMP3]] = getelementptr inbounds i8, i8* [[P_0]], i64 1
 ; CHECK-NEXT:    [[V:%.*]] = load i8, i8* [[TMP3]]
-; CHECK-NEXT:    [[TMP4]] = add nuw i8 [[I_0]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8 [[TMP4]], -10
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[TMP3]], [[LFTR_LIMIT]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[V_LCSSA:%.*]] = phi i8 [ [[V]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i8 [[V_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %i.0 = phi i8 [ 0, %entry ], [ %tmp4, %loop ]
   %p.0 = phi i8* [ %a, %entry ], [ %tmp3, %loop ]
   %tmp3 = getelementptr inbounds i8, i8* %p.0, i64 1
   %v = load i8, i8* %tmp3
   %tmp4 = add i8 %i.0, 1
   %tmp5 = icmp ult i8 %tmp4, -10
   br i1 %tmp5, label %loop, label %exit
 
 exit:
   ret i8 %v
 }
 
 define i64 @dom_div(i64 %a) #0 {
 ; CHECK-LABEL: @dom_div(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[A:%.*]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[TMP0]], -10
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[TMP4:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[I_1:%.*]] = phi i64 [ [[A:%.*]], [[ENTRY]] ], [ [[TMP3:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_1:%.*]] = phi i64 [ [[A]], [[ENTRY:%.*]] ], [ [[TMP3:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[TMP3]] = add nuw nsw i64 [[I_1]], 1
 ; CHECK-NEXT:    [[V:%.*]] = udiv i64 5, [[TMP3]]
-; CHECK-NEXT:    [[TMP4]] = add nuw i8 [[I_0]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8 [[TMP4]], -10
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[TMP3]] to i8
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8 [[LFTR_WIDEIV]], [[TMP1]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[V_LCSSA:%.*]] = phi i64 [ [[V]], [[LOOP]] ]
 ; CHECK-NEXT:    ret i64 [[V_LCSSA]]
 ;
 entry:
   br label %loop
 

test/Transforms/IndVarSimplify/lftr-reuse.ll

for.body:
   %p.02 = phi i8* [ %base, %entry ], [ %incdec.ptr, %for.body ]
   ; cruft to make the IV useful
   %sub.ptr.lhs.cast = ptrtoint i8* %p.02 to i64
   %sub.ptr.rhs.cast = ptrtoint i8* %base to i64
   %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
   %conv = trunc i64 %sub.ptr.sub to i8
   store i8 %conv, i8* %p.02
   %incdec.ptr = getelementptr inbounds i8, i8* %p.02, i32 1
   %cmp = icmp ult i8* %incdec.ptr, %add.ptr
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
 ; This test checks that SCEVExpander can handle an outer loop that has been
 ; simplified, and as a result the inner loop's exit test will be rewritten.

 
 return:
   ret void
 }
 
 ; Remove %i which is only used by the exit test.
 ; Verify that SCEV can still compute a backedge count from the sign
 ; extended %n, used for pointer comparison by LFTR.
-;
-; TODO: Fix for PR13371 currently makes this impossible. See
-; IndVarSimplify.cpp hasConcreteDef(). We may want to change to undef rules.
 define void @geplftr(i8* %base, i32 %x, i32 %y, i32 %n) nounwind {
 ; CHECK-LABEL: @geplftr(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X_EXT:%.*]] = sext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[X_EXT]]
 ; CHECK-NEXT:    [[Y_EXT:%.*]] = sext i32 [[Y:%.*]] to i64
 ; CHECK-NEXT:    [[ADD_PTR10:%.*]] = getelementptr inbounds i8, i8* [[ADD_PTR]], i64 [[Y_EXT]]
 ; CHECK-NEXT:    [[LIM:%.*]] = add i32 [[X]], [[N:%.*]]
 ; CHECK-NEXT:    [[CMP_PH:%.*]] = icmp ult i32 [[X]], [[LIM]]
 ; CHECK-NEXT:    br i1 [[CMP_PH]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N]] to i64
+; CHECK-NEXT:    [[LFTR_LIMIT:%.*]] = getelementptr i8, i8* [[ADD_PTR10]], i64 [[TMP0]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INC:%.*]], [[LOOP]] ], [ [[X]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[APTR:%.*]] = phi i8* [ [[INCDEC_PTR:%.*]], [[LOOP]] ], [ [[ADD_PTR10]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr inbounds i8, i8* [[APTR]], i32 1
 ; CHECK-NEXT:    store i8 3, i8* [[APTR]]
-; CHECK-NEXT:    [[INC]] = add nuw i32 [[I]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[INC]], [[LIM]]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8* [[INCDEC_PTR]], [[LFTR_LIMIT]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %x.ext = sext i32 %x to i64
entry:
   %ivend = getelementptr inbounds [256 x i8], [256 x i8]* %base, i32 0, i32 %n
   %cmp.ph = icmp ult i8* %ivstart, %ivend
   br i1 %cmp.ph, label %loop, label %exit
 
 loop:
   %aptr = phi i8* [ %ivstart, %entry ], [ %incdec.ptr, %loop ]
   %incdec.ptr = getelementptr inbounds i8, i8* %aptr, i32 1
   store i8 3, i8* %aptr
   %cmp = icmp ult i8* %incdec.ptr, %ivend
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }