1 files changed, 108 insertions, 69 deletions

diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 6291e995847..684da98ce25 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/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);