Fix how DependenceAnalysis calls de-linearization

[vaivaswatha]

Summary

DependenceAnalysis currently does not call de-linearization correctly. Fix it based on how de-linearization is called in Delinearization.cpp.

[vaivaswatha]

Added changes in DependenceAnalysis.h

[jingyue]

I don't have enough expertise on DependenceAnalysis unfortunately. You'd have to wait for others to chime it.

[hfinkel]

lib/Analysis/DependenceAnalysis.cpp

3247–3262

Can these be const Instruction*?

3255

The code in Delinearization.cpp does this:

// Delinearize the memory access as analyzed in all the surrounding loops.
// Do not analyze memory accesses outside loops.
for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
  const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);

So it walks up the chain of loops instead of just always using the inner loop. Should something similar be done here?

3429

Am I correct that an alternative way to fix this problem is to call getSCEVAtScope on the SCEVs being passed here?

[vaivaswatha]

lib/Analysis/DependenceAnalysis.cpp

3247–3262

Ideally, yes. However, ScalarEvolution::getElementSize() below does not take a const Instruction as its argument.

3255

From what I understand, It doesn't make much sense to do this here since all we need is to see the value's evolution in the innermost loop its defined in.

3429

Yes. Note that getSCEVAtScope needs to be called on "Src" and not "Pair[0].Src".
Also, I've removed the check "Pairs == 1" because its too strict. Even when the indices are linearized, its possible that the first index is 0 and the second one actually contains the linearized index (this is quite a common case) when indexing arrays (rather than pointers).

[vaivaswatha]

The assert on Src element size and Dst element size was incorrect. Fixing that.

[hfinkel]

LGTM.

[vaivaswatha]

@hfinkel Thank you very much for the review. I don't have permission to commit to the repo. Can you please commit this on my behalf?

[hfinkel]

r245408, thanks!

include/llvm/Analysis/DependenceAnalysis.h

const SCEV *addToCoefficient(const SCEV *Expr,
                                  const Loop *TargetLoop,
                                  const SCEV *Value)  const;
 
     /// updateDirection - Update direction vector entry
     /// based on the current constraint.
     void updateDirection(Dependence::DVEntry &Level,
                          const Constraint &CurConstraint) const;
 
-    bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV,
-                        SmallVectorImpl<Subscript> &Pair,
-                        const SCEV *ElementSize);
+    bool tryDelinearize(Instruction *Src, Instruction *Dst,
+                        SmallVectorImpl<Subscript> &Pair);
 
   public:
     static char ID; // Class identification, replacement for typeinfo
     DependenceAnalysis() : FunctionPass(ID) {
       initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;

lib/Analysis/DependenceAnalysis.cpp

void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level,
   else
     llvm_unreachable("constraint has unexpected kind");
 }
 
 /// Check if we can delinearize the subscripts. If the SCEVs representing the
 /// source and destination array references are recurrences on a nested loop,
 /// this function flattens the nested recurrences into separate recurrences
 /// for each loop level.
-bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV,
-                                        const SCEV *DstSCEV,
-                                        SmallVectorImpl<Subscript> &Pair,
-                                        const SCEV *ElementSize) {
+bool DependenceAnalysis::tryDelinearize(Instruction *Src,
+                                        Instruction *Dst,
+                                        SmallVectorImpl<Subscript> &Pair)
+{
+  Value *SrcPtr = getPointerOperand(Src);
+  Value *DstPtr = getPointerOperand(Dst);
+
+  Loop *SrcLoop = LI->getLoopFor(Src->getParent());
+  Loop *DstLoop = LI->getLoopFor(Dst->getParent());
+
+  // Below code mimics the code in Delinearization.cpp
+  const SCEV *SrcAccessFn =
+    SE->getSCEVAtScope(SrcPtr, SrcLoop);
+  const SCEV *DstAccessFn =
+    SE->getSCEVAtScope(DstPtr, DstLoop);
+
   const SCEVUnknown *SrcBase =
-      dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcSCEV));
+      dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
   const SCEVUnknown *DstBase =
