[InstCombine] Signed saturation tests. NFC
[llvm-complete.git] / lib / Analysis / TypeBasedAliasAnalysis.cpp
blob3b9040aa0f52a47acc6c4370d5ae397040bd82de
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.
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.
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.
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 }
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.
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.
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).
47 // With struct-path aware TBAA, the MDNodes attached to an instruction using
48 // "!tbaa" are called path tag nodes.
50 // The path tag node has 4 fields with the last field being optional.
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".
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.
63 // Given an example
64 // typedef struct {
65 // short s;
66 // } A;
67 // typedef struct {
68 // uint16_t s;
69 // A a;
70 // } B;
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.
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
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
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.
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.
106 //===----------------------------------------------------------------------===//
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>
124 using namespace llvm;
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);
131 namespace {
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;
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;
151 public:
152 TBAANodeImpl() = default;
153 explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
155 /// getNode - Get the MDNode for this TBAANode.
156 MDNodeTy *getNode() const { return Node; }
158 /// isNewFormat - Return true iff the wrapped type node is in the new
159 /// size-aware format.
160 bool isNewFormat() const { return isNewFormatTypeNode(Node); }
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)));
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);
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];
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 /// @}
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;
204 public:
205 explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
207 /// Get the MDNode for this TBAAStructTagNode.
208 MDNodeTy *getNode() const { return Node; }
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;
221 MDNodeTy *getBaseType() const {
222 return dyn_cast_or_null<MDNode>(Node->getOperand(0));
225 MDNodeTy *getAccessType() const {
226 return dyn_cast_or_null<MDNode>(Node->getOperand(1));
229 uint64_t getOffset() const {
230 return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue();
233 uint64_t getSize() const {
234 if (!isNewFormat())
235 return UINT64_MAX;
236 return mdconst::extract<ConstantInt>(Node->getOperand(3))->getZExtValue();
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];
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 /// @}
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;
267 public:
268 TBAAStructTypeNode() = default;
269 explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
271 /// Get the MDNode for this TBAAStructTypeNode.
272 const MDNode *getNode() const { return Node; }
274 /// isNewFormat - Return true iff the wrapped type node is in the new
275 /// size-aware format.
276 bool isNewFormat() const { return isNewFormatTypeNode(Node); }
278 bool operator==(const TBAAStructTypeNode &Other) const {
279 return getNode() == Other.getNode();
282 /// getId - Return type identifier.
283 Metadata *getId() const {
284 return Node->getOperand(isNewFormat() ? 2 : 0);
287 unsigned getNumFields() const {
288 unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
289 unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
290 return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;
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);
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();
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
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);
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;
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);
358 } // end anonymous namespace
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;
369 AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,
370 const MemoryLocation &LocB,
371 AAQueryInfo &AAQI) {
372 if (!EnableTBAA)
373 return AAResultBase::alias(LocA, LocB, AAQI);
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);
379 // Otherwise return a definitive result.
380 return NoAlias;
383 bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
384 AAQueryInfo &AAQI,
385 bool OrLocal) {
386 if (!EnableTBAA)
387 return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
389 const MDNode *M = Loc.AATags.TBAA;
390 if (!M)
391 return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
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;
399 return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
402 FunctionModRefBehavior
403 TypeBasedAAResult::getModRefBehavior(const CallBase *Call) {
404 if (!EnableTBAA)
405 return AAResultBase::getModRefBehavior(Call);
407 FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
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;
416 return FunctionModRefBehavior(AAResultBase::getModRefBehavior(Call) & Min);
419 FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) {
420 // Functions don't have metadata. Just chain to the next implementation.
421 return AAResultBase::getModRefBehavior(F);
424 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call,
425 const MemoryLocation &Loc,
426 AAQueryInfo &AAQI) {
427 if (!EnableTBAA)
428 return AAResultBase::getModRefInfo(Call, Loc, AAQI);
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;
435 return AAResultBase::getModRefInfo(Call, Loc, AAQI);
438 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call1,
439 const CallBase *Call2,
440 AAQueryInfo &AAQI) {
441 if (!EnableTBAA)
442 return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
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;
449 return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
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;
460 return false;
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;
472 static bool matchAccessTags(const MDNode *A, const MDNode *B,
473 const MDNode **GenericTag = nullptr);
475 MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
476 const MDNode *GenericTag;
477 matchAccessTags(A, B, &GenericTag);
478 return const_cast<MDNode*>(GenericTag);
481 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
482 if (!A || !B)
483 return nullptr;
485 if (A == B)
486 return A;
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();
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();
506 int IA = PathA.size() - 1;
507 int IB = PathB.size() - 1;
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;
519 return Ret;
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);
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);
535 if (Merge)
536 N.NoAlias =
537 MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
538 else
539 N.NoAlias = getMetadata(LLVMContext::MD_noalias);
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;
548 Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
549 auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
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);
563 Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
564 const_cast<MDNode*>(AccessType),
565 OffsetNode};
566 return MDNode::get(AccessType->getContext(), Ops);
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;
576 return false;
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;
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();
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;
618 if (BaseType.getNode() == SubobjectTag.getBaseType()) {
619 bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
620 if (GenericTag) {
621 *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
622 createAccessTag(CommonType);
624 MayAlias = SameMemberAccess;
625 return true;
628 // With new-format nodes we stop at the access type.
629 if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
630 break;
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);
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;
651 return false;
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;
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;
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!");
677 TBAAStructTagNode TagA(A), TagB(B);
678 const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
679 TagB.getAccessType());
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;
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;
698 // Otherwise, we've proved there's no alias.
699 if (GenericTag)
700 *GenericTag = createAccessTag(CommonType);
701 return false;
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);
710 AnalysisKey TypeBasedAA::Key;
712 TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) {
713 return TypeBasedAAResult();
716 char TypeBasedAAWrapperPass::ID = 0;
717 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
718 false, true)
720 ImmutablePass *llvm::createTypeBasedAAWrapperPass() {
721 return new TypeBasedAAWrapperPass();
724 TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) {
725 initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry());
728 bool TypeBasedAAWrapperPass::doInitialization(Module &M) {
729 Result.reset(new TypeBasedAAResult());
730 return false;
733 bool TypeBasedAAWrapperPass::doFinalization(Module &M) {
734 Result.reset();
735 return false;
738 void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
739 AU.setPreservesAll();