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/ScalarEvolutionAliasAnalysis.h" 23#include "llvm/Analysis/TargetLibraryInfo.h" 24using namespace llvm; 25 26AliasResult SCEVAAResult::alias(const MemoryLocation &LocA, 27 const MemoryLocation &LocB) { 28 // If either of the memory references is empty, it doesn't matter what the 29 // pointer values are. This allows the code below to ignore this special 30 // case. 31 if (LocA.Size == 0 || LocB.Size == 0) 32 return NoAlias; 33 34 // This is SCEVAAResult. Get the SCEVs! 35 const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr)); 36 const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr)); 37 38 // If they evaluate to the same expression, it's a MustAlias. 39 if (AS == BS) 40 return MustAlias; 41 42 // If something is known about the difference between the two addresses, 43 // see if it's enough to prove a NoAlias. 44 if (SE.getEffectiveSCEVType(AS->getType()) == 45 SE.getEffectiveSCEVType(BS->getType())) { 46 unsigned BitWidth = SE.getTypeSizeInBits(AS->getType()); 47 APInt ASizeInt(BitWidth, LocA.Size); 48 APInt BSizeInt(BitWidth, LocB.Size); 49 50 // Compute the difference between the two pointers. 51 const SCEV *BA = SE.getMinusSCEV(BS, AS); 52 53 // Test whether the difference is known to be great enough that memory of 54 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 55 // are non-zero, which is special-cased above. 56 if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) && 57 (-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax())) 58 return NoAlias; 59 60 // Folding the subtraction while preserving range information can be tricky 61 // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS 62 // and try again to see if things fold better that way. 63 64 // Compute the difference between the two pointers. 65 const SCEV *AB = SE.getMinusSCEV(AS, BS); 66 67 // Test whether the difference is known to be great enough that memory of 68 // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt 69 // are non-zero, which is special-cased above. 70 if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) && 71 (-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax())) 72 return NoAlias; 73 } 74 75 // If ScalarEvolution can find an underlying object, form a new query. 76 // The correctness of this depends on ScalarEvolution not recognizing 77 // inttoptr and ptrtoint operators. 78 Value *AO = GetBaseValue(AS); 79 Value *BO = GetBaseValue(BS); 80 if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr)) 81 if (alias(MemoryLocation(AO ? AO : LocA.Ptr, 82 AO ? +MemoryLocation::UnknownSize : LocA.Size, 83 AO ? AAMDNodes() : LocA.AATags), 84 MemoryLocation(BO ? BO : LocB.Ptr, 85 BO ? +MemoryLocation::UnknownSize : LocB.Size, 86 BO ? AAMDNodes() : LocB.AATags)) == NoAlias) 87 return NoAlias; 88 89 // Forward the query to the next analysis. 90 return AAResultBase::alias(LocA, LocB); 91} 92 93/// Given an expression, try to find a base value. 94/// 95/// Returns null if none was found. 96Value *SCEVAAResult::GetBaseValue(const SCEV *S) { 97 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 98 // In an addrec, assume that the base will be in the start, rather 99 // than the step. 100 return GetBaseValue(AR->getStart()); 101 } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 102 // If there's a pointer operand, it'll be sorted at the end of the list. 103 const SCEV *Last = A->getOperand(A->getNumOperands() - 1); 104 if (Last->getType()->isPointerTy()) 105 return GetBaseValue(Last); 106 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 107 // This is a leaf node. 108 return U->getValue(); 109 } 110 // No Identified object found. 111 return nullptr; 112} 113 114SCEVAAResult SCEVAA::run(Function &F, AnalysisManager<Function> *AM) { 115 return SCEVAAResult(AM->getResult<TargetLibraryAnalysis>(F), 116 AM->getResult<ScalarEvolutionAnalysis>(F)); 117} 118 119char SCEVAA::PassID; 120 121char SCEVAAWrapperPass::ID = 0; 122INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa", 123 "ScalarEvolution-based Alias Analysis", false, true) 124INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 125INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 126INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa", 127 "ScalarEvolution-based Alias Analysis", false, true) 128 129FunctionPass *llvm::createSCEVAAWrapperPass() { 130 return new SCEVAAWrapperPass(); 131} 132 133SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) { 134 initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry()); 135} 136 137bool SCEVAAWrapperPass::runOnFunction(Function &F) { 138 Result.reset( 139 new SCEVAAResult(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), 140 getAnalysis<ScalarEvolutionWrapperPass>().getSE())); 141 return false; 142} 143 144void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 145 AU.setPreservesAll(); 146 AU.addRequired<ScalarEvolutionWrapperPass>(); 147 AU.addRequired<TargetLibraryInfoWrapperPass>(); 148} 149