LLVM  10.0.0svn
TypeBasedAliasAnalysis.cpp
Go to the documentation of this file.
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 
109 #include "llvm/ADT/SetVector.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"
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 
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 
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 
404  if (!EnableTBAA)
405  return AAResultBase::getModRefBehavior(Call);
406 
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 
417 }
418 
420  // Functions don't have metadata. Just chain to the next implementation.
422 }
423 
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 
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 
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 
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 
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 
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 
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)
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 
713  return TypeBasedAAResult();
714 }
715 
717 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
718  false, true)
719 
721  return new TypeBasedAAWrapperPass();
722 }
723 
726 }
727 
729  Result.reset(new TypeBasedAAResult());
730  return false;
731 }
732 
734  Result.reset();
735  return false;
736 }
737 
739  AU.setPreservesAll();
740 }
static const MDNode * createAccessTag(const MDNode *AccessType)
The access neither references nor modifies the value stored in memory.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
MDNode * Scope
The tag for alias scope specification (used with noalias).
Definition: Metadata.h:660
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
MDNode * TBAA
The tag for type-based alias analysis.
Definition: Metadata.h:657
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:922
This class stores info we want to provide to or retain within an alias query.
This file contains the declarations for metadata subclasses.
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
static enum BaseType getBaseType(const Value *Val)
Return the baseType for Val which states whether Val is exclusively derived from constant/null, or not exclusively derived from constant.
Metadata node.
Definition: Metadata.h:863
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
void initializeTypeBasedAAWrapperPassPass(PassRegistry &)
TypeBasedAAResult run(Function &F, FunctionAnalysisManager &AM)
This indicates that the function could not be classified into one of the behaviors above...
Legacy wrapper pass to provide the TypeBasedAAResult object.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
bool isTBAAVtableAccess() const
Check whether MDNode is a vtable access.
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
#define UINT64_MAX
Definition: DataTypes.h:83
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
LLVMContext & getContext() const
Definition: Metadata.h:923
static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag, TBAAStructTagNode SubobjectTag, const MDNode *CommonType, const MDNode **GenericTag, bool &MayAlias)
Return true if for two given accesses, one of the accessed objects may be a subobject of the other...
FunctionModRefBehavior
Summary of how a function affects memory in the program.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:234
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:909
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:409
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This is the interface for a metadata-based TBAA.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static const MDNode * getLeastCommonType(const MDNode *A, const MDNode *B)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Represent the analysis usage information of a pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A simple AA result that uses TBAA metadata to answer queries.
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
R600 Clause Merge
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
Representation for a specific memory location.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:239
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:255
INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis", false, true) ImmutablePass *llvm
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:643
MDNode * NoAlias
The tag specifying the noalias scope.
Definition: Metadata.h:663
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:653
static bool matchAccessTags(const MDNode *A, const MDNode *B, const MDNode **GenericTag=nullptr)
matchTags - Return true if the given couple of accesses are allowed to overlap.
This function does not perform any non-local stores or volatile loads, but may read from any memory l...
void setPreservesAll()
Set by analyses that do not transform their input at all.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
This file provides utility analysis objects describing memory locations.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static MemAccessTy getAccessType(const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)
Return the type of the memory being accessed.
ImmutablePass * createTypeBasedAAWrapperPass()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool hasField(TBAAStructTypeNode BaseType, TBAAStructTypeNode FieldType)
static const Function * getParent(const Value *V)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
A single uniqued string.
Definition: Metadata.h:603
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1973
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
Root of the metadata hierarchy.
Definition: Metadata.h:57
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
static cl::opt< bool > EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden)
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
static bool isStructPathTBAA(const MDNode *MD)
Check the first operand of the tbaa tag node, if it is a MDNode, we treat it as struct-path aware TBA...