LLVM  16.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  const ArrayRef<MDOperand> Operands = Node->operands();
307  const unsigned NumOperands = Operands.size();
308 
309  if (NewFormat) {
310  // New-format root and scalar type nodes have no fields.
311  if (NumOperands < 6)
312  return TBAAStructTypeNode();
313  } else {
314  // Parent can be omitted for the root node.
315  if (NumOperands < 2)
316  return TBAAStructTypeNode();
317 
318  // Fast path for a scalar type node and a struct type node with a single
319  // field.
320  if (NumOperands <= 3) {
321  uint64_t Cur =
322  NumOperands == 2
323  ? 0
324  : mdconst::extract<ConstantInt>(Operands[2])->getZExtValue();
325  Offset -= Cur;
326  MDNode *P = dyn_cast_or_null<MDNode>(Operands[1]);
327  if (!P)
328  return TBAAStructTypeNode();
329  return TBAAStructTypeNode(P);
330  }
331  }
332 
333  // Assume the offsets are in order. We return the previous field if
334  // the current offset is bigger than the given offset.
335  unsigned FirstFieldOpNo = NewFormat ? 3 : 1;
336  unsigned NumOpsPerField = NewFormat ? 3 : 2;
337  unsigned TheIdx = 0;
338 
339  for (unsigned Idx = FirstFieldOpNo; Idx < NumOperands;
340  Idx += NumOpsPerField) {
341  uint64_t Cur =
342  mdconst::extract<ConstantInt>(Operands[Idx + 1])->getZExtValue();
343  if (Cur > Offset) {
344  assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
345  "TBAAStructTypeNode::getField should have an offset match!");
346  TheIdx = Idx - NumOpsPerField;
347  break;
348  }
349  }
350  // Move along the last field.
351  if (TheIdx == 0)
352  TheIdx = NumOperands - NumOpsPerField;
353  uint64_t Cur =
354  mdconst::extract<ConstantInt>(Operands[TheIdx + 1])->getZExtValue();
355  Offset -= Cur;
356  MDNode *P = dyn_cast_or_null<MDNode>(Operands[TheIdx]);
357  if (!P)
358  return TBAAStructTypeNode();
359  return TBAAStructTypeNode(P);
360  }
361 };
362 
363 } // end anonymous namespace
364 
365 /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat
366 /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA
367 /// format.
368 static bool isStructPathTBAA(const MDNode *MD) {
369  // Anonymous TBAA root starts with a MDNode and dragonegg uses it as
370  // a TBAA tag.
371  return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
372 }
373 
375  const MemoryLocation &LocB,
376  AAQueryInfo &AAQI) {
377  if (!EnableTBAA)
378  return AAResultBase::alias(LocA, LocB, AAQI);
379 
380  // If accesses may alias, chain to the next AliasAnalysis.
381  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
382  return AAResultBase::alias(LocA, LocB, AAQI);
383 
384  // Otherwise return a definitive result.
385  return AliasResult::NoAlias;
386 }
387 
389  AAQueryInfo &AAQI,
390  bool IgnoreLocals) {
391  if (!EnableTBAA)
392  return AAResultBase::getModRefInfoMask(Loc, AAQI, IgnoreLocals);
393 
394  const MDNode *M = Loc.AATags.TBAA;
395  if (!M)
396  return AAResultBase::getModRefInfoMask(Loc, AAQI, IgnoreLocals);
397 
398  // If this is an "immutable" type, we can assume the pointer is pointing
399  // to constant memory.
400  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
401  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
402  return ModRefInfo::NoModRef;
403 
404  return AAResultBase::getModRefInfoMask(Loc, AAQI, IgnoreLocals);
405 }
406 
408  AAQueryInfo &AAQI) {
409  if (!EnableTBAA)
410  return AAResultBase::getMemoryEffects(Call, AAQI);
411 
412  // If this is an "immutable" type, the access is not observable.
413  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
414  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
415  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
416  return MemoryEffects::none();
417 
418  return AAResultBase::getMemoryEffects(Call, AAQI);
419 }
420 
422  // Functions don't have metadata. Just chain to the next implementation.
424 }
425 
427  const MemoryLocation &Loc,
428  AAQueryInfo &AAQI) {
429  if (!EnableTBAA)
430  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
431 
432  if (const MDNode *L = Loc.AATags.TBAA)
433  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
434  if (!Aliases(L, M))
435  return ModRefInfo::NoModRef;
436 
437  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
438 }
439 
441  const CallBase *Call2,
442  AAQueryInfo &AAQI) {
443  if (!EnableTBAA)
444  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
445 
446  if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))
447  if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))
448  if (!Aliases(M1, M2))
449  return ModRefInfo::NoModRef;
450 
451  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
452 }
453 
455  if (!isStructPathTBAA(this)) {
456  if (getNumOperands() < 1)
457  return false;
458  if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
459  if (Tag1->getString() == "vtable pointer")
460  return true;
461  }
462  return false;
463  }
464 
465  // For struct-path aware TBAA, we use the access type of the tag.
466  TBAAStructTagNode Tag(this);
467  TBAAStructTypeNode AccessType(Tag.getAccessType());
468  if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
469  if (Id->getString() == "vtable pointer")
470  return true;
471  return false;
472 }
473 
474 static bool matchAccessTags(const MDNode *A, const MDNode *B,
475  const MDNode **GenericTag = nullptr);
476 
478  const MDNode *GenericTag;
479  matchAccessTags(A, B, &GenericTag);
480  return const_cast<MDNode*>(GenericTag);
481 }
482 
483 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
484  if (!A || !B)
485  return nullptr;
486 
487  if (A == B)
488  return A;
489 
491  TBAANode TA(A);
492  while (TA.getNode()) {
493  if (PathA.count(TA.getNode()))
494  report_fatal_error("Cycle found in TBAA metadata.");
495  PathA.insert(TA.getNode());
496  TA = TA.getParent();
497  }
498 
500  TBAANode TB(B);
501  while (TB.getNode()) {
502  if (PathB.count(TB.getNode()))
503  report_fatal_error("Cycle found in TBAA metadata.");
504  PathB.insert(TB.getNode());
505  TB = TB.getParent();
506  }
507 
508  int IA = PathA.size() - 1;
509  int IB = PathB.size() - 1;
510 
511  const MDNode *Ret = nullptr;
512  while (IA >= 0 && IB >= 0) {
513  if (PathA[IA] == PathB[IB])
514  Ret = PathA[IA];
515  else
516  break;
517  --IA;
518  --IB;
519  }
520 
521  return Ret;
522 }
523 
524 AAMDNodes AAMDNodes::merge(const AAMDNodes &Other) const {
525  AAMDNodes Result;
526  Result.TBAA = MDNode::getMostGenericTBAA(TBAA, Other.TBAA);
527  Result.TBAAStruct = nullptr;
528  Result.Scope = MDNode::getMostGenericAliasScope(Scope, Other.Scope);
529  Result.NoAlias = MDNode::intersect(NoAlias, Other.NoAlias);
530  return Result;
531 }
532 
533 AAMDNodes AAMDNodes::concat(const AAMDNodes &Other) const {
534  AAMDNodes Result;
535  Result.TBAA = Result.TBAAStruct = nullptr;
536  Result.Scope = MDNode::getMostGenericAliasScope(Scope, Other.Scope);
537  Result.NoAlias = MDNode::intersect(NoAlias, Other.NoAlias);
538  return Result;
539 }
540 
541 static const MDNode *createAccessTag(const MDNode *AccessType) {
542  // If there is no access type or the access type is the root node, then
543  // we don't have any useful access tag to return.
544  if (!AccessType || AccessType->getNumOperands() < 2)
545  return nullptr;
546 
547  Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
548  auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
549 
550  if (TBAAStructTypeNode(AccessType).isNewFormat()) {
551  // TODO: Take access ranges into account when matching access tags and
552  // fix this code to generate actual access sizes for generic tags.
553  uint64_t AccessSize = UINT64_MAX;
554  auto *SizeNode =
555  ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
556  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
557  const_cast<MDNode*>(AccessType),
558  OffsetNode, SizeNode};
559  return MDNode::get(AccessType->getContext(), Ops);
560  }
561 
562  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
563  const_cast<MDNode*>(AccessType),
564  OffsetNode};
565  return MDNode::get(AccessType->getContext(), Ops);
566 }
567 
568 static bool hasField(TBAAStructTypeNode BaseType,
569  TBAAStructTypeNode FieldType) {
570  for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {
571  TBAAStructTypeNode T = BaseType.getFieldType(I);
572  if (T == FieldType || hasField(T, FieldType))
573  return true;
574  }
575  return false;
576 }
577 
578 /// Return true if for two given accesses, one of the accessed objects may be a
579 /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
580 /// describe the accesses to the base object and the subobject respectively.
581 /// \p CommonType must be the metadata node describing the common type of the
582 /// accessed objects. On return, \p MayAlias is set to true iff these accesses
583 /// may alias and \p Generic, if not null, points to the most generic access
584 /// tag for the given two.
585 static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
586  TBAAStructTagNode SubobjectTag,
587  const MDNode *CommonType,
588  const MDNode **GenericTag,
589  bool &MayAlias) {
590  // If the base object is of the least common type, then this may be an access
591  // to its subobject.
592  if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
593  BaseTag.getAccessType() == CommonType) {
594  if (GenericTag)
595  *GenericTag = createAccessTag(CommonType);
596  MayAlias = true;
597  return true;
598  }
599 
600  // If the access to the base object is through a field of the subobject's
601  // type, then this may be an access to that field. To check for that we start
602  // from the base type, follow the edge with the correct offset in the type DAG
603  // and adjust the offset until we reach the field type or until we reach the
604  // access type.
605  bool NewFormat = BaseTag.isNewFormat();
606  TBAAStructTypeNode BaseType(BaseTag.getBaseType());
607  uint64_t OffsetInBase = BaseTag.getOffset();
608 
609  for (;;) {
610  // In the old format there is no distinction between fields and parent
611  // types, so in this case we consider all nodes up to the root.
612  if (!BaseType.getNode()) {
613  assert(!NewFormat && "Did not see access type in access path!");
614  break;
615  }
616 
617  if (BaseType.getNode() == SubobjectTag.getBaseType()) {
618  bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
619  if (GenericTag) {
620  *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
621  createAccessTag(CommonType);
622  }
623  MayAlias = SameMemberAccess;
624  return true;
625  }
626 
627  // With new-format nodes we stop at the access type.
628  if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
629  break;
630 
631  // Follow the edge with the correct offset. Offset will be adjusted to
632  // be relative to the field type.
633  BaseType = BaseType.getField(OffsetInBase);
634  }
635 
636  // If the base object has a direct or indirect field of the subobject's type,
637  // then this may be an access to that field. We need this to check now that
638  // we support aggregates as access types.
639  if (NewFormat) {
640  // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
641  TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
642  if (hasField(BaseType, FieldType)) {
643  if (GenericTag)
644  *GenericTag = createAccessTag(CommonType);
645  MayAlias = true;
646  return true;
647  }
648  }
649 
650  return false;
651 }
652 
653 /// matchTags - Return true if the given couple of accesses are allowed to
654 /// overlap. If \arg GenericTag is not null, then on return it points to the
655 /// most generic access descriptor for the given two.
656 static bool matchAccessTags(const MDNode *A, const MDNode *B,
657  const MDNode **GenericTag) {
658  if (A == B) {
659  if (GenericTag)
660  *GenericTag = A;
661  return true;
662  }
663 
664  // Accesses with no TBAA information may alias with any other accesses.
665  if (!A || !B) {
666  if (GenericTag)
667  *GenericTag = nullptr;
668  return true;
669  }
670 
671  // Verify that both input nodes are struct-path aware. Auto-upgrade should
672  // have taken care of this.
673  assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
674  assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
675 
676  TBAAStructTagNode TagA(A), TagB(B);
677  const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
678  TagB.getAccessType());
679 
680  // If the final access types have different roots, they're part of different
681  // potentially unrelated type systems, so we must be conservative.
682  if (!CommonType) {
683  if (GenericTag)
684  *GenericTag = nullptr;
685  return true;
686  }
687 
688  // If one of the accessed objects may be a subobject of the other, then such
689  // accesses may alias.
690  bool MayAlias;
691  if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
692  CommonType, GenericTag, MayAlias) ||
693  mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
694  CommonType, GenericTag, MayAlias))
695  return MayAlias;
696 
697  // Otherwise, we've proved there's no alias.
698  if (GenericTag)
699  *GenericTag = createAccessTag(CommonType);
700  return false;
701 }
702 
703 /// Aliases - Test whether the access represented by tag A may alias the
704 /// access represented by tag B.
705 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
706  return matchAccessTags(A, B);
707 }
708 
709 AnalysisKey TypeBasedAA::Key;
710 
712  return TypeBasedAAResult();
713 }
714 
716 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
717  false, true)
718 
720  return new TypeBasedAAWrapperPass();
721 }
722 
725 }
726 
728  Result.reset(new TypeBasedAAResult());
729  return false;
730 }
731 
733  Result.reset();
734  return false;
735 }
736 
738  AU.setPreservesAll();
739 }
740 
741 MDNode *AAMDNodes::shiftTBAA(MDNode *MD, size_t Offset) {
742  // Fast path if there's no offset
743  if (Offset == 0)
744  return MD;
745  // Fast path if there's no path tbaa node (and thus scalar)
746  if (!isStructPathTBAA(MD))
747  return MD;
748 
749  // The correct behavior here is to add the offset into the TBAA
750  // struct node offset. The base type, however may not have defined
751  // a type at this additional offset, resulting in errors. Since
752  // this method is only used within a given load/store access
753  // the offset provided is only used to subdivide the previous load
754  // maintaining the validity of the previous TBAA.
755  //
756  // This, however, should be revisited in the future.
757  return MD;
758 }
759 
761  // Fast path if there's no offset
762  if (Offset == 0)
763  return MD;
765  for (size_t i = 0, size = MD->getNumOperands(); i < size; i += 3) {
766  ConstantInt *InnerOffset = mdconst::extract<ConstantInt>(MD->getOperand(i));
767  ConstantInt *InnerSize =
768  mdconst::extract<ConstantInt>(MD->getOperand(i + 1));
769  // Don't include any triples that aren't in bounds
770  if (InnerOffset->getZExtValue() + InnerSize->getZExtValue() <= Offset)
771  continue;
772 
773  uint64_t NewSize = InnerSize->getZExtValue();
774  uint64_t NewOffset = InnerOffset->getZExtValue() - Offset;
775  if (InnerOffset->getZExtValue() < Offset) {
776  NewOffset = 0;
777  NewSize -= Offset - InnerOffset->getZExtValue();
778  }
779 
780  // Shift the offset of the triple
781  Sub.push_back(ConstantAsMetadata::get(
782  ConstantInt::get(InnerOffset->getType(), NewOffset)));
783  Sub.push_back(ConstantAsMetadata::get(
784  ConstantInt::get(InnerSize->getType(), NewSize)));
785  Sub.push_back(MD->getOperand(i + 2));
786  }
787  return MDNode::get(MD->getContext(), Sub);
788 }
789 
791  // Fast path if 0-length
792  if (Len == 0)
793  return nullptr;
794 
795  // Regular TBAA is invariant of length, so we only need to consider
796  // struct-path TBAA.
797  if (!isStructPathTBAA(MD))
798  return MD;
799 
800  TBAAStructTagNode Tag(MD);
801 
802  // Only new format TBAA has a size
803  if (!Tag.isNewFormat())
804  return MD;
805 
806  // If unknown size, drop the TBAA.
807  if (Len == -1)
808  return nullptr;
809 
810  // Otherwise, create TBAA with the new Len
811  ArrayRef<MDOperand> MDOperands = MD->operands();
812  SmallVector<Metadata *, 4> NextNodes(MDOperands.begin(), MDOperands.end());
813  ConstantInt *PreviousSize = mdconst::extract<ConstantInt>(NextNodes[3]);
814 
815  // Don't create a new MDNode if it is the same length.
816  if (PreviousSize->equalsInt(Len))
817  return MD;
818 
819  NextNodes[3] =
820  ConstantAsMetadata::get(ConstantInt::get(PreviousSize->getType(), Len));
821  return MDNode::get(MD->getContext(), NextNodes);
822 }
i
i
Definition: README.txt:29
TypeBasedAliasAnalysis.h
llvm::TypeBasedAAResult::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Definition: TypeBasedAliasAnalysis.cpp:426
llvm::ModRefInfo::NoModRef
@ NoModRef
The access neither references nor modifies the value stored in memory.
llvm::TypeBasedAAResult::getModRefInfoMask
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool IgnoreLocals)
Definition: TypeBasedAliasAnalysis.cpp:388
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:541
llvm::AAMDNodes::extendToTBAA
static MDNode * extendToTBAA(MDNode *TBAA, ssize_t len)
Definition: TypeBasedAliasAnalysis.cpp:790
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::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:732
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:711
llvm::X86II::TA
@ TA
Definition: X86BaseInfo.h:813
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::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:1199
llvm::TypeBasedAAWrapperPass::TypeBasedAAWrapperPass
TypeBasedAAWrapperPass()
Definition: TypeBasedAliasAnalysis.cpp:723
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:585
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:83
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:568
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::getOffset
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
Definition: RuntimeDyld.cpp:172
llvm::TypeBasedAAWrapperPass::doInitialization
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: TypeBasedAliasAnalysis.cpp:727
OpIndex
unsigned OpIndex
Definition: SPIRVModuleAnalysis.cpp:46
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:1400
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1298
AliasAnalysis.h
llvm::AAMDNodes::shiftTBAA
static MDNode * shiftTBAA(MDNode *M, size_t off)
Definition: TypeBasedAliasAnalysis.cpp:741
llvm::MemoryEffects
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:233
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:232
llvm::TypeBasedAAResult::getMemoryEffects
MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
Definition: TypeBasedAliasAnalysis.cpp:407
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::AAResultBase::getModRefInfoMask
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool IgnoreLocals)
Definition: AliasAnalysis.h:805
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
InstrTypes.h
llvm::MDNode::operands
ArrayRef< MDOperand > operands() const
Definition: Metadata.h:1290
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:145
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:879
llvm::AArch64PACKey::IA
@ IA
Definition: AArch64BaseInfo.h:819
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:276
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1292
llvm::TypeBasedAAWrapperPass
Legacy wrapper pass to provide the TypeBasedAAResult object.
Definition: TypeBasedAliasAnalysis.h:69
llvm::cl::opt< bool >
getLeastCommonType
static const MDNode * getLeastCommonType(const MDNode *A, const MDNode *B)
Definition: TypeBasedAliasAnalysis.cpp:483
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:73
llvm::MDNode::intersect
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1020
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:419
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:737
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:368
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::AArch64PACKey::IB
@ IB
Definition: AArch64BaseInfo.h:820
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:446
llvm::MDNode::getMostGenericTBAA
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
Definition: TypeBasedAliasAnalysis.cpp:477
llvm::TypeBasedAAResult::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: TypeBasedAliasAnalysis.cpp:374
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
llvm::MemoryEffects::none
static MemoryEffects none()
Create MemoryEffects that cannot read or write any memory.
Definition: ModRef.h:118
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2010
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::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::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:1715
llvm::initializeTypeBasedAAWrapperPassPass
void initializeTypeBasedAAWrapperPassPass(PassRegistry &)
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
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:524
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:805
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:101
llvm::MDNode::getMostGenericAliasScope
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1033
llvm::MDNode::isTBAAVtableAccess
bool isTBAAVtableAccess() const
Check whether MDNode is a vtable access.
Definition: TypeBasedAliasAnalysis.cpp:454
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:1108
INITIALIZE_PASS
INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis", false, true) ImmutablePass *llvm
Definition: TypeBasedAliasAnalysis.cpp:716
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:656
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
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::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:822
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:533
Other
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1252
llvm::AAResultBase::getMemoryEffects
MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:814
N
#define N
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::X86II::TB
@ TB
Definition: X86BaseInfo.h:810
llvm::M1
unsigned M1(unsigned Val)
Definition: VE.h:466
llvm::AMDGPU::VGPRIndexMode::Id
Id
Definition: SIDefines.h:244
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:760
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
getAccessType
static MemAccessTy getAccessType(const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)
Return the type of the memory being accessed.
Definition: LoopStrengthReduce.cpp:897
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:800
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:211
SetVector.h