ScopedNoAliasAA.cpp revision 277718
1226586Sdim//===- ScopedNoAliasAA.cpp - Scoped No-Alias Alias Analysis ---------------===// 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10226586Sdim// This file defines the ScopedNoAlias alias-analysis pass, which implements 11226586Sdim// metadata-based scoped no-alias support. 12226586Sdim// 13226586Sdim// Alias-analysis scopes are defined by an id (which can be a string or some 14239462Sdim// other metadata node), a domain node, and an optional descriptive string. 15226586Sdim// A domain is defined by an id (which can be a string or some other metadata 16226586Sdim// node), and an optional descriptive string. 17226586Sdim// 18226586Sdim// !dom0 = metadata !{ metadata !"domain of foo()" } 19226586Sdim// !scope1 = metadata !{ metadata !scope1, metadata !dom0, metadata !"scope 1" } 20226586Sdim// !scope2 = metadata !{ metadata !scope2, metadata !dom0, metadata !"scope 2" } 21226586Sdim// 22226586Sdim// Loads and stores can be tagged with an alias-analysis scope, and also, with 23226586Sdim// a noalias tag for a specific scope: 24239462Sdim// 25226586Sdim// ... = load %ptr1, !alias.scope !{ !scope1 } 26226586Sdim// ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 } 27226586Sdim// 28226586Sdim// When evaluating an aliasing query, if one of the instructions is associated 29226586Sdim// has a set of noalias scopes in some domain that is superset of the alias 30226586Sdim// scopes in that domain of some other instruction, then the two memory 31226586Sdim// accesses are assumed not to alias. 32226586Sdim// 33226586Sdim//===----------------------------------------------------------------------===// 34234353Sdim 35234353Sdim#include "llvm/ADT/SmallPtrSet.h" 36234353Sdim#include "llvm/Analysis/AliasAnalysis.h" 37226586Sdim#include "llvm/Analysis/Passes.h" 38226586Sdim#include "llvm/IR/Constants.h" 39226586Sdim#include "llvm/IR/LLVMContext.h" 40239462Sdim#include "llvm/IR/Metadata.h" 41226586Sdim#include "llvm/IR/Module.h" 42226586Sdim#include "llvm/Pass.h" 43226586Sdim#include "llvm/Support/CommandLine.h" 44243830Sdimusing namespace llvm; 45243830Sdim 46243830Sdim// A handy option for disabling scoped no-alias functionality. The same effect 47226586Sdim// can also be achieved by stripping the associated metadata tags from IR, but 48226586Sdim// this option is sometimes more convenient. 49226586Sdimstatic cl::opt<bool> 50226586SdimEnableScopedNoAlias("enable-scoped-noalias", cl::init(true)); 51226586Sdim 52226586Sdimnamespace { 53226586Sdim/// AliasScopeNode - This is a simple wrapper around an MDNode which provides 54226586Sdim/// a higher-level interface by hiding the details of how alias analysis 55226586Sdim/// information is encoded in its operands. 56226586Sdimclass AliasScopeNode { 57226586Sdim const MDNode *Node; 58226586Sdim 59226586Sdimpublic: 60226586Sdim AliasScopeNode() : Node(0) {} 61226586Sdim explicit AliasScopeNode(const MDNode *N) : Node(N) {} 62226586Sdim 63226586Sdim /// getNode - Get the MDNode for this AliasScopeNode. 64226586Sdim const MDNode *getNode() const { return Node; } 65226586Sdim 66226586Sdim /// getDomain - Get the MDNode for this AliasScopeNode's domain. 67226586Sdim const MDNode *getDomain() const { 68226586Sdim if (Node->getNumOperands() < 2) 69226586Sdim return nullptr; 70226586Sdim return dyn_cast_or_null<MDNode>(Node->getOperand(1)); 71226586Sdim } 72226586Sdim}; 73226586Sdim 74226586Sdim/// ScopedNoAliasAA - This is a simple alias analysis 75226586Sdim/// implementation that uses scoped-noalias metadata to answer queries. 76234353Sdimclass ScopedNoAliasAA : public ImmutablePass, public AliasAnalysis { 77234353Sdimpublic: 78234353Sdim static char ID; // Class identification, replacement for typeinfo 79234353Sdim ScopedNoAliasAA() : ImmutablePass(ID) { 80234353Sdim initializeScopedNoAliasAAPass(*PassRegistry::getPassRegistry()); 81234353Sdim } 82234353Sdim 83234353Sdim void initializePass() override { InitializeAliasAnalysis(this); } 84234353Sdim 85226586Sdim /// getAdjustedAnalysisPointer - This method is used when a pass implements 86226586Sdim /// an analysis interface through multiple inheritance. If needed, it 87226586Sdim /// should override this to adjust the this pointer as needed for the 88226586Sdim /// specified pass info. 89226586Sdim void *getAdjustedAnalysisPointer(const void *PI) override { 90226586Sdim if (PI == &AliasAnalysis::ID) 91226586Sdim return (AliasAnalysis*)this; 92239462Sdim return this; 93239462Sdim } 94226586Sdim 95226586Sdimprotected: 96226586Sdim bool mayAliasInScopes(const MDNode *Scopes, const MDNode *NoAlias) const; 97226586Sdim void collectMDInDomain(const MDNode *List, const MDNode *Domain, 98226586Sdim SmallPtrSetImpl<const MDNode *> &Nodes) const; 99226586Sdim 100243830Sdimprivate: 101243830Sdim void getAnalysisUsage(AnalysisUsage &AU) const override; 102243830Sdim AliasResult alias(const Location &LocA, const Location &LocB) override; 103243830Sdim bool pointsToConstantMemory(const Location &Loc, bool OrLocal) override; 104243830Sdim ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override; 105243830Sdim ModRefBehavior getModRefBehavior(const Function *F) override; 106243830Sdim ModRefResult getModRefInfo(ImmutableCallSite CS, 107243830Sdim const Location &Loc) override; 108243830Sdim ModRefResult getModRefInfo(ImmutableCallSite CS1, 109243830Sdim ImmutableCallSite CS2) override; 110243830Sdim}; 111243830Sdim} // End of anonymous namespace 112226586Sdim 113226586Sdim// Register this pass... 114226586Sdimchar ScopedNoAliasAA::ID = 0; 115226586SdimINITIALIZE_AG_PASS(ScopedNoAliasAA, AliasAnalysis, "scoped-noalias", 116226586Sdim "Scoped NoAlias Alias Analysis", false, true, false) 117226586Sdim 118226586SdimImmutablePass *llvm::createScopedNoAliasAAPass() { 119226586Sdim return new ScopedNoAliasAA(); 120226586Sdim} 121226586Sdim 122226586Sdimvoid 123226586SdimScopedNoAliasAA::getAnalysisUsage(AnalysisUsage &AU) const { 124226586Sdim AU.setPreservesAll(); 125243830Sdim AliasAnalysis::getAnalysisUsage(AU); 126243830Sdim} 127243830Sdim 128243830Sdimvoid 129243830SdimScopedNoAliasAA::collectMDInDomain(const MDNode *List, const MDNode *Domain, 130243830Sdim SmallPtrSetImpl<const MDNode *> &Nodes) const { 131243830Sdim for (unsigned i = 0, ie = List->getNumOperands(); i != ie; ++i) 132243830Sdim if (const MDNode *MD = dyn_cast<MDNode>(List->getOperand(i))) 133243830Sdim if (AliasScopeNode(MD).getDomain() == Domain) 134243830Sdim Nodes.insert(MD); 135243830Sdim} 136243830Sdim 137243830Sdimbool 138243830SdimScopedNoAliasAA::mayAliasInScopes(const MDNode *Scopes, 139243830Sdim const MDNode *NoAlias) const { 140243830Sdim if (!Scopes || !NoAlias) 141243830Sdim return true; 142243830Sdim 143243830Sdim // Collect the set of scope domains relevant to the noalias scopes. 144243830Sdim SmallPtrSet<const MDNode *, 16> Domains; 145243830Sdim for (unsigned i = 0, ie = NoAlias->getNumOperands(); i != ie; ++i) 146243830Sdim if (const MDNode *NAMD = dyn_cast<MDNode>(NoAlias->getOperand(i))) 147243830Sdim if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain()) 148243830Sdim Domains.insert(Domain); 149243830Sdim 150243830Sdim // We alias unless, for some domain, the set of noalias scopes in that domain 151243830Sdim // is a superset of the set of alias scopes in that domain. 152243830Sdim for (const MDNode *Domain : Domains) { 153243830Sdim SmallPtrSet<const MDNode *, 16> NANodes, ScopeNodes; 154243830Sdim collectMDInDomain(NoAlias, Domain, NANodes); 155243830Sdim collectMDInDomain(Scopes, Domain, ScopeNodes); 156243830Sdim if (!ScopeNodes.size()) 157243830Sdim continue; 158243830Sdim 159243830Sdim // To not alias, all of the nodes in ScopeNodes must be in NANodes. 160243830Sdim bool FoundAll = true; 161243830Sdim for (const MDNode *SMD : ScopeNodes) 162243830Sdim if (!NANodes.count(SMD)) { 163243830Sdim FoundAll = false; 164243830Sdim break; 165243830Sdim } 166243830Sdim 167243830Sdim if (FoundAll) 168243830Sdim return false; 169243830Sdim } 170243830Sdim 171243830Sdim return true; 172243830Sdim} 173243830Sdim 174243830SdimAliasAnalysis::AliasResult 175243830SdimScopedNoAliasAA::alias(const Location &LocA, const Location &LocB) { 176243830Sdim if (!EnableScopedNoAlias) 177243830Sdim return AliasAnalysis::alias(LocA, LocB); 178243830Sdim 179243830Sdim // Get the attached MDNodes. 180243830Sdim const MDNode *AScopes = LocA.AATags.Scope, 181243830Sdim *BScopes = LocB.AATags.Scope; 182243830Sdim 183243830Sdim const MDNode *ANoAlias = LocA.AATags.NoAlias, 184243830Sdim *BNoAlias = LocB.AATags.NoAlias; 185243830Sdim 186243830Sdim if (!mayAliasInScopes(AScopes, BNoAlias)) 187243830Sdim return NoAlias; 188243830Sdim 189243830Sdim if (!mayAliasInScopes(BScopes, ANoAlias)) 190243830Sdim return NoAlias; 191243830Sdim 192243830Sdim // If they may alias, chain to the next AliasAnalysis. 193243830Sdim return AliasAnalysis::alias(LocA, LocB); 194243830Sdim} 195243830Sdim 196243830Sdimbool ScopedNoAliasAA::pointsToConstantMemory(const Location &Loc, 197243830Sdim bool OrLocal) { 198243830Sdim return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 199243830Sdim} 200243830Sdim 201243830SdimAliasAnalysis::ModRefBehavior 202243830SdimScopedNoAliasAA::getModRefBehavior(ImmutableCallSite CS) { 203243830Sdim return AliasAnalysis::getModRefBehavior(CS); 204226586Sdim} 205243830Sdim 206234353SdimAliasAnalysis::ModRefBehavior 207243830SdimScopedNoAliasAA::getModRefBehavior(const Function *F) { 208226586Sdim return AliasAnalysis::getModRefBehavior(F); 209226586Sdim} 210226586Sdim 211226586SdimAliasAnalysis::ModRefResult 212226586SdimScopedNoAliasAA::getModRefInfo(ImmutableCallSite CS, const Location &Loc) { 213226586Sdim if (!EnableScopedNoAlias) 214243830Sdim return AliasAnalysis::getModRefInfo(CS, Loc); 215226586Sdim 216 if (!mayAliasInScopes(Loc.AATags.Scope, CS.getInstruction()->getMetadata( 217 LLVMContext::MD_noalias))) 218 return NoModRef; 219 220 if (!mayAliasInScopes( 221 CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), 222 Loc.AATags.NoAlias)) 223 return NoModRef; 224 225 return AliasAnalysis::getModRefInfo(CS, Loc); 226} 227 228AliasAnalysis::ModRefResult 229ScopedNoAliasAA::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 230 if (!EnableScopedNoAlias) 231 return AliasAnalysis::getModRefInfo(CS1, CS2); 232 233 if (!mayAliasInScopes( 234 CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), 235 CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias))) 236 return NoModRef; 237 238 if (!mayAliasInScopes( 239 CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), 240 CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias))) 241 return NoModRef; 242 243 return AliasAnalysis::getModRefInfo(CS1, CS2); 244} 245 246