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/Instruction.h" 116 #include "llvm/IR/LLVMContext.h" 117 #include "llvm/IR/Metadata.h" 118 #include "llvm/InitializePasses.h" 119 #include "llvm/Pass.h" 120 #include "llvm/Support/Casting.h" 121 #include "llvm/Support/CommandLine.h" 122 #include "llvm/Support/ErrorHandling.h" 123 #include <cassert> 124 #include <cstdint> 125 126 using namespace llvm; 127 128 // A handy option for disabling TBAA functionality. The same effect can also be 129 // achieved by stripping the !tbaa tags from IR, but this option is sometimes 130 // more convenient. 131 static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden); 132 133 namespace { 134 135 /// isNewFormatTypeNode - Return true iff the given type node is in the new 136 /// size-aware format. 137 static bool isNewFormatTypeNode(const MDNode *N) { 138 if (N->getNumOperands() < 3) 139 return false; 140 // In the old format the first operand is a string. 141 if (!isa<MDNode>(N->getOperand(0))) 142 return false; 143 return true; 144 } 145 146 /// This is a simple wrapper around an MDNode which provides a higher-level 147 /// interface by hiding the details of how alias analysis information is encoded 148 /// in its operands. 149 template<typename MDNodeTy> 150 class TBAANodeImpl { 151 MDNodeTy *Node = nullptr; 152 153 public: 154 TBAANodeImpl() = default; 155 explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {} 156 157 /// getNode - Get the MDNode for this TBAANode. 158 MDNodeTy *getNode() const { return Node; } 159 160 /// isNewFormat - Return true iff the wrapped type node is in the new 161 /// size-aware format. 162 bool isNewFormat() const { return isNewFormatTypeNode(Node); } 163 164 /// getParent - Get this TBAANode's Alias tree parent. 165 TBAANodeImpl<MDNodeTy> getParent() const { 166 if (isNewFormat()) 167 return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0))); 168 169 if (Node->getNumOperands() < 2) 170 return TBAANodeImpl<MDNodeTy>(); 171 MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1)); 172 if (!P) 173 return TBAANodeImpl<MDNodeTy>(); 174 // Ok, this node has a valid parent. Return it. 175 return TBAANodeImpl<MDNodeTy>(P); 176 } 177 178 /// Test if this TBAANode represents a type for objects which are 179 /// not modified (by any means) in the context where this 180 /// AliasAnalysis is relevant. 181 bool isTypeImmutable() const { 182 if (Node->getNumOperands() < 3) 183 return false; 184 ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2)); 185 if (!CI) 186 return false; 187 return CI->getValue()[0]; 188 } 189 }; 190 191 /// \name Specializations of \c TBAANodeImpl for const and non const qualified 192 /// \c MDNode. 193 /// @{ 194 using TBAANode = TBAANodeImpl<const MDNode>; 195 using MutableTBAANode = TBAANodeImpl<MDNode>; 196 /// @} 197 198 /// This is a simple wrapper around an MDNode which provides a 199 /// higher-level interface by hiding the details of how alias analysis 200 /// information is encoded in its operands. 201 template<typename MDNodeTy> 202 class TBAAStructTagNodeImpl { 203 /// This node should be created with createTBAAAccessTag(). 204 MDNodeTy *Node; 205 206 public: 207 explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {} 208 209 /// Get the MDNode for this TBAAStructTagNode. 210 MDNodeTy *getNode() const { return Node; } 211 212 /// isNewFormat - Return true iff the wrapped access tag is in the new 213 /// size-aware format. 214 bool isNewFormat() const { 215 if (Node->getNumOperands() < 4) 216 return false; 217 if (MDNodeTy *AccessType = getAccessType()) 218 if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat()) 219 return false; 220 return true; 221 } 222 223 MDNodeTy *getBaseType() const { 224 return dyn_cast_or_null<MDNode>(Node->getOperand(0)); 225 } 226 227 MDNodeTy *getAccessType() const { 228 return dyn_cast_or_null<MDNode>(Node->getOperand(1)); 229 } 230 231 uint64_t getOffset() const { 232 return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue(); 233 } 234 235 uint64_t getSize() const { 236 if (!isNewFormat()) 237 return UINT64_MAX; 238 return mdconst::extract<ConstantInt>(Node->getOperand(3))->getZExtValue(); 239 } 240 241 /// Test if this TBAAStructTagNode represents a type for objects 242 /// which are not modified (by any means) in the context where this 243 /// AliasAnalysis is relevant. 244 bool isTypeImmutable() const { 245 unsigned OpNo = isNewFormat() ? 4 : 3; 246 if (Node->getNumOperands() < OpNo + 1) 247 return false; 248 ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(OpNo)); 249 if (!CI) 250 return false; 251 return CI->getValue()[0]; 252 } 253 }; 254 255 /// \name Specializations of \c TBAAStructTagNodeImpl for const and non const 256 /// qualified \c MDNods. 257 /// @{ 258 using TBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>; 259 using MutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>; 260 /// @} 261 262 /// This is a simple wrapper around an MDNode which provides a 263 /// higher-level interface by hiding the details of how alias analysis 264 /// information is encoded in its operands. 265 class TBAAStructTypeNode { 266 /// This node should be created with createTBAATypeNode(). 267 const MDNode *Node = nullptr; 268 269 public: 270 TBAAStructTypeNode() = default; 271 explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} 272 273 /// Get the MDNode for this TBAAStructTypeNode. 274 const MDNode *getNode() const { return Node; } 275 276 /// isNewFormat - Return true iff the wrapped type node is in the new 277 /// size-aware format. 278 bool isNewFormat() const { return isNewFormatTypeNode(Node); } 279 280 bool operator==(const TBAAStructTypeNode &Other) const { 281 return getNode() == Other.getNode(); 282 } 283 284 /// getId - Return type identifier. 285 Metadata *getId() const { 286 return Node->getOperand(isNewFormat() ? 2 : 0); 287 } 288 289 unsigned getNumFields() const { 290 unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; 291 unsigned NumOpsPerField = isNewFormat() ? 3 : 2; 292 return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField; 293 } 294 295 TBAAStructTypeNode getFieldType(unsigned FieldIndex) const { 296 unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; 297 unsigned NumOpsPerField = isNewFormat() ? 3 : 2; 298 unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField; 299 auto *TypeNode = cast<MDNode>(getNode()->getOperand(OpIndex)); 300 return TBAAStructTypeNode(TypeNode); 301 } 302 303 /// Get this TBAAStructTypeNode's field in the type DAG with 304 /// given offset. Update the offset to be relative to the field type. 305 TBAAStructTypeNode getField(uint64_t &Offset) const { 306 bool NewFormat = isNewFormat(); 307 if (NewFormat) { 308 // New-format root and scalar type nodes have no fields. 309 if (Node->getNumOperands() < 6) 310 return TBAAStructTypeNode(); 311 } else { 312 // Parent can be omitted for the root node. 313 if (Node->getNumOperands() < 2) 314 return TBAAStructTypeNode(); 315 316 // Fast path for a scalar type node and a struct type node with a single 317 // field. 318 if (Node->getNumOperands() <= 3) { 319 uint64_t Cur = Node->getNumOperands() == 2 320 ? 0 321 : mdconst::extract<ConstantInt>(Node->getOperand(2)) 322 ->getZExtValue(); 323 Offset -= Cur; 324 MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 325 if (!P) 326 return TBAAStructTypeNode(); 327 return TBAAStructTypeNode(P); 328 } 329 } 330 331 // Assume the offsets are in order. We return the previous field if 332 // the current offset is bigger than the given offset. 333 unsigned FirstFieldOpNo = NewFormat ? 3 : 1; 334 unsigned NumOpsPerField = NewFormat ? 3 : 2; 335 unsigned TheIdx = 0; 336 for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands(); 337 Idx += NumOpsPerField) { 338 uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1)) 339 ->getZExtValue(); 340 if (Cur > Offset) { 341 assert(Idx >= FirstFieldOpNo + NumOpsPerField && 342 "TBAAStructTypeNode::getField should have an offset match!"); 343 TheIdx = Idx - NumOpsPerField; 344 break; 345 } 346 } 347 // Move along the last field. 348 if (TheIdx == 0) 349 TheIdx = Node->getNumOperands() - NumOpsPerField; 350 uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1)) 351 ->getZExtValue(); 352 Offset -= Cur; 353 MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx)); 354 if (!P) 355 return TBAAStructTypeNode(); 356 return TBAAStructTypeNode(P); 357 } 358 }; 359 360 } // end anonymous namespace 361 362 /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat 363 /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA 364 /// format. 365 static bool isStructPathTBAA(const MDNode *MD) { 366 // Anonymous TBAA root starts with a MDNode and dragonegg uses it as 367 // a TBAA tag. 368 return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3; 369 } 370 371 AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA, 372 const MemoryLocation &LocB, 373 AAQueryInfo &AAQI) { 374 if (!EnableTBAA) 375 return AAResultBase::alias(LocA, LocB, AAQI); 376 377 // If accesses may alias, chain to the next AliasAnalysis. 378 if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA)) 379 return AAResultBase::alias(LocA, LocB, AAQI); 380 381 // Otherwise return a definitive result. 382 return NoAlias; 383 } 384 385 bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc, 386 AAQueryInfo &AAQI, 387 bool OrLocal) { 388 if (!EnableTBAA) 389 return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); 390 391 const MDNode *M = Loc.AATags.TBAA; 392 if (!M) 393 return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); 394 395 // If this is an "immutable" type, we can assume the pointer is pointing 396 // to constant memory. 397 if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) || 398 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable())) 399 return true; 400 401 return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); 402 } 403 404 FunctionModRefBehavior 405 TypeBasedAAResult::getModRefBehavior(const CallBase *Call) { 406 if (!EnableTBAA) 407 return AAResultBase::getModRefBehavior(Call); 408 409 FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; 410 411 // If this is an "immutable" type, we can assume the call doesn't write 412 // to memory. 413 if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa)) 414 if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) || 415 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable())) 416 Min = FMRB_OnlyReadsMemory; 417 418 return FunctionModRefBehavior(AAResultBase::getModRefBehavior(Call) & Min); 419 } 420 421 FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) { 422 // Functions don't have metadata. Just chain to the next implementation. 423 return AAResultBase::getModRefBehavior(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.count(TA.getNode())) 494 report_fatal_error("Cycle found in TBAA metadata."); 495 PathA.insert(TA.getNode()); 496 TA = TA.getParent(); 497 } 498 499 SmallSetVector<const MDNode *, 4> PathB; 500 TBAANode TB(B); 501 while (TB.getNode()) { 502 if (PathB.count(TB.getNode())) 503 report_fatal_error("Cycle found in TBAA metadata."); 504 PathB.insert(TB.getNode()); 505 TB = TB.getParent(); 506 } 507 508 int IA = PathA.size() - 1; 509 int IB = PathB.size() - 1; 510 511 const MDNode *Ret = nullptr; 512 while (IA >= 0 && IB >= 0) { 513 if (PathA[IA] == PathB[IB]) 514 Ret = PathA[IA]; 515 else 516 break; 517 --IA; 518 --IB; 519 } 520 521 return Ret; 522 } 523 524 void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const { 525 if (Merge) { 526 N.TBAA = 527 MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa)); 528 N.TBAAStruct = nullptr; 529 N.Scope = MDNode::getMostGenericAliasScope( 530 N.Scope, getMetadata(LLVMContext::MD_alias_scope)); 531 N.NoAlias = 532 MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias)); 533 } else { 534 N.TBAA = getMetadata(LLVMContext::MD_tbaa); 535 N.TBAAStruct = getMetadata(LLVMContext::MD_tbaa_struct); 536 N.Scope = getMetadata(LLVMContext::MD_alias_scope); 537 N.NoAlias = getMetadata(LLVMContext::MD_noalias); 538 } 539 } 540 541 static const MDNode *createAccessTag(const MDNode *AccessType) { 542 // If there is no access type or the access type is the root node, then 543 // we don't have any useful access tag to return. 544 if (!AccessType || AccessType->getNumOperands() < 2) 545 return nullptr; 546 547 Type *Int64 = IntegerType::get(AccessType->getContext(), 64); 548 auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0)); 549 550 if (TBAAStructTypeNode(AccessType).isNewFormat()) { 551 // TODO: Take access ranges into account when matching access tags and 552 // fix this code to generate actual access sizes for generic tags. 553 uint64_t AccessSize = UINT64_MAX; 554 auto *SizeNode = 555 ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize)); 556 Metadata *Ops[] = {const_cast<MDNode*>(AccessType), 557 const_cast<MDNode*>(AccessType), 558 OffsetNode, SizeNode}; 559 return MDNode::get(AccessType->getContext(), Ops); 560 } 561 562 Metadata *Ops[] = {const_cast<MDNode*>(AccessType), 563 const_cast<MDNode*>(AccessType), 564 OffsetNode}; 565 return MDNode::get(AccessType->getContext(), Ops); 566 } 567 568 static bool hasField(TBAAStructTypeNode BaseType, 569 TBAAStructTypeNode FieldType) { 570 for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) { 571 TBAAStructTypeNode T = BaseType.getFieldType(I); 572 if (T == FieldType || hasField(T, FieldType)) 573 return true; 574 } 575 return false; 576 } 577 578 /// Return true if for two given accesses, one of the accessed objects may be a 579 /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters 580 /// describe the accesses to the base object and the subobject respectively. 581 /// \p CommonType must be the metadata node describing the common type of the 582 /// accessed objects. On return, \p MayAlias is set to true iff these accesses 583 /// may alias and \p Generic, if not null, points to the most generic access 584 /// tag for the given two. 585 static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag, 586 TBAAStructTagNode SubobjectTag, 587 const MDNode *CommonType, 588 const MDNode **GenericTag, 589 bool &MayAlias) { 590 // If the base object is of the least common type, then this may be an access 591 // to its subobject. 592 if (BaseTag.getAccessType() == BaseTag.getBaseType() && 593 BaseTag.getAccessType() == CommonType) { 594 if (GenericTag) 595 *GenericTag = createAccessTag(CommonType); 596 MayAlias = true; 597 return true; 598 } 599 600 // If the access to the base object is through a field of the subobject's 601 // type, then this may be an access to that field. To check for that we start 602 // from the base type, follow the edge with the correct offset in the type DAG 603 // and adjust the offset until we reach the field type or until we reach the 604 // access type. 605 bool NewFormat = BaseTag.isNewFormat(); 606 TBAAStructTypeNode BaseType(BaseTag.getBaseType()); 607 uint64_t OffsetInBase = BaseTag.getOffset(); 608 609 for (;;) { 610 // In the old format there is no distinction between fields and parent 611 // types, so in this case we consider all nodes up to the root. 612 if (!BaseType.getNode()) { 613 assert(!NewFormat && "Did not see access type in access path!"); 614 break; 615 } 616 617 if (BaseType.getNode() == SubobjectTag.getBaseType()) { 618 bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset(); 619 if (GenericTag) { 620 *GenericTag = SameMemberAccess ? SubobjectTag.getNode() : 621 createAccessTag(CommonType); 622 } 623 MayAlias = SameMemberAccess; 624 return true; 625 } 626 627 // With new-format nodes we stop at the access type. 628 if (NewFormat && BaseType.getNode() == BaseTag.getAccessType()) 629 break; 630 631 // Follow the edge with the correct offset. Offset will be adjusted to 632 // be relative to the field type. 633 BaseType = BaseType.getField(OffsetInBase); 634 } 635 636 // If the base object has a direct or indirect field of the subobject's type, 637 // then this may be an access to that field. We need this to check now that 638 // we support aggregates as access types. 639 if (NewFormat) { 640 // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType()); 641 TBAAStructTypeNode FieldType(SubobjectTag.getBaseType()); 642 if (hasField(BaseType, FieldType)) { 643 if (GenericTag) 644 *GenericTag = createAccessTag(CommonType); 645 MayAlias = true; 646 return true; 647 } 648 } 649 650 return false; 651 } 652 653 /// matchTags - Return true if the given couple of accesses are allowed to 654 /// overlap. If \arg GenericTag is not null, then on return it points to the 655 /// most generic access descriptor for the given two. 656 static bool matchAccessTags(const MDNode *A, const MDNode *B, 657 const MDNode **GenericTag) { 658 if (A == B) { 659 if (GenericTag) 660 *GenericTag = A; 661 return true; 662 } 663 664 // Accesses with no TBAA information may alias with any other accesses. 665 if (!A || !B) { 666 if (GenericTag) 667 *GenericTag = nullptr; 668 return true; 669 } 670 671 // Verify that both input nodes are struct-path aware. Auto-upgrade should 672 // have taken care of this. 673 assert(isStructPathTBAA(A) && "Access A is not struct-path aware!"); 674 assert(isStructPathTBAA(B) && "Access B is not struct-path aware!"); 675 676 TBAAStructTagNode TagA(A), TagB(B); 677 const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(), 678 TagB.getAccessType()); 679 680 // If the final access types have different roots, they're part of different 681 // potentially unrelated type systems, so we must be conservative. 682 if (!CommonType) { 683 if (GenericTag) 684 *GenericTag = nullptr; 685 return true; 686 } 687 688 // If one of the accessed objects may be a subobject of the other, then such 689 // accesses may alias. 690 bool MayAlias; 691 if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB, 692 CommonType, GenericTag, MayAlias) || 693 mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA, 694 CommonType, GenericTag, MayAlias)) 695 return MayAlias; 696 697 // Otherwise, we've proved there's no alias. 698 if (GenericTag) 699 *GenericTag = createAccessTag(CommonType); 700 return false; 701 } 702 703 /// Aliases - Test whether the access represented by tag A may alias the 704 /// access represented by tag B. 705 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const { 706 return matchAccessTags(A, B); 707 } 708 709 AnalysisKey TypeBasedAA::Key; 710 711 TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) { 712 return TypeBasedAAResult(); 713 } 714 715 char TypeBasedAAWrapperPass::ID = 0; 716 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis", 717 false, true) 718 719 ImmutablePass *llvm::createTypeBasedAAWrapperPass() { 720 return new TypeBasedAAWrapperPass(); 721 } 722 723 TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) { 724 initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry()); 725 } 726 727 bool TypeBasedAAWrapperPass::doInitialization(Module &M) { 728 Result.reset(new TypeBasedAAResult()); 729 return false; 730 } 731 732 bool TypeBasedAAWrapperPass::doFinalization(Module &M) { 733 Result.reset(); 734 return false; 735 } 736 737 void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 738 AU.setPreservesAll(); 739 } 740 741 MDNode *AAMDNodes::ShiftTBAA(MDNode *MD, size_t Offset) { 742 // Fast path if there's no offset 743 if (Offset == 0) 744 return MD; 745 // Fast path if there's no path tbaa node (and thus scalar) 746 if (!isStructPathTBAA(MD)) 747 return MD; 748 749 TBAAStructTagNode Tag(MD); 750 SmallVector<Metadata *, 5> Sub; 751 Sub.push_back(MD->getOperand(0)); 752 Sub.push_back(MD->getOperand(1)); 753 ConstantInt *InnerOffset = mdconst::extract<ConstantInt>(MD->getOperand(2)); 754 755 if (Tag.isNewFormat()) { 756 ConstantInt *InnerSize = mdconst::extract<ConstantInt>(MD->getOperand(3)); 757 758 if (InnerOffset->getZExtValue() + InnerSize->getZExtValue() <= Offset) { 759 return nullptr; 760 } 761 762 uint64_t NewSize = InnerSize->getZExtValue(); 763 uint64_t NewOffset = InnerOffset->getZExtValue() - Offset; 764 if (InnerOffset->getZExtValue() < Offset) { 765 NewOffset = 0; 766 NewSize -= Offset - InnerOffset->getZExtValue(); 767 } 768 769 Sub.push_back(ConstantAsMetadata::get( 770 ConstantInt::get(InnerOffset->getType(), NewOffset))); 771 772 Sub.push_back(ConstantAsMetadata::get( 773 ConstantInt::get(InnerSize->getType(), NewSize))); 774 775 // immutable type 776 if (MD->getNumOperands() >= 5) 777 Sub.push_back(MD->getOperand(4)); 778 } else { 779 if (InnerOffset->getZExtValue() < Offset) 780 return nullptr; 781 782 Sub.push_back(ConstantAsMetadata::get(ConstantInt::get( 783 InnerOffset->getType(), InnerOffset->getZExtValue() - Offset))); 784 785 // immutable type 786 if (MD->getNumOperands() >= 4) 787 Sub.push_back(MD->getOperand(3)); 788 } 789 return MDNode::get(MD->getContext(), Sub); 790 } 791 792 MDNode *AAMDNodes::ShiftTBAAStruct(MDNode *MD, size_t Offset) { 793 // Fast path if there's no offset 794 if (Offset == 0) 795 return MD; 796 SmallVector<Metadata *, 3> Sub; 797 for (size_t i = 0, size = MD->getNumOperands(); i < size; i += 3) { 798 ConstantInt *InnerOffset = mdconst::extract<ConstantInt>(MD->getOperand(i)); 799 ConstantInt *InnerSize = 800 mdconst::extract<ConstantInt>(MD->getOperand(i + 1)); 801 // Don't include any triples that aren't in bounds 802 if (InnerOffset->getZExtValue() + InnerSize->getZExtValue() <= Offset) 803 continue; 804 805 uint64_t NewSize = InnerSize->getZExtValue(); 806 uint64_t NewOffset = InnerOffset->getZExtValue() - Offset; 807 if (InnerOffset->getZExtValue() < Offset) { 808 NewOffset = 0; 809 NewSize -= Offset - InnerOffset->getZExtValue(); 810 } 811 812 // Shift the offset of the triple 813 Sub.push_back(ConstantAsMetadata::get( 814 ConstantInt::get(InnerOffset->getType(), NewOffset))); 815 Sub.push_back(ConstantAsMetadata::get( 816 ConstantInt::get(InnerSize->getType(), NewSize))); 817 Sub.push_back(MD->getOperand(i + 2)); 818 } 819 return MDNode::get(MD->getContext(), Sub); 820 }