Fix crash in Dependence Analysis module

[karthikthecool]

Summary

Hi All,
This crash in Dependency analysis is because we assume here that in case of UsefulGEP both source and destination have the same number of operands which may not be true. This incorrect assumption results in crash while populating Pairs. Fix the same.
Consider the case -

struct s{
  int A[10][10];
  int C[10][10][10]; 
} S;
void dep_constraint_crash_test(int k,int N)  {
   for( int i=0;i<N;i++)
     for( int j=0;j<N;j++)
       S.A[0][0] = S.C[0][0][k];
}

In this case the GEP corresponding to store has 2 operands and that corresponding to load has 3 operands. This was resulting in a crash during dependency analysis.
Please let me know your inputs on the patch.

Thanks and Regards
Karthik Bhat

[hfinkel]

I don't object to this fix, as such, but is the logic you're fixing even right? Your test case has:

struct s {
  int A[10][10];
  int C[10][10][10]; 
} S;

void dep_constraint_crash_test(int k,int N) {
  for( int i=0;i<N;i++)
    for( int j=0;j<N;j++)
      S.A[0][0] = S.C[0][0][k];
}

but what if it has:

struct s {
  int C[10][10][10]; 
  int A[10][10];
} S;

void dep_constraint_crash_test(int k,int N) {
  for( int i=0;i<N;i++)
    for( int j=0;j<N;j++)
      S.A[0][0] = S.C[0][0][k];
}

what does it say about the dependence of the two? If k > 10, then it could overlap with S.A[0][0].

[karthikthecool]

Hi Hal,
The logic added currently prevents marking the GEP as UsefulGEP and hence different GEP index are not compared independently.
Dependency analysis currently reports an anti dependency between the 2 memory access as -

da analyze - consistent input [S S]!
da analyze - anti [S S|<]!
da analyze - consistent output [S S]!

as it is not considered as UsefulGEP as it doesn't know if k can overflow or not.

I understand from http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130701/179665.html that it is not valid to independently analyze 2 different indices of a GEP as the higher index may overflow into lower index but if it is provable at compile time that this never happens then we can still use this part of the code as is.
So we might want to add additional checks that concludes if a GEP is UsefulGEP and hence can be analyzed independently?
I still need to go through this module in more detail but i feel that part of code inside UsefulGEP will be valid if we can conculde that we can independetly analyze different indices of a GetElementPointer.
Please if you could let me know if i'm thinking in the right direction. Will go through this module in more detail.
Thanks and Regards
Karthik Bhat

[hfinkel]

In D8162#137454, @karthikthecool wrote:

Hi Hal,
The logic added currently prevents marking the GEP as UsefulGEP and hence different GEP index are not compared independently.

Okay, LGTM.

Dependency analysis currently reports an anti dependency between the 2 memory access as -

da analyze - consistent input [S S]!
da analyze - anti [S S|<]!
da analyze - consistent output [S S]!

as it is not considered as UsefulGEP as it doesn't know if k can overflow or not.

I understand from http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130701/179665.html that it is not valid to independently analyze 2 different indices of a GEP as the higher index may overflow into lower index but if it is provable at compile time that this never happens then we can still use this part of the code as is.
So we might want to add additional checks that concludes if a GEP is UsefulGEP and hence can be analyzed independently?

Yes, we might. I'm not sure whether this is useful, or whether we should just rely on / extend the delinearization analysis instead. Using the GEPs as a 'good guess' that require validation is likely reasonable.

I still need to go through this module in more detail but i feel that part of code inside UsefulGEP will be valid if we can conculde that we can independetly analyze different indices of a GetElementPointer.
Please if you could let me know if i'm thinking in the right direction. Will go through this module in more detail.

Sounds good. Please do (but this fix is fine for now).

Thanks and Regards
Karthik Bhat

[karthikthecool]

Thanks Hal. Comitted as r231784.
Will try to understand delinearization analysis and get back shortly.
Can you also have a look at D8059 when you find time.
Thanks and Regards
Karthik Bhat

lib/Analysis/DependenceAnalysis.cpp

DependenceAnalysis::depends(Instruction *Src, Instruction *Dst,
   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()));
+    UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
+                isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) &&
+                (SrcGEP->getNumOperands() == DstGEP->getNumOperands());
   }
   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(),
const  SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep,
   // 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());
-    UsefulGEP =
-      isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
-      isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent()));
+    UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
+                isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) &&
+                (SrcGEP->getNumOperands() == DstGEP->getNumOperands());
   }
   unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
   SmallVector<Subscript, 4> Pair(Pairs);
   if (UsefulGEP) {
     unsigned P = 0;
     for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
            SrcEnd = SrcGEP->idx_end(),
            DstIdx = DstGEP->idx_begin();

test/Analysis/DependenceAnalysis/UsefulGEP.ll

+; RUN: opt < %s -analyze -basicaa -da
+;; Check this doesn't crash.
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;; struct s {
+;;   int A[10][10];
+;;   int C[10][10][10]; 
+;; } S;
+
+;; void dep_constraint_crash_test(int k,int N) {
+;;   for( int i=0;i<N;i++)
+;;     for( int j=0;j<N;j++)
+;;       S.A[0][0] = S.C[0][0][k];
+;; }
+
+
+%struct.s = type { [10 x [10 x i32]], [10 x [10 x [10 x i32]]] }
+
+@S = common global %struct.s zeroinitializer
+
+define void @dep_constraint_crash_test(i32 %k, i32 %N) {
+entry:
+  %cmp12 = icmp sgt i32 %N, 0
+  br i1 %cmp12, label %for.cond1.preheader.lr.ph, label %for.end6
+
+for.cond1.preheader.lr.ph:                        
+  %idxprom = sext i32 %k to i64
+  %arrayidx = getelementptr inbounds %struct.s, %struct.s* @S, i64 0, i32 1, i64 0, i64 0, i64 %idxprom
+  br label %for.body3.preheader
+
+for.body3.preheader:                              
+  %i.013 = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc5, %for.inc4 ]
+  br label %for.body3
+
+for.body3:                                        
+  %j.011 = phi i32 [ %inc, %for.body3 ], [ 0, %for.body3.preheader ]
+  %0 = load i32, i32* %arrayidx
+  store i32 %0, i32* getelementptr inbounds (%struct.s* @S, i64 0, i32 0, i64 0, i64 0)
+  %inc = add nuw nsw i32 %j.011, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %for.inc4, label %for.body3
+
+for.inc4:                                         
+  %inc5 = add nuw nsw i32 %i.013, 1
+  %exitcond14 = icmp eq i32 %inc5, %N
+  br i1 %exitcond14, label %for.end6, label %for.body3.preheader
+
+for.end6:                                         
+  ret void
+}