1 //===- ScopedNoAliasAA.cpp - Scoped No-Alias 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 ScopedNoAlias alias-analysis pass, which implements 11 // metadata-based scoped no-alias support. 12 // 13 // Alias-analysis scopes are defined by an id (which can be a string or some 14 // other metadata node), a domain node, and an optional descriptive string. 15 // A domain is defined by an id (which can be a string or some other metadata 16 // node), and an optional descriptive string. 17 // 18 // !dom0 = metadata !{ metadata !"domain of foo()" } 19 // !scope1 = metadata !{ metadata !scope1, metadata !dom0, metadata !"scope 1" } 20 // !scope2 = metadata !{ metadata !scope2, metadata !dom0, metadata !"scope 2" } 21 // 22 // Loads and stores can be tagged with an alias-analysis scope, and also, with 23 // a noalias tag for a specific scope: 24 // 25 // ... = load %ptr1, !alias.scope !{ !scope1 } 26 // ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 } 27 // 28 // When evaluating an aliasing query, if one of the instructions is associated 29 // has a set of noalias scopes in some domain that is a superset of the alias 30 // scopes in that domain of some other instruction, then the two memory 31 // accesses are assumed not to alias. 32 // 33 //===----------------------------------------------------------------------===// 34 35 #include "llvm/Analysis/ScopedNoAliasAA.h" 36 #include "llvm/ADT/SmallPtrSet.h" 37 #include "llvm/IR/Constants.h" 38 #include "llvm/IR/LLVMContext.h" 39 #include "llvm/IR/Metadata.h" 40 #include "llvm/IR/Module.h" 41 #include "llvm/Pass.h" 42 #include "llvm/Support/CommandLine.h" 43 44 using namespace llvm; 45 46 // A handy option for disabling scoped no-alias functionality. The same effect 47 // can also be achieved by stripping the associated metadata tags from IR, but 48 // this option is sometimes more convenient. 49 static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias", 50 cl::init(true)); 51 52 namespace { 53 /// This is a simple wrapper around an MDNode which provides a higher-level 54 /// interface by hiding the details of how alias analysis information is encoded 55 /// in its operands. 56 class AliasScopeNode { 57 const MDNode *Node; 58 59 public: 60 AliasScopeNode() : Node(nullptr) {} 61 explicit AliasScopeNode(const MDNode *N) : Node(N) {} 62 63 /// Get the MDNode for this AliasScopeNode. 64 const MDNode *getNode() const { return Node; } 65 66 /// Get the MDNode for this AliasScopeNode's domain. 67 const MDNode *getDomain() const { 68 if (Node->getNumOperands() < 2) 69 return nullptr; 70 return dyn_cast_or_null<MDNode>(Node->getOperand(1)); 71 } 72 }; 73 } // end of anonymous namespace 74 75 AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA, 76 const MemoryLocation &LocB) { 77 if (!EnableScopedNoAlias) 78 return AAResultBase::alias(LocA, LocB); 79 80 // Get the attached MDNodes. 81 const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope; 82 83 const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias; 84 85 if (!mayAliasInScopes(AScopes, BNoAlias)) 86 return NoAlias; 87 88 if (!mayAliasInScopes(BScopes, ANoAlias)) 89 return NoAlias; 90 91 // If they may alias, chain to the next AliasAnalysis. 92 return AAResultBase::alias(LocA, LocB); 93 } 94 95 ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS, 96 const MemoryLocation &Loc) { 97 if (!EnableScopedNoAlias) 98 return AAResultBase::getModRefInfo(CS, Loc); 99 100 if (!mayAliasInScopes(Loc.AATags.Scope, CS.getInstruction()->getMetadata( 101 LLVMContext::MD_noalias))) 102 return MRI_NoModRef; 103 104 if (!mayAliasInScopes( 105 CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), 106 Loc.AATags.NoAlias)) 107 return MRI_NoModRef; 108 109 return AAResultBase::getModRefInfo(CS, Loc); 110 } 111 112 ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS1, 113 ImmutableCallSite CS2) { 114 if (!EnableScopedNoAlias) 115 return AAResultBase::getModRefInfo(CS1, CS2); 116 117 if (!mayAliasInScopes( 118 CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), 119 CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias))) 120 return MRI_NoModRef; 121 122 if (!mayAliasInScopes( 123 CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), 124 CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias))) 125 return MRI_NoModRef; 126 127 return AAResultBase::getModRefInfo(CS1, CS2); 128 } 129 130 void ScopedNoAliasAAResult::collectMDInDomain( 131 const MDNode *List, const MDNode *Domain, 132 SmallPtrSetImpl<const MDNode *> &Nodes) const { 133 for (const MDOperand &MDOp : List->operands()) 134 if (const MDNode *MD = dyn_cast<MDNode>(MDOp)) 135 if (AliasScopeNode(MD).getDomain() == Domain) 136 Nodes.insert(MD); 137 } 138 139 bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes, 140 const MDNode *NoAlias) const { 141 if (!Scopes || !NoAlias) 142 return true; 143 144 // Collect the set of scope domains relevant to the noalias scopes. 145 SmallPtrSet<const MDNode *, 16> Domains; 146 for (const MDOperand &MDOp : NoAlias->operands()) 147 if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp)) 148 if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain()) 149 Domains.insert(Domain); 150 151 // We alias unless, for some domain, the set of noalias scopes in that domain 152 // is a superset of the set of alias scopes in that domain. 153 for (const MDNode *Domain : Domains) { 154 SmallPtrSet<const MDNode *, 16> NANodes, ScopeNodes; 155 collectMDInDomain(NoAlias, Domain, NANodes); 156 collectMDInDomain(Scopes, Domain, ScopeNodes); 157 if (!ScopeNodes.size()) 158 continue; 159 160 // To not alias, all of the nodes in ScopeNodes must be in NANodes. 161 bool FoundAll = true; 162 for (const MDNode *SMD : ScopeNodes) 163 if (!NANodes.count(SMD)) { 164 FoundAll = false; 165 break; 166 } 167 168 if (FoundAll) 169 return false; 170 } 171 172 return true; 173 } 174 175 char ScopedNoAliasAA::PassID; 176 177 ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F, 178 AnalysisManager<Function> &AM) { 179 return ScopedNoAliasAAResult(); 180 } 181 182 char ScopedNoAliasAAWrapperPass::ID = 0; 183 INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias", 184 "Scoped NoAlias Alias Analysis", false, true) 185 186 ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() { 187 return new ScopedNoAliasAAWrapperPass(); 188 } 189 190 ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) { 191 initializeScopedNoAliasAAWrapperPassPass(*PassRegistry::getPassRegistry()); 192 } 193 194 bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) { 195 Result.reset(new ScopedNoAliasAAResult()); 196 return false; 197 } 198 199 bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) { 200 Result.reset(); 201 return false; 202 } 203 204 void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 205 AU.setPreservesAll(); 206 } 207