[SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided pointer detection

[sbaranga]

Summary

This change adds no wrap SCEV predicates with:

• support for runtime checking
• support for expression rewriting: (sext ({x,+,y}) -> {sext(x),+,sext(y)} (zext ({x,+,y}) -> {zext(x),+,sext(y)}

Note that we are sign extending the increment of the SCEV, even for
the zext case. This is needed to cover the fairly common case where y would
be a (small) negative integer. In order to do this, this change adds two new
flags: nusw and nssw that are applicable to AddRecExprs and permit the
transformations above.

We also change isStridedPtr in LAA to be able to make use of
these predicates. With this feature we should now always be able to
work around overflow issues in the dependence analysis.

[sanjoy]

(Reviewed the SCEV bits)

include/llvm/Analysis/ScalarEvolution.h

273

Nit: notation is {a,+,b}.

286

Nit: I'd return an SCEVAddRecExpr *.

lib/Analysis/ScalarEvolution.cpp

9596

Minor nit: I'd use auto *OF here.

9663

Please either directly pass in a SCEVAddRecExpr or use a cast<> instead of a static_cast<>.

9726

Minor: I'd just put this definition in the header.

9729

I don't think you need to dyn_cast<> to const T. If you're casting from a const pointer, you'll automatically get a const pointer.

9876

Please use cast<SCEVAddRecExpr>

lib/Analysis/ScalarEvolutionExpander.cpp

1964

There is an Instruction::getModule

1986

I think you need to always zero extend the exit count. For instance, if you have a loop with an exit count of i8 255 then i16 {0x7fff,+,1} will sign overflow, even though 0x7fff + (1 * (-1)) will not sign overflow in either the * or the +.

1999

Please assert that AR is affine. Also, it would be easier to read if you extracted out const SCEV *Step = AR->getOperand(1) and used Step here instead.

2021

I don't think this is needed -- the trip count is interpreted as an unsigned value, so you should just need to check that it is ule iDstBits -1.

2044

Minor nit: please call this "sadd" or "uadd" depending on AddF (or just call it "add").

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

2046

Actually, now that I think of it, I don't think this scheme will work for nsw. E.g. if AR is i8 {0,+,1} and TripCount is i8 255 == i8 -1 then neither (i8 1) * (i8 255) == i8 -1 nor 0 + (-1) will sign overflow, while the add recurrence clearly does sign overflow.

I think the most obvious way to check for no nsw is to check sext(Start + TripCount * Step) == sext(Start) + zext(TripCount) * sext(Step), where you extend to 2 * Bitwidth(Start). There could also potentially be a more efficient scheme, but I don't have one with me right now.

[sbaranga]

lib/Analysis/ScalarEvolutionExpander.cpp

2046

Thanks for the catch! This is indeed a problem. I'll think about some more alternatives to this.

[sbaranga]

include/llvm/Analysis/ScalarEvolution.h

286

This is part of the SCEVPredicate interface (and is missing an override), so it has to return a a const SCEV *.

lib/Analysis/ScalarEvolutionExpander.cpp

2046

We might be able to check this without extending by writing TripCount as MAX_INT + x if it larger than MAX_INT,
and doing the check twice? I don't know if this will be more efficient.

This also got me thinking about negative increments as well, and I think that there is an issue with the nuw flag and negative increments: they will always wrap.

We actually want a property that will allow us to sign extend the increment for both the nuw and nsw cases:

zext({a,+,b}) -> {zext(a),+,sext(b)}
sext({a,+,b}) -> {sext(a),+,sext(b)}

We should define separate flags for this property, as the unsigned case doesn't have the same semantics as the nuw flag. I think we should be able to emit checks for this.

[sbaranga]

Renamed SCEVAddRecOverflowPredicate to SCEVWrapPredicate.

SCEVWrapPredicate now has its own flags for NUW/NSW, with
a slightly different meaning of the NUW flag from SCEV.
These flags allow us to do the transformation:

zext({a,+,b}) -> {zext(a),+,sext(b)}
sext({a,+,b}) -> {sext(a),+,sext(b)}

Updated the predicate checking code to use the Sanjoy's
method of checking:

• we extend to a large enough type to remove all possible overflows
• we check that the the final value (without any overflow) is what we would get if we would compute the expression and then do the extend.

This should also address the remaining review comments.

lib/Analysis/ScalarEvolution.cpp

9726

This is a bit difficult. AR is a SCEVAddRecExpr and not a SCEV, and therefore moving this to the header would require casting.

[sbaranga]

Further cleanups: this removes all the remaining occurrences of "AddRecOverflow" and replace them with "Wrap".

Add NoWrapFlags manipulation functions to SCEVWrapPredicate (similar to ScalarEvolution).

Add a getImpliedFlags static method to SCEVWrapPredicate, which deduces the statically
implied flags: the NSW flag can be taken directly from AddRecExprs. The NUW flag can be
transfered only if the the increment of the AddRecExpr is constant and positive).

[sanjoy]

include/llvm/Analysis/ScalarEvolution.h

277

I'm still reading through the patch; but if you must introduce a new concept to replace nuw, it should be called something else to avoid confusion.

279

Do you mean zext(a + b) != ...?

281

I'd be a lot more explicit here. What (I think) you're saying is that

0 <= F(a) + F(b) < 2^n

where the inequalities and arithmetic above are normal inequalities and arithmetic over integers, and F maps an n bit tuple to the integer it represents in twos complement.

Is that correct?

288

Very minor, but why not NoWrapMask = FlagNUW | FlagNSW?

294

Minor, but what about doing some sanity checking on Mask here?

300

Same here and below on clearFlags: some minor sanity checking here would be nice.

319

explicit?

1478

Will clients ever try to RAUW / delete Value s from under this map. If not, this should be changed to use an AssertingVH; otherwise it needs to use a CallbackVH like SCEV.

1483

Minor: can you please check if it possible to make this a const reference?

lib/Analysis/ScalarEvolution.cpp

9608

Please add a comment on what Assume means, and use a more descriptive name if possible.

9668

Why not just return P.implies(A);?

9733

Why not check if Op->Flags is a superset of Flags?

9736

Might also want to return true if Flags == NSW && AR->hasNSW().

9761

This doesn't look correct? You probably want something like Step->getValue()->getValue().isNonNegative().

9892

Please use cast<>

lib/Analysis/ScalarEvolutionExpander.cpp

2002

Please use cast<>

2004

I think you can use ConstantInt::getFalse(IP->getContext()) here.

[sbaranga]

Hi Sanjoy,

Sorry for the delayed reply (holidays..). I should have a new version of this up for review soon.

Thanks,
Silviu

include/llvm/Analysis/ScalarEvolution.h

281

I think almost correct. You would technically need a different function for a, since we regard it as unsigned. So that means

0 <= G(a) + F(b) < 2^n, where F maps to twos complement and G is simple base 2 conversion.

Some examples:

So for a 16-bit example of a = 0xffff and b = 0xfffe we would get F(0xffff) = 2^16 - 1 and G(0xfffe) = -2 and
0 <= 2^16 - 3 < 2^16 which is satisfied.

For a = 0x0, b = 0xffff we get

0 <= -1 < 2^16 which is false.

For a = 0xffff, b = 0x0010 we get

0 <= 2^16 -1 + 2 < 2^16 which is false.

Does this make sense to you?

1478

I think AssertingVH would make the most sense here.

[sbaranga]

Rebase the change and address the current issues raised by Sanjoy in the last review round.

[sbaranga]

include/llvm/Analysis/ScalarEvolution.h

288

There's no reason why we couldn't do that (apart from consistency with SCEV::NoWrapFlags). I have no preference for this.

[sanjoy]

include/llvm/Analysis/ScalarEvolution.h

286

Do you mean G(a) + F(b) here? Might be helpful to name these as Signed and Unsigned instead of F and G.

Might be useful to explicitly note that SCEVWrapPredicate:: IncrementNUW is not commutative, and you're interpreting {a,+,b} as (((a + b) + b) + b) ... for the purposes of SCEVWrapPredicate.

291

Please don't call this nuw (here, and elsewhere in comments) -- I don't think having two definitions of nuw float around it the codebase is a good idea. Pretty much any name other than nuw is fine.

300

What you have here is fine, but I'd have done assert(Flags & IncrementNoWrapMask == Flags) instead.

lib/Analysis/ScalarEvolution.cpp

9635

As mentioned earlier, please don't call this "nuw".

9733

Very minor, but why not return Op && Op->AR == AR && setFlags(Flags, Op->Flags) == Flags; instead of the early exit above?

9741

Minor and optional, but why not have an early return here as return IFlags == IncrementNSW;?

9749

As mentioned earlier, please don't call this <nuw>.

[sbaranga]

include/llvm/Analysis/ScalarEvolution.h

286

Good catch, it should have been G(a) + F(b). It is indeed not commutative. I'll update the text to reflect this.

300

That seems a better way to do it, thanks.

lib/Analysis/ScalarEvolution.cpp

9741

This is a corner case, but that wouldn't work if Flags == IncrementAnyWrap (in which case the predicate would always be true).

[sbaranga]

Rebased and addressed the comments from the last review.

Renamed the new NUW/NSW flags to NUSW and NSSW (No Unsigned/Signed With
Signed increment Wrap) and update the documentation for these flags
according to the last review round.

[sbaranga]

Update some missed comments to reflect the previous renaming (NUW -> NUSW and NSW -> NSSW).

[sbaranga]

After further thinking, we should support RAUW/delete for values in FlagsMap.

This change replaces the DenseMap with a ValueMap (with the default configuration)
which will move the flags to the new value in case of RAUW or remove the entry
in case of delete.

We now also need to explicitly specify the copy contructor for
PredicatedScalarEvolution since ValueMap deletes the default copy constructor.

[sanjoy]

SCEV bits lgtm with minor nits inline.

include/llvm/Analysis/ScalarEvolution.h

296

Do you mean "is already non-commutative"?

302

This is much better, thanks! Might be helpful to clarify htat NSSW is basically nsw, but NUSW is a hybrid specific to SCEVWrapPredicate.

lib/Analysis/ScalarEvolutionExpander.cpp

2011

I'd suggest not generating the redundant or instruction, since it is easy to avoid here.

[anemet]

Hi Silviu,

Just started to look at this (sorry about the delay) and on first impression, I am surprised by the lack of tests. Can't we cover this with LAA tests?

Adam

[sbaranga]

In D15412#336209, @anemet wrote:

Hi Silviu,

Just started to look at this (sorry about the delay) and on first impression, I am surprised by the lack of tests. Can't we cover this with LAA tests?

Adam

Hi Adam,

I've been having some trouble testing this with just LAA (we were bailing out when checking if we can do runtime checks).
However, I can now trigger this by adding noalias on the input pointers, so that problem has been solved and I can trigger all code paths with LAA.

I'll also need your change for loop versioning testing (http://reviews.llvm.org/D16612) in order to test the runtime checks, so I'll wait for that to go in before updating this.

Thanks,
Silviu

[sbaranga]

Add test cases where LAA can use the SCEV predicates to both transform non-AddRecExprs to AddRecExprs and directly add no overflow flags for pointers.
The test cases check both the result of LAA and that LoopVectorize adds run-time checks for the SCEV predicates.

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

812

Do you want to try to coerce the expression into affine/non-wrapping here too? This may be a more common case for C/C++ where we are always inbounds for GEP.

Just asking, it does not have to and probably shouldn't be part of this patch.

913–916

No {}

Also, any particular reason you have a dbg message above but not here?

test/Analysis/LoopAccessAnalysis/wrapping-pointer-versioning.ll

7 ↗

(On Diff #46635)

Isnt't this initialized to 0 in the IR below?

26–27 ↗

(On Diff #46635)

We should include the SCEV for %mul_ext here in a comment between the two. Probably both with and without the added flag on %mul. This is more critical later when more things are going on. This way we'd have the whole reasoning in front of us.

75–78 ↗

(On Diff #46635)

Don't you mean 2 * index as the expression for this part? The GEP is covered later.

[sbaranga]

Address comments from Adam.

[sbaranga]

lib/Analysis/LoopAccessAnalysis.cpp

812

I think that's already covered by the current change, because isStridedPtr will add the predicates if needed (and I think this is only called from isStridedPtr).

This should be better because isStridedPtr might return true even if isNoWrapAddRec returns false (for example in the case of unit strided pointers), and we try to only add predicates when needed.

If we ever end up calling isNoWrapAddRec from somewhere else than isStridedPtr, it would be a good idea to allow coercing here as well.

913–916

Thanks, I intended to add the debug message here as well.

test/Analysis/LoopAccessAnalysis/wrapping-pointer-versioning.ll

27–28 ↗

(On Diff #46770)

Added text with the SCEV expressions for %mul_ext before and after the predicates for all tests.

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

812

OK, that's possible, quite a few things are happening here implicitly. But then please add a test for it. I.e. gep with inbounds but the index not marked with nowrap.

test/Analysis/LoopAccessAnalysis/wrapping-pointer-versioning.ll

99 ↗

(On Diff #46770)

Long line, a few more further down.

[sbaranga]

Added a test case with an inbounds GEPs, with the GEP index
having a non AddRec SCEV expression. This covers more
accurately the case where the input comes from C/C++.

Fixed the long lines in the test.

I've also noticed that the debug messages in isStridedPtr
would get confusing because they would use the SCEV expression
of the pointer before being coerced into an AddRecExpr. This
also changes the debug messages to use the updated expressions.

[sbaranga]

lib/Analysis/LoopAccessAnalysis.cpp

812

I've added a test for this.

FWIW I've looked in detail at what's going on here and I believe there is a chance to improve things: in the added test, OBO->hasNoSignedWrap() returns false, and we therefore bail out.

I think we can deduce the NSW flag from the added SCEV predicates. This would reduce the number of required SCEV predicates by 1.

[anemet]

LGTM too.

test/Analysis/LoopAccessAnalysis/wrapping-pointer-versioning.ll

2 ↗

(On Diff #47009)

Are you planning to change these to use the new loop-versioning pass in a follow-on patch?

249 ↗

(On Diff #47009)

Not AddRecExpr or rather not nsw/nuw?

[sbaranga]

test/Analysis/LoopAccessAnalysis/wrapping-pointer-versioning.ll

2 ↗

(On Diff #47009)

Sure, I'll do that in a follow-up change.

[sbaranga]

Fix a comment in on of the tests.

[sbaranga]

Committed in r260085. Thanks!

-Silviu

include/llvm/Analysis/LoopAccessAnalysis.h

const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
                                       const ValueToValueMap &PtrToStride,
                                       Value *Ptr, Value *OrigPtr = nullptr);
 
 /// \brief Check the stride of the pointer and ensure that it does not wrap in
 /// the address space, assuming \p Preds is true.
 ///
 /// If necessary this method will version the stride of the pointer according
 /// to \p PtrToStride and therefore add a new predicate to \p Preds.
+/// The \p Assume parameter indicates if we are allowed to make additional
+/// run-time assumptions.
 int isStridedPtr(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp,
-                 const ValueToValueMap &StridesMap);
+                 const ValueToValueMap &StridesMap, bool Assume = false);
 
 /// \brief This analysis provides dependence information for the memory accesses
 /// of a loop.
 ///
 /// It runs the analysis for a loop on demand.  This can be initiated by
 /// querying the loop access info via LAA::getInfo.  getInfo return a
 /// LoopAccessInfo object.  See this class for the specifics of what information
 /// is provided.

include/llvm/Analysis/ScalarEvolution.h

namespace llvm {
   class SCEVPredicate : public FoldingSetNode {
     friend struct FoldingSetTrait<SCEVPredicate>;
 
     /// A reference to an Interned FoldingSetNodeID for this node.  The
     /// ScalarEvolution's BumpPtrAllocator holds the data.
     FoldingSetNodeIDRef FastID;
 
   public:
-    enum SCEVPredicateKind { P_Union, P_Equal };
+    enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap };
 
   protected:
     SCEVPredicateKind Kind;
     ~SCEVPredicate() = default;
     SCEVPredicate(const SCEVPredicate&) = default;
     SCEVPredicate &operator=(const SCEVPredicate&) = default;
 
   public:
public:
     const SCEVConstant *getRHS() const { return RHS; }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEVPredicate *P) {
       return P->getKind() == P_Equal;
     }
   };
 
+  /// SCEVWrapPredicate - This class represents an assumption
+  /// made on an AddRec expression. Given an affine AddRec expression
+  /// {a,+,b}, we assume that it has nsw or nuw flags.
+  class SCEVWrapPredicate final : public SCEVPredicate {
+  public:
+    /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
+    /// for FlagNUW. The increment is considered to be signed, and a + b
+    /// (where b is the increment) is considered to wrap if:
+    ///    zext(a + b) != zext(a) + sext(b)
+    ///
+    /// If Signed is a function that takes an n-bit tuple and maps to the
+    /// integer
+    /// domain as the tuples value interpreted as twos complement, and Unsigned
+    /// a
+    /// function that takes an n-bit tuple and maps to the integer domain as
+    /// as the base two value of input tuple, then a + b has IncrementNUW iff:
+    ///
+    /// 0 <= Unsigned(a) + Signed(b) < 2^n
+    ///
+    /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
+    ///
+    /// Note that the IncrementNUSW flag is not commutative: if base + inc
+    /// has IncrementNUSW, then inc + base doesn't neccessarily have this
+    /// property. The reason for this is that this is used for sign/zero
+    /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
+    /// assumed. A {base,+,inc} expression is already commutative with
+    /// regards to base and inc, since it is interpreted as:
+    ///     (((base + inc) + inc) + inc) ...
+    enum IncrementWrapFlags {
+      IncrementAnyWrap = 0,     // No guarantee.
+      IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
+      IncrementNSSW = (1 << 1), // No signed with signed increment wrap.
+      IncrementNoWrapMask = (1 << 2) - 1
+    };
+
+    /// Convenient IncrementWrapFlags manipulation methods.
+    static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT
+    clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
+               SCEVWrapPredicate::IncrementWrapFlags OffFlags) {
+      assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
+      assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
+             "Invalid flags value!");
+      return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
+    }
+
+    static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT
+    maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) {
+      assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
+      assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
+
+      return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);
+    }
+
+    static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT
+    setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
+             SCEVWrapPredicate::IncrementWrapFlags OnFlags) {
+      assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
+      assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
+             "Invalid flags value!");
+
+      return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
+    }
+
+    /// \brief Returns the set of SCEVWrapPredicate no wrap flags implied
+    /// by a SCEVAddRecExpr.
+    static SCEVWrapPredicate::IncrementWrapFlags
+    getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);
+
+  private:
+    const SCEVAddRecExpr *AR;
+    IncrementWrapFlags Flags;
+
+  public:
+    explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
+                               const SCEVAddRecExpr *AR,
+                               IncrementWrapFlags Flags);
+
+    /// \brief Returns the set assumed no overflow flags.
+    IncrementWrapFlags getFlags() const { return Flags; }
+    /// Implementation of the SCEVPredicate interface
+    const SCEV *getExpr() const override;
+    bool implies(const SCEVPredicate *N) const override;
+    void print(raw_ostream &OS, unsigned Depth = 0) const override;
+    bool isAlwaysTrue() const override;
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVPredicate *P) {
+      return P->getKind() == P_Wrap;
+    }
+  };
+
   /// SCEVUnionPredicate - This class represents a composition of other
   /// SCEV predicates, and is the class that most clients will interact with.
   /// This is equivalent to a logical "AND" of all the predicates in the union.
   class SCEVUnionPredicate final : public SCEVPredicate {
   private:
     typedef DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>
         PredicateMap;
 
public:
     /// operating on.
     const DataLayout &getDataLayout() const {
       return F.getParent()->getDataLayout();
     }
 
     const SCEVPredicate *getEqualPredicate(const SCEVUnknown *LHS,
                                            const SCEVConstant *RHS);
 
+    const SCEVPredicate *
+    getWrapPredicate(const SCEVAddRecExpr *AR,
+                     SCEVWrapPredicate::IncrementWrapFlags AddedFlags);
+
     /// Re-writes the SCEV according to the Predicates in \p Preds.
-    const SCEV *rewriteUsingPredicate(const SCEV *Scev, SCEVUnionPredicate &A);
+    const SCEV *rewriteUsingPredicate(const SCEV *Scev, const Loop *L,
+                                      SCEVUnionPredicate &A);
+    /// Tries to convert the \p Scev expression to an AddRec expression,
+    /// adding additional predicates to \p Preds as required.
+    const SCEV *convertSCEVToAddRecWithPredicates(const SCEV *Scev,
+                                                  const Loop *L,
+                                                  SCEVUnionPredicate &Preds);
 
   private:
     /// Compute the backedge taken count knowing the interval difference, the
     /// stride and presence of the equality in the comparison.
     const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
                                bool Equality);
 
     /// Verify if an linear IV with positive stride can overflow when in a

   ///     expression for a single Value is consistent across two different
   ///     getSCEV calls. This means that, for example, once we've obtained
   ///     an AddRec expression for a certain value through expression
   ///     rewriting, we will continue to get an AddRec expression for that
   ///     Value.
   ///   - lowers the number of expression rewrites.
   class PredicatedScalarEvolution {
   public:
-    PredicatedScalarEvolution(ScalarEvolution &SE);
+    PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L);
     const SCEVUnionPredicate &getUnionPredicate() const;
     /// \brief Returns the SCEV expression of V, in the context of the current
     /// SCEV predicate.
     /// The order of transformations applied on the expression of V returned
     /// by ScalarEvolution is guaranteed to be preserved, even when adding new
     /// predicates.
     const SCEV *getSCEV(Value *V);
     /// \brief Adds a new predicate.
     void addPredicate(const SCEVPredicate &Pred);
