X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionAliasAnalysis.cpp;h=ccec0a877f5a460ab89183ff7de38a1579e0d441;hb=c16fc548515f2fd01bc2cbe4befd822a636cc154;hp=204d193625ac63a3fe36148ae442c9f524339939;hpb=6726b6d75a8b679068a58cb954ba97cf9d1690ba;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp index 204d193625a..ccec0a877f5 100644 --- a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp +++ b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp @@ -10,16 +10,20 @@ // 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. // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/Passes.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Analysis/Passes.h" +#include "llvm/IR/Module.h" #include "llvm/Pass.h" -#include "llvm/Support/Compiler.h" using namespace llvm; namespace { @@ -31,25 +35,37 @@ namespace { public: static char ID; // Class identification, replacement for typeinfo - ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} + ScalarEvolutionAliasAnalysis() : FunctionPass(ID), SE(nullptr) { + 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. + void *getAdjustedAnalysisPointer(AnalysisID PI) override { + 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); + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; + AliasResult alias(const Location &LocA, const Location &LocB) override; - Value *GetUnderlyingIdentifiedObject(const SCEV *S); + Value *GetBaseValue(const SCEV *S); }; } // End of anonymous 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(); @@ -64,41 +80,44 @@ ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { bool ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { - InitializeAliasAnalysis(this); + InitializeAliasAnalysis(this, &F.getParent()->getDataLayout()); SE = &getAnalysis(); return false; } -/// GetUnderlyingIdentifiedObject - Given an expression, try to find an -/// "identified object" (see AliasAnalysis::isIdentifiedObject) base -/// value. Return null is none was found. +/// GetBaseValue - Given an expression, try to find a +/// base value. Return null is none was found. Value * -ScalarEvolutionAliasAnalysis::GetUnderlyingIdentifiedObject(const SCEV *S) { +ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { if (const SCEVAddRecExpr *AR = dyn_cast(S)) { // In an addrec, assume that the base will be in the start, rather // than the step. - return GetUnderlyingIdentifiedObject(AR->getStart()); + return GetBaseValue(AR->getStart()); } 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())) - return GetUnderlyingIdentifiedObject(Last); + if (Last->getType()->isPointerTy()) + return GetBaseValue(Last); } else if (const SCEVUnknown *U = dyn_cast(S)) { - // Determine if we've found an Identified object. - Value *V = U->getValue(); - if (isIdentifiedObject(V)) - return V; + // This is a leaf node. + return U->getValue(); } // No Identified object found. - return 0; + return nullptr; } 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; @@ -108,26 +127,48 @@ 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. // The correctness of this depends on ScalarEvolution not recognizing // inttoptr and ptrtoint operators. - Value *AO = GetUnderlyingIdentifiedObject(AS); - Value *BO = GetUnderlyingIdentifiedObject(BS); - if ((AO && AO != A) || (BO && BO != B)) - if (alias(AO ? AO : A, AO ? ~0u : ASize, - BO ? BO : B, BO ? ~0u : BSize) == NoAlias) + Value *AO = GetBaseValue(AS); + Value *BO = GetBaseValue(BS); + if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) + if (alias(Location(AO ? AO : LocA.Ptr, + AO ? +UnknownSize : LocA.Size, + AO ? AAMDNodes() : LocA.AATags), + Location(BO ? BO : LocB.Ptr, + BO ? +UnknownSize : LocB.Size, + BO ? AAMDNodes() : LocB.AATags)) == NoAlias) return NoAlias; // Forward the query to the next analysis. - return AliasAnalysis::alias(A, ASize, B, BSize); + return AliasAnalysis::alias(LocA, LocB); }