[WIP][ScalarEvolution] Strictly enforce pointer/int type rules.

[efriedma]

Summary

Rules for determining if a SCEV expression is pointer-typed:

1. SCEVUnknown is a pointer if and only if the LLVM IR value is a pointer.
2. SCEVPtrToInt is never a pointer.
3. If any other SCEV expression has no pointer operands, the result is an integer.
4. If a SCEVAddExpr has exactly one pointer operand, the result is a pointer.
5. If a SCEVAddRecExpr's first operand is a pointer, and it has no other pointer operands, the result is a pointer.
6. If a SCEVMinMaxExpr has all pointer operands, the result is a pointer.
7. Otherwise, the SCEV expression is invalid.

I'm not sure how useful rule 6 is in practice. If we exclude it, we can
guarantee that ScalarEvolution::getPointerBase always returns a
SCEVUnknown, which might be a helpful property. Anyway, I'll leave that
for a followup.

Currently has some regression test failures related to LSR; the
generated code is changing. scev-custom-dl.ll currently crashes because
getPointerDiff() can return SCEVCouldNotCompute for exotic pointers.
Otherwise passes regression tests.

Open questions:

1. Is it worth keeping getPointerDiff separate from getMinusSCEV? It's an extra SCEV entry point which is in some sense redundant. But one advantage is that the new API lets us land the changes to various transforms incrementally.
2. How do we want to deal with ScalarEvolution::isImpliedCond? Currently, I have a few targeted bailouts for pointers, but we could just ptrtoint all the operands.
3. What do we do about exotic pointers? None of the places that use getPointerDiff have any handling for failure.
4. What do we do about LSR? CollectFixupsAndInitialFormulae() subtracts two pointers to model an icmp; using getPointerDiff here is correct, but wrecks a bunch of the heuristics because "ptrtoint %x" is not the same SCEV expression as "%x". And LSR is really fragile; touching almost anything to try to address that will affect other tests. Not sure what to do here.

[mkazantsev]

Are pointer SCEVConstants disallowed? If so, why?

[efriedma]

In D104498#2826535, @mkazantsev wrote:

Are pointer SCEVConstants disallowed? If so, why?

It's currently impossible to create such a constant, even without this patch; the API forces the type to an integer type. I don't see any reason to change that. Normal code doesn't do math on pointers with a known integer value.

SCEVUnknown supports pointer-typed constants.

[efriedma]

This patch will probably end up getting split, so the most important bits I'm looking for feedback on are the following:

1. Is this worth doing?
2. Does the getPointerDiff() API make sense?

[reames]

Eli,

I'm not really clear on this yet. I keep debating between this and adding pointer subtraction as a first class concept. I was planning on prototyping the later this week, but ended up busy with something else. Could you give me a week or so to get back to you? If you want to discuss, brainstorming this offline could be really helpful. I keep feeling like I don't have my mind around all of the implications just yet.

The major use cases I've got right now are:

1. backedge taken computation implementation - can definitely be done without
2. SCEV-AA
3. Vectorizer aliasing checks - I think I've convinced myself we only need pointer min/max and not subtract for this.
4. LSR - may be able to dodge issue

Edit...

The interesting case is when we have p - q, and it turns out that q is based on the same object as p. This is the case where p-q has a well defined* difference for two arbitrary pointers. If we read p and q at different moments (e.g. use ptrtoint) for non-integral pointers we can get two unrelated values which hide the true diff between the pointers which maintain the based on relationship. Basically, we need a way to read both p and q at the same "moment".

• By analogy to the current icmp semantics, if p and q were based on different objects, the result would be indeterminate, but must preserve the fact the objects can't overlap. e.g. A pointer 10 bytes under the start of one allocation, can't be less than 90 bytes from the beginning of another 100 byte allocation. There's also an interaction with when p and q are poison due to the "inbounds" rules for GEPs.)

[efriedma]

I'm not sure I understand what the difference would be between ptrtoint(a) - ptrtoint(b) and ptrsubtract(a, b) would be. I guess the idea is that ptrsubtract() would somehow be allowed with non-integral pointers, where ptrtoint wouldn't be legal? So the question is whether we can get away without adding ptrsubtract(), without significantly regressing non-integral pointer handling?

There are some number of places which actually only care whether the difference between two pointers is a constant. We actually have a dedicated method computeConstantDifference() for that, but it's currently weaker than just writing isa<SCEVConstant>(SE.getMinusSCEV(a, b)) or whatever. I experimented with fixing that, but I think we'd need a completely different implementation strategy.

We could improve computeConstantDifference(), and use it various places to reduce the number of places that want a real pointer diff. Along those lines, there are also a few places that want to compute a constant range for the distance between two pointers; we could also add a method for that.

There are also places that either statically know the two SCEVs they're subtracting have the same pointer base, or don't care about the result if the pointer bases are different; we could add a method for that.

If we had all that, I'm not sure we would need the full-power getPointerDiff() anywhere. At least, looking over my patch, all the cases this patch uses getPointerDiff would be covered, I think, except maybe LSR.

[reames]

Spent some further time prototyping this. I mocked up a quick and dirty patch which simply made all calls to getMinusSCEV with two pointer arguments return CouldNotCompute. There were surprisingly few places which needed adjusted both based on failing tests, and some (quick) manual skimming. The end result is something which mostly doesn't crash on make check, but bails out of every pointer subtraction query.

Unfortunately, there's some *major* optimization impact. This is to be expected, but given it's the baseline which is being considered for non-integral pointers, we need to assess whether the impact is reasonable.

A few key points:

1. We completely break dependency analysis as used by the vectorizer, fusion, and distribution passes.
2. We weaken LSRs ability to fold together related expressions.
3. We completely break SCEV-AA.

(1) is somewhat of a non-starter. Before we get to how to craw that back, a digression...

Thinking through what the existing code does for subtraction of non-integral pointers, I'm not sure it's even correct for the general case. When we can find a common base in the expressions, everything works out to an integer result, but in the case we can't, we seem (based on the code) to either crash or generate the ptrtoint after all. I'm going to try to find a test case for this, I haven't managed yet.

Given all of that, I think this is the right approach, but we're going to have to deal with the opt impact. One approach is to add specific folding rules for when the base pointer for the two expressions is the same. I think we can recover most of the impact, and suggest using the proxy of "how many test cases fail if I treat *all* pointers this way* as a reasonable metric. I expect we can drive this "close enough" to zero without too much effort.

Style wise, I really don't see the value in the getPointerDiff api. Most of the places which need to compute a diff work with both pointers and integers. I'd rather just have getMinusSCEV documented as being able to return CouldNotCompute when both operands are pointers.

