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