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 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 if (!EnableTBAA) 373 return AAResultBase::alias(LocA, LocB); 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); 378 379 // Otherwise return a definitive result. 380 return NoAlias; 381 } 382 383 bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc, 384 bool OrLocal) { 385 if (!EnableTBAA) 386 return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 387 388 const MDNode *M = Loc.AATags.TBAA; 389 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 if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) || 395 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable())) 396 return true; 397 398 return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 399 } 400 401 FunctionModRefBehavior 402 TypeBasedAAResult::getModRefBehavior(ImmutableCallSite CS) { 403 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 if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 411 if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) || 412 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable())) 413 Min = FMRB_OnlyReadsMemory; 414 415 return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min); 416 } 417 418 FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) { 419 // Functions don't have metadata. Just chain to the next implementation. 420 return AAResultBase::getModRefBehavior(F); 421 } 422 423 ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS, 424 const MemoryLocation &Loc) { 425 if (!EnableTBAA) 426 return AAResultBase::getModRefInfo(CS, Loc); 427 428 if (const MDNode *L = Loc.AATags.TBAA) 429 if (const MDNode *M = 430 CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 431 if (!Aliases(L, M)) 432 return ModRefInfo::NoModRef; 433 434 return AAResultBase::getModRefInfo(CS, Loc); 435 } 436 437 ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS1, 438 ImmutableCallSite CS2) { 439 if (!EnableTBAA) 440 return AAResultBase::getModRefInfo(CS1, CS2); 441 442 if (const MDNode *M1 = 443 CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 444 if (const MDNode *M2 = 445 CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 446 if (!Aliases(M1, M2)) 447 return ModRefInfo::NoModRef; 448 449 return AAResultBase::getModRefInfo(CS1, CS2); 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 } 741