I also want to preserve the existing "it's an error to query information about CouldNotCompute" structure. Given this, callers should bail before calling isKnownX and friends. We should strengthen asserts on access. A couple of the stack traces got surprisingly far into SCEV before we hit an access assert.

[reames]

FYI, the quick and dirty patch I mentioned in the last comment can be found here: https://reviews.llvm.org/D104761

[reames]

Ok, I remember why I can't create a case where we miss handle non-integral pointer subtraction. We never expand it. We use the subtract form for analysis, but generate the bounds conflict form (using icmps) in the transforms. There's an undocumented assumption that such subtracts aren't safe to expand. Fun. :)

[reames]

(This comment is largely an aside, just recording a thought on a vaguely related topic. This has nothing to do with non-integral pointers directly.)

As a further aside, the overlap check we generate in e.g. loop-versioning-licm* is:

%scevgep = getelementptr i8, i8* %a, i64 4
%scevgep1 = getelementptr i8, i8* %b, i64 4
%bound0 = icmp ult i8* %a, %scevgep1
%bound1 = icmp ult i8* %b, %scevgep
%found.conflict = and i1 %bound0, %bound1

This does gets codegened as two distinct checks on x86.

If subtract of pointers was valid in IR, we could instead write:

%diff = sub i8* %a, %b ;; pretend result type is i64
%bound0 = icmp slt i64 %diff, 4
%bound1 = icmp sgt i64 %diff, -4
%found.conflict = and i1 %bound0, %bound1

Which reduces to:

%diff = sub i8* %a, %b ;; pretend result type is i64
%diff.off = add i64 %diff, 3
%1 = icmp ult i64 %diff.off, 7

• This was the easiest example to exercise, from code structure the loop vectorizer does the same when versioning.

[efriedma]

In D104498#2835013, @reames wrote:

Style wise, I really don't see the value in the getPointerDiff api. Most of the places which need to compute a diff work with both pointers and integers. I'd rather just have getMinusSCEV documented as being able to return CouldNotCompute when both operands are pointers.

Do you mean getMinusSCEV would never generate PtrToInt expressions, or just that it wouldn't generate them for non-integral pointers? I mean, we could make it work either way, but it would probably be easier to support non-integral pointers if all pointers behave the same way.

I also want to preserve the existing "it's an error to query information about CouldNotCompute" structure. Given this, callers should bail before calling isKnownX and friends. We should strengthen asserts on access. A couple of the stack traces got surprisingly far into SCEV before we hit an access assert.

Makes sense.

[reames]

In D104498#2835096, @efriedma wrote:

In D104498#2835013, @reames wrote:

Style wise, I really don't see the value in the getPointerDiff api. Most of the places which need to compute a diff work with both pointers and integers. I'd rather just have getMinusSCEV documented as being able to return CouldNotCompute when both operands are pointers.

Do you mean getMinusSCEV would never generate PtrToInt expressions, or just that it wouldn't generate them for non-integral pointers? I mean, we could make it work either way, but it would probably be easier to support non-integral pointers if all pointers behave the same way.

Conceptual cleanliness says to treat all pointers the same, but I think the code becomes a lot more complicated if we do. I think I would special case NI pointers for the moment.

[efriedma]

Current plan:

1. Change the semantics of getMinusSCEV(): D104806.
2. Fix getMinusSCEV() implementation so it doesn't multiply pointers by -1.
3. Land the small number of remaining changes together with the assertions.

[efriedma]

I'll post a fresh patch with the remaining changes.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// Return the SCEV object corresponding to ~V.
   const SCEV *getNotSCEV(const SCEV *V);
 
   /// Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.
   const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
                            unsigned Depth = 0);
 
+  /// Return LHS-RHS, casted to an integer.
+  const SCEV *getPointerDiff(const SCEV *LHS, const SCEV *RHS);
+
   /// Return a SCEV corresponding to a conversion of the input value to the
   /// specified type.  If the type must be extended, it is zero extended.
   const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
                                       unsigned Depth = 0);
 
   /// Return a SCEV corresponding to a conversion of the input value to the
   /// specified type.  If the type must be extended, it is sign extended.
   const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty,

llvm/lib/Analysis/Delinearization.cpp

for (Instruction &Inst : instructions(F)) {
     for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
 
       const SCEVUnknown *BasePointer =
           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
       // Do not delinearize if we cannot find the base pointer.
       if (!BasePointer)
         break;
-      AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
+      AccessFn = SE->getPointerDiff(AccessFn, BasePointer);
 
       O << "\n";
       O << "Inst:" << Inst << "\n";
       O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
       O << "AccessFunction: " << *AccessFn << "\n";
 
       SmallVector<const SCEV *, 3> Subscripts, Sizes;
       SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));

llvm/lib/Analysis/DependenceAnalysis.cpp

bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X,
   }
   if (SE->isKnownPredicate(Pred, X, Y))
     return true;
   // If SE->isKnownPredicate can't prove the condition,
   // we try the brute-force approach of subtracting
   // and testing the difference.
   // By testing with SE->isKnownPredicate first, we avoid
   // the possibility of overflow when the arguments are constants.
-  const SCEV *Delta = SE->getMinusSCEV(X, Y);
+  const SCEV *Delta = SE->getPointerDiff(X, Y);
   switch (Pred) {
   case CmpInst::ICMP_EQ:
     return Delta->isZero();
   case CmpInst::ICMP_NE:
     return SE->isKnownNonZero(Delta);
   case CmpInst::ICMP_SGE:
     return SE->isKnownNonNegative(Delta);
   case CmpInst::ICMP_SLE:
bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst);
   LLVM_DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst);
   LLVM_DEBUG(dbgs() << ", " << *DstConst->getType() << "\n");
   ++StrongSIVapplications;
   assert(0 < Level && Level <= CommonLevels && "level out of range");
   Level--;
 
-  const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
+  const SCEV *Delta = SE->getPointerDiff(SrcConst, DstConst);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta);
   LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n");
 
   // check that |Delta| < iteration count
   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
     LLVM_DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound);
     LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n");
     const SCEV *AbsDelta =
