LLVM  9.0.0svn
TypeFinder.cpp
Go to the documentation of this file.
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.
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 
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
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 }
uint64_t CallInst * C
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
This file contains the declarations for metadata subclasses.
Metadata node.
Definition: Metadata.h:863
This defines the Use class.
Class to represent struct types.
Definition: DerivedTypes.h:232
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
op_range operands() const
Definition: Metadata.h:1066
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
std::reverse_iterator< subtype_iterator > subtype_reverse_iterator
Definition: Type.h:320
op_range operands()
Definition: User.h:237
subtype_reverse_iterator subtype_rbegin() const
Definition: Type.h:322
void run(const Module &M, bool onlyNamed)
Definition: TypeFinder.cpp:31
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
subtype_reverse_iterator subtype_rend() const
Definition: Type.h:325
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
LLVM Value Representation.
Definition: Value.h:72
iterator_range< global_iterator > globals()
Definition: Module.h:587
Root of the metadata hierarchy.
Definition: Metadata.h:57
iterator_range< alias_iterator > aliases()
Definition: Module.h:627