LCOV - code coverage report
Current view: top level - lib/Analysis - TypeBasedAliasAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 182 220 82.7 %
Date: 2018-10-20 13:21:21 Functions: 28 41 68.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- TypeBasedAliasAnalysis.cpp - Type-Based 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 TypeBasedAliasAnalysis pass, which implements
      11             : // metadata-based TBAA.
      12             : //
      13             : // In LLVM IR, memory does not have types, so LLVM's own type system is not
      14             : // suitable for doing TBAA. Instead, metadata is added to the IR to describe
      15             : // a type system of a higher level language. This can be used to implement
      16             : // typical C/C++ TBAA, but it can also be used to implement custom alias
      17             : // analysis behavior for other languages.
      18             : //
      19             : // We now support two types of metadata format: scalar TBAA and struct-path
      20             : // aware TBAA. After all testing cases are upgraded to use struct-path aware
      21             : // TBAA and we can auto-upgrade existing bc files, the support for scalar TBAA
      22             : // can be dropped.
      23             : //
      24             : // The scalar TBAA metadata format is very simple. TBAA MDNodes have up to
      25             : // three fields, e.g.:
      26             : //   !0 = !{ !"an example type tree" }
      27             : //   !1 = !{ !"int", !0 }
      28             : //   !2 = !{ !"float", !0 }
      29             : //   !3 = !{ !"const float", !2, i64 1 }
      30             : //
      31             : // The first field is an identity field. It can be any value, usually
      32             : // an MDString, which uniquely identifies the type. The most important
      33             : // name in the tree is the name of the root node. Two trees with
      34             : // different root node names are entirely disjoint, even if they
      35             : // have leaves with common names.
      36             : //
      37             : // The second field identifies the type's parent node in the tree, or
      38             : // is null or omitted for a root node. A type is considered to alias
      39             : // all of its descendants and all of its ancestors in the tree. Also,
      40             : // a type is considered to alias all types in other trees, so that
      41             : // bitcode produced from multiple front-ends is handled conservatively.
      42             : //
      43             : // If the third field is present, it's an integer which if equal to 1
      44             : // indicates that the type is "constant" (meaning pointsToConstantMemory
      45             : // should return true; see
      46             : // http://llvm.org/docs/AliasAnalysis.html#OtherItfs).
      47             : //
      48             : // With struct-path aware TBAA, the MDNodes attached to an instruction using
      49             : // "!tbaa" are called path tag nodes.
      50             : //
      51             : // The path tag node has 4 fields with the last field being optional.
      52             : //
      53             : // The first field is the base type node, it can be a struct type node
      54             : // or a scalar type node. The second field is the access type node, it
      55             : // must be a scalar type node. The third field is the offset into the base type.
      56             : // The last field has the same meaning as the last field of our scalar TBAA:
      57             : // it's an integer which if equal to 1 indicates that the access is "constant".
      58             : //
      59             : // The struct type node has a name and a list of pairs, one pair for each member
      60             : // of the struct. The first element of each pair is a type node (a struct type
      61             : // node or a scalar type node), specifying the type of the member, the second
      62             : // element of each pair is the offset of the member.
      63             : //
      64             : // Given an example
      65             : // typedef struct {
      66             : //   short s;
      67             : // } A;
      68             : // typedef struct {
      69             : //   uint16_t s;
      70             : //   A a;
      71             : // } B;
      72             : //
      73             : // For an access to B.a.s, we attach !5 (a path tag node) to the load/store
      74             : // instruction. The base type is !4 (struct B), the access type is !2 (scalar
      75             : // type short) and the offset is 4.
      76             : //
      77             : // !0 = !{!"Simple C/C++ TBAA"}
      78             : // !1 = !{!"omnipotent char", !0} // Scalar type node
      79             : // !2 = !{!"short", !1}           // Scalar type node
      80             : // !3 = !{!"A", !2, i64 0}        // Struct type node
      81             : // !4 = !{!"B", !2, i64 0, !3, i64 4}
      82             : //                                                           // Struct type node
      83             : // !5 = !{!4, !2, i64 4}          // Path tag node
      84             : //
      85             : // The struct type nodes and the scalar type nodes form a type DAG.
      86             : //         Root (!0)
      87             : //         char (!1)  -- edge to Root
      88             : //         short (!2) -- edge to char
      89             : //         A (!3) -- edge with offset 0 to short
      90             : //         B (!4) -- edge with offset 0 to short and edge with offset 4 to A
      91             : //
      92             : // To check if two tags (tagX and tagY) can alias, we start from the base type
      93             : // of tagX, follow the edge with the correct offset in the type DAG and adjust
      94             : // the offset until we reach the base type of tagY or until we reach the Root
      95             : // node.
      96             : // If we reach the base type of tagY, compare the adjusted offset with
      97             : // offset of tagY, return Alias if the offsets are the same, return NoAlias
      98             : // otherwise.
      99             : // If we reach the Root node, perform the above starting from base type of tagY
     100             : // to see if we reach base type of tagX.
     101             : //
     102             : // If they have different roots, they're part of different potentially
     103             : // unrelated type systems, so we return Alias to be conservative.
     104             : // If neither node is an ancestor of the other and they have the same root,
     105             : // then we say NoAlias.
     106             : //
     107             : //===----------------------------------------------------------------------===//
     108             : 
     109             : #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
     110             : #include "llvm/ADT/SetVector.h"
     111             : #include "llvm/Analysis/AliasAnalysis.h"
     112             : #include "llvm/Analysis/MemoryLocation.h"
     113             : #include "llvm/IR/Constants.h"
     114             : #include "llvm/IR/DerivedTypes.h"
     115             : #include "llvm/IR/Instruction.h"
     116             : #include "llvm/IR/LLVMContext.h"
     117             : #include "llvm/IR/Metadata.h"
     118             : #include "llvm/Pass.h"
     119             : #include "llvm/Support/Casting.h"
     120             : #include "llvm/Support/CommandLine.h"
     121             : #include "llvm/Support/ErrorHandling.h"
     122             : #include <cassert>
     123             : #include <cstdint>
     124             : 
     125             : using namespace llvm;
     126             : 
     127             : // A handy option for disabling TBAA functionality. The same effect can also be
     128             : // achieved by stripping the !tbaa tags from IR, but this option is sometimes
     129             : // more convenient.
     130             : static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden);
     131             : 
     132             : namespace {
     133             : 
     134             : /// isNewFormatTypeNode - Return true iff the given type node is in the new
     135             : /// size-aware format.
     136             : static bool isNewFormatTypeNode(const MDNode *N) {
     137         679 :   if (N->getNumOperands() < 3)
     138             :     return false;
     139             :   // In the old format the first operand is a string.
     140             :   if (!isa<MDNode>(N->getOperand(0)))
     141             :     return false;
     142             :   return true;
     143             : }
     144             : 
     145             : /// This is a simple wrapper around an MDNode which provides a higher-level
     146             : /// interface by hiding the details of how alias analysis information is encoded
     147             : /// in its operands.
     148             : template<typename MDNodeTy>
     149             : class TBAANodeImpl {
     150             :   MDNodeTy *Node = nullptr;
     151             : 
     152             : public:
     153           0 :   TBAANodeImpl() = default;
     154      310392 :   explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
     155             : 
     156             :   /// getNode - Get the MDNode for this TBAANode.
     157           0 :   MDNodeTy *getNode() const { return Node; }
     158             : 
     159             :   /// isNewFormat - Return true iff the wrapped type node is in the new
     160             :   /// size-aware format.
     161           0 :   bool isNewFormat() const { return isNewFormatTypeNode(Node); }
     162             : 
     163             :   /// getParent - Get this TBAANode's Alias tree parent.
     164      828896 :   TBAANodeImpl<MDNodeTy> getParent() const {
     165      828896 :     if (isNewFormat())
     166         139 :       return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0)));
     167             : 
     168      828757 :     if (Node->getNumOperands() < 2)
     169      310392 :       return TBAANodeImpl<MDNodeTy>();
     170             :     MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
     171             :     if (!P)
     172           0 :       return TBAANodeImpl<MDNodeTy>();
     173             :     // Ok, this node has a valid parent. Return it.
     174      518365 :     return TBAANodeImpl<MDNodeTy>(P);
     175             :   }
     176             : 
     177             :   /// Test if this TBAANode represents a type for objects which are
     178             :   /// not modified (by any means) in the context where this
     179             :   /// AliasAnalysis is relevant.
     180           0 :   bool isTypeImmutable() const {
     181           0 :     if (Node->getNumOperands() < 3)
     182           0 :       return false;
     183             :     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2));
     184             :     if (!CI)
     185           0 :       return false;
     186           0 :     return CI->getValue()[0];
     187             :   }
     188             : };
     189             : 
     190             : /// \name Specializations of \c TBAANodeImpl for const and non const qualified
     191             : /// \c MDNode.
     192             : /// @{
     193             : using TBAANode = TBAANodeImpl<const MDNode>;
     194             : using MutableTBAANode = TBAANodeImpl<MDNode>;
     195             : /// @}
     196             : 
     197             : /// This is a simple wrapper around an MDNode which provides a
     198             : /// higher-level interface by hiding the details of how alias analysis
     199             : /// information is encoded in its operands.
     200             : template<typename MDNodeTy>
     201             : class TBAAStructTagNodeImpl {
     202             :   /// This node should be created with createTBAAAccessTag().
     203             :   MDNodeTy *Node;
     204             : 
     205             : public:
     206      483442 :   explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
     207             : 
     208             :   /// Get the MDNode for this TBAAStructTagNode.
     209           0 :   MDNodeTy *getNode() const { return Node; }
     210             : 
     211             :   /// isNewFormat - Return true iff the wrapped access tag is in the new
     212             :   /// size-aware format.
     213           0 :   bool isNewFormat() const {
     214           0 :     if (Node->getNumOperands() < 4)
     215           0 :       return false;
     216             :     if (MDNodeTy *AccessType = getAccessType())
     217             :       if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat())
     218           0 :         return false;
     219             :     return true;
     220             :   }
     221             : 
     222           0 :   MDNodeTy *getBaseType() const {
     223           0 :     return dyn_cast_or_null<MDNode>(Node->getOperand(0));
     224             :   }
     225             : 
     226           0 :   MDNodeTy *getAccessType() const {
     227           0 :     return dyn_cast_or_null<MDNode>(Node->getOperand(1));
     228             :   }
     229             : 
     230           0 :   uint64_t getOffset() const {
     231           0 :     return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue();
     232             :   }
     233             : 
     234             :   uint64_t getSize() const {
     235             :     if (!isNewFormat())
     236             :       return UINT64_MAX;
     237             :     return mdconst::extract<ConstantInt>(Node->getOperand(3))->getZExtValue();
     238             :   }
     239             : 
     240             :   /// Test if this TBAAStructTagNode represents a type for objects
     241             :   /// which are not modified (by any means) in the context where this
     242             :   /// AliasAnalysis is relevant.
     243      483442 :   bool isTypeImmutable() const {
     244      483442 :     unsigned OpNo = isNewFormat() ? 4 : 3;
     245      483442 :     if (Node->getNumOperands() < OpNo + 1)
     246             :       return false;
     247             :     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(OpNo));
     248             :     if (!CI)
     249             :       return false;
     250         659 :     return CI->getValue()[0];
     251             :   }
     252             : };
     253             : 
     254             : /// \name Specializations of \c TBAAStructTagNodeImpl for const and non const
     255             : /// qualified \c MDNods.
     256             : /// @{
     257             : using TBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>;
     258             : using MutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>;
     259             : /// @}
     260             : 
     261             : /// This is a simple wrapper around an MDNode which provides a
     262             : /// higher-level interface by hiding the details of how alias analysis
     263             : /// information is encoded in its operands.
     264             : class TBAAStructTypeNode {
     265             :   /// This node should be created with createTBAATypeNode().
     266             :   const MDNode *Node = nullptr;
     267             : 
     268             : public:
     269           0 :   TBAAStructTypeNode() = default;
     270      264827 :   explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
     271             : 
     272             :   /// Get the MDNode for this TBAAStructTypeNode.
     273           0 :   const MDNode *getNode() const { return Node; }
     274             : 
     275             :   /// isNewFormat - Return true iff the wrapped type node is in the new
     276             :   /// size-aware format.
     277           0 :   bool isNewFormat() const { return isNewFormatTypeNode(Node); }
     278             : 
     279             :   bool operator==(const TBAAStructTypeNode &Other) const {
     280          55 :     return getNode() == Other.getNode();
     281             :   }
     282             : 
     283             :   /// getId - Return type identifier.
     284           0 :   Metadata *getId() const {
     285           0 :     return Node->getOperand(isNewFormat() ? 2 : 0);
     286             :   }
     287             : 
     288         110 :   unsigned getNumFields() const {
     289         110 :     unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
     290             :     unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
     291         110 :     return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;
     292             :   }
     293             : 
     294          55 :   TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {
     295          55 :     unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
     296             :     unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
     297          55 :     unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;
     298             :     auto *TypeNode = cast<MDNode>(getNode()->getOperand(OpIndex));
     299          55 :     return TBAAStructTypeNode(TypeNode);
     300             :   }
     301             : 
     302             :   /// Get this TBAAStructTypeNode's field in the type DAG with
     303             :   /// given offset. Update the offset to be relative to the field type.
     304      769077 :   TBAAStructTypeNode getField(uint64_t &Offset) const {
     305      769077 :     bool NewFormat = isNewFormat();
     306             :     if (NewFormat) {
     307             :       // New-format root and scalar type nodes have no fields.
     308          79 :       if (Node->getNumOperands() < 6)
     309           0 :         return TBAAStructTypeNode();
     310             :     } else {
     311             :       // Parent can be omitted for the root node.
     312      768998 :       if (Node->getNumOperands() < 2)
     313      191077 :         return TBAAStructTypeNode();
     314             : 
     315             :       // Fast path for a scalar type node and a struct type node with a single
     316             :       // field.
     317      577921 :       if (Node->getNumOperands() <= 3) {
     318             :         uint64_t Cur = Node->getNumOperands() == 2
     319      432373 :                            ? 0
     320             :                            : mdconst::extract<ConstantInt>(Node->getOperand(2))
     321             :                                  ->getZExtValue();
     322      432373 :         Offset -= Cur;
     323             :         MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
     324             :         if (!P)
     325           0 :           return TBAAStructTypeNode();
     326      432373 :         return TBAAStructTypeNode(P);
     327             :       }
     328             :     }
     329             : 
     330             :     // Assume the offsets are in order. We return the previous field if
     331             :     // the current offset is bigger than the given offset.
     332      145627 :     unsigned FirstFieldOpNo = NewFormat ? 3 : 1;
     333      145627 :     unsigned NumOpsPerField = NewFormat ? 3 : 2;
     334             :     unsigned TheIdx = 0;
     335      551214 :     for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands();
     336      405587 :          Idx += NumOpsPerField) {
     337             :       uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
     338      518273 :                          ->getZExtValue();
     339      518273 :       if (Cur > Offset) {
     340             :         assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
     341             :                "TBAAStructTypeNode::getField should have an offset match!");
     342      112686 :         TheIdx = Idx - NumOpsPerField;
     343      112686 :         break;
     344             :       }
     345             :     }
     346             :     // Move along the last field.
     347      145627 :     if (TheIdx == 0)
     348       32941 :       TheIdx = Node->getNumOperands() - NumOpsPerField;
     349             :     uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
     350      145627 :                        ->getZExtValue();
     351      145627 :     Offset -= Cur;
     352             :     MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
     353             :     if (!P)
     354           0 :       return TBAAStructTypeNode();
     355      145627 :     return TBAAStructTypeNode(P);
     356             :   }
     357             : };
     358             : 
     359             : } // end anonymous namespace
     360             : 
     361             : /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat
     362             : /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA
     363             : /// format.
     364             : static bool isStructPathTBAA(const MDNode *MD) {
     365             :   // Anonymous TBAA root starts with a MDNode and dragonegg uses it as
     366             :   // a TBAA tag.
     367      966909 :   return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
     368             : }
     369             : 
     370     6581675 : AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,
     371             :                                      const MemoryLocation &LocB) {
     372     6581675 :   if (!EnableTBAA)
     373             :     return AAResultBase::alias(LocA, LocB);
     374             : 
     375             :   // If accesses may alias, chain to the next AliasAnalysis.
     376     6581675 :   if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
     377     6469779 :     return AAResultBase::alias(LocA, LocB);
     378             : 
     379             :   // Otherwise return a definitive result.
     380             :   return NoAlias;
     381             : }
     382             : 
     383     6663153 : bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
     384             :                                                bool OrLocal) {
     385     6663153 :   if (!EnableTBAA)
     386             :     return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
     387             : 
     388     6663153 :   const MDNode *M = Loc.AATags.TBAA;
     389     6663153 :   if (!M)
     390             :     return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
     391             : 
     392             :   // If this is an "immutable" type, we can assume the pointer is pointing
     393             :   // to constant memory.
     394           0 :   if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
     395      483276 :       (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
     396         639 :     return true;
     397             : 
     398      482637 :   return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
     399             : }
     400             : 
     401             : FunctionModRefBehavior
     402    10251478 : TypeBasedAAResult::getModRefBehavior(ImmutableCallSite CS) {
     403    10251478 :   if (!EnableTBAA)
     404             :     return AAResultBase::getModRefBehavior(CS);
     405             : 
     406             :   FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
     407             : 
     408             :   // If this is an "immutable" type, we can assume the call doesn't write
     409             :   // to memory.
     410     3754896 :   if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
     411           0 :     if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
     412         166 :         (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
     413             :       Min = FMRB_OnlyReadsMemory;
     414             : 
     415    10251478 :   return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
     416             : }
     417             : 
     418    10159473 : FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) {
     419             :   // Functions don't have metadata. Just chain to the next implementation.
     420    10159473 :   return AAResultBase::getModRefBehavior(F);
     421             : }
     422             : 
     423     5407963 : ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS,
     424             :                                             const MemoryLocation &Loc) {
     425     5407963 :   if (!EnableTBAA)
     426             :     return AAResultBase::getModRefInfo(CS, Loc);
     427             : 
     428     5407963 :   if (const MDNode *L = Loc.AATags.TBAA)
     429      144906 :     if (const MDNode *M =
     430             :             CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
     431           4 :       if (!Aliases(L, M))
     432             :         return ModRefInfo::NoModRef;
     433             : 
     434     5407963 :   return AAResultBase::getModRefInfo(CS, Loc);
     435             : }
     436             : 
     437     2172907 : ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS1,
     438             :                                             ImmutableCallSite CS2) {
     439     2172907 :   if (!EnableTBAA)
     440             :     return AAResultBase::getModRefInfo(CS1, CS2);
     441             : 
     442       30961 :   if (const MDNode *M1 =
     443             :           CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
     444          18 :     if (const MDNode *M2 =
     445             :             CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
     446          18 :       if (!Aliases(M1, M2))
     447             :         return ModRefInfo::NoModRef;
     448             : 
     449     2172899 :   return AAResultBase::getModRefInfo(CS1, CS2);
     450             : }
     451             : 
     452          25 : bool MDNode::isTBAAVtableAccess() const {
     453             :   if (!isStructPathTBAA(this)) {
     454           0 :     if (getNumOperands() < 1)
     455             :       return false;
     456             :     if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
     457           0 :       if (Tag1->getString() == "vtable pointer")
     458             :         return true;
     459             :     }
     460           0 :     return false;
     461             :   }
     462             : 
     463             :   // For struct-path aware TBAA, we use the access type of the tag.
     464             :   TBAAStructTagNode Tag(this);
     465             :   TBAAStructTypeNode AccessType(Tag.getAccessType());
     466             :   if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
     467          25 :     if (Id->getString() == "vtable pointer")
     468          22 :       return true;
     469             :   return false;
     470             : }
     471             : 
     472             : static bool matchAccessTags(const MDNode *A, const MDNode *B,
     473             :                             const MDNode **GenericTag = nullptr);
     474             : 
     475        4724 : MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
     476             :   const MDNode *GenericTag;
     477        4724 :   matchAccessTags(A, B, &GenericTag);
     478        4724 :   return const_cast<MDNode*>(GenericTag);
     479             : }
     480             : 
     481      210464 : static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
     482      210464 :   if (!A || !B)
     483             :     return nullptr;
     484             : 
     485      210464 :   if (A == B)
     486             :     return A;
     487             : 
     488             :   SmallSetVector<const MDNode *, 4> PathA;
     489             :   TBAANode TA(A);
     490      577185 :   while (TA.getNode()) {
     491      421989 :     if (PathA.count(TA.getNode()))
     492           0 :       report_fatal_error("Cycle found in TBAA metadata.");
     493      421989 :     PathA.insert(TA.getNode());
     494      421989 :     TA = TA.getParent();
     495             :   }
     496             : 
     497             :   SmallSetVector<const MDNode *, 4> PathB;
     498             :   TBAANode TB(B);
     499      562103 :   while (TB.getNode()) {
     500      406907 :     if (PathB.count(TB.getNode()))
     501           0 :       report_fatal_error("Cycle found in TBAA metadata.");
     502      406907 :     PathB.insert(TB.getNode());
     503      406907 :     TB = TB.getParent();
     504             :   }
     505             : 
     506      155196 :   int IA = PathA.size() - 1;
     507      155196 :   int IB = PathB.size() - 1;
     508             : 
     509             :   const MDNode *Ret = nullptr;
     510      440470 :   while (IA >= 0 && IB >= 0) {
     511     1100040 :     if (PathA[IA] == PathB[IB])
     512             :       Ret = PathA[IA];
     513             :     else
     514             :       break;
     515      285274 :     --IA;
     516      285274 :     --IB;
     517             :   }
     518             : 
     519             :   return Ret;
     520             : }
     521             : 
     522    52466266 : void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {
     523    52466266 :   if (Merge)
     524         223 :     N.TBAA =
     525         223 :         MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa));
     526             :   else
     527    52466043 :     N.TBAA = getMetadata(LLVMContext::MD_tbaa);
     528             : 
     529    52466266 :   if (Merge)
     530         223 :     N.Scope = MDNode::getMostGenericAliasScope(
     531             :         N.Scope, getMetadata(LLVMContext::MD_alias_scope));
     532             :   else
     533    52466043 :     N.Scope = getMetadata(LLVMContext::MD_alias_scope);
     534             : 
     535    52466266 :   if (Merge)
     536         223 :     N.NoAlias =
     537         223 :         MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
     538             :   else
     539    52466043 :     N.NoAlias = getMetadata(LLVMContext::MD_noalias);
     540    52466266 : }
     541             : 
     542         491 : static const MDNode *createAccessTag(const MDNode *AccessType) {
     543             :   // If there is no access type or the access type is the root node, then
     544             :   // we don't have any useful access tag to return.
     545         491 :   if (!AccessType || AccessType->getNumOperands() < 2)
     546             :     return nullptr;
     547             : 
     548         489 :   Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
     549         489 :   auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
     550             : 
     551             :   if (TBAAStructTypeNode(AccessType).isNewFormat()) {
     552             :     // TODO: Take access ranges into account when matching access tags and
     553             :     // fix this code to generate actual access sizes for generic tags.
     554             :     uint64_t AccessSize = UINT64_MAX;
     555             :     auto *SizeNode =
     556           0 :         ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
     557             :     Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
     558             :                        const_cast<MDNode*>(AccessType),
     559           0 :                        OffsetNode, SizeNode};
     560             :     return MDNode::get(AccessType->getContext(), Ops);
     561             :   }
     562             : 
     563             :   Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
     564             :                      const_cast<MDNode*>(AccessType),
     565         489 :                      OffsetNode};
     566             :   return MDNode::get(AccessType->getContext(), Ops);
     567             : }
     568             : 
     569         110 : static bool hasField(TBAAStructTypeNode BaseType,
     570             :                      TBAAStructTypeNode FieldType) {
     571         133 :   for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {
     572          55 :     TBAAStructTypeNode T = BaseType.getFieldType(I);
     573          55 :     if (T == FieldType || hasField(T, FieldType))
     574          32 :       return true;
     575             :   }
     576             :   return false;
     577             : }
     578             : 
     579             : /// Return true if for two given accesses, one of the accessed objects may be a
     580             : /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
     581             : /// describe the accesses to the base object and the subobject respectively.
     582             : /// \p CommonType must be the metadata node describing the common type of the
     583             : /// accessed objects. On return, \p MayAlias is set to true iff these accesses
     584             : /// may alias and \p Generic, if not null, points to the most generic access
     585             : /// tag for the given two.
     586      306797 : static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
     587             :                                      TBAAStructTagNode SubobjectTag,
     588             :                                      const MDNode *CommonType,
     589             :                                      const MDNode **GenericTag,
     590             :                                      bool &MayAlias) {
     591             :   // If the base object is of the least common type, then this may be an access
     592             :   // to its subobject.
     593      432163 :   if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
     594             :       BaseTag.getAccessType() == CommonType) {
     595       41970 :     if (GenericTag)
     596          54 :       *GenericTag = createAccessTag(CommonType);
     597       41970 :     MayAlias = true;
     598       41970 :     return true;
     599             :   }
     600             : 
     601             :   // If the access to the base object is through a field of the subobject's
     602             :   // type, then this may be an access to that field. To check for that we start
     603             :   // from the base type, follow the edge with the correct offset in the type DAG
     604             :   // and adjust the offset until we reach the field type or until we reach the
     605             :   // access type.
     606      264827 :   bool NewFormat = BaseTag.isNewFormat();
     607             :   TBAAStructTypeNode BaseType(BaseTag.getBaseType());
     608      264827 :   uint64_t OffsetInBase = BaseTag.getOffset();
     609             : 
     610             :   for (;;) {
     611             :     // In the old format there is no distinction between fields and parent
     612             :     // types, so in this case we consider all nodes up to the root.
     613     1033904 :     if (!BaseType.getNode()) {
     614             :       assert(!NewFormat && "Did not see access type in access path!");
     615             :       break;
     616             :     }
     617             : 
     618      842827 :     if (BaseType.getNode() == SubobjectTag.getBaseType()) {
     619       73671 :       bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
     620       73671 :       if (GenericTag) {
     621         848 :         *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
     622         369 :                                          createAccessTag(CommonType);
     623             :       }
     624       73671 :       MayAlias = SameMemberAccess;
     625       73671 :       return true;
     626             :     }
     627             : 
     628             :     // With new-format nodes we stop at the access type.
     629      769314 :     if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
     630             :       break;
     631             : 
     632             :     // Follow the edge with the correct offset. Offset will be adjusted to
     633             :     // be relative to the field type.
     634      769077 :     BaseType = BaseType.getField(OffsetInBase);
     635      769077 :   }
     636             : 
     637             :   // If the base object has a direct or indirect field of the subobject's type,
     638             :   // then this may be an access to that field. We need this to check now that
     639             :   // we support aggregates as access types.
     640      191156 :   if (NewFormat) {
     641             :     // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
     642             :     TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
     643          79 :     if (hasField(BaseType, FieldType)) {
     644          24 :       if (GenericTag)
     645           0 :         *GenericTag = createAccessTag(CommonType);
     646          24 :       MayAlias = true;
     647          24 :       return true;
     648             :     }
     649             :   }
     650             : 
     651             :   return false;
     652             : }
     653             : 
     654             : /// matchTags - Return true if the given couple of accesses are allowed to
     655             : /// overlap. If \arg GenericTag is not null, then on return it points to the
     656             : /// most generic access descriptor for the given two.
     657     6586421 : static bool matchAccessTags(const MDNode *A, const MDNode *B,
     658             :                             const MDNode **GenericTag) {
     659     6586421 :   if (A == B) {
     660     4856753 :     if (GenericTag)
     661        4100 :       *GenericTag = A;
     662     4856753 :     return true;
     663             :   }
     664             : 
     665             :   // Accesses with no TBAA information may alias with any other accesses.
     666     1729668 :   if (!A || !B) {
     667     1519204 :     if (GenericTag)
     668          21 :       *GenericTag = nullptr;
     669     1519204 :     return true;
     670             :   }
     671             : 
     672             :   // Verify that both input nodes are struct-path aware.  Auto-upgrade should
     673             :   // have taken care of this.
     674             :   assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
     675             :   assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
     676             : 
     677             :   TBAAStructTagNode TagA(A), TagB(B);
     678      210464 :   const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
     679             :                                                 TagB.getAccessType());
     680             : 
     681             :   // If the final access types have different roots, they're part of different
     682             :   // potentially unrelated type systems, so we must be conservative.
     683      210464 :   if (!CommonType) {
     684          13 :     if (GenericTag)
     685           2 :       *GenericTag = nullptr;
     686          13 :     return true;
     687             :   }
     688             : 
     689             :   // If one of the accessed objects may be a subobject of the other, then such
     690             :   // accesses may alias.
     691             :   bool MayAlias;
     692      210451 :   if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
     693      306797 :                                CommonType, GenericTag, MayAlias) ||
     694       96346 :       mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
     695             :                                CommonType, GenericTag, MayAlias))
     696      115665 :     return MayAlias;
     697             : 
     698             :   // Otherwise, we've proved there's no alias.
     699       94786 :   if (GenericTag)
     700          68 :     *GenericTag = createAccessTag(CommonType);
     701             :   return false;
     702             : }
     703             : 
     704             : /// Aliases - Test whether the access represented by tag A may alias the
     705             : /// access represented by tag B.
     706     6581697 : bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
     707     6581697 :   return matchAccessTags(A, B);
     708             : }
     709             : 
     710             : AnalysisKey TypeBasedAA::Key;
     711             : 
     712         195 : TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) {
     713         195 :   return TypeBasedAAResult();
     714             : }
     715             : 
     716             : char TypeBasedAAWrapperPass::ID = 0;
     717      211733 : INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
     718             :                 false, true)
     719             : 
     720       30109 : ImmutablePass *llvm::createTypeBasedAAWrapperPass() {
     721       30109 :   return new TypeBasedAAWrapperPass();
     722             : }
     723             : 
     724       60346 : TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) {
     725       30173 :   initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry());
     726       30173 : }
     727             : 
     728       30031 : bool TypeBasedAAWrapperPass::doInitialization(Module &M) {
     729       30031 :   Result.reset(new TypeBasedAAResult());
     730       30031 :   return false;
     731             : }
     732             : 
     733       29880 : bool TypeBasedAAWrapperPass::doFinalization(Module &M) {
     734             :   Result.reset();
     735       29880 :   return false;
     736             : }
     737             : 
     738       30035 : void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     739             :   AU.setPreservesAll();
     740       30035 : }

Generated by: LCOV version 1.13