bool DependenceInfo::weakCrossingSIVtest(
   LLVM_DEBUG(dbgs() << "\tWeak-Crossing SIV test\n");
   LLVM_DEBUG(dbgs() << "\t    Coeff = " << *Coeff << "\n");
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++WeakCrossingSIVapplications;
   assert(0 < Level && Level <= CommonLevels && "Level out of range");
   Level--;
   Result.Consistent = false;
-  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
+  const SCEV *Delta = SE->getPointerDiff(DstConst, SrcConst);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
   NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
   if (Delta->isZero()) {
     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
     ++WeakCrossingSIVsuccesses;
     if (!Result.DV[Level].Direction) {
       ++WeakCrossingSIVindependence;
bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
   LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
   LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++ExactSIVapplications;
   assert(0 < Level && Level <= CommonLevels && "Level out of range");
   Level--;
   Result.Consistent = false;
-  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
+  const SCEV *Delta = SE->getPointerDiff(DstConst, SrcConst);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
   NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta,
                         CurLoop);
   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
     return false;
bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff,
   LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");
   LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << "\n");
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++WeakZeroSIVapplications;
   assert(0 < Level && Level <= MaxLevels && "Level out of range");
   Level--;
   Result.Consistent = false;
-  const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
+  const SCEV *Delta = SE->getPointerDiff(SrcConst, DstConst);
   NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta,
                         CurLoop);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
   if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) {
     if (Level < CommonLevels) {
       Result.DV[Level].Direction &= Dependence::DVEntry::GE;
       Result.DV[Level].PeelFirst = true;
       ++WeakZeroSIVsuccesses;
bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff,
   LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");
   LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << "\n");
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++WeakZeroSIVapplications;
   assert(0 < Level && Level <= SrcLevels && "Level out of range");
   Level--;
   Result.Consistent = false;
-  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
+  const SCEV *Delta = SE->getPointerDiff(DstConst, SrcConst);
   NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta,
                         CurLoop);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
   if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) {
     if (Level < CommonLevels) {
       Result.DV[Level].Direction &= Dependence::DVEntry::LE;
       Result.DV[Level].PeelFirst = true;
       ++WeakZeroSIVsuccesses;
bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
                                    FullDependence &Result) const {
   LLVM_DEBUG(dbgs() << "\tExact RDIV test\n");
   LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
   LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
   LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
   LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
   ++ExactRDIVapplications;
   Result.Consistent = false;
-  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
+  const SCEV *Delta = SE->getPointerDiff(DstConst, SrcConst);
   LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
     return false;
 
   // find gcd
bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2,
   LLVM_DEBUG(dbgs() << ", type = " << *A1->getType() << "\n");
   LLVM_DEBUG(dbgs() << "\t    A2 = " << *A2 << "\n");
   LLVM_DEBUG(dbgs() << "\t    C1 = " << *C1 << "\n");
   LLVM_DEBUG(dbgs() << "\t    C2 = " << *C2 << "\n");
   const SCEV *N1 = collectUpperBound(Loop1, A1->getType());
   const SCEV *N2 = collectUpperBound(Loop2, A1->getType());
   LLVM_DEBUG(if (N1) dbgs() << "\t    N1 = " << *N1 << "\n");
   LLVM_DEBUG(if (N2) dbgs() << "\t    N2 = " << *N2 << "\n");
-  const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);
-  const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);
+  const SCEV *C2_C1 = SE->getPointerDiff(C2, C1);
+  const SCEV *C1_C2 = SE->getPointerDiff(C1, C2);
   LLVM_DEBUG(dbgs() << "\t    C2 - C1 = " << *C2_C1 << "\n");
   LLVM_DEBUG(dbgs() << "\t    C1 - C2 = " << *C1_C2 << "\n");
   if (SE->isKnownNonNegative(A1)) {
     if (SE->isKnownNonNegative(A2)) {
       // A1 >= 0 && A2 >= 0
       if (N1) {
         // make sure that c2 - c1 <= a1*N1
         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
if (!Constant)
       return false;
     APInt ConstCoeff = Constant->getAPInt();
     RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
     Coefficients = AddRec->getStart();
   }
   const SCEV *DstConst = Coefficients;
 
   APInt ExtraGCD = APInt::getNullValue(BitWidth);
-  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
+  const SCEV *Delta = SE->getPointerDiff(DstConst, SrcConst);
   LLVM_DEBUG(dbgs() << "    Delta = " << *Delta << "\n");
   const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta);
   if (const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
     // If Delta is a sum of products, we may be able to make further progress.
     for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) {
       const SCEV *Operand = Sum->getOperand(Op);
       if (isa<SCEVConstant>(Operand)) {
         assert(!Constant && "Surprised to find multiple constants");
bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,
   ++BanerjeeApplications;
   LLVM_DEBUG(dbgs() << "    Src = " << *Src << '\n');
   const SCEV *A0;
   CoefficientInfo *A = collectCoeffInfo(Src, true, A0);
   LLVM_DEBUG(dbgs() << "    Dst = " << *Dst << '\n');
   const SCEV *B0;
   CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);
   BoundInfo *Bound = new BoundInfo[MaxLevels + 1];
-  const SCEV *Delta = SE->getMinusSCEV(B0, A0);
+  const SCEV *Delta = SE->getPointerDiff(B0, A0);
   LLVM_DEBUG(dbgs() << "\tDelta = " << *Delta << '\n');
 
   // Compute bounds for all the * directions.
   LLVM_DEBUG(dbgs() << "\tBounds[*]\n");
   for (unsigned K = 1; K <= MaxLevels; ++K) {
     Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;
     Bound[K].Direction = Dependence::DVEntry::ALL;
     Bound[K].DirSet = Dependence::DVEntry::NONE;
const SCEVUnknown *DstBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
   assert(SrcBase && DstBase && SrcBase == DstBase &&
          "expected src and dst scev unknowns to be equal");
 
   const SCEV *ElementSize = SE->getElementSize(Src);
   if (ElementSize != SE->getElementSize(Dst))
     return false;
 
-  const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
-  const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
+  const SCEV *SrcSCEV = SE->getPointerDiff(SrcAccessFn, SrcBase);
+  const SCEV *DstSCEV = SE->getPointerDiff(DstAccessFn, DstBase);
 
   const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
   const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
   if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
     return false;
 
   // First step: collect parametric terms in both array references.
   SmallVector<const SCEV *, 4> Terms;

llvm/lib/Analysis/LoopAccessAnalysis.cpp

for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
         return true;
   return false;
 }
 
 /// Compare \p I and \p J and return the minimum.
 /// Return nullptr in case we couldn't find an answer.
 static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
                                    ScalarEvolution *SE) {
-  const SCEV *Diff = SE->getMinusSCEV(J, I);
+  const SCEV *Diff = SE->getPointerDiff(J, I);
   const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);
 
   if (!C)
     return nullptr;
   if (C->getValue()->isNegative())
     return J;
   return I;
 }
