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/DebugInfoMetadata.h"
18 #include "llvm/IR/DerivedTypes.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/Instruction.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/Metadata.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/Operator.h"
25 #include "llvm/IR/Type.h"
26 #include "llvm/IR/Use.h"
27 #include "llvm/IR/User.h"
28 #include "llvm/IR/Value.h"
29 #include "llvm/Support/Casting.h"
30 #include <utility>
31 
32 using namespace llvm;
33 
34 void TypeFinder::run(const Module &M, bool onlyNamed) {
35   OnlyNamed = onlyNamed;
36 
37   // Get types from global variables.
38   for (const auto &G : M.globals()) {
39     incorporateType(G.getValueType());
40     if (G.hasInitializer())
41       incorporateValue(G.getInitializer());
42   }
43 
44   // Get types from aliases.
45   for (const auto &A : M.aliases()) {
46     incorporateType(A.getValueType());
47     if (const Value *Aliasee = A.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.getFunctionType());
55     incorporateAttributes(FI.getAttributes());
56 
57     for (const Use &U : FI.operands())
58       incorporateValue(U.get());
59 
60     // First incorporate the arguments.
61     for (const auto &A : FI.args())
62       incorporateValue(&A);
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 (const auto &O : I.operands())
72           if (&*O && !isa<Instruction>(&*O))
73             incorporateValue(&*O);
74 
75         if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
76           incorporateType(GEP->getSourceElementType());
77         if (auto *AI = dyn_cast<AllocaInst>(&I))
78           incorporateType(AI->getAllocatedType());
79         if (const auto *CB = dyn_cast<CallBase>(&I))
80           incorporateAttributes(CB->getAttributes());
81 
82         // Incorporate types hiding in metadata.
83         I.getAllMetadataOtherThanDebugLoc(MDForInst);
84         for (const auto &MD : MDForInst)
85           incorporateMDNode(MD.second);
86         MDForInst.clear();
87       }
88   }
89 
90   for (const auto &NMD : M.named_metadata())
91     for (const auto *MDOp : NMD.operands())
92       incorporateMDNode(MDOp);
93 }
94 
95 void TypeFinder::clear() {
96   VisitedConstants.clear();
97   VisitedTypes.clear();
98   StructTypes.clear();
99 }
100 
101 /// incorporateType - This method adds the type to the list of used structures
102 /// if it's not in there already.
103 void TypeFinder::incorporateType(Type *Ty) {
104   // Check to see if we've already visited this type.
105   if (!VisitedTypes.insert(Ty).second)
106     return;
107 
108   SmallVector<Type *, 4> TypeWorklist;
109   TypeWorklist.push_back(Ty);
110   do {
111     Ty = TypeWorklist.pop_back_val();
112 
113     // If this is a structure or opaque type, add a name for the type.
114     if (StructType *STy = dyn_cast<StructType>(Ty))
115       if (!OnlyNamed || STy->hasName())
116         StructTypes.push_back(STy);
117 
118     // Add all unvisited subtypes to worklist for processing
119     for (Type *SubTy : llvm::reverse(Ty->subtypes()))
120       if (VisitedTypes.insert(SubTy).second)
121         TypeWorklist.push_back(SubTy);
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   if (auto *GEP = dyn_cast<GEPOperator>(V))
152     incorporateType(GEP->getSourceElementType());
153 
154   // Look in operands for types.
155   const User *U = cast<User>(V);
156   for (const auto &I : U->operands())
157     incorporateValue(&*I);
158 }
159 
160 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
161 /// find types hiding within.
162 void TypeFinder::incorporateMDNode(const MDNode *V) {
163   // Already visited?
164   if (!VisitedMetadata.insert(V).second)
165     return;
166 
167   // The arguments in DIArgList are not exposed as operands, so handle such
168   // nodes specifically here.
169   if (const auto *AL = dyn_cast<DIArgList>(V)) {
170     for (auto *Arg : AL->getArgs())
171       incorporateValue(Arg->getValue());
172     return;
173   }
174 
175   // Look in operands for types.
176   for (Metadata *Op : V->operands()) {
177     if (!Op)
178       continue;
179     if (auto *N = dyn_cast<MDNode>(Op)) {
180       incorporateMDNode(N);
181       continue;
182     }
183     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
184       incorporateValue(C->getValue());
185       continue;
186     }
187   }
188 }
189 
190 void TypeFinder::incorporateAttributes(AttributeList AL) {
191   if (!VisitedAttributes.insert(AL).second)
192     return;
193 
194   for (AttributeSet AS : AL)
195     for (Attribute A : AS)
196       if (A.isTypeAttribute())
197         incorporateType(A.getValueAsType());
198 }
199