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 | |
108 | #include "llvm/Analysis/TypeBasedAliasAnalysis.h" |
109 | #include "llvm/ADT/SetVector.h" |
110 | #include "llvm/Analysis/AliasAnalysis.h" |
111 | #include "llvm/Analysis/MemoryLocation.h" |
112 | #include "llvm/IR/Constants.h" |
113 | #include "llvm/IR/DerivedTypes.h" |
114 | #include "llvm/IR/InstrTypes.h" |
115 | #include "llvm/IR/LLVMContext.h" |
116 | #include "llvm/IR/Metadata.h" |
117 | #include "llvm/InitializePasses.h" |
118 | #include "llvm/Pass.h" |
119 | #include "llvm/Support/Casting.h" |
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(Val: true), cl::Hidden); |
131 | |
132 | namespace { |
133 | |
134 | /// isNewFormatTypeNode - Return true iff the given type node is in the new |
135 | /// size-aware format. |
136 | static bool isNewFormatTypeNode(const MDNode *N) { |
137 | if (N->getNumOperands() < 3) |
138 | return false; |
139 | // In the old format the first operand is a string. |
140 | if (!isa<MDNode>(Val: N->getOperand(I: 0))) |
141 | return false; |
142 | return true; |
143 | } |
144 | |
145 | /// This is a simple wrapper around an MDNode which provides a higher-level |
146 | /// interface by hiding the details of how alias analysis information is encoded |
147 | /// in its operands. |
148 | template<typename MDNodeTy> |
149 | class TBAANodeImpl { |
150 | MDNodeTy *Node = nullptr; |
151 | |
152 | public: |
153 | TBAANodeImpl() = default; |
154 | explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {} |
155 | |
156 | /// getNode - Get the MDNode for this TBAANode. |
157 | MDNodeTy *getNode() const { return Node; } |
158 | |
159 | /// isNewFormat - Return true iff the wrapped type node is in the new |
160 | /// size-aware format. |
161 | bool isNewFormat() const { return isNewFormatTypeNode(Node); } |
162 | |
163 | /// getParent - Get this TBAANode's Alias tree parent. |
164 | TBAANodeImpl<MDNodeTy> getParent() const { |
165 | if (isNewFormat()) |
166 | return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0))); |
167 | |
168 | if (Node->getNumOperands() < 2) |
169 | return TBAANodeImpl<MDNodeTy>(); |
170 | MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1)); |
171 | if (!P) |
172 | return TBAANodeImpl<MDNodeTy>(); |
173 | // Ok, this node has a valid parent. Return it. |
174 | return TBAANodeImpl<MDNodeTy>(P); |
175 | } |
176 | |
177 | /// Test if this TBAANode represents a type for objects which are |
178 | /// not modified (by any means) in the context where this |
179 | /// AliasAnalysis is relevant. |
180 | bool isTypeImmutable() const { |
181 | if (Node->getNumOperands() < 3) |
182 | return false; |
183 | ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2)); |
184 | if (!CI) |
185 | return false; |
186 | return CI->getValue()[0]; |
187 | } |
188 | }; |
189 | |
190 | /// \name Specializations of \c TBAANodeImpl for const and non const qualified |
191 | /// \c MDNode. |
192 | /// @{ |
193 | using TBAANode = TBAANodeImpl<const MDNode>; |
194 | using MutableTBAANode = TBAANodeImpl<MDNode>; |
195 | /// @} |
196 | |
197 | /// This is a simple wrapper around an MDNode which provides a |
198 | /// higher-level interface by hiding the details of how alias analysis |
199 | /// information is encoded in its operands. |
200 | template<typename MDNodeTy> |
201 | class TBAAStructTagNodeImpl { |
202 | /// This node should be created with createTBAAAccessTag(). |
203 | MDNodeTy *Node; |
204 | |
205 | public: |
206 | explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {} |
207 | |
208 | /// Get the MDNode for this TBAAStructTagNode. |
209 | MDNodeTy *getNode() const { return Node; } |
210 | |
211 | /// isNewFormat - Return true iff the wrapped access tag is in the new |
212 | /// size-aware format. |
213 | bool isNewFormat() const { |
214 | if (Node->getNumOperands() < 4) |
215 | return false; |
216 | if (MDNodeTy *AccessType = getAccessType()) |
217 | if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat()) |
218 | return false; |
219 | return true; |
220 | } |
221 | |
222 | MDNodeTy *getBaseType() const { |
223 | return dyn_cast_or_null<MDNode>(Node->getOperand(0)); |
224 | } |
225 | |
226 | MDNodeTy *getAccessType() const { |
227 | return dyn_cast_or_null<MDNode>(Node->getOperand(1)); |
228 | } |
229 | |
230 | uint64_t getOffset() const { |
231 | return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue(); |
232 | } |
233 | |
234 | uint64_t getSize() const { |
235 | if (!isNewFormat()) |
236 | return UINT64_MAX; |
237 | return mdconst::extract<ConstantInt>(Node->getOperand(3))->getZExtValue(); |
238 | } |
239 | |
240 | /// Test if this TBAAStructTagNode represents a type for objects |
241 | /// which are not modified (by any means) in the context where this |
242 | /// AliasAnalysis is relevant. |
243 | bool isTypeImmutable() const { |
244 | unsigned OpNo = isNewFormat() ? 4 : 3; |
245 | if (Node->getNumOperands() < OpNo + 1) |
246 | return false; |
247 | ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(OpNo)); |
248 | if (!CI) |
249 | return false; |
250 | return CI->getValue()[0]; |
251 | } |
252 | }; |
253 | |
254 | /// \name Specializations of \c TBAAStructTagNodeImpl for const and non const |
255 | /// qualified \c MDNods. |
256 | /// @{ |
257 | using TBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>; |
258 | using MutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>; |
259 | /// @} |
260 | |
261 | /// This is a simple wrapper around an MDNode which provides a |
262 | /// higher-level interface by hiding the details of how alias analysis |
263 | /// information is encoded in its operands. |
264 | class TBAAStructTypeNode { |
265 | /// This node should be created with createTBAATypeNode(). |
266 | const MDNode *Node = nullptr; |
267 | |
268 | public: |
269 | TBAAStructTypeNode() = default; |
270 | explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} |
271 | |
272 | /// Get the MDNode for this TBAAStructTypeNode. |
273 | const MDNode *getNode() const { return Node; } |
274 | |
275 | /// isNewFormat - Return true iff the wrapped type node is in the new |
276 | /// size-aware format. |
277 | bool isNewFormat() const { return isNewFormatTypeNode(N: Node); } |
278 | |
279 | bool operator==(const TBAAStructTypeNode &Other) const { |
280 | return getNode() == Other.getNode(); |
281 | } |
282 | |
283 | /// getId - Return type identifier. |
284 | Metadata *getId() const { |
285 | return Node->getOperand(I: isNewFormat() ? 2 : 0); |
286 | } |
287 | |
288 | unsigned getNumFields() const { |
289 | unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; |
290 | unsigned NumOpsPerField = isNewFormat() ? 3 : 2; |
291 | return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField; |
292 | } |
293 | |
294 | TBAAStructTypeNode getFieldType(unsigned FieldIndex) const { |
295 | unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; |
296 | unsigned NumOpsPerField = isNewFormat() ? 3 : 2; |
297 | unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField; |
298 | auto *TypeNode = cast<MDNode>(Val: getNode()->getOperand(I: OpIndex)); |
299 | return TBAAStructTypeNode(TypeNode); |
300 | } |
301 | |
302 | /// Get this TBAAStructTypeNode's field in the type DAG with |
303 | /// given offset. Update the offset to be relative to the field type. |
304 | TBAAStructTypeNode getField(uint64_t &Offset) const { |
305 | bool NewFormat = isNewFormat(); |
306 | const ArrayRef<MDOperand> Operands = Node->operands(); |
307 | const unsigned NumOperands = Operands.size(); |
308 | |
309 | if (NewFormat) { |
310 | // New-format root and scalar type nodes have no fields. |
311 | if (NumOperands < 6) |
312 | return TBAAStructTypeNode(); |
313 | } else { |
314 | // Parent can be omitted for the root node. |
315 | if (NumOperands < 2) |
316 | return TBAAStructTypeNode(); |
317 | |
318 | // Fast path for a scalar type node and a struct type node with a single |
319 | // field. |
320 | if (NumOperands <= 3) { |
321 | uint64_t Cur = |
322 | NumOperands == 2 |
323 | ? 0 |
324 | : mdconst::extract<ConstantInt>(MD: Operands[2])->getZExtValue(); |
325 | Offset -= Cur; |
326 | MDNode *P = dyn_cast_or_null<MDNode>(Val: Operands[1]); |
327 | if (!P) |
328 | return TBAAStructTypeNode(); |
329 | return TBAAStructTypeNode(P); |
330 | } |
331 | } |
332 | |
333 | // Assume the offsets are in order. We return the previous field if |
334 | // the current offset is bigger than the given offset. |
335 | unsigned FirstFieldOpNo = NewFormat ? 3 : 1; |
336 | unsigned NumOpsPerField = NewFormat ? 3 : 2; |
337 | unsigned TheIdx = 0; |
338 | |
339 | for (unsigned Idx = FirstFieldOpNo; Idx < NumOperands; |
340 | Idx += NumOpsPerField) { |
341 | uint64_t Cur = |
342 | mdconst::extract<ConstantInt>(MD: Operands[Idx + 1])->getZExtValue(); |
343 | if (Cur > Offset) { |
344 | assert(Idx >= FirstFieldOpNo + NumOpsPerField && |
345 | "TBAAStructTypeNode::getField should have an offset match!" ); |
346 | TheIdx = Idx - NumOpsPerField; |
347 | break; |
348 | } |
349 | } |
350 | // Move along the last field. |
351 | if (TheIdx == 0) |
352 | TheIdx = NumOperands - NumOpsPerField; |
353 | uint64_t Cur = |
354 | mdconst::extract<ConstantInt>(MD: Operands[TheIdx + 1])->getZExtValue(); |
355 | Offset -= Cur; |
356 | MDNode *P = dyn_cast_or_null<MDNode>(Val: Operands[TheIdx]); |
357 | if (!P) |
358 | return TBAAStructTypeNode(); |
359 | return TBAAStructTypeNode(P); |
360 | } |
361 | }; |
362 | |
363 | } // end anonymous namespace |
364 | |
365 | /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat |
366 | /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA |
367 | /// format. |
368 | static bool isStructPathTBAA(const MDNode *MD) { |
369 | // Anonymous TBAA root starts with a MDNode and dragonegg uses it as |
370 | // a TBAA tag. |
371 | return isa<MDNode>(Val: MD->getOperand(I: 0)) && MD->getNumOperands() >= 3; |
372 | } |
373 | |
374 | AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA, |
375 | const MemoryLocation &LocB, |
376 | AAQueryInfo &AAQI, const Instruction *) { |
377 | if (!EnableTBAA) |
378 | return AliasResult::MayAlias; |
379 | |
380 | if (Aliases(A: LocA.AATags.TBAA, B: LocB.AATags.TBAA)) |
381 | return AliasResult::MayAlias; |
382 | |
383 | // Otherwise return a definitive result. |
384 | return AliasResult::NoAlias; |
385 | } |
386 | |
387 | ModRefInfo TypeBasedAAResult::getModRefInfoMask(const MemoryLocation &Loc, |
388 | AAQueryInfo &AAQI, |
389 | bool IgnoreLocals) { |
390 | if (!EnableTBAA) |
391 | return ModRefInfo::ModRef; |
392 | |
393 | const MDNode *M = Loc.AATags.TBAA; |
394 | if (!M) |
395 | return ModRefInfo::ModRef; |
396 | |
397 | // If this is an "immutable" type, we can assume the pointer is pointing |
398 | // to constant memory. |
399 | if ((!isStructPathTBAA(MD: M) && TBAANode(M).isTypeImmutable()) || |
400 | (isStructPathTBAA(MD: M) && TBAAStructTagNode(M).isTypeImmutable())) |
401 | return ModRefInfo::NoModRef; |
402 | |
403 | return ModRefInfo::ModRef; |
404 | } |
405 | |
406 | MemoryEffects TypeBasedAAResult::getMemoryEffects(const CallBase *Call, |
407 | AAQueryInfo &AAQI) { |
408 | if (!EnableTBAA) |
409 | return MemoryEffects::unknown(); |
410 | |
411 | // If this is an "immutable" type, the access is not observable. |
412 | if (const MDNode *M = Call->getMetadata(KindID: LLVMContext::MD_tbaa)) |
413 | if ((!isStructPathTBAA(MD: M) && TBAANode(M).isTypeImmutable()) || |
414 | (isStructPathTBAA(MD: M) && TBAAStructTagNode(M).isTypeImmutable())) |
415 | return MemoryEffects::none(); |
416 | |
417 | return MemoryEffects::unknown(); |
418 | } |
419 | |
420 | MemoryEffects TypeBasedAAResult::getMemoryEffects(const Function *F) { |
421 | // Functions don't have metadata. |
422 | return MemoryEffects::unknown(); |
423 | } |
424 | |
425 | ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call, |
426 | const MemoryLocation &Loc, |
427 | AAQueryInfo &AAQI) { |
428 | if (!EnableTBAA) |
429 | return ModRefInfo::ModRef; |
430 | |
431 | if (const MDNode *L = Loc.AATags.TBAA) |
432 | if (const MDNode *M = Call->getMetadata(KindID: LLVMContext::MD_tbaa)) |
433 | if (!Aliases(A: L, B: M)) |
434 | return ModRefInfo::NoModRef; |
435 | |
436 | return ModRefInfo::ModRef; |
437 | } |
438 | |
439 | ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call1, |
440 | const CallBase *Call2, |
441 | AAQueryInfo &AAQI) { |
442 | if (!EnableTBAA) |
443 | return ModRefInfo::ModRef; |
444 | |
445 | if (const MDNode *M1 = Call1->getMetadata(KindID: LLVMContext::MD_tbaa)) |
446 | if (const MDNode *M2 = Call2->getMetadata(KindID: LLVMContext::MD_tbaa)) |
447 | if (!Aliases(A: M1, B: M2)) |
448 | return ModRefInfo::NoModRef; |
449 | |
450 | return ModRefInfo::ModRef; |
451 | } |
452 | |
453 | bool MDNode::isTBAAVtableAccess() const { |
454 | if (!isStructPathTBAA(MD: this)) { |
455 | if (getNumOperands() < 1) |
456 | return false; |
457 | if (MDString *Tag1 = dyn_cast<MDString>(Val: getOperand(I: 0))) { |
458 | if (Tag1->getString() == "vtable pointer" ) |
459 | return true; |
460 | } |
461 | return false; |
462 | } |
463 | |
464 | // For struct-path aware TBAA, we use the access type of the tag. |
465 | TBAAStructTagNode Tag(this); |
466 | TBAAStructTypeNode AccessType(Tag.getAccessType()); |
467 | if(auto *Id = dyn_cast<MDString>(Val: AccessType.getId())) |
468 | if (Id->getString() == "vtable pointer" ) |
469 | return true; |
470 | return false; |
471 | } |
472 | |
473 | static bool matchAccessTags(const MDNode *A, const MDNode *B, |
474 | const MDNode **GenericTag = nullptr); |
475 | |
476 | MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { |
477 | const MDNode *GenericTag; |
478 | matchAccessTags(A, B, GenericTag: &GenericTag); |
479 | return const_cast<MDNode*>(GenericTag); |
480 | } |
481 | |
482 | static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) { |
483 | if (!A || !B) |
484 | return nullptr; |
485 | |
486 | if (A == B) |
487 | return A; |
488 | |
489 | SmallSetVector<const MDNode *, 4> PathA; |
490 | TBAANode TA(A); |
491 | while (TA.getNode()) { |
492 | if (!PathA.insert(X: TA.getNode())) |
493 | report_fatal_error(reason: "Cycle found in TBAA metadata." ); |
494 | TA = TA.getParent(); |
495 | } |
496 | |
497 | SmallSetVector<const MDNode *, 4> PathB; |
498 | TBAANode TB(B); |
499 | while (TB.getNode()) { |
500 | if (!PathB.insert(X: TB.getNode())) |
501 | report_fatal_error(reason: "Cycle found in TBAA metadata." ); |
502 | TB = TB.getParent(); |
503 | } |
504 | |
505 | int IA = PathA.size() - 1; |
506 | int IB = PathB.size() - 1; |
507 | |
508 | const MDNode *Ret = nullptr; |
509 | while (IA >= 0 && IB >= 0) { |
510 | if (PathA[IA] == PathB[IB]) |
511 | Ret = PathA[IA]; |
512 | else |
513 | break; |
514 | --IA; |
515 | --IB; |
516 | } |
517 | |
518 | return Ret; |
519 | } |
520 | |
521 | AAMDNodes AAMDNodes::merge(const AAMDNodes &Other) const { |
522 | AAMDNodes Result; |
523 | Result.TBAA = MDNode::getMostGenericTBAA(A: TBAA, B: Other.TBAA); |
524 | Result.TBAAStruct = nullptr; |
525 | Result.Scope = MDNode::getMostGenericAliasScope(A: Scope, B: Other.Scope); |
526 | Result.NoAlias = MDNode::intersect(A: NoAlias, B: Other.NoAlias); |
527 | return Result; |
528 | } |
529 | |
530 | AAMDNodes AAMDNodes::concat(const AAMDNodes &Other) const { |
531 | AAMDNodes Result; |
532 | Result.TBAA = Result.TBAAStruct = nullptr; |
533 | Result.Scope = MDNode::getMostGenericAliasScope(A: Scope, B: Other.Scope); |
534 | Result.NoAlias = MDNode::intersect(A: NoAlias, B: Other.NoAlias); |
535 | return Result; |
536 | } |
537 | |
538 | static const MDNode *createAccessTag(const MDNode *AccessType) { |
539 | // If there is no access type or the access type is the root node, then |
540 | // we don't have any useful access tag to return. |
541 | if (!AccessType || AccessType->getNumOperands() < 2) |
542 | return nullptr; |
543 | |
544 | Type *Int64 = IntegerType::get(C&: AccessType->getContext(), NumBits: 64); |
545 | auto *OffsetNode = ConstantAsMetadata::get(C: ConstantInt::get(Ty: Int64, V: 0)); |
546 | |
547 | if (TBAAStructTypeNode(AccessType).isNewFormat()) { |
548 | // TODO: Take access ranges into account when matching access tags and |
549 | // fix this code to generate actual access sizes for generic tags. |
550 | uint64_t AccessSize = UINT64_MAX; |
551 | auto *SizeNode = |
552 | ConstantAsMetadata::get(C: ConstantInt::get(Ty: Int64, V: AccessSize)); |
553 | Metadata *Ops[] = {const_cast<MDNode*>(AccessType), |
554 | const_cast<MDNode*>(AccessType), |
555 | OffsetNode, SizeNode}; |
556 | return MDNode::get(Context&: AccessType->getContext(), MDs: Ops); |
557 | } |
558 | |
559 | Metadata *Ops[] = {const_cast<MDNode*>(AccessType), |
560 | const_cast<MDNode*>(AccessType), |
561 | OffsetNode}; |
562 | return MDNode::get(Context&: AccessType->getContext(), MDs: Ops); |
563 | } |
564 | |
565 | static bool hasField(TBAAStructTypeNode BaseType, |
566 | TBAAStructTypeNode FieldType) { |
567 | for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) { |
568 | TBAAStructTypeNode T = BaseType.getFieldType(FieldIndex: I); |
569 | if (T == FieldType || hasField(BaseType: T, FieldType)) |
570 | return true; |
571 | } |
572 | return false; |
573 | } |
574 | |
575 | /// Return true if for two given accesses, one of the accessed objects may be a |
576 | /// subobject of the other. The \p BaseTag and \p SubobjectTag parameters |
577 | /// describe the accesses to the base object and the subobject respectively. |
578 | /// \p CommonType must be the metadata node describing the common type of the |
579 | /// accessed objects. On return, \p MayAlias is set to true iff these accesses |
580 | /// may alias and \p Generic, if not null, points to the most generic access |
581 | /// tag for the given two. |
582 | static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag, |
583 | TBAAStructTagNode SubobjectTag, |
584 | const MDNode *CommonType, |
585 | const MDNode **GenericTag, |
586 | bool &MayAlias) { |
587 | // If the base object is of the least common type, then this may be an access |
588 | // to its subobject. |
589 | if (BaseTag.getAccessType() == BaseTag.getBaseType() && |
590 | BaseTag.getAccessType() == CommonType) { |
591 | if (GenericTag) |
592 | *GenericTag = createAccessTag(AccessType: CommonType); |
593 | MayAlias = true; |
594 | return true; |
595 | } |
596 | |
597 | // If the access to the base object is through a field of the subobject's |
598 | // type, then this may be an access to that field. To check for that we start |
599 | // from the base type, follow the edge with the correct offset in the type DAG |
600 | // and adjust the offset until we reach the field type or until we reach the |
601 | // access type. |
602 | bool NewFormat = BaseTag.isNewFormat(); |
603 | TBAAStructTypeNode BaseType(BaseTag.getBaseType()); |
604 | uint64_t OffsetInBase = BaseTag.getOffset(); |
605 | |
606 | for (;;) { |
607 | // In the old format there is no distinction between fields and parent |
608 | // types, so in this case we consider all nodes up to the root. |
609 | if (!BaseType.getNode()) { |
610 | assert(!NewFormat && "Did not see access type in access path!" ); |
611 | break; |
612 | } |
613 | |
614 | if (BaseType.getNode() == SubobjectTag.getBaseType()) { |
615 | bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset(); |
616 | if (GenericTag) { |
617 | *GenericTag = SameMemberAccess ? SubobjectTag.getNode() : |
618 | createAccessTag(AccessType: CommonType); |
619 | } |
620 | MayAlias = SameMemberAccess; |
621 | return true; |
622 | } |
623 | |
624 | // With new-format nodes we stop at the access type. |
625 | if (NewFormat && BaseType.getNode() == BaseTag.getAccessType()) |
626 | break; |
627 | |
628 | // Follow the edge with the correct offset. Offset will be adjusted to |
629 | // be relative to the field type. |
630 | BaseType = BaseType.getField(Offset&: OffsetInBase); |
631 | } |
632 | |
633 | // If the base object has a direct or indirect field of the subobject's type, |
634 | // then this may be an access to that field. We need this to check now that |
635 | // we support aggregates as access types. |
636 | if (NewFormat) { |
637 | // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType()); |
638 | TBAAStructTypeNode FieldType(SubobjectTag.getBaseType()); |
639 | if (hasField(BaseType, FieldType)) { |
640 | if (GenericTag) |
641 | *GenericTag = createAccessTag(AccessType: CommonType); |
642 | MayAlias = true; |
643 | return true; |
644 | } |
645 | } |
646 | |
647 | return false; |
648 | } |
649 | |
650 | /// matchTags - Return true if the given couple of accesses are allowed to |
651 | /// overlap. If \arg GenericTag is not null, then on return it points to the |
652 | /// most generic access descriptor for the given two. |
653 | static bool matchAccessTags(const MDNode *A, const MDNode *B, |
654 | const MDNode **GenericTag) { |
655 | if (A == B) { |
656 | if (GenericTag) |
657 | *GenericTag = A; |
658 | return true; |
659 | } |
660 | |
661 | // Accesses with no TBAA information may alias with any other accesses. |
662 | if (!A || !B) { |
663 | if (GenericTag) |
664 | *GenericTag = nullptr; |
665 | return true; |
666 | } |
667 | |
668 | // Verify that both input nodes are struct-path aware. Auto-upgrade should |
669 | // have taken care of this. |
670 | assert(isStructPathTBAA(A) && "Access A is not struct-path aware!" ); |
671 | assert(isStructPathTBAA(B) && "Access B is not struct-path aware!" ); |
672 | |
673 | TBAAStructTagNode TagA(A), TagB(B); |
674 | const MDNode *CommonType = getLeastCommonType(A: TagA.getAccessType(), |
675 | B: TagB.getAccessType()); |
676 | |
677 | // If the final access types have different roots, they're part of different |
678 | // potentially unrelated type systems, so we must be conservative. |
679 | if (!CommonType) { |
680 | if (GenericTag) |
681 | *GenericTag = nullptr; |
682 | return true; |
683 | } |
684 | |
685 | // If one of the accessed objects may be a subobject of the other, then such |
686 | // accesses may alias. |
687 | bool MayAlias; |
688 | if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB, |
689 | CommonType, GenericTag, MayAlias) || |
690 | mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA, |
691 | CommonType, GenericTag, MayAlias)) |
692 | return MayAlias; |
693 | |
694 | // Otherwise, we've proved there's no alias. |
695 | if (GenericTag) |
696 | *GenericTag = createAccessTag(AccessType: CommonType); |
697 | return false; |
698 | } |
699 | |
700 | /// Aliases - Test whether the access represented by tag A may alias the |
701 | /// access represented by tag B. |
702 | bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const { |
703 | return matchAccessTags(A, B); |
704 | } |
705 | |
706 | AnalysisKey TypeBasedAA::Key; |
707 | |
708 | TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) { |
709 | return TypeBasedAAResult(); |
710 | } |
711 | |
712 | char TypeBasedAAWrapperPass::ID = 0; |
713 | INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa" , "Type-Based Alias Analysis" , |
714 | false, true) |
715 | |
716 | ImmutablePass *llvm::createTypeBasedAAWrapperPass() { |
717 | return new TypeBasedAAWrapperPass(); |
718 | } |
719 | |
720 | TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) { |
721 | initializeTypeBasedAAWrapperPassPass(Registry&: *PassRegistry::getPassRegistry()); |
722 | } |
723 | |
724 | bool TypeBasedAAWrapperPass::doInitialization(Module &M) { |
725 | Result.reset(p: new TypeBasedAAResult()); |
726 | return false; |
727 | } |
728 | |
729 | bool TypeBasedAAWrapperPass::doFinalization(Module &M) { |
730 | Result.reset(); |
731 | return false; |
732 | } |
733 | |
734 | void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
735 | AU.setPreservesAll(); |
736 | } |
737 | |
738 | MDNode *AAMDNodes::shiftTBAA(MDNode *MD, size_t Offset) { |
739 | // Fast path if there's no offset |
740 | if (Offset == 0) |
741 | return MD; |
742 | // Fast path if there's no path tbaa node (and thus scalar) |
743 | if (!isStructPathTBAA(MD)) |
744 | return MD; |
745 | |
746 | // The correct behavior here is to add the offset into the TBAA |
747 | // struct node offset. The base type, however may not have defined |
748 | // a type at this additional offset, resulting in errors. Since |
749 | // this method is only used within a given load/store access |
750 | // the offset provided is only used to subdivide the previous load |
751 | // maintaining the validity of the previous TBAA. |
752 | // |
753 | // This, however, should be revisited in the future. |
754 | return MD; |
755 | } |
756 | |
757 | MDNode *AAMDNodes::shiftTBAAStruct(MDNode *MD, size_t Offset) { |
758 | // Fast path if there's no offset |
759 | if (Offset == 0) |
760 | return MD; |
761 | SmallVector<Metadata *, 3> Sub; |
762 | for (size_t i = 0, size = MD->getNumOperands(); i < size; i += 3) { |
763 | ConstantInt *InnerOffset = mdconst::extract<ConstantInt>(MD: MD->getOperand(I: i)); |
764 | ConstantInt *InnerSize = |
765 | mdconst::extract<ConstantInt>(MD: MD->getOperand(I: i + 1)); |
766 | // Don't include any triples that aren't in bounds |
767 | if (InnerOffset->getZExtValue() + InnerSize->getZExtValue() <= Offset) |
768 | continue; |
769 | |
770 | uint64_t NewSize = InnerSize->getZExtValue(); |
771 | uint64_t NewOffset = InnerOffset->getZExtValue() - Offset; |
772 | if (InnerOffset->getZExtValue() < Offset) { |
773 | NewOffset = 0; |
774 | NewSize -= Offset - InnerOffset->getZExtValue(); |
775 | } |
776 | |
777 | // Shift the offset of the triple |
778 | Sub.push_back(Elt: ConstantAsMetadata::get( |
779 | C: ConstantInt::get(Ty: InnerOffset->getType(), V: NewOffset))); |
780 | Sub.push_back(Elt: ConstantAsMetadata::get( |
781 | C: ConstantInt::get(Ty: InnerSize->getType(), V: NewSize))); |
782 | Sub.push_back(Elt: MD->getOperand(I: i + 2)); |
783 | } |
784 | return MDNode::get(Context&: MD->getContext(), MDs: Sub); |
785 | } |
786 | |
787 | MDNode *AAMDNodes::extendToTBAA(MDNode *MD, ssize_t Len) { |
788 | // Fast path if 0-length |
789 | if (Len == 0) |
790 | return nullptr; |
791 | |
792 | // Regular TBAA is invariant of length, so we only need to consider |
793 | // struct-path TBAA. |
794 | if (!isStructPathTBAA(MD)) |
795 | return MD; |
796 | |
797 | TBAAStructTagNode Tag(MD); |
798 | |
799 | // Only new format TBAA has a size |
800 | if (!Tag.isNewFormat()) |
801 | return MD; |
802 | |
803 | // If unknown size, drop the TBAA. |
804 | if (Len == -1) |
805 | return nullptr; |
806 | |
807 | // Otherwise, create TBAA with the new Len |
808 | ArrayRef<MDOperand> MDOperands = MD->operands(); |
809 | SmallVector<Metadata *, 4> NextNodes(MDOperands.begin(), MDOperands.end()); |
810 | ConstantInt *PreviousSize = mdconst::extract<ConstantInt>(MD&: NextNodes[3]); |
811 | |
812 | // Don't create a new MDNode if it is the same length. |
813 | if (PreviousSize->equalsInt(V: Len)) |
814 | return MD; |
815 | |
816 | NextNodes[3] = |
817 | ConstantAsMetadata::get(C: ConstantInt::get(Ty: PreviousSize->getType(), V: Len)); |
818 | return MDNode::get(Context&: MD->getContext(), MDs: NextNodes); |
819 | } |
820 | |
821 | AAMDNodes AAMDNodes::adjustForAccess(unsigned AccessSize) { |
822 | AAMDNodes New = *this; |
823 | MDNode *M = New.TBAAStruct; |
824 | New.TBAAStruct = nullptr; |
825 | if (M && M->getNumOperands() == 3 && M->getOperand(I: 0) && |
826 | mdconst::hasa<ConstantInt>(MD: M->getOperand(I: 0)) && |
827 | mdconst::extract<ConstantInt>(MD: M->getOperand(I: 0))->isZero() && |
828 | M->getOperand(I: 1) && mdconst::hasa<ConstantInt>(MD: M->getOperand(I: 1)) && |
829 | mdconst::extract<ConstantInt>(MD: M->getOperand(I: 1))->getValue() == |
830 | AccessSize && |
831 | M->getOperand(I: 2) && isa<MDNode>(Val: M->getOperand(I: 2))) |
832 | New.TBAA = cast<MDNode>(Val: M->getOperand(I: 2)); |
833 | return New; |
834 | } |
835 | |