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 } 739