LLVM 17.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:163
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:256
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
LLT getLLTTy(const MachineRegisterInfo &MRI) const
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:318
The CSE Analysis object.
Definition: CSEInfo.h:69
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:226
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:403
constexpr bool isVector() const
constexpr LLT getElementType() const
Returns the vector's element type. Only valid for vector types.
constexpr unsigned getAddressSpace() const
constexpr LLT getScalarType() const
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:516
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:445
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:941
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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:1735
std::optional< APFloat > ConstantFoldIntToFloat(unsigned Opcode, LLT DstTy, Register Src, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:780
std::optional< APFloat > ConstantFoldFPBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:560
std::optional< APInt > ConstantFoldExtOp(unsigned Opcode, const Register Op1, uint64_t Imm, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:762
std::optional< APInt > ConstantFoldBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:494
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:614
std::optional< SmallVector< unsigned > > ConstantFoldCTLZ(Register Src, const MachineRegisterInfo &MRI)
Tries to constant fold a G_CTLZ operation on Src.
Definition: Utils.cpp:793
GISelChangeObserver * Observer