X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionAliasAnalysis.cpp;h=e9edb3e083def8e4160e33cfa3bb10761226bb41;hb=ff10341183adf74760e6118a55cbd1debf50f90f;hp=498c4a876c9807eced75f9c19898ccdbff929eb2;hpb=1bc76d48d476446f226f06f0aced7efb268f2536;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp index 498c4a876c9..e9edb3e083d 100644 --- a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp +++ b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp @@ -10,6 +10,10 @@ // This file defines the ScalarEvolutionAliasAnalysis pass, which implements a // simple alias analysis implemented in terms of ScalarEvolution queries. // +// This differs from traditional loop dependence analysis in that it tests +// for dependencies within a single iteration of a loop, rather than +// dependencies between different iterations. +// // ScalarEvolution has a more complete understanding of pointer arithmetic // than BasicAliasAnalysis' collection of ad-hoc analyses. // @@ -30,23 +34,25 @@ namespace { public: static char ID; // Class identification, replacement for typeinfo - ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} + ScalarEvolutionAliasAnalysis() : FunctionPass(ID), SE(0) { + initializeScalarEvolutionAliasAnalysisPass( + *PassRegistry::getPassRegistry()); + } /// getAdjustedAnalysisPointer - This method is used when a pass implements /// an analysis interface through multiple inheritance. If needed, it /// should override this to adjust the this pointer as needed for the /// specified pass info. - virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { - if (PI->isPassID(&AliasAnalysis::ID)) + virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { + if (PI == &AliasAnalysis::ID) return (AliasAnalysis*)this; return this; } - + private: virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual bool runOnFunction(Function &F); - virtual AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); + virtual AliasResult alias(const Location &LocA, const Location &LocB); Value *GetBaseValue(const SCEV *S); }; @@ -54,11 +60,11 @@ namespace { // Register this pass... char ScalarEvolutionAliasAnalysis::ID = 0; -static RegisterPass -X("scev-aa", "ScalarEvolution-based Alias Analysis", false, true); - -// Declare that we implement the AliasAnalysis interface -static RegisterAnalysisGroup Y(X); +INITIALIZE_AG_PASS_BEGIN(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", + "ScalarEvolution-based Alias Analysis", false, true, false) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) +INITIALIZE_AG_PASS_END(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", + "ScalarEvolution-based Alias Analysis", false, true, false) FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { return new ScalarEvolutionAliasAnalysis(); @@ -89,7 +95,7 @@ ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { } else if (const SCEVAddExpr *A = dyn_cast(S)) { // If there's a pointer operand, it'll be sorted at the end of the list. const SCEV *Last = A->getOperand(A->getNumOperands()-1); - if (isa(Last->getType())) + if (Last->getType()->isPointerTy()) return GetBaseValue(Last); } else if (const SCEVUnknown *U = dyn_cast(S)) { // This is a leaf node. @@ -100,11 +106,17 @@ ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { } AliasAnalysis::AliasResult -ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, - const Value *B, unsigned BSize) { +ScalarEvolutionAliasAnalysis::alias(const Location &LocA, + const Location &LocB) { + // If either of the memory references is empty, it doesn't matter what the + // pointer values are. This allows the code below to ignore this special + // case. + if (LocA.Size == 0 || LocB.Size == 0) + return NoAlias; + // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! - const SCEV *AS = SE->getSCEV(const_cast(A)); - const SCEV *BS = SE->getSCEV(const_cast(B)); + const SCEV *AS = SE->getSCEV(const_cast(LocA.Ptr)); + const SCEV *BS = SE->getSCEV(const_cast(LocB.Ptr)); // If they evaluate to the same expression, it's a MustAlias. if (AS == BS) return MustAlias; @@ -114,14 +126,32 @@ ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, if (SE->getEffectiveSCEVType(AS->getType()) == SE->getEffectiveSCEVType(BS->getType())) { unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); - APInt AI(BitWidth, ASize); + APInt ASizeInt(BitWidth, LocA.Size); + APInt BSizeInt(BitWidth, LocB.Size); + + // Compute the difference between the two pointers. const SCEV *BA = SE->getMinusSCEV(BS, AS); - if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) { - APInt BI(BitWidth, BSize); - const SCEV *AB = SE->getMinusSCEV(AS, BS); - if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin())) - return NoAlias; - } + + // Test whether the difference is known to be great enough that memory of + // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt + // are non-zero, which is special-cased above. + if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) && + (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax())) + return NoAlias; + + // Folding the subtraction while preserving range information can be tricky + // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS + // and try again to see if things fold better that way. + + // Compute the difference between the two pointers. + const SCEV *AB = SE->getMinusSCEV(AS, BS); + + // Test whether the difference is known to be great enough that memory of + // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt + // are non-zero, which is special-cased above. + if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) && + (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax())) + return NoAlias; } // If ScalarEvolution can find an underlying object, form a new query. @@ -129,11 +159,15 @@ ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, // inttoptr and ptrtoint operators. Value *AO = GetBaseValue(AS); Value *BO = GetBaseValue(BS); - if ((AO && AO != A) || (BO && BO != B)) - if (alias(AO ? AO : A, AO ? ~0u : ASize, - BO ? BO : B, BO ? ~0u : BSize) == NoAlias) + if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) + if (alias(Location(AO ? AO : LocA.Ptr, + AO ? +UnknownSize : LocA.Size, + AO ? 0 : LocA.TBAATag), + Location(BO ? BO : LocB.Ptr, + BO ? +UnknownSize : LocB.Size, + BO ? 0 : LocB.TBAATag)) == NoAlias) return NoAlias; // Forward the query to the next analysis. - return AliasAnalysis::alias(A, ASize, B, BSize); + return AliasAnalysis::alias(LocA, LocB); }