LLVM  13.0.0git
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"
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.
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 
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
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 }
llvm
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:250
Metadata.h
llvm::User::operands
op_range operands()
Definition: User.h:242
DebugInfoMetadata.h
llvm::Function
Definition: Function.h:61
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
Module.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:634
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
Use.h
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1100
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
Instruction.h
llvm::TypeFinder::clear
void clear()
Definition: TypeFinder.cpp:85
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
TypeFinder.h
llvm::Instruction
Definition: Instruction.h:45
llvm::Type::subtype_rbegin
subtype_reverse_iterator subtype_rbegin() const
Definition: Type.h:336
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
Type.h
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
BasicBlock.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:179
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::Type::subtype_rend
subtype_reverse_iterator subtype_rend() const
Definition: Type.h:339
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
llvm::TypeFinder::run
void run(const Module &M, bool onlyNamed)
Definition: TypeFinder.cpp:32
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
Constant.h
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
Casting.h
Function.h
SmallVector.h
User.h
N
#define N
llvm::Type::subtype_reverse_iterator
std::reverse_iterator< subtype_iterator > subtype_reverse_iterator
Definition: Type.h:334
DerivedTypes.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44