if (PtrA1 == PtrB1) {
 
     OffsetB -= OffsetA;
     Val = OffsetB.getSExtValue();
   } else {
     // Otherwise compute the distance with SCEV between the base pointers.
     const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
     const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
     const auto *Diff =
-        dyn_cast<SCEVConstant>(SE.getMinusSCEV(PtrSCEVB, PtrSCEVA));
+        dyn_cast<SCEVConstant>(SE.getPointerDiff(PtrSCEVB, PtrSCEVA));
     if (!Diff)
       return None;
     Val = Diff->getAPInt().getSExtValue();
   }
   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
   int Size = DL.getTypeStoreSize(Ty);
   int Dist = Val / Size;
 
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   if (StrideAPtr < 0) {
     std::swap(APtr, BPtr);
     std::swap(Src, Sink);
     std::swap(AIsWrite, BIsWrite);
     std::swap(AIdx, BIdx);
     std::swap(StrideAPtr, StrideBPtr);
   }
 
-  const SCEV *Dist = PSE.getSE()->getMinusSCEV(Sink, Src);
+  const SCEV *Dist = PSE.getSE()->getPointerDiff(Sink, Src);
 
   LLVM_DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
                     << "(Induction step: " << StrideAPtr << ")\n");
   LLVM_DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
                     << *InstMap[BIdx] << ": " << *Dist << "\n");
 
   // Need accesses with constant stride. We don't want to vectorize
   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in

llvm/lib/Analysis/LoopCacheAnalysis.cpp

if (Loop *L = LI.getLoopFor(BB)) {
     BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));
     if (BasePointer == nullptr) {
       LLVM_DEBUG(
           dbgs().indent(2)
           << "ERROR: failed to delinearize, can't identify base pointer\n");
       return false;
     }
 
-    AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
+    AccessFn = SE.getPointerDiff(AccessFn, BasePointer);
 
     LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
                                 << "', AccessFn: " << *AccessFn << "\n");
 
     SE.delinearize(AccessFn, Subscripts, Sizes,
                    SE.getElementSize(&StoreOrLoadInst));
 
     if (Subscripts.empty() || Sizes.empty() ||

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
     return true;
   }
 
   // Check if the offset from the base address becomes a constant.
   auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
   if (!Base)
     return false;
   auto *Offset =
-      dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
+      dyn_cast<SCEVConstant>(SE.getPointerDiff(ValueAtIteration, Base));
   if (!Offset)
     return false;
   SimplifiedAddress Address;
   Address.Base = Base->getValue();
   Address.Offset = Offset->getValue();
   SimplifiedAddresses[I] = Address;
   return false;
 }

llvm/lib/Analysis/ScalarEvolution.cpp

 }
 
 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty,
                                              unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
          "This is not a truncating conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
+  assert(!Op->getType()->isPointerTy() && "Can't truncate pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
   FoldingSetNodeID ID;
   ID.AddInteger(scTruncate);
   ID.AddPointer(Op);
   ID.AddPointer(Ty);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;

 }
 
 const SCEV *
 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
+  assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
   // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getZExt(SC->getValue(), Ty)));
 
   // zext(zext(x)) --> zext(x)

 }
 
 const SCEV *
 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
+  assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
   // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getSExt(SC->getValue(), Ty)));
 
   // sext(sext(x)) --> sext(x)
assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty add!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "SCEVAddExpr operand types don't match!");
+  unsigned NumPtrs = count_if(
+      Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); });
+  assert(NumPtrs <= 1 && "add has at most one pointer operand");
 #endif
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
       // to avoid multiplying by the same constant scale multiple times.
       std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
       for (const SCEV *NewOp : NewOps)
         MulOpLists[M.find(NewOp)->second].push_back(NewOp);
       // Re-generate the operands list.
       Ops.clear();
       if (AccumulatedConstant != 0)
         Ops.push_back(getConstant(AccumulatedConstant));
-      for (auto &MulOp : MulOpLists)
-        if (MulOp.first != 0)
+      for (auto &MulOp : MulOpLists) {
+        if (MulOp.first == 1) {
+          Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1));
+        } else if (MulOp.first != 0) {
           Ops.push_back(getMulExpr(
               getConstant(MulOp.first),
               getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1),
               SCEV::FlagAnyWrap, Depth + 1));
+        }
+      }
       if (Ops.empty())
         return getZero(Ty);
       if (Ops.size() == 1)
         return Ops[0];
       return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
     }
   }
 

 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags OrigFlags,
                                         unsigned Depth) {
   assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty mul!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
-  Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
+  Type *ETy = Ops[0]->getType();
+  assert(!ETy->isPointerTy());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
-    assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
+    assert(Ops[i]->getType() == ETy &&
            "SCEVMulExpr operand types don't match!");
 #endif
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
   const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW);
   return getMinusSCEV(LHS, Mult, SCEV::FlagNUW);
 }
 
 /// Get a canonical unsigned division expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
-  assert(getEffectiveSCEVType(LHS->getType()) ==
-         getEffectiveSCEVType(RHS->getType()) &&
+  assert(!LHS->getType()->isPointerTy() &&
+         "SCEVUDivExpr operand can't be pointer!");
+  assert(LHS->getType() == RHS->getType() &&
          "SCEVUDivExpr operand types don't match!");
 
   FoldingSetNodeID ID;
   ID.AddInteger(scUDivExpr);
   ID.AddPointer(LHS);
   ID.AddPointer(RHS);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))

 /// Get an add recurrence expression for the specified loop.  Simplify the
 /// expression as much as possible.
 const SCEV *
 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
                                const Loop *L, SCEV::NoWrapFlags Flags) {
   if (Operands.size() == 1) return Operands[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Operands[0]->getType());
-  for (unsigned i = 1, e = Operands.size(); i != e; ++i)
+  for (unsigned i = 1, e = Operands.size(); i != e; ++i) {
     assert(getEffectiveSCEVType(Operands[i]->getType()) == ETy &&
            "SCEVAddRecExpr operand types don't match!");
+    assert(!Operands[i]->getType()->isPointerTy() && "Step must be integer");
+  }
   for (unsigned i = 0, e = Operands.size(); i != e; ++i)
     assert(isLoopInvariant(Operands[i], L) &&
            "SCEVAddRecExpr operand is not loop-invariant!");
 #endif
 
   if (Operands.back()->isZero()) {
     Operands.pop_back();
     return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0}  -->  X

 }
 
 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind,
                                            SmallVectorImpl<const SCEV *> &Ops) {
   assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
-  for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+  for (unsigned i = 1, e = Ops.size(); i != e; ++i) {
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "Operand types don't match!");
+    assert(Ops[0]->getType()->isPointerTy() ==
+               Ops[i]->getType()->isPointerTy() &&
+           "min/max should be consistently pointerish");
+  }
 #endif
 
   bool IsSigned = Kind == scSMaxExpr || Kind == scSMinExpr;
   bool IsMax = Kind == scSMaxExpr || Kind == scUMaxExpr;
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
   // relative to a loop that is to be found in a recurrence in LHS and
   // not in RHS. Applying NSW to (-1)*M may then let the NSW have a
   // larger scope than intended.
   auto NegFlags = RHSIsNotMinSigned ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
 
   return getAddExpr(LHS, getNegativeSCEV(RHS, NegFlags), AddFlags, Depth);
 }
 
