xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp (revision 95b4436e989df29f6368f13832cb13d7cbc52eac) 
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 
20 using namespace llvm;
21 
22 bool 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 
36 MachineInstrBuilder
37 CSEMIRBuilder::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, CurMBB, NodeInsertPos);
44   if (MI) {
45     CSEInfo->countOpcodeHit(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(*CurMBB, std::next(MII));
52     } else if (!dominates(MI, 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(getDebugLoc(), MI->getDebugLoc());
56       MI->setDebugLoc(Loc);
57       CurMBB->splice(CurrPos, CurMBB, MI);
58     }
59     return MachineInstrBuilder(getMF(), MI);
60   }
61   return MachineInstrBuilder();
62 }
63 
64 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
65   const GISelCSEInfo *CSEInfo = getCSEInfo();
66   if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
67     return false;
68   return true;
69 }
70 
71 void CSEMIRBuilder::profileDstOp(const DstOp &Op,
72                                  GISelInstProfileBuilder &B) const {
73   switch (Op.getDstOpKind()) {
74   case DstOp::DstType::Ty_RC: {
75     B.addNodeIDRegType(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(Op.getReg());
81     break;
82   }
83   case DstOp::DstType::Ty_LLT: {
84     B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
85     break;
86   }
87   case DstOp::DstType::Ty_VRegAttrs: {
88     B.addNodeIDRegType(Op.getVRegAttrs());
89     break;
90   }
91   }
92 }
93 
94 void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
95                                  GISelInstProfileBuilder &B) const {
96   switch (Op.getSrcOpKind()) {
97   case SrcOp::SrcType::Ty_Imm:
98     B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm()));
99     break;
100   case SrcOp::SrcType::Ty_Predicate:
101     B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
102     break;
103   default:
104     B.addNodeIDRegType(Op.getReg());
105     break;
106   }
107 }
108 
109 void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
110                                      unsigned Opc) const {
111   // First add the MBB (Local CSE).
112   B.addNodeIDMBB(&getMBB());
113   // Then add the opcode.
114   B.addNodeIDOpcode(Opc);
115 }
116 
117 void 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(DstOps, B);
125   // Then add the SrcOps.
126   profileSrcOps(SrcOps, B);
127   // Add Flags if passed in.
128   if (Flags)
129     B.addNodeIDFlag(*Flags);
130 }
131 
132 MachineInstrBuilder 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(MIBInstr, NodeInsertPos);
138   return MIB;
139 }
140 
141 bool 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(DstOps, [](const DstOp &Op) {
146     DstOp::DstType DT = Op.getDstOpKind();
147     return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
148   });
149 }
150 
151 MachineInstrBuilder
152 CSEMIRBuilder::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(Op.getReg(), MIB.getReg(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(*MIB);
170     MIB->setDebugLoc(
171         DebugLoc::getMergedLocation(MIB->getDebugLoc(), getDebugLoc()));
172     if (Observer)
173       Observer->changedInstr(*MIB);
174   }
175 
176   return MIB;
177 }
178 
179 MachineInstrBuilder 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(*getMRI());
190     LLT DstTy = DstOps[0].getLLTTy(*getMRI());
191     auto BoolExtOp = getBoolExtOp(SrcTy.isVector(), false);
192 
193     if (std::optional<SmallVector<APInt>> Cst = ConstantFoldICmp(
194             SrcOps[0].getPredicate(), SrcOps[1].getReg(), SrcOps[2].getReg(),
195             DstTy.getScalarSizeInBits(), BoolExtOp, *getMRI())) {
196       if (SrcTy.isVector())
197         return buildBuildVectorConstant(DstOps[0], *Cst);
198       return buildConstant(DstOps[0], 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(*getMRI());
224 
225     if (Opc == TargetOpcode::G_PTR_ADD &&
226         getDataLayout().isNonIntegralAddressSpace(SrcTy.getAddressSpace()))
227       break;
228 
229     if (SrcTy.isVector()) {
230       // Try to constant fold vector constants.
231       SmallVector<APInt> VecCst = ConstantFoldVectorBinop(
232           Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI());
233       if (!VecCst.empty())
234         return buildBuildVectorConstant(DstOps[0], VecCst);
235       break;
236     }
237 
238     if (std::optional<APInt> Cst = ConstantFoldBinOp(
239             Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
240       return buildConstant(DstOps[0], *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             Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
260       return buildFConstant(DstOps[0], *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(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
271       return buildConstant(Dst, *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             Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
281       return buildFConstant(DstOps[0], *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(SrcOps[0].getReg(), *getMRI(), CB);
294     if (!MaybeCsts)
295       break;
296     if (MaybeCsts->size() == 1)
297       return buildConstant(DstOps[0], (*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(*getMRI());
301     for (unsigned Cst : *MaybeCsts)
302       ConstantRegs.emplace_back(
303           buildConstant(VecTy.getScalarType(), Cst).getReg(0));
304     return buildBuildVector(DstOps[0], ConstantRegs);
305   }
306   }
307   bool CanCopy = checkCopyToDefsPossible(DstOps);
308   if (!canPerformCSEForOpc(Opc))
309     return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, 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, Flag);
314     // CSEInfo would have tracked this instruction. Remove it from the temporary
315     // insts.
316     getCSEInfo()->handleRemoveInst(&*MIB);
317     return MIB;
318   }
319   FoldingSetNodeID ID;
320   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
321   void *InsertPos = nullptr;
322   profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
323   MachineInstrBuilder MIB = getDominatingInstrForID(ID, 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, Flag);
331   return memoizeMI(NewMIB, InsertPos);
332 }
333 
334 MachineInstrBuilder 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(*getMRI());
342   if (Ty.isVector())
343     return buildSplatBuildVector(Res, buildConstant(Ty.getElementType(), Val));
344 
345   FoldingSetNodeID ID;
346   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
347   void *InsertPos = nullptr;
348   profileMBBOpcode(ProfBuilder, Opc);
349   profileDstOp(Res, ProfBuilder);
350   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
351   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
352   if (MIB) {
353     // Handle generating copies here.
354     return generateCopiesIfRequired({Res}, MIB);
355   }
356 
357   MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
358   return memoizeMI(NewMIB, InsertPos);
359 }
360 
361 MachineInstrBuilder 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(*getMRI());
369   if (Ty.isVector())
370     return buildSplatBuildVector(Res, buildFConstant(Ty.getElementType(), Val));
371 
372   FoldingSetNodeID ID;
373   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
374   void *InsertPos = nullptr;
375   profileMBBOpcode(ProfBuilder, Opc);
376   profileDstOp(Res, ProfBuilder);
377   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
378   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
379   if (MIB) {
380     // Handle generating copies here.
381     return generateCopiesIfRequired({Res}, MIB);
382   }
383   MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
384   return memoizeMI(NewMIB, InsertPos);
385 }
386