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