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, MBB: CurMBB, InsertPos&: NodeInsertPos); |
45 | if (MI) { |
46 | CSEInfo->countOpcodeHit(Opc: 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(MBB&: *CurMBB, II: std::next(x: MII)); |
53 | } else if (!dominates(A: MI, B: CurrPos)) { |
54 | CurMBB->splice(Where: CurrPos, Other: CurMBB, From: MI); |
55 | } |
56 | return MachineInstrBuilder(getMF(), MI); |
57 | } |
58 | return MachineInstrBuilder(); |
59 | } |
60 | |
61 | bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const { |
62 | const GISelCSEInfo *CSEInfo = getCSEInfo(); |
63 | if (!CSEInfo || !CSEInfo->shouldCSE(Opc)) |
64 | return false; |
65 | return true; |
66 | } |
67 | |
68 | void CSEMIRBuilder::profileDstOp(const DstOp &Op, |
69 | GISelInstProfileBuilder &B) const { |
70 | switch (Op.getDstOpKind()) { |
71 | case DstOp::DstType::Ty_RC: |
72 | B.addNodeIDRegType(RC: Op.getRegClass()); |
73 | break; |
74 | case DstOp::DstType::Ty_Reg: { |
75 | // Regs can have LLT&(RB|RC). If those exist, profile them as well. |
76 | B.addNodeIDReg(Reg: Op.getReg()); |
77 | break; |
78 | } |
79 | default: |
80 | B.addNodeIDRegType(Ty: Op.getLLTTy(MRI: *getMRI())); |
81 | break; |
82 | } |
83 | } |
84 | |
85 | void CSEMIRBuilder::profileSrcOp(const SrcOp &Op, |
86 | GISelInstProfileBuilder &B) const { |
87 | switch (Op.getSrcOpKind()) { |
88 | case SrcOp::SrcType::Ty_Imm: |
89 | B.addNodeIDImmediate(Imm: static_cast<int64_t>(Op.getImm())); |
90 | break; |
91 | case SrcOp::SrcType::Ty_Predicate: |
92 | B.addNodeIDImmediate(Imm: static_cast<int64_t>(Op.getPredicate())); |
93 | break; |
94 | default: |
95 | B.addNodeIDRegType(Op.getReg()); |
96 | break; |
97 | } |
98 | } |
99 | |
100 | void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B, |
101 | unsigned Opc) const { |
102 | // First add the MBB (Local CSE). |
103 | B.addNodeIDMBB(MBB: &getMBB()); |
104 | // Then add the opcode. |
105 | B.addNodeIDOpcode(Opc); |
106 | } |
107 | |
108 | void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps, |
109 | ArrayRef<SrcOp> SrcOps, |
110 | std::optional<unsigned> Flags, |
111 | GISelInstProfileBuilder &B) const { |
112 | |
113 | profileMBBOpcode(B, Opc); |
114 | // Then add the DstOps. |
115 | profileDstOps(Ops: DstOps, B); |
116 | // Then add the SrcOps. |
117 | profileSrcOps(Ops: SrcOps, B); |
118 | // Add Flags if passed in. |
119 | if (Flags) |
120 | B.addNodeIDFlag(Flag: *Flags); |
121 | } |
122 | |
123 | MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB, |
124 | void *NodeInsertPos) { |
125 | assert(canPerformCSEForOpc(MIB->getOpcode()) && |
126 | "Attempting to CSE illegal op" ); |
127 | MachineInstr *MIBInstr = MIB; |
128 | getCSEInfo()->insertInstr(MI: MIBInstr, InsertPos: NodeInsertPos); |
129 | return MIB; |
130 | } |
131 | |
132 | bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) { |
133 | if (DstOps.size() == 1) |
134 | return true; // always possible to emit copy to just 1 vreg. |
135 | |
136 | return llvm::all_of(Range&: DstOps, P: [](const DstOp &Op) { |
137 | DstOp::DstType DT = Op.getDstOpKind(); |
138 | return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC; |
139 | }); |
140 | } |
141 | |
142 | MachineInstrBuilder |
143 | CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps, |
144 | MachineInstrBuilder &MIB) { |
145 | assert(checkCopyToDefsPossible(DstOps) && |
146 | "Impossible return a single MIB with copies to multiple defs" ); |
147 | if (DstOps.size() == 1) { |
148 | const DstOp &Op = DstOps[0]; |
149 | if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg) |
150 | return buildCopy(Res: Op.getReg(), Op: MIB.getReg(Idx: 0)); |
151 | } |
152 | |
153 | // If we didn't generate a copy then we're re-using an existing node directly |
154 | // instead of emitting any code. Merge the debug location we wanted to emit |
155 | // into the instruction we're CSE'ing with. Debug locations arent part of the |
156 | // profile so we don't need to recompute it. |
157 | if (getDebugLoc()) { |
158 | GISelChangeObserver *Observer = getState().Observer; |
159 | if (Observer) |
160 | Observer->changingInstr(MI&: *MIB); |
161 | MIB->setDebugLoc( |
162 | DILocation::getMergedLocation(LocA: MIB->getDebugLoc(), LocB: getDebugLoc())); |
163 | if (Observer) |
164 | Observer->changedInstr(MI&: *MIB); |
165 | } |
166 | |
167 | return MIB; |
168 | } |
169 | |
170 | MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc, |
171 | ArrayRef<DstOp> DstOps, |
172 | ArrayRef<SrcOp> SrcOps, |
173 | std::optional<unsigned> Flag) { |
174 | switch (Opc) { |
175 | default: |
176 | break; |
177 | case TargetOpcode::G_ICMP: { |
178 | assert(SrcOps.size() == 3 && "Invalid sources" ); |
179 | assert(DstOps.size() == 1 && "Invalid dsts" ); |
180 | LLT SrcTy = SrcOps[1].getLLTTy(MRI: *getMRI()); |
181 | |
182 | if (std::optional<SmallVector<APInt>> Cst = |
183 | ConstantFoldICmp(Pred: SrcOps[0].getPredicate(), Op1: SrcOps[1].getReg(), |
184 | Op2: SrcOps[2].getReg(), MRI: *getMRI())) { |
185 | if (SrcTy.isVector()) |
186 | return buildBuildVectorConstant(Res: DstOps[0], Ops: *Cst); |
187 | return buildConstant(Res: DstOps[0], Val: Cst->front()); |
188 | } |
189 | break; |
190 | } |
191 | case TargetOpcode::G_ADD: |
192 | case TargetOpcode::G_PTR_ADD: |
193 | case TargetOpcode::G_AND: |
194 | case TargetOpcode::G_ASHR: |
195 | case TargetOpcode::G_LSHR: |
196 | case TargetOpcode::G_MUL: |
197 | case TargetOpcode::G_OR: |
198 | case TargetOpcode::G_SHL: |
199 | case TargetOpcode::G_SUB: |
200 | case TargetOpcode::G_XOR: |
201 | case TargetOpcode::G_UDIV: |
202 | case TargetOpcode::G_SDIV: |
203 | case TargetOpcode::G_UREM: |
204 | case TargetOpcode::G_SREM: |
205 | case TargetOpcode::G_SMIN: |
206 | case TargetOpcode::G_SMAX: |
207 | case TargetOpcode::G_UMIN: |
208 | case TargetOpcode::G_UMAX: { |
209 | // Try to constant fold these. |
210 | assert(SrcOps.size() == 2 && "Invalid sources" ); |
211 | assert(DstOps.size() == 1 && "Invalid dsts" ); |
212 | LLT SrcTy = SrcOps[0].getLLTTy(MRI: *getMRI()); |
213 | |
214 | if (Opc == TargetOpcode::G_PTR_ADD && |
215 | getDataLayout().isNonIntegralAddressSpace(AddrSpace: SrcTy.getAddressSpace())) |
216 | break; |
217 | |
218 | if (SrcTy.isVector()) { |
219 | // Try to constant fold vector constants. |
220 | SmallVector<APInt> VecCst = ConstantFoldVectorBinop( |
221 | Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()); |
222 | if (!VecCst.empty()) |
223 | return buildBuildVectorConstant(Res: DstOps[0], Ops: VecCst); |
224 | break; |
225 | } |
226 | |
227 | if (std::optional<APInt> Cst = ConstantFoldBinOp( |
228 | Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI())) |
229 | return buildConstant(Res: DstOps[0], Val: *Cst); |
230 | break; |
231 | } |
232 | case TargetOpcode::G_FADD: |
233 | case TargetOpcode::G_FSUB: |
234 | case TargetOpcode::G_FMUL: |
235 | case TargetOpcode::G_FDIV: |
236 | case TargetOpcode::G_FREM: |
237 | case TargetOpcode::G_FMINNUM: |
238 | case TargetOpcode::G_FMAXNUM: |
239 | case TargetOpcode::G_FMINNUM_IEEE: |
240 | case TargetOpcode::G_FMAXNUM_IEEE: |
241 | case TargetOpcode::G_FMINIMUM: |
242 | case TargetOpcode::G_FMAXIMUM: |
243 | case TargetOpcode::G_FCOPYSIGN: { |
244 | // Try to constant fold these. |
245 | assert(SrcOps.size() == 2 && "Invalid sources" ); |
246 | assert(DstOps.size() == 1 && "Invalid dsts" ); |
247 | if (std::optional<APFloat> Cst = ConstantFoldFPBinOp( |
248 | Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI())) |
249 | return buildFConstant(Res: DstOps[0], Val: *Cst); |
250 | break; |
251 | } |
252 | case TargetOpcode::G_SEXT_INREG: { |
253 | assert(DstOps.size() == 1 && "Invalid dst ops" ); |
254 | assert(SrcOps.size() == 2 && "Invalid src ops" ); |
255 | const DstOp &Dst = DstOps[0]; |
256 | const SrcOp &Src0 = SrcOps[0]; |
257 | const SrcOp &Src1 = SrcOps[1]; |
258 | if (auto MaybeCst = |
259 | ConstantFoldExtOp(Opcode: Opc, Op1: Src0.getReg(), Imm: Src1.getImm(), MRI: *getMRI())) |
260 | return buildConstant(Res: Dst, Val: *MaybeCst); |
261 | break; |
262 | } |
263 | case TargetOpcode::G_SITOFP: |
264 | case TargetOpcode::G_UITOFP: { |
265 | // Try to constant fold these. |
266 | assert(SrcOps.size() == 1 && "Invalid sources" ); |
267 | assert(DstOps.size() == 1 && "Invalid dsts" ); |
268 | if (std::optional<APFloat> Cst = ConstantFoldIntToFloat( |
269 | Opcode: Opc, DstTy: DstOps[0].getLLTTy(MRI: *getMRI()), Src: SrcOps[0].getReg(), MRI: *getMRI())) |
270 | return buildFConstant(Res: DstOps[0], Val: *Cst); |
271 | break; |
272 | } |
273 | case TargetOpcode::G_CTLZ: |
274 | case TargetOpcode::G_CTTZ: { |
275 | assert(SrcOps.size() == 1 && "Expected one source" ); |
276 | assert(DstOps.size() == 1 && "Expected one dest" ); |
277 | std::function<unsigned(APInt)> CB; |
278 | if (Opc == TargetOpcode::G_CTLZ) |
279 | CB = [](APInt V) -> unsigned { return V.countl_zero(); }; |
280 | else |
281 | CB = [](APInt V) -> unsigned { return V.countTrailingZeros(); }; |
282 | auto MaybeCsts = ConstantFoldCountZeros(Src: SrcOps[0].getReg(), MRI: *getMRI(), CB); |
283 | if (!MaybeCsts) |
284 | break; |
285 | if (MaybeCsts->size() == 1) |
286 | return buildConstant(Res: DstOps[0], Val: (*MaybeCsts)[0]); |
287 | // This was a vector constant. Build a G_BUILD_VECTOR for them. |
288 | SmallVector<Register> ConstantRegs; |
289 | LLT VecTy = DstOps[0].getLLTTy(MRI: *getMRI()); |
290 | for (unsigned Cst : *MaybeCsts) |
291 | ConstantRegs.emplace_back( |
292 | Args: buildConstant(Res: VecTy.getScalarType(), Val: Cst).getReg(Idx: 0)); |
293 | return buildBuildVector(Res: DstOps[0], Ops: ConstantRegs); |
294 | } |
295 | } |
296 | bool CanCopy = checkCopyToDefsPossible(DstOps); |
297 | if (!canPerformCSEForOpc(Opc)) |
298 | return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag); |
299 | // If we can CSE this instruction, but involves generating copies to multiple |
300 | // regs, give up. This frequently happens to UNMERGEs. |
301 | if (!CanCopy) { |
302 | auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag); |
303 | // CSEInfo would have tracked this instruction. Remove it from the temporary |
304 | // insts. |
305 | getCSEInfo()->handleRemoveInst(MI: &*MIB); |
306 | return MIB; |
307 | } |
308 | FoldingSetNodeID ID; |
309 | GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
310 | void *InsertPos = nullptr; |
311 | profileEverything(Opc, DstOps, SrcOps, Flags: Flag, B&: ProfBuilder); |
312 | MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos); |
313 | if (MIB) { |
314 | // Handle generating copies here. |
315 | return generateCopiesIfRequired(DstOps, MIB); |
316 | } |
317 | // This instruction does not exist in the CSEInfo. Build it and CSE it. |
318 | MachineInstrBuilder NewMIB = |
319 | MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag); |
320 | return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos); |
321 | } |
322 | |
323 | MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res, |
324 | const ConstantInt &Val) { |
325 | constexpr unsigned Opc = TargetOpcode::G_CONSTANT; |
326 | if (!canPerformCSEForOpc(Opc)) |
327 | return MachineIRBuilder::buildConstant(Res, Val); |
328 | |
329 | // For vectors, CSE the element only for now. |
330 | LLT Ty = Res.getLLTTy(MRI: *getMRI()); |
331 | if (Ty.isVector()) |
332 | return buildSplatBuildVector(Res, Src: buildConstant(Res: Ty.getElementType(), Val)); |
333 | |
334 | FoldingSetNodeID ID; |
335 | GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
336 | void *InsertPos = nullptr; |
337 | profileMBBOpcode(B&: ProfBuilder, Opc); |
338 | profileDstOp(Op: Res, B&: ProfBuilder); |
339 | ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateCImm(CI: &Val)); |
340 | MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos); |
341 | if (MIB) { |
342 | // Handle generating copies here. |
343 | return generateCopiesIfRequired(DstOps: {Res}, MIB); |
344 | } |
345 | |
346 | MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val); |
347 | return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos); |
348 | } |
349 | |
350 | MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res, |
351 | const ConstantFP &Val) { |
352 | constexpr unsigned Opc = TargetOpcode::G_FCONSTANT; |
353 | if (!canPerformCSEForOpc(Opc)) |
354 | return MachineIRBuilder::buildFConstant(Res, Val); |
355 | |
356 | // For vectors, CSE the element only for now. |
357 | LLT Ty = Res.getLLTTy(MRI: *getMRI()); |
358 | if (Ty.isVector()) |
359 | return buildSplatBuildVector(Res, Src: buildFConstant(Res: Ty.getElementType(), Val)); |
360 | |
361 | FoldingSetNodeID ID; |
362 | GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
363 | void *InsertPos = nullptr; |
364 | profileMBBOpcode(B&: ProfBuilder, Opc); |
365 | profileDstOp(Op: Res, B&: ProfBuilder); |
366 | ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateFPImm(CFP: &Val)); |
367 | MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos); |
368 | if (MIB) { |
369 | // Handle generating copies here. |
370 | return generateCopiesIfRequired(DstOps: {Res}, MIB); |
371 | } |
372 | MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val); |
373 | return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos); |
374 | } |
375 | |