+    /// \brief Attempts to produce an AddRecExpr for V by adding additional
+    /// SCEV predicates.
+    const SCEV *getAsAddRec(Value *V);
+    /// \brief Proves that V doesn't overflow by adding SCEV predicate.
+    void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
+    /// \brief Returns true if we've proved that V doesn't wrap by means of a
+    /// SCEV predicate.
+    bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
     /// \brief Returns the ScalarEvolution analysis used.
     ScalarEvolution *getSE() const { return &SE; }
 
   private:
     /// \brief Increments the version number of the predicate.
     /// This needs to be called every time the SCEV predicate changes.
     void updateGeneration();
     /// Holds a SCEV and the version number of the SCEV predicate used to
     /// perform the rewrite of the expression.
     typedef std::pair<unsigned, const SCEV *> RewriteEntry;
     /// Maps a SCEV to the rewrite result of that SCEV at a certain version
     /// number. If this number doesn't match the current Generation, we will
     /// need to do a rewrite. To preserve the transformation order of previous
     /// rewrites, we will rewrite the previous result instead of the original
     /// SCEV.
     DenseMap<const SCEV *, RewriteEntry> RewriteMap;
+    /// Records what NoWrap flags we've added to a Value *.
+    DenseMap<AssertingVH<Value>, SCEVWrapPredicate::IncrementWrapFlags>
+        FlagsMap;
     /// The ScalarEvolution analysis.
     ScalarEvolution &SE;
