LLVM  15.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/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 
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.
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  }
93 
94  for (const auto &NMD : M.named_metadata())
95  for (const auto *MDOp : NMD.operands())
96  incorporateMDNode(MDOp);
97 }
98 
100  VisitedConstants.clear();
101  VisitedTypes.clear();
102  StructTypes.clear();
103 }
104 
105 /// incorporateType - This method adds the type to the list of used structures
106 /// if it's not in there already.
107 void TypeFinder::incorporateType(Type *Ty) {
108  // Check to see if we've already visited this type.
109  if (!VisitedTypes.insert(Ty).second)
110  return;
111 
112  SmallVector<Type *, 4> TypeWorklist;
113  TypeWorklist.push_back(Ty);
114  do {
115  Ty = TypeWorklist.pop_back_val();
116 
117  // If this is a structure or opaque type, add a name for the type.
118  if (StructType *STy = dyn_cast<StructType>(Ty))
119  if (!OnlyNamed || STy->hasName())
120  StructTypes.push_back(STy);
121 
122  // Add all unvisited subtypes to worklist for processing
123  for (Type *SubTy : llvm::reverse(Ty->subtypes()))
124  if (VisitedTypes.insert(SubTy).second)
125  TypeWorklist.push_back(SubTy);
126  } while (!TypeWorklist.empty());
127 }
128 
129 /// incorporateValue - This method is used to walk operand lists finding types
130 /// hiding in constant expressions and other operands that won't be walked in
131 /// other ways. GlobalValues, basic blocks, instructions, and inst operands are
132 /// all explicitly enumerated.
133 void TypeFinder::incorporateValue(const Value *V) {
134  if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
135  if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
136  return incorporateMDNode(N);
137  if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
138  return incorporateValue(MDV->getValue());
139  return;
140  }
141 
142  if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
143 
144  // Already visited?
145  if (!VisitedConstants.insert(V).second)
146  return;
147 
148  // Check this type.
149  incorporateType(V->getType());
150 
151  // If this is an instruction, we incorporate it separately.
152  if (isa<Instruction>(V))
153  return;
154 
155  if (auto *GEP = dyn_cast<GEPOperator>(V))
156  incorporateType(GEP->getSourceElementType());
157 
158  // Look in operands for types.
159  const User *U = cast<User>(V);
160  for (const auto &I : U->operands())
161  incorporateValue(&*I);
162 }
163 
164 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
165 /// find types hiding within.
166 void TypeFinder::incorporateMDNode(const MDNode *V) {
167  // Already visited?
168  if (!VisitedMetadata.insert(V).second)
169  return;
170 
171  // The arguments in DIArgList are not exposed as operands, so handle such
172  // nodes specifically here.
173  if (const auto *AL = dyn_cast<DIArgList>(V)) {
174  for (auto *Arg : AL->getArgs())
175  incorporateValue(Arg->getValue());
176  return;
177  }
178 
179  // Look in operands for types.
180  for (Metadata *Op : V->operands()) {
181  if (!Op)
182  continue;
183  if (auto *N = dyn_cast<MDNode>(Op)) {
184  incorporateMDNode(N);
185  continue;
186  }
187  if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
188  incorporateValue(C->getValue());
189  continue;
190  }
191  }
192 }
193 
194 void TypeFinder::incorporateAttributes(AttributeList AL) {
195  if (!VisitedAttributes.insert(AL).second)
196  return;
197 
198  for (AttributeSet AS : AL)
199  for (Attribute A : AS)
200  if (A.isTypeAttribute())
201  incorporateType(A.getValueAsType());
202 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:269
Metadata.h
llvm::User::operands
op_range operands()
Definition: User.h:242
DebugInfoMetadata.h
llvm::Function
Definition: Function.h:60
llvm::Attribute
Definition: Attributes.h:52
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::AttributeList
Definition: Attributes.h:408
Operator.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
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:1191
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
Instruction.h
llvm::TypeFinder::clear
void clear()
Definition: TypeFinder.cpp:99
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
TypeFinder.h
llvm::Instruction
Definition: Instruction.h:42
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
Type.h
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::Type::subtypes
ArrayRef< Type * > subtypes() const
Definition: Type.h:322
BasicBlock.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MDNode
Metadata node.
Definition: Metadata.h:926
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::TypeFinder::run
void run(const Module &M, bool onlyNamed)
Definition: TypeFinder.cpp:34
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
Constant.h
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:326
Casting.h
Function.h
Instructions.h
llvm::AttributeSet
Definition: Attributes.h:274
SmallVector.h
User.h
N
#define N
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
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43