[DependenceAnalysis] Make sure base objects are the same when comparing GEPs

[bcahoon]

Summary

The dependence analysis was returning incorrect information when using the GEPs to compute the dependence. The analysis uses the GEP indices to perform the check under certain conditions. It incorrectly does this if the base objects are aliases, but are actually pointing to different locations in an array. Because the SCEVs for the GEPs indices were the same, DA returns a distance of 0.

This patch adds another check for the base objects. If the SCEVs for the base pointers are compared, using getMinusSCEV() and the value is not 0, the analysis should fall back on the path that uses the whole SCEV for the dependence check. Not just the GEP indices.

Fixes bug 33567.

[philip.pfaffe]

The idea seems solid. Can you merge the testcases into one? If the testcase is named BasePtrBug, please also add the bug id, either in the name directly or in a comment inside.

lib/Analysis/DependenceAnalysis.cpp

3340

Why did you choose to look at the difference instead of checking isKnownPredicate? Is there an advantage in looking at the difference? isKnownPredicate would communicate to the reader better the intention of this check.

test/Analysis/DependenceAnalysis/BasePtrBug1.ll

4 ↗

(On Diff #104221)

"generates" and "different"

[bcahoon]

Hi Philip - thanks for the review. I made the changes you suggested.

This version uses isKnownPredicate to compare the base pointers. I've combined the two test cases in to file.

[philip.pfaffe]

One formatting nit aside, LGMT.

test/Analysis/DependenceAnalysis/BasePtrBug.ll

8

Indentation

lib/Analysis/DependenceAnalysis.cpp

DependenceInfo::depends(Instruction *Src, Instruction *Dst,
   // See if there are GEPs we can use.
   bool UsefulGEP = false;
   GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr);
   GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr);
   if (SrcGEP && DstGEP &&
       SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) {
     const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand());
     const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand());
     DEBUG(dbgs() << "    SrcPtrSCEV = " << *SrcPtrSCEV << "\n");
     DEBUG(dbgs() << "    DstPtrSCEV = " << *DstPtrSCEV << "\n");
 
     UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
                 isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) &&
-                (SrcGEP->getNumOperands() == DstGEP->getNumOperands());
+                (SrcGEP->getNumOperands() == DstGEP->getNumOperands()) &&
+                isKnownPredicate(CmpInst::ICMP_EQ, SrcPtrSCEV, DstPtrSCEV);
   }
   unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
   SmallVector<Subscript, 4> Pair(Pairs);
   if (UsefulGEP) {
     DEBUG(dbgs() << "    using GEPs\n");
     unsigned P = 0;
     for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
            SrcEnd = SrcGEP->idx_end(),

test/Analysis/DependenceAnalysis/BasePtrBug.ll

+; RUN: opt < %s -analyze -basicaa -da  | FileCheck %s
+
+; Test that the dependence analysis generates the correct results when using
+; an aliased object that points to a different element in the same array.
+; PR33567 - https://bugs.llvm.org/show_bug.cgi?id=33567
+
+; void test1(int *A, int *B, int N) {
+;   int *top = A;
+;  int *bot = A + N/2;
+;   for (int i = 0; i < N; i++)
+;     B[i] = top[i] + bot[i];
+; }
+
+; CHECK-LABEL: test1
+; CHECK: da analyze - input [*|<]!
+
+define void @test1(i32* nocapture %A, i32* nocapture %B, i32 %N) #0 {
+entry:
+  %cmp9 = icmp sgt i32 %N, 0
+  br i1 %cmp9, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:
+  %div = sdiv i32 %N, 2
+  %bot.gep = getelementptr i32, i32* %A, i32 %div
+  br label %for.body
+
+for.body:
+  %i = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %gep.0 = getelementptr i32, i32* %A, i32 %i
+  %gep.1 = getelementptr i32, i32* %bot.gep, i32 %i
+  %gep.B = getelementptr i32, i32* %B, i32 %i
+  %0 = load i32, i32* %gep.0, align 4
+  %1 = load i32, i32* %gep.1, align 4
+  %add = add nsw i32 %1, %0
+  store i32 %add, i32* %gep.B, align 4
+  %inc = add nsw i32 %i, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
+
+
+; void test2(int *A, unsigned n) {
+;  int *B = A + 1;
+;  for (unsigned i = 0; i < n; ++i) {
+;    A[i] = B[i];
+;  }
+; }
+
+; CHECK-LABEL: test2
+; CHECK: da analyze - consistent anti [1]!
+
+define void @test2(i32*, i32) #3 {
+  %3 = getelementptr inbounds i32, i32* %0, i64 1
+  br label %4
+
+; <label>:4:
+  %.0 = phi i32 [ 0, %2 ], [ %14, %13 ]
+  %5 = sub i32 %1, 1
+  %6 = icmp ult i32 %.0, %5
+  br i1 %6, label %7, label %15
+
+; <label>:7:
+  %8 = zext i32 %.0 to i64
+  %9 = getelementptr inbounds i32, i32* %3, i64 %8
+  %10 = load i32, i32* %9, align 4
+  %11 = zext i32 %.0 to i64
+  %12 = getelementptr inbounds i32, i32* %0, i64 %11
+  store i32 %10, i32* %12, align 4
+  br label %13
+
+; <label>:13:
+  %14 = add i32 %.0, 1
+  br label %4
+
+; <label>:15:
+  ret void
+}