1 //===-- TypeFinder.cpp - Implement the TypeFinder class -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the TypeFinder class for the IR library.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/IR/TypeFinder.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/IR/BasicBlock.h"
17 #include "llvm/IR/DerivedTypes.h"
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/Metadata.h"
20 #include "llvm/IR/Module.h"
23 void TypeFinder::run(const Module &M, bool onlyNamed) {
24 OnlyNamed = onlyNamed;
26 // Get types from global variables.
27 for (Module::const_global_iterator I = M.global_begin(),
28 E = M.global_end(); I != E; ++I) {
29 incorporateType(I->getType());
30 if (I->hasInitializer())
31 incorporateValue(I->getInitializer());
34 // Get types from aliases.
35 for (Module::const_alias_iterator I = M.alias_begin(),
36 E = M.alias_end(); I != E; ++I) {
37 incorporateType(I->getType());
38 if (const Value *Aliasee = I->getAliasee())
39 incorporateValue(Aliasee);
42 // Get types from functions.
43 SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
44 for (const Function &FI : M) {
45 incorporateType(FI.getType());
47 for (const Use &U : FI.operands())
48 incorporateValue(U.get());
50 // First incorporate the arguments.
51 for (Function::const_arg_iterator AI = FI.arg_begin(), AE = FI.arg_end();
53 incorporateValue(&*AI);
55 for (const BasicBlock &BB : FI)
56 for (const Instruction &I : BB) {
57 // Incorporate the type of the instruction.
58 incorporateType(I.getType());
60 // Incorporate non-instruction operand types. (We are incorporating all
61 // instructions with this loop.)
62 for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
64 if (*OI && !isa<Instruction>(OI))
65 incorporateValue(*OI);
67 // Incorporate types hiding in metadata.
68 I.getAllMetadataOtherThanDebugLoc(MDForInst);
69 for (unsigned i = 0, e = MDForInst.size(); i != e; ++i)
70 incorporateMDNode(MDForInst[i].second);
76 for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
77 E = M.named_metadata_end(); I != E; ++I) {
78 const NamedMDNode *NMD = &*I;
79 for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
80 incorporateMDNode(NMD->getOperand(i));
84 void TypeFinder::clear() {
85 VisitedConstants.clear();
90 /// incorporateType - This method adds the type to the list of used structures
91 /// if it's not in there already.
92 void TypeFinder::incorporateType(Type *Ty) {
93 // Check to see if we've already visited this type.
94 if (!VisitedTypes.insert(Ty).second)
97 SmallVector<Type *, 4> TypeWorklist;
98 TypeWorklist.push_back(Ty);
100 Ty = TypeWorklist.pop_back_val();
102 // If this is a structure or opaque type, add a name for the type.
103 if (StructType *STy = dyn_cast<StructType>(Ty))
104 if (!OnlyNamed || STy->hasName())
105 StructTypes.push_back(STy);
107 // Add all unvisited subtypes to worklist for processing
108 for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
109 E = Ty->subtype_rend();
111 if (VisitedTypes.insert(*I).second)
112 TypeWorklist.push_back(*I);
113 } while (!TypeWorklist.empty());
116 /// incorporateValue - This method is used to walk operand lists finding types
117 /// hiding in constant expressions and other operands that won't be walked in
118 /// other ways. GlobalValues, basic blocks, instructions, and inst operands are
119 /// all explicitly enumerated.
120 void TypeFinder::incorporateValue(const Value *V) {
121 if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
122 if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
123 return incorporateMDNode(N);
124 if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
125 return incorporateValue(MDV->getValue());
129 if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
132 if (!VisitedConstants.insert(V).second)
136 incorporateType(V->getType());
138 // If this is an instruction, we incorporate it separately.
139 if (isa<Instruction>(V))
142 // Look in operands for types.
143 const User *U = cast<User>(V);
144 for (Constant::const_op_iterator I = U->op_begin(),
145 E = U->op_end(); I != E;++I)
146 incorporateValue(*I);
149 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
150 /// find types hiding within.
151 void TypeFinder::incorporateMDNode(const MDNode *V) {
153 if (!VisitedMetadata.insert(V).second)
156 // Look in operands for types.
157 for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) {
158 Metadata *Op = V->getOperand(i);
161 if (auto *N = dyn_cast<MDNode>(Op)) {
162 incorporateMDNode(N);
165 if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
166 incorporateValue(C->getValue());