xref: /llvm-project/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp (revision 89881480030f48f83af668175b70a9798edca2fb) 
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       // 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 
66 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 
73 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 
90 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 
105 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 
113 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 
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 
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
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 
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_FMINIMUMNUM:
249   case TargetOpcode::G_FMAXIMUMNUM:
250   case TargetOpcode::G_FCOPYSIGN: {
251     // Try to constant fold these.
252     assert(SrcOps.size() == 2 && "Invalid sources");
253     assert(DstOps.size() == 1 && "Invalid dsts");
254     if (std::optional<APFloat> Cst = ConstantFoldFPBinOp(
255             Opc, SrcOps[0].getReg(), SrcOps[1].getReg(), *getMRI()))
256       return buildFConstant(DstOps[0], *Cst);
257     break;
258   }
259   case TargetOpcode::G_SEXT_INREG: {
260     assert(DstOps.size() == 1 && "Invalid dst ops");
261     assert(SrcOps.size() == 2 && "Invalid src ops");
262     const DstOp &Dst = DstOps[0];
263     const SrcOp &Src0 = SrcOps[0];
264     const SrcOp &Src1 = SrcOps[1];
265     if (auto MaybeCst =
266             ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
267       return buildConstant(Dst, *MaybeCst);
268     break;
269   }
270   case TargetOpcode::G_SITOFP:
271   case TargetOpcode::G_UITOFP: {
272     // Try to constant fold these.
273     assert(SrcOps.size() == 1 && "Invalid sources");
274     assert(DstOps.size() == 1 && "Invalid dsts");
275     if (std::optional<APFloat> Cst = ConstantFoldIntToFloat(
276             Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
277       return buildFConstant(DstOps[0], *Cst);
278     break;
279   }
280   case TargetOpcode::G_CTLZ:
281   case TargetOpcode::G_CTTZ: {
282     assert(SrcOps.size() == 1 && "Expected one source");
283     assert(DstOps.size() == 1 && "Expected one dest");
284     std::function<unsigned(APInt)> CB;
285     if (Opc == TargetOpcode::G_CTLZ)
286       CB = [](APInt V) -> unsigned { return V.countl_zero(); };
287     else
288       CB = [](APInt V) -> unsigned { return V.countTrailingZeros(); };
289     auto MaybeCsts = ConstantFoldCountZeros(SrcOps[0].getReg(), *getMRI(), CB);
290     if (!MaybeCsts)
291       break;
292     if (MaybeCsts->size() == 1)
293       return buildConstant(DstOps[0], (*MaybeCsts)[0]);
294     // This was a vector constant. Build a G_BUILD_VECTOR for them.
295     SmallVector<Register> ConstantRegs;
296     LLT VecTy = DstOps[0].getLLTTy(*getMRI());
297     for (unsigned Cst : *MaybeCsts)
298       ConstantRegs.emplace_back(
299           buildConstant(VecTy.getScalarType(), Cst).getReg(0));
300     return buildBuildVector(DstOps[0], ConstantRegs);
301   }
302   }
303   bool CanCopy = checkCopyToDefsPossible(DstOps);
304   if (!canPerformCSEForOpc(Opc))
305     return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
306   // If we can CSE this instruction, but involves generating copies to multiple
307   // regs, give up. This frequently happens to UNMERGEs.
308   if (!CanCopy) {
309     auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
310     // CSEInfo would have tracked this instruction. Remove it from the temporary
311     // insts.
312     getCSEInfo()->handleRemoveInst(&*MIB);
313     return MIB;
314   }
315   FoldingSetNodeID ID;
316   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
317   void *InsertPos = nullptr;
318   profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
319   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
320   if (MIB) {
321     // Handle generating copies here.
322     return generateCopiesIfRequired(DstOps, MIB);
323   }
324   // This instruction does not exist in the CSEInfo. Build it and CSE it.
325   MachineInstrBuilder NewMIB =
326       MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
327   return memoizeMI(NewMIB, InsertPos);
328 }
329 
330 MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
331                                                  const ConstantInt &Val) {
332   constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
333   if (!canPerformCSEForOpc(Opc))
334     return MachineIRBuilder::buildConstant(Res, Val);
335 
336   // For vectors, CSE the element only for now.
337   LLT Ty = Res.getLLTTy(*getMRI());
338   if (Ty.isVector())
339     return buildSplatBuildVector(Res, buildConstant(Ty.getElementType(), Val));
340 
341   FoldingSetNodeID ID;
342   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
343   void *InsertPos = nullptr;
344   profileMBBOpcode(ProfBuilder, Opc);
345   profileDstOp(Res, ProfBuilder);
346   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
347   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
348   if (MIB) {
349     // Handle generating copies here.
350     return generateCopiesIfRequired({Res}, MIB);
351   }
352 
353   MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
354   return memoizeMI(NewMIB, InsertPos);
355 }
356 
357 MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
358                                                   const ConstantFP &Val) {
359   constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
360   if (!canPerformCSEForOpc(Opc))
361     return MachineIRBuilder::buildFConstant(Res, Val);
362 
363   // For vectors, CSE the element only for now.
364   LLT Ty = Res.getLLTTy(*getMRI());
365   if (Ty.isVector())
366     return buildSplatBuildVector(Res, buildFConstant(Ty.getElementType(), Val));
367 
368   FoldingSetNodeID ID;
369   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
370   void *InsertPos = nullptr;
371   profileMBBOpcode(ProfBuilder, Opc);
372   profileDstOp(Res, ProfBuilder);
373   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
374   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
375   if (MIB) {
376     // Handle generating copies here.
377     return generateCopiesIfRequired({Res}, MIB);
378   }
379   MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
380   return memoizeMI(NewMIB, InsertPos);
381 }
382