xref: /freebsd/contrib/llvm-project/llvm/lib/IR/TypeFinder.cpp (revision 6c4b055cfb6bf549e9145dde6454cc6b178c35e4)
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 
run(const Module & M,bool onlyNamed)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         // Incorporate types hiding in variable-location information.
93         for (const auto &Dbg : I.getDbgRecordRange()) {
94           // Pick out records that have Values.
95           if (const DbgVariableRecord *DVI =
96                   dyn_cast<DbgVariableRecord>(&Dbg)) {
97             for (Value *V : DVI->location_ops())
98               incorporateValue(V);
99             if (DVI->isDbgAssign()) {
100               if (Value *Addr = DVI->getAddress())
101                 incorporateValue(Addr);
102             }
103           }
104         }
105       }
106   }
107 
108   for (const auto &NMD : M.named_metadata())
109     for (const auto *MDOp : NMD.operands())
110       incorporateMDNode(MDOp);
111 }
112 
clear()113 void TypeFinder::clear() {
114   VisitedConstants.clear();
115   VisitedTypes.clear();
116   StructTypes.clear();
117 }
118 
119 /// incorporateType - This method adds the type to the list of used structures
120 /// if it's not in there already.
incorporateType(Type * Ty)121 void TypeFinder::incorporateType(Type *Ty) {
122   // Check to see if we've already visited this type.
123   if (!VisitedTypes.insert(Ty).second)
124     return;
125 
126   SmallVector<Type *, 4> TypeWorklist;
127   TypeWorklist.push_back(Ty);
128   do {
129     Ty = TypeWorklist.pop_back_val();
130 
131     // If this is a structure or opaque type, add a name for the type.
132     if (StructType *STy = dyn_cast<StructType>(Ty))
133       if (!OnlyNamed || STy->hasName())
134         StructTypes.push_back(STy);
135 
136     // Add all unvisited subtypes to worklist for processing
137     for (Type *SubTy : llvm::reverse(Ty->subtypes()))
138       if (VisitedTypes.insert(SubTy).second)
139         TypeWorklist.push_back(SubTy);
140   } while (!TypeWorklist.empty());
141 }
142 
143 /// incorporateValue - This method is used to walk operand lists finding types
144 /// hiding in constant expressions and other operands that won't be walked in
145 /// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
146 /// all explicitly enumerated.
incorporateValue(const Value * V)147 void TypeFinder::incorporateValue(const Value *V) {
148   if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
149     if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
150       return incorporateMDNode(N);
151     if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
152       return incorporateValue(MDV->getValue());
153     if (const auto *AL = dyn_cast<DIArgList>(M->getMetadata())) {
154       for (auto *Arg : AL->getArgs())
155         incorporateValue(Arg->getValue());
156       return;
157     }
158     return;
159   }
160 
161   if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
162 
163   // Already visited?
164   if (!VisitedConstants.insert(V).second)
165     return;
166 
167   // Check this type.
168   incorporateType(V->getType());
169 
170   // If this is an instruction, we incorporate it separately.
171   if (isa<Instruction>(V))
172     return;
173 
174   if (auto *GEP = dyn_cast<GEPOperator>(V))
175     incorporateType(GEP->getSourceElementType());
176 
177   // Look in operands for types.
178   const User *U = cast<User>(V);
179   for (const auto &I : U->operands())
180     incorporateValue(&*I);
181 }
182 
183 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
184 /// find types hiding within.
incorporateMDNode(const MDNode * V)185 void TypeFinder::incorporateMDNode(const MDNode *V) {
186   // Already visited?
187   if (!VisitedMetadata.insert(V).second)
188     return;
189 
190   // Look in operands for types.
191   for (Metadata *Op : V->operands()) {
192     if (!Op)
193       continue;
194     if (auto *N = dyn_cast<MDNode>(Op)) {
195       incorporateMDNode(N);
196       continue;
197     }
198     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
199       incorporateValue(C->getValue());
200       continue;
201     }
202   }
203 }
204 
incorporateAttributes(AttributeList AL)205 void TypeFinder::incorporateAttributes(AttributeList AL) {
206   if (!VisitedAttributes.insert(AL).second)
207     return;
208 
209   for (AttributeSet AS : AL)
210     for (Attribute A : AS)
211       if (A.isTypeAttribute())
212         incorporateType(A.getValueAsType());
213 }
214