Corrects a problem where we reply exclusively of GEPs to drive

analysis.  Better is to look for cases with useful GEPs and use them
when possible.  When a pair of useful GEPs is not available, use the
raw SCEVs directly. This approach supports better analysis of pointer
dereferencing.

In parallel, all the test cases are updated appropriately.
Cases where we have a store to *B++ can now be analyzed!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168474 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 108 insertions, 69 deletions

diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp
index 6291e99..684da98 100644
--- a/lib/Analysis/DependenceAnalysis.cpp
+++ b/lib/Analysis/DependenceAnalysis.cpp
@@ -2218,7 +2218,7 @@ bool DependenceAnalysis::gcdMIVtest(const SCEV *Src,
                                     FullDependence &Result) const {
   DEBUG(dbgs() << "starting gcd\n");
   ++GCDapplications;
-  unsigned BitWidth = Src->getType()->getIntegerBitWidth();
+  unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
   APInt RunningGCD = APInt::getNullValue(BitWidth);
 
   // Examine Src coefficients.
@@ -3194,7 +3194,8 @@ static void dumpSmallBitVector(SmallBitVector &BV) {
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
 //
-// Care is required to keep the code below up to date w.r.t. this routine.
+// Care is required to keep the routine below, getSplitIteration(),
+// up to date with respect to this routine.
 Dependence *DependenceAnalysis::depends(Instruction *Src,
                                         Instruction *Dst,
                                         bool PossiblyLoopIndependent) {
@@ -3203,9 +3204,11 @@ Dependence *DependenceAnalysis::depends(Instruction *Src,
     // if both instructions don't reference memory, there's no dependence
     return NULL;
 
-  if (!isLoadOrStore(Src) || !isLoadOrStore(Dst))
+  if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
     // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
+    DEBUG(dbgs() << "can only handle simple loads and stores\n");
     return new Dependence(Src, Dst);
+  }
 
   Value *SrcPtr = getPointerOperand(Src);
   Value *DstPtr = getPointerOperand(Dst);
@@ -3214,22 +3217,16 @@ Dependence *DependenceAnalysis::depends(Instruction *Src,
   case AliasAnalysis::MayAlias:
   case AliasAnalysis::PartialAlias:
     // cannot analyse objects if we don't understand their aliasing.
+    DEBUG(dbgs() << "can't analyze may or partial alias\n");
     return new Dependence(Src, Dst);
   case AliasAnalysis::NoAlias:
     // If the objects noalias, they are distinct, accesses are independent.
+    DEBUG(dbgs() << "no alias\n");
     return NULL;
   case AliasAnalysis::MustAlias:
     break; // The underlying objects alias; test accesses for dependence.
   }
 
-  GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr);
-  GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr);
-  if (!SrcGEP || !DstGEP)
-    return new Dependence(Src, Dst); // missing GEP, assume dependence
-
-  if (SrcGEP->getPointerOperandType() != DstGEP->getPointerOperandType())
-    return new Dependence(Src, Dst); // different types, assume dependence
-
   // establish loop nesting levels
   establishNestingLevels(Src, Dst);
   DEBUG(dbgs() << "    common nesting levels = " << CommonLevels << "\n");
@@ -3238,36 +3235,62 @@ Dependence *DependenceAnalysis::depends(Instruction *Src,
   FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
   ++TotalArrayPairs;
 
-  // classify subscript pairs
-  unsigned Pairs = SrcGEP->idx_end() - SrcGEP->idx_begin();
+  // 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()));
+  }
+  unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
   SmallVector<Subscript, 4> Pair(Pairs);
-  for (unsigned SI = 0; SI < Pairs; ++SI) {
-    Pair[SI].Loops.resize(MaxLevels + 1);
-    Pair[SI].GroupLoops.resize(MaxLevels + 1);
-    Pair[SI].Group.resize(Pairs);
-  }
-  Pairs = 0;
-  for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
-         SrcEnd = SrcGEP->idx_end(),
-         DstIdx = DstGEP->idx_begin(),
-         DstEnd = DstGEP->idx_end();
-       SrcIdx != SrcEnd && DstIdx != DstEnd;
-       ++SrcIdx, ++DstIdx, ++Pairs) {
-    Pair[Pairs].Src = SE->getSCEV(*SrcIdx);
-    Pair[Pairs].Dst = SE->getSCEV(*DstIdx);
-    removeMatchingExtensions(&Pair[Pairs]);
-    Pair[Pairs].Classification =
-      classifyPair(Pair[Pairs].Src, LI->getLoopFor(Src->getParent()),
-                   Pair[Pairs].Dst, LI->getLoopFor(Dst->getParent()),
-                   Pair[Pairs].Loops);
-    Pair[Pairs].GroupLoops = Pair[Pairs].Loops;
-    Pair[Pairs].Group.set(Pairs);
-    DEBUG(dbgs() << "    subscript " << Pairs << "\n");
-    DEBUG(dbgs() << "\tsrc = " << *Pair[Pairs].Src << "\n");
-    DEBUG(dbgs() << "\tdst = " << *Pair[Pairs].Dst << "\n");
-    DEBUG(dbgs() << "\tclass = " << Pair[Pairs].Classification << "\n");
+  if (UsefulGEP) {
+    DEBUG(dbgs() << "    using GEPs\n");
+    unsigned P = 0;
+    for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
+           SrcEnd = SrcGEP->idx_end(),
+           DstIdx = DstGEP->idx_begin();
+         SrcIdx != SrcEnd;
+         ++SrcIdx, ++DstIdx, ++P) {
+      Pair[P].Src = SE->getSCEV(*SrcIdx);
+      Pair[P].Dst = SE->getSCEV(*DstIdx);
+    }
+  }
+  else {
+    DEBUG(dbgs() << "    ignoring GEPs\n");
+    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;
+  }
+
+  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()),
+                   Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
+                   Pair[P].Loops);
+    Pair[P].GroupLoops = Pair[P].Loops;
+    Pair[P].Group.set(P);
+    DEBUG(dbgs() << "    subscript " << P << "\n");
+    DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");
+    DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");
+    DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");
     DEBUG(dbgs() << "\tloops = ");
