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/InstrTypes.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 const ArrayRef<MDOperand> Operands = Node->operands(); 307 const unsigned NumOperands = Operands.size(); 308 309 if (NewFormat) { 310 // New-format root and scalar type nodes have no fields. 311 if (NumOperands < 6) 312 return TBAAStructTypeNode(); 313 } else { 314 // Parent can be omitted for the root node. 315 if (NumOperands < 2) 316 return TBAAStructTypeNode(); 317 318 // Fast path for a scalar type node and a struct type node with a single 319 // field. 320 if (NumOperands <= 3) { 321 uint64_t Cur = 322 NumOperands == 2 323 ? 0 324 : mdconst::extract<ConstantInt>(Operands[2])->getZExtValue(); 325 Offset -= Cur; 326 MDNode *P = dyn_cast_or_null<MDNode>(Operands[1]); 327 if (!P) 328 return TBAAStructTypeNode(); 329 return TBAAStructTypeNode(P); 330 } 331 } 332 333 // Assume the offsets are in order. We return the previous field if 334 // the current offset is bigger than the given offset. 335 unsigned FirstFieldOpNo = NewFormat ? 3 : 1; 336 unsigned NumOpsPerField = NewFormat ? 3 : 2; 337 unsigned TheIdx = 0; 338 339 for (unsigned Idx = FirstFieldOpNo; Idx < NumOperands; 340 Idx += NumOpsPerField) { 341 uint64_t Cur = 342 mdconst::extract<ConstantInt>(Operands[Idx + 1])->getZExtValue(); 343 if (Cur > Offset) { 344 assert(Idx >= FirstFieldOpNo + NumOpsPerField && 345 "TBAAStructTypeNode::getField should have an offset match!"); 346 TheIdx = Idx - NumOpsPerField; 347 break; 348 } 349 } 350 // Move along the last field. 351 if (TheIdx == 0) 352 TheIdx = NumOperands - NumOpsPerField; 353 uint64_t Cur = 354 mdconst::extract<ConstantInt>(Operands[TheIdx + 1])->getZExtValue(); 355 Offset -= Cur; 356 MDNode *P = dyn_cast_or_null<MDNode>(Operands[TheIdx]); 357 if (!P) 358 return TBAAStructTypeNode(); 359 return TBAAStructTypeNode(P); 360 } 361 }; 362 363 } // end anonymous namespace 364 365 /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat 366 /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA 367 /// format. 368 static bool isStructPathTBAA(const MDNode *MD) { 369 // Anonymous TBAA root starts with a MDNode and dragonegg uses it as 370 // a TBAA tag. 371 return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3; 372 } 373 374 AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA, 375 const MemoryLocation &LocB, 376 AAQueryInfo &AAQI, const Instruction *) { 377 if (!EnableTBAA) 378 return AAResultBase::alias(LocA, LocB, AAQI, nullptr); 379 380 // If accesses may alias, chain to the next AliasAnalysis. 381 if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA)) 382 return AAResultBase::alias(LocA, LocB, AAQI, nullptr); 383 384 // Otherwise return a definitive result. 385 return AliasResult::NoAlias; 386 } 387 388 ModRefInfo TypeBasedAAResult::getModRefInfoMask(const MemoryLocation &Loc, 389 AAQueryInfo &AAQI, 390 bool IgnoreLocals) { 391 if (!EnableTBAA) 392 return AAResultBase::getModRefInfoMask(Loc, AAQI, IgnoreLocals); 393 394 const MDNode *M = Loc.AATags.TBAA; 395 if (!M) 396 return AAResultBase::getModRefInfoMask(Loc, AAQI, IgnoreLocals); 397 398 // If this is an "immutable" type, we can assume the pointer is pointing 399 // to constant memory. 400 if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) || 401 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable())) 402 return ModRefInfo::NoModRef; 403 404 return AAResultBase::getModRefInfoMask(Loc, AAQI, IgnoreLocals); 405 } 406 407 MemoryEffects TypeBasedAAResult::getMemoryEffects(const CallBase *Call, 408 AAQueryInfo &AAQI) { 409 if (!EnableTBAA) 410 return AAResultBase::getMemoryEffects(Call, AAQI); 411 412 // If this is an "immutable" type, the access is not observable. 413 if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa)) 414 if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) || 415 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable())) 416 return MemoryEffects::none(); 417 418 return AAResultBase::getMemoryEffects(Call, AAQI); 419 } 420 421 MemoryEffects TypeBasedAAResult::getMemoryEffects(const Function *F) { 422 // Functions don't have metadata. Just chain to the next implementation. 423 return AAResultBase::getMemoryEffects(F); 424 } 425 426 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call, 427 const MemoryLocation &Loc, 428 AAQueryInfo &AAQI) { 429 if (!EnableTBAA) 430 return AAResultBase::getModRefInfo(Call, Loc, AAQI); 431 432 if (const MDNode *L = Loc.AATags.TBAA) 433 if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa)) 434 if (!Aliases(L, M)) 435 return ModRefInfo::NoModRef; 436 437 return AAResultBase::getModRefInfo(Call, Loc, AAQI); 438 } 439 440 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call1, 441 const CallBase *Call2, 442 AAQueryInfo &AAQI) { 443 if (!EnableTBAA) 444 return AAResultBase::getModRefInfo(Call1, Call2, AAQI); 445 446 if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa)) 447 if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa)) 448 if (!Aliases(M1, M2)) 449 return ModRefInfo::NoModRef; 450 451 return AAResultBase::getModRefInfo(Call1, Call2, AAQI); 452 } 453 454 bool MDNode::isTBAAVtableAccess() const { 455 if (!isStructPathTBAA(this)) { 456 if (getNumOperands() < 1) 457 return false; 458 if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) { 459 if (Tag1->getString() == "vtable pointer") 460 return true; 461 } 462 return false; 463 } 464 465 // For struct-path aware TBAA, we use the access type of the tag. 466 TBAAStructTagNode Tag(this); 467 TBAAStructTypeNode AccessType(Tag.getAccessType()); 468 if(auto *Id = dyn_cast<MDString>(AccessType.getId())) 469 if (Id->getString() == "vtable pointer") 470 return true; 471 return false; 472 } 473 474 static bool matchAccessTags(const MDNode *A, const MDNode *B, 475 const MDNode **GenericTag = nullptr); 476 477 MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { 478 const MDNode *GenericTag; 479 matchAccessTags(A, B, &GenericTag); 480 return const_cast<MDNode*>(GenericTag); 481 } 482 483 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) { 484 if (!A || !B) 485 return nullptr; 486 487 if (A == B) 488 return A; 489 490 SmallSetVector<const MDNode *, 4> PathA; 491 TBAANode TA(A); 492 while (TA.getNode()) { 493 if (!PathA.insert(TA.getNode())) 494 report_fatal_error("Cycle found in TBAA metadata."); 495 TA = TA.getParent(); 496 } 497 498 SmallSetVector<const MDNode *, 4> PathB; 499 TBAANode TB(B); 500 while (TB.getNode()) { 501 if (!PathB.insert(TB.getNode())) 502 report_fatal_error("Cycle found in TBAA metadata."); 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 AAMDNodes AAMDNodes::merge(const AAMDNodes &Other) const { 523 AAMDNodes Result; 524 Result.TBAA = MDNode::getMostGenericTBAA(TBAA, Other.TBAA); 525 Result.TBAAStruct = nullptr; 526 Result.Scope = MDNode::getMostGenericAliasScope(Scope, Other.Scope); 527 Result.NoAlias = MDNode::intersect(NoAlias, Other.NoAlias); 528 return Result; 529 } 530 531 AAMDNodes AAMDNodes::concat(const AAMDNodes &Other) const { 532 AAMDNodes Result; 533 Result.TBAA = Result.TBAAStruct = nullptr; 534 Result.Scope = MDNode::getMostGenericAliasScope(Scope, Other.Scope); 535 Result.NoAlias = MDNode::intersect(NoAlias, Other.NoAlias); 536 return Result; 537 } 538 539 static const MDNode *createAccessTag(const MDNode *AccessType) { 540 // If there is no access type or the access type is the root node, then 541 // we don't have any useful access tag to return. 542 if (!AccessType || AccessType->getNumOperands() < 2) 543 return nullptr; 544 545 Type *Int64 = IntegerType::get(AccessType->getContext(), 64); 546 auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0)); 547 548 if (TBAAStructTypeNode(AccessType).isNewFormat()) { 549 // TODO: Take access ranges into account when matching access tags and 550 // fix this code to generate actual access sizes for generic tags. 551 uint64_t AccessSize = UINT64_MAX; 552 auto *SizeNode = 553 ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize)); 554 Metadata *Ops[] = {const_cast<MDNode*>(AccessType), 555 const_cast<MDNode*>(AccessType), 556 OffsetNode, SizeNode}; 557 return MDNode::get(AccessType->getContext(), Ops); 558 } 559 560 Metadata *Ops[] = {const_cast<MDNode*>(AccessType), 561 const_cast<MDNode*>(AccessType), 562 OffsetNode}; 563 return MDNode::get(AccessType->getContext(), Ops); 564 } 565 566 static bool hasField(TBAAStructTypeNode BaseType, 567 TBAAStructTypeNode FieldType) { 568 for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) { 569 TBAAStructTypeNode T = BaseType.getFieldType(I); 570 if (T == FieldType || hasField(T, FieldType)) 571 return true; 572 } 573 return false; 574 } 575 576 /// Return true if for two given accesses, one of the accessed objects may be a 577 /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters 578 /// describe the accesses to the base object and the subobject respectively. 579 /// \p CommonType must be the metadata node describing the common type of the 580 /// accessed objects. On return, \p MayAlias is set to true iff these accesses 581 /// may alias and \p Generic, if not null, points to the most generic access 582 /// tag for the given two. 583 static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag, 584 TBAAStructTagNode SubobjectTag, 585 const MDNode *CommonType, 586 const MDNode **GenericTag, 587 bool &MayAlias) { 588 // If the base object is of the least common type, then this may be an access 589 // to its subobject. 590 if (BaseTag.getAccessType() == BaseTag.getBaseType() && 591 BaseTag.getAccessType() == CommonType) { 592 if (GenericTag) 593 *GenericTag = createAccessTag(CommonType); 594 MayAlias = true; 595 return true; 596 } 597 598 // If the access to the base object is through a field of the subobject's 599 // type, then this may be an access to that field. To check for that we start 600 // from the base type, follow the edge with the correct offset in the type DAG 601 // and adjust the offset until we reach the field type or until we reach the 602 // access type. 603 bool NewFormat = BaseTag.isNewFormat(); 604 TBAAStructTypeNode BaseType(BaseTag.getBaseType()); 605 uint64_t OffsetInBase = BaseTag.getOffset(); 606 607 for (;;) { 608 // In the old format there is no distinction between fields and parent 609 // types, so in this case we consider all nodes up to the root. 610 if (!BaseType.getNode()) { 611 assert(!NewFormat && "Did not see access type in access path!"); 612 break; 613 } 614 615 if (BaseType.getNode() == SubobjectTag.getBaseType()) { 616 bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset(); 617 if (GenericTag) { 618 *GenericTag = SameMemberAccess ? SubobjectTag.getNode() : 619 createAccessTag(CommonType); 620 } 621 MayAlias = SameMemberAccess; 622 return true; 623 } 624 625 // With new-format nodes we stop at the access type. 626 if (NewFormat && BaseType.getNode() == BaseTag.getAccessType()) 627 break; 628 629 // Follow the edge with the correct offset. Offset will be adjusted to 630 // be relative to the field type. 631 BaseType = BaseType.getField(OffsetInBase); 632 } 633 634 // If the base object has a direct or indirect field of the subobject's type, 635 // then this may be an access to that field. We need this to check now that 636 // we support aggregates as access types. 637 if (NewFormat) { 638 // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType()); 639 TBAAStructTypeNode FieldType(SubobjectTag.getBaseType()); 640 if (hasField(BaseType, FieldType)) { 641 if (GenericTag) 642 *GenericTag = createAccessTag(CommonType); 643 MayAlias = true; 644 return true; 645 } 646 } 647 648 return false; 649 } 650 651 /// matchTags - Return true if the given couple of accesses are allowed to 652 /// overlap. If \arg GenericTag is not null, then on return it points to the 653 /// most generic access descriptor for the given two. 654 static bool matchAccessTags(const MDNode *A, const MDNode *B, 655 const MDNode **GenericTag) { 656 if (A == B) { 657 if (GenericTag) 658 *GenericTag = A; 659 return true; 660 } 661 662 // Accesses with no TBAA information may alias with any other accesses. 663 if (!A || !B) { 664 if (GenericTag) 665 *GenericTag = nullptr; 666 return true; 667 } 668 669 // Verify that both input nodes are struct-path aware. Auto-upgrade should 670 // have taken care of this. 671 assert(isStructPathTBAA(A) && "Access A is not struct-path aware!"); 672 assert(isStructPathTBAA(B) && "Access B is not struct-path aware!"); 673 674 TBAAStructTagNode TagA(A), TagB(B); 675 const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(), 676 TagB.getAccessType()); 677 678 // If the final access types have different roots, they're part of different 679 // potentially unrelated type systems, so we must be conservative. 680 if (!CommonType) { 681 if (GenericTag) 682 *GenericTag = nullptr; 683 return true; 684 } 685 686 // If one of the accessed objects may be a subobject of the other, then such 687 // accesses may alias. 688 bool MayAlias; 689 if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB, 690 CommonType, GenericTag, MayAlias) || 691 mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA, 692 CommonType, GenericTag, MayAlias)) 693 return MayAlias; 694 695 // Otherwise, we've proved there's no alias. 696 if (GenericTag) 697 *GenericTag = createAccessTag(CommonType); 698 return false; 699 } 700 701 /// Aliases - Test whether the access represented by tag A may alias the 702 /// access represented by tag B. 703 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const { 704 return matchAccessTags(A, B); 705 } 706 707 AnalysisKey TypeBasedAA::Key; 708 709 TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) { 710 return TypeBasedAAResult(); 711 } 712 713 char TypeBasedAAWrapperPass::ID = 0; 714 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis", 715 false, true) 716 717 ImmutablePass *llvm::createTypeBasedAAWrapperPass() { 718 return new TypeBasedAAWrapperPass(); 719 } 720 721 TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) { 722 initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry()); 723 } 724 725 bool TypeBasedAAWrapperPass::doInitialization(Module &M) { 726 Result.reset(new TypeBasedAAResult()); 727 return false; 728 } 729 730 bool TypeBasedAAWrapperPass::doFinalization(Module &M) { 731 Result.reset(); 732 return false; 733 } 734 735 void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 736 AU.setPreservesAll(); 737 } 738 739 MDNode *AAMDNodes::shiftTBAA(MDNode *MD, size_t Offset) { 740 // Fast path if there's no offset 741 if (Offset == 0) 742 return MD; 743 // Fast path if there's no path tbaa node (and thus scalar) 744 if (!isStructPathTBAA(MD)) 745 return MD; 746 747 // The correct behavior here is to add the offset into the TBAA 748 // struct node offset. The base type, however may not have defined 749 // a type at this additional offset, resulting in errors. Since 750 // this method is only used within a given load/store access 751 // the offset provided is only used to subdivide the previous load 752 // maintaining the validity of the previous TBAA. 753 // 754 // This, however, should be revisited in the future. 755 return MD; 756 } 757 758 MDNode *AAMDNodes::shiftTBAAStruct(MDNode *MD, size_t Offset) { 759 // Fast path if there's no offset 760 if (Offset == 0) 761 return MD; 762 SmallVector<Metadata *, 3> Sub; 763 for (size_t i = 0, size = MD->getNumOperands(); i < size; i += 3) { 764 ConstantInt *InnerOffset = mdconst::extract<ConstantInt>(MD->getOperand(i)); 765 ConstantInt *InnerSize = 766 mdconst::extract<ConstantInt>(MD->getOperand(i + 1)); 767 // Don't include any triples that aren't in bounds 768 if (InnerOffset->getZExtValue() + InnerSize->getZExtValue() <= Offset) 769 continue; 770 771 uint64_t NewSize = InnerSize->getZExtValue(); 772 uint64_t NewOffset = InnerOffset->getZExtValue() - Offset; 773 if (InnerOffset->getZExtValue() < Offset) { 774 NewOffset = 0; 775 NewSize -= Offset - InnerOffset->getZExtValue(); 776 } 777 778 // Shift the offset of the triple 779 Sub.push_back(ConstantAsMetadata::get( 780 ConstantInt::get(InnerOffset->getType(), NewOffset))); 781 Sub.push_back(ConstantAsMetadata::get( 782 ConstantInt::get(InnerSize->getType(), NewSize))); 783 Sub.push_back(MD->getOperand(i + 2)); 784 } 785 return MDNode::get(MD->getContext(), Sub); 786 } 787 788 MDNode *AAMDNodes::extendToTBAA(MDNode *MD, ssize_t Len) { 789 // Fast path if 0-length 790 if (Len == 0) 791 return nullptr; 792 793 // Regular TBAA is invariant of length, so we only need to consider 794 // struct-path TBAA. 795 if (!isStructPathTBAA(MD)) 796 return MD; 797 798 TBAAStructTagNode Tag(MD); 799 800 // Only new format TBAA has a size 801 if (!Tag.isNewFormat()) 802 return MD; 803 804 // If unknown size, drop the TBAA. 805 if (Len == -1) 806 return nullptr; 807 808 // Otherwise, create TBAA with the new Len 809 ArrayRef<MDOperand> MDOperands = MD->operands(); 810 SmallVector<Metadata *, 4> NextNodes(MDOperands.begin(), MDOperands.end()); 811 ConstantInt *PreviousSize = mdconst::extract<ConstantInt>(NextNodes[3]); 812 813 // Don't create a new MDNode if it is the same length. 814 if (PreviousSize->equalsInt(Len)) 815 return MD; 816 817 NextNodes[3] = 818 ConstantAsMetadata::get(ConstantInt::get(PreviousSize->getType(), Len)); 819 return MDNode::get(MD->getContext(), NextNodes); 820 } 821