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 CurMBB->splice(Where: CurrPos, Other: CurMBB, From: 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,
69 GISelInstProfileBuilder &B) const {
70 switch (Op.getDstOpKind()) {
71 case DstOp::DstType::Ty_RC:
72 B.addNodeIDRegType(RC: Op.getRegClass());
73 break;
74 case DstOp::DstType::Ty_Reg: {
75 // Regs can have LLT&(RB|RC). If those exist, profile them as well.
76 B.addNodeIDReg(Reg: Op.getReg());
77 break;
78 }
79 default:
80 B.addNodeIDRegType(Ty: Op.getLLTTy(MRI: *getMRI()));
81 break;
82 }
83}
84
85void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
86 GISelInstProfileBuilder &B) const {
87 switch (Op.getSrcOpKind()) {
88 case SrcOp::SrcType::Ty_Imm:
89 B.addNodeIDImmediate(Imm: static_cast<int64_t>(Op.getImm()));
90 break;
91 case SrcOp::SrcType::Ty_Predicate:
92 B.addNodeIDImmediate(Imm: 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(MBB: &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(Ops: DstOps, B);
116 // Then add the SrcOps.
117 profileSrcOps(Ops: SrcOps, B);
118 // Add Flags if passed in.
119 if (Flags)
120 B.addNodeIDFlag(Flag: *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(MI: MIBInstr, InsertPos: 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(Range&: DstOps, P: [](const DstOp &Op) {
137 DstOp::DstType DT = Op.getDstOpKind();
138 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
139 });
140}
141
142MachineInstrBuilder
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(Res: Op.getReg(), Op: MIB.getReg(Idx: 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()) {
158 GISelChangeObserver *Observer = getState().Observer;
159 if (Observer)
160 Observer->changingInstr(MI&: *MIB);
161 MIB->setDebugLoc(
162 DILocation::getMergedLocation(LocA: MIB->getDebugLoc(), LocB: getDebugLoc()));
163 if (Observer)
164 Observer->changedInstr(MI&: *MIB);
165 }
166
167 return MIB;
168}
169
170MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,
171 ArrayRef<DstOp> DstOps,
172 ArrayRef<SrcOp> SrcOps,
173 std::optional<unsigned> Flag) {
174 switch (Opc) {
175 default:
176 break;
177 case TargetOpcode::G_ICMP: {
178 assert(SrcOps.size() == 3 && "Invalid sources");
179 assert(DstOps.size() == 1 && "Invalid dsts");
180 LLT SrcTy = SrcOps[1].getLLTTy(MRI: *getMRI());
181
182 if (std::optional<SmallVector<APInt>> Cst =
183 ConstantFoldICmp(Pred: SrcOps[0].getPredicate(), Op1: SrcOps[1].getReg(),
184 Op2: SrcOps[2].getReg(), MRI: *getMRI())) {
185 if (SrcTy.isVector())
186 return buildBuildVectorConstant(Res: DstOps[0], Ops: *Cst);
187 return buildConstant(Res: DstOps[0], Val: Cst->front());
188 }
189 break;
190 }
191 case TargetOpcode::G_ADD:
192 case TargetOpcode::G_PTR_ADD:
193 case TargetOpcode::G_AND:
194 case TargetOpcode::G_ASHR:
195 case TargetOpcode::G_LSHR:
196 case TargetOpcode::G_MUL:
197 case TargetOpcode::G_OR:
198 case TargetOpcode::G_SHL:
199 case TargetOpcode::G_SUB:
200 case TargetOpcode::G_XOR:
201 case TargetOpcode::G_UDIV:
202 case TargetOpcode::G_SDIV:
203 case TargetOpcode::G_UREM:
204 case TargetOpcode::G_SREM:
205 case TargetOpcode::G_SMIN:
206 case TargetOpcode::G_SMAX:
207 case TargetOpcode::G_UMIN:
208 case TargetOpcode::G_UMAX: {
209 // Try to constant fold these.
210 assert(SrcOps.size() == 2 && "Invalid sources");
211 assert(DstOps.size() == 1 && "Invalid dsts");
212 LLT SrcTy = SrcOps[0].getLLTTy(MRI: *getMRI());
213
214 if (Opc == TargetOpcode::G_PTR_ADD &&
215 getDataLayout().isNonIntegralAddressSpace(AddrSpace: SrcTy.getAddressSpace()))
216 break;
217
218 if (SrcTy.isVector()) {
219 // Try to constant fold vector constants.
220 SmallVector<APInt> VecCst = ConstantFoldVectorBinop(
221 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI());
222 if (!VecCst.empty())
223 return buildBuildVectorConstant(Res: DstOps[0], Ops: VecCst);
224 break;
225 }
226
227 if (std::optional<APInt> Cst = ConstantFoldBinOp(
228 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()))
229 return buildConstant(Res: DstOps[0], Val: *Cst);
230 break;
231 }
232 case TargetOpcode::G_FADD:
233 case TargetOpcode::G_FSUB:
234 case TargetOpcode::G_FMUL:
235 case TargetOpcode::G_FDIV:
236 case TargetOpcode::G_FREM:
237 case TargetOpcode::G_FMINNUM:
238 case TargetOpcode::G_FMAXNUM:
239 case TargetOpcode::G_FMINNUM_IEEE:
240 case TargetOpcode::G_FMAXNUM_IEEE:
241 case TargetOpcode::G_FMINIMUM:
242 case TargetOpcode::G_FMAXIMUM:
243 case TargetOpcode::G_FCOPYSIGN: {
244 // Try to constant fold these.
245 assert(SrcOps.size() == 2 && "Invalid sources");
246 assert(DstOps.size() == 1 && "Invalid dsts");
247 if (std::optional<APFloat> Cst = ConstantFoldFPBinOp(
248 Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()))
249 return buildFConstant(Res: DstOps[0], Val: *Cst);
250 break;
251 }
252 case TargetOpcode::G_SEXT_INREG: {
253 assert(DstOps.size() == 1 && "Invalid dst ops");
254 assert(SrcOps.size() == 2 && "Invalid src ops");
255 const DstOp &Dst = DstOps[0];
256 const SrcOp &Src0 = SrcOps[0];
257 const SrcOp &Src1 = SrcOps[1];
258 if (auto MaybeCst =
259 ConstantFoldExtOp(Opcode: Opc, Op1: Src0.getReg(), Imm: Src1.getImm(), MRI: *getMRI()))
260 return buildConstant(Res: Dst, Val: *MaybeCst);
261 break;
262 }
263 case TargetOpcode::G_SITOFP:
264 case TargetOpcode::G_UITOFP: {
265 // Try to constant fold these.
266 assert(SrcOps.size() == 1 && "Invalid sources");
267 assert(DstOps.size() == 1 && "Invalid dsts");
268 if (std::optional<APFloat> Cst = ConstantFoldIntToFloat(
269 Opcode: Opc, DstTy: DstOps[0].getLLTTy(MRI: *getMRI()), Src: SrcOps[0].getReg(), MRI: *getMRI()))
270 return buildFConstant(Res: DstOps[0], Val: *Cst);
271 break;
272 }
273 case TargetOpcode::G_CTLZ:
274 case TargetOpcode::G_CTTZ: {
275 assert(SrcOps.size() == 1 && "Expected one source");
276 assert(DstOps.size() == 1 && "Expected one dest");
277 std::function<unsigned(APInt)> CB;
278 if (Opc == TargetOpcode::G_CTLZ)
279 CB = [](APInt V) -> unsigned { return V.countl_zero(); };
280 else
281 CB = [](APInt V) -> unsigned { return V.countTrailingZeros(); };
282 auto MaybeCsts = ConstantFoldCountZeros(Src: SrcOps[0].getReg(), MRI: *getMRI(), CB);
283 if (!MaybeCsts)
284 break;
285 if (MaybeCsts->size() == 1)
286 return buildConstant(Res: DstOps[0], Val: (*MaybeCsts)[0]);
287 // This was a vector constant. Build a G_BUILD_VECTOR for them.
288 SmallVector<Register> ConstantRegs;
289 LLT VecTy = DstOps[0].getLLTTy(MRI: *getMRI());
290 for (unsigned Cst : *MaybeCsts)
291 ConstantRegs.emplace_back(
292 Args: buildConstant(Res: VecTy.getScalarType(), Val: Cst).getReg(Idx: 0));
293 return buildBuildVector(Res: DstOps[0], Ops: ConstantRegs);
294 }
295 }
296 bool CanCopy = checkCopyToDefsPossible(DstOps);
297 if (!canPerformCSEForOpc(Opc))
298 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag);
299 // If we can CSE this instruction, but involves generating copies to multiple
300 // regs, give up. This frequently happens to UNMERGEs.
301 if (!CanCopy) {
302 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag);
303 // CSEInfo would have tracked this instruction. Remove it from the temporary
304 // insts.
305 getCSEInfo()->handleRemoveInst(MI: &*MIB);
306 return MIB;
307 }
308 FoldingSetNodeID ID;
309 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
310 void *InsertPos = nullptr;
311 profileEverything(Opc, DstOps, SrcOps, Flags: Flag, B&: ProfBuilder);
312 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
313 if (MIB) {
314 // Handle generating copies here.
315 return generateCopiesIfRequired(DstOps, MIB);
316 }
317 // This instruction does not exist in the CSEInfo. Build it and CSE it.
318 MachineInstrBuilder NewMIB =
319 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag);
320 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
321}
322
323MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
324 const ConstantInt &Val) {
325 constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
326 if (!canPerformCSEForOpc(Opc))
327 return MachineIRBuilder::buildConstant(Res, Val);
328
329 // For vectors, CSE the element only for now.
330 LLT Ty = Res.getLLTTy(MRI: *getMRI());
331 if (Ty.isVector())
332 return buildSplatBuildVector(Res, Src: buildConstant(Res: Ty.getElementType(), Val));
333
334 FoldingSetNodeID ID;
335 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
336 void *InsertPos = nullptr;
337 profileMBBOpcode(B&: ProfBuilder, Opc);
338 profileDstOp(Op: Res, B&: ProfBuilder);
339 ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateCImm(CI: &Val));
340 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
341 if (MIB) {
342 // Handle generating copies here.
343 return generateCopiesIfRequired(DstOps: {Res}, MIB);
344 }
345
346 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
347 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
348}
349
350MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
351 const ConstantFP &Val) {
352 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
353 if (!canPerformCSEForOpc(Opc))
354 return MachineIRBuilder::buildFConstant(Res, Val);
355
356 // For vectors, CSE the element only for now.
357 LLT Ty = Res.getLLTTy(MRI: *getMRI());
358 if (Ty.isVector())
359 return buildSplatBuildVector(Res, Src: buildFConstant(Res: Ty.getElementType(), Val));
360
361 FoldingSetNodeID ID;
362 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
363 void *InsertPos = nullptr;
364 profileMBBOpcode(B&: ProfBuilder, Opc);
365 profileDstOp(Op: Res, B&: ProfBuilder);
366 ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateFPImm(CFP: &Val));
367 MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos);
368 if (MIB) {
369 // Handle generating copies here.
370 return generateCopiesIfRequired(DstOps: {Res}, MIB);
371 }
372 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
373 return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos);
374}
375

source code of llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp