]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | // | |
1a4d82fc JJ |
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 | |
223e47cc LB |
25 | // three fields, e.g.: |
26 | // !0 = metadata !{ metadata !"an example type tree" } | |
27 | // !1 = metadata !{ metadata !"int", metadata !0 } | |
28 | // !2 = metadata !{ metadata !"float", metadata !0 } | |
29 | // !3 = metadata !{ metadata !"const float", metadata !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 | // | |
1a4d82fc JJ |
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 sclar 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 acess 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 = metadata !{metadata !"Simple C/C++ TBAA"} | |
78 | // !1 = metadata !{metadata !"omnipotent char", metadata !0} // Scalar type node | |
79 | // !2 = metadata !{metadata !"short", metadata !1} // Scalar type node | |
80 | // !3 = metadata !{metadata !"A", metadata !2, i64 0} // Struct type node | |
81 | // !4 = metadata !{metadata !"B", metadata !2, i64 0, metadata !3, i64 4} | |
82 | // // Struct type node | |
83 | // !5 = metadata !{metadata !4, metadata !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 | // | |
223e47cc LB |
107 | // TODO: The current metadata format doesn't support struct |
108 | // fields. For example: | |
109 | // struct X { | |
110 | // double d; | |
111 | // int i; | |
112 | // }; | |
113 | // void foo(struct X *x, struct X *y, double *p) { | |
114 | // *x = *y; | |
115 | // *p = 0.0; | |
116 | // } | |
117 | // Struct X has a double member, so the store to *x can alias the store to *p. | |
118 | // Currently it's not possible to precisely describe all the things struct X | |
119 | // aliases, so struct assignments must use conservative TBAA nodes. There's | |
120 | // no scheme for attaching metadata to @llvm.memcpy yet either. | |
121 | // | |
122 | //===----------------------------------------------------------------------===// | |
123 | ||
223e47cc | 124 | #include "llvm/Analysis/Passes.h" |
970d7e83 LB |
125 | #include "llvm/Analysis/AliasAnalysis.h" |
126 | #include "llvm/IR/Constants.h" | |
127 | #include "llvm/IR/LLVMContext.h" | |
128 | #include "llvm/IR/Metadata.h" | |
129 | #include "llvm/IR/Module.h" | |
223e47cc LB |
130 | #include "llvm/Pass.h" |
131 | #include "llvm/Support/CommandLine.h" | |
132 | using namespace llvm; | |
133 | ||
134 | // A handy option for disabling TBAA functionality. The same effect can also be | |
135 | // achieved by stripping the !tbaa tags from IR, but this option is sometimes | |
136 | // more convenient. | |
137 | static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true)); | |
138 | ||
139 | namespace { | |
140 | /// TBAANode - This is a simple wrapper around an MDNode which provides a | |
141 | /// higher-level interface by hiding the details of how alias analysis | |
142 | /// information is encoded in its operands. | |
143 | class TBAANode { | |
144 | const MDNode *Node; | |
145 | ||
146 | public: | |
1a4d82fc | 147 | TBAANode() : Node(nullptr) {} |
223e47cc LB |
148 | explicit TBAANode(const MDNode *N) : Node(N) {} |
149 | ||
150 | /// getNode - Get the MDNode for this TBAANode. | |
151 | const MDNode *getNode() const { return Node; } | |
152 | ||
153 | /// getParent - Get this TBAANode's Alias tree parent. | |
154 | TBAANode getParent() const { | |
155 | if (Node->getNumOperands() < 2) | |
156 | return TBAANode(); | |
157 | MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); | |
158 | if (!P) | |
159 | return TBAANode(); | |
160 | // Ok, this node has a valid parent. Return it. | |
161 | return TBAANode(P); | |
162 | } | |
163 | ||
164 | /// TypeIsImmutable - Test if this TBAANode represents a type for objects | |
165 | /// which are not modified (by any means) in the context where this | |
166 | /// AliasAnalysis is relevant. | |
167 | bool TypeIsImmutable() const { | |
168 | if (Node->getNumOperands() < 3) | |
169 | return false; | |
85aaf69f | 170 | ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2)); |
223e47cc LB |
171 | if (!CI) |
172 | return false; | |
173 | return CI->getValue()[0]; | |
174 | } | |
175 | }; | |
1a4d82fc JJ |
176 | |
177 | /// This is a simple wrapper around an MDNode which provides a | |
178 | /// higher-level interface by hiding the details of how alias analysis | |
179 | /// information is encoded in its operands. | |
180 | class TBAAStructTagNode { | |
181 | /// This node should be created with createTBAAStructTagNode. | |
182 | const MDNode *Node; | |
183 | ||
184 | public: | |
185 | explicit TBAAStructTagNode(const MDNode *N) : Node(N) {} | |
186 | ||
187 | /// Get the MDNode for this TBAAStructTagNode. | |
188 | const MDNode *getNode() const { return Node; } | |
189 | ||
190 | const MDNode *getBaseType() const { | |
191 | return dyn_cast_or_null<MDNode>(Node->getOperand(0)); | |
192 | } | |
193 | const MDNode *getAccessType() const { | |
194 | return dyn_cast_or_null<MDNode>(Node->getOperand(1)); | |
195 | } | |
196 | uint64_t getOffset() const { | |
85aaf69f | 197 | return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue(); |
1a4d82fc JJ |
198 | } |
199 | /// TypeIsImmutable - Test if this TBAAStructTagNode represents a type for | |
200 | /// objects which are not modified (by any means) in the context where this | |
201 | /// AliasAnalysis is relevant. | |
202 | bool TypeIsImmutable() const { | |
203 | if (Node->getNumOperands() < 4) | |
204 | return false; | |
85aaf69f | 205 | ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(3)); |
1a4d82fc JJ |
206 | if (!CI) |
207 | return false; | |
208 | return CI->getValue()[0]; | |
209 | } | |
210 | }; | |
211 | ||
212 | /// This is a simple wrapper around an MDNode which provides a | |
213 | /// higher-level interface by hiding the details of how alias analysis | |
214 | /// information is encoded in its operands. | |
215 | class TBAAStructTypeNode { | |
216 | /// This node should be created with createTBAAStructTypeNode. | |
217 | const MDNode *Node; | |
218 | ||
219 | public: | |
220 | TBAAStructTypeNode() : Node(nullptr) {} | |
221 | explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} | |
222 | ||
223 | /// Get the MDNode for this TBAAStructTypeNode. | |
224 | const MDNode *getNode() const { return Node; } | |
225 | ||
226 | /// Get this TBAAStructTypeNode's field in the type DAG with | |
227 | /// given offset. Update the offset to be relative to the field type. | |
228 | TBAAStructTypeNode getParent(uint64_t &Offset) const { | |
229 | // Parent can be omitted for the root node. | |
230 | if (Node->getNumOperands() < 2) | |
231 | return TBAAStructTypeNode(); | |
232 | ||
233 | // Fast path for a scalar type node and a struct type node with a single | |
234 | // field. | |
235 | if (Node->getNumOperands() <= 3) { | |
85aaf69f SL |
236 | uint64_t Cur = Node->getNumOperands() == 2 |
237 | ? 0 | |
238 | : mdconst::extract<ConstantInt>(Node->getOperand(2)) | |
239 | ->getZExtValue(); | |
1a4d82fc JJ |
240 | Offset -= Cur; |
241 | MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); | |
242 | if (!P) | |
243 | return TBAAStructTypeNode(); | |
244 | return TBAAStructTypeNode(P); | |
245 | } | |
246 | ||
247 | // Assume the offsets are in order. We return the previous field if | |
248 | // the current offset is bigger than the given offset. | |
249 | unsigned TheIdx = 0; | |
250 | for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) { | |
85aaf69f SL |
251 | uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1)) |
252 | ->getZExtValue(); | |
1a4d82fc JJ |
253 | if (Cur > Offset) { |
254 | assert(Idx >= 3 && | |
255 | "TBAAStructTypeNode::getParent should have an offset match!"); | |
256 | TheIdx = Idx - 2; | |
257 | break; | |
258 | } | |
259 | } | |
260 | // Move along the last field. | |
261 | if (TheIdx == 0) | |
262 | TheIdx = Node->getNumOperands() - 2; | |
85aaf69f SL |
263 | uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1)) |
264 | ->getZExtValue(); | |
1a4d82fc JJ |
265 | Offset -= Cur; |
266 | MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx)); | |
267 | if (!P) | |
268 | return TBAAStructTypeNode(); | |
269 | return TBAAStructTypeNode(P); | |
270 | } | |
271 | }; | |
223e47cc LB |
272 | } |
273 | ||
274 | namespace { | |
275 | /// TypeBasedAliasAnalysis - This is a simple alias analysis | |
276 | /// implementation that uses TypeBased to answer queries. | |
277 | class TypeBasedAliasAnalysis : public ImmutablePass, | |
278 | public AliasAnalysis { | |
279 | public: | |
280 | static char ID; // Class identification, replacement for typeinfo | |
281 | TypeBasedAliasAnalysis() : ImmutablePass(ID) { | |
282 | initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); | |
283 | } | |
284 | ||
1a4d82fc | 285 | void initializePass() override { |
223e47cc LB |
286 | InitializeAliasAnalysis(this); |
287 | } | |
288 | ||
289 | /// getAdjustedAnalysisPointer - This method is used when a pass implements | |
290 | /// an analysis interface through multiple inheritance. If needed, it | |
291 | /// should override this to adjust the this pointer as needed for the | |
292 | /// specified pass info. | |
1a4d82fc | 293 | void *getAdjustedAnalysisPointer(const void *PI) override { |
223e47cc LB |
294 | if (PI == &AliasAnalysis::ID) |
295 | return (AliasAnalysis*)this; | |
296 | return this; | |
297 | } | |
298 | ||
299 | bool Aliases(const MDNode *A, const MDNode *B) const; | |
1a4d82fc | 300 | bool PathAliases(const MDNode *A, const MDNode *B) const; |
223e47cc LB |
301 | |
302 | private: | |
1a4d82fc JJ |
303 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
304 | AliasResult alias(const Location &LocA, const Location &LocB) override; | |
305 | bool pointsToConstantMemory(const Location &Loc, bool OrLocal) override; | |
306 | ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override; | |
307 | ModRefBehavior getModRefBehavior(const Function *F) override; | |
308 | ModRefResult getModRefInfo(ImmutableCallSite CS, | |
309 | const Location &Loc) override; | |
310 | ModRefResult getModRefInfo(ImmutableCallSite CS1, | |
311 | ImmutableCallSite CS2) override; | |
223e47cc LB |
312 | }; |
313 | } // End of anonymous namespace | |
314 | ||
315 | // Register this pass... | |
316 | char TypeBasedAliasAnalysis::ID = 0; | |
317 | INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", | |
318 | "Type-Based Alias Analysis", false, true, false) | |
319 | ||
320 | ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { | |
321 | return new TypeBasedAliasAnalysis(); | |
322 | } | |
323 | ||
324 | void | |
325 | TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { | |
326 | AU.setPreservesAll(); | |
327 | AliasAnalysis::getAnalysisUsage(AU); | |
328 | } | |
329 | ||
1a4d82fc JJ |
330 | /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat |
331 | /// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA | |
332 | /// format. | |
333 | static bool isStructPathTBAA(const MDNode *MD) { | |
334 | // Anonymous TBAA root starts with a MDNode and dragonegg uses it as | |
335 | // a TBAA tag. | |
336 | return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3; | |
337 | } | |
338 | ||
223e47cc LB |
339 | /// Aliases - Test whether the type represented by A may alias the |
340 | /// type represented by B. | |
341 | bool | |
342 | TypeBasedAliasAnalysis::Aliases(const MDNode *A, | |
343 | const MDNode *B) const { | |
1a4d82fc JJ |
344 | // Make sure that both MDNodes are struct-path aware. |
345 | if (isStructPathTBAA(A) && isStructPathTBAA(B)) | |
346 | return PathAliases(A, B); | |
347 | ||
223e47cc LB |
348 | // Keep track of the root node for A and B. |
349 | TBAANode RootA, RootB; | |
350 | ||
351 | // Climb the tree from A to see if we reach B. | |
352 | for (TBAANode T(A); ; ) { | |
353 | if (T.getNode() == B) | |
354 | // B is an ancestor of A. | |
355 | return true; | |
356 | ||
357 | RootA = T; | |
358 | T = T.getParent(); | |
359 | if (!T.getNode()) | |
360 | break; | |
361 | } | |
362 | ||
363 | // Climb the tree from B to see if we reach A. | |
364 | for (TBAANode T(B); ; ) { | |
365 | if (T.getNode() == A) | |
366 | // A is an ancestor of B. | |
367 | return true; | |
368 | ||
369 | RootB = T; | |
370 | T = T.getParent(); | |
371 | if (!T.getNode()) | |
372 | break; | |
373 | } | |
374 | ||
375 | // Neither node is an ancestor of the other. | |
376 | ||
377 | // If they have different roots, they're part of different potentially | |
378 | // unrelated type systems, so we must be conservative. | |
379 | if (RootA.getNode() != RootB.getNode()) | |
380 | return true; | |
381 | ||
382 | // If they have the same root, then we've proved there's no alias. | |
383 | return false; | |
384 | } | |
385 | ||
1a4d82fc JJ |
386 | /// Test whether the struct-path tag represented by A may alias the |
387 | /// struct-path tag represented by B. | |
388 | bool | |
389 | TypeBasedAliasAnalysis::PathAliases(const MDNode *A, | |
390 | const MDNode *B) const { | |
391 | // Verify that both input nodes are struct-path aware. | |
392 | assert(isStructPathTBAA(A) && "MDNode A is not struct-path aware."); | |
393 | assert(isStructPathTBAA(B) && "MDNode B is not struct-path aware."); | |
394 | ||
395 | // Keep track of the root node for A and B. | |
396 | TBAAStructTypeNode RootA, RootB; | |
397 | TBAAStructTagNode TagA(A), TagB(B); | |
398 | ||
399 | // TODO: We need to check if AccessType of TagA encloses AccessType of | |
400 | // TagB to support aggregate AccessType. If yes, return true. | |
401 | ||
402 | // Start from the base type of A, follow the edge with the correct offset in | |
403 | // the type DAG and adjust the offset until we reach the base type of B or | |
404 | // until we reach the Root node. | |
405 | // Compare the adjusted offset once we have the same base. | |
406 | ||
407 | // Climb the type DAG from base type of A to see if we reach base type of B. | |
408 | const MDNode *BaseA = TagA.getBaseType(); | |
409 | const MDNode *BaseB = TagB.getBaseType(); | |
410 | uint64_t OffsetA = TagA.getOffset(), OffsetB = TagB.getOffset(); | |
411 | for (TBAAStructTypeNode T(BaseA); ; ) { | |
412 | if (T.getNode() == BaseB) | |
413 | // Base type of A encloses base type of B, check if the offsets match. | |
414 | return OffsetA == OffsetB; | |
415 | ||
416 | RootA = T; | |
417 | // Follow the edge with the correct offset, OffsetA will be adjusted to | |
418 | // be relative to the field type. | |
419 | T = T.getParent(OffsetA); | |
420 | if (!T.getNode()) | |
421 | break; | |
422 | } | |
423 | ||
424 | // Reset OffsetA and climb the type DAG from base type of B to see if we reach | |
425 | // base type of A. | |
426 | OffsetA = TagA.getOffset(); | |
427 | for (TBAAStructTypeNode T(BaseB); ; ) { | |
428 | if (T.getNode() == BaseA) | |
429 | // Base type of B encloses base type of A, check if the offsets match. | |
430 | return OffsetA == OffsetB; | |
431 | ||
432 | RootB = T; | |
433 | // Follow the edge with the correct offset, OffsetB will be adjusted to | |
434 | // be relative to the field type. | |
435 | T = T.getParent(OffsetB); | |
436 | if (!T.getNode()) | |
437 | break; | |
438 | } | |
439 | ||
440 | // Neither node is an ancestor of the other. | |
441 | ||
442 | // If they have different roots, they're part of different potentially | |
443 | // unrelated type systems, so we must be conservative. | |
444 | if (RootA.getNode() != RootB.getNode()) | |
445 | return true; | |
446 | ||
447 | // If they have the same root, then we've proved there's no alias. | |
448 | return false; | |
449 | } | |
450 | ||
223e47cc LB |
451 | AliasAnalysis::AliasResult |
452 | TypeBasedAliasAnalysis::alias(const Location &LocA, | |
453 | const Location &LocB) { | |
454 | if (!EnableTBAA) | |
455 | return AliasAnalysis::alias(LocA, LocB); | |
456 | ||
457 | // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must | |
458 | // be conservative. | |
1a4d82fc | 459 | const MDNode *AM = LocA.AATags.TBAA; |
223e47cc | 460 | if (!AM) return AliasAnalysis::alias(LocA, LocB); |
1a4d82fc | 461 | const MDNode *BM = LocB.AATags.TBAA; |
223e47cc LB |
462 | if (!BM) return AliasAnalysis::alias(LocA, LocB); |
463 | ||
464 | // If they may alias, chain to the next AliasAnalysis. | |
465 | if (Aliases(AM, BM)) | |
466 | return AliasAnalysis::alias(LocA, LocB); | |
467 | ||
468 | // Otherwise return a definitive result. | |
469 | return NoAlias; | |
470 | } | |
471 | ||
472 | bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, | |
473 | bool OrLocal) { | |
474 | if (!EnableTBAA) | |
475 | return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); | |
476 | ||
1a4d82fc | 477 | const MDNode *M = Loc.AATags.TBAA; |
223e47cc LB |
478 | if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); |
479 | ||
480 | // If this is an "immutable" type, we can assume the pointer is pointing | |
481 | // to constant memory. | |
1a4d82fc JJ |
482 | if ((!isStructPathTBAA(M) && TBAANode(M).TypeIsImmutable()) || |
483 | (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) | |
223e47cc LB |
484 | return true; |
485 | ||
486 | return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); | |
487 | } | |
488 | ||
489 | AliasAnalysis::ModRefBehavior | |
490 | TypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { | |
491 | if (!EnableTBAA) | |
492 | return AliasAnalysis::getModRefBehavior(CS); | |
493 | ||
494 | ModRefBehavior Min = UnknownModRefBehavior; | |
495 | ||
496 | // If this is an "immutable" type, we can assume the call doesn't write | |
497 | // to memory. | |
498 | if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) | |
1a4d82fc JJ |
499 | if ((!isStructPathTBAA(M) && TBAANode(M).TypeIsImmutable()) || |
500 | (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) | |
223e47cc LB |
501 | Min = OnlyReadsMemory; |
502 | ||
503 | return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); | |
504 | } | |
505 | ||
506 | AliasAnalysis::ModRefBehavior | |
507 | TypeBasedAliasAnalysis::getModRefBehavior(const Function *F) { | |
508 | // Functions don't have metadata. Just chain to the next implementation. | |
509 | return AliasAnalysis::getModRefBehavior(F); | |
510 | } | |
511 | ||
512 | AliasAnalysis::ModRefResult | |
513 | TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS, | |
514 | const Location &Loc) { | |
515 | if (!EnableTBAA) | |
516 | return AliasAnalysis::getModRefInfo(CS, Loc); | |
517 | ||
1a4d82fc | 518 | if (const MDNode *L = Loc.AATags.TBAA) |
223e47cc | 519 | if (const MDNode *M = |
85aaf69f | 520 | CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) |
223e47cc LB |
521 | if (!Aliases(L, M)) |
522 | return NoModRef; | |
523 | ||
524 | return AliasAnalysis::getModRefInfo(CS, Loc); | |
525 | } | |
526 | ||
527 | AliasAnalysis::ModRefResult | |
528 | TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, | |
529 | ImmutableCallSite CS2) { | |
530 | if (!EnableTBAA) | |
531 | return AliasAnalysis::getModRefInfo(CS1, CS2); | |
532 | ||
533 | if (const MDNode *M1 = | |
85aaf69f | 534 | CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) |
223e47cc | 535 | if (const MDNode *M2 = |
85aaf69f | 536 | CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) |
223e47cc LB |
537 | if (!Aliases(M1, M2)) |
538 | return NoModRef; | |
539 | ||
540 | return AliasAnalysis::getModRefInfo(CS1, CS2); | |
541 | } | |
1a4d82fc JJ |
542 | |
543 | bool MDNode::isTBAAVtableAccess() const { | |
544 | if (!isStructPathTBAA(this)) { | |
545 | if (getNumOperands() < 1) return false; | |
546 | if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) { | |
547 | if (Tag1->getString() == "vtable pointer") return true; | |
548 | } | |
549 | return false; | |
550 | } | |
551 | ||
552 | // For struct-path aware TBAA, we use the access type of the tag. | |
553 | if (getNumOperands() < 2) return false; | |
554 | MDNode *Tag = cast_or_null<MDNode>(getOperand(1)); | |
555 | if (!Tag) return false; | |
556 | if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) { | |
557 | if (Tag1->getString() == "vtable pointer") return true; | |
558 | } | |
559 | return false; | |
560 | } | |
561 | ||
562 | MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { | |
563 | if (!A || !B) | |
564 | return nullptr; | |
565 | ||
566 | if (A == B) | |
567 | return A; | |
568 | ||
569 | // For struct-path aware TBAA, we use the access type of the tag. | |
570 | bool StructPath = isStructPathTBAA(A) && isStructPathTBAA(B); | |
571 | if (StructPath) { | |
572 | A = cast_or_null<MDNode>(A->getOperand(1)); | |
573 | if (!A) return nullptr; | |
574 | B = cast_or_null<MDNode>(B->getOperand(1)); | |
575 | if (!B) return nullptr; | |
576 | } | |
577 | ||
578 | SmallVector<MDNode *, 4> PathA; | |
579 | MDNode *T = A; | |
580 | while (T) { | |
581 | PathA.push_back(T); | |
582 | T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) | |
583 | : nullptr; | |
584 | } | |
585 | ||
586 | SmallVector<MDNode *, 4> PathB; | |
587 | T = B; | |
588 | while (T) { | |
589 | PathB.push_back(T); | |
590 | T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) | |
591 | : nullptr; | |
592 | } | |
593 | ||
594 | int IA = PathA.size() - 1; | |
595 | int IB = PathB.size() - 1; | |
596 | ||
597 | MDNode *Ret = nullptr; | |
598 | while (IA >= 0 && IB >=0) { | |
599 | if (PathA[IA] == PathB[IB]) | |
600 | Ret = PathA[IA]; | |
601 | else | |
602 | break; | |
603 | --IA; | |
604 | --IB; | |
605 | } | |
606 | if (!StructPath) | |
607 | return Ret; | |
608 | ||
609 | if (!Ret) | |
610 | return nullptr; | |
611 | // We need to convert from a type node to a tag node. | |
612 | Type *Int64 = IntegerType::get(A->getContext(), 64); | |
85aaf69f SL |
613 | Metadata *Ops[3] = {Ret, Ret, |
614 | ConstantAsMetadata::get(ConstantInt::get(Int64, 0))}; | |
1a4d82fc JJ |
615 | return MDNode::get(A->getContext(), Ops); |
616 | } | |
617 | ||
618 | void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const { | |
619 | if (Merge) | |
85aaf69f SL |
620 | N.TBAA = |
621 | MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa)); | |
1a4d82fc JJ |
622 | else |
623 | N.TBAA = getMetadata(LLVMContext::MD_tbaa); | |
624 | ||
625 | if (Merge) | |
85aaf69f SL |
626 | N.Scope = MDNode::getMostGenericAliasScope( |
627 | N.Scope, getMetadata(LLVMContext::MD_alias_scope)); | |
1a4d82fc JJ |
628 | else |
629 | N.Scope = getMetadata(LLVMContext::MD_alias_scope); | |
630 | ||
631 | if (Merge) | |
85aaf69f SL |
632 | N.NoAlias = |
633 | MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias)); | |
1a4d82fc JJ |
634 | else |
635 | N.NoAlias = getMetadata(LLVMContext::MD_noalias); | |
636 | } | |
637 |