+const SCEV *ScalarEvolution::getPointerDiff(const SCEV *LHS, const SCEV *RHS) {
+  if (LHS->getType()->isPointerTy()) {
+    LHS = getLosslessPtrToIntExpr(LHS);
+    if (isa<SCEVCouldNotCompute>(LHS))
+      return LHS;
+  }
+  if (RHS->getType()->isPointerTy()) {
+    RHS = getLosslessPtrToIntExpr(RHS);
+    if (isa<SCEVCouldNotCompute>(RHS))
+      return RHS;
+  }
+  return getMinusSCEV(LHS, RHS);
+}
+
 const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
                                                      unsigned Depth) {
   Type *SrcTy = V->getType();
   assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
          "Cannot truncate or zero extend with non-integer arguments!");
   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
     return V;  // No conversion
   if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
if (FoundIndex != Add->getNumOperands()) {
           // about signed or unsigned overflow because pointers are
           // unsigned but we may have a negative index from the base
           // pointer. We can guarantee that no unsigned wrap occurs if the
           // indices form a positive value.
           if (GEP->isInBounds() && GEP->getOperand(0) == PN) {
             Flags = setFlags(Flags, SCEV::FlagNW);
 
             const SCEV *Ptr = getSCEV(GEP->getPointerOperand());
-            if (isKnownPositive(getMinusSCEV(getSCEV(GEP), Ptr)))
+            if (isKnownPositive(getPointerDiff(getSCEV(GEP), Ptr)))
               Flags = setFlags(Flags, SCEV::FlagNUW);
           }
 
           // We cannot transfer nuw and nsw flags from subtraction
           // operations -- sub nuw X, Y is not the same as add nuw X, -Y
           // for instance.
         }
 
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
 
         const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
         if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
       }
 
   switch (Pred) {
   case ICmpInst::ICMP_NE: {                     // while (X != Y)
     // Convert to: while (X-Y != 0)
-    if (LHS->getType()->isPointerTy()) {
-      LHS = getLosslessPtrToIntExpr(LHS);
-      if (isa<SCEVCouldNotCompute>(LHS))
-        return LHS;
-    }
-    if (RHS->getType()->isPointerTy()) {
-      RHS = getLosslessPtrToIntExpr(RHS);
-      if (isa<SCEVCouldNotCompute>(RHS))
-        return RHS;
-    }
-    ExitLimit EL = howFarToZero(getMinusSCEV(LHS, RHS), L, ControlsExit,
+    ExitLimit EL = howFarToZero(getPointerDiff(LHS, RHS), L, ControlsExit,
                                 AllowPredicates);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   case ICmpInst::ICMP_EQ: {                     // while (X == Y)
     // Convert to: while (X-Y == 0)
-    ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L);
+    ExitLimit EL = howFarToNonZero(getPointerDiff(LHS, RHS), L);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_ULT: {                    // while (X < Y)
     bool IsSigned = Pred == ICmpInst::ICMP_SLT;
     ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit,
                                     AllowPredicates);
bool ScalarEvolution::isKnownPredicateViaConstantRanges(
   // The check at the top of the function catches the case where the values are
   // known to be equal.
   if (Pred == CmpInst::ICMP_EQ)
     return false;
 
   if (Pred == CmpInst::ICMP_NE)
     return CheckRanges(getSignedRange(LHS), getSignedRange(RHS)) ||
            CheckRanges(getUnsignedRange(LHS), getUnsignedRange(RHS)) ||
-           isKnownNonZero(getMinusSCEV(LHS, RHS));
+           isKnownNonZero(getPointerDiff(LHS, RHS));
 
   if (CmpInst::isSigned(Pred))
     return CheckRanges(getSignedRange(LHS), getSignedRange(RHS));
 
   return CheckRanges(getUnsignedRange(LHS), getUnsignedRange(RHS));
 }
 
 bool ScalarEvolution::isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred,
if (!CmpInst::isSigned(FoundPred)) {
         const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType);
         const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType);
         if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, TruncFoundLHS,
                                        TruncFoundRHS, Context))
           return true;
       }
     }
 
+    if (LHS->getType()->isPointerTy())
+      return false;
     if (CmpInst::isSigned(Pred)) {
       LHS = getSignExtendExpr(LHS, FoundLHS->getType());
       RHS = getSignExtendExpr(RHS, FoundLHS->getType());
     } else {
       LHS = getZeroExtendExpr(LHS, FoundLHS->getType());
       RHS = getZeroExtendExpr(RHS, FoundLHS->getType());
     }
   } else if (getTypeSizeInBits(LHS->getType()) >
       getTypeSizeInBits(FoundLHS->getType())) {
+    if (FoundLHS->getType()->isPointerTy())
+      return false;
     if (CmpInst::isSigned(FoundPred)) {
       FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType());
       FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType());
     } else {
       FoundLHS = getZeroExtendExpr(FoundLHS, LHS->getType());
       FoundRHS = getZeroExtendExpr(FoundRHS, LHS->getType());
     }
   }
if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
     // Forms 1. and 2. require swapping the operands of one condition. Don't
     // do this if it would break canonical constant/addrec ordering.
     if (!isa<SCEVConstant>(RHS) && !isa<SCEVAddRecExpr>(LHS))
       return isImpliedCondOperands(FoundPred, RHS, LHS, FoundLHS, FoundRHS,
                                    Context);
     if (!isa<SCEVConstant>(FoundRHS) && !isa<SCEVAddRecExpr>(FoundLHS))
       return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS, Context);
 
+    // Don't try to getNotSCEV pointers.
+    if (LHS->getType()->isPointerTy() || FoundLHS->getType()->isPointerTy())
+      return false;
+
     // There's no clear preference between forms 3. and 4., try both.
     return isImpliedCondOperands(FoundPred, getNotSCEV(LHS), getNotSCEV(RHS),
                                  FoundLHS, FoundRHS, Context) ||
            isImpliedCondOperands(Pred, LHS, RHS, getNotSCEV(FoundLHS),
                                  getNotSCEV(FoundRHS), Context);
   }
 
   // Unsigned comparison is the same as signed comparison when both the operands

llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp

if (SE.getEffectiveSCEVType(AS->getType()) ==
     APInt ASizeInt(BitWidth, LocA.Size.hasValue()
                                  ? LocA.Size.getValue()
                                  : MemoryLocation::UnknownSize);
     APInt BSizeInt(BitWidth, LocB.Size.hasValue()
                                  ? LocB.Size.getValue()
                                  : MemoryLocation::UnknownSize);
 
     // Compute the difference between the two pointers.
-    const SCEV *BA = SE.getMinusSCEV(BS, AS);
+    const SCEV *BA = SE.getPointerDiff(BS, AS);
 
     // Test whether the difference is known to be great enough that memory of
     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
     // are non-zero, which is special-cased above.
     if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
         (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax()))
       return AliasResult::NoAlias;
 
     // Folding the subtraction while preserving range information can be tricky
     // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
     // and try again to see if things fold better that way.
 
     // Compute the difference between the two pointers.
-    const SCEV *AB = SE.getMinusSCEV(AS, BS);
+    const SCEV *AB = SE.getPointerDiff(AS, BS);
 
     // Test whether the difference is known to be great enough that memory of
     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
     // are non-zero, which is special-cased above.
     if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
         (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax()))
       return AliasResult::NoAlias;
   }

llvm/lib/Analysis/StackSafetyAnalysis.cpp

 
 ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {
   if (!SE.isSCEVable(Addr->getType()) || !SE.isSCEVable(Base->getType()))
     return UnknownRange;
 
   auto *PtrTy = IntegerType::getInt8PtrTy(SE.getContext());
   const SCEV *AddrExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Addr), PtrTy);
   const SCEV *BaseExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Base), PtrTy);
-  const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);
+  const SCEV *Diff = SE.getPointerDiff(AddrExp, BaseExp);
 
   ConstantRange Offset = SE.getSignedRange(Diff);
   if (isUnsafe(Offset))
     return UnknownRange;
   return Offset.sextOrTrunc(PointerSize);
 }
 
 ConstantRange

llvm/lib/Analysis/VectorUtils.cpp

for (auto AI = std::next(BI); AI != E; ++AI) {
 
       // Ignore A if the memory object of A and B don't belong to the same
       // address space
       if (getLoadStoreAddressSpace(A) != getLoadStoreAddressSpace(B))
         continue;
 
       // Calculate the distance from A to B.
       const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
-          PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
+          PSE.getSE()->getPointerDiff(DesA.Scev, DesB.Scev));
       if (!DistToB)
         continue;
       int64_t DistanceToB = DistToB->getAPInt().getSExtValue();
 
       // Check rule 3. Ignore A if its distance to B is not a multiple of the
       // size.
       if (DistanceToB % static_cast<int64_t>(DesB.Size))
         continue;

llvm/lib/Target/PowerPC/PPCLoopInstrFormPrep.cpp

 void PPCLoopInstrFormPrep::addOneCandidate(Instruction *MemI, const SCEV *LSCEV,
                                         SmallVector<Bucket, 16> &Buckets,
                                         unsigned MaxCandidateNum) {
   assert((MemI && GetPointerOperand(MemI)) &&
          "Candidate should be a memory instruction.");
   assert(LSCEV && "Invalid SCEV for Ptr value.");
   bool FoundBucket = false;
   for (auto &B : Buckets) {
-    const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);
+    const SCEV *Diff = SE->getPointerDiff(LSCEV, B.BaseSCEV);
     if (const auto *CDiff = dyn_cast<SCEVConstant>(Diff)) {
       B.Elements.push_back(BucketElement(CDiff, MemI));
       FoundBucket = true;
       break;
     }
   }
 
   if (!FoundBucket) {
if (CurrentPHINode->getNumIncomingValues() == 2) {
           // The existing PHI (CurrentPHINode) has the same start and increment
           // as the PHI that we wanted to create.
           if (Form == UpdateForm &&
               PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {
             ++PHINodeAlreadyExistsUpdate;
             return true;
           } 
           if (Form == DSForm || Form == DQForm) {
-            const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
-                SE->getMinusSCEV(PHIBasePtrSCEV->getStart(), BasePtrStartSCEV));
+            const SCEVConstant *Diff =
+                dyn_cast<SCEVConstant>(SE->getPointerDiff(
+                    PHIBasePtrSCEV->getStart(), BasePtrStartSCEV));
             if (Diff && !Diff->getAPInt().urem(Form)) {
               if (Form == DSForm)
                 ++PHINodeAlreadyExistsDS;
               else
                 ++PHINodeAlreadyExistsDQ;
               return true;
             }
           } 

llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

static Align getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV,
                              const SCEV *OffSCEV, Value *Ptr,
                              ScalarEvolution *SE) {
   const SCEV *PtrSCEV = SE->getSCEV(Ptr);
   // On a platform with 32-bit allocas, but 64-bit flat/global pointer sizes
   // (*cough* AMDGPU), the effective SCEV type of AASCEV and PtrSCEV
   // may disagree. Trunc/extend so they agree.
   PtrSCEV = SE->getTruncateOrZeroExtend(
       PtrSCEV, SE->getEffectiveSCEVType(AASCEV->getType()));
-  const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV);
+  const SCEV *DiffSCEV = SE->getPointerDiff(PtrSCEV, AASCEV);
 
   // On 32-bit platforms, DiffSCEV might now have type i32 -- we've always
   // sign-extended OffSCEV to i64, so make sure they agree again.
   DiffSCEV = SE->getNoopOrSignExtend(DiffSCEV, OffSCEV->getType());
 
   // What we really want to know is the overall offset to the aligned
   // address. This address is displaced by the provided offset.
   DiffSCEV = SE->getAddExpr(DiffSCEV, OffSCEV);

llvm/lib/Transforms/Scalar/LoopDataPrefetch.cpp

for (auto &I : *BB) {
         continue;
       NumStridedMemAccesses++;
 
       // We don't want to double prefetch individual cache lines. If this
       // access is known to be within one cache line of some other one that
       // has already been prefetched, then don't prefetch this one as well.
       bool DupPref = false;
       for (auto &Pref : Prefetches) {
-        const SCEV *PtrDiff = SE->getMinusSCEV(LSCEVAddRec, Pref.LSCEVAddRec);
+        const SCEV *PtrDiff = SE->getPointerDiff(LSCEVAddRec, Pref.LSCEVAddRec);
         if (const SCEVConstant *ConstPtrDiff =
             dyn_cast<SCEVConstant>(PtrDiff)) {
           int64_t PD = std::abs(ConstPtrDiff->getValue()->getSExtValue());
           if (PD < (int64_t) TTI->getCacheLineSize()) {
             Pref.addInstruction(MemI, DT, PD);
             DupPref = true;
             break;
           }

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

bool isDependenceDistanceOfOne(PredicatedScalarEvolution &PSE,
     unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
 
     auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
     auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(StorePtr));
 
     // We don't need to check non-wrapping here because forward/backward
     // dependence wouldn't be valid if these weren't monotonic accesses.
     auto *Dist = cast<SCEVConstant>(
-        PSE.getSE()->getMinusSCEV(StorePtrSCEV, LoadPtrSCEV));
+        PSE.getSE()->getPointerDiff(StorePtrSCEV, LoadPtrSCEV));
     const APInt &Val = Dist->getAPInt();
     return Val == TypeByteSize;
   }
 
   Value *getLoadPtr() const { return Load->getPointerOperand(); }
 
 #ifndef NDEBUG
   friend raw_ostream &operator<<(raw_ostream &OS,

llvm/lib/Transforms/Scalar/LoopRerollPass.cpp

bool LoopReroll::DAGRootTracker::validateRootSet(DAGRootSet &DRS) {
   // Now, For the loop iterations to be consecutive:
   //   D = d * N
   const auto *ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
   if (!ADR)
     return false;
 
   // Check that the first root is evenly spaced.
   unsigned N = DRS.Roots.size() + 1;
-  const SCEV *StepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), ADR);
+  const SCEV *StepSCEV = SE->getPointerDiff(SE->getSCEV(DRS.Roots[0]), ADR);
   const SCEV *ScaleSCEV = SE->getConstant(StepSCEV->getType(), N);
   if (ADR->getStepRecurrence(*SE) != SE->getMulExpr(StepSCEV, ScaleSCEV))
     return false;
 
   // Check that the remainling roots are evenly spaced.
   for (unsigned i = 1; i < N - 1; ++i) {
-    const SCEV *NewStepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[i]),
-                                               SE->getSCEV(DRS.Roots[i-1]));
+    const SCEV *NewStepSCEV = SE->getPointerDiff(SE->getSCEV(DRS.Roots[i]),
+                                                 SE->getSCEV(DRS.Roots[i - 1]));
     if (NewStepSCEV != StepSCEV)
       return false;
   }
 
   return true;
 }
 
 bool LoopReroll::DAGRootTracker::
