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