[SCEV] Avoid pointer subtraction of non-integral pointers [WIP]

[reames]

Summary

This is a WIP, mostly posted for discussion and performance evaluation.

Over in D104322, and D103660, and a couple other related reviews, there's a desire to avoid pointer math in SCEV. For normal (integral) pointers, we can do this by pushing ptrtoint down expression trees, but we don't have that option for non-integral ones. This patch tries to minimally cripple SCEVs ability to reason about non-integrals, while still allowing forward progress on that idea.

The main impact of this is, from what I can tell, hurting the vectorizers ability to version loops and SCEV-AA. Note that handling ptr - int is important, without that we'd also loose LSR and that's a pretty much fatal flaw.

I'd like to see a performance validation of this patch. @mkazantsev, @skatkov - Can either of you help with that?

[lebedev.ri]

This is only going to work if getMinusSCEV() is called directly though.

[efriedma]

For normal pointers, I expect that what we want for pointer subtraction (cases where the RHS is a pointer) is to just ptrtoint the operands. It's easy to implement, and the result is intuitive.

Not sure that operation should be part of getMinusSCEV(), or if we should add a separate getPointerDiffSCEV(). Maybe worth separating if getPointerDiffSCEV() is going to be fallible (so getMinusSCEV stays infallible).

If we wanted to optimize getPointerDiffSCEV() for weird pointers, we could try to transform pointer subtraction to integral subtraction if the operands have the same pointer base. Not sure how important this is in practice.

[reames]

FYI, agree with all the stylistic comments from Eli. Waiting on perf numbers to see if this is worth cleaning up, or if we need a radically different approach.

[apilipenko]

FYI, I tried to take this patch for performance verification, but it crashed in smoke testing. I haven't yet looked why.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
 
   const SCEV *Dist = PSE.getSE()->getMinusSCEV(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");
 
+  if (isa<SCEVCouldNotCompute>(Dist))
+    return Dependence::Unknown;
+
   // Need accesses with constant stride. We don't want to vectorize
   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
   // the address space.
   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
     LLVM_DEBUG(dbgs() << "Pointer access with non-constant stride\n");
     return Dependence::Unknown;
   }
 

llvm/lib/Analysis/ScalarEvolution.cpp

 
 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
                                           SCEV::NoWrapFlags Flags,
                                           unsigned Depth) {
   // Fast path: X - X --> 0.
   if (LHS == RHS)
     return getZero(LHS->getType());
 
+  // Pointer subtraction when LHS and RHS are based on different objects is
+  // not well defined.  For integral pointers, we fall back to inttoptrs
+  // but we don't have that option for non-integral pointers. Note that
+  // subtracting an offset from a non-integral pointer is fine.
+  // TODO: If we had an actual pointer subtraction primitive which didn't
+  // require ptrtoint, we could get better results for non-integral pointers
+  // here.
+  if (getDataLayout().isNonIntegralPointerType(RHS->getType()))
+    return getCouldNotCompute();
+
   // We represent LHS - RHS as LHS + (-1)*RHS. This transformation
   // makes it so that we cannot make much use of NUW.
   auto AddFlags = SCEV::FlagAnyWrap;
   const bool RHSIsNotMinSigned =
       !getSignedRangeMin(RHS).isMinSignedValue();
   if (maskFlags(Flags, SCEV::FlagNSW) == SCEV::FlagNSW) {
     // Let M be the minimum representable signed value. Then (-1)*RHS
     // signed-wraps if and only if RHS is M. That can happen even for

llvm/test/Analysis/LoopAccessAnalysis/wrapping-pointer-ni.ll

 ; RUN: opt -loop-versioning -S < %s | FileCheck %s -check-prefix=LV
 
 ; NB: addrspaces 10-13 are non-integral
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:10:11:12:13"
 
 ; This matches the test case from PR38290
 ; Check that we expand the SCEV predicate check using GEP, rather
 ; than ptrtoint.
 
 %jl_value_t = type opaque
 %jl_array_t = type { i8 addrspace(13)*, i64, i16, i16, i32 }
 
 declare i64 @julia_steprange_last_4949()
 
+@G = external global i32
+
 define void @"japi1_align!_9477"(%jl_value_t addrspace(10)** %arg) {
 ; LV-LAVEL: L26.lver.check
-; LV: [[OFMul:%[^ ]*]]  = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[Step:%[^ ]*]])
-; LV-NEXT: [[OFMulResult:%[^ ]*]] = extractvalue { i64, i1 } [[OFMul]], 0
-; LV-NEXT: [[OFMulOverflow:%[^ ]*]] = extractvalue { i64, i1 } [[OFMul]], 1
-; LV-NEXT: [[PosGEP:%[^ ]*]] = getelementptr i32, i32 addrspace(13)* [[Base:%[^ ]*]], i64 [[Step]]
-; LV-NEXT: [[NegGEP:%[^ ]*]] = getelementptr i32, i32 addrspace(13)* [[Base]], i64 [[NegStep:%[^ ]*]]
-; LV-NEXT: icmp ugt i32 addrspace(13)* [[NegGEP]], [[Base]]
-; LV-NEXT: icmp ult i32 addrspace(13)* [[PosGEP]], [[Base]]
 ; LV-NOT: inttoptr
 ; LV-NOT: ptrtoint
 top:
   %tmp = load %jl_value_t addrspace(10)*, %jl_value_t addrspace(10)** %arg, align 8
-  %tmp1 = load i32, i32* inttoptr (i64 12 to i32*), align 4
+  %tmp1 = load i32, i32* @G, align 4
   %tmp2 = sub i32 0, %tmp1
   %tmp3 = call i64 @julia_steprange_last_4949()
   %tmp4 = addrspacecast %jl_value_t addrspace(10)* %tmp to %jl_value_t addrspace(11)*
   %tmp5 = bitcast %jl_value_t addrspace(11)* %tmp4 to %jl_value_t addrspace(10)* addrspace(11)*
   %tmp6 = load %jl_value_t addrspace(10)*, %jl_value_t addrspace(10)* addrspace(11)* %tmp5, align 8
   %tmp7 = addrspacecast %jl_value_t addrspace(10)* %tmp6 to %jl_value_t addrspace(11)*
   %tmp8 = bitcast %jl_value_t addrspace(11)* %tmp7 to i32 addrspace(13)* addrspace(11)*
   %tmp9 = load i32 addrspace(13)*, i32 addrspace(13)* addrspace(11)* %tmp8, align 8