X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionAliasAnalysis.cpp;h=6fcf27ea4ab6ed8803026cb7e8b3e552b6b4bb51;hb=2cdf5c3e038396a30afb2abafc0492fb137b1828;hp=f95d4019f3e723831f8149e81a84290ec69c1ecc;hpb=4f46e14b8ab3861a8dbea14ed70cb9527ae24a06;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp index f95d4019f3e..6fcf27ea4ab 100644 --- a/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp +++ b/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp @@ -19,80 +19,46 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Pass.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.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(const PassInfo *PI) { - if (PI->isPassID(&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); - - 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(ScalarEvolutionWrapperPass) +INITIALIZE_AG_PASS_END(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(); +void ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredTransitive(); AU.setPreservesAll(); AliasAnalysis::getAnalysisUsage(AU); } -bool -ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { - InitializeAliasAnalysis(this); - SE = &getAnalysis(); +bool ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { + InitializeAliasAnalysis(this, &F.getParent()->getDataLayout()); + SE = &getAnalysis().getSE(); return false; } -/// GetBaseValue - Given an expression, try to find a -/// base value. Return null is none was found. -Value * -ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { +/// Given an expression, try to find a base value. +/// +/// Returns null if 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); + const SCEV *Last = A->getOperand(A->getNumOperands() - 1); if (Last->getType()->isPointerTy()) return GetBaseValue(Last); } else if (const SCEVUnknown *U = dyn_cast(S)) { @@ -100,32 +66,56 @@ ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 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) { +AliasResult ScalarEvolutionAliasAnalysis::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(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; + 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()); - 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. @@ -133,11 +123,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(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(A, ASize, B, BSize); + return AliasAnalysis::alias(LocA, LocB); }