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/Passes.h" 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/Analysis/ScalarEvolutionExpressions.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(nullptr) { 38 initializeScalarEvolutionAliasAnalysisPass( 39 *PassRegistry::getPassRegistry()); 40 } 41 42 /// getAdjustedAnalysisPointer - This method is used when a pass implements 43 /// an analysis interface through multiple inheritance. If needed, it 44 /// should override this to adjust the this pointer as needed for the 45 /// specified pass info. 46 void *getAdjustedAnalysisPointer(AnalysisID PI) override { 47 if (PI == &AliasAnalysis::ID) 48 return (AliasAnalysis*)this; 49 return this; 50 } 51 52 private: 53 void getAnalysisUsage(AnalysisUsage &AU) const override; 54 bool runOnFunction(Function &F) override; 55 AliasResult alias(const Location &LocA, const Location &LocB) override; 56 57 Value *GetBaseValue(const SCEV *S); 58 }; 59} // End of anonymous namespace 60 61// Register this pass... 62char ScalarEvolutionAliasAnalysis::ID = 0; 63INITIALIZE_AG_PASS_BEGIN(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 64 "ScalarEvolution-based Alias Analysis", false, true, false) 65INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 66INITIALIZE_AG_PASS_END(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 67 "ScalarEvolution-based Alias Analysis", false, true, false) 68 69FunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 70 return new ScalarEvolutionAliasAnalysis(); 71} 72 73void 74ScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 75 AU.addRequiredTransitive<ScalarEvolution>(); 76 AU.setPreservesAll(); 77 AliasAnalysis::getAnalysisUsage(AU); 78} 79 80bool 81ScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 82 InitializeAliasAnalysis(this); 83 SE = &getAnalysis<ScalarEvolution>(); 84 return false; 85} 86 87/// GetBaseValue - Given an expression, try to find a 88/// base value. Return null is none was found. 89Value * 90ScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 91 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 92 // In an addrec, assume that the base will be in the start, rather 93 // than the step. 94 return GetBaseValue(AR->getStart()); 95 } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 96 // If there's a pointer operand, it'll be sorted at the end of the list. 97 const SCEV *Last = A->getOperand(A->getNumOperands()-1); 98 if (Last->getType()->isPointerTy()) 99 return GetBaseValue(Last); 100 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 101 // This is a leaf node. 102 return U->getValue(); 103 } 104 // No Identified object found. 105 return nullptr; 106} 107 108AliasAnalysis::AliasResult 109ScalarEvolutionAliasAnalysis::alias(const Location &LocA, 110 const Location &LocB) { 111 // If either of the memory references is empty, it doesn't matter what the 112 // pointer values are. This allows the code below to ignore this special 113 // case. 114 if (LocA.Size == 0 || LocB.Size == 0) 115 return NoAlias; 116 117 // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 118 const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr)); 119 const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr)); 120 121 // If they evaluate to the same expression, it's a MustAlias. 122 if (AS == BS) return MustAlias; 123 124 // If something is known about the difference between the two addresses, 125 // see if it's enough to prove a NoAlias. 126 if (SE->getEffectiveSCEVType(AS->getType()) == 127 SE->getEffectiveSCEVType(BS->getType())) { 128 unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 129 APInt ASizeInt(BitWidth, LocA.Size); 130 APInt BSizeInt(BitWidth, LocB.Size); 131 132 // Compute the difference between the two pointers. 133 const SCEV *BA = SE->getMinusSCEV(BS, AS); 134 135 // Test whether the difference is known to be great enough that memory of 136 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 137 // are non-zero, which is special-cased above. 138 if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) && 139 (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax())) 140 return NoAlias; 141 142 // Folding the subtraction while preserving range information can be tricky 143 // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS 144 // and try again to see if things fold better that way. 145 146 // Compute the difference between the two pointers. 147 const SCEV *AB = SE->getMinusSCEV(AS, BS); 148 149 // Test whether the difference is known to be great enough that memory of 150 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 151 // are non-zero, which is special-cased above. 152 if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) && 153 (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax())) 154 return NoAlias; 155 } 156 157 // If ScalarEvolution can find an underlying object, form a new query. 158 // The correctness of this depends on ScalarEvolution not recognizing 159 // inttoptr and ptrtoint operators. 160 Value *AO = GetBaseValue(AS); 161 Value *BO = GetBaseValue(BS); 162 if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) 163 if (alias(Location(AO ? AO : LocA.Ptr, 164 AO ? +UnknownSize : LocA.Size, 165 AO ? nullptr : LocA.TBAATag), 166 Location(BO ? BO : LocB.Ptr, 167 BO ? +UnknownSize : LocB.Size, 168 BO ? nullptr : LocB.TBAATag)) == NoAlias) 169 return NoAlias; 170 171 // Forward the query to the next analysis. 172 return AliasAnalysis::alias(LocA, LocB); 173} 174