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