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
14#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
15#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
16#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
17#include "llvm/CodeGen/GlobalISel/Utils.h"
18#include "llvm/CodeGen/MachineInstrBuilder.h"
19
20using namespace llvm;
21
22bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
23 MachineBasicBlock::const_iterator B) const {
24 auto MBBEnd = getMBB().end();
25 if (B == MBBEnd)
26 return true;
27 assert(A->getParent() == B->getParent() &&
28 "Iterators should be in same block");
29 const MachineBasicBlock *BBA = A->getParent();
30 MachineBasicBlock::const_iterator I = BBA->begin();
31 for (; &*I != A && &*I != B; ++I)
32 ;
33 return &*I == A;
34}
35
36MachineInstrBuilder
37CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
38 void *&NodeInsertPos) {
39 GISelCSEInfo *CSEInfo = getCSEInfo();
40 assert(CSEInfo && "Can't get here without setting CSEInfo");
41 MachineBasicBlock *CurMBB = &getMBB();
42 MachineInstr *MI =
43 CSEInfo->getMachineInstrIfExists(ID, MBB: CurMBB, InsertPos&: NodeInsertPos);
44 if (MI) {
45 CSEInfo->countOpcodeHit(Opc: MI->getOpcode());
46 auto CurrPos = getInsertPt();
47 auto MII = MachineBasicBlock::iterator(MI);
48 if (MII == CurrPos) {
49 // Move the insert point ahead of the instruction so any future uses of
50 // this builder will have the def ready.
51 setInsertPt(MBB&: *CurMBB, II: std::next(x: MII));
52 } else if (!dominates(A: MI, B: CurrPos)) {
53 // Update the spliced machineinstr's debug location by merging it with the
54 // debug location of the instruction at the insertion point.
55 auto Loc = DebugLoc::getMergedLocation(LocA: getDebugLoc(), LocB: MI->getDebugLoc());
56 MI->setDebugLoc(Loc);
57 CurMBB->splice(Where: CurrPos, Other: CurMBB, From: MI);
58 }
59 return MachineInstrBuilder(getMF(), MI);
60 }
61 return MachineInstrBuilder();
62}
63
64bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
65 const GISelCSEInfo *CSEInfo = getCSEInfo();
66 if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
67 return false;
68 return true;
69}
70
71void CSEMIRBuilder::profileDstOp(const DstOp &Op,
72 GISelInstProfileBuilder &B) const {
73 switch (Op.getDstOpKind()) {
74 case DstOp::DstType::Ty_RC: {
75 B.addNodeIDRegType(RC: Op.getRegClass());
76 break;
77 }
78 case DstOp::DstType::Ty_Reg: {
79 // Regs can have LLT&(RB|RC). If those exist, profile them as well.
80 B.addNodeIDReg(Reg: Op.getReg());
81 break;
82 }
83 case DstOp::DstType::Ty_LLT: {
84 B.addNodeIDRegType(Ty: Op.getLLTTy(MRI: *getMRI()));
85 break;
86 }
87 case DstOp::DstType::Ty_VRegAttrs: {
88 B.addNodeIDRegType(Op.getVRegAttrs());
89 break;
90 }
91 }
92}
93
94void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
95 GISelInstProfileBuilder &B) const {
96 switch (Op.getSrcOpKind()) {
97 case SrcOp::SrcType::Ty_Imm:
98 B.addNodeIDImmediate(Imm: static_cast<int64_t>(Op.getImm()));
99 break;
100 case SrcOp::SrcType::Ty_Predicate:
101 B.addNodeIDImmediate(Imm: static_cast<int64_t>(Op.getPredicate()));
102 break;
103 default:
104 B.addNodeIDRegType(Op.getReg());
105 break;
106 }
107}
108
109void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
110 unsigned Opc) const {
111 // First add the MBB (Local CSE).
112 B.addNodeIDMBB(MBB: &getMBB());
113 // Then add the opcode.
114 B.addNodeIDOpcode(Opc);
115}
116
117void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
118 ArrayRef<SrcOp> SrcOps,
119 std::optional<unsigned> Flags,
120 GISelInstProfileBuilder &B) const {
121
122 profileMBBOpcode(B, Opc);
123 // Then add the DstOps.
124 profileDstOps(Ops: DstOps, B);
125 // Then add the SrcOps.
126 profileSrcOps(Ops: SrcOps, B);
127 // Add Flags if passed in.
128 if (Flags)
129 B.addNodeIDFlag(Flag: *Flags);
130}
131
132MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
133 void *NodeInsertPos) {
134 assert(canPerformCSEForOpc(MIB->getOpcode()) &&
135 "Attempting to CSE illegal op");
136 MachineInstr *MIBInstr = MIB;
137 getCSEInfo()->insertInstr(MI: MIBInstr, InsertPos: NodeInsertPos);
138 return MIB;
139}
140
141bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
142 if (DstOps.size() == 1)
143 return true; // always possible to emit copy to just 1 vreg.
144
145 return llvm::all_of(Range&: DstOps, P: [](const DstOp &Op) {
146 DstOp::DstType DT = Op.getDstOpKind();
147 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
148 });
149}
150
151MachineInstrBuilder
152CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
153 MachineInstrBuilder &MIB) {
154 assert(checkCopyToDefsPossible(DstOps) &&
155 "Impossible return a single MIB with copies to multiple defs");
156 if (DstOps.size() == 1) {
157 const DstOp &Op = DstOps[0];
158 if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
159 return buildCopy(Res: Op.getReg(), Op: MIB.getReg(Idx: 0));
160 }
161
162 // If we didn't generate a copy then we're re-using an existing node directly
163 // instead of emitting any code. Merge the debug location we wanted to emit
164 // into the instruction we're CSE'ing with. Debug locations arent part of the
165 // profile so we don't need to recompute it.
166 if (getDebugLoc()) {
167 GISelChangeObserver *Observer = getState().Observer;
168 if (Observer)
169 Observer->changingInstr(MI&: *MIB);
170 MIB->setDebugLoc(
171 DebugLoc::getMergedLocation(LocA: MIB->getDebugLoc(), LocB: getDebugLoc()));
172 if (Observer)
173 Observer->changedInstr(MI&: *MIB);
174 }
175
176 return MIB;
177}
178
179MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,
180 ArrayRef<DstOp> DstOps,
181 ArrayRef<SrcOp> SrcOps,
182 std::optional<unsigned> Flag) {
183 switch (Opc) {
184 default:
185 break;
186 case TargetOpcode::G_ICMP: {
187 assert(SrcOps.size() == 3 && "Invalid sources");
188 assert(DstOps.size() == 1 && "Invalid dsts");
189 LLT SrcTy = SrcOps[1].getLLTTy(MRI: *getMRI());
190 LLT DstTy = DstOps[0].getLLTTy(MRI: *getMRI());
191 auto BoolExtOp = getBoolExtOp(IsVec: SrcTy.isVector(), IsFP: false);
192
193 if (std::optional<SmallVector<APInt>> Cst = ConstantFoldICmp(
194 Pred: SrcOps[0].getPredicate(), Op1: SrcOps[1].getReg(), Op2: SrcOps[2].getReg(),
195 DstScalarSizeInBits: DstTy.getScalarSizeInBits(), ExtOp: BoolExtOp, MRI: *getMRI())) {
196 if (SrcTy.isVector())
197 return buildBuildVectorConstant(Res: DstOps[0], Ops: *Cst);
198 return buildConstant(Res: DstOps[0], Val: Cst->front());
199 }
200 break;
201 }
202 case TargetOpcode::G_ADD:
203 case TargetOpcode::G_PTR_ADD:
204 case TargetOpcode::G_AND:
205 case TargetOpcode::G_ASHR:
206 case TargetOpcode::G_LSHR:
207 case TargetOpcode::G_MUL:
208 case TargetOpcode::G_OR:
209 case TargetOpcode::G_SHL:
210 case TargetOpcode::G_SUB:
211 case TargetOpcode::G_XOR:
212 case TargetOpcode::G_UDIV:
213 case TargetOpcode::G_SDIV:
214 case TargetOpcode::G_UREM:
215 case TargetOpcode::G_SREM:
216 case TargetOpcode::G_SMIN:
217 case TargetOpcode::G_SMAX:
218 case TargetOpcode::G_UMIN:
219 case TargetOpcode::G_UMAX: {
220 // Try to constant fold these.
221 assert(SrcOps.size() == 2 && "Invalid sources");
222 assert(DstOps.size() == 1 && "Invalid dsts");
223 LLT SrcTy = SrcOps[0].getLLTTy(MRI: *getMRI());
224
225 if (Opc == TargetOpcode::G_PTR_ADD &&
226 getDataLayout().isNonIntegralAddressSpace(AddrSpace: SrcTy.getAddressSpace()))
227 break;
228
229 if (SrcTy.isVector()) {
230 // Try to constant fold vector constants.
231 SmallVector<APInt> VecCst = ConstantFoldVectorBinop(
232 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI());
233 if (!VecCst.empty())
234 return buildBuildVectorConstant(Res: DstOps[0], Ops: VecCst);
235 break;
236 }
237
238 if (std::optional<APInt> Cst = ConstantFoldBinOp(
239 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()))
240 return buildConstant(Res: DstOps[0], Val: *Cst);
241 break;
242 }
243 case TargetOpcode::G_FADD:
244 case TargetOpcode::G_FSUB:
245 case TargetOpcode::G_FMUL:
246 case TargetOpcode::G_FDIV:
247 case TargetOpcode::G_FREM:
248 case TargetOpcode::G_FMINNUM:
249 case TargetOpcode::G_FMAXNUM:
250 case TargetOpcode::G_FMINNUM_IEEE:
251 case TargetOpcode::G_FMAXNUM_IEEE:
252 case TargetOpcode::G_FMINIMUM:
253 case TargetOpcode::G_FMAXIMUM:
254 case TargetOpcode::G_FCOPYSIGN: {
255 // Try to constant fold these.
256 assert(SrcOps.size() == 2 && "Invalid sources");
257 assert(DstOps.size() == 1 && "Invalid dsts");
258 if (std::optional<APFloat> Cst = ConstantFoldFPBinOp(
259 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()))
260 return buildFConstant(Res: DstOps[0], Val: *Cst);
261 break;
262 }
263 case TargetOpcode::G_SEXT_INREG: {
264 assert(DstOps.size() == 1 && "Invalid dst ops");
265 assert(SrcOps.size() == 2 && "Invalid src ops");
266 const DstOp &Dst = DstOps[0];
267 const SrcOp &Src0 = SrcOps[0];
268 const SrcOp &Src1 = SrcOps[1];
269 if (auto MaybeCst =
270 ConstantFoldExtOp(Opcode: Opc, Op1: Src0.getReg(), Imm: Src1.getImm(), MRI: *getMRI()))
271 return buildConstant(Res: Dst, Val: *MaybeCst);
272 break;
273 }
274 case TargetOpcode::G_SITOFP:
275 case TargetOpcode::G_UITOFP: {
276 // Try to constant fold these.
277 assert(SrcOps.size() == 1 && "Invalid sources");
278 assert(DstOps.size() == 1 && "Invalid dsts");
279 if (std::optional<APFloat> Cst = ConstantFoldIntToFloat(
280 Opcode: Opc, DstTy: DstOps[0].getLLTTy(MRI: *getMRI()), Src: SrcOps[0].getReg(), MRI: *getMRI()))
281 return buildFConstant(Res: DstOps[0], Val: *Cst);
282 break;
283 }
284 case TargetOpcode::G_CTLZ:
285 case TargetOpcode::G_CTTZ: {
286 assert(SrcOps.size() == 1 && "Expected one source");
287 assert(DstOps.size() == 1 && "Expected one dest");
288 std::function<unsigned(APInt)> CB;
289 if (Opc == TargetOpcode::G_CTLZ)
290 CB = [](APInt V) -> unsigned { return V.countl_zero(); };
291 else
292 CB = [](APInt V) -> unsigned { return V.countTrailingZeros(); };
293 auto MaybeCsts = ConstantFoldCountZeros(Src: SrcOps[0].getReg(), MRI: *getMRI(), CB);
294 if (!MaybeCsts)
295 break;
296 if (MaybeCsts->size() == 1)
297 return buildConstant(Res: DstOps[0], Val: (*MaybeCsts)[0]);
298 // This was a vector constant. Build a G_BUILD_VECTOR for them.
299 SmallVector<Register> ConstantRegs;
300 LLT VecTy = DstOps[0].getLLTTy(MRI: *getMRI());
301 for (unsigned Cst : *MaybeCsts)
302 ConstantRegs.emplace_back(
303 Args: buildConstant(Res: VecTy.getScalarType(), Val: Cst).getReg(Idx: 0));
304 return buildBuildVector(Res: DstOps[0], Ops: ConstantRegs);
305 }
306 }
307 bool CanCopy = checkCopyToDefsPossible(DstOps);
308 if (!canPerformCSEForOpc(Opc))
309 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag);
310 // If we can CSE this instruction, but involves generating copies to multiple
311 // regs, give up. This frequently happens to UNMERGEs.
312 if (!CanCopy) {
313 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag);
314 // CSEInfo would have tracked this instruction. Remove it from the temporary
315 // insts.
316 getCSEInfo()->handleRemoveInst(MI: &*MIB);
317 return MIB;
318 }
319 FoldingSetNodeID ID;
320 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
321 void *InsertPos = nullptr;
322 profileEverything(Opc, DstOps, SrcOps, Flags: Flag, B&: ProfBuilder);
323 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
324 if (MIB) {
325 // Handle generating copies here.
326 return generateCopiesIfRequired(DstOps, MIB);
327 }
328 // This instruction does not exist in the CSEInfo. Build it and CSE it.
329 MachineInstrBuilder NewMIB =
330 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag);
331 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
332}
333
334MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
335 const ConstantInt &Val) {
336 constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
337 if (!canPerformCSEForOpc(Opc))
338 return MachineIRBuilder::buildConstant(Res, Val);
339
340 // For vectors, CSE the element only for now.
341 LLT Ty = Res.getLLTTy(MRI: *getMRI());
342 if (Ty.isVector())
343 return buildSplatBuildVector(Res, Src: buildConstant(Res: Ty.getElementType(), Val));
344
345 FoldingSetNodeID ID;
346 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
347 void *InsertPos = nullptr;
348 profileMBBOpcode(B&: ProfBuilder, Opc);
349 profileDstOp(Op: Res, B&: ProfBuilder);
350 ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateCImm(CI: &Val));
351 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
352 if (MIB) {
353 // Handle generating copies here.
354 return generateCopiesIfRequired(DstOps: {Res}, MIB);
355 }
356
357 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
358 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
359}
360
361MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
362 const ConstantFP &Val) {
363 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
364 if (!canPerformCSEForOpc(Opc))
365 return MachineIRBuilder::buildFConstant(Res, Val);
366
367 // For vectors, CSE the element only for now.
368 LLT Ty = Res.getLLTTy(MRI: *getMRI());
369 if (Ty.isVector())
370 return buildSplatBuildVector(Res, Src: buildFConstant(Res: Ty.getElementType(), Val));
371
372 FoldingSetNodeID ID;
373 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
374 void *InsertPos = nullptr;
375 profileMBBOpcode(B&: ProfBuilder, Opc);
376 profileDstOp(Op: Res, B&: ProfBuilder);
377 ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateFPImm(CFP: &Val));
378 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
379 if (MIB) {
380 // Handle generating copies here.
381 return generateCopiesIfRequired(DstOps: {Res}, MIB);
382 }
383 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
384 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
385}
386