void LoopReroll::DAGRootTracker::replace(const SCEV *BackedgeTakenCount) {
   // Compute the start and increment for each BaseInst before we start erasing
   // instructions.
   SmallVector<const SCEV *, 8> StartExprs;
   SmallVector<const SCEV *, 8> IncrExprs;
   for (auto &DRS : RootSets) {
     const SCEVAddRecExpr *IVSCEV =
         cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
     StartExprs.push_back(IVSCEV->getStart());
-    IncrExprs.push_back(SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), IVSCEV));
+    IncrExprs.push_back(SE->getPointerDiff(SE->getSCEV(DRS.Roots[0]), IVSCEV));
   }
 
   // Remove instructions associated with non-base iterations.
   for (BasicBlock::reverse_iterator J = Header->rbegin(), JE = Header->rend();
        J != JE;) {
     unsigned I = Uses[&*J].find_first();
     if (I > 0 && I < IL_All) {
       LLVM_DEBUG(dbgs() << "LRR: removing: " << *J << "\n");

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS,
 
   // Handle a few RHS special cases.
   const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS);
   if (RC) {
     const APInt &RA = RC->getAPInt();
     // Handle x /s -1 as x * -1, to give ScalarEvolution a chance to do
     // some folding.
     if (RA.isAllOnesValue())
-      return SE.getMulExpr(LHS, RC);
+      return SE.getPointerDiff(SE.getZero(LHS->getType()), LHS);
     // Handle x /s 1 as x.
     if (RA == 1)
       return LHS;
   }
 
   // Check for a division of a constant by a constant.
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) {
     if (!RC)
bool IVChain::isProfitableIncrement(const SCEV *OperExpr,
   // Aggressively form chains when -stress-ivchain.
   if (StressIVChain)
     return true;
 
   // Do not replace a constant offset from IV head with a nonconstant IV
   // increment.
   if (!isa<SCEVConstant>(IncExpr)) {
     const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Incs[0].IVOperand));
-    if (isa<SCEVConstant>(SE.getMinusSCEV(OperExpr, HeadExpr)))
+    if (isa<SCEVConstant>(SE.getPointerDiff(OperExpr, HeadExpr)))
       return false;
   }
 
   SmallPtrSet<const SCEV*, 8> Processed;
   return !isHighCostExpansion(IncExpr, Processed, SE);
 }
 
 /// Return true if the number of registers needed for the chain is estimated to
if (!isCompatibleIVType(PrevIV, NextIV))
       continue;
 
     // A phi node terminates a chain.
     if (isa<PHINode>(UserInst) && isa<PHINode>(Chain.tailUserInst()))
       continue;
 
     // The increment must be loop-invariant so it can be kept in a register.
     const SCEV *PrevExpr = SE.getSCEV(PrevIV);
-    const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr);
+    const SCEV *IncExpr = SE.getPointerDiff(OperExpr, PrevExpr);
     if (!SE.isLoopInvariant(IncExpr, L))
       continue;
 
     if (Chain.isProfitableIncrement(OperExpr, IncExpr, SE)) {
       LastIncExpr = IncExpr;
       break;
     }
   }
