Line data Source code
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 18994 : void TypeFinder::run(const Module &M, bool onlyNamed) {
33 18994 : OnlyNamed = onlyNamed;
34 :
35 : // Get types from global variables.
36 104409 : for (const auto &G : M.globals()) {
37 85415 : incorporateType(G.getType());
38 85415 : if (G.hasInitializer())
39 74321 : incorporateValue(G.getInitializer());
40 : }
41 :
42 : // Get types from aliases.
43 20276 : for (const auto &A : M.aliases()) {
44 1282 : incorporateType(A.getType());
45 : if (const Value *Aliasee = A.getAliasee())
46 1282 : incorporateValue(Aliasee);
47 : }
48 :
49 : // Get types from functions.
50 : SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
51 229778 : for (const Function &FI : M) {
52 210784 : incorporateType(FI.getType());
53 :
54 427253 : for (const Use &U : FI.operands())
55 5685 : incorporateValue(U.get());
56 :
57 : // First incorporate the arguments.
58 542356 : for (const auto &A : FI.args())
59 331572 : incorporateValue(&A);
60 :
61 523100 : for (const BasicBlock &BB : FI)
62 2593042 : for (const Instruction &I : BB) {
63 : // Incorporate the type of the instruction.
64 2280726 : incorporateType(I.getType());
65 :
66 : // Incorporate non-instruction operand types. (We are incorporating all
67 : // instructions with this loop.)
68 8252372 : for (const auto &O : I.operands())
69 3690920 : if (&*O && !isa<Instruction>(&*O))
70 1710841 : incorporateValue(&*O);
71 :
72 : // Incorporate types hiding in metadata.
73 : I.getAllMetadataOtherThanDebugLoc(MDForInst);
74 2371987 : for (const auto &MD : MDForInst)
75 91261 : incorporateMDNode(MD.second);
76 : MDForInst.clear();
77 : }
78 : }
79 :
80 39904 : for (const auto &NMD : M.named_metadata())
81 55147 : for (const auto &MDOp : NMD.operands())
82 34237 : incorporateMDNode(MDOp);
83 18994 : }
84 :
85 0 : void TypeFinder::clear() {
86 : VisitedConstants.clear();
87 : VisitedTypes.clear();
88 : StructTypes.clear();
89 0 : }
90 :
91 : /// incorporateType - This method adds the type to the list of used structures
92 : /// if it's not in there already.
93 2873344 : void TypeFinder::incorporateType(Type *Ty) {
94 : // Check to see if we've already visited this type.
95 2873344 : if (!VisitedTypes.insert(Ty).second)
96 2653847 : return;
97 :
98 : SmallVector<Type *, 4> TypeWorklist;
99 219497 : TypeWorklist.push_back(Ty);
100 : do {
101 477938 : Ty = TypeWorklist.pop_back_val();
102 :
103 : // If this is a structure or opaque type, add a name for the type.
104 477938 : if (StructType *STy = dyn_cast<StructType>(Ty))
105 42340 : if (!OnlyNamed || STy->hasName())
106 42287 : StructTypes.push_back(STy);
107 :
108 : // Add all unvisited subtypes to worklist for processing
109 477938 : for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
110 : E = Ty->subtype_rend();
111 1143605 : I != E; ++I)
112 665667 : if (VisitedTypes.insert(*I).second)
113 258441 : TypeWorklist.push_back(*I);
114 477938 : } while (!TypeWorklist.empty());
115 : }
116 :
117 : /// incorporateValue - This method is used to walk operand lists finding types
118 : /// hiding in constant expressions and other operands that won't be walked in
119 : /// other ways. GlobalValues, basic blocks, instructions, and inst operands are
120 : /// all explicitly enumerated.
121 2499651 : void TypeFinder::incorporateValue(const Value *V) {
122 2499651 : if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
123 16867 : if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
124 11140 : return incorporateMDNode(N);
125 : if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
126 5450 : return incorporateValue(MDV->getValue());
127 : return;
128 : }
129 :
130 2482784 : if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
131 :
132 : // Already visited?
133 1325495 : if (!VisitedConstants.insert(V).second)
134 : return;
135 :
136 : // Check this type.
137 295137 : incorporateType(V->getType());
138 :
139 : // If this is an instruction, we incorporate it separately.
140 590274 : if (isa<Instruction>(V))
141 : return;
142 :
143 : // Look in operands for types.
144 : const User *U = cast<User>(V);
145 587798 : for (const auto &I : U->operands())
146 292661 : incorporateValue(&*I);
147 : }
148 :
149 : /// incorporateMDNode - This method is used to walk the operands of an MDNode to
150 : /// find types hiding within.
151 232778 : void TypeFinder::incorporateMDNode(const MDNode *V) {
152 : // Already visited?
153 232778 : if (!VisitedMetadata.insert(V).second)
154 : return;
155 :
156 : // Look in operands for types.
157 379444 : for (Metadata *Op : V->operands()) {
158 290548 : if (!Op)
159 : continue;
160 : if (auto *N = dyn_cast<MDNode>(Op)) {
161 96140 : incorporateMDNode(N);
162 96140 : continue;
163 : }
164 : if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
165 77839 : incorporateValue(C->getValue());
166 77839 : continue;
167 : }
168 : }
169 : }
|