+    /// The analyzed Loop.
+    const Loop &L;
     /// The SCEVPredicate that forms our context. We will rewrite all
     /// expressions assuming that this predicate true.
     SCEVUnionPredicate Preds;
     /// Marks the version of the SCEV predicate used. When rewriting a SCEV
     /// expression we mark it with the version of the predicate. We use this to
     /// figure out if the predicate has changed from the last rewrite of the
     /// SCEV. If so, we need to perform a new rewrite.
     unsigned Generation;
   };
 }
 
 #endif

include/llvm/Analysis/ScalarEvolutionExpander.h

#endif
     /// predicate is false and 1 otherwise.
     Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc);
 
     /// \brief A specialized variant of expandCodeForPredicate, handling the
     /// case when we are expanding code for a SCEVEqualPredicate.
     Value *expandEqualPredicate(const SCEVEqualPredicate *Pred,
                                 Instruction *Loc);
 
+    /// \brief Generates code that evaluates if the \p AR expression will
+    /// overflow.
+    Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc,
+                                 bool Signed);
+
+    /// \brief A specialized variant of expandCodeForPredicate, handling the
+    /// case when we are expanding code for a SCEVWrapPredicate.
+    Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc);
+
     /// \brief A specialized variant of expandCodeForPredicate, handling the
     /// case when we are expanding code for a SCEVUnionPredicate.
     Value *expandUnionPredicate(const SCEVUnionPredicate *Pred,
                                 Instruction *Loc);
 
     /// \brief Set the current IV increment loop and position.
     void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
       assert(!CanonicalMode &&

lib/Analysis/LoopAccessAnalysis.cpp

static bool isInBoundsGep(Value *Ptr) {
   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
     return GEP->isInBounds();
   return false;
 }
 
 /// \brief Return true if an AddRec pointer \p Ptr is unsigned non-wrapping,
 /// i.e. monotonically increasing/decreasing.
 static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
-                           ScalarEvolution *SE, const Loop *L) {
+                           PredicatedScalarEvolution &PSE, const Loop *L) {
   // FIXME: This should probably only return true for NUW.
   if (AR->getNoWrapFlags(SCEV::NoWrapMask))
     return true;
 
   // Scalar evolution does not propagate the non-wrapping flags to values that
   // are derived from a non-wrapping induction variable because non-wrapping
   // could be flow-sensitive.
   //
static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
 
   // The index in GEP is signed.  It is non-wrapping if it's derived from a NSW
   // AddRec using a NSW operation.
   if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(NonConstIndex))
     if (OBO->hasNoSignedWrap() &&
         // Assume constant for other the operand so that the AddRec can be
         // easily found.
         isa<ConstantInt>(OBO->getOperand(1))) {
-      auto *OpScev = SE->getSCEV(OBO->getOperand(0));
+      auto *OpScev = PSE.getSCEV(OBO->getOperand(0));
 
       if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpScev))
         return OpAR->getLoop() == L && OpAR->getNoWrapFlags(SCEV::FlagNSW);
     }
 
   return false;
 }
 
 /// \brief Check whether the access through \p Ptr has a constant stride.
 int llvm::isStridedPtr(PredicatedScalarEvolution &PSE, Value *Ptr,
-                       const Loop *Lp, const ValueToValueMap &StridesMap) {
+                       const Loop *Lp, const ValueToValueMap &StridesMap,
+                       bool Assume) {
   Type *Ty = Ptr->getType();
   assert(Ty->isPointerTy() && "Unexpected non-ptr");
 
   // Make sure that the pointer does not point to aggregate types.
   auto *PtrTy = cast<PointerType>(Ty);
   if (PtrTy->getElementType()->isAggregateType()) {
-    DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
-          << *Ptr << "\n");
+    DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type" << *Ptr
+                 << "\n");
     return 0;
   }
 
   const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
 
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
+  if (Assume && !AR)
+    AR = dyn_cast<SCEVAddRecExpr>(PSE.getAsAddRec(Ptr));
+
   if (!AR) {
-    DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
-          << *Ptr << " SCEV: " << *PtrScev << "\n");
+    DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
+                 << " SCEV: " << *PtrScev << "\n");
     return 0;
   }
 
   // The accesss function must stride over the innermost loop.
   if (Lp != AR->getLoop()) {
     DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " <<
           *Ptr << " SCEV: " << *PtrScev << "\n");
     return 0;
   }
 
   // The address calculation must not wrap. Otherwise, a dependence could be
   // inverted.
   // An inbounds getelementptr that is a AddRec with a unit stride
   // cannot wrap per definition. The unit stride requirement is checked later.
   // An getelementptr without an inbounds attribute and unit stride would have
   // to access the pointer value "0" which is undefined behavior in address
   // space 0, therefore we can also vectorize this case.
   bool IsInBoundsGEP = isInBoundsGep(Ptr);
