[SCEV] Apply NSW and NUW flags via poison value analysis

[broune]

Summary

Make Scalar Evolution able to propagate NSW and NUW flags from instructions to SCEVs in some cases. This is based on reasoning about when poison from instructions with these flags would trigger undefined behavior. This gives a 13% speed-up on some Eigen3-based Google-internal microbenchmarks for NVPTX.

There does not seem to be clear agreement about when poison should be considered to propagate through instructions. In this analysis, poison propagates only in cases where that should be uncontroversial.

This change makes LSR able to create induction variables for expressions like &ptr[i + offset] for loops like this:

for (int i = 0; i < limit; ++i) {
  sum += ptr[i + offset];
}

Here ptr is a 64 bit pointer and offset is a 32 bit integer. For NVPTX, LSR currently creates an induction variable for i + offset instead, which is not as fast. Improving this situation is what brings the 13% speed-up on some Eigen3-based Google-internal microbenchmarks for NVPTX.

There are more details in this discussion on llvmdev.
June: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-June/thread.html#87234
July: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-July/thread.html#87392

Patch by Bjarke Roune

[sanjoy]

First round of comments inline. I'll do a more detailed review in the next couple of days.

lib/Analysis/ScalarEvolution.cpp

4205

LLVM convention is auto *.

4284

Same comment as earlier -- I don't think this assert adds much value. You could take Value &V if your really cared about not passing in nullptr, but if I were you I'd just remove the assert.

4287

Nit: propagate.

4307

Question: why isn't undefinedBehaviorIsGuaranteedIfPoison enough? IOW, why can't we have

if (undefinedBehaviorIsGuaranteedIfPoison(BinOp))
  return Flags;
else
  return SCEV::FlagAnyWrap;

4312

LLVM convention is auto *AddRec.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

4095–4096

I think isGuaranteedToExecuteForEveryIteration, propagatesPoison, getOperandThatCausesUndefinedBehaviorIfPoison and undefinedBehaviorIsGuaranteedIfPoison should live in ValueTracking.h, given that ValueTracking contains similar things like isSafeToSpeculativelyExecute.

4099

I don't think these asserts are adding much here. Do you think it will be cleaner to take I and L by reference instead, to indicate this invariant?

4114

Use isa. Also mayThrow implies isa<CallInst> || isa<ResumeInst> and since ResumeInst is a terminator, I think this check can just be isa<CallInst> with a comment that this checks for both infinite loops and throws.

4116

I'd swap this check with the previous one -- otherwise you'll always return false for calls.

4125

I agree these are fairly "obvious", but I'd like to run these by David Majnemer and Nuno Lopes to make sure that these rules are at least congruent on what they have in mind for poison's future.

4130

I don't think this assert adds much. It is fairly obvious that I is expected to be non null and if it is, we'll get a deterministic segfault in I->getOpcode().

4210

Same comment as above about nullness of I.

4263

Some comment as in isGuaranteedToExecuteForEveryIteration for CallInst and mayThrow.

4272

You can directly iterate over I->users().

[broune]

Address Sanjoy's initial comments.

lib/Analysis/ScalarEvolution.cpp

4099

I would have preferred references, but all the other functions in this file take pointers, so I wanted to be consistent. Asserting non-null is itself not consistent with the rest of this file, so I took it out.

4114

Done.

4116

Done.

4125

Thank you. I'm curious what their thoughts are on it.

4130

I removed it.

4205

Done.

4210

I removed it.

4263

Done.

4272

Thanks for the tip.

4284

I removed the assert.

4287

Done.

4307

I added a comment on why the other conditions are necessary. There may be a way around isLoopInvariant, but I'm not 100% sure about that, so I left it in.

[broune]

Added and used isGuaranteedToTransferExecutionToSuccessor (is there a better name?). Also slight improvement to comments.

I checked all the instructions in the langref to see if any others might also not terminate. All I found is that while the langref doesn't explicitly say so, some atomics like atomicrmw do not necessarily terminate if another thread keeps interfering. Looking at the C++14 standard, some thread is guaranteed to make progress but I could not find a statement that any given thread is guaranteed to make progress, so I made isGuaranteedToTransferExecutionToSuccessor conservative on that point.

[hfinkel]

In D11212#206104, @broune wrote:

Added and used isGuaranteedToTransferExecutionToSuccessor (is there a better name?). Also slight improvement to comments.

I checked all the instructions in the langref to see if any others might also not terminate. All I found is that while the langref doesn't explicitly say so, some atomics like atomicrmw do not necessarily terminate if another thread keeps interfering. Looking at the C++14 standard, some thread is guaranteed to make progress but I could not find a statement that any given thread is guaranteed to make progress, so I made isGuaranteedToTransferExecutionToSuccessor conservative on that point.

I think we'll end up needing some additional attribute to let us get the C++ semantics at the IR level, and we do want them, but we also need to support languages like Java where infinite loops are (sadly) well defined. Regarding C++, 1.10p27 says:

The implementation may assume that any thread will eventually do one of the following:
  terminate
  make a call to a library I/O function
  access or modify a volatile object, or
  perform a synchronization operation or an atomic operation

 [Note: This is intended to allow compiler transformations such as removal of empty loops, even
  when termination cannot be proven. — end note ]

And, thus, when we can assume C++ semantics, any thread is guaranteed to make progress, or call some external function, or access a volatile/atomic variable.

[majnemer]

lib/Analysis/ValueTracking.cpp

3369–3370

Left shift by poison is poison, not UB.

3418–3419

Call? Invoke?

[sanjoy]

In D11212#206138, @hfinkel wrote:

In D11212#206104, @broune wrote:

Added and used isGuaranteedToTransferExecutionToSuccessor (is there a better name?). Also slight improvement to comments.

