ScalarEvolutionAliasAnalysis.cpp revision 202878
118334Speter//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// 290075Sobrien// 3169699Skan// The LLVM Compiler Infrastructure 418334Speter// 590075Sobrien// This file is distributed under the University of Illinois Open Source 618334Speter// License. See LICENSE.TXT for details. 790075Sobrien// 890075Sobrien//===----------------------------------------------------------------------===// 990075Sobrien// 1090075Sobrien// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a 1118334Speter// simple alias analysis implemented in terms of ScalarEvolution queries. 1290075Sobrien// 1390075Sobrien// ScalarEvolution has a more complete understanding of pointer arithmetic 1490075Sobrien// than BasicAliasAnalysis' collection of ad-hoc analyses. 1590075Sobrien// 1618334Speter//===----------------------------------------------------------------------===// 1718334Speter 1890075Sobrien#include "llvm/Analysis/AliasAnalysis.h" 19169699Skan#include "llvm/Analysis/ScalarEvolutionExpressions.h" 20169699Skan#include "llvm/Analysis/Passes.h" 2118334Speter#include "llvm/Pass.h" 2218334Speterusing namespace llvm; 2318334Speter 2450397Sobriennamespace { 25132727Skan /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 26132727Skan /// implementation that uses ScalarEvolution to answer queries. 2718334Speter class ScalarEvolutionAliasAnalysis : public FunctionPass, 2890075Sobrien public AliasAnalysis { 2918334Speter ScalarEvolution *SE; 3018334Speter 3190075Sobrien public: 3218334Speter static char ID; // Class identification, replacement for typeinfo 3318334Speter ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} 34169699Skan 3590075Sobrien /// getAdjustedAnalysisPointer - This method is used when a pass implements 3690075Sobrien /// an analysis interface through multiple inheritance. If needed, it 3718334Speter /// should override this to adjust the this pointer as needed for the 3818334Speter /// specified pass info. 3952284Sobrien virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { 4052284Sobrien if (PI->isPassID(&AliasAnalysis::ID)) 4190075Sobrien return (AliasAnalysis*)this; 4290075Sobrien return this; 43169699Skan } 44169699Skan 4518334Speter private: 4618334Speter virtual void getAnalysisUsage(AnalysisUsage &AU) const; 4718334Speter virtual bool runOnFunction(Function &F); 4818334Speter virtual AliasResult alias(const Value *V1, unsigned V1Size, 4918334Speter const Value *V2, unsigned V2Size); 5018334Speter 5118334Speter Value *GetBaseValue(const SCEV *S); 5218334Speter }; 5318334Speter} // End of anonymous namespace 5452284Sobrien 5552284Sobrien// Register this pass... 5652284Sobrienchar ScalarEvolutionAliasAnalysis::ID = 0; 5752284Sobrienstatic RegisterPass<ScalarEvolutionAliasAnalysis> 5852284SobrienX("scev-aa", "ScalarEvolution-based Alias Analysis", false, true); 5952284Sobrien 6052284Sobrien// Declare that we implement the AliasAnalysis interface 6118334Speterstatic RegisterAnalysisGroup<AliasAnalysis> Y(X); 62132727Skan 63132727SkanFunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 64132727Skan return new ScalarEvolutionAliasAnalysis(); 65132727Skan} 6618334Speter 6718334Spetervoid 6818334SpeterScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 6918334Speter AU.addRequiredTransitive<ScalarEvolution>(); 7018334Speter AU.setPreservesAll(); 7118334Speter AliasAnalysis::getAnalysisUsage(AU); 7218334Speter} 7318334Speter 7418334Speterbool 7518334SpeterScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 7618334Speter InitializeAliasAnalysis(this); 7790075Sobrien SE = &getAnalysis<ScalarEvolution>(); 7852284Sobrien return false; 7952284Sobrien} 8052284Sobrien 8152284Sobrien/// GetBaseValue - Given an expression, try to find a 8252284Sobrien/// base value. Return null is none was found. 8318334SpeterValue * 8418334SpeterScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 8518334Speter if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 8618334Speter // In an addrec, assume that the base will be in the start, rather 8718334Speter // than the step. 8818334Speter return GetBaseValue(AR->getStart()); 8918334Speter } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 9018334Speter // If there's a pointer operand, it'll be sorted at the end of the list. 9118334Speter const SCEV *Last = A->getOperand(A->getNumOperands()-1); 9218334Speter if (isa<PointerType>(Last->getType())) 9318334Speter return GetBaseValue(Last); 94132727Skan } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 95132727Skan // This is a leaf node. 96132727Skan return U->getValue(); 9718334Speter } 9818334Speter // No Identified object found. 9918334Speter return 0; 10018334Speter} 10118334Speter 102132727SkanAliasAnalysis::AliasResult 10318334SpeterScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, 10418334Speter const Value *B, unsigned BSize) { 10518334Speter // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 10618334Speter const SCEV *AS = SE->getSCEV(const_cast<Value *>(A)); 10718334Speter const SCEV *BS = SE->getSCEV(const_cast<Value *>(B)); 108132727Skan 10918334Speter // If they evaluate to the same expression, it's a MustAlias. 11018334Speter if (AS == BS) return MustAlias; 11118334Speter 11218334Speter // If something is known about the difference between the two addresses, 11318334Speter // see if it's enough to prove a NoAlias. 11418334Speter if (SE->getEffectiveSCEVType(AS->getType()) == 11518334Speter SE->getEffectiveSCEVType(BS->getType())) { 11618334Speter unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 11718334Speter APInt AI(BitWidth, ASize); 118132727Skan const SCEV *BA = SE->getMinusSCEV(BS, AS); 11918334Speter if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) { 12052284Sobrien APInt BI(BitWidth, BSize); 12118334Speter const SCEV *AB = SE->getMinusSCEV(AS, BS); 12252284Sobrien if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin())) 12318334Speter return NoAlias; 12418334Speter } 12552284Sobrien } 12652284Sobrien 12752284Sobrien // If ScalarEvolution can find an underlying object, form a new query. 12852284Sobrien // The correctness of this depends on ScalarEvolution not recognizing 12952284Sobrien // inttoptr and ptrtoint operators. 13052284Sobrien Value *AO = GetBaseValue(AS); 13152284Sobrien Value *BO = GetBaseValue(BS); 13252284Sobrien if ((AO && AO != A) || (BO && BO != B)) 13352284Sobrien if (alias(AO ? AO : A, AO ? ~0u : ASize, 13452284Sobrien BO ? BO : B, BO ? ~0u : BSize) == NoAlias) 13518334Speter return NoAlias; 13618334Speter 13718334Speter // Forward the query to the next analysis. 13818334Speter return AliasAnalysis::alias(A, ASize, B, BSize); 13918334Speter} 140132727Skan