-  bool IsNoWrapAddRec = isNoWrapAddRec(Ptr, AR, PSE.getSE(), Lp);
+  bool IsNoWrapAddRec =
+      PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
+      isNoWrapAddRec(Ptr, AR, PSE, Lp);
   bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0;
   if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) {
+    if (Assume) {
+      PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
+      IsNoWrapAddRec = true;
+      DEBUG(dbgs() << "LAA: Pointer may wrap in the address space " << *Ptr
+                   << " SCEV: " << *PtrScev
+                   << " added an overflow assumption\n");
+    } else {
       DEBUG(dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
                    << *Ptr << " SCEV: " << *PtrScev << "\n");
       return 0;
     }
+  }
 
   // Check the step is constant.
   const SCEV *Step = AR->getStepRecurrence(*PSE.getSE());
 
   // Calculate the pointer stride and check if it is constant.
   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
   if (!C) {
     DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr <<
int llvm::isStridedPtr(PredicatedScalarEvolution &PSE, Value *Ptr,
   int64_t Rem = StepVal % Size;
   if (Rem)
     return 0;
 
   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
   // know we can't "wrap around the address space". In case of address space
   // zero we know that this won't happen without triggering undefined behavior.
   if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) &&
-      Stride != 1 && Stride != -1)
+      Stride != 1 && Stride != -1) {
+    if (Assume) {
+      // We can avoid this case by adding a run-time check.
+      PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
+    } else
       return 0;
+  }
 
   return Stride;
 }
 
 bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
   switch (Type) {
   case NoDep:
   case Forward:
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   // We cannot check pointers in different address spaces.
   if (APtr->getType()->getPointerAddressSpace() !=
       BPtr->getType()->getPointerAddressSpace())
     return Dependence::Unknown;
 
   const SCEV *AScev = replaceSymbolicStrideSCEV(PSE, Strides, APtr);
   const SCEV *BScev = replaceSymbolicStrideSCEV(PSE, Strides, BPtr);
 
-  int StrideAPtr = isStridedPtr(PSE, APtr, InnermostLoop, Strides);
-  int StrideBPtr = isStridedPtr(PSE, BPtr, InnermostLoop, Strides);
+  int StrideAPtr = isStridedPtr(PSE, APtr, InnermostLoop, Strides, true);
+  int StrideBPtr = isStridedPtr(PSE, BPtr, InnermostLoop, Strides, true);
 
   const SCEV *Src = AScev;
   const SCEV *Sink = BScev;
 
   // If the induction step is negative we have to invert source and sink of the
   // dependence.
   if (StrideAPtr < 0) {
     //Src = BScev;
LoopAccessInfo::addRuntimeChecks(Instruction *Loc) const {
   return addRuntimeChecks(Loc, PtrRtChecking.getChecks());
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT, LoopInfo *LI,
                                const ValueToValueMap &Strides)
-    : PSE(*SE), PtrRtChecking(SE), DepChecker(PSE, L), TheLoop(L), DL(DL),
+    : PSE(*SE, *L), PtrRtChecking(SE), DepChecker(PSE, L), TheLoop(L), DL(DL),
       TLI(TLI), AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
       MaxSafeDepDistBytes(-1U), CanVecMem(false),
       StoreToLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
     analyzeLoop(Strides);
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getEqualPredicate(const SCEVUnknown *LHS,
   if (const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
     return S;
   SCEVEqualPredicate *Eq = new (SCEVAllocator)
       SCEVEqualPredicate(ID.Intern(SCEVAllocator), LHS, RHS);
   UniquePreds.InsertNode(Eq, IP);
   return Eq;
 }
 
+const SCEVPredicate *ScalarEvolution::getWrapPredicate(
+    const SCEVAddRecExpr *AR,
+    SCEVWrapPredicate::IncrementWrapFlags AddedFlags) {
+  FoldingSetNodeID ID;
+  // Unique this node based on the arguments
+  ID.AddInteger(SCEVPredicate::P_Wrap);
+  ID.AddPointer(AR);
+  ID.AddInteger(AddedFlags);
+  void *IP = nullptr;
+  if (const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
+    return S;
+  auto *OF = new (SCEVAllocator)
+      SCEVWrapPredicate(ID.Intern(SCEVAllocator), AR, AddedFlags);
+  UniquePreds.InsertNode(OF, IP);
+  return OF;
+}
+
 namespace {
+
 class SCEVPredicateRewriter : public SCEVRewriteVisitor<SCEVPredicateRewriter> {
 public:
-  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
-                             SCEVUnionPredicate &A) {
-    SCEVPredicateRewriter Rewriter(SE, A);
+  // Rewrites Scev in the context of a loop L and the predicate A.
+  // If Assume is true, rewrite is free to add further predicates to A
+  // such that the result will be an AddRecExpr.
+  static const SCEV *rewrite(const SCEV *Scev, const Loop *L,
+                             ScalarEvolution &SE, SCEVUnionPredicate &A,
+                             bool Assume) {
+    SCEVPredicateRewriter Rewriter(L, SE, A, Assume);
     return Rewriter.visit(Scev);
   }
 
-  SCEVPredicateRewriter(ScalarEvolution &SE, SCEVUnionPredicate &P)
-      : SCEVRewriteVisitor(SE), P(P) {}
+  SCEVPredicateRewriter(const Loop *L, ScalarEvolution &SE,
+                        SCEVUnionPredicate &P, bool Assume)
+      : SCEVRewriteVisitor(SE), P(P), L(L), Assume(Assume) {}
 
   const SCEV *visitUnknown(const SCEVUnknown *Expr) {
     auto ExprPreds = P.getPredicatesForExpr(Expr);
     for (auto *Pred : ExprPreds)
       if (const auto *IPred = dyn_cast<const SCEVEqualPredicate>(Pred))
         if (IPred->getLHS() == Expr)
           return IPred->getRHS();
 
     return Expr;
   }
 
+  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+    const SCEV *Operand = visit(Expr->getOperand());
+    const SCEVAddRecExpr *AR = dyn_cast<const SCEVAddRecExpr>(Operand);
+    if (AR && AR->getLoop() == L && AR->isAffine()) {
+      // This couldn't be folded because the operand didn't have the nuw
+      // flag. Add the nuw flag as an assumption that we could make.
+      const SCEV *Step = AR->getStepRecurrence(SE);
+      Type *Ty = Expr->getType();
+      if (addOverflowAssumption(AR, SCEVWrapPredicate::IncrementNUSW))
+        return SE.getAddRecExpr(SE.getZeroExtendExpr(AR->getStart(), Ty),
+                                SE.getSignExtendExpr(Step, Ty), L,
+                                AR->getNoWrapFlags());
+    }
+    return SE.getZeroExtendExpr(Operand, Expr->getType());
+  }
+
+  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
+    const SCEV *Operand = visit(Expr->getOperand());
+    const SCEVAddRecExpr *AR = dyn_cast<const SCEVAddRecExpr>(Operand);
+    if (AR && AR->getLoop() == L && AR->isAffine()) {
+      // This couldn't be folded because the operand didn't have the nsw
+      // flag. Add the nsw flag as an assumption that we could make.
+      const SCEV *Step = AR->getStepRecurrence(SE);
+      Type *Ty = Expr->getType();
+      if (addOverflowAssumption(AR, SCEVWrapPredicate::IncrementNSSW))
+        return SE.getAddRecExpr(SE.getSignExtendExpr(AR->getStart(), Ty),
+                                SE.getSignExtendExpr(Step, Ty), L,
+                                AR->getNoWrapFlags());
+    }
+    return SE.getSignExtendExpr(Operand, Expr->getType());
+  }
+
 private:
+  bool addOverflowAssumption(const SCEVAddRecExpr *AR,
+                             SCEVWrapPredicate::IncrementWrapFlags AddedFlags) {
+    auto *A = SE.getWrapPredicate(AR, AddedFlags);
+    if (!Assume) {
+      // Check if we've already made this assumption.
+      if (P.implies(A))
+        return true;
+      return false;
+    }
+    P.add(A);
+    return true;
+  }
+
   SCEVUnionPredicate &P;
+  const Loop *L;
+  bool Assume;
 };
 } // end anonymous namespace
 
 const SCEV *ScalarEvolution::rewriteUsingPredicate(const SCEV *Scev,
+                                                   const Loop *L,
                                                    SCEVUnionPredicate &Preds) {
-  return SCEVPredicateRewriter::rewrite(Scev, *this, Preds);
+  return SCEVPredicateRewriter::rewrite(Scev, L, *this, Preds, false);
+}
+
+const SCEV *ScalarEvolution::convertSCEVToAddRecWithPredicates(
+    const SCEV *Scev, const Loop *L, SCEVUnionPredicate &Preds) {
+  return SCEVPredicateRewriter::rewrite(Scev, L, *this, Preds, true);
 }
 
 /// SCEV predicates
 SCEVPredicate::SCEVPredicate(const FoldingSetNodeIDRef ID,
                              SCEVPredicateKind Kind)
     : FastID(ID), Kind(Kind) {}
 
 SCEVEqualPredicate::SCEVEqualPredicate(const FoldingSetNodeIDRef ID,

 bool SCEVEqualPredicate::isAlwaysTrue() const { return false; }
 
 const SCEV *SCEVEqualPredicate::getExpr() const { return LHS; }
 
 void SCEVEqualPredicate::print(raw_ostream &OS, unsigned Depth) const {
   OS.indent(Depth) << "Equal predicate: " << *LHS << " == " << *RHS << "\n";
 }
 
+SCEVWrapPredicate::SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
+                                     const SCEVAddRecExpr *AR,
+                                     IncrementWrapFlags Flags)
+    : SCEVPredicate(ID, P_Wrap), AR(AR), Flags(Flags) {}
+
+const SCEV *SCEVWrapPredicate::getExpr() const { return AR; }
+
+bool SCEVWrapPredicate::implies(const SCEVPredicate *N) const {
+  const auto *Op = dyn_cast<SCEVWrapPredicate>(N);
+
+  return Op && Op->AR == AR && setFlags(Flags, Op->Flags) == Flags;
+}
+
+bool SCEVWrapPredicate::isAlwaysTrue() const {
+  SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags();
+  IncrementWrapFlags IFlags = Flags;
+
+  if (ScalarEvolution::setFlags(ScevFlags, SCEV::FlagNSW) == ScevFlags)
+    IFlags = clearFlags(IFlags, IncrementNSSW);
+
+  return IFlags == IncrementAnyWrap;
+}
+
+void SCEVWrapPredicate::print(raw_ostream &OS, unsigned Depth) const {
+  OS.indent(Depth) << *getExpr() << " Added Flags: ";
+  if (SCEVWrapPredicate::IncrementNUSW & getFlags())
+    OS << "<nusw>";
+  if (SCEVWrapPredicate::IncrementNSSW & getFlags())
+    OS << "<nssw>";
+  OS << "\n";
+}
+
+SCEVWrapPredicate::IncrementWrapFlags
+SCEVWrapPredicate::getImpliedFlags(const SCEVAddRecExpr *AR,
+                                   ScalarEvolution &SE) {
+  IncrementWrapFlags ImpliedFlags = IncrementAnyWrap;
+  SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags();
+
+  // We can safely transfer the NSW flag.
+  if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNSW) == StaticFlags)
+    ImpliedFlags = IncrementNSSW;
+
+  if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNUW) == StaticFlags) {
+    // If the increment is positive, the SCEV NUW flag will also imply the
+    // WrapPredicate NUW flag.
+    if (const auto *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
+      if (Step->getValue()->getValue().isNonNegative())
+        ImpliedFlags = setFlags(ImpliedFlags, IncrementNUSW);
+  }
+
+  return ImpliedFlags;
+}
+
 /// Union predicates don't get cached so create a dummy set ID for it.
 SCEVUnionPredicate::SCEVUnionPredicate()
     : SCEVPredicate(FoldingSetNodeIDRef(nullptr, 0), P_Union) {}
 
 bool SCEVUnionPredicate::isAlwaysTrue() const {
   return all_of(Preds,
                 [](const SCEVPredicate *I) { return I->isAlwaysTrue(); });
 }
