LCOV - code coverage report
Current view: top level - lib/Analysis - ScopedNoAliasAA.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 53 53 100.0 %
Date: 2018-02-23 15:42:53 Functions: 15 15 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/Analysis/MemoryLocation.h"
      38             : #include "llvm/IR/Instruction.h"
      39             : #include "llvm/IR/LLVMContext.h"
      40             : #include "llvm/IR/Metadata.h"
      41             : #include "llvm/Pass.h"
      42             : #include "llvm/Support/Casting.h"
      43             : #include "llvm/Support/CommandLine.h"
      44             : 
      45             : using namespace llvm;
      46             : 
      47             : // A handy option for disabling scoped no-alias functionality. The same effect
      48             : // can also be achieved by stripping the associated metadata tags from IR, but
      49             : // this option is sometimes more convenient.
      50       81686 : static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
      51       81686 :                                          cl::init(true), cl::Hidden);
      52             : 
      53             : namespace {
      54             : 
      55             : /// This is a simple wrapper around an MDNode which provides a higher-level
      56             : /// interface by hiding the details of how alias analysis information is encoded
      57             : /// in its operands.
      58             : class AliasScopeNode {
      59             :   const MDNode *Node = nullptr;
      60             : 
      61             : public:
      62             :   AliasScopeNode() = default;
      63             :   explicit AliasScopeNode(const MDNode *N) : Node(N) {}
      64             : 
      65             :   /// Get the MDNode for this AliasScopeNode.
      66             :   const MDNode *getNode() const { return Node; }
      67             : 
      68             :   /// Get the MDNode for this AliasScopeNode's domain.
      69             :   const MDNode *getDomain() const {
      70       23649 :     if (Node->getNumOperands() < 2)
      71             :       return nullptr;
      72             :     return dyn_cast_or_null<MDNode>(Node->getOperand(1));
      73             :   }
      74             : };
      75             : 
      76             : } // end anonymous namespace
      77             : 
      78     2134153 : AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA,
      79             :                                          const MemoryLocation &LocB) {
      80     2134153 :   if (!EnableScopedNoAlias)
      81             :     return AAResultBase::alias(LocA, LocB);
      82             : 
      83             :   // Get the attached MDNodes.
      84     2134153 :   const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope;
      85             : 
      86     2134153 :   const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
      87             : 
      88     2134153 :   if (!mayAliasInScopes(AScopes, BNoAlias))
      89             :     return NoAlias;
      90             : 
      91     2131548 :   if (!mayAliasInScopes(BScopes, ANoAlias))
      92             :     return NoAlias;
      93             : 
      94             :   // If they may alias, chain to the next AliasAnalysis.
      95     2129263 :   return AAResultBase::alias(LocA, LocB);
      96             : }
      97             : 
      98     4248827 : ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS,
      99             :                                                 const MemoryLocation &Loc) {
     100     4248827 :   if (!EnableScopedNoAlias)
     101             :     return AAResultBase::getModRefInfo(CS, Loc);
     102             : 
     103     4248827 :   if (!mayAliasInScopes(Loc.AATags.Scope, CS.getInstruction()->getMetadata(
     104             :                                               LLVMContext::MD_noalias)))
     105             :     return ModRefInfo::NoModRef;
     106             : 
     107     4248415 :   if (!mayAliasInScopes(
     108             :           CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
     109     4248415 :           Loc.AATags.NoAlias))
     110             :     return ModRefInfo::NoModRef;
     111             : 
     112     4248393 :   return AAResultBase::getModRefInfo(CS, Loc);
     113             : }
     114             : 
     115     2050984 : ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS1,
     116             :                                                 ImmutableCallSite CS2) {
     117     2050984 :   if (!EnableScopedNoAlias)
     118             :     return AAResultBase::getModRefInfo(CS1, CS2);
     119             : 
     120     2050984 :   if (!mayAliasInScopes(
     121             :           CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
     122             :           CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
     123             :     return ModRefInfo::NoModRef;
     124             : 
     125     2050558 :   if (!mayAliasInScopes(
     126             :           CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
     127             :           CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
     128             :     return ModRefInfo::NoModRef;
     129             : 
     130     2050132 :   return AAResultBase::getModRefInfo(CS1, CS2);
     131             : }
     132             : 
     133       13406 : static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
     134             :                               SmallPtrSetImpl<const MDNode *> &Nodes) {
     135       43772 :   for (const MDOperand &MDOp : List->operands())
     136             :     if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
     137       15183 :       if (AliasScopeNode(MD).getDomain() == Domain)
     138       15161 :         Nodes.insert(MD);
     139       13406 : }
     140             : 
     141    16864485 : bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
     142             :                                              const MDNode *NoAlias) const {
     143    16864485 :   if (!Scopes || !NoAlias)
     144             :     return true;
     145             : 
     146             :   // Collect the set of scope domains relevant to the noalias scopes.
     147             :   SmallPtrSet<const MDNode *, 16> Domains;
     148       23639 :   for (const MDOperand &MDOp : NoAlias->operands())
     149             :     if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
     150             :       if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
     151        8466 :         Domains.insert(Domain);
     152             : 
     153             :   // We alias unless, for some domain, the set of noalias scopes in that domain
     154             :   // is a superset of the set of alias scopes in that domain.
     155        6707 :   for (const MDNode *Domain : Domains) {
     156             :     SmallPtrSet<const MDNode *, 16> ScopeNodes;
     157        6710 :     collectMDInDomain(Scopes, Domain, ScopeNodes);
     158        6710 :     if (ScopeNodes.empty())
     159             :       continue;
     160             : 
     161             :     SmallPtrSet<const MDNode *, 16> NANodes;
     162        6696 :     collectMDInDomain(NoAlias, Domain, NANodes);
     163             : 
     164             :     // To not alias, all of the nodes in ScopeNodes must be in NANodes.
     165             :     bool FoundAll = true;
     166        6696 :     for (const MDNode *SMD : ScopeNodes)
     167        6702 :       if (!NANodes.count(SMD)) {
     168             :         FoundAll = false;
     169             :         break;
     170             :       }
     171             : 
     172        6696 :     if (FoundAll)
     173             :       return false;
     174             :   }
     175             : 
     176         531 :   return true;
     177             : }
     178             : 
     179             : AnalysisKey ScopedNoAliasAA::Key;
     180             : 
     181         162 : ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F,
     182             :                                            FunctionAnalysisManager &AM) {
     183         162 :   return ScopedNoAliasAAResult();
     184             : }
     185             : 
     186             : char ScopedNoAliasAAWrapperPass::ID = 0;
     187             : 
     188      299730 : INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias",
     189             :                 "Scoped NoAlias Alias Analysis", false, true)
     190             : 
     191       20809 : ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() {
     192       20809 :   return new ScopedNoAliasAAWrapperPass();
     193             : }
     194             : 
     195       41644 : ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) {
     196       20822 :   initializeScopedNoAliasAAWrapperPassPass(*PassRegistry::getPassRegistry());
     197       20822 : }
     198             : 
     199       20741 : bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) {
     200       20741 :   Result.reset(new ScopedNoAliasAAResult());
     201       20741 :   return false;
     202             : }
     203             : 
     204       20634 : bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) {
     205             :   Result.reset();
     206       20634 :   return false;
     207             : }
     208             : 
     209       20737 : void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     210             :   AU.setPreservesAll();
     211      265795 : }

Generated by: LCOV version 1.13