LLVM  6.0.0svn
TypeFinder.cpp
Go to the documentation of this file.
1 //===- TypeFinder.cpp - Implement the TypeFinder class --------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the TypeFinder class for the IR library.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/IR/TypeFinder.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/IR/BasicBlock.h"
17 #include "llvm/IR/Constant.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.
37  E = M.global_end(); I != E; ++I) {
38  incorporateType(I->getType());
39  if (I->hasInitializer())
40  incorporateValue(I->getInitializer());
41  }
42 
43  // Get types from aliases.
45  E = M.alias_end(); I != E; ++I) {
46  incorporateType(I->getType());
47  if (const Value *Aliasee = I->getAliasee())
48  incorporateValue(Aliasee);
49  }
50 
51  // Get types from functions.
53  for (const Function &FI : M) {
54  incorporateType(FI.getType());
55 
56  for (const Use &U : FI.operands())
57  incorporateValue(U.get());
58 
59  // First incorporate the arguments.
60  for (Function::const_arg_iterator AI = FI.arg_begin(), AE = FI.arg_end();
61  AI != AE; ++AI)
62  incorporateValue(&*AI);
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 (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
72  OI != OE; ++OI)
73  if (*OI && !isa<Instruction>(OI))
74  incorporateValue(*OI);
75 
76  // Incorporate types hiding in metadata.
77  I.getAllMetadataOtherThanDebugLoc(MDForInst);
78  for (unsigned i = 0, e = MDForInst.size(); i != e; ++i)
79  incorporateMDNode(MDForInst[i].second);
80 
81  MDForInst.clear();
82  }
83  }
84 
85  for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
86  E = M.named_metadata_end(); I != E; ++I) {
87  const NamedMDNode *NMD = &*I;
88  for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
89  incorporateMDNode(NMD->getOperand(i));
90  }
91 }
92 
94  VisitedConstants.clear();
95  VisitedTypes.clear();
96  StructTypes.clear();
97 }
98 
99 /// incorporateType - This method adds the type to the list of used structures
100 /// if it's not in there already.
101 void TypeFinder::incorporateType(Type *Ty) {
102  // Check to see if we've already visited this type.
103  if (!VisitedTypes.insert(Ty).second)
104  return;
105 
106  SmallVector<Type *, 4> TypeWorklist;
107  TypeWorklist.push_back(Ty);
108  do {
109  Ty = TypeWorklist.pop_back_val();
110 
111  // If this is a structure or opaque type, add a name for the type.
112  if (StructType *STy = dyn_cast<StructType>(Ty))
113  if (!OnlyNamed || STy->hasName())
114  StructTypes.push_back(STy);
115 
116  // Add all unvisited subtypes to worklist for processing
118  E = Ty->subtype_rend();
119  I != E; ++I)
120  if (VisitedTypes.insert(*I).second)
121  TypeWorklist.push_back(*I);
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  // Look in operands for types.
152  const User *U = cast<User>(V);
154  E = U->op_end(); I != E;++I)
155  incorporateValue(*I);
156 }
157 
158 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
159 /// find types hiding within.
160 void TypeFinder::incorporateMDNode(const MDNode *V) {
161  // Already visited?
162  if (!VisitedMetadata.insert(V).second)
163  return;
164 
165  // Look in operands for types.
166  for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) {
167  Metadata *Op = V->getOperand(i);
168  if (!Op)
169  continue;
170  if (auto *N = dyn_cast<MDNode>(Op)) {
171  incorporateMDNode(N);
172  continue;
173  }
174  if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
175  incorporateValue(C->getValue());
176  continue;
177  }
178  }
179 }
uint64_t CallInst * C
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
MDNode * getOperand(unsigned i) const
Definition: Metadata.cpp:1073
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
This file contains the declarations for metadata subclasses.
unsigned second
Metadata node.
Definition: Metadata.h:862
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
This defines the Use class.
op_iterator op_begin()
Definition: User.h:214
A tuple of MDNodes.
Definition: Metadata.h:1323
Class to represent struct types.
Definition: DerivedTypes.h:201
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
unsigned getNumOperands() const
Definition: Metadata.cpp:1069
global_iterator global_begin()
Definition: Module.h:555
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
alias_iterator alias_end()
Definition: Module.h:596
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
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:318
op_iterator op_end()
Definition: User.h:216
subtype_reverse_iterator subtype_rbegin() const
Definition: Type.h:320
global_iterator global_end()
Definition: Module.h:557
Iterator for intrusive lists based on ilist_node.
void run(const Module &M, bool onlyNamed)
Definition: TypeFinder.cpp:32
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
alias_iterator alias_begin()
Definition: Module.h:594
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
subtype_reverse_iterator subtype_rend() const
Definition: Type.h:323
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
LLVM Value Representation.
Definition: Value.h:73
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
Root of the metadata hierarchy.
Definition: Metadata.h:58