LLVM  9.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  if (!EnableTBAA)
372  return AAResultBase::alias(LocA, LocB);
373 
374  // If accesses may alias, chain to the next AliasAnalysis.
375  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
376  return AAResultBase::alias(LocA, LocB);
377 
378  // Otherwise return a definitive result.
379  return NoAlias;
380 }
381 
383  bool OrLocal) {
384  if (!EnableTBAA)
385  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
386 
387  const MDNode *M = Loc.AATags.TBAA;
388  if (!M)
389  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
390 
391  // If this is an "immutable" type, we can assume the pointer is pointing
392  // to constant memory.
393  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
394  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
395  return true;
396 
397  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
398 }
399 
402  if (!EnableTBAA)
403  return AAResultBase::getModRefBehavior(Call);
404 
406 
407  // If this is an "immutable" type, we can assume the call doesn't write
408  // to memory.
409  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
410  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
411  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
412  Min = FMRB_OnlyReadsMemory;
413 
415 }
416 
418  // Functions don't have metadata. Just chain to the next implementation.
420 }
421 
423  const MemoryLocation &Loc) {
424  if (!EnableTBAA)
425  return AAResultBase::getModRefInfo(Call, Loc);
426 
427  if (const MDNode *L = Loc.AATags.TBAA)
428  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
429  if (!Aliases(L, M))
430  return ModRefInfo::NoModRef;
431 
432  return AAResultBase::getModRefInfo(Call, Loc);
433 }
434 
436  const CallBase *Call2) {
437  if (!EnableTBAA)
438  return AAResultBase::getModRefInfo(Call1, Call2);
439 
440  if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))
441  if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))
442  if (!Aliases(M1, M2))
443  return ModRefInfo::NoModRef;
444 
445  return AAResultBase::getModRefInfo(Call1, Call2);
446 }
447 
449  if (!isStructPathTBAA(this)) {
450  if (getNumOperands() < 1)
451  return false;
452  if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
453  if (Tag1->getString() == "vtable pointer")
454  return true;
455  }
456  return false;
457  }
458 
459  // For struct-path aware TBAA, we use the access type of the tag.
460  TBAAStructTagNode Tag(this);
461  TBAAStructTypeNode AccessType(Tag.getAccessType());
462  if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
463  if (Id->getString() == "vtable pointer")
464  return true;
465  return false;
466 }
467 
468 static bool matchAccessTags(const MDNode *A, const MDNode *B,
469  const MDNode **GenericTag = nullptr);
470 
472  const MDNode *GenericTag;
473  matchAccessTags(A, B, &GenericTag);
474  return const_cast<MDNode*>(GenericTag);
475 }
476 
477 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
478  if (!A || !B)
479  return nullptr;
480 
481  if (A == B)
482  return A;
483 
485  TBAANode TA(A);
486  while (TA.getNode()) {
487  if (PathA.count(TA.getNode()))
488  report_fatal_error("Cycle found in TBAA metadata.");
489  PathA.insert(TA.getNode());
490  TA = TA.getParent();
491  }
492 
494  TBAANode TB(B);
495  while (TB.getNode()) {
496  if (PathB.count(TB.getNode()))
497  report_fatal_error("Cycle found in TBAA metadata.");
498  PathB.insert(TB.getNode());
499  TB = TB.getParent();
500  }
501 
502  int IA = PathA.size() - 1;
503  int IB = PathB.size() - 1;
504 
505  const MDNode *Ret = nullptr;
506  while (IA >= 0 && IB >= 0) {
507  if (PathA[IA] == PathB[IB])
508  Ret = PathA[IA];
509  else
510  break;
511  --IA;
512  --IB;
513  }
514 
515  return Ret;
516 }
517 
519  if (Merge)
520  N.TBAA =
522  else
523  N.TBAA = getMetadata(LLVMContext::MD_tbaa);
524 
525  if (Merge)
527  N.Scope, getMetadata(LLVMContext::MD_alias_scope));
528  else
529  N.Scope = getMetadata(LLVMContext::MD_alias_scope);
530 
531  if (Merge)
532  N.NoAlias =
534  else
535  N.NoAlias = getMetadata(LLVMContext::MD_noalias);
536 }
537 
538 static const MDNode *createAccessTag(const MDNode *AccessType) {
539  // If there is no access type or the access type is the root node, then
540  // we don't have any useful access tag to return.
541  if (!AccessType || AccessType->getNumOperands() < 2)
542  return nullptr;
543 
544  Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
545  auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
546 
547  if (TBAAStructTypeNode(AccessType).isNewFormat()) {
548  // TODO: Take access ranges into account when matching access tags and
549  // fix this code to generate actual access sizes for generic tags.
550  uint64_t AccessSize = UINT64_MAX;
551  auto *SizeNode =
552  ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
553  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
554  const_cast<MDNode*>(AccessType),
555  OffsetNode, SizeNode};
556  return MDNode::get(AccessType->getContext(), Ops);
557  }
558 
559  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
560  const_cast<MDNode*>(AccessType),
561  OffsetNode};
562  return MDNode::get(AccessType->getContext(), Ops);
563 }
564 
565 static bool hasField(TBAAStructTypeNode BaseType,
566  TBAAStructTypeNode FieldType) {
567  for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {
568  TBAAStructTypeNode T = BaseType.getFieldType(I);
569  if (T == FieldType || hasField(T, FieldType))
570  return true;
571  }
572  return false;
573 }
574 
575 /// Return true if for two given accesses, one of the accessed objects may be a
576 /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
577 /// describe the accesses to the base object and the subobject respectively.
578 /// \p CommonType must be the metadata node describing the common type of the
579 /// accessed objects. On return, \p MayAlias is set to true iff these accesses
580 /// may alias and \p Generic, if not null, points to the most generic access
581 /// tag for the given two.
582 static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
583  TBAAStructTagNode SubobjectTag,
584  const MDNode *CommonType,
585  const MDNode **GenericTag,
586  bool &MayAlias) {
587  // If the base object is of the least common type, then this may be an access
588  // to its subobject.
589  if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
590  BaseTag.getAccessType() == CommonType) {
591  if (GenericTag)
592  *GenericTag = createAccessTag(CommonType);
593  MayAlias = true;
594  return true;
595  }
596 
597  // If the access to the base object is through a field of the subobject's
598  // type, then this may be an access to that field. To check for that we start
599  // from the base type, follow the edge with the correct offset in the type DAG
600  // and adjust the offset until we reach the field type or until we reach the
601  // access type.
602  bool NewFormat = BaseTag.isNewFormat();
603  TBAAStructTypeNode BaseType(BaseTag.getBaseType());
604  uint64_t OffsetInBase = BaseTag.getOffset();
605 
606  for (;;) {
607  // In the old format there is no distinction between fields and parent
608  // types, so in this case we consider all nodes up to the root.
609  if (!BaseType.getNode()) {
610  assert(!NewFormat && "Did not see access type in access path!");
611  break;
612  }
613 
614  if (BaseType.getNode() == SubobjectTag.getBaseType()) {
615  bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
616  if (GenericTag) {
617  *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
618  createAccessTag(CommonType);
619  }
620  MayAlias = SameMemberAccess;
621  return true;
622  }
623 
624  // With new-format nodes we stop at the access type.
625  if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
626  break;
627 
628  // Follow the edge with the correct offset. Offset will be adjusted to
629  // be relative to the field type.
630  BaseType = BaseType.getField(OffsetInBase);
631  }
632 
633  // If the base object has a direct or indirect field of the subobject's type,
634  // then this may be an access to that field. We need this to check now that
635  // we support aggregates as access types.
636  if (NewFormat) {
637  // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
638  TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
639  if (hasField(BaseType, FieldType)) {
640  if (GenericTag)
641  *GenericTag = createAccessTag(CommonType);
642  MayAlias = true;
643  return true;
644  }
645  }
646 
647  return false;
648 }
649 
650 /// matchTags - Return true if the given couple of accesses are allowed to
651 /// overlap. If \arg GenericTag is not null, then on return it points to the
652 /// most generic access descriptor for the given two.
653 static bool matchAccessTags(const MDNode *A, const MDNode *B,
654  const MDNode **GenericTag) {
655  if (A == B) {
656  if (GenericTag)
657  *GenericTag = A;
658  return true;
659  }
660 
661  // Accesses with no TBAA information may alias with any other accesses.
662  if (!A || !B) {
663  if (GenericTag)
664  *GenericTag = nullptr;
665  return true;
666  }
667 
668  // Verify that both input nodes are struct-path aware. Auto-upgrade should
669  // have taken care of this.
670  assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
671  assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
672 
673  TBAAStructTagNode TagA(A), TagB(B);
674  const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
675  TagB.getAccessType());
676 
677  // If the final access types have different roots, they're part of different
678  // potentially unrelated type systems, so we must be conservative.
679  if (!CommonType) {
680  if (GenericTag)
681  *GenericTag = nullptr;
682  return true;
683  }
684 
685  // If one of the accessed objects may be a subobject of the other, then such
686  // accesses may alias.
687  bool MayAlias;
688  if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
689  CommonType, GenericTag, MayAlias) ||
690  mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
691  CommonType, GenericTag, MayAlias))
692  return MayAlias;
693 
694  // Otherwise, we've proved there's no alias.
695  if (GenericTag)
696  *GenericTag = createAccessTag(CommonType);
697  return false;
698 }
699 
700 /// Aliases - Test whether the access represented by tag A may alias the
701 /// access represented by tag B.
702 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
703  return matchAccessTags(A, B);
704 }
705 
706 AnalysisKey TypeBasedAA::Key;
707 
709  return TypeBasedAAResult();
710 }
711 
713 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
714  false, true)
715 
717  return new TypeBasedAAWrapperPass();
718 }
719 
722 }
723 
725  Result.reset(new TypeBasedAAResult());
726  return false;
727 }
728 
730  Result.reset();
731  return false;
732 }
733 
735  AU.setPreservesAll();
736 }
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:64
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal)
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:922
This file contains the declarations for metadata subclasses.
The two locations do not alias at all.
Definition: AliasAnalysis.h:83
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:1014
F(f)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
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.
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
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
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: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:77
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:422
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:85
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
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
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.
#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(const CallBase *Call, 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:603
A container for analyses that lazily runs them and caches their results.
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1966
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
Root of the metadata hierarchy.
Definition: Metadata.h:57
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...