xref: /llvm-project/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp (revision 3a106e5b2cd9f4073b2961b991ebaeee96786309) 
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 
23 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
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       CurMBB->splice(CurrPos, CurMBB, MI);
55     }
56     return MachineInstrBuilder(getMF(), MI);
57   }
58   return MachineInstrBuilder();
59 }
60 
61 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
62   const GISelCSEInfo *CSEInfo = getCSEInfo();
63   if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
64     return false;
65   return true;
66 }
67 
68 void CSEMIRBuilder::profileDstOp(const DstOp &Op,
69                                  GISelInstProfileBuilder &B) const {
70   switch (Op.getDstOpKind()) {
71   case DstOp::DstType::Ty_RC:
72     B.addNodeIDRegType(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(Op.getReg());
77     break;
78   }
79   default:
80     B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
81     break;
82   }
83 }
84 
85 void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
86                                  GISelInstProfileBuilder &B) const {
87   switch (Op.getSrcOpKind()) {
88   case SrcOp::SrcType::Ty_Imm:
89     B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm()));
90     break;
91   case SrcOp::SrcType::Ty_Predicate:
92     B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
93     break;
94   default:
95     B.addNodeIDRegType(Op.getReg());
96     break;
97   }
98 }
99 
100 void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
101                                      unsigned Opc) const {
102   // First add the MBB (Local CSE).
103   B.addNodeIDMBB(&getMBB());
104   // Then add the opcode.
105   B.addNodeIDOpcode(Opc);
106 }
107 
108 void 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(DstOps, B);
116   // Then add the SrcOps.
117   profileSrcOps(SrcOps, B);
118   // Add Flags if passed in.
119   if (Flags)
120     B.addNodeIDFlag(*Flags);
121 }
122 
123 MachineInstrBuilder 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(MIBInstr, NodeInsertPos);
129   return MIB;
130 }
131 
132 bool 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(DstOps, [](const DstOp &Op) {
137     DstOp::DstType DT = Op.getDstOpKind();
138     return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
139   });
140 }
141 
142 MachineInstrBuilder
143 CSEMIRBuilder::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(Op.getReg(), MIB.getReg(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(*MIB);
161     MIB->setDebugLoc(
162         DILocation::getMergedLocation(MIB->getDebugLoc(), getDebugLoc()));
163     if (Observer)
164       Observer->changedInstr(*MIB);
165   }
166 
167   return MIB;
168 }
169 
170 MachineInstrBuilder 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(*getMRI());
181 
182     if (std::optional<SmallVector<APInt>> Cst =
183             ConstantFoldICmp(SrcOps[0].getPredicate(), SrcOps[1].getReg(),
184                              SrcOps[2].getReg(), *getMRI())) {
185       if (SrcTy.isVector())
186         return buildBuildVectorConstant(DstOps[0], *Cst);
187       return buildConstant(DstOps[0], 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(*getMRI());
213 
214     if (Opc == TargetOpcode::G_PTR_ADD &&
215         getDataLayout().isNonIntegralAddressSpace(SrcTy.getAddressSpace()))
216       break;
217 
218     if (SrcTy.isVector()) {
219       // Try to constant fold vector constants.
220       SmallVector<APInt> VecCst = ConstantFoldVectorBinop(
221           Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI());
222       if (!VecCst.empty())
223         return buildBuildVectorConstant(DstOps[0], VecCst);
224       break;
225     }
226 
227     if (std::optional<APInt> Cst = ConstantFoldBinOp(
228             Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
229       return buildConstant(DstOps[0], *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             Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
249       return buildFConstant(DstOps[0], *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(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
260       return buildConstant(Dst, *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             Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
270       return buildFConstant(DstOps[0], *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(SrcOps[0].getReg(), *getMRI(), CB);
283     if (!MaybeCsts)
284       break;
285     if (MaybeCsts->size() == 1)
286       return buildConstant(DstOps[0], (*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(*getMRI());
290     for (unsigned Cst : *MaybeCsts)
291       ConstantRegs.emplace_back(
292           buildConstant(VecTy.getScalarType(), Cst).getReg(0));
293     return buildBuildVector(DstOps[0], ConstantRegs);
294   }
295   }
296   bool CanCopy = checkCopyToDefsPossible(DstOps);
297   if (!canPerformCSEForOpc(Opc))
298     return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, 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, Flag);
303     // CSEInfo would have tracked this instruction. Remove it from the temporary
304     // insts.
305     getCSEInfo()->handleRemoveInst(&*MIB);
306     return MIB;
307   }
308   FoldingSetNodeID ID;
309   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
310   void *InsertPos = nullptr;
311   profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
312   MachineInstrBuilder MIB = getDominatingInstrForID(ID, 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, Flag);
320   return memoizeMI(NewMIB, InsertPos);
321 }
322 
323 MachineInstrBuilder 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(*getMRI());
331   if (Ty.isVector())
332     return buildSplatBuildVector(Res, buildConstant(Ty.getElementType(), Val));
333 
334   FoldingSetNodeID ID;
335   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
336   void *InsertPos = nullptr;
337   profileMBBOpcode(ProfBuilder, Opc);
338   profileDstOp(Res, ProfBuilder);
339   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
340   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
341   if (MIB) {
342     // Handle generating copies here.
343     return generateCopiesIfRequired({Res}, MIB);
344   }
345 
346   MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
347   return memoizeMI(NewMIB, InsertPos);
348 }
349 
350 MachineInstrBuilder 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(*getMRI());
358   if (Ty.isVector())
359     return buildSplatBuildVector(Res, buildFConstant(Ty.getElementType(), Val));
360 
361   FoldingSetNodeID ID;
362   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
363   void *InsertPos = nullptr;
364   profileMBBOpcode(ProfBuilder, Opc);
365   profileDstOp(Res, ProfBuilder);
366   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
367   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
368   if (MIB) {
369     // Handle generating copies here.
370     return generateCopiesIfRequired({Res}, MIB);
371   }
372   MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
373   return memoizeMI(NewMIB, InsertPos);
374 }
375