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 }
93
94 for (const auto &NMD : M.named_metadata())
95 for (const auto *MDOp : NMD.operands())
96 incorporateMDNode(V: MDOp);
97}
98
99void 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.
107void 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.
133void 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.
171void 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
191void 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

source code of llvm/lib/IR/TypeFinder.cpp