LLVM  15.0.0git
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/InstrTypes.h"
115 #include "llvm/IR/LLVMContext.h"
116 #include "llvm/IR/Metadata.h"
117 #include "llvm/InitializePasses.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  AAQueryInfo &AAQI) {
373  if (!EnableTBAA)
374  return AAResultBase::alias(LocA, LocB, AAQI);
375 
376  // If accesses may alias, chain to the next AliasAnalysis.
377  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
378  return AAResultBase::alias(LocA, LocB, AAQI);
379 
380  // Otherwise return a definitive result.
381  return AliasResult::NoAlias;
382 }
383 
385  AAQueryInfo &AAQI,
386  bool OrLocal) {
387  if (!EnableTBAA)
388  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
389 
390  const MDNode *M = Loc.AATags.TBAA;
391  if (!M)
392  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
393 
394  // If this is an "immutable" type, we can assume the pointer is pointing
395  // to constant memory.
396  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
397  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
398  return true;
399 
400  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
401 }
402 
405  if (!EnableTBAA)
406  return AAResultBase::getModRefBehavior(Call);
407 
409 
410  // If this is an "immutable" type, we can assume the call doesn't write
411  // to memory.
412  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
413  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
414  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
415  Min = FMRB_OnlyReadsMemory;
416 
418 }
419 
421  // Functions don't have metadata. Just chain to the next implementation.
423 }
424 
426  const MemoryLocation &Loc,
427  AAQueryInfo &AAQI) {
428  if (!EnableTBAA)
429  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
430 
431  if (const MDNode *L = Loc.AATags.TBAA)
432  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
433  if (!Aliases(L, M))
434  return ModRefInfo::NoModRef;
435 
436  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
437 }
438 
440  const CallBase *Call2,
441  AAQueryInfo &AAQI) {
442  if (!EnableTBAA)
443  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
444 
445  if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))
446  if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))
447  if (!Aliases(M1, M2))
448  return ModRefInfo::NoModRef;
449 
450  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
451 }
452 
454  if (!isStructPathTBAA(this)) {
455  if (getNumOperands() < 1)
456  return false;
457  if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
458  if (Tag1->getString() == "vtable pointer")
459  return true;
460  }
461  return false;
462  }
463 
464  // For struct-path aware TBAA, we use the access type of the tag.
465  TBAAStructTagNode Tag(this);
466  TBAAStructTypeNode AccessType(Tag.getAccessType());
467  if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
468  if (Id->getString() == "vtable pointer")
469  return true;
470  return false;
471 }
472 
473 static bool matchAccessTags(const MDNode *A, const MDNode *B,
474  const MDNode **GenericTag = nullptr);
475 
477  const MDNode *GenericTag;
478  matchAccessTags(A, B, &GenericTag);
479  return const_cast<MDNode*>(GenericTag);
480 }
481 
482 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
483  if (!A || !B)
484  return nullptr;
485 
486  if (A == B)
487  return A;
488 
490  TBAANode TA(A);
491  while (TA.getNode()) {
492  if (PathA.count(TA.getNode()))
493  report_fatal_error("Cycle found in TBAA metadata.");
494  PathA.insert(TA.getNode());
495  TA = TA.getParent();
496  }
497 
499  TBAANode TB(B);
500  while (TB.getNode()) {
501  if (PathB.count(TB.getNode()))
502  report_fatal_error("Cycle found in TBAA metadata.");
503  PathB.insert(TB.getNode());
504  TB = TB.getParent();
505  }
506 
507  int IA = PathA.size() - 1;
508  int IB = PathB.size() - 1;
509 
510  const MDNode *Ret = nullptr;
511  while (IA >= 0 && IB >= 0) {
512  if (PathA[IA] == PathB[IB])
513  Ret = PathA[IA];
514  else
515  break;
516  --IA;
517  --IB;
518  }
519 
520  return Ret;
521 }
522 
523 AAMDNodes AAMDNodes::merge(const AAMDNodes &Other) const {
524  AAMDNodes Result;
525  Result.TBAA = MDNode::getMostGenericTBAA(TBAA, Other.TBAA);
526  Result.TBAAStruct = nullptr;
527  Result.Scope = MDNode::getMostGenericAliasScope(Scope, Other.Scope);
528  Result.NoAlias = MDNode::intersect(NoAlias, Other.NoAlias);
529  return Result;
530 }
531 
532 AAMDNodes AAMDNodes::concat(const AAMDNodes &Other) const {
533  AAMDNodes Result;
534  Result.TBAA = Result.TBAAStruct = nullptr;
535  Result.Scope = MDNode::getMostGenericAliasScope(Scope, Other.Scope);
536  Result.NoAlias = MDNode::intersect(NoAlias, Other.NoAlias);
537  return Result;
538 }
539 
540 static const MDNode *createAccessTag(const MDNode *AccessType) {
541  // If there is no access type or the access type is the root node, then
542  // we don't have any useful access tag to return.
543  if (!AccessType || AccessType->getNumOperands() < 2)
544  return nullptr;
545 
546  Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
547  auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
548 
549  if (TBAAStructTypeNode(AccessType).isNewFormat()) {
550  // TODO: Take access ranges into account when matching access tags and
551  // fix this code to generate actual access sizes for generic tags.
552  uint64_t AccessSize = UINT64_MAX;
553  auto *SizeNode =
554  ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
555  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
556  const_cast<MDNode*>(AccessType),
557  OffsetNode, SizeNode};
558  return MDNode::get(AccessType->getContext(), Ops);
559  }
560 
561  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
562  const_cast<MDNode*>(AccessType),
563  OffsetNode};
564  return MDNode::get(AccessType->getContext(), Ops);
565 }
566 
567 static bool hasField(TBAAStructTypeNode BaseType,
568  TBAAStructTypeNode FieldType) {
569  for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {
570  TBAAStructTypeNode T = BaseType.getFieldType(I);
571  if (T == FieldType || hasField(T, FieldType))
572  return true;
573  }
574  return false;
575 }
576 
577 /// Return true if for two given accesses, one of the accessed objects may be a
578 /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
579 /// describe the accesses to the base object and the subobject respectively.
580 /// \p CommonType must be the metadata node describing the common type of the
581 /// accessed objects. On return, \p MayAlias is set to true iff these accesses
582 /// may alias and \p Generic, if not null, points to the most generic access
583 /// tag for the given two.
584 static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
585  TBAAStructTagNode SubobjectTag,
586  const MDNode *CommonType,
587  const MDNode **GenericTag,
588  bool &MayAlias) {
589  // If the base object is of the least common type, then this may be an access
590  // to its subobject.
591  if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
592  BaseTag.getAccessType() == CommonType) {
593  if (GenericTag)
594  *GenericTag = createAccessTag(CommonType);
595  MayAlias = true;
596  return true;
597  }
598 
599  // If the access to the base object is through a field of the subobject's
600  // type, then this may be an access to that field. To check for that we start
601  // from the base type, follow the edge with the correct offset in the type DAG
602  // and adjust the offset until we reach the field type or until we reach the
603  // access type.
604  bool NewFormat = BaseTag.isNewFormat();
605  TBAAStructTypeNode BaseType(BaseTag.getBaseType());
606  uint64_t OffsetInBase = BaseTag.getOffset();
607 
608  for (;;) {
609  // In the old format there is no distinction between fields and parent
610  // types, so in this case we consider all nodes up to the root.
611  if (!BaseType.getNode()) {
612  assert(!NewFormat && "Did not see access type in access path!");
613  break;
614  }
615 
616  if (BaseType.getNode() == SubobjectTag.getBaseType()) {
617  bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
618  if (GenericTag) {
619  *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
620  createAccessTag(CommonType);
621  }
622  MayAlias = SameMemberAccess;
623  return true;
624  }
625 
626  // With new-format nodes we stop at the access type.
627  if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
628  break;
629 
630  // Follow the edge with the correct offset. Offset will be adjusted to
631  // be relative to the field type.
632  BaseType = BaseType.getField(OffsetInBase);
633  }
634 
635  // If the base object has a direct or indirect field of the subobject's type,
636  // then this may be an access to that field. We need this to check now that
637  // we support aggregates as access types.
638  if (NewFormat) {
639  // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
640  TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
641  if (hasField(BaseType, FieldType)) {
642  if (GenericTag)
643  *GenericTag = createAccessTag(CommonType);
644  MayAlias = true;
645  return true;
646  }
647  }
648 
649  return false;
650 }
651 
652 /// matchTags - Return true if the given couple of accesses are allowed to
653 /// overlap. If \arg GenericTag is not null, then on return it points to the
654 /// most generic access descriptor for the given two.
655 static bool matchAccessTags(const MDNode *A, const MDNode *B,
656  const MDNode **GenericTag) {
657  if (A == B) {
658  if (GenericTag)
659  *GenericTag = A;
660  return true;
661  }
662 
663  // Accesses with no TBAA information may alias with any other accesses.
664  if (!A || !B) {
665  if (GenericTag)
666  *GenericTag = nullptr;
667  return true;
668  }
669 
670  // Verify that both input nodes are struct-path aware. Auto-upgrade should
671  // have taken care of this.
672  assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
673  assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
674 
675  TBAAStructTagNode TagA(A), TagB(B);
676  const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
677  TagB.getAccessType());
678 
679  // If the final access types have different roots, they're part of different
680  // potentially unrelated type systems, so we must be conservative.
681  if (!CommonType) {
682  if (GenericTag)
683  *GenericTag = nullptr;
684  return true;
685  }
686 
687  // If one of the accessed objects may be a subobject of the other, then such
688  // accesses may alias.
689  bool MayAlias;
690  if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
691  CommonType, GenericTag, MayAlias) ||
692  mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
693  CommonType, GenericTag, MayAlias))
694  return MayAlias;
695 
696  // Otherwise, we've proved there's no alias.
697  if (GenericTag)
698  *GenericTag = createAccessTag(CommonType);
699  return false;
700 }
701 
702 /// Aliases - Test whether the access represented by tag A may alias the
703 /// access represented by tag B.
704 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
705  return matchAccessTags(A, B);
706 }
707 
708 AnalysisKey TypeBasedAA::Key;
709 
711  return TypeBasedAAResult();
712 }
713 
715 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
716  false, true)
717 
719  return new TypeBasedAAWrapperPass();
720 }
721 
724 }
725 
727  Result.reset(new TypeBasedAAResult());
728  return false;
729 }
730 
732  Result.reset();
733  return false;
734 }
735 
737  AU.setPreservesAll();
738 }
739 
740 MDNode *AAMDNodes::shiftTBAA(MDNode *MD, size_t Offset) {
741  // Fast path if there's no offset
742  if (Offset == 0)
743  return MD;
744  // Fast path if there's no path tbaa node (and thus scalar)
745  if (!isStructPathTBAA(MD))
746  return MD;
747 
748  // The correct behavior here is to add the offset into the TBAA
749  // struct node offset. The base type, however may not have defined
750  // a type at this additional offset, resulting in errors. Since
751  // this method is only used within a given load/store access
752  // the offset provided is only used to subdivide the previous load
753  // maintaining the validity of the previous TBAA.
754  //
755  // This, however, should be revisited in the future.
756  return MD;
757 }
758 
760  // Fast path if there's no offset
761  if (Offset == 0)
762  return MD;
764  for (size_t i = 0, size = MD->getNumOperands(); i < size; i += 3) {
765  ConstantInt *InnerOffset = mdconst::extract<ConstantInt>(MD->getOperand(i));
766  ConstantInt *InnerSize =
767  mdconst::extract<ConstantInt>(MD->getOperand(i + 1));
768  // Don't include any triples that aren't in bounds
769  if (InnerOffset->getZExtValue() + InnerSize->getZExtValue() <= Offset)
770  continue;
771 
772  uint64_t NewSize = InnerSize->getZExtValue();
773  uint64_t NewOffset = InnerOffset->getZExtValue() - Offset;
774  if (InnerOffset->getZExtValue() < Offset) {
775  NewOffset = 0;
776  NewSize -= Offset - InnerOffset->getZExtValue();
777  }
778 
779  // Shift the offset of the triple
780  Sub.push_back(ConstantAsMetadata::get(
781  ConstantInt::get(InnerOffset->getType(), NewOffset)));
782  Sub.push_back(ConstantAsMetadata::get(
783  ConstantInt::get(InnerSize->getType(), NewSize)));
784  Sub.push_back(MD->getOperand(i + 2));
785  }
786  return MDNode::get(MD->getContext(), Sub);
787 }
788 
790  // Fast path if 0-length
791  if (Len == 0)
792  return nullptr;
793 
794  // Regular TBAA is invariant of length, so we only need to consider
795  // struct-path TBAA.
796  if (!isStructPathTBAA(MD))
797  return MD;
798 
799  TBAAStructTagNode Tag(MD);
800 
801  // Only new format TBAA has a size
802  if (!Tag.isNewFormat())
803  return MD;
804 
805  // If unknown size, drop the TBAA.
806  if (Len == -1)
807  return nullptr;
808 
809  // Otherwise, create TBAA with the new Len
810  SmallVector<Metadata *, 4> NextNodes(MD->operands());
811  ConstantInt *PreviousSize = mdconst::extract<ConstantInt>(NextNodes[3]);
812 
813  // Don't create a new MDNode if it is the same length.
814  if (PreviousSize->equalsInt(Len))
815  return MD;
816 
817  NextNodes[3] =
818  ConstantAsMetadata::get(ConstantInt::get(PreviousSize->getType(), Len));
819  return MDNode::get(MD->getContext(), NextNodes);
820 }
i
i
Definition: README.txt:29
TypeBasedAliasAnalysis.h
llvm::TypeBasedAAResult::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Definition: TypeBasedAliasAnalysis.cpp:425
llvm::ModRefInfo::NoModRef
@ NoModRef
The access neither references nor modifies the value stored in memory.
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
createAccessTag
static const MDNode * createAccessTag(const MDNode *AccessType)
Definition: TypeBasedAliasAnalysis.cpp:540
llvm::AAMDNodes::extendToTBAA
static MDNode * extendToTBAA(MDNode *TBAA, ssize_t len)
Definition: TypeBasedAliasAnalysis.cpp:789
Metadata.h
llvm::ConstantInt::getType
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:173
llvm::X86II::TA
@ TA
Definition: X86BaseInfo.h:808
llvm::TypeBasedAAWrapperPass::doFinalization
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: TypeBasedAliasAnalysis.cpp:731
llvm::ImmutablePass
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:279
llvm::TypeBasedAA::run
TypeBasedAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: TypeBasedAliasAnalysis.cpp:710
T
llvm::Function
Definition: Function.h:60
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::X86II::TB
@ TB
Definition: X86BaseInfo.h:805
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::TypeBasedAAWrapperPass::TypeBasedAAWrapperPass
TypeBasedAAWrapperPass()
Definition: TypeBasedAliasAnalysis.cpp:722
ErrorHandling.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
mayBeAccessToSubobjectOf
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.
Definition: TypeBasedAliasAnalysis.cpp:584
llvm::TypeBasedAAResult
A simple AA result that uses TBAA metadata to answer queries.
Definition: TypeBasedAliasAnalysis.h:31
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
llvm::ConstantAsMetadata::get
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:420
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
hasField
static bool hasField(TBAAStructTypeNode BaseType, TBAAStructTypeNode FieldType)
Definition: TypeBasedAliasAnalysis.cpp:567
llvm::AAMDNodes::Scope
MDNode * Scope
The tag for alias scope specification (used with noalias).
Definition: Metadata.h:675
llvm::dwarf::Tag
Tag
Definition: Dwarf.h:105
BaseType
llvm::FMRB_UnknownModRefBehavior
@ FMRB_UnknownModRefBehavior
This indicates that the function could not be classified into one of the behaviors above.
Definition: AliasAnalysis.h:368
llvm::getOffset
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
Definition: RuntimeDyld.cpp:174
llvm::TypeBasedAAWrapperPass::doInitialization
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: TypeBasedAliasAnalysis.cpp:726
OpIndex
unsigned OpIndex
Definition: SPIRVModuleAnalysis.cpp:41
getBaseType
static enum BaseType getBaseType(const Value *Val)
Return the baseType for Val which states whether Val is exclusively derived from constant/null,...
Definition: SafepointIRVerifier.cpp:326
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1384
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1276
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1284
AliasAnalysis.h
llvm::AAMDNodes::shiftTBAA
static MDNode * shiftTBAA(MDNode *M, size_t off)
Definition: TypeBasedAliasAnalysis.cpp:740
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:462
CommandLine.h
llvm::MemoryLocation::AATags
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
Definition: MemoryLocation.h:231
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
InstrTypes.h
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
UINT64_MAX
#define UINT64_MAX
Definition: DataTypes.h:77
llvm::ConstantInt::equalsInt
bool equalsInt(uint64_t V) const
A helper method that can be used to determine if the constant contained within is equal to a constant...
Definition: Constants.h:168
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:143
llvm::ConstantInt::get
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:924
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:279
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1222
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1278
llvm::TypeBasedAAWrapperPass
Legacy wrapper pass to provide the TypeBasedAAResult object.
Definition: TypeBasedAliasAnalysis.h:71
llvm::cl::opt< bool >
getLeastCommonType
static const MDNode * getLeastCommonType(const MDNode *A, const MDNode *B)
Definition: TypeBasedAliasAnalysis.cpp:482
BaseType
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
Definition: SafepointIRVerifier.cpp:314
llvm::TypeBasedAAWrapperPass::ID
static char ID
Definition: TypeBasedAliasAnalysis.h:75
llvm::MDNode::intersect
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1026
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
uint64_t
llvm::TypeBasedAAWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: TypeBasedAliasAnalysis.cpp:736
isStructPathTBAA
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...
Definition: TypeBasedAliasAnalysis.cpp:364
MemoryLocation.h
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::MDNode::getMostGenericTBAA
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
Definition: TypeBasedAliasAnalysis.cpp:476
llvm::TypeBasedAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: TypeBasedAliasAnalysis.cpp:370
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:148
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1990
llvm::createTypeBasedAAWrapperPass
ImmutablePass * createTypeBasedAAWrapperPass()
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
llvm::AAResultBase::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Definition: AliasAnalysis.h:1236
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::TypeBasedAAResult::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Definition: TypeBasedAliasAnalysis.cpp:404
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1598
llvm::initializeTypeBasedAAWrapperPassPass
void initializeTypeBasedAAWrapperPassPass(PassRegistry &)
llvm::AAMDNodes::merge
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
Definition: TypeBasedAliasAnalysis.cpp:523
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:845
llvm::FMRB_OnlyReadsMemory
@ FMRB_OnlyReadsMemory
This function does not perform any non-local stores or volatile loads, but may read from any memory l...
Definition: AliasAnalysis.h:357
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
llvm::MDNode::getMostGenericAliasScope
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1039
llvm::FunctionModRefBehavior
FunctionModRefBehavior
Summary of how a function affects memory in the program.
Definition: AliasAnalysis.h:262
llvm::MDNode::isTBAAVtableAccess
bool isTBAAVtableAccess() const
Check whether MDNode is a vtable access.
Definition: TypeBasedAliasAnalysis.cpp:453
llvm::AAResultBase::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1244
llvm::ConstantInt::getZExtValue
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:142
llvm::MDNode::getContext
LLVMContext & getContext() const
Definition: Metadata.h:1094
INITIALIZE_PASS
INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis", false, true) ImmutablePass *llvm
Definition: TypeBasedAliasAnalysis.cpp:715
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::AAMDNodes::NoAlias
MDNode * NoAlias
The tag specifying the noalias scope.
Definition: Metadata.h:678
matchAccessTags
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.
Definition: TypeBasedAliasAnalysis.cpp:655
Casting.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::AAResultBase::pointsToConstantMemory
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
Definition: AliasAnalysis.h:1227
llvm::AAMDNodes::TBAA
MDNode * TBAA
The tag for type-based alias analysis.
Definition: Metadata.h:669
llvm::AAMDNodes::concat
AAMDNodes concat(const AAMDNodes &Other) const
Determine the best AAMDNodes after concatenating two different locations together.
Definition: TypeBasedAliasAnalysis.cpp:532
N
#define N
llvm::TypeBasedAAResult::pointsToConstantMemory
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
Definition: TypeBasedAliasAnalysis.cpp:384
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
DerivedTypes.h
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:311
EnableTBAA
static cl::opt< bool > EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden)
LLVMContext.h
llvm::M1
unsigned M1(unsigned Val)
Definition: VE.h:370
llvm::AMDGPU::VGPRIndexMode::Id
Id
Definition: SIDefines.h:241
llvm::MDString
A single uniqued string.
Definition: Metadata.h:612
InitializePasses.h
llvm::AAMDNodes::shiftTBAAStruct
static MDNode * shiftTBAAStruct(MDNode *M, size_t off)
Definition: TypeBasedAliasAnalysis.cpp:759
getAccessType
static MemAccessTy getAccessType(const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)
Return the type of the memory being accessed.
Definition: LoopStrengthReduce.cpp:884
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
SetVector.h
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1237