void SCEVUnionPredicate::add(const SCEVPredicate *N) {
   const SCEV *Key = N->getExpr();
   assert(Key && "Only SCEVUnionPredicate doesn't have an "
                 " associated expression!");
 
   SCEVToPreds[Key].push_back(N);
   Preds.push_back(N);
 }
 
-PredicatedScalarEvolution::PredicatedScalarEvolution(ScalarEvolution &SE)
-    : SE(SE), Generation(0) {}
+PredicatedScalarEvolution::PredicatedScalarEvolution(ScalarEvolution &SE,
+                                                     Loop &L)
+    : SE(SE), L(L), Generation(0) {}
 
 const SCEV *PredicatedScalarEvolution::getSCEV(Value *V) {
   const SCEV *Expr = SE.getSCEV(V);
   RewriteEntry &Entry = RewriteMap[Expr];
 
   // If we already have an entry and the version matches, return it.
   if (Entry.second && Generation == Entry.first)
     return Entry.second;
 
   // We found an entry but it's stale. Rewrite the stale entry
   // acording to the current predicate.
   if (Entry.second)
     Expr = Entry.second;
 
-  const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, Preds);
+  const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, Preds);
   Entry = {Generation, NewSCEV};
 
   return NewSCEV;
 }
 
 void PredicatedScalarEvolution::addPredicate(const SCEVPredicate &Pred) {
   if (Preds.implies(&Pred))
     return;
   Preds.add(&Pred);
   updateGeneration();
 }
 
 const SCEVUnionPredicate &PredicatedScalarEvolution::getUnionPredicate() const {
   return Preds;
 }
 
 void PredicatedScalarEvolution::updateGeneration() {
   // If the generation number wrapped recompute everything.
   if (++Generation == 0) {
     for (auto &II : RewriteMap) {
       const SCEV *Rewritten = II.second.second;
-      II.second = {Generation, SE.rewriteUsingPredicate(Rewritten, Preds)};
+      II.second = {Generation, SE.rewriteUsingPredicate(Rewritten, &L, Preds)};
     }
   }
 }