if (ICmpInst *CI = dyn_cast<ICmpInst>(UserInst)) {
 
         // x == y  -->  x - y == 0
         const SCEV *N = SE.getSCEV(NV);
         if (SE.isLoopInvariant(N, L) && isSafeToExpand(N, SE)) {
           // S is normalized, so normalize N before folding it into S
           // to keep the result normalized.
           N = normalizeForPostIncUse(N, TmpPostIncLoops, SE);
           Kind = LSRUse::ICmpZero;
-          S = SE.getMinusSCEV(N, S);
+          // FIXME: Replacing getMinusSCEV with getPointerDiff here causes
+          // codegen differences in regression tests. Need to figure out
+          // a different way to handle this.
+          S = SE.getPointerDiff(N, S);
         }
 
         // -1 and the negations of all interesting strides (except the negation
         // of -1) are now also interesting.
         for (size_t i = 0, e = Factors.size(); i != e; ++i)
           if (Factors[i] != -1)
             Factors.insert(-(uint64_t)Factors[i]);
         Factors.insert(-1);

 /// Generate reuse formulae from different IV types.
 void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) {
   // Don't bother truncating symbolic values.
   if (Base.BaseGV) return;
 
   // Determine the integer type for the base formula.
   Type *DstTy = Base.getType();
   if (!DstTy) return;
-  DstTy = SE.getEffectiveSCEVType(DstTy);
+  if (DstTy->isPointerTy())
+    return;
 
   for (Type *SrcTy : Types) {
     if (SrcTy != DstTy && TTI.isTruncateFree(SrcTy, DstTy)) {
       Formula F = Base;
 
       // Sometimes SCEV is able to prove zero during ext transform. It may
       // happen if SCEV did not do all possible transforms while creating the
       // initial node (maybe due to depth limitations), but it can do them while
if (LU.Kind == LSRUse::ICmpZero) {
       Ops.push_back(ScaledS);
     }
   }
 
   // Expand the GV portion.
   if (F.BaseGV) {
     // Flush the operand list to suppress SCEVExpander hoisting.
     if (!Ops.empty()) {
-      Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty);
+      Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), IntTy);
       Ops.clear();
       Ops.push_back(SE.getUnknown(FullV));
     }
     Ops.push_back(SE.getUnknown(F.BaseGV));
   }
 
   // Flush the operand list to suppress SCEVExpander hoisting of both folded and
   // unfolded offsets. LSR assumes they both live next to their uses.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

static bool canBeCheaplyTransformed(ScalarEvolution &SE,
 
   // Check whether truncation will help.
   if (Phi == Requested) {
     InvertStep = false;
     return true;
   }
 
   // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
-  if (SE.getAddExpr(Requested->getStart(),
-                    SE.getNegativeSCEV(Requested)) == Phi) {
+  if (SE.getPointerDiff(Requested->getStart(), Requested) == Phi) {
     InvertStep = true;
     return true;
   }
 
   return false;
 }
 
 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
   PHINode *CanonicalIV = nullptr;
   if (PHINode *PN = L->getCanonicalInductionVariable())
     if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
       CanonicalIV = PN;
 
   // Rewrite an AddRec in terms of the canonical induction variable, if
   // its type is more narrow.
   if (CanonicalIV &&
-      SE.getTypeSizeInBits(CanonicalIV->getType()) >
-      SE.getTypeSizeInBits(Ty)) {
+      SE.getTypeSizeInBits(CanonicalIV->getType()) > SE.getTypeSizeInBits(Ty) &&
+      !S->getType()->isPointerTy()) {
     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
                                        S->getNoWrapFlags(SCEV::FlagNW)));
     BasicBlock::iterator NewInsertPt =
         findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
     V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,

llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

bool Vectorizer::areConsecutivePointers(Value *PtrA, Value *PtrB,
   const SCEV *X = SE.getAddExpr(PtrSCEVA, C);
   if (X == PtrSCEVB)
     return true;
 
   // The above check will not catch the cases where one of the pointers is
   // factorized but the other one is not, such as (C + (S * (A + B))) vs
   // (AS + BS). Get the minus scev. That will allow re-combining the expresions
   // and getting the simplified difference.
-  const SCEV *Dist = SE.getMinusSCEV(PtrSCEVB, PtrSCEVA);
+  const SCEV *Dist = SE.getPointerDiff(PtrSCEVB, PtrSCEVA);
   if (C == Dist)
     return true;
 
   // Sometimes even this doesn't work, because SCEV can't always see through
   // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
   // things the hard way.
   return lookThroughComplexAddresses(PtrA, PtrB, BaseDelta, Depth);
 }

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

for (unsigned BI = 0, BE = Entry.second.size(); BI < BE; BI += MaxElts) {
       for (int I = 0, E = GEPList.size(); I < E && Candidates.size() > 1; ++I) {
         auto *GEPI = GEPList[I];
         if (!Candidates.count(GEPI))
           continue;
         auto *SCEVI = SE->getSCEV(GEPList[I]);
         for (int J = I + 1; J < E && Candidates.size() > 1; ++J) {
           auto *GEPJ = GEPList[J];
           auto *SCEVJ = SE->getSCEV(GEPList[J]);
-          if (isa<SCEVConstant>(SE->getMinusSCEV(SCEVI, SCEVJ))) {
+          if (isa<SCEVConstant>(SE->getPointerDiff(SCEVI, SCEVJ))) {
             Candidates.remove(GEPI);
             Candidates.remove(GEPJ);
           } else if (GEPI->idx_begin()->get() == GEPJ->idx_begin()->get()) {
             Candidates.remove(GEPJ);
           }
         }
       }
 

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
   Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
 
   ScalarEvolution SE = buildSE(*F);
 
   const SCEV *S0 = SE.getSCEV(V0);
   const SCEV *S1 = SE.getSCEV(V1);
   const SCEV *S2 = SE.getSCEV(V2);
 
-  const SCEV *P0 = SE.getAddExpr(S0, S0);
-  const SCEV *P1 = SE.getAddExpr(S1, S1);
-  const SCEV *P2 = SE.getAddExpr(S2, S2);
-
-  const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0);
-  const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1);
-  const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2);
+  const SCEV *P0 = SE.getAddExpr(S0, SE.getConstant(S0->getType(), 2));
+  const SCEV *P1 = SE.getAddExpr(S1, SE.getConstant(S0->getType(), 2));
+  const SCEV *P2 = SE.getAddExpr(S2, SE.getConstant(S0->getType(), 2));
+
+  auto *M0 = cast<SCEVAddExpr>(P0);
+  auto *M1 = cast<SCEVAddExpr>(P1);
+  auto *M2 = cast<SCEVAddExpr>(P2);
 
   EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),
             2u);
   EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),
             2u);
   EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),
             2u);
 
for (int i = 0; i < Iters; i++) {
     Accum = GetElementPtrInst::Create(I8Ty, Accum, PN, "gep", EndBB);
 
     PrevBB = CondBB;
     CondBB = NextBB;
   }
   ReturnInst::Create(Context, nullptr, EndBB);
   ScalarEvolution SE = buildSE(*F);
   const SCEV *S = SE.getSCEV(Accum);
+  S = SE.getLosslessPtrToIntExpr(S);
   Type *I128Ty = Type::getInt128Ty(Context);
   SE.getZeroExtendExpr(S, I128Ty);
 }
 
 // Make sure that SCEV invalidates exit limits after invalidating the values it
 // depends on when we forget a loop.
 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) {
   /*