I checked all the instructions in the langref to see if any others might also not terminate. All I found is that while the langref doesn't explicitly say so, some atomics like atomicrmw do not necessarily terminate if another thread keeps interfering. Looking at the C++14 standard, some thread is guaranteed to make progress but I could not find a statement that any given thread is guaranteed to make progress, so I made isGuaranteedToTransferExecutionToSuccessor conservative on that point.

And, thus, when we can assume C++ semantics, any thread is guaranteed to make progress, or call some external function, or access a volatile/atomic variable.

I don't think this is relevant here -- even assuming C++ semantics [edit: unless we can prove the call to be readonly / readnone] CallInst is not guaranteed to always return -- the called function could be stalled doing an infinite number of volatile accesses for instance.

[broune]

Addresses David Majnemer's comment on shl.

[broune]

In D11212#206138, @hfinkel wrote:

In D11212#206104, @broune wrote:

Added and used isGuaranteedToTransferExecutionToSuccessor (is there a better name?). Also slight improvement to comments.

I checked all the instructions in the langref to see if any others might also not terminate. All I found is that while the langref doesn't explicitly say so, some atomics like atomicrmw do not necessarily terminate if another thread keeps interfering. Looking at the C++14 standard, some thread is guaranteed to make progress but I could not find a statement that any given thread is guaranteed to make progress, so I made isGuaranteedToTransferExecutionToSuccessor conservative on that point.

I think we'll end up needing some additional attribute to let us get the C++ semantics at the IR level, and we do want them, but we also need to support languages like Java where infinite loops are (sadly) well defined. Regarding C++, 1.10p27 says:

The implementation may assume that any thread will eventually do one of the following:
  terminate
  make a call to a library I/O function
  access or modify a volatile object, or
  perform a synchronization operation or an atomic operation

 [Note: This is intended to allow compiler transformations such as removal of empty loops, even
  when termination cannot be proven. — end note ]

And, thus, when we can assume C++ semantics, any thread is guaranteed to make progress, or call some external function, or access a volatile/atomic variable.

From the LLVM atomics guide, we have a pass AtomicExpandPass that e.g. can expand atomicrmw into a loop with compare-exchange. There may be a reason that such a loop always terminates, but I'm not aware of one. The expanded loop does meet the requirement that it will continually perform an atomic operation (just not successfully). If that isn't guaranteed to terminate, and AtomicExpandPass is correct in choosing that implementation for atomicrmw, then it's not clear to me that we can assume that atomicrmw terminates.

It may be that we can assume that e.g. atomicrmw always terminates, I just haven't so far been able to convince myself of that, so I decided to be conservative. I also haven't looked into the Java semantics. If you're confident that it's not an issue, I'll go with that.

lib/Analysis/ValueTracking.cpp

3369–3370

You're right, thank you. From the langref on shl:

"If op2 is (statically or dynamically) equal to or larger than the number of bits in op1, the result is undefined."

I had read that as undefined behavior, but it only says undefined, which I'm thinking just means undef. That 0 << poison would be poison makes sense to me, so I'll go with that if no one objects.

3418–3419

I'm not sure what the question is. Are you suggesting that there are some intrinsics that it would be good to handle? This function is conservative, so returning false for Call and Invoke is correct.

[majnemer]

lib/Analysis/ValueTracking.cpp

3418–3419

I misread how propagatesFullPoison is supposed to work. I think the name needs some work.

[broune]

lib/Analysis/ValueTracking.cpp

3418–3419

What thing would you like the name to be clearer about? I'm happy to change it. I could do isGuaranteedToYieldFullPoisonIfGivenFullPoison; it's clearer even if not as succinct. Any suggestions?

[sanjoy]

Second round of review comments inline.

include/llvm/Analysis/ScalarEvolution.h

587

Minor & optional: I'd call this getNoWrapFlagsFromUB.

include/llvm/Analysis/ValueTracking.h

313

Is the indentation a little bit off here?

Actually, I'll just assume you'll run this change through clang-format before checking in, and won't make any further whitespace related comments. Please let me know if you'd prefer otherwise.

327

I'd prefer if you were a little more terse -- perhaps getGuaranteedNonPoisonOp?

(IOW, which operand is guaranteed to not be poison since if it were poison then the program is undefined)

339

Similarly, how about calling this isKnownNotPoison?

lib/Analysis/ScalarEvolution.cpp

4144

I'm not sure that this is correct. I think you need to prove that the instruction you used to justify UB if V was poison is what needs to execute on every loop iteration.

This is not a problem currently because undefinedBehaviorIsGuaranteedIfFullPoison only looks at a single basic block, but semantically, the following program will be problematic:

loop_header:
  %x = add nsw %p, %q
  ...

outside_the_loop:
  ;; no other uses of %x
  store i32 42, GEP(@global, %x)

You can conclude that the %x does not overflow in the last iteration, but that's it -- even if %x was poison in all the other iterations your program is well defined.

lib/Analysis/ValueTracking.cpp

3327

If you're dealing with terminator instructions here (I'm not sure that that is necessary) why is br okay? Can't a br form an infinite loop?

[broune]

Thanks for the comments, Sanjoy. I'll update the code with name changes Monday.

include/llvm/Analysis/ScalarEvolution.h

587

SGTM, I'll make the change.

include/llvm/Analysis/ValueTracking.h

313

Sorry, I need to find a better way to set up my editor. I'll run clang-format before checking in.

327

I wasn't so happy with it myself and I like your suggestion. Maybe getGuaranteedNonFullPoisonOp ? I'll change it Monday.

339

Nice. isKnownNotFullPoison? I'm concerned that it would be too easy to miss the distinction between poison and full-poison and the bugs from that would be hard to shake out.

lib/Analysis/ScalarEvolution.cpp

4144

As you point out, UB is not guaranteed on poison in this example, so even if undefinedBehaviorIsGuaranteedIfFullPoison is made stronger by considering more basic blocks, it should still return false here, right?

lib/Analysis/ValueTracking.cpp

3327

Yes, br can form an infinite loop. This function should still return false for br, as each single execution of br does terminate and then transfers execution to its successor (even if it is its own successor), but I suspect that that's not what you're getting at with this question. :)

