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.
// 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) {
// 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);
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");
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);
// 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
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);
projects / oota-llvm.git / blobdiff