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 
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     if (FI->hasPrefixData())
48       incorporateValue(FI->getPrefixData());
49 
50     if (FI->hasPrologueData())
51       incorporateValue(FI->getPrologueData());
52 
53     if (FI->hasPersonalityFn())
54       incorporateValue(FI->getPersonalityFn());
55 
56     // First incorporate the arguments.
57     for (Function::const_arg_iterator AI = FI->arg_begin(),
58            AE = FI->arg_end(); AI != AE; ++AI)
59       incorporateValue(&*AI);
60 
61     for (Function::const_iterator BB = FI->begin(), E = FI->end();
62          BB != E;++BB)
63       for (BasicBlock::const_iterator II = BB->begin(),
64              E = BB->end(); II != E; ++II) {
65         const Instruction &I = *II;
66 
67         // Incorporate the type of the instruction.
68         incorporateType(I.getType());
69 
70         // Incorporate non-instruction operand types. (We are incorporating all
71         // instructions with this loop.)
72         for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
73              OI != OE; ++OI)
74           if (*OI && !isa<Instruction>(OI))
75             incorporateValue(*OI);
76 
77         // Incorporate types hiding in metadata.
78         I.getAllMetadataOtherThanDebugLoc(MDForInst);
79         for (unsigned i = 0, e = MDForInst.size(); i != e; ++i)
80           incorporateMDNode(MDForInst[i].second);
81 
82         MDForInst.clear();
83       }
84   }
85 
86   for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
87          E = M.named_metadata_end(); I != E; ++I) {
88     const NamedMDNode *NMD = &*I;
89     for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
90       incorporateMDNode(NMD->getOperand(i));
91   }
92 }
93 
94 void TypeFinder::clear() {
95   VisitedConstants.clear();
96   VisitedTypes.clear();
97   StructTypes.clear();
98 }
99 
100 /// incorporateType - This method adds the type to the list of used structures
101 /// if it's not in there already.
102 void TypeFinder::incorporateType(Type *Ty) {
103   // Check to see if we've already visited this type.
104   if (!VisitedTypes.insert(Ty).second)
105     return;
106 
107   SmallVector<Type *, 4> TypeWorklist;
108   TypeWorklist.push_back(Ty);
109   do {
110     Ty = TypeWorklist.pop_back_val();
111 
112     // If this is a structure or opaque type, add a name for the type.
113     if (StructType *STy = dyn_cast<StructType>(Ty))
114       if (!OnlyNamed || STy->hasName())
115         StructTypes.push_back(STy);
116 
117     // Add all unvisited subtypes to worklist for processing
118     for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
119                                         E = Ty->subtype_rend();
120          I != E; ++I)
121       if (VisitedTypes.insert(*I).second)
122         TypeWorklist.push_back(*I);
123   } while (!TypeWorklist.empty());
124 }
125 
126 /// incorporateValue - This method is used to walk operand lists finding types
127 /// hiding in constant expressions and other operands that won't be walked in
128 /// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
129 /// all explicitly enumerated.
130 void TypeFinder::incorporateValue(const Value *V) {
131   if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
132     if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
133       return incorporateMDNode(N);
134     if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
135       return incorporateValue(MDV->getValue());
136     return;
137   }
138 
139   if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
140 
141   // Already visited?
142   if (!VisitedConstants.insert(V).second)
143     return;
144 
145   // Check this type.
146   incorporateType(V->getType());
147 
148   // If this is an instruction, we incorporate it separately.
149   if (isa<Instruction>(V))
150     return;
151 
152   // Look in operands for types.
153   const User *U = cast<User>(V);
154   for (Constant::const_op_iterator I = U->op_begin(),
155          E = U->op_end(); I != E;++I)
156     incorporateValue(*I);
157 }
158 
159 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
160 /// find types hiding within.
161 void TypeFinder::incorporateMDNode(const MDNode *V) {
162   // Already visited?
163   if (!VisitedMetadata.insert(V).second)
164     return;
165 
166   // Look in operands for types.
167   for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) {
168     Metadata *Op = V->getOperand(i);
169     if (!Op)
170       continue;
171     if (auto *N = dyn_cast<MDNode>(Op)) {
172       incorporateMDNode(N);
173       continue;
174     }
175     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
176       incorporateValue(C->getValue());
177       continue;
178     }
179   }
180 }
181