contrib/llvm-project/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

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