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 ifuncs.
52   for (const auto &GI : M.ifuncs())
53     incorporateType(GI.getValueType());
54 
55   // Get types from functions.
56   SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
57   for (const Function &FI : M) {
58     incorporateType(FI.getFunctionType());
59     incorporateAttributes(FI.getAttributes());
60 
61     for (const Use &U : FI.operands())
62       incorporateValue(U.get());
63 
64     // First incorporate the arguments.
65     for (const auto &A : FI.args())
66       incorporateValue(&A);
67 
68     for (const BasicBlock &BB : FI)
69       for (const Instruction &I : BB) {
70         // Incorporate the type of the instruction.
71         incorporateType(I.getType());
72 
73         // Incorporate non-instruction operand types. (We are incorporating all
74         // instructions with this loop.)
75         for (const auto &O : I.operands())
76           if (&*O && !isa<Instruction>(&*O))
77             incorporateValue(&*O);
78 
79         if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
80           incorporateType(GEP->getSourceElementType());
81         if (auto *AI = dyn_cast<AllocaInst>(&I))
82           incorporateType(AI->getAllocatedType());
83         if (const auto *CB = dyn_cast<CallBase>(&I))
84           incorporateAttributes(CB->getAttributes());
85 
86         // Incorporate types hiding in metadata.
87         I.getAllMetadataOtherThanDebugLoc(MDForInst);
88         for (const auto &MD : MDForInst)
89           incorporateMDNode(MD.second);
90         MDForInst.clear();
91       }
92   }
93 
94   for (const auto &NMD : M.named_metadata())
95     for (const auto *MDOp : NMD.operands())
96       incorporateMDNode(MDOp);
97 }
98 
99 void TypeFinder::clear() {
100   VisitedConstants.clear();
101   VisitedTypes.clear();
102   StructTypes.clear();
103 }
104 
105 /// incorporateType - This method adds the type to the list of used structures
106 /// if it's not in there already.
107 void TypeFinder::incorporateType(Type *Ty) {
108   // Check to see if we've already visited this type.
109   if (!VisitedTypes.insert(Ty).second)
110     return;
111 
112   SmallVector<Type *, 4> TypeWorklist;
113   TypeWorklist.push_back(Ty);
114   do {
115     Ty = TypeWorklist.pop_back_val();
116 
117     // If this is a structure or opaque type, add a name for the type.
118     if (StructType *STy = dyn_cast<StructType>(Ty))
119       if (!OnlyNamed || STy->hasName())
120         StructTypes.push_back(STy);
121 
122     // Add all unvisited subtypes to worklist for processing
123     for (Type *SubTy : llvm::reverse(Ty->subtypes()))
124       if (VisitedTypes.insert(SubTy).second)
125         TypeWorklist.push_back(SubTy);
126   } while (!TypeWorklist.empty());
127 }
128 
129 /// incorporateValue - This method is used to walk operand lists finding types
130 /// hiding in constant expressions and other operands that won't be walked in
131 /// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
132 /// all explicitly enumerated.
133 void TypeFinder::incorporateValue(const Value *V) {
134   if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
135     if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
136       return incorporateMDNode(N);
137     if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
138       return incorporateValue(MDV->getValue());
139     return;
140   }
141 
142   if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
143 
144   // Already visited?
145   if (!VisitedConstants.insert(V).second)
146     return;
147 
148   // Check this type.
149   incorporateType(V->getType());
150 
151   // If this is an instruction, we incorporate it separately.
152   if (isa<Instruction>(V))
153     return;
154 
155   if (auto *GEP = dyn_cast<GEPOperator>(V))
156     incorporateType(GEP->getSourceElementType());
157 
158   // Look in operands for types.
159   const User *U = cast<User>(V);
160   for (const auto &I : U->operands())
161     incorporateValue(&*I);
162 }
163 
164 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
165 /// find types hiding within.
166 void TypeFinder::incorporateMDNode(const MDNode *V) {
167   // Already visited?
168   if (!VisitedMetadata.insert(V).second)
169     return;
170 
171   // The arguments in DIArgList are not exposed as operands, so handle such
172   // nodes specifically here.
173   if (const auto *AL = dyn_cast<DIArgList>(V)) {
174     for (auto *Arg : AL->getArgs())
175       incorporateValue(Arg->getValue());
176     return;
177   }
178 
179   // Look in operands for types.
180   for (Metadata *Op : V->operands()) {
181     if (!Op)
182       continue;
183     if (auto *N = dyn_cast<MDNode>(Op)) {
184       incorporateMDNode(N);
185       continue;
186     }
187     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
188       incorporateValue(C->getValue());
189       continue;
190     }
191   }
192 }
193 
194 void TypeFinder::incorporateAttributes(AttributeList AL) {
195   if (!VisitedAttributes.insert(AL).second)
196     return;
197 
198   for (AttributeSet AS : AL)
199     for (Attribute A : AS)
200       if (A.isTypeAttribute())
201         incorporateType(A.getValueAsType());
202 }
203