1 //===- TypeFinder.cpp - Implement the TypeFinder class --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the TypeFinder class for the IR library.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/IR/TypeFinder.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Constant.h"
17 #include "llvm/IR/DerivedTypes.h"
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/Instruction.h"
20 #include "llvm/IR/Metadata.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/IR/Type.h"
23 #include "llvm/IR/Use.h"
24 #include "llvm/IR/User.h"
25 #include "llvm/IR/Value.h"
26 #include "llvm/Support/Casting.h"
27 #include <utility>
28 
29 using namespace llvm;
30 
31 void TypeFinder::run(const Module &M, bool onlyNamed) {
32   OnlyNamed = onlyNamed;
33 
34   // Get types from global variables.
35   for (const auto &G : M.globals()) {
36     incorporateType(G.getType());
37     if (G.hasInitializer())
38       incorporateValue(G.getInitializer());
39   }
40 
41   // Get types from aliases.
42   for (const auto &A : M.aliases()) {
43     incorporateType(A.getType());
44     if (const Value *Aliasee = A.getAliasee())
45       incorporateValue(Aliasee);
46   }
47 
48   // Get types from functions.
49   SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
50   for (const Function &FI : M) {
51     incorporateType(FI.getType());
52 
53     for (const Use &U : FI.operands())
54       incorporateValue(U.get());
55 
56     // First incorporate the arguments.
57     for (const auto &A : FI.args())
58       incorporateValue(&A);
59 
60     for (const BasicBlock &BB : FI)
61       for (const Instruction &I : BB) {
62         // Incorporate the type of the instruction.
63         incorporateType(I.getType());
64 
65         // Incorporate non-instruction operand types. (We are incorporating all
66         // instructions with this loop.)
67         for (const auto &O : I.operands())
68           if (&*O && !isa<Instruction>(&*O))
69             incorporateValue(&*O);
70 
71         // Incorporate types hiding in metadata.
72         I.getAllMetadataOtherThanDebugLoc(MDForInst);
73         for (const auto &MD : MDForInst)
74           incorporateMDNode(MD.second);
75         MDForInst.clear();
76       }
77   }
78 
79   for (const auto &NMD : M.named_metadata())
80     for (const auto *MDOp : NMD.operands())
81       incorporateMDNode(MDOp);
82 }
83 
84 void TypeFinder::clear() {
85   VisitedConstants.clear();
86   VisitedTypes.clear();
87   StructTypes.clear();
88 }
89 
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)
95     return;
96 
97   SmallVector<Type *, 4> TypeWorklist;
98   TypeWorklist.push_back(Ty);
99   do {
100     Ty = TypeWorklist.pop_back_val();
101 
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);
106 
107     // Add all unvisited subtypes to worklist for processing
108     for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
109                                         E = Ty->subtype_rend();
110          I != E; ++I)
111       if (VisitedTypes.insert(*I).second)
112         TypeWorklist.push_back(*I);
113   } while (!TypeWorklist.empty());
114 }
115 
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());
126     return;
127   }
128 
129   if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
130 
131   // Already visited?
132   if (!VisitedConstants.insert(V).second)
133     return;
134 
135   // Check this type.
136   incorporateType(V->getType());
137 
138   // If this is an instruction, we incorporate it separately.
139   if (isa<Instruction>(V))
140     return;
141 
142   // Look in operands for types.
143   const User *U = cast<User>(V);
144   for (const auto &I : U->operands())
145     incorporateValue(&*I);
146 }
147 
148 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
149 /// find types hiding within.
150 void TypeFinder::incorporateMDNode(const MDNode *V) {
151   // Already visited?
152   if (!VisitedMetadata.insert(V).second)
153     return;
154 
155   // Look in operands for types.
156   for (Metadata *Op : V->operands()) {
157     if (!Op)
158       continue;
159     if (auto *N = dyn_cast<MDNode>(Op)) {
160       incorporateMDNode(N);
161       continue;
162     }
163     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
164       incorporateValue(C->getValue());
165       continue;
166     }
167   }
168 }
169