[DependenceAnalysis] Guard analysis using getPointerBase()

[efriedma]

Summary

D104806 broke some uses of getMinusSCEV() in DependenceAnalysis: subtraction with different pointer bases returns a SCEVCouldNotCompute. Make sure we avoid cases involving such subtractions.

[reames]

LGTM

I think I number of these queries could handle inequal base objects, but given there's no test coverage for it, it doesn't appear to matter.

[bmahjour]

llvm/lib/Analysis/DependenceAnalysis.cpp

3556

We only get here if the two pointers MustAlias. If my understanding of MustAlias is correct (that it means precise and complete overlapping of memory), and if the two references are in the same loop, then comparing indexes seems reasonable. In that case, the effect of the following analysis should be as if src and dst SCEVs have their base pointers replaced with the same value. Not sure what's the best way to deal with such cases. Does it make sense to introduce a mode in getMinusSCEV where different base pointers can be permitted?

[efriedma]

llvm/lib/Analysis/DependenceAnalysis.cpp

3556

underlyingObjectsAlias(Src, Dst) == MustAlias is basically a slightly fancier version isIdentifiedObject(getUnderlyingObject(Src)) && isIdentifiedObject(getUnderlyingObject(Dst)) && getUnderlyingObject(Src) == getUnderlyingObject(Dst). The issue here is that getPointerBase() is less powerful than getUnderlyingObject().

It is possible to cast the operands of getMinusSCEV to integers using getPtrToIntExpr(); in that case, you won't get a SCEVCouldNotCompute. But then you end up with a SCEV containing something like ptrtoint(SrcSCEVPointerBase) - ptrtoint(DstSCEVPointerBase), which is basically impossible to analyze. So it seems simpler to just reject early.

[efriedma]

llvm/lib/Analysis/DependenceAnalysis.cpp

3556

Oh, also, there's been work to allow SCEV to look through LCSSA PHI nodes; that would allow DependenceAnalysis to analyze more cases. But that patch got reverted; not sure what the current status is.

[artemrad]

llvm/lib/Analysis/DependenceAnalysis.cpp

3556

This seems like a subset of cases we should be filtering out. Please also add checks for the access width being unaligned with the store/load size. In this case the base pointers are different but the accesses can still overlap. This case will not be caught by DependenceAnalysis.

define void @z0(i32* %A, i64 %n) nounwind uwtable ssp {
entry:
  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %n
  %arrayidx_cast = bitcast i32* %arrayidx to i64*
  store i64 0, i64* %arrayidx_cast, align 4

; CHECK: da analyze - confused!
; CHECK: da analyze - confused!
; CHECK: da analyze - confused!
; CHECK: da analyze - none
; CHECK: da analyze - confused!
; CHECK: da analyze - confused!

  %add1 = add i64 %n, 1
  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %add1
  %0 = load i32, i32* %arrayidx2, align 4
 
  ; Even if the load and store types are the same, if their
  ; alignments are smaller than the store size and they are
  ; accesses through something other than a straightforward
  ; gep, they can still overlap, as this access shows
  %arrayidx2_cast = bitcast i32* %arrayidx2 to i64*
  %1 = load i64, i64* %arrayidx2_cast, align 4
  ret void
}

[efriedma]

llvm/lib/Analysis/DependenceAnalysis.cpp

3556

Well, there are a few things we can do in that case:

1. Bail out if we don't have two naturally aligned accesses of the same size.
2. Perform multiple dependency checks, and merge the results. For example, if you have a size 4 access, and a size 8 access, you can treat the size 8 access as two size 4 accesses, and merge the results accordingly.
3. Teach the dependence checks to use ranges, instead of plain indexes.

I'm afraid (1) will hurt performance. And I don't really want to sign up to do (2) or (3).

[artemrad]

llvm/lib/Analysis/DependenceAnalysis.cpp

3556

Well currently we do not bail out in the case of (1), so it is worse than loosing performance, we are giving incorrect results.

As for (2) and (3) completely agree this is a project and I did not mean to imply that you should undertake it. Apologies, that was not my intention.

llvm/lib/Analysis/DependenceAnalysis.cpp

DependenceInfo::depends(Instruction *Src, Instruction *Dst,
   ++TotalArrayPairs;
 
   unsigned Pairs = 1;
   SmallVector<Subscript, 2> Pair(Pairs);
   const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
   const SCEV *DstSCEV = SE->getSCEV(DstPtr);
   LLVM_DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");
   LLVM_DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");
+  if (SE->getPointerBase(SrcSCEV) != SE->getPointerBase(DstSCEV)) {
+    // If two pointers have different bases, trying to analyze indexes won't
+    // work; we can't compare them to each other. This can happen, for example,
+    // if one is produced by an LCSSA PHI node.
+    //
+    // We check this upfront so we don't crash in cases where getMinusSCEV()
+    // returns a SCEVCouldNotCompute.
+    LLVM_DEBUG(dbgs() << "can't analyze SCEV with different pointer base\n");
+    return std::make_unique<Dependence>(Src, Dst);
+  }
   Pair[0].Src = SrcSCEV;
   Pair[0].Dst = DstSCEV;
 
   if (Delinearize) {
     if (tryDelinearize(Src, Dst, Pair)) {
       LLVM_DEBUG(dbgs() << "    delinearized\n");
       Pairs = Pair.size();
     }

llvm/test/Analysis/DependenceAnalysis/lcssa.ll

+; RUN: opt < %s -disable-output "-passes=print<da>"                            \
+; RUN: "-aa-pipeline=basic-aa,tbaa" 2>&1 | FileCheck %s
+; RUN: opt < %s -analyze -enable-new-pm=0 -basic-aa -tbaa -da | FileCheck %s
+
+; CHECK:      Src:  %v = load i32, i32* %arrayidx1, align 4 --> Dst:  store i32 %add, i32* %a.lcssa, align 4
+; CHECK-NEXT: da analyze - confused!
+
+define void @f(i32 *%a, i32 %n, i64 %n2) {
+entry:
+  br label %while.body
+
+while.body:
+  %n.addr = phi i32 [ %mul, %while.body ], [ %n, %entry ]
+  %inc.phi = phi i32 [ %inc, %while.body ], [ 0, %entry ]
+  %mul = mul i32 %n.addr, 3
+  %div = udiv i32 %mul, 2
+  %inc = add i32 %inc.phi, 1
+  %incdec.ptr = getelementptr inbounds i32, i32* %a, i32 %inc
+  %cmp.not = icmp eq i32 %div, 1
+  br i1 %cmp.not, label %while.end, label %while.body
+
+while.end:
+  %a.lcssa = phi i32* [ %incdec.ptr, %while.body ]
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 1, %while.end ], [ %indvars.iv.next, %for.body ]
+  %arrayidx1 = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %v = load i32, i32* %arrayidx1, align 4
+  %add = add nsw i32 %v, 1
+  store i32 %add, i32* %a.lcssa, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.not = icmp eq i64 %indvars.iv.next, %n2
+  br i1 %exitcond.not, label %ret, label %for.body
+
+ret:
+  ret void
+}