1133359Sobrien//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// 268349Sobrien// 3139368Sobrien// The LLVM Compiler Infrastructure 468349Sobrien// 568349Sobrien// This file is distributed under the University of Illinois Open Source 6139368Sobrien// License. See LICENSE.TXT for details. 768349Sobrien// 868349Sobrien//===----------------------------------------------------------------------===// 9139368Sobrien// 1084685Sobrien// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a 1184685Sobrien// simple alias analysis implemented in terms of ScalarEvolution queries. 12139368Sobrien// 13139368Sobrien// This differs from traditional loop dependence analysis in that it tests 14133359Sobrien// for dependencies within a single iteration of a loop, rather than 15133359Sobrien// dependencies between different iterations. 16133359Sobrien// 17133359Sobrien// ScalarEvolution has a more complete understanding of pointer arithmetic 18133359Sobrien// than BasicAliasAnalysis' collection of ad-hoc analyses. 19133359Sobrien// 20133359Sobrien//===----------------------------------------------------------------------===// 21133359Sobrien 22110949Sobrien#include "llvm/Analysis/Passes.h" 23110949Sobrien#include "llvm/Analysis/AliasAnalysis.h" 24133359Sobrien#include "llvm/Analysis/ScalarEvolutionExpressions.h" 25133359Sobrien#include "llvm/Pass.h" 26133359Sobrienusing namespace llvm; 27133359Sobrien 28133359Sobriennamespace { 29133359Sobrien /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 30133359Sobrien /// implementation that uses ScalarEvolution to answer queries. 31133359Sobrien class ScalarEvolutionAliasAnalysis : public FunctionPass, 32133359Sobrien public AliasAnalysis { 33139368Sobrien ScalarEvolution *SE; 34139368Sobrien 35139368Sobrien public: 36133359Sobrien static char ID; // Class identification, replacement for typeinfo 37133359Sobrien ScalarEvolutionAliasAnalysis() : FunctionPass(ID), SE(0) { 38133359Sobrien initializeScalarEvolutionAliasAnalysisPass( 39133359Sobrien *PassRegistry::getPassRegistry()); 40133359Sobrien } 41133359Sobrien 42133359Sobrien /// getAdjustedAnalysisPointer - This method is used when a pass implements 43103373Sobrien /// an analysis interface through multiple inheritance. If needed, it 44103373Sobrien /// should override this to adjust the this pointer as needed for the 45133359Sobrien /// specified pass info. 4680588Sobrien virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 4780588Sobrien if (PI == &AliasAnalysis::ID) 48133359Sobrien return (AliasAnalysis*)this; 49133359Sobrien return this; 50133359Sobrien } 51133359Sobrien 52133359Sobrien private: 53133359Sobrien virtual void getAnalysisUsage(AnalysisUsage &AU) const; 54133359Sobrien virtual bool runOnFunction(Function &F); 5568349Sobrien virtual AliasResult alias(const Location &LocA, const Location &LocB); 5668349Sobrien 57133359Sobrien Value *GetBaseValue(const SCEV *S); 58133359Sobrien }; 5968349Sobrien} // End of anonymous namespace 60133359Sobrien 61133359Sobrien// Register this pass... 62103373Sobrienchar ScalarEvolutionAliasAnalysis::ID = 0; 63133359SobrienINITIALIZE_AG_PASS_BEGIN(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 64133359Sobrien "ScalarEvolution-based Alias Analysis", false, true, false) 65103373SobrienINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 66133359SobrienINITIALIZE_AG_PASS_END(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 67133359Sobrien "ScalarEvolution-based Alias Analysis", false, true, false) 68110949Sobrien 69133359SobrienFunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 70133359Sobrien return new ScalarEvolutionAliasAnalysis(); 71133359Sobrien} 7268349Sobrien 73133359Sobrienvoid 7480588SobrienScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 7580588Sobrien AU.addRequiredTransitive<ScalarEvolution>(); 76133359Sobrien AU.setPreservesAll(); 77103373Sobrien AliasAnalysis::getAnalysisUsage(AU); 78103373Sobrien} 79133359Sobrien 80103373Sobrienbool 81103373SobrienScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 82133359Sobrien InitializeAliasAnalysis(this); 83133359Sobrien SE = &getAnalysis<ScalarEvolution>(); 84133359Sobrien return false; 85133359Sobrien} 86133359Sobrien 87133359Sobrien/// GetBaseValue - Given an expression, try to find a 88139368Sobrien/// base value. Return null is none was found. 89139368SobrienValue * 90139368SobrienScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 91133359Sobrien if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 92133359Sobrien // In an addrec, assume that the base will be in the start, rather 93133359Sobrien // than the step. 94133359Sobrien return GetBaseValue(AR->getStart()); 95133359Sobrien } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 96133359Sobrien // If there's a pointer operand, it'll be sorted at the end of the list. 97133359Sobrien const SCEV *Last = A->getOperand(A->getNumOperands()-1); 9868349Sobrien if (Last->getType()->isPointerTy()) 9968349Sobrien return GetBaseValue(Last); 100133359Sobrien } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 101133359Sobrien // This is a leaf node. 102103373Sobrien return U->getValue(); 103133359Sobrien } 104133359Sobrien // No Identified object found. 105133359Sobrien return 0; 106133359Sobrien} 107133359Sobrien 108133359SobrienAliasAnalysis::AliasResult 109133359SobrienScalarEvolutionAliasAnalysis::alias(const Location &LocA, 110133359Sobrien const Location &LocB) { 111133359Sobrien // If either of the memory references is empty, it doesn't matter what the 112133359Sobrien // pointer values are. This allows the code below to ignore this special 113133359Sobrien // case. 114133359Sobrien if (LocA.Size == 0 || LocB.Size == 0) 115133359Sobrien return NoAlias; 116133359Sobrien 117133359Sobrien // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 118133359Sobrien const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr)); 119133359Sobrien const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr)); 120133359Sobrien 121133359Sobrien // If they evaluate to the same expression, it's a MustAlias. 122133359Sobrien if (AS == BS) return MustAlias; 12368349Sobrien 12468349Sobrien // If something is known about the difference between the two addresses, 12568349Sobrien // see if it's enough to prove a NoAlias. 126133359Sobrien if (SE->getEffectiveSCEVType(AS->getType()) == 127133359Sobrien SE->getEffectiveSCEVType(BS->getType())) { 128133359Sobrien unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 129133359Sobrien APInt ASizeInt(BitWidth, LocA.Size); 130133359Sobrien APInt BSizeInt(BitWidth, LocB.Size); 131133359Sobrien 132133359Sobrien // Compute the difference between the two pointers. 133133359Sobrien const SCEV *BA = SE->getMinusSCEV(BS, AS); 134133359Sobrien 135133359Sobrien // Test whether the difference is known to be great enough that memory of 136133359Sobrien // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 137133359Sobrien // are non-zero, which is special-cased above. 138133359Sobrien if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) && 139133359Sobrien (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax())) 140133359Sobrien return NoAlias; 141139368Sobrien 142139368Sobrien // Folding the subtraction while preserving range information can be tricky 143139368Sobrien // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS 144139368Sobrien // and try again to see if things fold better that way. 145139368Sobrien 146139368Sobrien // Compute the difference between the two pointers. 147139368Sobrien const SCEV *AB = SE->getMinusSCEV(AS, BS); 148139368Sobrien 149139368Sobrien // Test whether the difference is known to be great enough that memory of 150139368Sobrien // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 151139368Sobrien // are non-zero, which is special-cased above. 152139368Sobrien if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) && 153133359Sobrien (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax())) 154133359Sobrien return NoAlias; 155133359Sobrien } 156133359Sobrien 157133359Sobrien // If ScalarEvolution can find an underlying object, form a new query. 158133359Sobrien // The correctness of this depends on ScalarEvolution not recognizing 15968349Sobrien // inttoptr and ptrtoint operators. 16068349Sobrien Value *AO = GetBaseValue(AS); 16168349Sobrien Value *BO = GetBaseValue(BS); 162103373Sobrien if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) 163103373Sobrien if (alias(Location(AO ? AO : LocA.Ptr, 164103373Sobrien AO ? +UnknownSize : LocA.Size, 165103373Sobrien AO ? 0 : LocA.TBAATag), 166103373Sobrien Location(BO ? BO : LocB.Ptr, 167103373Sobrien BO ? +UnknownSize : LocB.Size, 168133359Sobrien BO ? 0 : LocB.TBAATag)) == NoAlias) 169133359Sobrien return NoAlias; 170133359Sobrien 171139368Sobrien // Forward the query to the next analysis. 172139368Sobrien return AliasAnalysis::alias(LocA, LocB); 173139368Sobrien} 174133359Sobrien