LLVM  6.0.0svn
TypeBasedAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the TypeBasedAliasAnalysis pass, which implements
11 // metadata-based TBAA.
12 //
13 // In LLVM IR, memory does not have types, so LLVM's own type system is not
14 // suitable for doing TBAA. Instead, metadata is added to the IR to describe
15 // a type system of a higher level language. This can be used to implement
16 // typical C/C++ TBAA, but it can also be used to implement custom alias
17 // analysis behavior for other languages.
18 //
19 // We now support two types of metadata format: scalar TBAA and struct-path
20 // aware TBAA. After all testing cases are upgraded to use struct-path aware
21 // TBAA and we can auto-upgrade existing bc files, the support for scalar TBAA
22 // can be dropped.
23 //
24 // The scalar TBAA metadata format is very simple. TBAA MDNodes have up to
25 // three fields, e.g.:
26 // !0 = !{ !"an example type tree" }
27 // !1 = !{ !"int", !0 }
28 // !2 = !{ !"float", !0 }
29 // !3 = !{ !"const float", !2, i64 1 }
30 //
31 // The first field is an identity field. It can be any value, usually
32 // an MDString, which uniquely identifies the type. The most important
33 // name in the tree is the name of the root node. Two trees with
34 // different root node names are entirely disjoint, even if they
35 // have leaves with common names.
36 //
37 // The second field identifies the type's parent node in the tree, or
38 // is null or omitted for a root node. A type is considered to alias
39 // all of its descendants and all of its ancestors in the tree. Also,
40 // a type is considered to alias all types in other trees, so that
41 // bitcode produced from multiple front-ends is handled conservatively.
42 //
43 // If the third field is present, it's an integer which if equal to 1
44 // indicates that the type is "constant" (meaning pointsToConstantMemory
45 // should return true; see
46 // http://llvm.org/docs/AliasAnalysis.html#OtherItfs).
47 //
48 // With struct-path aware TBAA, the MDNodes attached to an instruction using
49 // "!tbaa" are called path tag nodes.
50 //
51 // The path tag node has 4 fields with the last field being optional.
52 //
53 // The first field is the base type node, it can be a struct type node
54 // or a scalar type node. The second field is the access type node, it
55 // must be a scalar type node. The third field is the offset into the base type.
56 // The last field has the same meaning as the last field of our scalar TBAA:
57 // it's an integer which if equal to 1 indicates that the access is "constant".
58 //
59 // The struct type node has a name and a list of pairs, one pair for each member
60 // of the struct. The first element of each pair is a type node (a struct type
61 // node or a scalar type node), specifying the type of the member, the second
62 // element of each pair is the offset of the member.
63 //
64 // Given an example
65 // typedef struct {
66 // short s;
67 // } A;
68 // typedef struct {
69 // uint16_t s;
70 // A a;
71 // } B;
72 //
73 // For an access to B.a.s, we attach !5 (a path tag node) to the load/store
74 // instruction. The base type is !4 (struct B), the access type is !2 (scalar
75 // type short) and the offset is 4.
76 //
77 // !0 = !{!"Simple C/C++ TBAA"}
78 // !1 = !{!"omnipotent char", !0} // Scalar type node
79 // !2 = !{!"short", !1} // Scalar type node
80 // !3 = !{!"A", !2, i64 0} // Struct type node
81 // !4 = !{!"B", !2, i64 0, !3, i64 4}
82 // // Struct type node
83 // !5 = !{!4, !2, i64 4} // Path tag node
84 //
85 // The struct type nodes and the scalar type nodes form a type DAG.
86 // Root (!0)
87 // char (!1) -- edge to Root
88 // short (!2) -- edge to char
89 // A (!3) -- edge with offset 0 to short
90 // B (!4) -- edge with offset 0 to short and edge with offset 4 to A
91 //
92 // To check if two tags (tagX and tagY) can alias, we start from the base type
93 // of tagX, follow the edge with the correct offset in the type DAG and adjust
94 // the offset until we reach the base type of tagY or until we reach the Root
95 // node.
96 // If we reach the base type of tagY, compare the adjusted offset with
97 // offset of tagY, return Alias if the offsets are the same, return NoAlias
98 // otherwise.
99 // If we reach the Root node, perform the above starting from base type of tagY
100 // to see if we reach base type of tagX.
101 //
102 // If they have different roots, they're part of different potentially
103 // unrelated type systems, so we return Alias to be conservative.
104 // If neither node is an ancestor of the other and they have the same root,
105 // then we say NoAlias.
106 //
107 // TODO: The current metadata format doesn't support struct
108 // fields. For example:
109 // struct X {
110 // double d;
111 // int i;
112 // };
113 // void foo(struct X *x, struct X *y, double *p) {
114 // *x = *y;
115 // *p = 0.0;
116 // }
117 // Struct X has a double member, so the store to *x can alias the store to *p.
118 // Currently it's not possible to precisely describe all the things struct X
119 // aliases, so struct assignments must use conservative TBAA nodes. There's
120 // no scheme for attaching metadata to @llvm.memcpy yet either.
121 //
122 //===----------------------------------------------------------------------===//
123 
125 #include "llvm/ADT/SetVector.h"
128 #include "llvm/IR/Constants.h"
129 #include "llvm/IR/DerivedTypes.h"
130 #include "llvm/IR/Instruction.h"
131 #include "llvm/IR/LLVMContext.h"
132 #include "llvm/IR/Metadata.h"
133 #include "llvm/Pass.h"
134 #include "llvm/Support/Casting.h"
137 #include <cassert>
138 #include <cstdint>
139 
140 using namespace llvm;
141 
142 // A handy option for disabling TBAA functionality. The same effect can also be
143 // achieved by stripping the !tbaa tags from IR, but this option is sometimes
144 // more convenient.
145 static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true));
146 
147 namespace {
148 
149 /// This is a simple wrapper around an MDNode which provides a higher-level
150 /// interface by hiding the details of how alias analysis information is encoded
151 /// in its operands.
152 template<typename MDNodeTy>
153 class TBAANodeImpl {
154  MDNodeTy *Node = nullptr;
155 
156 public:
157  TBAANodeImpl() = default;
158  explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
159 
160  /// getNode - Get the MDNode for this TBAANode.
161  MDNodeTy *getNode() const { return Node; }
162 
163  /// getParent - Get this TBAANode's Alias tree parent.
164  TBAANodeImpl<MDNodeTy> getParent() const {
165  if (Node->getNumOperands() < 2)
166  return TBAANodeImpl<MDNodeTy>();
167  MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
168  if (!P)
169  return TBAANodeImpl<MDNodeTy>();
170  // Ok, this node has a valid parent. Return it.
171  return TBAANodeImpl<MDNodeTy>(P);
172  }
173 
174  /// Test if this TBAANode represents a type for objects which are
175  /// not modified (by any means) in the context where this
176  /// AliasAnalysis is relevant.
177  bool isTypeImmutable() const {
178  if (Node->getNumOperands() < 3)
179  return false;
180  ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2));
181  if (!CI)
182  return false;
183  return CI->getValue()[0];
184  }
185 };
186 
187 /// \name Specializations of \c TBAANodeImpl for const and non const qualified
188 /// \c MDNode.
189 /// @{
190 using TBAANode = TBAANodeImpl<const MDNode>;
191 using MutableTBAANode = TBAANodeImpl<MDNode>;
192 /// @}
193 
194 /// This is a simple wrapper around an MDNode which provides a
195 /// higher-level interface by hiding the details of how alias analysis
196 /// information is encoded in its operands.
197 template<typename MDNodeTy>
198 class TBAAStructTagNodeImpl {
199  /// This node should be created with createTBAAStructTagNode.
200  MDNodeTy *Node;
201 
202 public:
203  explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
204 
205  /// Get the MDNode for this TBAAStructTagNode.
206  MDNodeTy *getNode() const { return Node; }
207 
208  MDNodeTy *getBaseType() const {
209  return dyn_cast_or_null<MDNode>(Node->getOperand(0));
210  }
211 
212  MDNodeTy *getAccessType() const {
213  return dyn_cast_or_null<MDNode>(Node->getOperand(1));
214  }
215 
216  uint64_t getOffset() const {
217  return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue();
218  }
219 
220  /// Test if this TBAAStructTagNode represents a type for objects
221  /// which are not modified (by any means) in the context where this
222  /// AliasAnalysis is relevant.
223  bool isTypeImmutable() const {
224  if (Node->getNumOperands() < 4)
225  return false;
226  ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(3));
227  if (!CI)
228  return false;
229  return CI->getValue()[0];
230  }
231 };
232 
233 /// \name Specializations of \c TBAAStructTagNodeImpl for const and non const
234 /// qualified \c MDNods.
235 /// @{
236 using TBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>;
237 using MutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>;
238 /// @}
239 
240 /// This is a simple wrapper around an MDNode which provides a
241 /// higher-level interface by hiding the details of how alias analysis
242 /// information is encoded in its operands.
243 class TBAAStructTypeNode {
244  /// This node should be created with createTBAAStructTypeNode.
245  const MDNode *Node = nullptr;
246 
247 public:
248  TBAAStructTypeNode() = default;
249  explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
250 
251  /// Get the MDNode for this TBAAStructTypeNode.
252  const MDNode *getNode() const { return Node; }
253 
254  /// Get this TBAAStructTypeNode's field in the type DAG with
255  /// given offset. Update the offset to be relative to the field type.
256  TBAAStructTypeNode getParent(uint64_t &Offset) const {
257  // Parent can be omitted for the root node.
258  if (Node->getNumOperands() < 2)
259  return TBAAStructTypeNode();
260 
261  // Fast path for a scalar type node and a struct type node with a single
262  // field.
263  if (Node->getNumOperands() <= 3) {
264  uint64_t Cur = Node->getNumOperands() == 2
265  ? 0
266  : mdconst::extract<ConstantInt>(Node->getOperand(2))
267  ->getZExtValue();
268  Offset -= Cur;
269  MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
270  if (!P)
271  return TBAAStructTypeNode();
272  return TBAAStructTypeNode(P);
273  }
274 
275  // Assume the offsets are in order. We return the previous field if
276  // the current offset is bigger than the given offset.
277  unsigned TheIdx = 0;
278  for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) {
279  uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
280  ->getZExtValue();
281  if (Cur > Offset) {
282  assert(Idx >= 3 &&
283  "TBAAStructTypeNode::getParent should have an offset match!");
284  TheIdx = Idx - 2;
285  break;
286  }
287  }
288  // Move along the last field.
289  if (TheIdx == 0)
290  TheIdx = Node->getNumOperands() - 2;
291  uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
292  ->getZExtValue();
293  Offset -= Cur;
294  MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
295  if (!P)
296  return TBAAStructTypeNode();
297  return TBAAStructTypeNode(P);
298  }
299 };
300 
301 } // end anonymous namespace
302 
303 /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat
304 /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA
305 /// format.
306 static bool isStructPathTBAA(const MDNode *MD) {
307  // Anonymous TBAA root starts with a MDNode and dragonegg uses it as
308  // a TBAA tag.
309  return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
310 }
311 
313  const MemoryLocation &LocB) {
314  if (!EnableTBAA)
315  return AAResultBase::alias(LocA, LocB);
316 
317  // If accesses may alias, chain to the next AliasAnalysis.
318  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
319  return AAResultBase::alias(LocA, LocB);
320 
321  // Otherwise return a definitive result.
322  return NoAlias;
323 }
324 
326  bool OrLocal) {
327  if (!EnableTBAA)
328  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
329 
330  const MDNode *M = Loc.AATags.TBAA;
331  if (!M)
332  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
333 
334  // If this is an "immutable" type, we can assume the pointer is pointing
335  // to constant memory.
336  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
337  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
338  return true;
339 
340  return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
341 }
342 
345  if (!EnableTBAA)
347 
349 
350  // If this is an "immutable" type, we can assume the call doesn't write
351  // to memory.
353  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
354  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
355  Min = FMRB_OnlyReadsMemory;
356 
358 }
359 
361  // Functions don't have metadata. Just chain to the next implementation.
363 }
364 
366  const MemoryLocation &Loc) {
367  if (!EnableTBAA)
368  return AAResultBase::getModRefInfo(CS, Loc);
369 
370  if (const MDNode *L = Loc.AATags.TBAA)
371  if (const MDNode *M =
373  if (!Aliases(L, M))
374  return MRI_NoModRef;
375 
376  return AAResultBase::getModRefInfo(CS, Loc);
377 }
378 
380  ImmutableCallSite CS2) {
381  if (!EnableTBAA)
382  return AAResultBase::getModRefInfo(CS1, CS2);
383 
384  if (const MDNode *M1 =
386  if (const MDNode *M2 =
388  if (!Aliases(M1, M2))
389  return MRI_NoModRef;
390 
391  return AAResultBase::getModRefInfo(CS1, CS2);
392 }
393 
395  if (!isStructPathTBAA(this)) {
396  if (getNumOperands() < 1)
397  return false;
398  if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
399  if (Tag1->getString() == "vtable pointer")
400  return true;
401  }
402  return false;
403  }
404 
405  // For struct-path aware TBAA, we use the access type of the tag.
406  if (getNumOperands() < 2)
407  return false;
408  MDNode *Tag = cast_or_null<MDNode>(getOperand(1));
409  if (!Tag)
410  return false;
411  if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) {
412  if (Tag1->getString() == "vtable pointer")
413  return true;
414  }
415  return false;
416 }
417 
418 static bool matchAccessTags(const MDNode *A, const MDNode *B,
419  const MDNode **GenericTag = nullptr);
420 
422  const MDNode *GenericTag;
423  matchAccessTags(A, B, &GenericTag);
424  return const_cast<MDNode*>(GenericTag);
425 }
426 
427 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
428  if (!A || !B)
429  return nullptr;
430 
431  if (A == B)
432  return A;
433 
435  TBAANode TA(A);
436  while (TA.getNode()) {
437  if (PathA.count(TA.getNode()))
438  report_fatal_error("Cycle found in TBAA metadata.");
439  PathA.insert(TA.getNode());
440  TA = TA.getParent();
441  }
442 
444  TBAANode TB(B);
445  while (TB.getNode()) {
446  if (PathB.count(TB.getNode()))
447  report_fatal_error("Cycle found in TBAA metadata.");
448  PathB.insert(TB.getNode());
449  TB = TB.getParent();
450  }
451 
452  int IA = PathA.size() - 1;
453  int IB = PathB.size() - 1;
454 
455  const MDNode *Ret = nullptr;
456  while (IA >= 0 && IB >= 0) {
457  if (PathA[IA] == PathB[IB])
458  Ret = PathA[IA];
459  else
460  break;
461  --IA;
462  --IB;
463  }
464 
465  return Ret;
466 }
467 
469  if (Merge)
470  N.TBAA =
472  else
473  N.TBAA = getMetadata(LLVMContext::MD_tbaa);
474 
475  if (Merge)
477  N.Scope, getMetadata(LLVMContext::MD_alias_scope));
478  else
479  N.Scope = getMetadata(LLVMContext::MD_alias_scope);
480 
481  if (Merge)
482  N.NoAlias =
484  else
485  N.NoAlias = getMetadata(LLVMContext::MD_noalias);
486 }
487 
488 static bool findAccessType(TBAAStructTagNode BaseTag,
489  const MDNode *AccessTypeNode,
490  uint64_t &OffsetInBase) {
491  // Start from the base type, follow the edge with the correct offset in
492  // the type DAG and adjust the offset until we reach the access type or
493  // until we reach a root node.
494  TBAAStructTypeNode BaseType(BaseTag.getBaseType());
495  OffsetInBase = BaseTag.getOffset();
496 
497  while (const MDNode *BaseTypeNode = BaseType.getNode()) {
498  if (BaseTypeNode == AccessTypeNode)
499  return true;
500 
501  // Follow the edge with the correct offset, Offset will be adjusted to
502  // be relative to the field type.
503  BaseType = BaseType.getParent(OffsetInBase);
504  }
505  return false;
506 }
507 
508 static const MDNode *createAccessTag(const MDNode *AccessType) {
509  // If there is no access type or the access type is the root node, then
510  // we don't have any useful access tag to return.
511  if (!AccessType || AccessType->getNumOperands() < 2)
512  return nullptr;
513 
514  Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
515  auto *ImmutabilityFlag = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
516  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
517  const_cast<MDNode*>(AccessType), ImmutabilityFlag};
518  return MDNode::get(AccessType->getContext(), Ops);
519 }
520 
521 /// matchTags - Return true if the given couple of accesses are allowed to
522 /// overlap. If \arg GenericTag is not null, then on return it points to the
523 /// most generic access descriptor for the given two.
524 static bool matchAccessTags(const MDNode *A, const MDNode *B,
525  const MDNode **GenericTag) {
526  if (A == B) {
527  if (GenericTag)
528  *GenericTag = A;
529  return true;
530  }
531 
532  // Accesses with no TBAA information may alias with any other accesses.
533  if (!A || !B) {
534  if (GenericTag)
535  *GenericTag = nullptr;
536  return true;
537  }
538 
539  // Verify that both input nodes are struct-path aware. Auto-upgrade should
540  // have taken care of this.
541  assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
542  assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
543 
544  TBAAStructTagNode TagA(A), TagB(B);
545  const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
546  TagB.getAccessType());
547  if (GenericTag)
548  *GenericTag = createAccessTag(CommonType);
549 
550  // TODO: We need to check if AccessType of TagA encloses AccessType of
551  // TagB to support aggregate AccessType. If yes, return true.
552 
553  // Climb the type DAG from base type of A to see if we reach base type of B.
554  uint64_t OffsetA;
555  if (findAccessType(TagA, TagB.getBaseType(), OffsetA))
556  return OffsetA == TagB.getOffset();
557 
558  // Climb the type DAG from base type of B to see if we reach base type of A.
559  uint64_t OffsetB;
560  if (findAccessType(TagB, TagA.getBaseType(), OffsetB))
561  return OffsetB == TagA.getOffset();
562 
563  // If the final access types have different roots, they're part of different
564  // potentially unrelated type systems, so we must be conservative.
565  if (!CommonType)
566  return true;
567 
568  // If they have the same root, then we've proved there's no alias.
569  return false;
570 }
571 
572 /// Aliases - Test whether the access represented by tag A may alias the
573 /// access represented by tag B.
574 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
575  return matchAccessTags(A, B);
576 }
577 
578 AnalysisKey TypeBasedAA::Key;
579 
581  return TypeBasedAAResult();
582 }
583 
585 INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
586  false, true)
587 
589  return new TypeBasedAAWrapperPass();
590 }
591 
594 }
595 
597  Result.reset(new TypeBasedAAResult());
598  return false;
599 }
600 
602  Result.reset();
603  return false;
604 }
605 
607  AU.setPreservesAll();
608 }
static const MDNode * createAccessTag(const MDNode *AccessType)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
MDNode * Scope
The tag for alias scope specification (used with noalias).
Definition: Metadata.h:659
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
MDNode * TBAA
The tag for type-based alias analysis.
Definition: Metadata.h:656
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal)
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:915
This file contains the declarations for metadata subclasses.
static enum BaseType getBaseType(const Value *Val)
Return the baseType for Val which states whether Val is exclusively derived from constant/null, or not exclusively derived from constant.
Metadata node.
Definition: Metadata.h:862
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
F(f)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
void initializeTypeBasedAAWrapperPassPass(PassRegistry &)
TypeBasedAAResult run(Function &F, FunctionAnalysisManager &AM)
This indicates that the function could not be classified into one of the behaviors above...
Legacy wrapper pass to provide the TypeBasedAAResult object.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
InstrTy * getInstruction() const
Definition: CallSite.h:92
bool isTBAAVtableAccess() const
Check whether MDNode is a vtable access.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
static bool findAccessType(TBAAStructTagNode BaseTag, const MDNode *AccessTypeNode, uint64_t &OffsetInBase)
LLVMContext & getContext() const
Definition: Metadata.h:922
FunctionModRefBehavior
Summary of how a function affects memory in the program.
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:194
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:902
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:408
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
The access neither references nor modifies the value stored in memory.
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This is the interface for a metadata-based TBAA.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static const MDNode * getLeastCommonType(const MDNode *A, const MDNode *B)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
Represent the analysis usage information of a pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A simple AA result that uses TBAA metadata to answer queries.
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
R600 Clause Merge
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
Representation for a specific memory location.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:240
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis", false, true) ImmutablePass *llvm
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
MDNode * NoAlias
The tag specifying the noalias scope.
Definition: Metadata.h:662
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:560
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.
static cl::opt< bool > EnableTBAA("enable-tbaa", cl::init(true))
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
This file provides utility analysis objects describing memory locations.
Establish a view to a call site for examination.
Definition: CallSite.h:713
#define N
static MemAccessTy getAccessType(const Instruction *Inst)
Return the type of the memory being accessed.
ImmutablePass * createTypeBasedAAWrapperPass()
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const Function * getParent(const Value *V)
A single uniqued string.
Definition: Metadata.h:602
A container for analyses that lazily runs them and caches their results.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
Root of the metadata hierarchy.
Definition: Metadata.h:58
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
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...