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
21 using namespace llvm;
22
dominates(MachineBasicBlock::const_iterator A,MachineBasicBlock::const_iterator B) const23 bool 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
37 MachineInstrBuilder
getDominatingInstrForID(FoldingSetNodeID & ID,void * & NodeInsertPos)38 CSEMIRBuilder::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, CurMBB, NodeInsertPos);
45 if (MI) {
46 CSEInfo->countOpcodeHit(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(*CurMBB, std::next(MII));
53 } else if (!dominates(MI, 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(getDebugLoc().get(),
57 MI->getDebugLoc().get());
58 MI->setDebugLoc(Loc);
59 CurMBB->splice(CurrPos, CurMBB, MI);
60 }
61 return MachineInstrBuilder(getMF(), MI);
62 }
63 return MachineInstrBuilder();
64 }
65
canPerformCSEForOpc(unsigned Opc) const66 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
67 const GISelCSEInfo *CSEInfo = getCSEInfo();
68 if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
69 return false;
70 return true;
71 }
72
profileDstOp(const DstOp & Op,GISelInstProfileBuilder & B) const73 void CSEMIRBuilder::profileDstOp(const DstOp &Op,
74 GISelInstProfileBuilder &B) const {
75 switch (Op.getDstOpKind()) {
76 case DstOp::DstType::Ty_RC:
77 B.addNodeIDRegType(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(Op.getReg());
82 break;
83 }
84 default:
85 B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
86 break;
87 }
88 }
89
profileSrcOp(const SrcOp & Op,GISelInstProfileBuilder & B) const90 void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
91 GISelInstProfileBuilder &B) const {
92 switch (Op.getSrcOpKind()) {
93 case SrcOp::SrcType::Ty_Imm:
94 B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm()));
95 break;
96 case SrcOp::SrcType::Ty_Predicate:
97 B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
98 break;
99 default:
100 B.addNodeIDRegType(Op.getReg());
101 break;
102 }
103 }
104
profileMBBOpcode(GISelInstProfileBuilder & B,unsigned Opc) const105 void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
106 unsigned Opc) const {
107 // First add the MBB (Local CSE).
108 B.addNodeIDMBB(&getMBB());
109 // Then add the opcode.
110 B.addNodeIDOpcode(Opc);
111 }
112
profileEverything(unsigned Opc,ArrayRef<DstOp> DstOps,ArrayRef<SrcOp> SrcOps,std::optional<unsigned> Flags,GISelInstProfileBuilder & B) const113 void 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(DstOps, B);
121 // Then add the SrcOps.
122 profileSrcOps(SrcOps, B);
123 // Add Flags if passed in.
124 if (Flags)
125 B.addNodeIDFlag(*Flags);
126 }
127
memoizeMI(MachineInstrBuilder MIB,void * NodeInsertPos)128 MachineInstrBuilder 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(MIBInstr, NodeInsertPos);
134 return MIB;
135 }
136
checkCopyToDefsPossible(ArrayRef<DstOp> DstOps)137 bool 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(DstOps, [](const DstOp &Op) {
142 DstOp::DstType DT = Op.getDstOpKind();
143 return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
144 });
145 }
146
147 MachineInstrBuilder
generateCopiesIfRequired(ArrayRef<DstOp> DstOps,MachineInstrBuilder & MIB)148 CSEMIRBuilder::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(Op.getReg(), MIB.getReg(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(*MIB);
166 MIB->setDebugLoc(
167 DILocation::getMergedLocation(MIB->getDebugLoc(), getDebugLoc()));
168 if (Observer)
169 Observer->changedInstr(*MIB);
170 }
171
172 return MIB;
173 }
174
buildInstr(unsigned Opc,ArrayRef<DstOp> DstOps,ArrayRef<SrcOp> SrcOps,std::optional<unsigned> Flag)175 MachineInstrBuilder 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(*getMRI());
186
187 if (std::optional<SmallVector<APInt>> Cst =
188 ConstantFoldICmp(SrcOps[0].getPredicate(), SrcOps[1].getReg(),
189 SrcOps[2].getReg(), *getMRI())) {
190 if (SrcTy.isVector())
191 return buildBuildVectorConstant(DstOps[0], *Cst);
192 return buildConstant(DstOps[0], 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(*getMRI());
218
219 if (Opc == TargetOpcode::G_PTR_ADD &&
220 getDataLayout().isNonIntegralAddressSpace(SrcTy.getAddressSpace()))
221 break;
222
223 if (SrcTy.isVector()) {
224 // Try to constant fold vector constants.
225 SmallVector<APInt> VecCst = ConstantFoldVectorBinop(
226 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI());
227 if (!VecCst.empty())
228 return buildBuildVectorConstant(DstOps[0], VecCst);
229 break;
230 }
231
232 if (std::optional<APInt> Cst = ConstantFoldBinOp(
233 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
234 return buildConstant(DstOps[0], *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 Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
254 return buildFConstant(DstOps[0], *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(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
265 return buildConstant(Dst, *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 Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
275 return buildFConstant(DstOps[0], *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(SrcOps[0].getReg(), *getMRI(), CB);
288 if (!MaybeCsts)
289 break;
290 if (MaybeCsts->size() == 1)
291 return buildConstant(DstOps[0], (*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(*getMRI());
295 for (unsigned Cst : *MaybeCsts)
296 ConstantRegs.emplace_back(
297 buildConstant(VecTy.getScalarType(), Cst).getReg(0));
298 return buildBuildVector(DstOps[0], ConstantRegs);
299 }
300 }
301 bool CanCopy = checkCopyToDefsPossible(DstOps);
302 if (!canPerformCSEForOpc(Opc))
303 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, 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, Flag);
308 // CSEInfo would have tracked this instruction. Remove it from the temporary
309 // insts.
310 getCSEInfo()->handleRemoveInst(&*MIB);
311 return MIB;
312 }
313 FoldingSetNodeID ID;
314 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
315 void *InsertPos = nullptr;
316 profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
317 MachineInstrBuilder MIB = getDominatingInstrForID(ID, 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, Flag);
325 return memoizeMI(NewMIB, InsertPos);
326 }
327
buildConstant(const DstOp & Res,const ConstantInt & Val)328 MachineInstrBuilder 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(*getMRI());
336 if (Ty.isVector())
337 return buildSplatBuildVector(Res, buildConstant(Ty.getElementType(), Val));
338
339 FoldingSetNodeID ID;
340 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
341 void *InsertPos = nullptr;
342 profileMBBOpcode(ProfBuilder, Opc);
343 profileDstOp(Res, ProfBuilder);
344 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
345 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
346 if (MIB) {
347 // Handle generating copies here.
348 return generateCopiesIfRequired({Res}, MIB);
349 }
350
351 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
352 return memoizeMI(NewMIB, InsertPos);
353 }
354
buildFConstant(const DstOp & Res,const ConstantFP & Val)355 MachineInstrBuilder 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(*getMRI());
363 if (Ty.isVector())
364 return buildSplatBuildVector(Res, buildFConstant(Ty.getElementType(), Val));
365
366 FoldingSetNodeID ID;
367 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
368 void *InsertPos = nullptr;
369 profileMBBOpcode(ProfBuilder, Opc);
370 profileDstOp(Res, ProfBuilder);
371 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
372 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
373 if (MIB) {
374 // Handle generating copies here.
375 return generateCopiesIfRequired({Res}, MIB);
376 }
377 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
378 return memoizeMI(NewMIB, InsertPos);
379 }
380