Zooming out a bit, what I'm really using this function for is as a component of proving that one instruction B strongly post-dominates another instruction A. Part of that is to prove that there are no infinite paths from A to B, since in such a path we'd never actually get to B, even if B (non-strongly) post-dominates A. In the general case, yes, we'd also need to take into account loops between A and B within the same CFG/function and prove that they terminate. The main reason that I'm only considering one basic block at a time is to make things simpler by avoiding the need for that, since I think that this change is already complex enough as it is. Even then, we still need to look out for single instructions where a single invocation can be enough to prevent strong post-dominance (even within a basic block), and this function serves that purpose.

You're right that this over-all feature could work with a function like this that did not consider terminators. I included terminators anyway just because it gives this function a cohesive responsibility hat makes it easier to think about and it's also what would/will be needed when reasoning about strong post-dominance across basic blocks. I don't have any strong objection to taking the terminators out for now, though.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

4144

In that case why do we bother with isGuaranteedToExecuteForEveryIteration?

IOW, why not

if (undefinedBehaviorIsGuaranteedIfFullPoison(BinOp))
  return Flags;

lib/Analysis/ValueTracking.cpp

3327

I think removing terminators and assert(!isa<Terminator>(I) && "..."); will be an improvement. If we later decide to make the algorithm more precise around control flow, then we can consider adding terminators.

[sanjoy]

lib/Analysis/ValueTracking.cpp

3327

On second thought, I take back what I said and agree with your reasoning -- I think the function is fine as is.

[broune]

lib/Analysis/ScalarEvolution.cpp

4144

That would prove that if BinOp is executed, then what it calculates will not wrap. There is then still the possibility that BinOp is not executed on a given iteration, in which case we have no information about wrapping of the SCEV for that iteration. Then we cannot apply the flag to the SCEV as other instructions in the loop that map to the same SCEV would then also get the flag on the shared SCEV, but we have not actually proven that the shared SCEV does not wrap.

[sanjoy]

Minor nits inline. At this point I think this change is ready to go in once the style / naming fixes are done. However:

• I'd like to take a look at the final change before it goes in.
• I'd also like Andy to take a look before this goes in.

Side comment and optional: have you bootstrapped clang with this change? That's a good sanity check for this sort of change. You may consider bootstrapping with ubsan / asan too to get some extra coverage: the extra control flow the sanitizers add tends to shake out a lot of bugs.

include/llvm/Analysis/ValueTracking.h

293

This is borderline bikeshedding, but the rest of the file specifies behavior as a verb -- Return true if ...

311

Minor: I'd just say "Note that this currently only looks at the loop header". Specifically, I'd avoid using the term "analysis" since that has a specific meaning within LLVM.

327

SGTM.

339

SGTM.

lib/Analysis/ScalarEvolution.cpp

4113

Nitpick: elsewhere you use SCEV not "scev".

4144

Ah, right. You also have a large comment explaining the very same thing -- sorry for making you repeat yourself.

4207

The Do an operation by itself if a no-wrap flag can be applied bit did not parse for me.

lib/Analysis/ValueTracking.cpp

3397

Can't you use for (Value *V : OBO->operands()) here?

[broune]

Comments addressed and ran clang-format.

[broune]

In D11212#208037, @sanjoy wrote: [...]

Side comment and optional: have you bootstrapped clang with this change? That's a good sanity check for this sort of change. You may consider bootstrapping with ubsan / asan too to get some extra coverage: the extra control flow the sanitizers add tends to shake out a lot of bugs.

I'm not sure what this entails, but I made a guess: I took a release-with-asserts build of llvm, built with my patch, and used the binaries from that with cmake like so:

CXX=path/to/release/with/asserts/clang/bin/clang++ CC=path/to/release/with/asserts/clang/bin/clang++ cmake -G Ninja ../llvm -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_ASSERTIONS=Yes

then I did ninja check and ninja check-asan. If that's not what you had in mind, feel free to let me know. I didn't find a guide on how to test LLVM via bootstrapping.

lib/Analysis/ScalarEvolution.cpp

4207

I clarified the comment.

[broune]

Change comments to avoid referring to what this change does as "analysis".

[atrick]

Looks good. Nice comments.

For the goal of reassociating array address computation, I would have tried a different approach, but I think this is still valid and generally adds more power to SCEV.

I trust that Sanjoy has tried to poke enough holes in the logic. Overall, it looks pretty solid to me. Thanks for the thorough review, Sanjoy.

[broune]

Improve handling of case where V is a ConstantExpr in createSCEV.

[sanjoy]

Some very minor non-semantic nits inline, otherwise looks good to me. Feel free to check in as is and fix the nits in a follow up change if you find that more convenient.

include/llvm/Analysis/ValueTracking.h

293

Please fix this in the comments for the other functions you added as well.

lib/Analysis/ScalarEvolution.cpp

4111

Nit: change "rec" to something more descriptive, perhaps "add recurrence"?

lib/Analysis/ValueTracking.cpp

3326

Minor nit: invokes can also throw (see https://llvm.org/bugs/show_bug.cgi?id=24185, especially https://llvm.org/bugs/show_bug.cgi?id=24185). Btw, I got the idea for testing for 24185 bug from reading this function.

[broune]

Tiny update to comments.

[broune]

Thank you to Sanjoy and Andy for the review.

include/llvm/Analysis/ValueTracking.h

293

Argh, sorry about that. Done.

lib/Analysis/ValueTracking.cpp

3326

As I understand the bug, an invoke could throw somewhere other than to the landingpad successor in the CFG, if the landingpad is not a match for the exception thrown, so I updated the comment. I referred to the bug you mentioned.

include/llvm/Analysis/ScalarEvolution.h

private:
     /// of LHS and RHS.
     ///
     bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS);
 
     /// forgetMemoizedResults - Drop memoized information computed for S.
     void forgetMemoizedResults(const SCEV *S);
 