-      dyn_cast<SCEVUnknown>(SE->getPointerBase(DstSCEV));
+      dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
 
   if (!SrcBase || !DstBase || SrcBase != DstBase)
     return false;
 
-  SrcSCEV = SE->getMinusSCEV(SrcSCEV, SrcBase);
-  DstSCEV = SE->getMinusSCEV(DstSCEV, DstBase);
+  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 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;
for (int VI = BV.find_first(); VI >= 0; VI = BV.find_next(VI)) {
     dbgs() << VI;
     if (BV.find_next(VI) >= 0)
       dbgs() << ' ';
   }
   dbgs() << "}\n";
 }
 #endif
 
-
 // depends -
 // Returns NULL if there is no dependence.
 // Otherwise, return a Dependence with as many details as possible.
 // Corresponds to Section 3.1 in the paper
 //
 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
else {
     const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
     const SCEV *DstSCEV = SE->getSCEV(DstPtr);
     DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");
     DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");
     Pair[0].Src = SrcSCEV;
     Pair[0].Dst = DstSCEV;
   }
 
-  if (Delinearize && Pairs == 1 && CommonLevels > 1 &&
-      tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) {
+  if (Delinearize && CommonLevels > 1) {
+    if (tryDelinearize(Src, Dst, Pair)) {
       DEBUG(dbgs() << "    delinerized GEP\n");
       Pairs = Pair.size();
     }
+  }
 
   for (unsigned P = 0; P < Pairs; ++P) {
     Pair[P].Loops.resize(MaxLevels + 1);
     Pair[P].GroupLoops.resize(MaxLevels + 1);
     Pair[P].Group.resize(Pairs);
     removeMatchingExtensions(&Pair[P]);
     Pair[P].Classification =
       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
const  SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep,
   }
   else {
     const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
     const SCEV *DstSCEV = SE->getSCEV(DstPtr);
     Pair[0].Src = SrcSCEV;
     Pair[0].Dst = DstSCEV;
   }
 
-  if (Delinearize && Pairs == 1 && CommonLevels > 1 &&
-      tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) {
+  if (Delinearize && CommonLevels > 1) {
+    if (tryDelinearize(Src, Dst, Pair)) {
       DEBUG(dbgs() << "    delinerized GEP\n");
       Pairs = Pair.size();
     }
+  }
 
   for (unsigned P = 0; P < Pairs; ++P) {
     Pair[P].Loops.resize(MaxLevels + 1);
     Pair[P].GroupLoops.resize(MaxLevels + 1);
     Pair[P].Group.resize(Pairs);
     removeMatchingExtensions(&Pair[P]);
     Pair[P].Classification =
       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),

test/Analysis/DependenceAnalysis/GCD.ll

 ; CHECK: da analyze - output [* *]!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - input [* *]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 ; DELIN: 'Dependence Analysis' for function 'gcd4'
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc17
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc17 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc18, %for.inc17 ]
   br label %for.body3
 

 ; CHECK: da analyze - output [* *]!
 ; CHECK: da analyze - flow [<> *]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - input [* *]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
 ; DELIN: 'Dependence Analysis' for function 'gcd5'
-; DELIN: da analyze - output [* *]!
-; DELIN: da analyze - flow [<> *]!
+; DELIN: da analyze - none!
+; DELIN: da analyze - flow [> *]!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 
 for.cond1.preheader:                              ; preds = %entry, %for.inc17
   %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc17 ]
   %i.03 = phi i64 [ 0, %entry ], [ %inc18, %for.inc17 ]
   br label %for.body3
 

 ; CHECK: da analyze - output [* *]!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - input [* *]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - output [* *]!
 
 ; DELIN: 'Dependence Analysis' for function 'gcd6'
-; DELIN: da analyze - output [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
-; DELIN: da analyze - input [* *]!
+; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - output [* *]!
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc10
   %i.06 = phi i64 [ %inc11, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ]