ScalarEvolutionAliasAnalysis.cpp revision 8be3291f5942e3ae4a5d66c480e7aabe2f771031
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// This differs from traditional loop dependence analysis in that it tests 14// for dependencies within a single iteration of a loop, rather than 15// dependencies between different iterations. 16// 17// ScalarEvolution has a more complete understanding of pointer arithmetic 18// than BasicAliasAnalysis' collection of ad-hoc analyses. 19// 20//===----------------------------------------------------------------------===// 21 22#include "llvm/Analysis/AliasAnalysis.h" 23#include "llvm/Analysis/ScalarEvolutionExpressions.h" 24#include "llvm/Analysis/Passes.h" 25#include "llvm/Pass.h" 26using namespace llvm; 27 28namespace { 29 /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 30 /// implementation that uses ScalarEvolution to answer queries. 31 class ScalarEvolutionAliasAnalysis : public FunctionPass, 32 public AliasAnalysis { 33 ScalarEvolution *SE; 34 35 public: 36 static char ID; // Class identification, replacement for typeinfo 37 ScalarEvolutionAliasAnalysis() : FunctionPass(&ID), SE(0) {} 38 39 /// getAdjustedAnalysisPointer - This method is used when a pass implements 40 /// an analysis interface through multiple inheritance. If needed, it 41 /// should override this to adjust the this pointer as needed for the 42 /// specified pass info. 43 virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { 44 if (PI->isPassID(&AliasAnalysis::ID)) 45 return (AliasAnalysis*)this; 46 return this; 47 } 48 49 private: 50 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 51 virtual bool runOnFunction(Function &F); 52 virtual AliasResult alias(const Value *V1, unsigned V1Size, 53 const Value *V2, unsigned V2Size); 54 55 Value *GetBaseValue(const SCEV *S); 56 }; 57} // End of anonymous namespace 58 59// Register this pass... 60char ScalarEvolutionAliasAnalysis::ID = 0; 61static RegisterPass<ScalarEvolutionAliasAnalysis> 62X("scev-aa", "ScalarEvolution-based Alias Analysis", false, true); 63 64// Declare that we implement the AliasAnalysis interface 65static RegisterAnalysisGroup<AliasAnalysis> Y(X); 66 67FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 68 return new ScalarEvolutionAliasAnalysis(); 69} 70 71void 72ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 73 AU.addRequiredTransitive<ScalarEvolution>(); 74 AU.setPreservesAll(); 75 AliasAnalysis::getAnalysisUsage(AU); 76} 77 78bool 79ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 80 InitializeAliasAnalysis(this); 81 SE = &getAnalysis<ScalarEvolution>(); 82 return false; 83} 84 85/// GetBaseValue - Given an expression, try to find a 86/// base value. Return null is none was found. 87Value * 88ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 89 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 90 // In an addrec, assume that the base will be in the start, rather 91 // than the step. 92 return GetBaseValue(AR->getStart()); 93 } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 94 // If there's a pointer operand, it'll be sorted at the end of the list. 95 const SCEV *Last = A->getOperand(A->getNumOperands()-1); 96 if (Last->getType()->isPointerTy()) 97 return GetBaseValue(Last); 98 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 99 // This is a leaf node. 100 return U->getValue(); 101 } 102 // No Identified object found. 103 return 0; 104} 105 106AliasAnalysis::AliasResult 107ScalarEvolutionAliasAnalysis::alias(const Value *A, unsigned ASize, 108 const Value *B, unsigned BSize) { 109 // If either of the memory references is empty, it doesn't matter what the 110 // pointer values are. This allows the code below to ignore this special 111 // case. 112 if (ASize == 0 || BSize == 0) 113 return NoAlias; 114 115 // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 116 const SCEV *AS = SE->getSCEV(const_cast<Value *>(A)); 117 const SCEV *BS = SE->getSCEV(const_cast<Value *>(B)); 118 119 // If they evaluate to the same expression, it's a MustAlias. 120 if (AS == BS) return MustAlias; 121 122 // If something is known about the difference between the two addresses, 123 // see if it's enough to prove a NoAlias. 124 if (SE->getEffectiveSCEVType(AS->getType()) == 125 SE->getEffectiveSCEVType(BS->getType())) { 126 unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 127 APInt ASizeInt(BitWidth, ASize); 128 APInt BSizeInt(BitWidth, BSize); 129 130 // Compute the difference between the two pointers. 131 const SCEV *BA = SE->getMinusSCEV(BS, AS); 132 133 // Test whether the difference is known to be great enough that memory of 134 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 135 // are non-zero, which is special-cased above. 136 if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) && 137 (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax())) 138 return NoAlias; 139 140 // Folding the subtraction while preserving range information can be tricky 141 // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS 142 // and try again to see if things fold better that way. 143 144 // Compute the difference between the two pointers. 145 const SCEV *AB = SE->getMinusSCEV(AS, BS); 146 147 // Test whether the difference is known to be great enough that memory of 148 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 149 // are non-zero, which is special-cased above. 150 if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) && 151 (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax())) 152 return NoAlias; 153 } 154 155 // If ScalarEvolution can find an underlying object, form a new query. 156 // The correctness of this depends on ScalarEvolution not recognizing 157 // inttoptr and ptrtoint operators. 158 Value *AO = GetBaseValue(AS); 159 Value *BO = GetBaseValue(BS); 160 if ((AO && AO != A) || (BO && BO != B)) 161 if (alias(AO ? AO : A, AO ? ~0u : ASize, 162 BO ? BO : B, BO ? ~0u : BSize) == NoAlias) 163 return NoAlias; 164 165 // Forward the query to the next analysis. 166 return AliasAnalysis::alias(A, ASize, B, BSize); 167} 168