+    /// 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;
 
     // Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be equal
     // to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}.  This is equivalent to
     // proving no signed (resp. unsigned) wrap in {`Start`,+,`Step`} if
     // `ExtendOpTy` is `SCEVSignExtendExpr` (resp. `SCEVZeroExtendExpr`).
     //
     template<typename ExtendOpTy>
     bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
                                    const Loop *L);
 
+    // Return SCEV no-wrap flags that can be proven based on reasoning
+    // about how poison produced from no-wrap flags on this value
+    // (e.g. a nuw add) would trigger undefined behavior on overflow.
+    SCEV::NoWrapFlags getNoWrapFlagsFromPoison(const Value *V);
+
   public:
     static char ID; // Pass identification, replacement for typeid
     ScalarEvolution();
 
     LLVMContext &getContext() const { return F->getContext(); }
 
     /// isSCEVable - Test if values of the given type are analyzable within
     /// the SCEV framework. This primarily includes integer types, and it

include/llvm/Analysis/ValueTracking.h

namespace llvm {
   class APInt;
   class DataLayout;
   class StringRef;
   class MDNode;
   class AssumptionCache;
   class DominatorTree;
   class TargetLibraryInfo;
   class LoopInfo;
+  class Loop;
 
   /// Determine which bits of V are known to be either zero or one and return
   /// them in the KnownZero/KnownOne bit sets.
   ///
   /// This function is defined on values with integer type, values with pointer
   /// type, and vectors of integers.  In the case
   /// where V is a vector, the known zero and known one values are the
   /// same width as the vector element, and the bit is set only if it is true
OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT);
   OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
                                                const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT);
-  
+  /// Returns true if this function can prove that the instruction I will
+  /// always transfer execution to one of its successors (including the next
+  /// instruction that follows within a basic block). E.g. this is not
+  /// guaranteed for function calls that could loop infinitely.
+  ///
+  /// In other words, this function returns false for instructions that may
+  /// transfer execution or fail to transfer execution in a way that is not
+  /// captured in the CFG nor in the sequence of instructions within a basic
+  /// block.
+  ///
+  /// Undefined behavior is assumed not to happen, so e.g. division is
+  /// guaranteed to transfer execution to the following instruction even
+  /// though division by zero might cause undefined behavior.
+  bool isGuaranteedToTransferExecutionToSuccessor(const Instruction* I);
+
+  /// Returns true if this function can prove that the instruction I
+  /// is executed for every iteration of the loop L.
+  ///
+  /// Note that this is currently based on an analysis that only considers
+  /// the loop header.
+  bool isGuaranteedToExecuteForEveryIteration(const Instruction *I,
+                const Loop *L);
+
+  /// Returns true if this function can prove that I is guaranteed to yield
+  /// full-poison (all bits poison) if at least one of its operands are
+  /// full-poison (all bits poison).
+  ///
+  /// The exact rules for how poison propagates through instructions have
+  /// not been settled as of 2015-07-10, so this function is conservative
+  /// and only considers poison to be propagated in uncontroversial
+  /// cases. There is no attempt to track values that may be only partially
+  /// poison.
+  bool propagatesFullPoison(const Instruction *I);
+
+  /// Returns either nullptr or an operand of I such that I will trigger
+  /// undefined behavior if I is executed and that operand has a full-poison
+  /// value (all bits poison).
+  const Value *
+  getOperandThatCausesUndefinedBehaviorIfFullPoison(const Instruction *I);
+
+  /// Returns true if this function can prove that if PoisonI is executed
+  /// and yields a full-poison value (all bits poison), then that will
+  /// trigger undefined behavior.
+  ///
+  /// Note that this is currently based on an analysis that only considers
+  /// the basic block that is the parent of I.
+  bool undefinedBehaviorIsGuaranteedIfFullPoison(const Instruction *PoisonI);
+
   /// \brief Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
     SPF_SMIN,                   // Signed minimum
     SPF_UMIN,                   // Unsigned minimum
     SPF_SMAX,                   // Signed maximum
     SPF_UMAX,                   // Unsigned maximum
     SPF_ABS,                    // Absolute value

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getGEPExpr(Type *PointeeType, const SCEV *BaseExpr,
                             const SmallVectorImpl<const SCEV *> &IndexExprs,
                             bool InBounds) {
   // getSCEV(Base)->getType() has the same address space as Base->getType()
   // because SCEV::getType() preserves the address space.
   Type *IntPtrTy = getEffectiveSCEVType(BaseExpr->getType());
   // FIXME(PR23527): Don't blindly transfer the inbounds flag from the GEP
   // instruction to its SCEV, because the Instruction may be guarded by control
   // flow and the no-overflow bits may not be valid for the expression in any
-  // context.
+  // context. This can be fixed similarly to how these flags are handled for
+  // adds.
   SCEV::NoWrapFlags Wrap = InBounds ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
 
   const SCEV *TotalOffset = getConstant(IntPtrTy, 0);
   // The address space is unimportant. The first thing we do on CurTy is getting
   // its element type.
   Type *CurTy = PointerType::getUnqual(PointeeType);
   for (const SCEV *IndexExpr : IndexExprs) {
     // Compute the (potentially symbolic) offset in bytes for this index.
bool ScalarEvolution::checkValidity(const SCEV *S) const {
   return !F.FindOne;
 }
 
 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
 /// expression and create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
+  const SCEV *S = getExistingSCEV(V);
+  if (S == nullptr) {
+    S = createSCEV(V);
+    ValueExprMap.insert(std::make_pair(SCEVCallbackVH(V, this), S));
+  }
+  return S;
+}
+
+const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
+  assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
+
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;
     if (checkValidity(S))
       return S;
-    else
-      ValueExprMap.erase(I);
   }
