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