1 | //===- TypeFinder.cpp - Implement the TypeFinder class --------------------===// |
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 implements the TypeFinder class for the IR library. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "llvm/IR/TypeFinder.h" |
14 | #include "llvm/ADT/SmallVector.h" |
15 | #include "llvm/IR/BasicBlock.h" |
16 | #include "llvm/IR/Constant.h" |
17 | #include "llvm/IR/DebugInfoMetadata.h" |
18 | #include "llvm/IR/DerivedTypes.h" |
19 | #include "llvm/IR/Function.h" |
20 | #include "llvm/IR/Instruction.h" |
21 | #include "llvm/IR/Instructions.h" |
22 | #include "llvm/IR/Metadata.h" |
23 | #include "llvm/IR/Module.h" |
24 | #include "llvm/IR/Operator.h" |
25 | #include "llvm/IR/Type.h" |
26 | #include "llvm/IR/Use.h" |
27 | #include "llvm/IR/User.h" |
28 | #include "llvm/IR/Value.h" |
29 | #include "llvm/Support/Casting.h" |
30 | #include <utility> |
31 | |
32 | using namespace llvm; |
33 | |
34 | void TypeFinder::run(const Module &M, bool onlyNamed) { |
35 | OnlyNamed = onlyNamed; |
36 | |
37 | // Get types from global variables. |
38 | for (const auto &G : M.globals()) { |
39 | incorporateType(Ty: G.getValueType()); |
40 | if (G.hasInitializer()) |
41 | incorporateValue(V: G.getInitializer()); |
42 | } |
43 | |
44 | // Get types from aliases. |
45 | for (const auto &A : M.aliases()) { |
46 | incorporateType(Ty: A.getValueType()); |
47 | if (const Value *Aliasee = A.getAliasee()) |
48 | incorporateValue(V: Aliasee); |
49 | } |
50 | |
51 | // Get types from ifuncs. |
52 | for (const auto &GI : M.ifuncs()) |
53 | incorporateType(Ty: GI.getValueType()); |
54 | |
55 | // Get types from functions. |
56 | SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst; |
57 | for (const Function &FI : M) { |
58 | incorporateType(Ty: FI.getFunctionType()); |
59 | incorporateAttributes(AL: FI.getAttributes()); |
60 | |
61 | for (const Use &U : FI.operands()) |
62 | incorporateValue(V: U.get()); |
63 | |
64 | // First incorporate the arguments. |
65 | for (const auto &A : FI.args()) |
66 | incorporateValue(V: &A); |
67 | |
68 | for (const BasicBlock &BB : FI) |
69 | for (const Instruction &I : BB) { |
70 | // Incorporate the type of the instruction. |
71 | incorporateType(Ty: I.getType()); |
72 | |
73 | // Incorporate non-instruction operand types. (We are incorporating all |
74 | // instructions with this loop.) |
75 | for (const auto &O : I.operands()) |
76 | if (&*O && !isa<Instruction>(Val: &*O)) |
77 | incorporateValue(V: &*O); |
78 | |
79 | if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: &I)) |
80 | incorporateType(Ty: GEP->getSourceElementType()); |
81 | if (auto *AI = dyn_cast<AllocaInst>(Val: &I)) |
82 | incorporateType(Ty: AI->getAllocatedType()); |
83 | if (const auto *CB = dyn_cast<CallBase>(Val: &I)) |
84 | incorporateAttributes(AL: CB->getAttributes()); |
85 | |
86 | // Incorporate types hiding in metadata. |
87 | I.getAllMetadataOtherThanDebugLoc(MDs&: MDForInst); |
88 | for (const auto &MD : MDForInst) |
89 | incorporateMDNode(V: MD.second); |
90 | MDForInst.clear(); |
91 | } |
92 | } |
93 | |
94 | for (const auto &NMD : M.named_metadata()) |
95 | for (const auto *MDOp : NMD.operands()) |
96 | incorporateMDNode(V: MDOp); |
97 | } |
98 | |
99 | void TypeFinder::clear() { |
100 | VisitedConstants.clear(); |
101 | VisitedTypes.clear(); |
102 | StructTypes.clear(); |
103 | } |
104 | |
105 | /// incorporateType - This method adds the type to the list of used structures |
106 | /// if it's not in there already. |
107 | void TypeFinder::incorporateType(Type *Ty) { |
108 | // Check to see if we've already visited this type. |
109 | if (!VisitedTypes.insert(V: Ty).second) |
110 | return; |
111 | |
112 | SmallVector<Type *, 4> TypeWorklist; |
113 | TypeWorklist.push_back(Elt: Ty); |
114 | do { |
115 | Ty = TypeWorklist.pop_back_val(); |
116 | |
117 | // If this is a structure or opaque type, add a name for the type. |
118 | if (StructType *STy = dyn_cast<StructType>(Val: Ty)) |
119 | if (!OnlyNamed || STy->hasName()) |
120 | StructTypes.push_back(x: STy); |
121 | |
122 | // Add all unvisited subtypes to worklist for processing |
123 | for (Type *SubTy : llvm::reverse(C: Ty->subtypes())) |
124 | if (VisitedTypes.insert(V: SubTy).second) |
125 | TypeWorklist.push_back(Elt: SubTy); |
126 | } while (!TypeWorklist.empty()); |
127 | } |
128 | |
129 | /// incorporateValue - This method is used to walk operand lists finding types |
130 | /// hiding in constant expressions and other operands that won't be walked in |
131 | /// other ways. GlobalValues, basic blocks, instructions, and inst operands are |
132 | /// all explicitly enumerated. |
133 | void TypeFinder::incorporateValue(const Value *V) { |
134 | if (const auto *M = dyn_cast<MetadataAsValue>(Val: V)) { |
135 | if (const auto *N = dyn_cast<MDNode>(Val: M->getMetadata())) |
136 | return incorporateMDNode(V: N); |
137 | if (const auto *MDV = dyn_cast<ValueAsMetadata>(Val: M->getMetadata())) |
138 | return incorporateValue(V: MDV->getValue()); |
139 | if (const auto *AL = dyn_cast<DIArgList>(Val: M->getMetadata())) { |
140 | for (auto *Arg : AL->getArgs()) |
141 | incorporateValue(V: Arg->getValue()); |
142 | return; |
143 | } |
144 | return; |
145 | } |
146 | |
147 | if (!isa<Constant>(Val: V) || isa<GlobalValue>(Val: V)) return; |
148 | |
149 | // Already visited? |
150 | if (!VisitedConstants.insert(V).second) |
151 | return; |
152 | |
153 | // Check this type. |
154 | incorporateType(Ty: V->getType()); |
155 | |
156 | // If this is an instruction, we incorporate it separately. |
157 | if (isa<Instruction>(Val: V)) |
158 | return; |
159 | |
160 | if (auto *GEP = dyn_cast<GEPOperator>(Val: V)) |
161 | incorporateType(Ty: GEP->getSourceElementType()); |
162 | |
163 | // Look in operands for types. |
164 | const User *U = cast<User>(Val: V); |
165 | for (const auto &I : U->operands()) |
166 | incorporateValue(V: &*I); |
167 | } |
168 | |
169 | /// incorporateMDNode - This method is used to walk the operands of an MDNode to |
170 | /// find types hiding within. |
171 | void TypeFinder::incorporateMDNode(const MDNode *V) { |
172 | // Already visited? |
173 | if (!VisitedMetadata.insert(V).second) |
174 | return; |
175 | |
176 | // Look in operands for types. |
177 | for (Metadata *Op : V->operands()) { |
178 | if (!Op) |
179 | continue; |
180 | if (auto *N = dyn_cast<MDNode>(Val: Op)) { |
181 | incorporateMDNode(V: N); |
182 | continue; |
183 | } |
184 | if (auto *C = dyn_cast<ConstantAsMetadata>(Val: Op)) { |
185 | incorporateValue(V: C->getValue()); |
186 | continue; |
187 | } |
188 | } |
189 | } |
190 | |
191 | void TypeFinder::incorporateAttributes(AttributeList AL) { |
192 | if (!VisitedAttributes.insert(V: AL).second) |
193 | return; |
194 | |
195 | for (AttributeSet AS : AL) |
196 | for (Attribute A : AS) |
197 | if (A.isTypeAttribute()) |
198 | incorporateType(Ty: A.getValueAsType()); |
199 | } |
200 | |