-  const SCEV *S = createSCEV(V);
-
-  // The process of creating a SCEV for V may have caused other SCEVs
-  // to have been created, so it's necessary to insert the new entry
-  // from scratch, rather than trying to remember the insert position
-  // above.
-  ValueExprMap.insert(std::make_pair(SCEVCallbackVH(V, this), S));
-  return S;
+  return nullptr;
 }
 
 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
 ///
 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V) {
   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
     return getConstant(
                cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
                           APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1));
     }
 
     return setRange(U, SignHint, ConservativeResult);
   }
 
   return setRange(S, SignHint, ConservativeResult);
 }
 
-/// createSCEV - We know that there is no SCEV for the specified value.
-/// Analyze the expression.
+SCEV::NoWrapFlags
+ScalarEvolution::getNoWrapFlagsFromPoison(const Value *V) {
+  const BinaryOperator *BinOp = cast<BinaryOperator>(V);
+
+  // Return early if there are no flags to propagate to the SCEV.
+  SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
+  if (BinOp->hasNoUnsignedWrap())
+    Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
+  if (BinOp->hasNoSignedWrap())
+    Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
+  if (Flags == SCEV::FlagAnyWrap) {
+    return SCEV::FlagAnyWrap;
+  }
+
+  // Here we check that BinOp is in the header of the innermost loop
+  // containing BinOp, since we only deal with instructions in the loop
+  // header. The actual loop we need to check later will come from a rec, but
+  // getting that requires computing the scev of the operands, which can be
+  // expensive. This check we can do cheaply to rule out some cases early.
+  Loop *innermostContainingLoop = LI->getLoopFor(BinOp->getParent());
+  if (innermostContainingLoop == nullptr ||
+      innermostContainingLoop->getHeader() != BinOp->getParent())
+    return SCEV::FlagAnyWrap;
+
+  if (!undefinedBehaviorIsGuaranteedIfFullPoison(BinOp))
+    return SCEV::FlagAnyWrap;
+
+  // At this point we know that if V is executed, then it does not wrap
+  // according to at least one of NSW or NUW. If V is not executed, then we do
+  // not know if the calculation that V represents would wrap. Multiple
+  // instructions can map to the same SCEV. If we apply NSW or NUW from V to
+  // the SCEV, we must guarantee no wrapping for that SCEV also when it is
+  // derived from other instructions that map to the same SCEV. We cannot make
+  // that guarantee for cases where V is not executed. So we need to find the
+  // loop that V is considered in relation to and prove that V is executed for
+  // every iteration of that loop. That implies that the value that V
+  // calculates does not wrap anywhere in the loop, so then we can apply the
+  // flags to the SCEV.
+  //
+  // We check isLoopInvariant to disambiguate in case we are adding two
+  // recurrences from different loops, so that we know which loop to prove
+  // that V is executed in.
+  for (int OpIndex = 0; OpIndex < 2; ++OpIndex) {
+    const SCEV *Op = getSCEV(BinOp->getOperand(OpIndex));
+    if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
+      const int OtherOpIndex = 1 - OpIndex;
+      const SCEV *OtherOp = getSCEV(BinOp->getOperand(OtherOpIndex));
+      if (isLoopInvariant(OtherOp, AddRec->getLoop()) &&
+          isGuaranteedToExecuteForEveryIteration(BinOp, AddRec->getLoop()))
+        return Flags;
+    }
+  }
+  return SCEV::FlagAnyWrap;
+}
+
+/// createSCEV - We know that there is no SCEV for the specified value.  Analyze
+/// the expression.
 ///
 const SCEV *ScalarEvolution::createSCEV(Value *V) {
   if (!isSCEVable(V->getType()))
     return getUnknown(V);
 
   unsigned Opcode = Instruction::UserOp1;
   if (Instruction *I = dyn_cast<Instruction>(V)) {
     Opcode = I->getOpcode();
const SCEV *ScalarEvolution::createSCEV(Value *V) {
   case Instruction::Add: {
     // The simple thing to do would be to just call getSCEV on both operands
     // and call getAddExpr with the result. However if we're looking at a
     // bunch of things all added together, this can be quite inefficient,
     // because it leads to N-1 getAddExpr calls for N ultimate operands.
     // Instead, gather up all the operands and make a single getAddExpr call.
     // LLVM IR canonical form means we need only traverse the left operands.
     //
-    // Don't apply this instruction's NSW or NUW flags to the new
-    // expression. The instruction may be guarded by control flow that the
-    // no-wrap behavior depends on. Non-control-equivalent instructions can be
-    // mapped to the same SCEV expression, and it would be incorrect to transfer
-    // NSW/NUW semantics to those operations.
+    // FIXME: Expand this handling of NSW and NUW to other instructions, like
+    // sub and mul.
     SmallVector<const SCEV *, 4> AddOps;
-    AddOps.push_back(getSCEV(U->getOperand(1)));
-    for (Value *Op = U->getOperand(0); ; Op = U->getOperand(0)) {
+    for (Value *Op = U; ; Op = U->getOperand(0)) {
       unsigned Opcode = Op->getValueID() - Value::InstructionVal;
-      if (Opcode != Instruction::Add && Opcode != Instruction::Sub)
+      if (Opcode != Instruction::Add && Opcode != Instruction::Sub) {
+        assert(Op != V && "V should be an add");
+        AddOps.push_back(getSCEV(Op));
+        break;
+      }
+
+      if (auto *OpSCEV = getExistingSCEV(Op)) {
+        AddOps.push_back(OpSCEV);
         break;
+      }
+
       U = cast<Operator>(Op);
+
+      // Do an operation by itself if a no-wrap flag can be applied, since the
+      // flag only applies to that particular operation.
+      //
+      // FIXME: Expand this to sub instructions.
+      if (Opcode == Instruction::Add) {
+        SCEV::NoWrapFlags Flags = getNoWrapFlagsFromPoison(U);
+        if (Flags != SCEV::FlagAnyWrap) {
+          AddOps.push_back(getAddExpr(getSCEV(U->getOperand(0)),
+                                      getSCEV(U->getOperand(1)), Flags));
+          break;
+        }
+      }
+
       const SCEV *Op1 = getSCEV(U->getOperand(1));
       if (Opcode == Instruction::Sub)
         AddOps.push_back(getNegativeSCEV(Op1));
       else
         AddOps.push_back(Op1);
     }
-    AddOps.push_back(getSCEV(U->getOperand(0)));
     return getAddExpr(AddOps);
   }
+
   case Instruction::Mul: {
-    // Don't transfer NSW/NUW for the same reason as AddExpr.
+    // FIXME: Transfer NSW/NUW as in AddExpr.
     SmallVector<const SCEV *, 4> MulOps;
     MulOps.push_back(getSCEV(U->getOperand(1)));
     for (Value *Op = U->getOperand(0);
          Op->getValueID() == Instruction::Mul + Value::InstructionVal;
          Op = U->getOperand(0)) {
       U = cast<Operator>(Op);
       MulOps.push_back(getSCEV(U->getOperand(1)));
     }
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
         return getSCEV(U->getOperand(0));
       const APInt &A = CI->getValue();
 
       // Instcombine's ShrinkDemandedConstant may strip bits out of
       // constants, obscuring what would otherwise be a low-bits mask.
       // Use computeKnownBits to compute what ShrinkDemandedConstant
       // knew about to reconstruct a low-bits mask value.
       unsigned LZ = A.countLeadingZeros();
       unsigned TZ = A.countTrailingZeros();
       unsigned BitWidth = A.getBitWidth();
       APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
       computeKnownBits(U->getOperand(0), KnownZero, KnownOne,
                        F->getParent()->getDataLayout(), 0, AC, nullptr, DT);
 
       APInt EffectiveMask =
           APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ);
       if ((LZ != 0 || TZ != 0) && !((~A & ~KnownZero) & EffectiveMask)) {
         const SCEV *MulCount = getConstant(
             ConstantInt::get(getContext(), APInt::getOneBitSet(BitWidth, TZ)));
         return getMulExpr(
             getZeroExtendExpr(
                 getTruncateExpr(
                     getUDivExactExpr(getSCEV(U->getOperand(0)), MulCount),
                     IntegerType::get(getContext(), BitWidth - LZ - TZ)),
                 U->getType()),
             MulCount);
       }
     }
     break;
 
   case Instruction::Or:
     // If the RHS of the Or is a constant, we may have something like:
     // X*4+1 which got turned into X*4|1.  Handle this as an Add so loop
     // optimizations will transparently handle this case.
     //
     // In order for this transformation to be safe, the LHS must be of the
     // form X*(2^n) and the Or constant must be less than 2^n.
     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
       const SCEV *LHS = getSCEV(U->getOperand(0));
       const APInt &CIVal = CI->getValue();
       if (GetMinTrailingZeros(LHS) >=
           (CIVal.getBitWidth() - CIVal.countLeadingZeros())) {
         // Build a plain add SCEV.
         const SCEV *S = getAddExpr(LHS, getSCEV(CI));
         // If the LHS of the add was an addrec and it has no-wrap flags,
         // transfer the no-wrap flags, since an or won't introduce a wrap.
         if (const SCEVAddRecExpr *NewAR = dyn_cast<SCEVAddRecExpr>(S)) {
           const SCEVAddRecExpr *OldAR = cast<SCEVAddRecExpr>(LHS);
           const_cast<SCEVAddRecExpr *>(NewAR)->setNoWrapFlags(
             OldAR->getNoWrapFlags());
         }
         return S;
       }
     }
     break;
   case Instruction::Xor:
     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
       // If the RHS of the xor is a signbit, then this is just an add.
       // Instcombine turns add of signbit into xor as a strength reduction step.
       if (CI->getValue().isSignBit())
         return getAddExpr(getSCEV(U->getOperand(0)),
                           getSCEV(U->getOperand(1)));
 
       // If the RHS of xor is -1, then this is a not operation.
       if (CI->isAllOnesValue())
         return getNotSCEV(getSCEV(U->getOperand(0)));

lib/Analysis/ValueTracking.cpp

if (LHSKnownNonNegative && RHSKnownNonNegative) {
       // Create a simple add instruction, and insert it into the struct.
       return OverflowResult::NeverOverflows;
     }
   }
 
   return OverflowResult::MayOverflow;
 }
 
