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 // Update the spliced machineinstr's debug location by merging it with the
55 // debug location of the instruction at the insertion point.
57 MI->getDebugLoc().get());
58 MI->setDebugLoc(Loc);
59 CurMBB->splice(CurrPos, CurMBB, MI);
60 }
61 return MachineInstrBuilder(getMF(), MI);
62 }
63 return MachineInstrBuilder();
64}
65
66bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
67 const GISelCSEInfo *CSEInfo = getCSEInfo();
68 if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
69 return false;
70 return true;
71}
72
73void CSEMIRBuilder::profileDstOp(const DstOp &Op,
75 switch (Op.getDstOpKind()) {
77 B.addNodeIDRegType(Op.getRegClass());
78 break;
80 // Regs can have LLT&(RB|RC). If those exist, profile them as well.
81 B.addNodeIDReg(Op.getReg());
82 break;
83 }
84 default:
85 B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
86 break;
87 }
88}
89
90void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
92 switch (Op.getSrcOpKind()) {
94 B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm()));
95 break;
97 B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
98 break;
99 default:
100 B.addNodeIDRegType(Op.getReg());
101 break;
102 }
103}
104
105void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
106 unsigned Opc) const {
107 // First add the MBB (Local CSE).
108 B.addNodeIDMBB(&getMBB());
109 // Then add the opcode.
110 B.addNodeIDOpcode(Opc);
111}
112
113void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
114 ArrayRef<SrcOp> SrcOps,
115 std::optional<unsigned> Flags,
116 GISelInstProfileBuilder &B) const {
117
118 profileMBBOpcode(B, Opc);
119 // Then add the DstOps.
120 profileDstOps(DstOps, B);
121 // Then add the SrcOps.
122 profileSrcOps(SrcOps, B);
123 // Add Flags if passed in.
124 if (Flags)
125 B.addNodeIDFlag(*Flags);
126}
127
128MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
129 void *NodeInsertPos) {
130 assert(canPerformCSEForOpc(MIB->getOpcode()) &&
131 "Attempting to CSE illegal op");
132 MachineInstr *MIBInstr = MIB;
133 getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);
134 return MIB;
135}
136
137bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
138 if (DstOps.size() == 1)
139 return true; // always possible to emit copy to just 1 vreg.
140
141 return llvm::all_of(DstOps, [](const DstOp &Op) {
142 DstOp::DstType DT = Op.getDstOpKind();
143 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
144 });
145}
146
148CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
149 MachineInstrBuilder &MIB) {
150 assert(checkCopyToDefsPossible(DstOps) &&
151 "Impossible return a single MIB with copies to multiple defs");
152 if (DstOps.size() == 1) {
153 const DstOp &Op = DstOps[0];
154 if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
155 return buildCopy(Op.getReg(), MIB.getReg(0));
156 }
157
158 // If we didn't generate a copy then we're re-using an existing node directly
159 // instead of emitting any code. Merge the debug location we wanted to emit
160 // into the instruction we're CSE'ing with. Debug locations arent part of the
161 // profile so we don't need to recompute it.
162 if (getDebugLoc()) {
164 if (Observer)
165 Observer->changingInstr(*MIB);
166 MIB->setDebugLoc(
168 if (Observer)
169 Observer->changedInstr(*MIB);
170 }
171
172 return MIB;
173}
174
176 ArrayRef<DstOp> DstOps,
177 ArrayRef<SrcOp> SrcOps,
178 std::optional<unsigned> Flag) {
179 switch (Opc) {
180 default:
181 break;
182 case TargetOpcode::G_ICMP: {
183 assert(SrcOps.size() == 3 && "Invalid sources");
184 assert(DstOps.size() == 1 && "Invalid dsts");
185 LLT SrcTy = SrcOps[1].getLLTTy(*getMRI());
186
187 if (std::optional<SmallVector<APInt>> Cst =
188 ConstantFoldICmp(SrcOps[0].getPredicate(), SrcOps[1].getReg(),
189 SrcOps[2].getReg(), *getMRI())) {
190 if (SrcTy.isVector())
191 return buildBuildVectorConstant(DstOps[0], *Cst);
192 return buildConstant(DstOps[0], Cst->front());
193 }
194 break;
195 }
196 case TargetOpcode::G_ADD:
197 case TargetOpcode::G_PTR_ADD:
198 case TargetOpcode::G_AND:
199 case TargetOpcode::G_ASHR:
200 case TargetOpcode::G_LSHR:
201 case TargetOpcode::G_MUL:
202 case TargetOpcode::G_OR:
203 case TargetOpcode::G_SHL:
204 case TargetOpcode::G_SUB:
205 case TargetOpcode::G_XOR:
206 case TargetOpcode::G_UDIV:
207 case TargetOpcode::G_SDIV:
208 case TargetOpcode::G_UREM:
209 case TargetOpcode::G_SREM:
210 case TargetOpcode::G_SMIN:
211 case TargetOpcode::G_SMAX:
212 case TargetOpcode::G_UMIN:
213 case TargetOpcode::G_UMAX: {
214 // Try to constant fold these.
215 assert(SrcOps.size() == 2 && "Invalid sources");
216 assert(DstOps.size() == 1 && "Invalid dsts");
217 LLT SrcTy = SrcOps[0].getLLTTy(*getMRI());
218
219 if (Opc == TargetOpcode::G_PTR_ADD &&
220 getDataLayout().isNonIntegralAddressSpace(SrcTy.getAddressSpace()))
221 break;
222
223 if (SrcTy.isVector()) {
224 // Try to constant fold vector constants.
226 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI());
227 if (!VecCst.empty())
228 return buildBuildVectorConstant(DstOps[0], VecCst);
229 break;
230 }
231
232 if (std::optional<APInt> Cst = ConstantFoldBinOp(
233 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
234 return buildConstant(DstOps[0], *Cst);
235 break;
236 }
237 case TargetOpcode::G_FADD:
238 case TargetOpcode::G_FSUB:
239 case TargetOpcode::G_FMUL:
240 case TargetOpcode::G_FDIV:
241 case TargetOpcode::G_FREM:
242 case TargetOpcode::G_FMINNUM:
243 case TargetOpcode::G_FMAXNUM:
244 case TargetOpcode::G_FMINNUM_IEEE:
245 case TargetOpcode::G_FMAXNUM_IEEE:
246 case TargetOpcode::G_FMINIMUM:
247 case TargetOpcode::G_FMAXIMUM:
248 case TargetOpcode::G_FCOPYSIGN: {
249 // Try to constant fold these.
250 assert(SrcOps.size() == 2 && "Invalid sources");
251 assert(DstOps.size() == 1 && "Invalid dsts");
252 if (std::optional<APFloat> Cst = ConstantFoldFPBinOp(
253 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
254 return buildFConstant(DstOps[0], *Cst);
255 break;
256 }
257 case TargetOpcode::G_SEXT_INREG: {
258 assert(DstOps.size() == 1 && "Invalid dst ops");
259 assert(SrcOps.size() == 2 && "Invalid src ops");
260 const DstOp &Dst = DstOps[0];
261 const SrcOp &Src0 = SrcOps[0];
262 const SrcOp &Src1 = SrcOps[1];
263 if (auto MaybeCst =
264 ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
265 return buildConstant(Dst, *MaybeCst);
266 break;
267 }
268 case TargetOpcode::G_SITOFP:
269 case TargetOpcode::G_UITOFP: {
270 // Try to constant fold these.
271 assert(SrcOps.size() == 1 && "Invalid sources");
272 assert(DstOps.size() == 1 && "Invalid dsts");
273 if (std::optional<APFloat> Cst = ConstantFoldIntToFloat(
274 Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
275 return buildFConstant(DstOps[0], *Cst);
276 break;
277 }
278 case TargetOpcode::G_CTLZ:
279 case TargetOpcode::G_CTTZ: {
280 assert(SrcOps.size() == 1 && "Expected one source");
281 assert(DstOps.size() == 1 && "Expected one dest");
282 std::function<unsigned(APInt)> CB;
283 if (Opc == TargetOpcode::G_CTLZ)
284 CB = [](APInt V) -> unsigned { return V.countl_zero(); };
285 else
286 CB = [](APInt V) -> unsigned { return V.countTrailingZeros(); };
287 auto MaybeCsts = ConstantFoldCountZeros(SrcOps[0].getReg(), *getMRI(), CB);
288 if (!MaybeCsts)
289 break;
290 if (MaybeCsts->size() == 1)
291 return buildConstant(DstOps[0], (*MaybeCsts)[0]);
292 // This was a vector constant. Build a G_BUILD_VECTOR for them.
293 SmallVector<Register> ConstantRegs;
294 LLT VecTy = DstOps[0].getLLTTy(*getMRI());
295 for (unsigned Cst : *MaybeCsts)
296 ConstantRegs.emplace_back(
297 buildConstant(VecTy.getScalarType(), Cst).getReg(0));
298 return buildBuildVector(DstOps[0], ConstantRegs);
299 }
300 }
301 bool CanCopy = checkCopyToDefsPossible(DstOps);
302 if (!canPerformCSEForOpc(Opc))
303 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
304 // If we can CSE this instruction, but involves generating copies to multiple
305 // regs, give up. This frequently happens to UNMERGEs.
306 if (!CanCopy) {
307 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
308 // CSEInfo would have tracked this instruction. Remove it from the temporary
309 // insts.
311 return MIB;
312 }
314 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
315 void *InsertPos = nullptr;
316 profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
317 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
318 if (MIB) {
319 // Handle generating copies here.
320 return generateCopiesIfRequired(DstOps, MIB);
321 }
322 // This instruction does not exist in the CSEInfo. Build it and CSE it.
323 MachineInstrBuilder NewMIB =
324 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
325 return memoizeMI(NewMIB, InsertPos);
326}
327
329 const ConstantInt &Val) {
330 constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
331 if (!canPerformCSEForOpc(Opc))
332 return MachineIRBuilder::buildConstant(Res, Val);
333
334 // For vectors, CSE the element only for now.
335 LLT Ty = Res.getLLTTy(*getMRI());
336 if (Ty.isVector())
337 return buildSplatBuildVector(Res, buildConstant(Ty.getElementType(), Val));
338
340 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
341 void *InsertPos = nullptr;
342 profileMBBOpcode(ProfBuilder, Opc);
343 profileDstOp(Res, ProfBuilder);
345 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
346 if (MIB) {
347 // Handle generating copies here.
348 return generateCopiesIfRequired({Res}, MIB);
349 }
350
352 return memoizeMI(NewMIB, InsertPos);
353}
354
356 const ConstantFP &Val) {
357 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
358 if (!canPerformCSEForOpc(Opc))
359 return MachineIRBuilder::buildFConstant(Res, Val);
360
361 // For vectors, CSE the element only for now.
362 LLT Ty = Res.getLLTTy(*getMRI());
363 if (Ty.isVector())
365
367 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
368 void *InsertPos = nullptr;
369 profileMBBOpcode(ProfBuilder, Opc);
370 profileDstOp(Res, ProfBuilder);
372 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
373 if (MIB) {
374 // Handle generating copies here.
375 return generateCopiesIfRequired({Res}, MIB);
376 }
378 return memoizeMI(NewMIB, InsertPos);
379}
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())
Class for arbitrary precision integers.
Definition: APInt.h:77
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:168
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:269
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
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:148
constexpr LLT getElementType() const
Returns the vector's element type. Only valid for vector types.
Definition: LowLevelType.h:290
constexpr unsigned getAddressSpace() const
Definition: LowLevelType.h:280
constexpr LLT getScalarType() const
Definition: LowLevelType.h:208
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 buildSplatBuildVector(const DstOp &Res, const SrcOp &Src)
Build and insert Res = G_BUILD_VECTOR with Src replicated to fill the number of elements.
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.
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:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:566
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:495
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:1722
std::optional< APFloat > ConstantFoldIntToFloat(unsigned Opcode, LLT DstTy, Register Src, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:971
std::optional< APFloat > ConstantFoldFPBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:727
std::optional< SmallVector< unsigned > > ConstantFoldCountZeros(Register Src, const MachineRegisterInfo &MRI, std::function< unsigned(APInt)> CB)
Tries to constant fold a counting-zero operation (G_CTLZ or G_CTTZ) on Src.
Definition: Utils.cpp:984
std::optional< APInt > ConstantFoldExtOp(unsigned Opcode, const Register Op1, uint64_t Imm, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:930
std::optional< APInt > ConstantFoldBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:658
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
std::optional< SmallVector< APInt > > ConstantFoldICmp(unsigned Pred, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:1016
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:781
GISelChangeObserver * Observer