1 //===-- TypeFinder.cpp - Implement the TypeFinder class -------------------===//
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 implements the TypeFinder class for the IR library.
11 //
12 //===----------------------------------------------------------------------===//
13
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"
21 using namespace llvm;
22
run(const Module & M,bool onlyNamed)23 void TypeFinder::run(const Module &M, bool onlyNamed) {
24 OnlyNamed = onlyNamed;
25
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());
32 }
33
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);
40 }
41
42 // Get types from functions.
43 SmallVector<std::pair<unsigned, MDNode*>, 4> MDForInst;
44 for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) {
45 incorporateType(FI->getType());
46
47 // First incorporate the arguments.
48 for (Function::const_arg_iterator AI = FI->arg_begin(),
49 AE = FI->arg_end(); AI != AE; ++AI)
50 incorporateValue(AI);
51
52 for (Function::const_iterator BB = FI->begin(), E = FI->end();
53 BB != E;++BB)
54 for (BasicBlock::const_iterator II = BB->begin(),
55 E = BB->end(); II != E; ++II) {
56 const Instruction &I = *II;
57
58 // Incorporate the type of the instruction.
59 incorporateType(I.getType());
60
61 // Incorporate non-instruction operand types. (We are incorporating all
62 // instructions with this loop.)
63 for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
64 OI != OE; ++OI)
65 if (!isa<Instruction>(OI))
66 incorporateValue(*OI);
67
68 // Incorporate types hiding in metadata.
69 I.getAllMetadataOtherThanDebugLoc(MDForInst);
70 for (unsigned i = 0, e = MDForInst.size(); i != e; ++i)
71 incorporateMDNode(MDForInst[i].second);
72
73 MDForInst.clear();
74 }
75 }
76
77 for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
78 E = M.named_metadata_end(); I != E; ++I) {
79 const NamedMDNode *NMD = I;
80 for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
81 incorporateMDNode(NMD->getOperand(i));
82 }
83 }
84
clear()85 void TypeFinder::clear() {
86 VisitedConstants.clear();
87 VisitedTypes.clear();
88 StructTypes.clear();
89 }
90
91 /// incorporateType - This method adds the type to the list of used structures
92 /// if it's not in there already.
incorporateType(Type * Ty)93 void TypeFinder::incorporateType(Type *Ty) {
94 // Check to see if we're already visited this type.
95 if (!VisitedTypes.insert(Ty).second)
96 return;
97
98 // If this is a structure or opaque type, add a name for the type.
99 if (StructType *STy = dyn_cast<StructType>(Ty))
100 if (!OnlyNamed || STy->hasName())
101 StructTypes.push_back(STy);
102
103 // Recursively walk all contained types.
104 for (Type::subtype_iterator I = Ty->subtype_begin(),
105 E = Ty->subtype_end(); I != E; ++I)
106 incorporateType(*I);
107 }
108
109 /// incorporateValue - This method is used to walk operand lists finding types
110 /// hiding in constant expressions and other operands that won't be walked in
111 /// other ways. GlobalValues, basic blocks, instructions, and inst operands are
112 /// all explicitly enumerated.
incorporateValue(const Value * V)113 void TypeFinder::incorporateValue(const Value *V) {
114 if (const MDNode *M = dyn_cast<MDNode>(V))
115 return incorporateMDNode(M);
116
117 if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
118
119 // Already visited?
120 if (!VisitedConstants.insert(V).second)
121 return;
122
123 // Check this type.
124 incorporateType(V->getType());
125
126 // If this is an instruction, we incorporate it separately.
127 if (isa<Instruction>(V))
128 return;
129
130 // Look in operands for types.
131 const User *U = cast<User>(V);
132 for (Constant::const_op_iterator I = U->op_begin(),
133 E = U->op_end(); I != E;++I)
134 incorporateValue(*I);
135 }
136
137 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
138 /// find types hiding within.
incorporateMDNode(const MDNode * V)139 void TypeFinder::incorporateMDNode(const MDNode *V) {
140 // Already visited?
141 if (!VisitedConstants.insert(V).second)
142 return;
143
144 // Look in operands for types.
145 for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i)
146 if (Value *Op = V->getOperand(i))
147 incorporateValue(Op);
148 }
149