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_ADD: |
178 | case TargetOpcode::G_PTR_ADD: |
179 | case TargetOpcode::G_AND: |
180 | case TargetOpcode::G_ASHR: |
181 | case TargetOpcode::G_LSHR: |
182 | case TargetOpcode::G_MUL: |
183 | case TargetOpcode::G_OR: |
184 | case TargetOpcode::G_SHL: |
185 | case TargetOpcode::G_SUB: |
186 | case TargetOpcode::G_XOR: |
187 | case TargetOpcode::G_UDIV: |
188 | case TargetOpcode::G_SDIV: |
189 | case TargetOpcode::G_UREM: |
190 | case TargetOpcode::G_SREM: |
191 | case TargetOpcode::G_SMIN: |
192 | case TargetOpcode::G_SMAX: |
193 | case TargetOpcode::G_UMIN: |
194 | case TargetOpcode::G_UMAX: { |
195 | // Try to constant fold these. |
196 | assert(SrcOps.size() == 2 && "Invalid sources" ); |
197 | assert(DstOps.size() == 1 && "Invalid dsts" ); |
198 | LLT SrcTy = SrcOps[0].getLLTTy(MRI: *getMRI()); |
199 | |
200 | if (Opc == TargetOpcode::G_PTR_ADD && |
201 | getDataLayout().isNonIntegralAddressSpace(AddrSpace: SrcTy.getAddressSpace())) |
202 | break; |
203 | |
204 | if (SrcTy.isVector()) { |
205 | // Try to constant fold vector constants. |
206 | SmallVector<APInt> VecCst = ConstantFoldVectorBinop( |
207 | Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI()); |
208 | if (!VecCst.empty()) |
209 | return buildBuildVectorConstant(Res: DstOps[0], Ops: VecCst); |
210 | break; |
211 | } |
212 | |
213 | if (std::optional<APInt> Cst = ConstantFoldBinOp( |
214 | Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI())) |
215 | return buildConstant(Res: DstOps[0], Val: *Cst); |
216 | break; |
217 | } |
218 | case TargetOpcode::G_FADD: |
219 | case TargetOpcode::G_FSUB: |
220 | case TargetOpcode::G_FMUL: |
221 | case TargetOpcode::G_FDIV: |
222 | case TargetOpcode::G_FREM: |
223 | case TargetOpcode::G_FMINNUM: |
224 | case TargetOpcode::G_FMAXNUM: |
225 | case TargetOpcode::G_FMINNUM_IEEE: |
226 | case TargetOpcode::G_FMAXNUM_IEEE: |
227 | case TargetOpcode::G_FMINIMUM: |
228 | case TargetOpcode::G_FMAXIMUM: |
229 | case TargetOpcode::G_FCOPYSIGN: { |
230 | // Try to constant fold these. |
231 | assert(SrcOps.size() == 2 && "Invalid sources" ); |
232 | assert(DstOps.size() == 1 && "Invalid dsts" ); |
233 | if (std::optional<APFloat> Cst = ConstantFoldFPBinOp( |
234 | Opcode: Opc, Op1: SrcOps[0].getReg(), Op2: SrcOps[1].getReg(), MRI: *getMRI())) |
235 | return buildFConstant(Res: DstOps[0], Val: *Cst); |
236 | break; |
237 | } |
238 | case TargetOpcode::G_SEXT_INREG: { |
239 | assert(DstOps.size() == 1 && "Invalid dst ops" ); |
240 | assert(SrcOps.size() == 2 && "Invalid src ops" ); |
241 | const DstOp &Dst = DstOps[0]; |
242 | const SrcOp &Src0 = SrcOps[0]; |
243 | const SrcOp &Src1 = SrcOps[1]; |
244 | if (auto MaybeCst = |
245 | ConstantFoldExtOp(Opcode: Opc, Op1: Src0.getReg(), Imm: Src1.getImm(), MRI: *getMRI())) |
246 | return buildConstant(Res: Dst, Val: *MaybeCst); |
247 | break; |
248 | } |
249 | case TargetOpcode::G_SITOFP: |
250 | case TargetOpcode::G_UITOFP: { |
251 | // Try to constant fold these. |
252 | assert(SrcOps.size() == 1 && "Invalid sources" ); |
253 | assert(DstOps.size() == 1 && "Invalid dsts" ); |
254 | if (std::optional<APFloat> Cst = ConstantFoldIntToFloat( |
255 | Opcode: Opc, DstTy: DstOps[0].getLLTTy(MRI: *getMRI()), Src: SrcOps[0].getReg(), MRI: *getMRI())) |
256 | return buildFConstant(Res: DstOps[0], Val: *Cst); |
257 | break; |
258 | } |
259 | case TargetOpcode::G_CTLZ: { |
260 | assert(SrcOps.size() == 1 && "Expected one source" ); |
261 | assert(DstOps.size() == 1 && "Expected one dest" ); |
262 | auto MaybeCsts = ConstantFoldCTLZ(Src: SrcOps[0].getReg(), MRI: *getMRI()); |
263 | if (!MaybeCsts) |
264 | break; |
265 | if (MaybeCsts->size() == 1) |
266 | return buildConstant(Res: DstOps[0], Val: (*MaybeCsts)[0]); |
267 | // This was a vector constant. Build a G_BUILD_VECTOR for them. |
268 | SmallVector<Register> ConstantRegs; |
269 | LLT VecTy = DstOps[0].getLLTTy(MRI: *getMRI()); |
270 | for (unsigned Cst : *MaybeCsts) |
271 | ConstantRegs.emplace_back( |
272 | Args: buildConstant(Res: VecTy.getScalarType(), Val: Cst).getReg(Idx: 0)); |
273 | return buildBuildVector(Res: DstOps[0], Ops: ConstantRegs); |
274 | } |
275 | } |
276 | bool CanCopy = checkCopyToDefsPossible(DstOps); |
277 | if (!canPerformCSEForOpc(Opc)) |
278 | return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag); |
279 | // If we can CSE this instruction, but involves generating copies to multiple |
280 | // regs, give up. This frequently happens to UNMERGEs. |
281 | if (!CanCopy) { |
282 | auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag); |
283 | // CSEInfo would have tracked this instruction. Remove it from the temporary |
284 | // insts. |
285 | getCSEInfo()->handleRemoveInst(MI: &*MIB); |
286 | return MIB; |
287 | } |
288 | FoldingSetNodeID ID; |
289 | GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
290 | void *InsertPos = nullptr; |
291 | profileEverything(Opc, DstOps, SrcOps, Flags: Flag, B&: ProfBuilder); |
292 | MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos); |
293 | if (MIB) { |
294 | // Handle generating copies here. |
295 | return generateCopiesIfRequired(DstOps, MIB); |
296 | } |
297 | // This instruction does not exist in the CSEInfo. Build it and CSE it. |
298 | MachineInstrBuilder NewMIB = |
299 | MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flags: Flag); |
300 | return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos); |
301 | } |
302 | |
303 | MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res, |
304 | const ConstantInt &Val) { |
305 | constexpr unsigned Opc = TargetOpcode::G_CONSTANT; |
306 | if (!canPerformCSEForOpc(Opc)) |
307 | return MachineIRBuilder::buildConstant(Res, Val); |
308 | |
309 | // For vectors, CSE the element only for now. |
310 | LLT Ty = Res.getLLTTy(MRI: *getMRI()); |
311 | if (Ty.isVector()) |
312 | return buildSplatVector(Res, Src: buildConstant(Res: Ty.getElementType(), Val)); |
313 | |
314 | FoldingSetNodeID ID; |
315 | GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
316 | void *InsertPos = nullptr; |
317 | profileMBBOpcode(B&: ProfBuilder, Opc); |
318 | profileDstOp(Op: Res, B&: ProfBuilder); |
319 | ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateCImm(CI: &Val)); |
320 | MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos); |
321 | if (MIB) { |
322 | // Handle generating copies here. |
323 | return generateCopiesIfRequired(DstOps: {Res}, MIB); |
324 | } |
325 | |
326 | MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val); |
327 | return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos); |
328 | } |
329 | |
330 | MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res, |
331 | const ConstantFP &Val) { |
332 | constexpr unsigned Opc = TargetOpcode::G_FCONSTANT; |
333 | if (!canPerformCSEForOpc(Opc)) |
334 | return MachineIRBuilder::buildFConstant(Res, Val); |
335 | |
336 | // For vectors, CSE the element only for now. |
337 | LLT Ty = Res.getLLTTy(MRI: *getMRI()); |
338 | if (Ty.isVector()) |
339 | return buildSplatVector(Res, Src: buildFConstant(Res: Ty.getElementType(), Val)); |
340 | |
341 | FoldingSetNodeID ID; |
342 | GISelInstProfileBuilder ProfBuilder(ID, *getMRI()); |
343 | void *InsertPos = nullptr; |
344 | profileMBBOpcode(B&: ProfBuilder, Opc); |
345 | profileDstOp(Op: Res, B&: ProfBuilder); |
346 | ProfBuilder.addNodeIDMachineOperand(MO: MachineOperand::CreateFPImm(CFP: &Val)); |
347 | MachineInstrBuilder MIB = getDominatingInstrForID(ID, NodeInsertPos&: InsertPos); |
348 | if (MIB) { |
349 | // Handle generating copies here. |
350 | return generateCopiesIfRequired(DstOps: {Res}, MIB); |
351 | } |
352 | MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val); |
353 | return memoizeMI(MIB: NewMIB, NodeInsertPos: InsertPos); |
354 | } |
355 | |