+bool llvm::isGuaranteedToTransferExecutionToSuccessor(const Instruction* I) {
+  // FIXME: This conservative implementation can be relaxed. E.g. most
+  // atomic operations are guaranteed to terminate on most platforms
+  // and most functions terminate.
+
+  return !I->isAtomic() &&  // atomics may never succeed on some platforms
+    !isa<CallInst>(I) &&  // could throw and might not terminate
+    !isa<InvokeInst>(I) && // might not terminate
+    !isa<ResumeInst>(I) && // has no successors
+    !isa<ReturnInst>(I); // has no successors
+}
+
+bool llvm::isGuaranteedToExecuteForEveryIteration(const Instruction *I,
+                                                  const Loop *L) {
+  // The loop header is guaranteed to be executed for every iteration.
+  //
+  // FIXME: Relax this constraint to cover all basic blocks that are
+  // guaranteed to be executed at every iteration.
+  if (I->getParent() != L->getHeader())
+    return false;
+
+  for (const Instruction &LI : *L->getHeader()) {
+    if (&LI == I)
+      return true;
+    if (!isGuaranteedToTransferExecutionToSuccessor(&LI))
+      return false;
+  }
+  llvm_unreachable("Instruction not contained in its own parent basic block.");
+}
+
+bool llvm::propagatesFullPoison(const Instruction *I) {
+  switch (I->getOpcode()) {
+  case Instruction::Add:
+  case Instruction::Sub:
+  case Instruction::Xor:
+  case Instruction::Trunc:
+  case Instruction::BitCast:
+  case Instruction::AddrSpaceCast:
+    // These operations all propagate poison unconditionally. Note that poison
+    // is not any particular value, so xor or subtraction of poison with
+    // itself still yields poison, not zero.
+    return true;
+
+  case Instruction::AShr:
+  case Instruction::SExt:
+    // For these operations, one bit of the input is replicated across
+    // multiple output bits. A replicated poison bit is still poison.
+    return true;
+
+  case Instruction::Shl: {
+    // Left shift *by* a poison value is undefined behavior, so we can assume
+    // that that does not happen.
+    //
+    // The number of positions to shift is unsigned, so no negative values are
+    // possible there. Left shift by zero places preserves poison. So we only
+    // need to consider left shift by a positive number of places.
+    //
+    // A left shift by a positive number of places leaves the lowest order bit
+    // non-poisoned. However, if such a shift has a no-wrap flag, then we can
+    // make the poison operand violate that flag, yielding a fresh full-poison
+    // value.
+    auto *OBO = cast<OverflowingBinaryOperator>(I);
+    return OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap();
+  }
+
+  case Instruction::Mul: {
+    // A multiplication by zero yields a non-poison zero result, so we need to
+    // rule out zero as an operand. Conservatively, multiplication by a
+    // non-zero constant is not multiplication by zero.
+    //
+    // Multiplication by a non-zero constant can leave some bits
+    // non-poisoned. For example, a multiplication by 2 leaves the lowest
+    // order bit unpoisoned. So we need to consider that.
+    //
+    // Multiplication by 1 preserves poison. If the multiplication has a
+    // no-wrap flag, then we can make the poison operand violate that flag
+    // when multiplied by any integer other than 0 and 1.
+    auto *OBO = cast<OverflowingBinaryOperator>(I);
+    if (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) {
+      for (int OpIndex = 0; OpIndex < 2; ++OpIndex) {
+        if (auto *CI = dyn_cast<ConstantInt>(OBO->getOperand(OpIndex))) {
+          // A ConstantInt cannot yield poison, so we can assume that it is
+          // the other operand that is poison.
+          return !CI->isZero();
+        }
+      }
+    }
+    return false;
+  }
+
+  case Instruction::GetElementPtr:
+    // A GEP implicitly represents a sequence of additions, subtractions,
+    // truncations, sign extensions and multiplications. The multiplications
+    // are by the non-zero sizes of some set of types, so we do not have to be
+    // concerned with multiplication by zero. If the GEP is in-bounds, then
+    // these operations are implicitly no-signed-wrap so poison is propagated
+    // by the arguments above for Add, Sub, Trunc, SExt and Mul.
+    return cast<GEPOperator>(I)->isInBounds();
+
+  default:
+    return false;
+  }
+}
+
+const Value *
+llvm::getOperandThatCausesUndefinedBehaviorIfFullPoison(const Instruction *I) {
+  switch (I->getOpcode()) {
+  case Instruction::Store:
+    return cast<StoreInst>(I)->getPointerOperand();
+
+  case Instruction::Load:
+    return cast<LoadInst>(I)->getPointerOperand();
+
+  case Instruction::AtomicCmpXchg:
+    return cast<AtomicCmpXchgInst>(I)->getPointerOperand();
+
+  case Instruction::AtomicRMW:
+    return cast<AtomicRMWInst>(I)->getPointerOperand();
+
+  case Instruction::UDiv:
+  case Instruction::SDiv:
+  case Instruction::URem:
+  case Instruction::SRem:
+    return I->getOperand(1);
+
+  default:
+    return nullptr;
+  }
+}
+
+bool
+llvm::undefinedBehaviorIsGuaranteedIfFullPoison(const Instruction *PoisonI) {
+  // We currently only look for uses of poison values within the same basic
+  // block, as that makes it easier to guarantee that the uses will be
+  // executed given that PoisonI is executed.
+  //
+  // FIXME: Expand this to consider uses beyond the same basic block. To do
+  // this, look out for the distinction between post-dominance and strong
+  // post-dominance.
+  const BasicBlock *BB = PoisonI->getParent();
+
+  // Set of instructions that we have proved will yield poison if PoisonI
+  // does.
+  SmallSet<const Value *, 16> YieldsPoison;
+  YieldsPoison.insert(PoisonI);
+
+  for (const Instruction *I = PoisonI, *E = BB->end();
+       I != E; I = I->getNextNode()) {
+    if (I != PoisonI) {
+      const Value *UBIfPoison =
+        getOperandThatCausesUndefinedBehaviorIfFullPoison(I);
+      if (UBIfPoison != nullptr && YieldsPoison.count(UBIfPoison))
+        return true;
+      if (!isGuaranteedToTransferExecutionToSuccessor(I))
+        return false;
+    }
+
+    // Mark poison that propagates from I through uses of I.
+    if (YieldsPoison.count(I)) {
+      for (const User *User : I->users()) {
+        const Instruction *UserI = cast<Instruction>(User);
+        if (UserI->getParent() == BB && propagatesFullPoison(UserI))
+          YieldsPoison.insert(User);
+      }
+    }
+  }
+  return false;
+}
+
 static SelectPatternFlavor matchSelectPattern(ICmpInst::Predicate Pred,
                                               Value *CmpLHS, Value *CmpRHS,
                                               Value *TrueVal, Value *FalseVal,
                                               Value *&LHS, Value *&RHS) {
   LHS = CmpLHS;
   RHS = CmpRHS;
 
   // (icmp X, Y) ? X : Y

test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll

 ; RUN: opt < %s -analyze -delinearize  | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o]) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+3][j-4][k+7] = 1.0;
 ; }
 
 ; AddRec: {{{(56 + (8 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{3,+,1}<nw><%for.i>][{-4,+,1}<nw><%for.j>][{7,+,1}<nw><%for.k>]
+; CHECK: ArrayRef[{3,+,1}<nw><%for.i>][{-4,+,1}<nw><%for.j>][{7,+,1}<nuw><nsw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll

 ; RUN: opt < %s -analyze -delinearize | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o], long p, long q, long r) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+p][j+q][k+r] = 1.0;
 ; }
 
 ; AddRec: {{{((8 * ((((%m * %p) + %q) * %o) + %r)) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{%p,+,1}<nw><%for.i>][{%q,+,1}<nw><%for.j>][{%r,+,1}<nw><%for.k>]
+; CHECK: ArrayRef[{%p,+,1}<nw><%for.i>][{%q,+,1}<nw><%for.j>][{%r,+,1}<nsw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A, i64 %p, i64 %q, i64 %r) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

test/Analysis/ScalarEvolution/flags-from-poison.ll

+; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
+
+; Positive and negative tests for inferring flags like nsw from
+; reasoning about how a poison value from overflow would trigger
+; undefined behavior.
+
+define void @foo() {
+  ret void
+}
+
+; Example where an add should get the nsw flag, so that a sext can be
+; distributed over the add.
+define void @test-add-nsw(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-nsw
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+  %index32 = add nsw i32 %i, %offset
+
+; CHECK: %index64 =
+; CHECK: --> {(sext i32 %offset to i64),+,1}<nsw>
+  %index64 = sext i32 %index32 to i64
+
+  %ptr = getelementptr inbounds float, float* %input, i64 %index64
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  call void @foo()
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Example where an add should get the nuw flag.
+define void @test-add-nuw(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-nuw
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nuw>
+  %index32 = add nuw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nuw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; With no load to trigger UB from poison, we cannot infer nsw.
+define void @test-add-no-load(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-no-load
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nuw i32 %i, 1
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; The current analysis is only supposed to look at the loop header, so
+; it should not infer nsw in this case, as that would require looking
+; outside the loop header.
+define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-not-header
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+  br label %loop2
+loop2:
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Same thing as test-add-not-header, but in this case only the load
+; instruction is outside the loop header.
+define void @test-add-not-header2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-not-header2
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  br label %loop2
+loop2:
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; The call instruction makes it not guaranteed that the add will be
+; executed, since it could run forever or throw an exception, so we
+; cannot assume that the UB is realized.
+define void @test-add-call(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-call
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  call void @foo()
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Same issue as test-add-call, but this time the call is between the
+; producer of poison and the load that consumes it.
+define void @test-add-call2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-call2
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  call void @foo()
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Without inbounds, GEP does not propagate poison in the very
+; conservative analysis used here.
+define void @test-add-no-inbounds(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-no-inbounds
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Multiplication by a non-zero constant propagates poison if there is
+; a nuw or nsw flag on the multiplication.
+define void @test-add-mul-propagates(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-mul-propagates
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+  %index32 = add nsw i32 %i, %offset
+
+  %indexmul = mul nuw i32 %index32, 2
+  %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Multiplication by a non-constant should not propagate poison in the
+; very conservative analysis used here.
+define void @test-add-mul-no-propagation(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-mul-no-propagation
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %indexmul = mul nsw i32 %index32, %offset
+  %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Multiplication by a non-zero constant does not propagate poison
+; without a no-wrap flag.
+define void @test-add-mul-no-propagation2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-mul-no-propagation2
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %indexmul = mul i32 %index32, 2
+  %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
+  %nexti = add nsw i32 %i, 1
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Division by poison triggers UB.
+define void @test-add-div(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-div
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %j =
+; CHECK: --> {%offset,+,1}<nsw>
+  %j = add nsw i32 %i, %offset
+
+  %q = sdiv i32 %numIterations, %j
+  %nexti = add nsw i32 %i, 1
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Remainder of poison by non-poison divisor does not trigger UB.
+define void @test-add-div2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-div2
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %j =
+; CHECK: --> {%offset,+,1}<nw>
+  %j = add nsw i32 %i, %offset
+
+  %q = sdiv i32 %j, %numIterations
+  %nexti = add nsw i32 %i, 1
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Store to poison address triggers UB.
+define void @test-add-store(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-store
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  store float 1.0, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Three sequential adds where the middle add should have nsw. There is
+; a special case for sequential adds and this test covers that. We have to
+; put the final add first in the program since otherwise the special case
+; is not triggered, hence the strange basic block ordering.
+define void @test-add-twice(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-twice
+entry:
+  br label %loop
+loop2:
+; CHECK: %seq =
+; CHECK: --> {(2 + %offset),+,1}<nw>
+  %seq = add nsw nuw i32 %index32, 1
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+
+loop:
+  %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+
+  %j = add nsw i32 %i, 1
+; CHECK: %index32 =
+; CHECK: --> {(1 + %offset),+,1}<nsw>
+  %index32 = add nsw i32 %j, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  store float 1.0, float* %ptr, align 4
+  br label %loop2
+exit:
+  ret void
+}

test/Transforms/LoopStrengthReduce/sext-ind-var.ll

+; RUN: opt -loop-reduce -S < %s | FileCheck %s
+
+target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
+target triple = "nvptx64-unknown-unknown"
+
+; LSR used not to be able to generate a float* induction variable in
+; these cases due to scalar evolution not propagating nsw from an
+; instruction to the SCEV, preventing distributing sext into the
+; corresponding addrec.
+
+define float @testadd(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @testadd
+; CHECK: sext i32 %offset to i64
+; CHECK: loop:
+; CHECK-DAG: phi float*
+; CHECK-DAG: phi i32
+; CHECK-NOT: sext
+
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+  %sum = phi float [ %nextsum, %loop ], [ 0.000000e+00, %entry ]
+  %index32 = add nuw nsw i32 %i, %offset
+  %index64 = sext i32 %index32 to i64
+  %ptr = getelementptr inbounds float, float* %input, i64 %index64
+  %addend = load float, float* %ptr, align 4
+  %nextsum = fadd float %sum, %addend
+  %nexti = add nuw nsw i32 %i, 1
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret float %nextsum
+}