+
+void PredicatedScalarEvolution::setNoOverflow(
+    Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags) {
+  const SCEV *Expr = getSCEV(V);
+  const auto *AR = cast<SCEVAddRecExpr>(Expr);
+
+  auto ImpliedFlags = SCEVWrapPredicate::getImpliedFlags(AR, SE);
+
+  // Clear the statically implied flags.
+  Flags = SCEVWrapPredicate::clearFlags(Flags, ImpliedFlags);
+  addPredicate(*SE.getWrapPredicate(AR, Flags));
+
+  auto II = FlagsMap.insert({V, Flags});
+  if (!II.second)
+    II.first->second = SCEVWrapPredicate::setFlags(Flags, II.first->second);
+}
+
+bool PredicatedScalarEvolution::hasNoOverflow(
+    Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags) {
+  const SCEV *Expr = getSCEV(V);
+  const auto *AR = cast<SCEVAddRecExpr>(Expr);
+
+  Flags = SCEVWrapPredicate::clearFlags(
+      Flags, SCEVWrapPredicate::getImpliedFlags(AR, SE));
+
+  auto II = FlagsMap.find(V);
+
+  if (II != FlagsMap.end())
+    Flags = SCEVWrapPredicate::clearFlags(Flags, II->second);
+
+  return Flags == SCEVWrapPredicate::IncrementAnyWrap;
+}
+
+const SCEV *PredicatedScalarEvolution::getAsAddRec(Value *V) {
+  const SCEV *Expr = this->getSCEV(V);
+  const SCEV *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, Preds);
+  updateGeneration();
+  RewriteMap[SE.getSCEV(V)] = {Generation, New};
+  return New;
+}

