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#include "llvm/IR/DebugInfoMetadata.h"
20
21using namespace llvm;
22
23bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
24 MachineBasicBlock::const_iterator B) const {
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();
31 MachineBasicBlock::const_iterator I = BBA->begin();
32 for (; &*I != A && &*I != B; ++I)
33 ;
34 return &*I == A;
35}
36
37MachineInstrBuilder
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();
43 MachineInstr *MI =
44 CSEInfo->getMachineInstrIfExists(ID, MBB: CurMBB, InsertPos&: NodeInsertPos);
45 if (MI) {
46 CSEInfo->countOpcodeHit(Opc: MI->getOpcode());
47 auto CurrPos = getInsertPt();
48 auto MII = MachineBasicBlock::iterator(MI);
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(MBB&: *CurMBB, II: std::next(x: MII));
53 } else if (!dominates(A: MI, B: CurrPos)) {
54 // Update the spliced machineinstr's debug location by merging it with the
55 // debug location of the instruction at the insertion point.
56 auto *Loc = DILocation::getMergedLocation(LocA: getDebugLoc().get(),
57 LocB: MI->getDebugLoc().get());
58 MI->setDebugLoc(Loc);
59 CurMBB->splice(Where: CurrPos, Other: CurMBB, From: 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,
74 GISelInstProfileBuilder &B) const {
75 switch (Op.getDstOpKind()) {
76 case DstOp::DstType::Ty_RC:
77 B.addNodeIDRegType(RC: Op.getRegClass());
78 break;
79 case DstOp::DstType::Ty_Reg: {
80 // Regs can have LLT&(RB|RC). If those exist, profile them as well.
81 B.addNodeIDReg(Reg: Op.getReg());
82 break;
83 }
84 default:
85 B.addNodeIDRegType(Ty: Op.getLLTTy(MRI: *getMRI()));
86 break;
87 }
88}
89
90void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
91 GISelInstProfileBuilder &B) const {
92 switch (Op.getSrcOpKind()) {
93 case SrcOp::SrcType::Ty_Imm:
94 B.addNodeIDImmediate(Imm: static_cast<int64_t>(Op.getImm()));
95 break;
96 case SrcOp::SrcType::Ty_Predicate:
97 B.addNodeIDImmediate(Imm: 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(MBB: &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(Ops: DstOps, B);
121 // Then add the SrcOps.
122 profileSrcOps(Ops: SrcOps, B);
123 // Add Flags if passed in.
124 if (Flags)
125 B.addNodeIDFlag(Flag: *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(MI: MIBInstr, InsertPos: 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(Range&: DstOps, P: [](const DstOp &Op) {
142 DstOp::DstType DT = Op.getDstOpKind();
143 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
144 });
145}
146
147MachineInstrBuilder
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(Res: Op.getReg(), Op: MIB.getReg(Idx: 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()) {
163 GISelChangeObserver *Observer = getState().Observer;
164 if (Observer)
165 Observer->changingInstr(MI&: *MIB);
166 MIB->setDebugLoc(
167 DILocation::getMergedLocation(LocA: MIB->getDebugLoc(), LocB: getDebugLoc()));
168 if (Observer)
169 Observer->changedInstr(MI&: *MIB);
170 }
171
172 return MIB;
173}
174
175MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,
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(MRI: *getMRI());
186
187 if (std::optional<SmallVector<APInt>> Cst =
188 ConstantFoldICmp(Pred: SrcOps[0].getPredicate(), Op1: SrcOps[1].getReg(),
189 Op2: SrcOps[2].getReg(), MRI: *getMRI())) {
190 if (SrcTy.isVector())
191 return buildBuildVectorConstant(Res: DstOps[0], Ops: *Cst);
192 return buildConstant(Res: DstOps[0], Val: 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(MRI: *getMRI());
218
219 if (Opc == TargetOpcode::G_PTR_ADD &&
220 getDataLayout().isNonIntegralAddressSpace(AddrSpace: SrcTy.getAddressSpace()))
221 break;
222
223 if (SrcTy.isVector()) {
224 // Try to constant fold vector constants.
225 SmallVector<APInt> VecCst = ConstantFoldVectorBinop(
226 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI());
227 if (!VecCst.empty())
228 return buildBuildVectorConstant(Res: DstOps[0], Ops: VecCst);
229 break;
230 }
231
232 if (std::optional<APInt> Cst = ConstantFoldBinOp(
233 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()))
234 return buildConstant(Res: DstOps[0], Val: *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 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()))
254 return buildFConstant(Res: DstOps[0], Val: *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(Opcode: Opc, Op1: Src0.getReg(), Imm: Src1.getImm(), MRI: *getMRI()))
265 return buildConstant(Res: Dst, Val: *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 Opcode: Opc, DstTy: DstOps[0].getLLTTy(MRI: *getMRI()), Src: SrcOps[0].getReg(), MRI: *getMRI()))
275 return buildFConstant(Res: DstOps[0], Val: *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(Src: SrcOps[0].getReg(), MRI: *getMRI(), CB);
288 if (!MaybeCsts)
289 break;
290 if (MaybeCsts->size() == 1)
291 return buildConstant(Res: DstOps[0], Val: (*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(MRI: *getMRI());
295 for (unsigned Cst : *MaybeCsts)
296 ConstantRegs.emplace_back(
297 Args: buildConstant(Res: VecTy.getScalarType(), Val: Cst).getReg(Idx: 0));
298 return buildBuildVector(Res: DstOps[0], Ops: ConstantRegs);
299 }
300 }
301 bool CanCopy = checkCopyToDefsPossible(DstOps);
302 if (!canPerformCSEForOpc(Opc))
303 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: 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, Flags: Flag);
308 // CSEInfo would have tracked this instruction. Remove it from the temporary
309 // insts.
310 getCSEInfo()->handleRemoveInst(MI: &*MIB);
311 return MIB;
312 }
313 FoldingSetNodeID ID;
314 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
315 void *InsertPos = nullptr;
316 profileEverything(Opc, DstOps, SrcOps, Flags: Flag, B&: ProfBuilder);
317 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: 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, Flags: Flag);
325 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
326}
327
328MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
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(MRI: *getMRI());
336 if (Ty.isVector())
337 return buildSplatBuildVector(Res, Src: buildConstant(Res: Ty.getElementType(), Val));
338
339 FoldingSetNodeID ID;
340 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
341 void *InsertPos = nullptr;
342 profileMBBOpcode(B&: ProfBuilder, Opc);
343 profileDstOp(Op: Res, B&: ProfBuilder);
344 ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateCImm(CI: &Val));
345 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
346 if (MIB) {
347 // Handle generating copies here.
348 return generateCopiesIfRequired(DstOps: {Res}, MIB);
349 }
350
351 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
352 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
353}
354
355MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
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(MRI: *getMRI());
363 if (Ty.isVector())
364 return buildSplatBuildVector(Res, Src: buildFConstant(Res: Ty.getElementType(), Val));
365
366 FoldingSetNodeID ID;
367 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
368 void *InsertPos = nullptr;
369 profileMBBOpcode(B&: ProfBuilder, Opc);
370 profileDstOp(Op: Res, B&: ProfBuilder);
371 ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateFPImm(CFP: &Val));
372 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
373 if (MIB) {
374 // Handle generating copies here.
375 return generateCopiesIfRequired(DstOps: {Res}, MIB);
376 }
377 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
378 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
379}
380