LCOV - code coverage report
Current view: top level - lib/Analysis - ScopedNoAliasAA.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 70 70 100.0 %
Date: 2017-09-14 15:23:50 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       72306 : static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
      51      144612 :                                          cl::init(true));
      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        9240 :     if (Node->getNumOperands() < 2)
      71             :       return nullptr;
      72       18480 :     return dyn_cast_or_null<MDNode>(Node->getOperand(1));
      73             :   }
      74             : };
      75             : 
      76             : } // end anonymous namespace
      77             : 
      78     2005720 : AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA,
      79             :                                          const MemoryLocation &LocB) {
      80     2005720 :   if (!EnableScopedNoAlias)
      81             :     return AAResultBase::alias(LocA, LocB);
      82             : 
      83             :   // Get the attached MDNodes.
      84     2005720 :   const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope;
      85             : 
      86     2005720 :   const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
      87             : 
      88     2005720 :   if (!mayAliasInScopes(AScopes, BNoAlias))
      89             :     return NoAlias;
      90             : 
      91     2005636 :   if (!mayAliasInScopes(BScopes, ANoAlias))
      92             :     return NoAlias;
      93             : 
      94             :   // If they may alias, chain to the next AliasAnalysis.
      95     2005606 :   return AAResultBase::alias(LocA, LocB);
      96             : }
      97             : 
      98     4051514 : ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS,
      99             :                                                 const MemoryLocation &Loc) {
     100     4051514 :   if (!EnableScopedNoAlias)
     101             :     return AAResultBase::getModRefInfo(CS, Loc);
     102             : 
     103     8103028 :   if (!mayAliasInScopes(Loc.AATags.Scope, CS.getInstruction()->getMetadata(
     104             :                                               LLVMContext::MD_noalias)))
     105             :     return MRI_NoModRef;
     106             : 
     107     4051098 :   if (!mayAliasInScopes(
     108     8102196 :           CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
     109     4051098 :           Loc.AATags.NoAlias))
     110             :     return MRI_NoModRef;
     111             : 
     112     4051076 :   return AAResultBase::getModRefInfo(CS, Loc);
     113             : }
     114             : 
     115     1907665 : ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS1,
     116             :                                                 ImmutableCallSite CS2) {
     117     1907665 :   if (!EnableScopedNoAlias)
     118             :     return AAResultBase::getModRefInfo(CS1, CS2);
     119             : 
     120     1907665 :   if (!mayAliasInScopes(
     121     3815330 :           CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
     122     3815330 :           CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
     123             :     return MRI_NoModRef;
     124             : 
     125     1907239 :   if (!mayAliasInScopes(
     126     3814478 :           CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
     127     3814478 :           CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
     128             :     return MRI_NoModRef;
     129             : 
     130     1906813 :   return AAResultBase::getModRefInfo(CS1, CS2);
     131             : }
     132             : 
     133        3798 : static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
     134             :                               SmallPtrSetImpl<const MDNode *> &Nodes) {
     135        9375 :   for (const MDOperand &MDOp : List->operands())
     136        5577 :     if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
     137       11154 :       if (AliasScopeNode(MD).getDomain() == Domain)
     138        5553 :         Nodes.insert(MD);
     139        3798 : }
     140             : 
     141    15928872 : bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
     142             :                                              const MDNode *NoAlias) const {
     143    15928872 :   if (!Scopes || !NoAlias)
     144             :     return true;
     145             : 
     146             :   // Collect the set of scope domains relevant to the noalias scopes.
     147        1903 :   SmallPtrSet<const MDNode *, 16> Domains;
     148        5566 :   for (const MDOperand &MDOp : NoAlias->operands())
     149        3663 :     if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
     150        7326 :       if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
     151        3663 :         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        3809 :   for (const MDNode *Domain : Domains) {
     156        2394 :     SmallPtrSet<const MDNode *, 16> ScopeNodes;
     157        1906 :     collectMDInDomain(Scopes, Domain, ScopeNodes);
     158        1906 :     if (ScopeNodes.empty())
     159          14 :       continue;
     160             : 
     161        2380 :     SmallPtrSet<const MDNode *, 16> NANodes;
     162        1892 :     collectMDInDomain(NoAlias, Domain, NANodes);
     163             : 
     164             :     // To not alias, all of the nodes in ScopeNodes must be in NANodes.
     165        1892 :     bool FoundAll = true;
     166        3790 :     for (const MDNode *SMD : ScopeNodes)
     167        1898 :       if (!NANodes.count(SMD)) {
     168             :         FoundAll = false;
     169             :         break;
     170             :       }
     171             : 
     172        1892 :     if (FoundAll)
     173        2808 :       return false;
     174             :   }
     175             : 
     176         499 :   return true;
     177             : }
     178             : 
     179             : AnalysisKey ScopedNoAliasAA::Key;
     180             : 
     181         140 : ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F,
     182             :                                            FunctionAnalysisManager &AM) {
     183         140 :   return ScopedNoAliasAAResult();
     184             : }
     185             : 
     186             : char ScopedNoAliasAAWrapperPass::ID = 0;
     187             : 
     188      349941 : INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias",
     189             :                 "Scoped NoAlias Alias Analysis", false, true)
     190             : 
     191       18701 : ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() {
     192       18701 :   return new ScopedNoAliasAAWrapperPass();
     193             : }
     194             : 
     195       56142 : ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) {
     196       18714 :   initializeScopedNoAliasAAWrapperPassPass(*PassRegistry::getPassRegistry());
     197       18714 : }
     198             : 
     199       18681 : bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) {
     200       37362 :   Result.reset(new ScopedNoAliasAAResult());
     201       18681 :   return false;
     202             : }
     203             : 
     204       18577 : bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) {
     205       37155 :   Result.reset();
     206       18578 :   return false;
     207             : }
     208             : 
     209       18677 : void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     210       18677 :   AU.setPreservesAll();
     211      235595 : }

Generated by: LCOV version 1.13