X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionAliasAnalysis.cpp;h=2e50c80c4e731bb1ea3ff9ca3ab0da7cf3bdaea5;hb=4d0731f50589c740744edcbc8af5250988c3e0ef;hp=d7ecdde3e6c74628f6cb67476dfbb9c1e68278f6;hpb=b2143b6247901ae4eca2192ee134564c4f5f7853;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp index d7ecdde3e6c..2e50c80c4e7 100644 --- a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp +++ b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp @@ -19,118 +19,42 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Pass.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/Analysis/TargetLibraryInfo.h" using namespace llvm; -namespace { - /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis - /// implementation that uses ScalarEvolution to answer queries. - class ScalarEvolutionAliasAnalysis : public FunctionPass, - public AliasAnalysis { - ScalarEvolution *SE; - - public: - static char ID; // Class identification, replacement for typeinfo - ScalarEvolutionAliasAnalysis() : FunctionPass(ID), SE(0) {} - - /// 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(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 Location &LocA, const Location &LocB); - - Value *GetBaseValue(const SCEV *S); - }; -} // End of anonymous namespace - -// Register this pass... -char ScalarEvolutionAliasAnalysis::ID = 0; -INITIALIZE_AG_PASS(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", - "ScalarEvolution-based Alias Analysis", false, true, false); - -FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { - return new ScalarEvolutionAliasAnalysis(); -} - -void -ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredTransitive(); - AU.setPreservesAll(); - AliasAnalysis::getAnalysisUsage(AU); -} - -bool -ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { - InitializeAliasAnalysis(this); - SE = &getAnalysis(); - return false; -} - -/// GetBaseValue - Given an expression, try to find a -/// base value. Return null is none was found. -Value * -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 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 (Last->getType()->isPointerTy()) - return GetBaseValue(Last); - } else if (const SCEVUnknown *U = dyn_cast(S)) { - // This is a leaf node. - return U->getValue(); - } - // No Identified object found. - return 0; -} - -AliasAnalysis::AliasResult -ScalarEvolutionAliasAnalysis::alias(const Location &LocA, - const Location &LocB) { +AliasResult SCEVAAResult::alias(const MemoryLocation &LocA, + const MemoryLocation &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(LocA.Ptr)); - const SCEV *BS = SE->getSCEV(const_cast(LocB.Ptr)); + // This is SCEVAAResult. Get the SCEVs! + 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; + if (AS == BS) + return MustAlias; // If something is known about the difference between the two addresses, // see if it's enough to prove a NoAlias. - if (SE->getEffectiveSCEVType(AS->getType()) == - SE->getEffectiveSCEVType(BS->getType())) { - unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); + if (SE.getEffectiveSCEVType(AS->getType()) == + SE.getEffectiveSCEVType(BS->getType())) { + unsigned BitWidth = SE.getTypeSizeInBits(AS->getType()); APInt ASizeInt(BitWidth, LocA.Size); APInt BSizeInt(BitWidth, LocB.Size); // Compute the difference between the two pointers. - const SCEV *BA = SE->getMinusSCEV(BS, AS); + const SCEV *BA = SE.getMinusSCEV(BS, AS); // 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())) + 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 @@ -138,13 +62,13 @@ ScalarEvolutionAliasAnalysis::alias(const Location &LocA, // 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); + 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())) + if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) && + (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax())) return NoAlias; } @@ -154,14 +78,71 @@ ScalarEvolutionAliasAnalysis::alias(const Location &LocA, 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 ? 0 : LocA.TBAATag), - Location(BO ? BO : LocB.Ptr, - BO ? +UnknownSize : LocB.Size, - BO ? 0 : LocB.TBAATag)) == NoAlias) + if (alias(MemoryLocation(AO ? AO : LocA.Ptr, + AO ? +MemoryLocation::UnknownSize : LocA.Size, + AO ? AAMDNodes() : LocA.AATags), + MemoryLocation(BO ? BO : LocB.Ptr, + BO ? +MemoryLocation::UnknownSize : LocB.Size, + BO ? AAMDNodes() : LocB.AATags)) == NoAlias) return NoAlias; // Forward the query to the next analysis. - return AliasAnalysis::alias(LocA, LocB); + return AAResultBase::alias(LocA, LocB); +} + +/// Given an expression, try to find a base value. +/// +/// Returns null if none was found. +Value *SCEVAAResult::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 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 (Last->getType()->isPointerTy()) + return GetBaseValue(Last); + } else if (const SCEVUnknown *U = dyn_cast(S)) { + // This is a leaf node. + return U->getValue(); + } + // No Identified object found. + return nullptr; +} + +SCEVAAResult SCEVAA::run(Function &F, AnalysisManager *AM) { + return SCEVAAResult(AM->getResult(F), + AM->getResult(F)); +} + +char SCEVAA::PassID; + +char SCEVAAWrapperPass::ID = 0; +INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa", + "ScalarEvolution-based Alias Analysis", false, true) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa", + "ScalarEvolution-based Alias Analysis", false, true) + +FunctionPass *llvm::createSCEVAAWrapperPass() { + return new SCEVAAWrapperPass(); +} + +SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) { + initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +bool SCEVAAWrapperPass::runOnFunction(Function &F) { + Result.reset( + new SCEVAAResult(getAnalysis().getTLI(), + getAnalysis().getSE())); + return false; +} + +void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + AU.addRequired(); }