LLVM  14.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/Instruction.h"
116 #include "llvm/IR/LLVMContext.h"
117 #include "llvm/IR/Metadata.h"
118 #include "llvm/InitializePasses.h"
119 #include "llvm/Pass.h"
120 #include "llvm/Support/Casting.h"
123 #include <cassert>
124 #include <cstdint>
125 
126 using namespace llvm;
127 
128 // A handy option for disabling TBAA functionality. The same effect can also be
129 // achieved by stripping the !tbaa tags from IR, but this option is sometimes
130 // more convenient.
131 static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden);
132 
133 namespace {
134 
135 /// isNewFormatTypeNode - Return true iff the given type node is in the new
136 /// size-aware format.
137 static bool isNewFormatTypeNode(const MDNode *N) {
138  if (N->getNumOperands() < 3)
139  return false;
140  // In the old format the first operand is a string.
141  if (!isa<MDNode>(N->getOperand(0)))
142  return false;
143  return true;
144 }
145 
146 /// This is a simple wrapper around an MDNode which provides a higher-level
147 /// interface by hiding the details of how alias analysis information is encoded
148 /// in its operands.
149 template<typename MDNodeTy>
150 class TBAANodeImpl {
151  MDNodeTy *Node = nullptr;
152 
153 public:
154  TBAANodeImpl() = default;
155  explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
156 
157  /// getNode - Get the MDNode for this TBAANode.
158  MDNodeTy *getNode() const { return Node; }
159 
160  /// isNewFormat - Return true iff the wrapped type node is in the new
161  /// size-aware format.
162  bool isNewFormat() const { return isNewFormatTypeNode(Node); }
163 
164  /// getParent - Get this TBAANode's Alias tree parent.
165  TBAANodeImpl<MDNodeTy> getParent() const {
166  if (isNewFormat())
167  return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0)));
168 
169  if (Node->getNumOperands() < 2)
170  return TBAANodeImpl<MDNodeTy>();
171  MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
172  if (!P)
173  return TBAANodeImpl<MDNodeTy>();
174  // Ok, this node has a valid parent. Return it.
175  return TBAANodeImpl<MDNodeTy>(P);
176  }
177 
178  /// Test if this TBAANode represents a type for objects which are
179  /// not modified (by any means) in the context where this
180  /// AliasAnalysis is relevant.
181  bool isTypeImmutable() const {
182  if (Node->getNumOperands() < 3)
183  return false;
184  ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2));
185  if (!CI)
186  return false;
187  return CI->getValue()[0];
188  }
189 };
190 
191 /// \name Specializations of \c TBAANodeImpl for const and non const qualified
192 /// \c MDNode.
193 /// @{
194 using TBAANode = TBAANodeImpl<const MDNode>;
195 using MutableTBAANode = TBAANodeImpl<MDNode>;
196 /// @}
197 
198 /// This is a simple wrapper around an MDNode which provides a
199 /// higher-level interface by hiding the details of how alias analysis
200 /// information is encoded in its operands.
201 template<typename MDNodeTy>
202 class TBAAStructTagNodeImpl {
203  /// This node should be created with createTBAAAccessTag().
204  MDNodeTy *Node;
205 
206 public:
207  explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
208 
209  /// Get the MDNode for this TBAAStructTagNode.
210  MDNodeTy *getNode() const { return Node; }
211 
212  /// isNewFormat - Return true iff the wrapped access tag is in the new
213  /// size-aware format.
214  bool isNewFormat() const {
215  if (Node->getNumOperands() < 4)
216  return false;
217  if (MDNodeTy *AccessType = getAccessType())
218  if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat())
219  return false;
220  return true;
221  }
222 
223  MDNodeTy *getBaseType() const {
224  return dyn_cast_or_null<MDNode>(Node->getOperand(0));
225  }
226 
227  MDNodeTy *getAccessType() const {
228  return dyn_cast_or_null<MDNode>(Node->getOperand(1));
229  }
230 
231  uint64_t getOffset() const {
232  return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue();
233  }
234 
235  uint64_t getSize() const {
236  if (!isNewFormat())
237  return UINT64_MAX;
238  return mdconst::extract<ConstantInt>(Node->getOperand(3))->getZExtValue();
239  }
240 
241  /// Test if this TBAAStructTagNode represents a type for objects
242  /// which are not modified (by any means) in the context where this
243  /// AliasAnalysis is relevant.
244  bool isTypeImmutable() const {
245  unsigned OpNo = isNewFormat() ? 4 : 3;
246  if (Node->getNumOperands() < OpNo + 1)
247  return false;
248  ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(OpNo));
249  if (!CI)
250  return false;
251  return CI->getValue()[0];
252  }
253 };
254 
255 /// \name Specializations of \c TBAAStructTagNodeImpl for const and non const
256 /// qualified \c MDNods.
257 /// @{
258 using TBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>;
259 using MutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>;
260 /// @}
261 
262 /// This is a simple wrapper around an MDNode which provides a
263 /// higher-level interface by hiding the details of how alias analysis
264 /// information is encoded in its operands.
265 class TBAAStructTypeNode {
266  /// This node should be created with createTBAATypeNode().
267  const MDNode *Node = nullptr;
268 
269 public:
270  TBAAStructTypeNode() = default;
271  explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
272 
273  /// Get the MDNode for this TBAAStructTypeNode.
274  const MDNode *getNode() const { return Node; }
275 
276  /// isNewFormat - Return true iff the wrapped type node is in the new
277  /// size-aware format.
278  bool isNewFormat() const { return isNewFormatTypeNode(Node); }
279 
280  bool operator==(const TBAAStructTypeNode &Other) const {
281  return getNode() == Other.getNode();
282  }
283 
284  /// getId - Return type identifier.
285  Metadata *getId() const {
286  return Node->getOperand(isNewFormat() ? 2 : 0);
287  }
288 
289  unsigned getNumFields() const {
290  unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
291  unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
292  return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;
293  }
294 
295  TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {
296  unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
297  unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
298  unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;
299  auto *TypeNode = cast<MDNode>(getNode()->getOperand(OpIndex));
300  return TBAAStructTypeNode(TypeNode);
301  }
302 
303  /// Get this TBAAStructTypeNode's field in the type DAG with
304  /// given offset. Update the offset to be relative to the field type.
305  TBAAStructTypeNode getField(uint64_t &Offset) const {
306  bool NewFormat = isNewFormat();
307  if (NewFormat) {
308  // New-format root and scalar type nodes have no fields.
309  if (Node->getNumOperands() < 6)
310  return TBAAStructTypeNode();
311  } else {
312  // Parent can be omitted for the root node.
313  if (Node->getNumOperands() < 2)
314  return TBAAStructTypeNode();
315 
316  // Fast path for a scalar type node and a struct type node with a single
317  // field.
318  if (Node->getNumOperands() <= 3) {
319  uint64_t Cur = Node->getNumOperands() == 2
320  ? 0
321  : mdconst::extract<ConstantInt>(Node->getOperand(2))
322  ->getZExtValue();
323  Offset -= Cur;
324  MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
325  if (!P)
326  return TBAAStructTypeNode();
327  return TBAAStructTypeNode(P);
328  }
329  }
330 
331  // Assume the offsets are in order. We return the previous field if
332  // the current offset is bigger than the given offset.
333  unsigned FirstFieldOpNo = NewFormat ? 3 : 1;
334  unsigned NumOpsPerField = NewFormat ? 3 : 2;
335  unsigned TheIdx = 0;
336  for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands();
337  Idx += NumOpsPerField) {
338  uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
339  ->getZExtValue();
340  if (Cur > Offset) {
341  assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
342  "TBAAStructTypeNode::getField should have an offset match!");
343  TheIdx = Idx - NumOpsPerField;
344  break;
345  }
346  }
347  // Move along the last field.
348  if (TheIdx == 0)
349  TheIdx = Node->getNumOperands() - NumOpsPerField;
350  uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
351  ->getZExtValue();
352  Offset -= Cur;
353  MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
354  if (!P)
355  return TBAAStructTypeNode();
356  return TBAAStructTypeNode(P);
357  }
358 };
359 
360 } // end anonymous namespace
361 
362 /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat
363 /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA
364 /// format.
365 static bool isStructPathTBAA(const MDNode *MD) {
366  // Anonymous TBAA root starts with a MDNode and dragonegg uses it as
367  // a TBAA tag.
368  return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
369 }
370 
372  const MemoryLocation &LocB,
373  AAQueryInfo &AAQI) {
374  if (!EnableTBAA)
375  return AAResultBase::alias(LocA, LocB, AAQI);
376 
377  // If accesses may alias, chain to the next AliasAnalysis.
378  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
379  return AAResultBase::alias(LocA, LocB, AAQI);
380 
381  // Otherwise return a definitive result.
382  return AliasResult::NoAlias;
383 }
384 
386  AAQueryInfo &AAQI,
387  bool OrLocal) {
388  if (!EnableTBAA)
389  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
390 
391  const MDNode *M = Loc.AATags.TBAA;
392  if (!M)
393  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
394 
395  // If this is an "immutable" type, we can assume the pointer is pointing
396  // to constant memory.
397  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
398  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
399  return true;
400 
401  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
402 }
403 
406  if (!EnableTBAA)
407  return AAResultBase::getModRefBehavior(Call);
408 
410 
411  // If this is an "immutable" type, we can assume the call doesn't write
412  // to memory.
413  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
414  if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
415  (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
416  Min = FMRB_OnlyReadsMemory;
417 
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 
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 }
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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
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:269
llvm::TypeBasedAA::run
TypeBasedAAResult run(Function &F, FunctionAnalysisManager &AM)
Definition: TypeBasedAliasAnalysis.cpp:711
llvm::Function
Definition: Function.h:61
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:1168
llvm::TypeBasedAAWrapperPass::TypeBasedAAWrapperPass
TypeBasedAAWrapperPass()
Definition: TypeBasedAliasAnalysis.cpp:723
ErrorHandling.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
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
T
#define T
Definition: Mips16ISelLowering.cpp:341
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:419
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
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:674
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:170
llvm::TypeBasedAAWrapperPass::doInitialization
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: TypeBasedAliasAnalysis.cpp:727
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:328
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1208
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1118
AliasAnalysis.h
llvm::AAMDNodes::shiftTBAA
static MDNode * shiftTBAA(MDNode *M, size_t off)
Definition: TypeBasedAliasAnalysis.cpp:741
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:414
Instruction.h
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:230
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
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:140
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:900
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:282
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1164
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1112
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:483
BaseType
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
Definition: SafepointIRVerifier.cpp:316
llvm::TypeBasedAAWrapperPass::ID
static char ID
Definition: TypeBasedAliasAnalysis.h:75
llvm::MDNode::intersect
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:928
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:365
MemoryLocation.h
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::X86II::TA
@ TA
Definition: X86BaseInfo.h:803
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
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:371
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:1974
llvm::createTypeBasedAAWrapperPass
ImmutablePass * createTypeBasedAAWrapperPass()
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::AAResultBase::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Definition: AliasAnalysis.h:1178
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:405
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:1532
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:524
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
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:941
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:454
llvm::AAResultBase::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1186
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:967
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:677
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
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:1169
llvm::AAMDNodes::TBAA
MDNode * TBAA
The tag for type-based alias analysis.
Definition: Metadata.h:668
llvm::AAMDNodes::concat
AAMDNodes concat(const AAMDNodes &Other) const
Determine the best AAMDNodes after concatenating two different locations together.
Definition: TypeBasedAliasAnalysis.cpp:533
llvm::X86II::TB
@ TB
Definition: X86BaseInfo.h:800
N
#define N
llvm::TypeBasedAAResult::pointsToConstantMemory
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal)
Definition: TypeBasedAliasAnalysis.cpp:385
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
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:44
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:275
EnableTBAA
static cl::opt< bool > EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden)
LLVMContext.h
llvm::M1
unsigned M1(unsigned Val)
Definition: VE.h:372
llvm::AMDGPU::VGPRIndexMode::Id
Id
Definition: SIDefines.h:228
llvm::MDString
A single uniqued string.
Definition: Metadata.h:611
InitializePasses.h
llvm::AAMDNodes::shiftTBAAStruct
static MDNode * shiftTBAAStruct(MDNode *M, size_t off)
Definition: TypeBasedAliasAnalysis.cpp:760
getAccessType
static MemAccessTy getAccessType(const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)
Return the type of the memory being accessed.
Definition: LoopStrengthReduce.cpp:881
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
SetVector.h
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37