1198090Srdivacky//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===// 2198090Srdivacky// 3198090Srdivacky// The LLVM Compiler Infrastructure 4198090Srdivacky// 5198090Srdivacky// This file is distributed under the University of Illinois Open Source 6198090Srdivacky// License. See LICENSE.TXT for details. 7198090Srdivacky// 8198090Srdivacky//===----------------------------------------------------------------------===// 9198090Srdivacky// 10198090Srdivacky// This file defines the ScalarEvolutionAliasAnalysis pass, which implements a 11198090Srdivacky// simple alias analysis implemented in terms of ScalarEvolution queries. 12198090Srdivacky// 13204642Srdivacky// This differs from traditional loop dependence analysis in that it tests 14204642Srdivacky// for dependencies within a single iteration of a loop, rather than 15210299Sed// dependencies between different iterations. 16204642Srdivacky// 17198090Srdivacky// ScalarEvolution has a more complete understanding of pointer arithmetic 18198090Srdivacky// than BasicAliasAnalysis' collection of ad-hoc analyses. 19198090Srdivacky// 20198090Srdivacky//===----------------------------------------------------------------------===// 21198090Srdivacky 22252723Sdim#include "llvm/Analysis/Passes.h" 23198090Srdivacky#include "llvm/Analysis/AliasAnalysis.h" 24198090Srdivacky#include "llvm/Analysis/ScalarEvolutionExpressions.h" 25198090Srdivacky#include "llvm/Pass.h" 26198090Srdivackyusing namespace llvm; 27198090Srdivacky 28198090Srdivackynamespace { 29198090Srdivacky /// ScalarEvolutionAliasAnalysis - This is a simple alias analysis 30198090Srdivacky /// implementation that uses ScalarEvolution to answer queries. 31198892Srdivacky class ScalarEvolutionAliasAnalysis : public FunctionPass, 32198892Srdivacky public AliasAnalysis { 33198090Srdivacky ScalarEvolution *SE; 34198090Srdivacky 35198090Srdivacky public: 36198090Srdivacky static char ID; // Class identification, replacement for typeinfo 37218893Sdim ScalarEvolutionAliasAnalysis() : FunctionPass(ID), SE(0) { 38218893Sdim initializeScalarEvolutionAliasAnalysisPass( 39218893Sdim *PassRegistry::getPassRegistry()); 40218893Sdim } 41198090Srdivacky 42202878Srdivacky /// getAdjustedAnalysisPointer - This method is used when a pass implements 43202878Srdivacky /// an analysis interface through multiple inheritance. If needed, it 44202878Srdivacky /// should override this to adjust the this pointer as needed for the 45202878Srdivacky /// specified pass info. 46212904Sdim virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 47212904Sdim if (PI == &AliasAnalysis::ID) 48202878Srdivacky return (AliasAnalysis*)this; 49202878Srdivacky return this; 50202878Srdivacky } 51204642Srdivacky 52198090Srdivacky private: 53198090Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const; 54198090Srdivacky virtual bool runOnFunction(Function &F); 55218893Sdim virtual AliasResult alias(const Location &LocA, const Location &LocB); 56198090Srdivacky 57198892Srdivacky Value *GetBaseValue(const SCEV *S); 58198090Srdivacky }; 59198090Srdivacky} // End of anonymous namespace 60198090Srdivacky 61198090Srdivacky// Register this pass... 62198090Srdivackychar ScalarEvolutionAliasAnalysis::ID = 0; 63218893SdimINITIALIZE_AG_PASS_BEGIN(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 64218893Sdim "ScalarEvolution-based Alias Analysis", false, true, false) 65218893SdimINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 66218893SdimINITIALIZE_AG_PASS_END(ScalarEvolutionAliasAnalysis, AliasAnalysis, "scev-aa", 67218893Sdim "ScalarEvolution-based Alias Analysis", false, true, false) 68198090Srdivacky 69198090SrdivackyFunctionPass *llvm::createScalarEvolutionAliasAnalysisPass() { 70198090Srdivacky return new ScalarEvolutionAliasAnalysis(); 71198090Srdivacky} 72198090Srdivacky 73198090Srdivackyvoid 74198090SrdivackyScalarEvolutionAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 75198090Srdivacky AU.addRequiredTransitive<ScalarEvolution>(); 76198090Srdivacky AU.setPreservesAll(); 77198090Srdivacky AliasAnalysis::getAnalysisUsage(AU); 78198090Srdivacky} 79198090Srdivacky 80198090Srdivackybool 81198090SrdivackyScalarEvolutionAliasAnalysis::runOnFunction(Function &F) { 82198090Srdivacky InitializeAliasAnalysis(this); 83198090Srdivacky SE = &getAnalysis<ScalarEvolution>(); 84198090Srdivacky return false; 85198090Srdivacky} 86198090Srdivacky 87198892Srdivacky/// GetBaseValue - Given an expression, try to find a 88198892Srdivacky/// base value. Return null is none was found. 89198090SrdivackyValue * 90198892SrdivackyScalarEvolutionAliasAnalysis::GetBaseValue(const SCEV *S) { 91198090Srdivacky if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 92198090Srdivacky // In an addrec, assume that the base will be in the start, rather 93198090Srdivacky // than the step. 94198892Srdivacky return GetBaseValue(AR->getStart()); 95198090Srdivacky } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 96198090Srdivacky // If there's a pointer operand, it'll be sorted at the end of the list. 97198090Srdivacky const SCEV *Last = A->getOperand(A->getNumOperands()-1); 98204642Srdivacky if (Last->getType()->isPointerTy()) 99198892Srdivacky return GetBaseValue(Last); 100198090Srdivacky } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 101198892Srdivacky // This is a leaf node. 102198892Srdivacky return U->getValue(); 103198090Srdivacky } 104198090Srdivacky // No Identified object found. 105198090Srdivacky return 0; 106198090Srdivacky} 107198090Srdivacky 108198090SrdivackyAliasAnalysis::AliasResult 109218893SdimScalarEvolutionAliasAnalysis::alias(const Location &LocA, 110218893Sdim const Location &LocB) { 111210299Sed // If either of the memory references is empty, it doesn't matter what the 112210299Sed // pointer values are. This allows the code below to ignore this special 113210299Sed // case. 114218893Sdim if (LocA.Size == 0 || LocB.Size == 0) 115210299Sed return NoAlias; 116210299Sed 117198090Srdivacky // This is ScalarEvolutionAliasAnalysis. Get the SCEVs! 118218893Sdim const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr)); 119218893Sdim const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr)); 120198090Srdivacky 121198090Srdivacky // If they evaluate to the same expression, it's a MustAlias. 122198090Srdivacky if (AS == BS) return MustAlias; 123198090Srdivacky 124198090Srdivacky // If something is known about the difference between the two addresses, 125198090Srdivacky // see if it's enough to prove a NoAlias. 126198090Srdivacky if (SE->getEffectiveSCEVType(AS->getType()) == 127198090Srdivacky SE->getEffectiveSCEVType(BS->getType())) { 128198090Srdivacky unsigned BitWidth = SE->getTypeSizeInBits(AS->getType()); 129218893Sdim APInt ASizeInt(BitWidth, LocA.Size); 130218893Sdim APInt BSizeInt(BitWidth, LocB.Size); 131210299Sed 132210299Sed // Compute the difference between the two pointers. 133198090Srdivacky const SCEV *BA = SE->getMinusSCEV(BS, AS); 134210299Sed 135210299Sed // Test whether the difference is known to be great enough that memory of 136210299Sed // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 137210299Sed // are non-zero, which is special-cased above. 138210299Sed if (ASizeInt.ule(SE->getUnsignedRange(BA).getUnsignedMin()) && 139210299Sed (-BSizeInt).uge(SE->getUnsignedRange(BA).getUnsignedMax())) 140210299Sed return NoAlias; 141210299Sed 142210299Sed // Folding the subtraction while preserving range information can be tricky 143210299Sed // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS 144210299Sed // and try again to see if things fold better that way. 145210299Sed 146210299Sed // Compute the difference between the two pointers. 147210299Sed const SCEV *AB = SE->getMinusSCEV(AS, BS); 148210299Sed 149210299Sed // Test whether the difference is known to be great enough that memory of 150210299Sed // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 151210299Sed // are non-zero, which is special-cased above. 152210299Sed if (BSizeInt.ule(SE->getUnsignedRange(AB).getUnsignedMin()) && 153210299Sed (-ASizeInt).uge(SE->getUnsignedRange(AB).getUnsignedMax())) 154210299Sed return NoAlias; 155198090Srdivacky } 156198090Srdivacky 157198090Srdivacky // If ScalarEvolution can find an underlying object, form a new query. 158198090Srdivacky // The correctness of this depends on ScalarEvolution not recognizing 159198090Srdivacky // inttoptr and ptrtoint operators. 160198892Srdivacky Value *AO = GetBaseValue(AS); 161198892Srdivacky Value *BO = GetBaseValue(BS); 162218893Sdim if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) 163218893Sdim if (alias(Location(AO ? AO : LocA.Ptr, 164218893Sdim AO ? +UnknownSize : LocA.Size, 165218893Sdim AO ? 0 : LocA.TBAATag), 166218893Sdim Location(BO ? BO : LocB.Ptr, 167218893Sdim BO ? +UnknownSize : LocB.Size, 168218893Sdim BO ? 0 : LocB.TBAATag)) == NoAlias) 169198090Srdivacky return NoAlias; 170198090Srdivacky 171198090Srdivacky // Forward the query to the next analysis. 172218893Sdim return AliasAnalysis::alias(LocA, LocB); 173198090Srdivacky} 174