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
32using namespace llvm;
33
34void 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 // Incorporate types hiding in variable-location information.
93 for (const auto &Dbg : I.getDbgRecordRange()) {
94 // Pick out records that have Values.
95 if (const DbgVariableRecord *DVI =
96 dyn_cast<DbgVariableRecord>(Val: &Dbg)) {
97 for (Value *V : DVI->location_ops())
98 incorporateValue(V);
99 if (DVI->isDbgAssign()) {
100 if (Value *Addr = DVI->getAddress())
101 incorporateValue(V: Addr);
102 }
103 }
104 }
105 }
106 }
107
108 for (const auto &NMD : M.named_metadata())
109 for (const auto *MDOp : NMD.operands())
110 incorporateMDNode(V: MDOp);
111}
112
113void TypeFinder::clear() {
114 VisitedConstants.clear();
115 VisitedTypes.clear();
116 StructTypes.clear();
117}
118
119/// incorporateType - This method adds the type to the list of used structures
120/// if it's not in there already.
121void TypeFinder::incorporateType(Type *Ty) {
122 // Check to see if we've already visited this type.
123 if (!VisitedTypes.insert(V: Ty).second)
124 return;
125
126 SmallVector<Type *, 4> TypeWorklist;
127 TypeWorklist.push_back(Elt: Ty);
128 do {
129 Ty = TypeWorklist.pop_back_val();
130
131 // If this is a structure or opaque type, add a name for the type.
132 if (StructType *STy = dyn_cast<StructType>(Val: Ty))
133 if (!OnlyNamed || STy->hasName())
134 StructTypes.push_back(x: STy);
135
136 // Add all unvisited subtypes to worklist for processing
137 for (Type *SubTy : llvm::reverse(C: Ty->subtypes()))
138 if (VisitedTypes.insert(V: SubTy).second)
139 TypeWorklist.push_back(Elt: SubTy);
140 } while (!TypeWorklist.empty());
141}
142
143/// incorporateValue - This method is used to walk operand lists finding types
144/// hiding in constant expressions and other operands that won't be walked in
145/// other ways. GlobalValues, basic blocks, instructions, and inst operands are
146/// all explicitly enumerated.
147void TypeFinder::incorporateValue(const Value *V) {
148 if (const auto *M = dyn_cast<MetadataAsValue>(Val: V)) {
149 if (const auto *N = dyn_cast<MDNode>(Val: M->getMetadata()))
150 return incorporateMDNode(V: N);
151 if (const auto *MDV = dyn_cast<ValueAsMetadata>(Val: M->getMetadata()))
152 return incorporateValue(V: MDV->getValue());
153 if (const auto *AL = dyn_cast<DIArgList>(Val: M->getMetadata())) {
154 for (auto *Arg : AL->getArgs())
155 incorporateValue(V: Arg->getValue());
156 return;
157 }
158 return;
159 }
160
161 if (!isa<Constant>(Val: V) || isa<GlobalValue>(Val: V)) return;
162
163 // Already visited?
164 if (!VisitedConstants.insert(V).second)
165 return;
166
167 // Check this type.
168 incorporateType(Ty: V->getType());
169
170 // If this is an instruction, we incorporate it separately.
171 if (isa<Instruction>(Val: V))
172 return;
173
174 if (auto *GEP = dyn_cast<GEPOperator>(Val: V))
175 incorporateType(Ty: GEP->getSourceElementType());
176
177 // Look in operands for types.
178 const User *U = cast<User>(Val: V);
179 for (const auto &I : U->operands())
180 incorporateValue(V: &*I);
181}
182
183/// incorporateMDNode - This method is used to walk the operands of an MDNode to
184/// find types hiding within.
185void TypeFinder::incorporateMDNode(const MDNode *V) {
186 // Already visited?
187 if (!VisitedMetadata.insert(V).second)
188 return;
189
190 // Look in operands for types.
191 for (Metadata *Op : V->operands()) {
192 if (!Op)
193 continue;
194 if (auto *N = dyn_cast<MDNode>(Val: Op)) {
195 incorporateMDNode(V: N);
196 continue;
197 }
198 if (auto *C = dyn_cast<ConstantAsMetadata>(Val: Op)) {
199 incorporateValue(V: C->getValue());
200 continue;
201 }
202 }
203}
204
205void TypeFinder::incorporateAttributes(AttributeList AL) {
206 if (!VisitedAttributes.insert(V: AL).second)
207 return;
208
209 for (AttributeSet AS : AL)
210 for (Attribute A : AS)
211 if (A.isTypeAttribute())
212 incorporateType(Ty: A.getValueAsType());
213}
214