LLVM 19.0.0git
CSEMIRBuilder.cpp
Go to the documentation of this file.
1//===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.cpp - MIBuilder--*- C++ -*-==//
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/// \file
9/// This file implements the CSEMIRBuilder class which CSEs as it builds
10/// instructions.
11//===----------------------------------------------------------------------===//
12//
13
20
21using namespace llvm;
22
23bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
25 auto MBBEnd = getMBB().end();
26 if (B == MBBEnd)
27 return true;
28 assert(A->getParent() == B->getParent() &&
29 "Iterators should be in same block");
30 const MachineBasicBlock *BBA = A->getParent();
32 for (; &*I != A && &*I != B; ++I)
33 ;
34 return &*I == A;
35}
36
38CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
39 void *&NodeInsertPos) {
40 GISelCSEInfo *CSEInfo = getCSEInfo();
41 assert(CSEInfo && "Can't get here without setting CSEInfo");
42 MachineBasicBlock *CurMBB = &getMBB();
44 CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
45 if (MI) {
46 CSEInfo->countOpcodeHit(MI->getOpcode());
47 auto CurrPos = getInsertPt();
49 if (MII == CurrPos) {
50 // Move the insert point ahead of the instruction so any future uses of
51 // this builder will have the def ready.
52 setInsertPt(*CurMBB, std::next(MII));
53 } else if (!dominates(MI, CurrPos)) {
54 CurMBB->splice(CurrPos, CurMBB, MI);
55 }
56 return MachineInstrBuilder(getMF(), MI);
57 }
58 return MachineInstrBuilder();
59}
60
61bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
62 const GISelCSEInfo *CSEInfo = getCSEInfo();
63 if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
64 return false;
65 return true;
66}
67
68void CSEMIRBuilder::profileDstOp(const DstOp &Op,
70 switch (Op.getDstOpKind()) {
72 B.addNodeIDRegType(Op.getRegClass());
73 break;
75 // Regs can have LLT&(RB|RC). If those exist, profile them as well.
76 B.addNodeIDReg(Op.getReg());
77 break;
78 }
79 default:
80 B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
81 break;
82 }
83}
84
85void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
87 switch (Op.getSrcOpKind()) {
89 B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm()));
90 break;
92 B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
93 break;
94 default:
95 B.addNodeIDRegType(Op.getReg());
96 break;
97 }
98}
99
100void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
101 unsigned Opc) const {
102 // First add the MBB (Local CSE).
103 B.addNodeIDMBB(&getMBB());
104 // Then add the opcode.
105 B.addNodeIDOpcode(Opc);
106}
107
108void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
109 ArrayRef<SrcOp> SrcOps,
110 std::optional<unsigned> Flags,
111 GISelInstProfileBuilder &B) const {
112
113 profileMBBOpcode(B, Opc);
114 // Then add the DstOps.
115 profileDstOps(DstOps, B);
116 // Then add the SrcOps.
117 profileSrcOps(SrcOps, B);
118 // Add Flags if passed in.
119 if (Flags)
120 B.addNodeIDFlag(*Flags);
121}
122
123MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
124 void *NodeInsertPos) {
125 assert(canPerformCSEForOpc(MIB->getOpcode()) &&
126 "Attempting to CSE illegal op");
127 MachineInstr *MIBInstr = MIB;
128 getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);
129 return MIB;
130}
131
132bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
133 if (DstOps.size() == 1)
134 return true; // always possible to emit copy to just 1 vreg.
135
136 return llvm::all_of(DstOps, [](const DstOp &Op) {
137 DstOp::DstType DT = Op.getDstOpKind();
138 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
139 });
140}
141
143CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
144 MachineInstrBuilder &MIB) {
145 assert(checkCopyToDefsPossible(DstOps) &&
146 "Impossible return a single MIB with copies to multiple defs");
147 if (DstOps.size() == 1) {
148 const DstOp &Op = DstOps[0];
149 if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
150 return buildCopy(Op.getReg(), MIB.getReg(0));
151 }
152
153 // If we didn't generate a copy then we're re-using an existing node directly
154 // instead of emitting any code. Merge the debug location we wanted to emit
155 // into the instruction we're CSE'ing with. Debug locations arent part of the
156 // profile so we don't need to recompute it.
157 if (getDebugLoc()) {
159 if (Observer)
160 Observer->changingInstr(*MIB);
161 MIB->setDebugLoc(
163 if (Observer)
164 Observer->changedInstr(*MIB);
165 }
166
167 return MIB;
168}
169
171 ArrayRef<DstOp> DstOps,
172 ArrayRef<SrcOp> SrcOps,
173 std::optional<unsigned> Flag) {
174 switch (Opc) {
175 default:
176 break;
177 case TargetOpcode::G_ADD:
178 case TargetOpcode::G_PTR_ADD:
179 case TargetOpcode::G_AND:
180 case TargetOpcode::G_ASHR:
181 case TargetOpcode::G_LSHR:
182 case TargetOpcode::G_MUL:
183 case TargetOpcode::G_OR:
184 case TargetOpcode::G_SHL:
185 case TargetOpcode::G_SUB:
186 case TargetOpcode::G_XOR:
187 case TargetOpcode::G_UDIV:
188 case TargetOpcode::G_SDIV:
189 case TargetOpcode::G_UREM:
190 case TargetOpcode::G_SREM:
191 case TargetOpcode::G_SMIN:
192 case TargetOpcode::G_SMAX:
193 case TargetOpcode::G_UMIN:
194 case TargetOpcode::G_UMAX: {
195 // Try to constant fold these.
196 assert(SrcOps.size() == 2 && "Invalid sources");
197 assert(DstOps.size() == 1 && "Invalid dsts");
198 LLT SrcTy = SrcOps[0].getLLTTy(*getMRI());
199
200 if (Opc == TargetOpcode::G_PTR_ADD &&
201 getDataLayout().isNonIntegralAddressSpace(SrcTy.getAddressSpace()))
202 break;
203
204 if (SrcTy.isVector()) {
205 // Try to constant fold vector constants.
207 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI());
208 if (!VecCst.empty())
209 return buildBuildVectorConstant(DstOps[0], VecCst);
210 break;
211 }
212
213 if (std::optional<APInt> Cst = ConstantFoldBinOp(
214 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
215 return buildConstant(DstOps[0], *Cst);
216 break;
217 }
218 case TargetOpcode::G_FADD:
219 case TargetOpcode::G_FSUB:
220 case TargetOpcode::G_FMUL:
221 case TargetOpcode::G_FDIV:
222 case TargetOpcode::G_FREM:
223 case TargetOpcode::G_FMINNUM:
224 case TargetOpcode::G_FMAXNUM:
225 case TargetOpcode::G_FMINNUM_IEEE:
226 case TargetOpcode::G_FMAXNUM_IEEE:
227 case TargetOpcode::G_FMINIMUM:
228 case TargetOpcode::G_FMAXIMUM:
229 case TargetOpcode::G_FCOPYSIGN: {
230 // Try to constant fold these.
231 assert(SrcOps.size() == 2 && "Invalid sources");
232 assert(DstOps.size() == 1 && "Invalid dsts");
233 if (std::optional<APFloat> Cst = ConstantFoldFPBinOp(
234 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
235 return buildFConstant(DstOps[0], *Cst);
236 break;
237 }
238 case TargetOpcode::G_SEXT_INREG: {
239 assert(DstOps.size() == 1 && "Invalid dst ops");
240 assert(SrcOps.size() == 2 && "Invalid src ops");
241 const DstOp &Dst = DstOps[0];
242 const SrcOp &Src0 = SrcOps[0];
243 const SrcOp &Src1 = SrcOps[1];
244 if (auto MaybeCst =
245 ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
246 return buildConstant(Dst, *MaybeCst);
247 break;
248 }
249 case TargetOpcode::G_SITOFP:
250 case TargetOpcode::G_UITOFP: {
251 // Try to constant fold these.
252 assert(SrcOps.size() == 1 && "Invalid sources");
253 assert(DstOps.size() == 1 && "Invalid dsts");
254 if (std::optional<APFloat> Cst = ConstantFoldIntToFloat(
255 Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
256 return buildFConstant(DstOps[0], *Cst);
257 break;
258 }
259 case TargetOpcode::G_CTLZ: {
260 assert(SrcOps.size() == 1 && "Expected one source");
261 assert(DstOps.size() == 1 && "Expected one dest");
262 auto MaybeCsts = ConstantFoldCTLZ(SrcOps[0].getReg(), *getMRI());
263 if (!MaybeCsts)
264 break;
265 if (MaybeCsts->size() == 1)
266 return buildConstant(DstOps[0], (*MaybeCsts)[0]);
267 // This was a vector constant. Build a G_BUILD_VECTOR for them.
268 SmallVector<Register> ConstantRegs;
269 LLT VecTy = DstOps[0].getLLTTy(*getMRI());
270 for (unsigned Cst : *MaybeCsts)
271 ConstantRegs.emplace_back(
272 buildConstant(VecTy.getScalarType(), Cst).getReg(0));
273 return buildBuildVector(DstOps[0], ConstantRegs);
274 }
275 }
276 bool CanCopy = checkCopyToDefsPossible(DstOps);
277 if (!canPerformCSEForOpc(Opc))
278 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
279 // If we can CSE this instruction, but involves generating copies to multiple
280 // regs, give up. This frequently happens to UNMERGEs.
281 if (!CanCopy) {
282 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
283 // CSEInfo would have tracked this instruction. Remove it from the temporary
284 // insts.
286 return MIB;
287 }
289 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
290 void *InsertPos = nullptr;
291 profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
292 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
293 if (MIB) {
294 // Handle generating copies here.
295 return generateCopiesIfRequired(DstOps, MIB);
296 }
297 // This instruction does not exist in the CSEInfo. Build it and CSE it.
298 MachineInstrBuilder NewMIB =
299 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
300 return memoizeMI(NewMIB, InsertPos);
301}
302
304 const ConstantInt &Val) {
305 constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
306 if (!canPerformCSEForOpc(Opc))
307 return MachineIRBuilder::buildConstant(Res, Val);
308
309 // For vectors, CSE the element only for now.
310 LLT Ty = Res.getLLTTy(*getMRI());
311 if (Ty.isVector())
312 return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
313
315 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
316 void *InsertPos = nullptr;
317 profileMBBOpcode(ProfBuilder, Opc);
318 profileDstOp(Res, ProfBuilder);
320 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
321 if (MIB) {
322 // Handle generating copies here.
323 return generateCopiesIfRequired({Res}, MIB);
324 }
325
327 return memoizeMI(NewMIB, InsertPos);
328}
329
331 const ConstantFP &Val) {
332 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
333 if (!canPerformCSEForOpc(Opc))
334 return MachineIRBuilder::buildFConstant(Res, Val);
335
336 // For vectors, CSE the element only for now.
337 LLT Ty = Res.getLLTTy(*getMRI());
338 if (Ty.isVector())
339 return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val));
340
342 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
343 void *InsertPos = nullptr;
344 profileMBBOpcode(ProfBuilder, Opc);
345 profileDstOp(Res, ProfBuilder);
347 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
348 if (MIB) {
349 // Handle generating copies here.
350 return generateCopiesIfRequired({Res}, MIB);
351 }
353 return memoizeMI(NewMIB, InsertPos);
354}
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Provides analysis for continuously CSEing during GISel passes.
This file implements a version of MachineIRBuilder which CSEs insts within a MachineBasicBlock.
This contains common code to allow clients to notify changes to machine instr.
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
static unsigned getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
MachineInstrBuilder buildInstr(unsigned Opc, ArrayRef< DstOp > DstOps, ArrayRef< SrcOp > SrcOps, std::optional< unsigned > Flag=std::nullopt) override
MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val) override
Build and insert Res = G_FCONSTANT Val.
MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val) override
Build and insert Res = G_CONSTANT Val.
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:267
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
LLT getLLTTy(const MachineRegisterInfo &MRI) const
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:319
The CSE Analysis object.
Definition: CSEInfo.h:69
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:230
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:172
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:211
Abstract class that contains various methods for clients to notify about changes.
virtual void changingInstr(MachineInstr &MI)=0
This instruction is about to be mutated in some way.
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.
const GISelInstProfileBuilder & addNodeIDMachineOperand(const MachineOperand &MO) const
Definition: CSEInfo.cpp:406
constexpr bool isVector() const
Definition: LowLevelType.h:147
constexpr LLT getElementType() const
Returns the vector's element type. Only valid for vector types.
Definition: LowLevelType.h:282
constexpr unsigned getAddressSpace() const
Definition: LowLevelType.h:272
constexpr LLT getScalarType() const
Definition: LowLevelType.h:200
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
void setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II)
Set the insertion point before the specified position.
GISelCSEInfo * getCSEInfo()
MachineBasicBlock::iterator getInsertPt()
Current insertion point for new instructions.
MachineInstrBuilder buildBuildVector(const DstOp &Res, ArrayRef< Register > Ops)
Build and insert Res = G_BUILD_VECTOR Op0, ...
virtual MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val)
Build and insert Res = G_FCONSTANT Val.
MachineInstrBuilder buildInstr(unsigned Opcode)
Build and insert <empty> = Opcode <empty>.
MachineInstrBuilder buildBuildVectorConstant(const DstOp &Res, ArrayRef< APInt > Ops)
Build and insert Res = G_BUILD_VECTOR Op0, ... where each OpN is built with G_CONSTANT.
MachineFunction & getMF()
Getter for the function we currently build.
MachineInstrBuilder buildSplatVector(const DstOp &Res, const SrcOp &Src)
Build and insert Res = G_BUILD_VECTOR with Src replicated to fill the number of elements.
const MachineBasicBlock & getMBB() const
Getter for the basic block we currently build.
const DebugLoc & getDebugLoc()
Get the current instruction's debug location.
MachineRegisterInfo * getMRI()
Getter for MRI.
MachineIRBuilderState & getState()
Getter for the State.
MachineInstrBuilder buildCopy(const DstOp &Res, const SrcOp &Op)
Build and insert Res = COPY Op.
const DataLayout & getDataLayout() const
virtual MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
Register getReg(unsigned Idx) const
Get the register for the operand index.
Representation of each machine instruction.
Definition: MachineInstr.h:68
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:543
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:472
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
static MachineOperand CreateFPImm(const ConstantFP *CFP)
static MachineOperand CreateCImm(const ConstantInt *CI)
bool empty() const
Definition: SmallVector.h:94
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
int64_t getImm() const
Register getReg() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1731
std::optional< APFloat > ConstantFoldIntToFloat(unsigned Opcode, LLT DstTy, Register Src, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:957
std::optional< APFloat > ConstantFoldFPBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:714
std::optional< APInt > ConstantFoldExtOp(unsigned Opcode, const Register Op1, uint64_t Imm, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:916
std::optional< APInt > ConstantFoldBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:645
SmallVector< APInt > ConstantFoldVectorBinop(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Tries to constant fold a vector binop with sources Op1 and Op2.
Definition: Utils.cpp:768
std::optional< SmallVector< unsigned > > ConstantFoldCTLZ(Register Src, const MachineRegisterInfo &MRI)
Tries to constant fold a G_CTLZ operation on Src.
Definition: Utils.cpp:970
GISelChangeObserver * Observer