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/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 void TypeFinder::run(const Module &M, bool onlyNamed) {
33   OnlyNamed = onlyNamed;
34 
35   // Get types from global variables.
36   for (const auto &G : M.globals()) {
37     incorporateType(G.getType());
38     if (G.hasInitializer())
39       incorporateValue(G.getInitializer());
40   }
41 
42   // Get types from aliases.
43   for (const auto &A : M.aliases()) {
44     incorporateType(A.getType());
45     if (const Value *Aliasee = A.getAliasee())
46       incorporateValue(Aliasee);
47   }
48 
49   // Get types from functions.
50   SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
51   for (const Function &FI : M) {
52     incorporateType(FI.getType());
53 
54     for (const Use &U : FI.operands())
55       incorporateValue(U.get());
56 
57     // First incorporate the arguments.
58     for (const auto &A : FI.args())
59       incorporateValue(&A);
60 
61     for (const BasicBlock &BB : FI)
62       for (const Instruction &I : BB) {
63         // Incorporate the type of the instruction.
64         incorporateType(I.getType());
65 
66         // Incorporate non-instruction operand types. (We are incorporating all
67         // instructions with this loop.)
68         for (const auto &O : I.operands())
69           if (&*O && !isa<Instruction>(&*O))
70             incorporateValue(&*O);
71 
72         // Incorporate types hiding in metadata.
73         I.getAllMetadataOtherThanDebugLoc(MDForInst);
74         for (const auto &MD : MDForInst)
75           incorporateMDNode(MD.second);
76         MDForInst.clear();
77       }
78   }
79 
80   for (const auto &NMD : M.named_metadata())
81     for (const auto *MDOp : NMD.operands())
82       incorporateMDNode(MDOp);
83 }
84 
85 void TypeFinder::clear() {
86   VisitedConstants.clear();
87   VisitedTypes.clear();
88   StructTypes.clear();
89 }
90 
91 /// incorporateType - This method adds the type to the list of used structures
92 /// if it's not in there already.
93 void TypeFinder::incorporateType(Type *Ty) {
94   // Check to see if we've already visited this type.
95   if (!VisitedTypes.insert(Ty).second)
96     return;
97 
98   SmallVector<Type *, 4> TypeWorklist;
99   TypeWorklist.push_back(Ty);
100   do {
101     Ty = TypeWorklist.pop_back_val();
102 
103     // If this is a structure or opaque type, add a name for the type.
104     if (StructType *STy = dyn_cast<StructType>(Ty))
105       if (!OnlyNamed || STy->hasName())
106         StructTypes.push_back(STy);
107 
108     // Add all unvisited subtypes to worklist for processing
109     for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
110                                         E = Ty->subtype_rend();
111          I != E; ++I)
112       if (VisitedTypes.insert(*I).second)
113         TypeWorklist.push_back(*I);
114   } 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 void TypeFinder::incorporateValue(const Value *V) {
122   if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
123     if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
124       return incorporateMDNode(N);
125     if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
126       return incorporateValue(MDV->getValue());
127     return;
128   }
129 
130   if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
131 
132   // Already visited?
133   if (!VisitedConstants.insert(V).second)
134     return;
135 
136   // Check this type.
137   incorporateType(V->getType());
138 
139   // If this is an instruction, we incorporate it separately.
140   if (isa<Instruction>(V))
141     return;
142 
143   // Look in operands for types.
144   const User *U = cast<User>(V);
145   for (const auto &I : U->operands())
146     incorporateValue(&*I);
147 }
148 
149 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
150 /// find types hiding within.
151 void TypeFinder::incorporateMDNode(const MDNode *V) {
152   // Already visited?
153   if (!VisitedMetadata.insert(V).second)
154     return;
155 
156   // The arguments in DIArgList are not exposed as operands, so handle such
157   // nodes specifically here.
158   if (const auto *AL = dyn_cast<DIArgList>(V)) {
159     for (auto *Arg : AL->getArgs())
160       incorporateValue(Arg->getValue());
161     return;
162   }
163 
164   // Look in operands for types.
165   for (Metadata *Op : V->operands()) {
166     if (!Op)
167       continue;
168     if (auto *N = dyn_cast<MDNode>(Op)) {
169       incorporateMDNode(N);
170       continue;
171     }
172     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
173       incorporateValue(C->getValue());
174       continue;
175     }
176   }
177 }
178