ScalarEvolutionAliasAnalysis.cpp revision 2385e0e22ca482f2896dfa975a08db2f54926c09
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" 22#include "llvm/Support/Compiler.h" 23using namespace llvm; 24 25namespace { 26 /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 27 /// implementation that uses ScalarEvolution to answer queries. 28 class VISIBILITY_HIDDEN ScalarEvolutionAliasAnalysis : public FunctionPass, 29 public AliasAnalysis { 30 ScalarEvolution *SE; 31 32 public: 33 static char ID; // Class identification, replacement for typeinfo 34 ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} 35 36 private: 37 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 38 virtual bool runOnFunction(Function &F); 39 virtual AliasResult alias(const Value *V1, unsigned V1Size, 40 const Value *V2, unsigned V2Size); 41 42 Value *GetUnderlyingIdentifiedObject(const SCEV *S); 43 }; 44} // End of anonymous namespace 45 46// Register this pass... 47char ScalarEvolutionAliasAnalysis::ID = 0; 48static RegisterPass<ScalarEvolutionAliasAnalysis> 49X("scev-aa", "ScalarEvolution-based Alias Analysis", false, true); 50 51// Declare that we implement the AliasAnalysis interface 52static RegisterAnalysisGroup<AliasAnalysis> Y(X); 53 54FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 55 return new ScalarEvolutionAliasAnalysis(); 56} 57 58void 59ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 60 AU.addRequiredTransitive<ScalarEvolution>(); 61 AU.setPreservesAll(); 62 AliasAnalysis::getAnalysisUsage(AU); 63} 64 65bool 66ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 67 InitializeAliasAnalysis(this); 68 SE = &getAnalysis<ScalarEvolution>(); 69 return false; 70} 71 72Value * 73ScalarEvolutionAliasAnalysis::GetUnderlyingIdentifiedObject(const SCEV *S) { 74 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 75 return GetUnderlyingIdentifiedObject(AR->getStart()); 76 } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 77 // If there's a pointer operand, it'll be sorted at the end of the list. 78 const SCEV *Last = A->getOperand(A->getNumOperands()-1); 79 if (isa<PointerType>(Last->getType())) 80 return GetUnderlyingIdentifiedObject(Last); 81 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 82 // Determine if we've found an Identified object. 83 Value *V = U->getValue(); 84 if (isIdentifiedObject(V)) 85 return V; 86 } 87 // No Identified object found. 88 return 0; 89} 90 91AliasAnalysis::AliasResult 92ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, 93 const Value *B, unsigned BSize) { 94 // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 95 const SCEV *AS = SE->getSCEV(const_cast<Value *>(A)); 96 const SCEV *BS = SE->getSCEV(const_cast<Value *>(B)); 97 98 // If they evaluate to the same expression, it's a MustAlias. 99 if (AS == BS) return MustAlias; 100 101 // If something is known about the difference between the two addresses, 102 // see if it's enough to prove a NoAlias. 103 if (SE->getEffectiveSCEVType(AS->getType()) == 104 SE->getEffectiveSCEVType(BS->getType())) { 105 unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 106 APInt AI(BitWidth, ASize); 107 const SCEV *BA = SE->getMinusSCEV(BS, AS); 108 if (AI.ule(SE->getUnsignedRange(BA).getUnsignedMin())) { 109 APInt BI(BitWidth, BSize); 110 const SCEV *AB = SE->getMinusSCEV(AS, BS); 111 if (BI.ule(SE->getUnsignedRange(AB).getUnsignedMin())) 112 return NoAlias; 113 } 114 } 115 116 // If ScalarEvolution can find an underlying object, form a new query. 117 // The correctness of this depends on ScalarEvolution not recognizing 118 // inttoptr and ptrtoint operators. 119 Value *AO = GetUnderlyingIdentifiedObject(AS); 120 Value *BO = GetUnderlyingIdentifiedObject(BS); 121 if ((AO && AO != A) || (BO && BO != B)) 122 if (alias(AO ? AO : A, AO ? ~0u : ASize, 123 BO ? BO : B, BO ? ~0u : BSize) == NoAlias) 124 return NoAlias; 125 126 // Forward the query to the next analysis. 127 return AliasAnalysis::alias(A, ASize, B, BSize); 128} 129