Home | History | Annotate | Download | only in Analysis 
      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