lib/Analysis/ScalarEvolutionExpander.cpp

 Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
                                             Instruction *IP) {
   assert(IP);
   switch (Pred->getKind()) {
   case SCEVPredicate::P_Union:
     return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
   case SCEVPredicate::P_Equal:
     return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
+  case SCEVPredicate::P_Wrap: {
+    auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
+    return expandWrapPredicate(AddRecPred, IP);
+  }
   }
   llvm_unreachable("Unknown SCEV predicate type");
 }
 
 Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
                                           Instruction *IP) {
   Value *Expr0 = expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP);
   Value *Expr1 = expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP);
 
   Builder.SetInsertPoint(IP);
   auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
   return I;
 }
 
+Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
+                                           Instruction *Loc, bool Signed) {
+  assert(AR->isAffine() && "Cannot generate RT check for "
+                           "non-affine expression");
+
+  const SCEV *ExitCount = SE.getBackedgeTakenCount(AR->getLoop());
+  const SCEV *Step = AR->getStepRecurrence(SE);
+  const SCEV *Start = AR->getStart();
+
+  unsigned DstBits = SE.getTypeSizeInBits(AR->getType());
+  unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
+  unsigned MaxBits = 2 * std::max(DstBits, SrcBits);
+
+  auto *TripCount = SE.getTruncateOrZeroExtend(ExitCount, AR->getType());
+  IntegerType *MaxTy = IntegerType::get(Loc->getContext(), MaxBits);
+
+  assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count");
+
+  const auto *ExtendedTripCount = SE.getZeroExtendExpr(ExitCount, MaxTy);
+  const auto *ExtendedStep = SE.getSignExtendExpr(Step, MaxTy);
+  const auto *ExtendedStart = Signed ? SE.getSignExtendExpr(Start, MaxTy)
+                                     : SE.getZeroExtendExpr(Start, MaxTy);
+
+  const SCEV *End = SE.getAddExpr(Start, SE.getMulExpr(TripCount, Step));
+  const SCEV *RHS = Signed ? SE.getSignExtendExpr(End, MaxTy)
+                           : SE.getZeroExtendExpr(End, MaxTy);
+
+  const SCEV *LHS = SE.getAddExpr(
+      ExtendedStart, SE.getMulExpr(ExtendedTripCount, ExtendedStep));
+
+  // Do all SCEV expansions now.
+  Value *LHSVal = expandCodeFor(LHS, MaxTy, Loc);
+  Value *RHSVal = expandCodeFor(RHS, MaxTy, Loc);
+
+  Builder.SetInsertPoint(Loc);
+
+  return Builder.CreateICmp(ICmpInst::ICMP_NE, RHSVal, LHSVal);
+}
+
+Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred,
+                                         Instruction *IP) {
+  const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
+  Value *Check = ConstantInt::getFalse(IP->getContext());
+
+  // Add a check for NUW
+  if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW)
+    Check = generateOverflowCheck(A, IP, false);
+
+  // Add a check for NSW
+  if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW)
+    Check = Builder.CreateOr(generateOverflowCheck(A, IP, true), Check);
+
+  return Check;
+}
+
 Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,
                                           Instruction *IP) {
   auto *BoolType = IntegerType::get(IP->getContext(), 1);
   Value *Check = ConstantInt::getNullValue(BoolType);
 
   // Loop over all checks in this set.
   for (auto Pred : Union->getPredicates()) {
     auto *NextCheck = expandCodeForPredicate(Pred, IP);
     Builder.SetInsertPoint(IP);
     Check = Builder.CreateOr(Check, NextCheck);
   }
 
   return Check;
 }
 
 namespace {
 // Search for a SCEV subexpression that is not safe to expand.  Any expression
 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
 // instruction, but the important thing is that we prove the denominator is
 // nonzero before expansion.
 //
 // IVUsers already checks that IV-derived expressions are safe. So this check is
 // only needed when the expression includes some subexpression that is not IV
 // derived.
 //
 // Currently, we only allow division by a nonzero constant here. If this is
 // inadequate, we could easily allow division by SCEVUnknown by using
 // ValueTracking to check isKnownNonZero().
 //
 // We cannot generally expand recurrences unless the step dominates the loop
 // header. The expander handles the special case of affine recurrences by
 // scaling the recurrence outside the loop, but this technique isn't generally
 // applicable. Expanding a nested recurrence outside a loop requires computing
 // binomial coefficients. This could be done, but the recurrence has to be in a
 // perfectly reduced form, which can't be guaranteed.
 struct SCEVFindUnsafe {
   ScalarEvolution &SE;
   bool IsUnsafe;

lib/Transforms/Vectorize/LoopVectorize.cpp

if (TC > 0u && TC < TinyTripCountVectorThreshold) {
         DEBUG(dbgs() << "\n");
         emitAnalysisDiag(F, L, Hints, VectorizationReport()
                                           << "vectorization is not beneficial "
                                              "and is not explicitly forced");
         return false;
       }
     }
 
-    PredicatedScalarEvolution PSE(*SE);
+    PredicatedScalarEvolution PSE(*SE, *L);
 
     // Check if it is legal to vectorize the loop.
     LoopVectorizationRequirements Requirements;
     LoopVectorizationLegality LVL(L, PSE, DT, TLI, AA, F, TTI, LAA,
                                   &Requirements, &Hints);
     if (!LVL.canVectorize()) {
       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
       emitMissedWarning(F, L, Hints);

test/Transforms/LoopVectorize/same-base-access.ll

; <label>:25                                      ; preds = %8
   store i32 %27, i32* %k, align 4
   br label %4
 
 ; <label>:28                                      ; preds = %4
   ret i32 0
 }
 
 
-
-; We don't vectorize this function because A[i*7] is scalarized, and the
-; different scalars can in theory wrap around and overwrite other scalar
-; elements. At the moment we only allow read/write access to arrays
-; that are consecutive.
+; A[i*7] is scalarized, and the different scalars can in theory wrap
+; around and overwrite other scalar elements. However we can still
+; vectorize because we can version the loop to avoid this case.
 ; 
 ; void foo(int *a) {
 ;   for (int i=0; i<256; ++i) {
 ;     int x = a[i*7];
 ;     if (x>3)
 ;       x = x*x+x*4;
 ;     a[i*7] = x+3;
 ;   }
 ; }
 
 ; CHECK-LABEL: @func2(
-; CHECK-NOT: <4 x i32>
+; CHECK: <4 x i32>
 ; CHECK: ret
 define i32 @func2(i32* nocapture %a) nounwind uwtable ssp {
   br label %1
 
 ; <label>:1                                       ; preds = %7, %0
   %indvars.iv = phi i64 [ 0, %0 ], [ %indvars.iv.next, %7 ]
   %2 = mul nsw i64 %indvars.iv, 7
   %3 = getelementptr inbounds i32, i32* %a, i64 %2