ScalarEvolutionAliasAnalysis.cpp revision 204642
1198090Srdivacky//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// 2198090Srdivacky// 3198090Srdivacky// The LLVM Compiler Infrastructure 4198090Srdivacky// 5198090Srdivacky// This file is distributed under the University of Illinois Open Source 6198090Srdivacky// License. See LICENSE.TXT for details. 7198090Srdivacky// 8198090Srdivacky//===----------------------------------------------------------------------===// 9198090Srdivacky// 10198090Srdivacky// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a 11198090Srdivacky// simple alias analysis implemented in terms of ScalarEvolution queries. 12198090Srdivacky// 13204642Srdivacky// This differs from traditional loop dependence analysis in that it tests 14204642Srdivacky// for dependencies within a single iteration of a loop, rather than 15204642Srdivacky// dependences between different iterations. 16204642Srdivacky// 17198090Srdivacky// ScalarEvolution has a more complete understanding of pointer arithmetic 18198090Srdivacky// than BasicAliasAnalysis' collection of ad-hoc analyses. 19198090Srdivacky// 20198090Srdivacky//===----------------------------------------------------------------------===// 21198090Srdivacky 22198090Srdivacky#include "llvm/Analysis/AliasAnalysis.h" 23198090Srdivacky#include "llvm/Analysis/ScalarEvolutionExpressions.h" 24198090Srdivacky#include "llvm/Analysis/Passes.h" 25198090Srdivacky#include "llvm/Pass.h" 26198090Srdivackyusing namespace llvm; 27198090Srdivacky 28198090Srdivackynamespace { 29198090Srdivacky /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 30198090Srdivacky /// implementation that uses ScalarEvolution to answer queries. 31198892Srdivacky class ScalarEvolutionAliasAnalysis : public FunctionPass, 32198892Srdivacky public AliasAnalysis { 33198090Srdivacky ScalarEvolution *SE; 34198090Srdivacky 35198090Srdivacky public: 36198090Srdivacky static char ID; // Class identification, replacement for typeinfo 37198090Srdivacky ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} 38198090Srdivacky 39202878Srdivacky /// getAdjustedAnalysisPointer - This method is used when a pass implements 40202878Srdivacky /// an analysis interface through multiple inheritance. If needed, it 41202878Srdivacky /// should override this to adjust the this pointer as needed for the 42202878Srdivacky /// specified pass info. 43202878Srdivacky virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { 44202878Srdivacky if (PI->isPassID(&AliasAnalysis::ID)) 45202878Srdivacky return (AliasAnalysis*)this; 46202878Srdivacky return this; 47202878Srdivacky } 48204642Srdivacky 49198090Srdivacky private: 50198090Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const; 51198090Srdivacky virtual bool runOnFunction(Function &F); 52198090Srdivacky virtual AliasResult alias(const Value *V1, unsigned V1Size, 53198090Srdivacky const Value *V2, unsigned V2Size); 54198090Srdivacky 55198892Srdivacky Value *GetBaseValue(const SCEV *S); 56198090Srdivacky }; 57198090Srdivacky} // End of anonymous namespace 58198090Srdivacky 59198090Srdivacky// Register this pass... 60198090Srdivackychar ScalarEvolutionAliasAnalysis::ID = 0; 61198090Srdivackystatic RegisterPass<ScalarEvolutionAliasAnalysis> 62198090SrdivackyX("scev-aa", "ScalarEvolution-based Alias Analysis", false, true); 63198090Srdivacky 64198090Srdivacky// Declare that we implement the AliasAnalysis interface 65198090Srdivackystatic RegisterAnalysisGroup<AliasAnalysis> Y(X); 66198090Srdivacky 67198090SrdivackyFunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 68198090Srdivacky return new ScalarEvolutionAliasAnalysis(); 69198090Srdivacky} 70198090Srdivacky 71198090Srdivackyvoid 72198090SrdivackyScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 73198090Srdivacky AU.addRequiredTransitive<ScalarEvolution>(); 74198090Srdivacky AU.setPreservesAll(); 75198090Srdivacky AliasAnalysis::getAnalysisUsage(AU); 76198090Srdivacky} 77198090Srdivacky 78198090Srdivackybool 79198090SrdivackyScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 80198090Srdivacky InitializeAliasAnalysis(this); 81198090Srdivacky SE = &getAnalysis<ScalarEvolution>(); 82198090Srdivacky return false; 83198090Srdivacky} 84198090Srdivacky 85198892Srdivacky/// GetBaseValue - Given an expression, try to find a 86198892Srdivacky/// base value. Return null is none was found. 87198090SrdivackyValue * 88198892SrdivackyScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 89198090Srdivacky if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 90198090Srdivacky // In an addrec, assume that the base will be in the start, rather 91198090Srdivacky // than the step. 92198892Srdivacky return GetBaseValue(AR->getStart()); 93198090Srdivacky } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 94198090Srdivacky // If there's a pointer operand, it'll be sorted at the end of the list. 95198090Srdivacky const SCEV *Last = A->getOperand(A->getNumOperands()-1); 96204642Srdivacky if (Last->getType()->isPointerTy()) 97198892Srdivacky return GetBaseValue(Last); 98198090Srdivacky } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 99198892Srdivacky // This is a leaf node. 100198892Srdivacky return U->getValue(); 101198090Srdivacky } 102198090Srdivacky // No Identified object found. 103198090Srdivacky return 0; 104198090Srdivacky} 105198090Srdivacky 106198090SrdivackyAliasAnalysis::AliasResult 107198090SrdivackyScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, 108198090Srdivacky const Value *B, unsigned BSize) { 109198090Srdivacky // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 110198090Srdivacky const SCEV *AS = SE->getSCEV(const_cast<Value *>(A)); 111198090Srdivacky const SCEV *BS = SE->getSCEV(const_cast<Value *>(B)); 112198090Srdivacky 113198090Srdivacky // If they evaluate to the same expression, it's a MustAlias. 114198090Srdivacky if (AS == BS) return MustAlias; 115198090Srdivacky 116198090Srdivacky // If something is known about the difference between the two addresses, 117198090Srdivacky // see if it's enough to prove a NoAlias. 118198090Srdivacky if (SE->getEffectiveSCEVType(AS->getType()) == 119198090Srdivacky SE->getEffectiveSCEVType(BS->getType())) { 120198090Srdivacky unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 121198090Srdivacky APInt AI(BitWidth, ASize); 122198090Srdivacky const SCEV *BA = SE->getMinusSCEV(BS, AS); 123198090Srdivacky if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) { 124198090Srdivacky APInt BI(BitWidth, BSize); 125198090Srdivacky const SCEV *AB = SE->getMinusSCEV(AS, BS); 126198090Srdivacky if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin())) 127198090Srdivacky return NoAlias; 128198090Srdivacky } 129198090Srdivacky } 130198090Srdivacky 131198090Srdivacky // If ScalarEvolution can find an underlying object, form a new query. 132198090Srdivacky // The correctness of this depends on ScalarEvolution not recognizing 133198090Srdivacky // inttoptr and ptrtoint operators. 134198892Srdivacky Value *AO = GetBaseValue(AS); 135198892Srdivacky Value *BO = GetBaseValue(BS); 136198090Srdivacky if ((AO && AO != A) || (BO && BO != B)) 137198090Srdivacky if (alias(AO ? AO : A, AO ? ~0u : ASize, 138198090Srdivacky BO ? BO : B, BO ? ~0u : BSize) == NoAlias) 139198090Srdivacky return NoAlias; 140198090Srdivacky 141198090Srdivacky // Forward the query to the next analysis. 142198090Srdivacky return AliasAnalysis::alias(A, ASize, B, BSize); 143198090Srdivacky} 144