-    DEBUG(dumpSmallBitVector(Pair[Pairs].Loops));
+    DEBUG(dumpSmallBitVector(Pair[P].Loops));
   }
 
   SmallBitVector Separable(Pairs);
@@ -3562,7 +3585,8 @@ Dependence *DependenceAnalysis::depends(Instruction *Src,
 // though simplified since we know that the dependence exists.
 // It's tedious, since we must go through all propagations, etc.
 //
-// Care is required to keep this code up to date w.r.t. the code above.
+// Care is required to keep this code up to date with respect to the routine
+// above, depends().
 //
 // Generally, the dependence analyzer will be used to build
 // a dependence graph for a function (basically a map from instructions
@@ -3611,44 +3635,59 @@ const  SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep,
   assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
   assert(isLoadOrStore(Src));
   assert(isLoadOrStore(Dst));
-  const Value *SrcPtr = getPointerOperand(Src);
-  const Value *DstPtr = getPointerOperand(Dst);
+  Value *SrcPtr = getPointerOperand(Src);
+  Value *DstPtr = getPointerOperand(Dst);
   assert(underlyingObjectsAlias(AA, DstPtr, SrcPtr) ==
          AliasAnalysis::MustAlias);
-  const GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr);
-  const GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr);
-  assert(SrcGEP);
-  assert(DstGEP);
-  assert(SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType());
 
   // establish loop nesting levels
   establishNestingLevels(Src, Dst);
 
   FullDependence Result(Src, Dst, false, CommonLevels);
 
-  // classify subscript pairs
-  unsigned Pairs = SrcGEP->idx_end() - SrcGEP->idx_begin();
+  // 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()));
+  }
+  unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
   SmallVector<Subscript, 4> Pair(Pairs);
-  for (unsigned SI = 0; SI < Pairs; ++SI) {
-    Pair[SI].Loops.resize(MaxLevels + 1);
-    Pair[SI].GroupLoops.resize(MaxLevels + 1);
-    Pair[SI].Group.resize(Pairs);
-  }
-  Pairs = 0;
-  for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
-         SrcEnd = SrcGEP->idx_end(),
-         DstIdx = DstGEP->idx_begin(),
-         DstEnd = DstGEP->idx_end();
-       SrcIdx != SrcEnd && DstIdx != DstEnd;
-       ++SrcIdx, ++DstIdx, ++Pairs) {
-    Pair[Pairs].Src = SE->getSCEV(*SrcIdx);
-    Pair[Pairs].Dst = SE->getSCEV(*DstIdx);
-    Pair[Pairs].Classification =
-      classifyPair(Pair[Pairs].Src, LI->getLoopFor(Src->getParent()),
-                   Pair[Pairs].Dst, LI->getLoopFor(Dst->getParent()),
-                   Pair[Pairs].Loops);
-    Pair[Pairs].GroupLoops = Pair[Pairs].Loops;
-    Pair[Pairs].Group.set(Pairs);
+  if (UsefulGEP) {
+    unsigned P = 0;
+    for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
+           SrcEnd = SrcGEP->idx_end(),
+           DstIdx = DstGEP->idx_begin();
+         SrcIdx != SrcEnd;
+         ++SrcIdx, ++DstIdx, ++P) {
+      Pair[P].Src = SE->getSCEV(*SrcIdx);
+      Pair[P].Dst = SE->getSCEV(*DstIdx);
+    }
+  }
+  else {
+    const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
+    const SCEV *DstSCEV = SE->getSCEV(DstPtr);
+    Pair[0].Src = SrcSCEV;
+    Pair[0].Dst = DstSCEV;
+  }
+
+  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()),
+                   Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
+                   Pair[P].Loops);
+    Pair[P].GroupLoops = Pair[P].Loops;
+    Pair[P].Group.set(P);
   }
 
   SmallBitVector Separable(Pairs);