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/InitializePasses.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   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   TBAANodeImpl() = default;
 154   explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
 155
 156   /// getNode - Get the MDNode for this TBAANode.
 157   MDNodeTy *getNode() const { return Node; }
 158
 159   /// isNewFormat - Return true iff the wrapped type node is in the new
 160   /// size-aware format.
 161   bool isNewFormat() const { return isNewFormatTypeNode(Node); }
 162
 163   /// getParent - Get this TBAANode's Alias tree parent.
 164   TBAANodeImpl<MDNodeTy> getParent() const {
 165     if (isNewFormat())
 166       return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0)));
 167
 168     if (Node->getNumOperands() < 2)
 169       return TBAANodeImpl<MDNodeTy>();
 170     MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
 171     if (!P)
 172       return TBAANodeImpl<MDNodeTy>();
 173     // Ok, this node has a valid parent. Return it.
 174     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   bool isTypeImmutable() const {
 181     if (Node->getNumOperands() < 3)
 182       return false;
 183     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2));
 184     if (!CI)
 185       return false;
 186     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   explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
 207
 208   /// Get the MDNode for this TBAAStructTagNode.
 209   MDNodeTy *getNode() const { return Node; }
 210
 211   /// isNewFormat - Return true iff the wrapped access tag is in the new
 212   /// size-aware format.
 213   bool isNewFormat() const {
 214     if (Node->getNumOperands() < 4)
 215       return false;
 216     if (MDNodeTy *AccessType = getAccessType())
 217       if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat())
 218         return false;
 219     return true;
 220   }
 221
 222   MDNodeTy *getBaseType() const {
 223     return dyn_cast_or_null<MDNode>(Node->getOperand(0));
 224   }
 225
 226   MDNodeTy *getAccessType() const {
 227     return dyn_cast_or_null<MDNode>(Node->getOperand(1));
 228   }
 229
 230   uint64_t getOffset() const {
 231     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   bool isTypeImmutable() const {
 244     unsigned OpNo = isNewFormat() ? 4 : 3;
 245     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     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   TBAAStructTypeNode() = default;
 270   explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
 271
 272   /// Get the MDNode for this TBAAStructTypeNode.
 273   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   bool isNewFormat() const { return isNewFormatTypeNode(Node); }
 278
 279   bool operator==(const TBAAStructTypeNode &Other) const {
 280     return getNode() == Other.getNode();
 281   }
 282
 283   /// getId - Return type identifier.
 284   Metadata *getId() const {
 285     return Node->getOperand(isNewFormat() ? 2 : 0);
 286   }
 287
 288   unsigned getNumFields() const {
 289     unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
 290     unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
 291     return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;
 292   }
 293
 294   TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {
 295     unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
 296     unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
 297     unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;
 298     auto *TypeNode = cast<MDNode>(getNode()->getOperand(OpIndex));
 299     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   TBAAStructTypeNode getField(uint64_t &Offset) const {
 305     bool NewFormat = isNewFormat();
 306     if (NewFormat) {
 307       // New-format root and scalar type nodes have no fields.
 308       if (Node->getNumOperands() < 6)
 309         return TBAAStructTypeNode();
 310     } else {
 311       // Parent can be omitted for the root node.
 312       if (Node->getNumOperands() < 2)
 313         return TBAAStructTypeNode();
 314
 315       // Fast path for a scalar type node and a struct type node with a single
 316       // field.
 317       if (Node->getNumOperands() <= 3) {
 318         uint64_t Cur = Node->getNumOperands() == 2
 319                            ? 0
 320                            : mdconst::extract<ConstantInt>(Node->getOperand(2))
 321                                  ->getZExtValue();
 322         Offset -= Cur;
 323         MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
 324         if (!P)
 325           return TBAAStructTypeNode();
 326         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     unsigned FirstFieldOpNo = NewFormat ? 3 : 1;
 333     unsigned NumOpsPerField = NewFormat ? 3 : 2;
 334     unsigned TheIdx = 0;
 335     for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands();
 336          Idx += NumOpsPerField) {
 337       uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
 338                          ->getZExtValue();
 339       if (Cur > Offset) {
 340         assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
 341                "TBAAStructTypeNode::getField should have an offset match!");
 342         TheIdx = Idx - NumOpsPerField;
 343         break;
 344       }
 345     }
 346     // Move along the last field.
 347     if (TheIdx == 0)
 348       TheIdx = Node->getNumOperands() - NumOpsPerField;
 349     uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
 350                        ->getZExtValue();
 351     Offset -= Cur;
 352     MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
 353     if (!P)
 354       return TBAAStructTypeNode();
 355     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   return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
 368 }
 369
 370 AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,
 371                                      const MemoryLocation &LocB,
 372                                      AAQueryInfo &AAQI) {
 373   if (!EnableTBAA)
 374     return AAResultBase::alias(LocA, LocB, AAQI);
 375
 376   // If accesses may alias, chain to the next AliasAnalysis.
 377   if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
 378     return AAResultBase::alias(LocA, LocB, AAQI);
 379
 380   // Otherwise return a definitive result.
 381   return NoAlias;
 382 }
 383
 384 bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
 385                                                AAQueryInfo &AAQI,
 386                                                bool OrLocal) {
 387   if (!EnableTBAA)
 388     return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
 389
 390   const MDNode *M = Loc.AATags.TBAA;
 391   if (!M)
 392     return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
 393
 394   // If this is an "immutable" type, we can assume the pointer is pointing
 395   // to constant memory.
 396   if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
 397       (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
 398     return true;
 399
 400   return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
 401 }
 402
 403 FunctionModRefBehavior
 404 TypeBasedAAResult::getModRefBehavior(const CallBase *Call) {
 405   if (!EnableTBAA)
 406     return AAResultBase::getModRefBehavior(Call);
 407
 408   FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
 409
 410   // If this is an "immutable" type, we can assume the call doesn't write
 411   // to memory.
 412   if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
 413     if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
 414         (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
 415       Min = FMRB_OnlyReadsMemory;
 416
 417   return FunctionModRefBehavior(AAResultBase::getModRefBehavior(Call) & Min);
 418 }
 419
 420 FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) {
 421   // Functions don't have metadata. Just chain to the next implementation.
 422   return AAResultBase::getModRefBehavior(F);
 423 }
 424
 425 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call,
 426                                             const MemoryLocation &Loc,
 427                                             AAQueryInfo &AAQI) {
 428   if (!EnableTBAA)
 429     return AAResultBase::getModRefInfo(Call, Loc, AAQI);
 430
 431   if (const MDNode *L = Loc.AATags.TBAA)
 432     if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
 433       if (!Aliases(L, M))
 434         return ModRefInfo::NoModRef;
 435
 436   return AAResultBase::getModRefInfo(Call, Loc, AAQI);
 437 }
 438
 439 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call1,
 440                                             const CallBase *Call2,
 441                                             AAQueryInfo &AAQI) {
 442   if (!EnableTBAA)
 443     return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
 444
 445   if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))
 446     if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))
 447       if (!Aliases(M1, M2))
 448         return ModRefInfo::NoModRef;
 449
 450   return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
 451 }
 452
 453 bool MDNode::isTBAAVtableAccess() const {
 454   if (!isStructPathTBAA(this)) {
 455     if (getNumOperands() < 1)
 456       return false;
 457     if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
 458       if (Tag1->getString() == "vtable pointer")
 459         return true;
 460     }
 461     return false;
 462   }
 463
 464   // For struct-path aware TBAA, we use the access type of the tag.
 465   TBAAStructTagNode Tag(this);
 466   TBAAStructTypeNode AccessType(Tag.getAccessType());
 467   if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
 468     if (Id->getString() == "vtable pointer")
 469       return true;
 470   return false;
 471 }
 472
 473 static bool matchAccessTags(const MDNode *A, const MDNode *B,
 474                             const MDNode **GenericTag = nullptr);
 475
 476 MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
 477   const MDNode *GenericTag;
 478   matchAccessTags(A, B, &GenericTag);
 479   return const_cast<MDNode*>(GenericTag);
 480 }
 481
 482 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
 483   if (!A || !B)
 484     return nullptr;
 485
 486   if (A == B)
 487     return A;
 488
 489   SmallSetVector<const MDNode *, 4> PathA;
 490   TBAANode TA(A);
 491   while (TA.getNode()) {
 492     if (PathA.count(TA.getNode()))
 493       report_fatal_error("Cycle found in TBAA metadata.");
 494     PathA.insert(TA.getNode());
 495     TA = TA.getParent();
 496   }
 497
 498   SmallSetVector<const MDNode *, 4> PathB;
 499   TBAANode TB(B);
 500   while (TB.getNode()) {
 501     if (PathB.count(TB.getNode()))
 502       report_fatal_error("Cycle found in TBAA metadata.");
 503     PathB.insert(TB.getNode());
 504     TB = TB.getParent();
 505   }
 506
 507   int IA = PathA.size() - 1;
 508   int IB = PathB.size() - 1;
 509
 510   const MDNode *Ret = nullptr;
 511   while (IA >= 0 && IB >= 0) {
 512     if (PathA[IA] == PathB[IB])
 513       Ret = PathA[IA];
 514     else
 515       break;
 516     --IA;
 517     --IB;
 518   }
 519
 520   return Ret;
 521 }
 522
 523 void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {
 524   if (Merge) {
 525     N.TBAA =
 526         MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa));
 527     N.TBAAStruct = nullptr;
 528     N.Scope = MDNode::getMostGenericAliasScope(
 529         N.Scope, getMetadata(LLVMContext::MD_alias_scope));
 530     N.NoAlias =
 531         MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
 532   } else {
 533     N.TBAA = getMetadata(LLVMContext::MD_tbaa);
 534     N.TBAAStruct = getMetadata(LLVMContext::MD_tbaa_struct);
 535     N.Scope = getMetadata(LLVMContext::MD_alias_scope);
 536     N.NoAlias = getMetadata(LLVMContext::MD_noalias);
 537   }
 538 }
 539
 540 static const MDNode *createAccessTag(const MDNode *AccessType) {
 541   // If there is no access type or the access type is the root node, then
 542   // we don't have any useful access tag to return.
 543   if (!AccessType || AccessType->getNumOperands() < 2)
 544     return nullptr;
 545
 546   Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
 547   auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
 548
 549   if (TBAAStructTypeNode(AccessType).isNewFormat()) {
 550     // TODO: Take access ranges into account when matching access tags and
 551     // fix this code to generate actual access sizes for generic tags.
 552     uint64_t AccessSize = UINT64_MAX;
 553     auto *SizeNode =
 554         ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
 555     Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
 556                        const_cast<MDNode*>(AccessType),
 557                        OffsetNode, SizeNode};
 558     return MDNode::get(AccessType->getContext(), Ops);
 559   }
 560
 561   Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
 562                      const_cast<MDNode*>(AccessType),
 563                      OffsetNode};
 564   return MDNode::get(AccessType->getContext(), Ops);
 565 }
 566
 567 static bool hasField(TBAAStructTypeNode BaseType,
 568                      TBAAStructTypeNode FieldType) {
 569   for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {
 570     TBAAStructTypeNode T = BaseType.getFieldType(I);
 571     if (T == FieldType || hasField(T, FieldType))
 572       return true;
 573   }
 574   return false;
 575 }
 576
 577 /// Return true if for two given accesses, one of the accessed objects may be a
 578 /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
 579 /// describe the accesses to the base object and the subobject respectively.
 580 /// \p CommonType must be the metadata node describing the common type of the
 581 /// accessed objects. On return, \p MayAlias is set to true iff these accesses
 582 /// may alias and \p Generic, if not null, points to the most generic access
 583 /// tag for the given two.
 584 static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
 585                                      TBAAStructTagNode SubobjectTag,
 586                                      const MDNode *CommonType,
 587                                      const MDNode **GenericTag,
 588                                      bool &MayAlias) {
 589   // If the base object is of the least common type, then this may be an access
 590   // to its subobject.
 591   if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
 592       BaseTag.getAccessType() == CommonType) {
 593     if (GenericTag)
 594       *GenericTag = createAccessTag(CommonType);
 595     MayAlias = true;
 596     return true;
 597   }
 598
 599   // If the access to the base object is through a field of the subobject's
 600   // type, then this may be an access to that field. To check for that we start
 601   // from the base type, follow the edge with the correct offset in the type DAG
 602   // and adjust the offset until we reach the field type or until we reach the
 603   // access type.
 604   bool NewFormat = BaseTag.isNewFormat();
 605   TBAAStructTypeNode BaseType(BaseTag.getBaseType());
 606   uint64_t OffsetInBase = BaseTag.getOffset();
 607
 608   for (;;) {
 609     // In the old format there is no distinction between fields and parent
 610     // types, so in this case we consider all nodes up to the root.
 611     if (!BaseType.getNode()) {
 612       assert(!NewFormat && "Did not see access type in access path!");
 613       break;
 614     }
 615
 616     if (BaseType.getNode() == SubobjectTag.getBaseType()) {
 617       bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
 618       if (GenericTag) {
 619         *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
 620                                          createAccessTag(CommonType);
 621       }
 622       MayAlias = SameMemberAccess;
 623       return true;
 624     }
 625
 626     // With new-format nodes we stop at the access type.
 627     if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
 628       break;
 629
 630     // Follow the edge with the correct offset. Offset will be adjusted to
 631     // be relative to the field type.
 632     BaseType = BaseType.getField(OffsetInBase);
 633   }
 634
 635   // If the base object has a direct or indirect field of the subobject's type,
 636   // then this may be an access to that field. We need this to check now that
 637   // we support aggregates as access types.
 638   if (NewFormat) {
 639     // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
 640     TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
 641     if (hasField(BaseType, FieldType)) {
 642       if (GenericTag)
 643         *GenericTag = createAccessTag(CommonType);
 644       MayAlias = true;
 645       return true;
 646     }
 647   }
 648
 649   return false;
 650 }
 651
 652 /// matchTags - Return true if the given couple of accesses are allowed to
 653 /// overlap. If \arg GenericTag is not null, then on return it points to the
 654 /// most generic access descriptor for the given two.
 655 static bool matchAccessTags(const MDNode *A, const MDNode *B,
 656                             const MDNode **GenericTag) {
 657   if (A == B) {
 658     if (GenericTag)
 659       *GenericTag = A;
 660     return true;
 661   }
 662
 663   // Accesses with no TBAA information may alias with any other accesses.
 664   if (!A || !B) {
 665     if (GenericTag)
 666       *GenericTag = nullptr;
 667     return true;
 668   }
 669
 670   // Verify that both input nodes are struct-path aware.  Auto-upgrade should
 671   // have taken care of this.
 672   assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
 673   assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
 674
 675   TBAAStructTagNode TagA(A), TagB(B);
 676   const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
 677                                                 TagB.getAccessType());
 678
 679   // If the final access types have different roots, they're part of different
 680   // potentially unrelated type systems, so we must be conservative.
 681   if (!CommonType) {
 682     if (GenericTag)
 683       *GenericTag = nullptr;
 684     return true;
 685   }
 686
 687   // If one of the accessed objects may be a subobject of the other, then such
 688   // accesses may alias.
 689   bool MayAlias;
 690   if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
 691                                CommonType, GenericTag, MayAlias) ||
 692       mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
 693                                CommonType, GenericTag, MayAlias))
 694     return MayAlias;
 695
 696   // Otherwise, we've proved there's no alias.
 697   if (GenericTag)
 698     *GenericTag = createAccessTag(CommonType);
 699   return false;
 700 }
 701
 702 /// Aliases - Test whether the access represented by tag A may alias the
 703 /// access represented by tag B.
 704 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
 705   return matchAccessTags(A, B);
 706 }
 707
 708 AnalysisKey TypeBasedAA::Key;
 709
 710 TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) {
 711   return TypeBasedAAResult();
 712 }
 713
 714 char TypeBasedAAWrapperPass::ID = 0;
 715 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
 716                 false, true)
 717
 718 ImmutablePass *llvm::createTypeBasedAAWrapperPass() {
 719   return new TypeBasedAAWrapperPass();
 720 }
 721
 722 TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) {
 723   initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry());
 724 }
 725
 726 bool TypeBasedAAWrapperPass::doInitialization(Module &M) {
 727   Result.reset(new TypeBasedAAResult());
 728   return false;
 729 }
 730
 731 bool TypeBasedAAWrapperPass::doFinalization(Module &M) {
 732   Result.reset();
 733   return false;
 734 }
 735
 736 void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 737   AU.setPreservesAll();
 738 }