LLVM  7.0.0svn
TypeBasedAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the TypeBasedAliasAnalysis pass, which implements
11 // metadata-based TBAA.
12 //
13 // In LLVM IR, memory does not have types, so LLVM's own type system is not
14 // suitable for doing TBAA. Instead, metadata is added to the IR to describe
15 // a type system of a higher level language. This can be used to implement
16 // typical C/C++ TBAA, but it can also be used to implement custom alias
17 // analysis behavior for other languages.
18 //
19 // We now support two types of metadata format: scalar TBAA and struct-path
20 // aware TBAA. After all testing cases are upgraded to use struct-path aware
21 // TBAA and we can auto-upgrade existing bc files, the support for scalar TBAA
22 // can be dropped.
23 //
24 // The scalar TBAA metadata format is very simple. TBAA MDNodes have up to
25 // three fields, e.g.:
26 // !0 = !{ !"an example type tree" }
27 // !1 = !{ !"int", !0 }
28 // !2 = !{ !"float", !0 }
29 // !3 = !{ !"const float", !2, i64 1 }
30 //
31 // The first field is an identity field. It can be any value, usually
32 // an MDString, which uniquely identifies the type. The most important
33 // name in the tree is the name of the root node. Two trees with
34 // different root node names are entirely disjoint, even if they
35 // have leaves with common names.
36 //
37 // The second field identifies the type's parent node in the tree, or
38 // is null or omitted for a root node. A type is considered to alias
39 // all of its descendants and all of its ancestors in the tree. Also,
40 // a type is considered to alias all types in other trees, so that
41 // bitcode produced from multiple front-ends is handled conservatively.
42 //
43 // If the third field is present, it's an integer which if equal to 1
44 // indicates that the type is "constant" (meaning pointsToConstantMemory
45 // should return true; see
46 // http://llvm.org/docs/AliasAnalysis.html#OtherItfs).
47 //
48 // With struct-path aware TBAA, the MDNodes attached to an instruction using
49 // "!tbaa" are called path tag nodes.
50 //
51 // The path tag node has 4 fields with the last field being optional.
52 //
53 // The first field is the base type node, it can be a struct type node
54 // or a scalar type node. The second field is the access type node, it
55 // must be a scalar type node. The third field is the offset into the base type.
56 // The last field has the same meaning as the last field of our scalar TBAA:
57 // it's an integer which if equal to 1 indicates that the access is "constant".
58 //
59 // The struct type node has a name and a list of pairs, one pair for each member
60 // of the struct. The first element of each pair is a type node (a struct type
61 // node or a scalar type node), specifying the type of the member, the second
62 // element of each pair is the offset of the member.
63 //
64 // Given an example
65 // typedef struct {
66 // short s;
67 // } A;
68 // typedef struct {
69 // uint16_t s;
70 // A a;
71 // } B;
72 //
73 // For an access to B.a.s, we attach !5 (a path tag node) to the load/store
74 // instruction. The base type is !4 (struct B), the access type is !2 (scalar
75 // type short) and the offset is 4.
76 //
77 // !0 = !{!"Simple C/C++ TBAA"}
78 // !1 = !{!"omnipotent char", !0} // Scalar type node
79 // !2 = !{!"short", !1} // Scalar type node
80 // !3 = !{!"A", !2, i64 0} // Struct type node
81 // !4 = !{!"B", !2, i64 0, !3, i64 4}
82 // // Struct type node
83 // !5 = !{!4, !2, i64 4} // Path tag node
84 //
85 // The struct type nodes and the scalar type nodes form a type DAG.
86 // Root (!0)
87 // char (!1) -- edge to Root
88 // short (!2) -- edge to char
89 // A (!3) -- edge with offset 0 to short
90 // B (!4) -- edge with offset 0 to short and edge with offset 4 to A
91 //
92 // To check if two tags (tagX and tagY) can alias, we start from the base type
93 // of tagX, follow the edge with the correct offset in the type DAG and adjust
94 // the offset until we reach the base type of tagY or until we reach the Root
95 // node.
96 // If we reach the base type of tagY, compare the adjusted offset with
97 // offset of tagY, return Alias if the offsets are the same, return NoAlias
98 // otherwise.
99 // If we reach the Root node, perform the above starting from base type of tagY
100 // to see if we reach base type of tagX.
101 //
102 // If they have different roots, they're part of different potentially
103 // unrelated type systems, so we return Alias to be conservative.
104 // If neither node is an ancestor of the other and they have the same root,
105 // then we say NoAlias.
106 //
107 //===----------------------------------------------------------------------===//
108 
110 #include "llvm/ADT/SetVector.h"
113 #include "llvm/IR/Constants.h"
114 #include "llvm/IR/DerivedTypes.h"
115 #include "llvm/IR/Instruction.h"
116 #include "llvm/IR/LLVMContext.h"
117 #include "llvm/IR/Metadata.h"
118 #include "llvm/Pass.h"
119 #include "llvm/Support/Casting.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  if (NewFormat) {
307  // New-format root and scalar type nodes have no fields.
308  if (Node->getNumOperands() < 6)
309  return TBAAStructTypeNode();
310  } else {
311  // Parent can be omitted for the root node.
312  if (Node->getNumOperands() < 2)
313  return TBAAStructTypeNode();
314 
315  // Fast path for a scalar type node and a struct type node with a single
316  // field.
317  if (Node->getNumOperands() <= 3) {
318  uint64_t Cur = Node->getNumOperands() == 2
319  ? 0
320  : mdconst::extract<ConstantInt>(Node->getOperand(2))
321  ->getZExtValue();
322  Offset -= Cur;
323  MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
324  if (!P)
325  return TBAAStructTypeNode();
326  return TBAAStructTypeNode(P);
327  }
328  }
329 
330  // Assume the offsets are in order. We return the previous field if
331  // the current offset is bigger than the given offset.
332  unsigned FirstFieldOpNo = NewFormat ? 3 : 1;
333  unsigned NumOpsPerField = NewFormat ? 3 : 2;
334  unsigned TheIdx = 0;
335  for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands();
336  Idx += NumOpsPerField) {
337  uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
338  ->getZExtValue();
339  if (Cur > Offset) {
340  assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
341  "TBAAStructTypeNode::getField should have an offset match!");
342  TheIdx = Idx - NumOpsPerField;
343  break;
344  }
345  }
346  // Move along the last field.
347  if (TheIdx == 0)
348  TheIdx = Node->getNumOperands() - NumOpsPerField;
349  uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
350  ->getZExtValue();
351  Offset -= Cur;
352  MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
353  if (!P)
354  return TBAAStructTypeNode();
355  return TBAAStructTypeNode(P);
356  }
357 };
358 
359 } // end anonymous namespace
360 
361 /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat
362 /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA
363 /// format.
364 static bool isStructPathTBAA(const MDNode *MD) {
365  // Anonymous TBAA root starts with a MDNode and dragonegg uses it as
366  // a TBAA tag.
367  return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
368 }
369 
371  const MemoryLocation &LocB) {
372  if (!EnableTBAA)
373  return AAResultBase::alias(LocA, LocB);
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);
378 
379  // Otherwise return a definitive result.
380  return NoAlias;
381 }
382 
384  bool OrLocal) {
385  if (!EnableTBAA)
386  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
387 
388  const MDNode *M = Loc.AATags.TBAA;
389  if (!M)
390  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
391 
392  // If this is an "immutable" type, we can assume the pointer is pointing
393  // to constant memory.
394  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
395  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
396  return true;
397 
398  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
399 }
400 
403  if (!EnableTBAA)
405 
407 
408  // If this is an "immutable" type, we can assume the call doesn't write
409  // to memory.
411  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
412  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
413  Min = FMRB_OnlyReadsMemory;
414 
416 }
417 
419  // Functions don't have metadata. Just chain to the next implementation.
421 }
422 
424  const MemoryLocation &Loc) {
425  if (!EnableTBAA)
426  return AAResultBase::getModRefInfo(CS, Loc);
427 
428  if (const MDNode *L = Loc.AATags.TBAA)
429  if (const MDNode *M =
431  if (!Aliases(L, M))
432  return ModRefInfo::NoModRef;
433 
434  return AAResultBase::getModRefInfo(CS, Loc);
435 }
436 
438  ImmutableCallSite CS2) {
439  if (!EnableTBAA)
440  return AAResultBase::getModRefInfo(CS1, CS2);
441 
442  if (const MDNode *M1 =
444  if (const MDNode *M2 =
446  if (!Aliases(M1, M2))
447  return ModRefInfo::NoModRef;
448 
449  return AAResultBase::getModRefInfo(CS1, CS2);
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 =
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 =
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:659
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:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
MDNode * TBAA
The tag for type-based alias analysis.
Definition: Metadata.h:656
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal)
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:923
This file contains the declarations for metadata subclasses.
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
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:862
F(f)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
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.
InstrTy * getInstruction() const
Definition: CallSite.h:92
bool isTBAAVtableAccess() const
Check whether MDNode is a vtable access.
#define UINT64_MAX
Definition: DataTypes.h:83
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
LLVMContext & getContext() const
Definition: Metadata.h:922
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.
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:200
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:910
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:408
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:211
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
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:1164
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
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:46
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
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
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:87
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:240
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
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:642
MDNode * NoAlias
The tag specifying the noalias scope.
Definition: Metadata.h:662
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:621
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.
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.
Establish a view to a call site for examination.
Definition: CallSite.h:714
#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()
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
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:602
A container for analyses that lazily runs them and caches their results.
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1960
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
Root of the metadata hierarchy.
Definition: Metadata.h:58
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 pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal)
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...