ScalarEvolutionAliasAnalysis.cpp revision 5a44ef9fd5f7c3964ad79b94778261175dea5c33
1//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a 11// simple alias analysis implemented in terms of ScalarEvolution queries. 12// 13// ScalarEvolution has a more complete understanding of pointer arithmetic 14// than BasicAliasAnalysis' collection of ad-hoc analyses. 15// 16//===----------------------------------------------------------------------===// 17 18#include "llvm/Analysis/AliasAnalysis.h" 19#include "llvm/Analysis/ScalarEvolutionExpressions.h" 20#include "llvm/Analysis/Passes.h" 21#include "llvm/Pass.h" 22using namespace llvm; 23 24namespace { 25 /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 26 /// implementation that uses ScalarEvolution to answer queries. 27 class ScalarEvolutionAliasAnalysis : public FunctionPass, 28 public AliasAnalysis { 29 ScalarEvolution *SE; 30 31 public: 32 static char ID; // Class identification, replacement for typeinfo 33 ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} 34 35 private: 36 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 37 virtual bool runOnFunction(Function &F); 38 virtual AliasResult alias(const Value *V1, unsigned V1Size, 39 const Value *V2, unsigned V2Size); 40 41 Value *GetUnderlyingIdentifiedObject(const SCEV *S); 42 }; 43} // End of anonymous namespace 44 45// Register this pass... 46char ScalarEvolutionAliasAnalysis::ID = 0; 47static RegisterPass<ScalarEvolutionAliasAnalysis> 48X("scev-aa", "ScalarEvolution-based Alias Analysis", false, true); 49 50// Declare that we implement the AliasAnalysis interface 51static RegisterAnalysisGroup<AliasAnalysis> Y(X); 52 53FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 54 return new ScalarEvolutionAliasAnalysis(); 55} 56 57void 58ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 59 AU.addRequiredTransitive<ScalarEvolution>(); 60 AU.setPreservesAll(); 61 AliasAnalysis::getAnalysisUsage(AU); 62} 63 64bool 65ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 66 InitializeAliasAnalysis(this); 67 SE = &getAnalysis<ScalarEvolution>(); 68 return false; 69} 70 71/// GetUnderlyingIdentifiedObject - Given an expression, try to find an 72/// "identified object" (see AliasAnalysis::isIdentifiedObject) base 73/// value. Return null is none was found. 74Value * 75ScalarEvolutionAliasAnalysis::GetUnderlyingIdentifiedObject(const SCEV *S) { 76 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 77 // In an addrec, assume that the base will be in the start, rather 78 // than the step. 79 return GetUnderlyingIdentifiedObject(AR->getStart()); 80 } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 81 // If there's a pointer operand, it'll be sorted at the end of the list. 82 const SCEV *Last = A->getOperand(A->getNumOperands()-1); 83 if (isa<PointerType>(Last->getType())) 84 return GetUnderlyingIdentifiedObject(Last); 85 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 86 // Determine if we've found an Identified object. 87 Value *V = U->getValue(); 88 if (isIdentifiedObject(V)) 89 return V; 90 } 91 // No Identified object found. 92 return 0; 93} 94 95AliasAnalysis::AliasResult 96ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, 97 const Value *B, unsigned BSize) { 98 // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 99 const SCEV *AS = SE->getSCEV(const_cast<Value *>(A)); 100 const SCEV *BS = SE->getSCEV(const_cast<Value *>(B)); 101 102 // If they evaluate to the same expression, it's a MustAlias. 103 if (AS == BS) return MustAlias; 104 105 // If something is known about the difference between the two addresses, 106 // see if it's enough to prove a NoAlias. 107 if (SE->getEffectiveSCEVType(AS->getType()) == 108 SE->getEffectiveSCEVType(BS->getType())) { 109 unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 110 APInt AI(BitWidth, ASize); 111 const SCEV *BA = SE->getMinusSCEV(BS, AS); 112 if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) { 113 APInt BI(BitWidth, BSize); 114 const SCEV *AB = SE->getMinusSCEV(AS, BS); 115 if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin())) 116 return NoAlias; 117 } 118 } 119 120 // If ScalarEvolution can find an underlying object, form a new query. 121 // The correctness of this depends on ScalarEvolution not recognizing 122 // inttoptr and ptrtoint operators. 123 Value *AO = GetUnderlyingIdentifiedObject(AS); 124 Value *BO = GetUnderlyingIdentifiedObject(BS); 125 if ((AO && AO != A) || (BO && BO != B)) 126 if (alias(AO ? AO : A, AO ? ~0u : ASize, 127 BO ? BO : B, BO ? ~0u : BSize) == NoAlias) 128 return NoAlias; 129 130 // Forward the query to the next analysis. 131 return AliasAnalysis::alias(A, ASize, B, BSize); 132} 133