From 3ad394931dbef4b5d95d3ee2e9be61faf5530889 Mon Sep 17 00:00:00 2001 From: Preston Briggs Date: Wed, 21 Nov 2012 23:50:04 +0000 Subject: 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! llvm-svn: 168474 --- llvm/lib/Analysis/DependenceAnalysis.cpp | 177 +++++++++++++++++++------------ 1 file changed, 108 insertions(+), 69 deletions(-) (limited to 'llvm/lib/Analysis/DependenceAnalysis.cpp') 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(SrcPtr); - GEPOperator *DstGEP = dyn_cast(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(SrcPtr); + GEPOperator *DstGEP = dyn_cast(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 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(SrcPtr); - const GEPOperator *DstGEP = dyn_cast(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(SrcPtr); + GEPOperator *DstGEP = dyn_cast(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 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); -- cgit v1.2.3