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/GISelChangeObserver.h"
16 #include "llvm/IR/DebugInfoMetadata.h"
17 
18 using namespace llvm;
19 
20 bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
21                               MachineBasicBlock::const_iterator B) const {
22   auto MBBEnd = getMBB().end();
23   if (B == MBBEnd)
24     return true;
25   assert(A->getParent() == B->getParent() &&
26          "Iterators should be in same block");
27   const MachineBasicBlock *BBA = A->getParent();
28   MachineBasicBlock::const_iterator I = BBA->begin();
29   for (; &*I != A && &*I != B; ++I)
30     ;
31   return &*I == A;
32 }
33 
34 MachineInstrBuilder
35 CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
36                                        void *&NodeInsertPos) {
37   GISelCSEInfo *CSEInfo = getCSEInfo();
38   assert(CSEInfo && "Can't get here without setting CSEInfo");
39   MachineBasicBlock *CurMBB = &getMBB();
40   MachineInstr *MI =
41       CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
42   if (MI) {
43     CSEInfo->countOpcodeHit(MI->getOpcode());
44     auto CurrPos = getInsertPt();
45     auto MII = MachineBasicBlock::iterator(MI);
46     if (MII == CurrPos) {
47       // Move the insert point ahead of the instruction so any future uses of
48       // this builder will have the def ready.
49       setInsertPt(*CurMBB, std::next(MII));
50     } else if (!dominates(MI, CurrPos)) {
51       CurMBB->splice(CurrPos, CurMBB, MI);
52     }
53     return MachineInstrBuilder(getMF(), MI);
54   }
55   return MachineInstrBuilder();
56 }
57 
58 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
59   const GISelCSEInfo *CSEInfo = getCSEInfo();
60   if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
61     return false;
62   return true;
63 }
64 
65 void CSEMIRBuilder::profileDstOp(const DstOp &Op,
66                                  GISelInstProfileBuilder &B) const {
67   switch (Op.getDstOpKind()) {
68   case DstOp::DstType::Ty_RC:
69     B.addNodeIDRegType(Op.getRegClass());
70     break;
71   case DstOp::DstType::Ty_Reg: {
72     // Regs can have LLT&(RB|RC). If those exist, profile them as well.
73     B.addNodeIDReg(Op.getReg());
74     break;
75   }
76   default:
77     B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
78     break;
79   }
80 }
81 
82 void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
83                                  GISelInstProfileBuilder &B) const {
84   switch (Op.getSrcOpKind()) {
85   case SrcOp::SrcType::Ty_Imm:
86     B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm()));
87     break;
88   case SrcOp::SrcType::Ty_Predicate:
89     B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
90     break;
91   default:
92     B.addNodeIDRegType(Op.getReg());
93     break;
94   }
95 }
96 
97 void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
98                                      unsigned Opc) const {
99   // First add the MBB (Local CSE).
100   B.addNodeIDMBB(&getMBB());
101   // Then add the opcode.
102   B.addNodeIDOpcode(Opc);
103 }
104 
105 void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
106                                       ArrayRef<SrcOp> SrcOps,
107                                       Optional<unsigned> Flags,
108                                       GISelInstProfileBuilder &B) const {
109 
110   profileMBBOpcode(B, Opc);
111   // Then add the DstOps.
112   profileDstOps(DstOps, B);
113   // Then add the SrcOps.
114   profileSrcOps(SrcOps, B);
115   // Add Flags if passed in.
116   if (Flags)
117     B.addNodeIDFlag(*Flags);
118 }
119 
120 MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
121                                              void *NodeInsertPos) {
122   assert(canPerformCSEForOpc(MIB->getOpcode()) &&
123          "Attempting to CSE illegal op");
124   MachineInstr *MIBInstr = MIB;
125   getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);
126   return MIB;
127 }
128 
129 bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
130   if (DstOps.size() == 1)
131     return true; // always possible to emit copy to just 1 vreg.
132 
133   return llvm::all_of(DstOps, [](const DstOp &Op) {
134     DstOp::DstType DT = Op.getDstOpKind();
135     return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
136   });
137 }
138 
139 MachineInstrBuilder
140 CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
141                                         MachineInstrBuilder &MIB) {
142   assert(checkCopyToDefsPossible(DstOps) &&
143          "Impossible return a single MIB with copies to multiple defs");
144   if (DstOps.size() == 1) {
145     const DstOp &Op = DstOps[0];
146     if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
147       return buildCopy(Op.getReg(), MIB.getReg(0));
148   }
149 
150   // If we didn't generate a copy then we're re-using an existing node directly
151   // instead of emitting any code. Merge the debug location we wanted to emit
152   // into the instruction we're CSE'ing with. Debug locations arent part of the
153   // profile so we don't need to recompute it.
154   if (getDebugLoc()) {
155     GISelChangeObserver *Observer = getState().Observer;
156     if (Observer)
157       Observer->changingInstr(*MIB);
158     MIB->setDebugLoc(
159         DILocation::getMergedLocation(MIB->getDebugLoc(), getDebugLoc()));
160     if (Observer)
161       Observer->changedInstr(*MIB);
162   }
163 
164   return MIB;
165 }
166 
167 MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,
168                                               ArrayRef<DstOp> DstOps,
169                                               ArrayRef<SrcOp> SrcOps,
170                                               Optional<unsigned> Flag) {
171   switch (Opc) {
172   default:
173     break;
174   case TargetOpcode::G_ADD:
175   case TargetOpcode::G_AND:
176   case TargetOpcode::G_ASHR:
177   case TargetOpcode::G_LSHR:
178   case TargetOpcode::G_MUL:
179   case TargetOpcode::G_OR:
180   case TargetOpcode::G_SHL:
181   case TargetOpcode::G_SUB:
182   case TargetOpcode::G_XOR:
183   case TargetOpcode::G_UDIV:
184   case TargetOpcode::G_SDIV:
185   case TargetOpcode::G_UREM:
186   case TargetOpcode::G_SREM: {
187     // Try to constant fold these.
188     assert(SrcOps.size() == 2 && "Invalid sources");
189     assert(DstOps.size() == 1 && "Invalid dsts");
190     if (Optional<APInt> Cst = ConstantFoldBinOp(Opc, SrcOps[0].getReg(),
191                                                 SrcOps[1].getReg(), *getMRI()))
192       return buildConstant(DstOps[0], *Cst);
193     break;
194   }
195   case TargetOpcode::G_SEXT_INREG: {
196     assert(DstOps.size() == 1 && "Invalid dst ops");
197     assert(SrcOps.size() == 2 && "Invalid src ops");
198     const DstOp &Dst = DstOps[0];
199     const SrcOp &Src0 = SrcOps[0];
200     const SrcOp &Src1 = SrcOps[1];
201     if (auto MaybeCst =
202             ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
203       return buildConstant(Dst, *MaybeCst);
204     break;
205   }
206   case TargetOpcode::G_SITOFP:
207   case TargetOpcode::G_UITOFP: {
208     // Try to constant fold these.
209     assert(SrcOps.size() == 1 && "Invalid sources");
210     assert(DstOps.size() == 1 && "Invalid dsts");
211     if (Optional<APFloat> Cst = ConstantFoldIntToFloat(
212             Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
213       return buildFConstant(DstOps[0], *Cst);
214     break;
215   }
216   }
217   bool CanCopy = checkCopyToDefsPossible(DstOps);
218   if (!canPerformCSEForOpc(Opc))
219     return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
220   // If we can CSE this instruction, but involves generating copies to multiple
221   // regs, give up. This frequently happens to UNMERGEs.
222   if (!CanCopy) {
223     auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
224     // CSEInfo would have tracked this instruction. Remove it from the temporary
225     // insts.
226     getCSEInfo()->handleRemoveInst(&*MIB);
227     return MIB;
228   }
229   FoldingSetNodeID ID;
230   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
231   void *InsertPos = nullptr;
232   profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
233   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
234   if (MIB) {
235     // Handle generating copies here.
236     return generateCopiesIfRequired(DstOps, MIB);
237   }
238   // This instruction does not exist in the CSEInfo. Build it and CSE it.
239   MachineInstrBuilder NewMIB =
240       MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
241   return memoizeMI(NewMIB, InsertPos);
242 }
243 
244 MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
245                                                  const ConstantInt &Val) {
246   constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
247   if (!canPerformCSEForOpc(Opc))
248     return MachineIRBuilder::buildConstant(Res, Val);
249 
250   // For vectors, CSE the element only for now.
251   LLT Ty = Res.getLLTTy(*getMRI());
252   if (Ty.isVector())
253     return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
254 
255   FoldingSetNodeID ID;
256   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
257   void *InsertPos = nullptr;
258   profileMBBOpcode(ProfBuilder, Opc);
259   profileDstOp(Res, ProfBuilder);
260   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
261   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
262   if (MIB) {
263     // Handle generating copies here.
264     return generateCopiesIfRequired({Res}, MIB);
265   }
266 
267   MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
268   return memoizeMI(NewMIB, InsertPos);
269 }
270 
271 MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
272                                                   const ConstantFP &Val) {
273   constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
274   if (!canPerformCSEForOpc(Opc))
275     return MachineIRBuilder::buildFConstant(Res, Val);
276 
277   // For vectors, CSE the element only for now.
278   LLT Ty = Res.getLLTTy(*getMRI());
279   if (Ty.isVector())
280     return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val));
281 
282   FoldingSetNodeID ID;
283   GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
284   void *InsertPos = nullptr;
285   profileMBBOpcode(ProfBuilder, Opc);
286   profileDstOp(Res, ProfBuilder);
287   ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
288   MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
289   if (MIB) {
290     // Handle generating copies here.
291     return generateCopiesIfRequired({Res}, MIB);
292   }
293   MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
294   return memoizeMI(NewMIB, InsertPos);
295 }
296