Line data Source code
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 : //===----------------------------------------------------------------------===//
108 :
109 : #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
110 : #include "llvm/ADT/SetVector.h"
111 : #include "llvm/Analysis/AliasAnalysis.h"
112 : #include "llvm/Analysis/MemoryLocation.h"
113 : #include "llvm/IR/Constants.h"
114 : #include "llvm/IR/DerivedTypes.h"
115 : #include "llvm/IR/Instruction.h"
116 : #include "llvm/IR/LLVMContext.h"
117 : #include "llvm/IR/Metadata.h"
118 : #include "llvm/Pass.h"
119 : #include "llvm/Support/Casting.h"
120 : #include "llvm/Support/CommandLine.h"
121 : #include "llvm/Support/ErrorHandling.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 679 : 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 0 : TBAANodeImpl() = default;
154 310392 : explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
155 :
156 : /// getNode - Get the MDNode for this TBAANode.
157 0 : MDNodeTy *getNode() const { return Node; }
158 :
159 : /// isNewFormat - Return true iff the wrapped type node is in the new
160 : /// size-aware format.
161 0 : bool isNewFormat() const { return isNewFormatTypeNode(Node); }
162 :
163 : /// getParent - Get this TBAANode's Alias tree parent.
164 828896 : TBAANodeImpl<MDNodeTy> getParent() const {
165 828896 : if (isNewFormat())
166 139 : return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0)));
167 :
168 828757 : if (Node->getNumOperands() < 2)
169 310392 : return TBAANodeImpl<MDNodeTy>();
170 : MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
171 : if (!P)
172 0 : return TBAANodeImpl<MDNodeTy>();
173 : // Ok, this node has a valid parent. Return it.
174 518365 : 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 0 : bool isTypeImmutable() const {
181 0 : if (Node->getNumOperands() < 3)
182 0 : return false;
183 : ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2));
184 : if (!CI)
185 0 : return false;
186 0 : 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 483442 : explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
207 :
208 : /// Get the MDNode for this TBAAStructTagNode.
209 0 : MDNodeTy *getNode() const { return Node; }
210 :
211 : /// isNewFormat - Return true iff the wrapped access tag is in the new
212 : /// size-aware format.
213 0 : bool isNewFormat() const {
214 0 : if (Node->getNumOperands() < 4)
215 0 : return false;
216 : if (MDNodeTy *AccessType = getAccessType())
217 : if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat())
218 0 : return false;
219 : return true;
220 : }
221 :
222 0 : MDNodeTy *getBaseType() const {
223 0 : return dyn_cast_or_null<MDNode>(Node->getOperand(0));
224 : }
225 :
226 0 : MDNodeTy *getAccessType() const {
227 0 : return dyn_cast_or_null<MDNode>(Node->getOperand(1));
228 : }
229 :
230 0 : uint64_t getOffset() const {
231 0 : 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 483442 : bool isTypeImmutable() const {
244 483442 : unsigned OpNo = isNewFormat() ? 4 : 3;
245 483442 : 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 659 : 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 0 : TBAAStructTypeNode() = default;
270 264827 : explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
271 :
272 : /// Get the MDNode for this TBAAStructTypeNode.
273 0 : 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 0 : bool isNewFormat() const { return isNewFormatTypeNode(Node); }
278 :
279 : bool operator==(const TBAAStructTypeNode &Other) const {
280 55 : return getNode() == Other.getNode();
281 : }
282 :
283 : /// getId - Return type identifier.
284 0 : Metadata *getId() const {
285 0 : return Node->getOperand(isNewFormat() ? 2 : 0);
286 : }
287 :
288 110 : unsigned getNumFields() const {
289 110 : unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
290 : unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
291 110 : return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;
292 : }
293 :
294 55 : TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {
295 55 : unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
296 : unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
297 55 : unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;
298 : auto *TypeNode = cast<MDNode>(getNode()->getOperand(OpIndex));
299 55 : 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 769077 : TBAAStructTypeNode getField(uint64_t &Offset) const {
305 769077 : bool NewFormat = isNewFormat();
306 : if (NewFormat) {
307 : // New-format root and scalar type nodes have no fields.
308 79 : if (Node->getNumOperands() < 6)
309 0 : return TBAAStructTypeNode();
310 : } else {
311 : // Parent can be omitted for the root node.
312 768998 : if (Node->getNumOperands() < 2)
313 191077 : return TBAAStructTypeNode();
314 :
315 : // Fast path for a scalar type node and a struct type node with a single
316 : // field.
317 577921 : if (Node->getNumOperands() <= 3) {
318 : uint64_t Cur = Node->getNumOperands() == 2
319 432373 : ? 0
320 : : mdconst::extract<ConstantInt>(Node->getOperand(2))
321 : ->getZExtValue();
322 432373 : Offset -= Cur;
323 : MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
324 : if (!P)
325 0 : return TBAAStructTypeNode();
326 432373 : return TBAAStructTypeNode(P);
327 : }
328 : }
329 :
330 : // Assume the offsets are in order. We return the previous field if
331 : // the current offset is bigger than the given offset.
332 145627 : unsigned FirstFieldOpNo = NewFormat ? 3 : 1;
333 145627 : unsigned NumOpsPerField = NewFormat ? 3 : 2;
334 : unsigned TheIdx = 0;
335 551214 : for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands();
336 405587 : Idx += NumOpsPerField) {
337 : uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
338 518273 : ->getZExtValue();
339 518273 : if (Cur > Offset) {
340 : assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
341 : "TBAAStructTypeNode::getField should have an offset match!");
342 112686 : TheIdx = Idx - NumOpsPerField;
343 112686 : break;
344 : }
345 : }
346 : // Move along the last field.
347 145627 : if (TheIdx == 0)
348 32941 : TheIdx = Node->getNumOperands() - NumOpsPerField;
349 : uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
350 145627 : ->getZExtValue();
351 145627 : Offset -= Cur;
352 : MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
353 : if (!P)
354 0 : return TBAAStructTypeNode();
355 145627 : return TBAAStructTypeNode(P);
356 : }
357 : };
358 :
359 : } // end anonymous namespace
360 :
361 : /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat
362 : /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA
363 : /// format.
364 : static bool isStructPathTBAA(const MDNode *MD) {
365 : // Anonymous TBAA root starts with a MDNode and dragonegg uses it as
366 : // a TBAA tag.
367 966909 : return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
368 : }
369 :
370 6581675 : AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,
371 : const MemoryLocation &LocB) {
372 6581675 : if (!EnableTBAA)
373 : return AAResultBase::alias(LocA, LocB);
374 :
375 : // If accesses may alias, chain to the next AliasAnalysis.
376 6581675 : if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
377 6469779 : return AAResultBase::alias(LocA, LocB);
378 :
379 : // Otherwise return a definitive result.
380 : return NoAlias;
381 : }
382 :
383 6663153 : bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
384 : bool OrLocal) {
385 6663153 : if (!EnableTBAA)
386 : return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
387 :
388 6663153 : const MDNode *M = Loc.AATags.TBAA;
389 6663153 : if (!M)
390 : return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
391 :
392 : // If this is an "immutable" type, we can assume the pointer is pointing
393 : // to constant memory.
394 0 : if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
395 483276 : (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
396 639 : return true;
397 :
398 482637 : return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
399 : }
400 :
401 : FunctionModRefBehavior
402 10251478 : TypeBasedAAResult::getModRefBehavior(ImmutableCallSite CS) {
403 10251478 : if (!EnableTBAA)
404 : return AAResultBase::getModRefBehavior(CS);
405 :
406 : FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
407 :
408 : // If this is an "immutable" type, we can assume the call doesn't write
409 : // to memory.
410 3754896 : if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
411 0 : if ((!isStructPathTBAA(M) && TBAANode(M).isTypeImmutable()) ||
412 166 : (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
413 : Min = FMRB_OnlyReadsMemory;
414 :
415 10251478 : return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
416 : }
417 :
418 10159473 : FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) {
419 : // Functions don't have metadata. Just chain to the next implementation.
420 10159473 : return AAResultBase::getModRefBehavior(F);
421 : }
422 :
423 5407963 : ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS,
424 : const MemoryLocation &Loc) {
425 5407963 : if (!EnableTBAA)
426 : return AAResultBase::getModRefInfo(CS, Loc);
427 :
428 5407963 : if (const MDNode *L = Loc.AATags.TBAA)
429 144906 : if (const MDNode *M =
430 : CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
431 4 : if (!Aliases(L, M))
432 : return ModRefInfo::NoModRef;
433 :
434 5407963 : return AAResultBase::getModRefInfo(CS, Loc);
435 : }
436 :
437 2172907 : ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS1,
438 : ImmutableCallSite CS2) {
439 2172907 : if (!EnableTBAA)
440 : return AAResultBase::getModRefInfo(CS1, CS2);
441 :
442 30961 : if (const MDNode *M1 =
443 : CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
444 18 : if (const MDNode *M2 =
445 : CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa))
446 18 : if (!Aliases(M1, M2))
447 : return ModRefInfo::NoModRef;
448 :
449 2172899 : return AAResultBase::getModRefInfo(CS1, CS2);
450 : }
451 :
452 25 : bool MDNode::isTBAAVtableAccess() const {
453 : if (!isStructPathTBAA(this)) {
454 0 : if (getNumOperands() < 1)
455 : return false;
456 : if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
457 0 : if (Tag1->getString() == "vtable pointer")
458 : return true;
459 : }
460 0 : return false;
461 : }
462 :
463 : // For struct-path aware TBAA, we use the access type of the tag.
464 : TBAAStructTagNode Tag(this);
465 : TBAAStructTypeNode AccessType(Tag.getAccessType());
466 : if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
467 25 : if (Id->getString() == "vtable pointer")
468 22 : return true;
469 : return false;
470 : }
471 :
472 : static bool matchAccessTags(const MDNode *A, const MDNode *B,
473 : const MDNode **GenericTag = nullptr);
474 :
475 4724 : MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
476 : const MDNode *GenericTag;
477 4724 : matchAccessTags(A, B, &GenericTag);
478 4724 : return const_cast<MDNode*>(GenericTag);
479 : }
480 :
481 210464 : static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
482 210464 : if (!A || !B)
483 : return nullptr;
484 :
485 210464 : if (A == B)
486 : return A;
487 :
488 : SmallSetVector<const MDNode *, 4> PathA;
489 : TBAANode TA(A);
490 577185 : while (TA.getNode()) {
491 421989 : if (PathA.count(TA.getNode()))
492 0 : report_fatal_error("Cycle found in TBAA metadata.");
493 421989 : PathA.insert(TA.getNode());
494 421989 : TA = TA.getParent();
495 : }
496 :
497 : SmallSetVector<const MDNode *, 4> PathB;
498 : TBAANode TB(B);
499 562103 : while (TB.getNode()) {
500 406907 : if (PathB.count(TB.getNode()))
501 0 : report_fatal_error("Cycle found in TBAA metadata.");
502 406907 : PathB.insert(TB.getNode());
503 406907 : TB = TB.getParent();
504 : }
505 :
506 155196 : int IA = PathA.size() - 1;
507 155196 : int IB = PathB.size() - 1;
508 :
509 : const MDNode *Ret = nullptr;
510 440470 : while (IA >= 0 && IB >= 0) {
511 1100040 : if (PathA[IA] == PathB[IB])
512 : Ret = PathA[IA];
513 : else
514 : break;
515 285274 : --IA;
516 285274 : --IB;
517 : }
518 :
519 : return Ret;
520 : }
521 :
522 52466266 : void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {
523 52466266 : if (Merge)
524 223 : N.TBAA =
525 223 : MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa));
526 : else
527 52466043 : N.TBAA = getMetadata(LLVMContext::MD_tbaa);
528 :
529 52466266 : if (Merge)
530 223 : N.Scope = MDNode::getMostGenericAliasScope(
531 : N.Scope, getMetadata(LLVMContext::MD_alias_scope));
532 : else
533 52466043 : N.Scope = getMetadata(LLVMContext::MD_alias_scope);
534 :
535 52466266 : if (Merge)
536 223 : N.NoAlias =
537 223 : MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
538 : else
539 52466043 : N.NoAlias = getMetadata(LLVMContext::MD_noalias);
540 52466266 : }
541 :
542 491 : static const MDNode *createAccessTag(const MDNode *AccessType) {
543 : // If there is no access type or the access type is the root node, then
544 : // we don't have any useful access tag to return.
545 491 : if (!AccessType || AccessType->getNumOperands() < 2)
546 : return nullptr;
547 :
548 489 : Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
549 489 : auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
550 :
551 : if (TBAAStructTypeNode(AccessType).isNewFormat()) {
552 : // TODO: Take access ranges into account when matching access tags and
553 : // fix this code to generate actual access sizes for generic tags.
554 : uint64_t AccessSize = UINT64_MAX;
555 : auto *SizeNode =
556 0 : ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
557 : Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
558 : const_cast<MDNode*>(AccessType),
559 0 : OffsetNode, SizeNode};
560 : return MDNode::get(AccessType->getContext(), Ops);
561 : }
562 :
563 : Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
564 : const_cast<MDNode*>(AccessType),
565 489 : OffsetNode};
566 : return MDNode::get(AccessType->getContext(), Ops);
567 : }
568 :
569 110 : static bool hasField(TBAAStructTypeNode BaseType,
570 : TBAAStructTypeNode FieldType) {
571 133 : for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {
572 55 : TBAAStructTypeNode T = BaseType.getFieldType(I);
573 55 : if (T == FieldType || hasField(T, FieldType))
574 32 : return true;
575 : }
576 : return false;
577 : }
578 :
579 : /// Return true if for two given accesses, one of the accessed objects may be a
580 : /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
581 : /// describe the accesses to the base object and the subobject respectively.
582 : /// \p CommonType must be the metadata node describing the common type of the
583 : /// accessed objects. On return, \p MayAlias is set to true iff these accesses
584 : /// may alias and \p Generic, if not null, points to the most generic access
585 : /// tag for the given two.
586 306797 : static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
587 : TBAAStructTagNode SubobjectTag,
588 : const MDNode *CommonType,
589 : const MDNode **GenericTag,
590 : bool &MayAlias) {
591 : // If the base object is of the least common type, then this may be an access
592 : // to its subobject.
593 432163 : if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
594 : BaseTag.getAccessType() == CommonType) {
595 41970 : if (GenericTag)
596 54 : *GenericTag = createAccessTag(CommonType);
597 41970 : MayAlias = true;
598 41970 : return true;
599 : }
600 :
601 : // If the access to the base object is through a field of the subobject's
602 : // type, then this may be an access to that field. To check for that we start
603 : // from the base type, follow the edge with the correct offset in the type DAG
604 : // and adjust the offset until we reach the field type or until we reach the
605 : // access type.
606 264827 : bool NewFormat = BaseTag.isNewFormat();
607 : TBAAStructTypeNode BaseType(BaseTag.getBaseType());
608 264827 : uint64_t OffsetInBase = BaseTag.getOffset();
609 :
610 : for (;;) {
611 : // In the old format there is no distinction between fields and parent
612 : // types, so in this case we consider all nodes up to the root.
613 1033904 : if (!BaseType.getNode()) {
614 : assert(!NewFormat && "Did not see access type in access path!");
615 : break;
616 : }
617 :
618 842827 : if (BaseType.getNode() == SubobjectTag.getBaseType()) {
619 73671 : bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
620 73671 : if (GenericTag) {
621 848 : *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
622 369 : createAccessTag(CommonType);
623 : }
624 73671 : MayAlias = SameMemberAccess;
625 73671 : return true;
626 : }
627 :
628 : // With new-format nodes we stop at the access type.
629 769314 : if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
630 : break;
631 :
632 : // Follow the edge with the correct offset. Offset will be adjusted to
633 : // be relative to the field type.
634 769077 : BaseType = BaseType.getField(OffsetInBase);
635 769077 : }
636 :
637 : // If the base object has a direct or indirect field of the subobject's type,
638 : // then this may be an access to that field. We need this to check now that
639 : // we support aggregates as access types.
640 191156 : if (NewFormat) {
641 : // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
642 : TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
643 79 : if (hasField(BaseType, FieldType)) {
644 24 : if (GenericTag)
645 0 : *GenericTag = createAccessTag(CommonType);
646 24 : MayAlias = true;
647 24 : return true;
648 : }
649 : }
650 :
651 : return false;
652 : }
653 :
654 : /// matchTags - Return true if the given couple of accesses are allowed to
655 : /// overlap. If \arg GenericTag is not null, then on return it points to the
656 : /// most generic access descriptor for the given two.
657 6586421 : static bool matchAccessTags(const MDNode *A, const MDNode *B,
658 : const MDNode **GenericTag) {
659 6586421 : if (A == B) {
660 4856753 : if (GenericTag)
661 4100 : *GenericTag = A;
662 4856753 : return true;
663 : }
664 :
665 : // Accesses with no TBAA information may alias with any other accesses.
666 1729668 : if (!A || !B) {
667 1519204 : if (GenericTag)
668 21 : *GenericTag = nullptr;
669 1519204 : return true;
670 : }
671 :
672 : // Verify that both input nodes are struct-path aware. Auto-upgrade should
673 : // have taken care of this.
674 : assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
675 : assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
676 :
677 : TBAAStructTagNode TagA(A), TagB(B);
678 210464 : const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
679 : TagB.getAccessType());
680 :
681 : // If the final access types have different roots, they're part of different
682 : // potentially unrelated type systems, so we must be conservative.
683 210464 : if (!CommonType) {
684 13 : if (GenericTag)
685 2 : *GenericTag = nullptr;
686 13 : return true;
687 : }
688 :
689 : // If one of the accessed objects may be a subobject of the other, then such
690 : // accesses may alias.
691 : bool MayAlias;
692 210451 : if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
693 306797 : CommonType, GenericTag, MayAlias) ||
694 96346 : mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
695 : CommonType, GenericTag, MayAlias))
696 115665 : return MayAlias;
697 :
698 : // Otherwise, we've proved there's no alias.
699 94786 : if (GenericTag)
700 68 : *GenericTag = createAccessTag(CommonType);
701 : return false;
702 : }
703 :
704 : /// Aliases - Test whether the access represented by tag A may alias the
705 : /// access represented by tag B.
706 6581697 : bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
707 6581697 : return matchAccessTags(A, B);
708 : }
709 :
710 : AnalysisKey TypeBasedAA::Key;
711 :
712 195 : TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) {
713 195 : return TypeBasedAAResult();
714 : }
715 :
716 : char TypeBasedAAWrapperPass::ID = 0;
717 211733 : INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
718 : false, true)
719 :
720 30109 : ImmutablePass *llvm::createTypeBasedAAWrapperPass() {
721 30109 : return new TypeBasedAAWrapperPass();
722 : }
723 :
724 60346 : TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) {
725 30173 : initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry());
726 30173 : }
727 :
728 30031 : bool TypeBasedAAWrapperPass::doInitialization(Module &M) {
729 30031 : Result.reset(new TypeBasedAAResult());
730 30031 : return false;
731 : }
732 :
733 29880 : bool TypeBasedAAWrapperPass::doFinalization(Module &M) {
734 : Result.reset();
735 29880 : return false;
736 : }
737 :
738 30035 : void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
739 : AU.setPreservesAll();
740 30035 : }
|
