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
dominates(MachineBasicBlock::const_iterator A,MachineBasicBlock::const_iterator B) const20 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
getDominatingInstrForID(FoldingSetNodeID & ID,void * & NodeInsertPos)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
canPerformCSEForOpc(unsigned Opc) const58 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
profileDstOp(const DstOp & Op,GISelInstProfileBuilder & B) const65 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
profileSrcOp(const SrcOp & Op,GISelInstProfileBuilder & B) const82 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
profileMBBOpcode(GISelInstProfileBuilder & B,unsigned Opc) const97 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
profileEverything(unsigned Opc,ArrayRef<DstOp> DstOps,ArrayRef<SrcOp> SrcOps,Optional<unsigned> Flags,GISelInstProfileBuilder & B) const105 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
memoizeMI(MachineInstrBuilder MIB,void * NodeInsertPos)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
checkCopyToDefsPossible(ArrayRef<DstOp> DstOps)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
generateCopiesIfRequired(ArrayRef<DstOp> DstOps,MachineInstrBuilder & MIB)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
buildInstr(unsigned Opc,ArrayRef<DstOp> DstOps,ArrayRef<SrcOp> SrcOps,Optional<unsigned> Flag)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->getSExtValue());
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->getSExtValue());
204 break;
205 }
206 }
207 bool CanCopy = checkCopyToDefsPossible(DstOps);
208 if (!canPerformCSEForOpc(Opc))
209 return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
210 // If we can CSE this instruction, but involves generating copies to multiple
211 // regs, give up. This frequently happens to UNMERGEs.
212 if (!CanCopy) {
213 auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
214 // CSEInfo would have tracked this instruction. Remove it from the temporary
215 // insts.
216 getCSEInfo()->handleRemoveInst(&*MIB);
217 return MIB;
218 }
219 FoldingSetNodeID ID;
220 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
221 void *InsertPos = nullptr;
222 profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
223 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
224 if (MIB) {
225 // Handle generating copies here.
226 return generateCopiesIfRequired(DstOps, MIB);
227 }
228 // This instruction does not exist in the CSEInfo. Build it and CSE it.
229 MachineInstrBuilder NewMIB =
230 MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
231 return memoizeMI(NewMIB, InsertPos);
232 }
233
buildConstant(const DstOp & Res,const ConstantInt & Val)234 MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
235 const ConstantInt &Val) {
236 constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
237 if (!canPerformCSEForOpc(Opc))
238 return MachineIRBuilder::buildConstant(Res, Val);
239
240 // For vectors, CSE the element only for now.
241 LLT Ty = Res.getLLTTy(*getMRI());
242 if (Ty.isVector())
243 return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
244
245 FoldingSetNodeID ID;
246 GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
247 void *InsertPos = nullptr;
248 profileMBBOpcode(ProfBuilder, Opc);
249 profileDstOp(Res, ProfBuilder);
250 ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
251 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
252 if (MIB) {
253 // Handle generating copies here.
254 return generateCopiesIfRequired({Res}, MIB);
255 }
256
257 MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
258 return memoizeMI(NewMIB, InsertPos);
259 }
260
buildFConstant(const DstOp & Res,const ConstantFP & Val)261 MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
262 const ConstantFP &Val) {
263 constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
264 if (!canPerformCSEForOpc(Opc))
265 return MachineIRBuilder::buildFConstant(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, buildFConstant(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::CreateFPImm(&Val));
278 MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
279 if (MIB) {
280 // Handle generating copies here.
281 return generateCopiesIfRequired({Res}, MIB);
282 }
283 MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
284 return memoizeMI(NewMIB, InsertPos);
285 }
286