1//===-- SIOptimizeExecMasking.cpp -----------------------------------------===//
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
9#include "SIOptimizeExecMasking.h"
10#include "AMDGPU.h"
11#include "AMDGPULaneMaskUtils.h"
12#include "GCNSubtarget.h"
13#include "SIRegisterInfo.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/CodeGen/LiveRegUnits.h"
16#include "llvm/CodeGen/MachineFunctionPass.h"
17#include "llvm/CodeGen/MachineOperand.h"
18#include "llvm/CodeGen/TargetRegisterInfo.h"
19#include "llvm/InitializePasses.h"
20
21using namespace llvm;
22
23#define DEBUG_TYPE "si-optimize-exec-masking"
24
25namespace {
26
27class SIOptimizeExecMasking {
28public:
29 SIOptimizeExecMasking(MachineFunction *MF)
30 : MF(MF), ST(&MF->getSubtarget<GCNSubtarget>()), TII(ST->getInstrInfo()),
31 TRI(&TII->getRegisterInfo()), MRI(&MF->getRegInfo()),
32 LMC(AMDGPU::LaneMaskConstants::get(ST: *ST)) {}
33 bool run();
34
35private:
36 MachineFunction *MF;
37 const GCNSubtarget *ST;
38 const SIInstrInfo *TII;
39 const SIRegisterInfo *TRI;
40 const MachineRegisterInfo *MRI;
41 const AMDGPU::LaneMaskConstants &LMC;
42
43 DenseMap<MachineInstr *, MachineInstr *> SaveExecVCmpMapping;
44 SmallVector<std::pair<MachineInstr *, MachineInstr *>, 1> OrXors;
45
46 Register isCopyFromExec(const MachineInstr &MI) const;
47 Register isCopyToExec(const MachineInstr &MI) const;
48 bool removeTerminatorBit(MachineInstr &MI) const;
49 MachineBasicBlock::reverse_iterator
50 fixTerminators(MachineBasicBlock &MBB) const;
51 MachineBasicBlock::reverse_iterator
52 findExecCopy(MachineBasicBlock &MBB,
53 MachineBasicBlock::reverse_iterator I) const;
54 bool isRegisterInUseBetween(MachineInstr &Stop, MachineInstr &Start,
55 MCRegister Reg, bool UseLiveOuts = false,
56 bool IgnoreStart = false) const;
57 bool isRegisterInUseAfter(MachineInstr &Stop, MCRegister Reg) const;
58 MachineInstr *findInstrBackwards(
59 MachineInstr &Origin, std::function<bool(MachineInstr *)> Pred,
60 ArrayRef<MCRegister> NonModifiableRegs,
61 unsigned MaxInstructions = 20) const;
62 bool optimizeExecSequence();
63 bool blocksAndN2Sink(const MachineInstr &MI, Register Dst) const;
64 bool optimizeAndN2WrExecSequence(MachineInstr &CopyToExecInst,
65 Register Dst) const;
66 void tryRecordVCmpxAndSaveexecSequence(MachineInstr &MI);
67 bool optimizeVCMPSaveExecSequence(MachineInstr &SaveExecInstr,
68 MachineInstr &VCmp) const;
69
70 void tryRecordOrSaveexecXorSequence(MachineInstr &MI);
71 bool optimizeOrSaveexecXorSequences();
72};
73
74class SIOptimizeExecMaskingLegacy : public MachineFunctionPass {
75public:
76 static char ID;
77
78 SIOptimizeExecMaskingLegacy() : MachineFunctionPass(ID) {}
79
80 bool runOnMachineFunction(MachineFunction &MF) override;
81
82 StringRef getPassName() const override {
83 return "SI optimize exec mask operations";
84 }
85
86 void getAnalysisUsage(AnalysisUsage &AU) const override {
87 AU.setPreservesCFG();
88 MachineFunctionPass::getAnalysisUsage(AU);
89 }
90};
91
92} // End anonymous namespace.
93
94PreservedAnalyses
95SIOptimizeExecMaskingPass::run(MachineFunction &MF,
96 MachineFunctionAnalysisManager &) {
97 SIOptimizeExecMasking Impl(&MF);
98
99 if (!Impl.run())
100 return PreservedAnalyses::all();
101
102 auto PA = getMachineFunctionPassPreservedAnalyses();
103 PA.preserveSet<CFGAnalyses>();
104 return PA;
105}
106
107INITIALIZE_PASS_BEGIN(SIOptimizeExecMaskingLegacy, DEBUG_TYPE,
108 "SI optimize exec mask operations", false, false)
109INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
110INITIALIZE_PASS_END(SIOptimizeExecMaskingLegacy, DEBUG_TYPE,
111 "SI optimize exec mask operations", false, false)
112
113char SIOptimizeExecMaskingLegacy::ID = 0;
114
115char &llvm::SIOptimizeExecMaskingLegacyID = SIOptimizeExecMaskingLegacy::ID;
116
117/// If \p MI is a copy from exec, return the register copied to.
118Register SIOptimizeExecMasking::isCopyFromExec(const MachineInstr &MI) const {
119 switch (MI.getOpcode()) {
120 case AMDGPU::COPY:
121 case AMDGPU::S_MOV_B64:
122 case AMDGPU::S_MOV_B64_term:
123 case AMDGPU::S_MOV_B32:
124 case AMDGPU::S_MOV_B32_term: {
125 const MachineOperand &Src = MI.getOperand(i: 1);
126 if (Src.isReg() && Src.getReg() == LMC.ExecReg)
127 return MI.getOperand(i: 0).getReg();
128 }
129 }
130
131 return AMDGPU::NoRegister;
132}
133
134/// If \p MI is a copy to exec, return the register copied from.
135Register SIOptimizeExecMasking::isCopyToExec(const MachineInstr &MI) const {
136 switch (MI.getOpcode()) {
137 case AMDGPU::COPY:
138 case AMDGPU::S_MOV_B64:
139 case AMDGPU::S_MOV_B32: {
140 const MachineOperand &Dst = MI.getOperand(i: 0);
141 if (Dst.isReg() && Dst.getReg() == LMC.ExecReg && MI.getOperand(i: 1).isReg())
142 return MI.getOperand(i: 1).getReg();
143 break;
144 }
145 case AMDGPU::S_MOV_B64_term:
146 case AMDGPU::S_MOV_B32_term:
147 llvm_unreachable("should have been replaced");
148 }
149
150 return Register();
151}
152
153/// If \p MI is a logical operation on an exec value,
154/// return the register copied to.
155static Register isLogicalOpOnExec(const MachineInstr &MI) {
156 switch (MI.getOpcode()) {
157 case AMDGPU::S_AND_B64:
158 case AMDGPU::S_OR_B64:
159 case AMDGPU::S_XOR_B64:
160 case AMDGPU::S_ANDN2_B64:
161 case AMDGPU::S_ORN2_B64:
162 case AMDGPU::S_NAND_B64:
163 case AMDGPU::S_NOR_B64:
164 case AMDGPU::S_XNOR_B64: {
165 const MachineOperand &Src1 = MI.getOperand(i: 1);
166 if (Src1.isReg() && Src1.getReg() == AMDGPU::EXEC)
167 return MI.getOperand(i: 0).getReg();
168 const MachineOperand &Src2 = MI.getOperand(i: 2);
169 if (Src2.isReg() && Src2.getReg() == AMDGPU::EXEC)
170 return MI.getOperand(i: 0).getReg();
171 break;
172 }
173 case AMDGPU::S_AND_B32:
174 case AMDGPU::S_OR_B32:
175 case AMDGPU::S_XOR_B32:
176 case AMDGPU::S_ANDN2_B32:
177 case AMDGPU::S_ORN2_B32:
178 case AMDGPU::S_NAND_B32:
179 case AMDGPU::S_NOR_B32:
180 case AMDGPU::S_XNOR_B32: {
181 const MachineOperand &Src1 = MI.getOperand(i: 1);
182 if (Src1.isReg() && Src1.getReg() == AMDGPU::EXEC_LO)
183 return MI.getOperand(i: 0).getReg();
184 const MachineOperand &Src2 = MI.getOperand(i: 2);
185 if (Src2.isReg() && Src2.getReg() == AMDGPU::EXEC_LO)
186 return MI.getOperand(i: 0).getReg();
187 break;
188 }
189 }
190
191 return AMDGPU::NoRegister;
192}
193
194static unsigned getSaveExecOp(unsigned Opc) {
195 switch (Opc) {
196 case AMDGPU::S_AND_B64:
197 return AMDGPU::S_AND_SAVEEXEC_B64;
198 case AMDGPU::S_OR_B64:
199 return AMDGPU::S_OR_SAVEEXEC_B64;
200 case AMDGPU::S_XOR_B64:
201 return AMDGPU::S_XOR_SAVEEXEC_B64;
202 case AMDGPU::S_ANDN2_B64:
203 return AMDGPU::S_ANDN2_SAVEEXEC_B64;
204 case AMDGPU::S_ORN2_B64:
205 return AMDGPU::S_ORN2_SAVEEXEC_B64;
206 case AMDGPU::S_NAND_B64:
207 return AMDGPU::S_NAND_SAVEEXEC_B64;
208 case AMDGPU::S_NOR_B64:
209 return AMDGPU::S_NOR_SAVEEXEC_B64;
210 case AMDGPU::S_XNOR_B64:
211 return AMDGPU::S_XNOR_SAVEEXEC_B64;
212 case AMDGPU::S_AND_B32:
213 return AMDGPU::S_AND_SAVEEXEC_B32;
214 case AMDGPU::S_OR_B32:
215 return AMDGPU::S_OR_SAVEEXEC_B32;
216 case AMDGPU::S_XOR_B32:
217 return AMDGPU::S_XOR_SAVEEXEC_B32;
218 case AMDGPU::S_ANDN2_B32:
219 return AMDGPU::S_ANDN2_SAVEEXEC_B32;
220 case AMDGPU::S_ORN2_B32:
221 return AMDGPU::S_ORN2_SAVEEXEC_B32;
222 case AMDGPU::S_NAND_B32:
223 return AMDGPU::S_NAND_SAVEEXEC_B32;
224 case AMDGPU::S_NOR_B32:
225 return AMDGPU::S_NOR_SAVEEXEC_B32;
226 case AMDGPU::S_XNOR_B32:
227 return AMDGPU::S_XNOR_SAVEEXEC_B32;
228 default:
229 return AMDGPU::INSTRUCTION_LIST_END;
230 }
231}
232
233// These are only terminators to get correct spill code placement during
234// register allocation, so turn them back into normal instructions.
235bool SIOptimizeExecMasking::removeTerminatorBit(MachineInstr &MI) const {
236 switch (MI.getOpcode()) {
237 case AMDGPU::S_MOV_B32_term: {
238 bool RegSrc = MI.getOperand(i: 1).isReg();
239 MI.setDesc(TII->get(Opcode: RegSrc ? AMDGPU::COPY : AMDGPU::S_MOV_B32));
240 return true;
241 }
242 case AMDGPU::S_MOV_B64_term: {
243 bool RegSrc = MI.getOperand(i: 1).isReg();
244 MI.setDesc(TII->get(Opcode: RegSrc ? AMDGPU::COPY : AMDGPU::S_MOV_B64));
245 return true;
246 }
247 case AMDGPU::S_XOR_B64_term: {
248 // This is only a terminator to get the correct spill code placement during
249 // register allocation.
250 MI.setDesc(TII->get(Opcode: AMDGPU::S_XOR_B64));
251 return true;
252 }
253 case AMDGPU::S_XOR_B32_term: {
254 // This is only a terminator to get the correct spill code placement during
255 // register allocation.
256 MI.setDesc(TII->get(Opcode: AMDGPU::S_XOR_B32));
257 return true;
258 }
259 case AMDGPU::S_OR_B64_term: {
260 // This is only a terminator to get the correct spill code placement during
261 // register allocation.
262 MI.setDesc(TII->get(Opcode: AMDGPU::S_OR_B64));
263 return true;
264 }
265 case AMDGPU::S_OR_B32_term: {
266 // This is only a terminator to get the correct spill code placement during
267 // register allocation.
268 MI.setDesc(TII->get(Opcode: AMDGPU::S_OR_B32));
269 return true;
270 }
271 case AMDGPU::S_ANDN2_B64_term: {
272 // This is only a terminator to get the correct spill code placement during
273 // register allocation.
274 MI.setDesc(TII->get(Opcode: AMDGPU::S_ANDN2_B64));
275 return true;
276 }
277 case AMDGPU::S_ANDN2_B32_term: {
278 // This is only a terminator to get the correct spill code placement during
279 // register allocation.
280 MI.setDesc(TII->get(Opcode: AMDGPU::S_ANDN2_B32));
281 return true;
282 }
283 case AMDGPU::S_AND_B64_term: {
284 // This is only a terminator to get the correct spill code placement during
285 // register allocation.
286 MI.setDesc(TII->get(Opcode: AMDGPU::S_AND_B64));
287 return true;
288 }
289 case AMDGPU::S_AND_B32_term: {
290 // This is only a terminator to get the correct spill code placement during
291 // register allocation.
292 MI.setDesc(TII->get(Opcode: AMDGPU::S_AND_B32));
293 return true;
294 }
295 case AMDGPU::V_CMPX_EQ_U32_nosdst_e32_term:
296 MI.setDesc(TII->get(Opcode: AMDGPU::V_CMPX_EQ_U32_nosdst_e32));
297 return true;
298 case AMDGPU::V_CMPX_EQ_U64_nosdst_e32_term:
299 MI.setDesc(TII->get(Opcode: AMDGPU::V_CMPX_EQ_U64_nosdst_e32));
300 return true;
301 default:
302 return false;
303 }
304}
305
306// Turn all pseudoterminators in the block into their equivalent non-terminator
307// instructions. Returns the reverse iterator to the first non-terminator
308// instruction in the block.
309MachineBasicBlock::reverse_iterator
310SIOptimizeExecMasking::fixTerminators(MachineBasicBlock &MBB) const {
311 MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend();
312
313 bool Seen = false;
314 MachineBasicBlock::reverse_iterator FirstNonTerm = I;
315 for (; I != E; ++I) {
316 if (!I->isTerminator())
317 return Seen ? FirstNonTerm : I;
318
319 if (removeTerminatorBit(MI&: *I)) {
320 if (!Seen) {
321 FirstNonTerm = I;
322 Seen = true;
323 }
324 }
325 }
326
327 return FirstNonTerm;
328}
329
330MachineBasicBlock::reverse_iterator SIOptimizeExecMasking::findExecCopy(
331 MachineBasicBlock &MBB, MachineBasicBlock::reverse_iterator I) const {
332 const unsigned InstLimit = 25;
333
334 auto E = MBB.rend();
335 for (unsigned N = 0; N <= InstLimit && I != E; ++I) {
336 if (I->isDebugInstr())
337 continue;
338 ++N;
339
340 Register CopyFromExec = isCopyFromExec(MI: *I);
341 if (CopyFromExec.isValid())
342 return I;
343 }
344
345 return E;
346}
347
348// XXX - Seems LiveRegUnits doesn't work correctly since it will incorrectly
349// report the register as unavailable because a super-register with a lane mask
350// is unavailable.
351static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg) {
352 for (MachineBasicBlock *Succ : MBB.successors()) {
353 if (Succ->isLiveIn(Reg))
354 return true;
355 }
356
357 return false;
358}
359
360// Backwards-iterate from Origin (for n=MaxInstructions iterations) until either
361// the beginning of the BB is reached or Pred evaluates to true - which can be
362// an arbitrary condition based on the current MachineInstr, for instance an
363// target instruction. Breaks prematurely by returning nullptr if one of the
364// registers given in NonModifiableRegs is modified by the current instruction.
365MachineInstr *SIOptimizeExecMasking::findInstrBackwards(
366 MachineInstr &Origin, std::function<bool(MachineInstr *)> Pred,
367 ArrayRef<MCRegister> NonModifiableRegs, unsigned MaxInstructions) const {
368 MachineBasicBlock::reverse_iterator A = Origin.getReverseIterator(),
369 E = Origin.getParent()->rend();
370 unsigned CurrentIteration = 0;
371
372 for (++A; CurrentIteration < MaxInstructions && A != E; ++A) {
373 if (A->isDebugInstr())
374 continue;
375
376 if (Pred(&*A))
377 return &*A;
378
379 for (MCRegister Reg : NonModifiableRegs) {
380 if (A->modifiesRegister(Reg, TRI))
381 return nullptr;
382 }
383
384 ++CurrentIteration;
385 }
386
387 return nullptr;
388}
389
390// Determine if a register Reg is not re-defined and still in use
391// in the range (Stop..Start].
392// It does so by backwards calculating liveness from the end of the BB until
393// either Stop or the beginning of the BB is reached.
394// After liveness is calculated, we can determine if Reg is still in use and not
395// defined inbetween the instructions.
396bool SIOptimizeExecMasking::isRegisterInUseBetween(MachineInstr &Stop,
397 MachineInstr &Start,
398 MCRegister Reg,
399 bool UseLiveOuts,
400 bool IgnoreStart) const {
401 LiveRegUnits LR(*TRI);
402 if (UseLiveOuts)
403 LR.addLiveOuts(MBB: *Stop.getParent());
404
405 MachineBasicBlock::reverse_iterator A(Start);
406
407 if (IgnoreStart)
408 ++A;
409
410 for (; A != Stop.getParent()->rend() && A != Stop; ++A) {
411 if (!A->isDebugInstr())
412 LR.stepBackward(MI: *A);
413 }
414
415 return !LR.available(Reg) || MRI->isReserved(PhysReg: Reg);
416}
417
418// Determine if a register Reg is not re-defined and still in use
419// in the range (Stop..BB.end].
420bool SIOptimizeExecMasking::isRegisterInUseAfter(MachineInstr &Stop,
421 MCRegister Reg) const {
422 return isRegisterInUseBetween(Stop, Start&: *Stop.getParent()->rbegin(), Reg, UseLiveOuts: true);
423}
424
425// Optimize sequences emitted for control flow lowering. They are originally
426// emitted as the separate operations because spill code may need to be
427// inserted for the saved copy of exec.
428//
429// x = copy exec
430// z = s_<op>_b64 x, y
431// exec = copy z
432// =>
433// x = s_<op>_saveexec_b64 y
434//
435bool SIOptimizeExecMasking::optimizeExecSequence() {
436 bool Changed = false;
437 for (MachineBasicBlock &MBB : *MF) {
438 MachineBasicBlock::reverse_iterator I = fixTerminators(MBB);
439 MachineBasicBlock::reverse_iterator E = MBB.rend();
440 if (I == E)
441 continue;
442
443 // It's possible to see other terminator copies after the exec copy. This
444 // can happen if control flow pseudos had their outputs used by phis.
445 Register CopyToExec;
446
447 for (unsigned SearchCount = 0, SearchLimit = 5;
448 I != E && SearchCount < SearchLimit; ++I) {
449 if (I->isDebugInstr())
450 continue;
451 ++SearchCount;
452 CopyToExec = isCopyToExec(MI: *I);
453 if (CopyToExec)
454 break;
455 }
456
457 if (!CopyToExec)
458 continue;
459
460 // Scan backwards to find the def.
461 auto *CopyToExecInst = &*I;
462 auto CopyFromExecInst = findExecCopy(MBB, I);
463 if (CopyFromExecInst == E) {
464 auto PrepareExecInst = next_nodbg(It: I, End: E);
465 if (PrepareExecInst == E)
466 continue;
467 // Fold exec = COPY (S_AND_B64 reg, exec) -> exec = S_AND_B64 reg, exec
468 if (CopyToExecInst->getOperand(i: 1).isKill() &&
469 isLogicalOpOnExec(MI: *PrepareExecInst) == CopyToExec) {
470 LLVM_DEBUG(dbgs() << "Fold exec copy: " << *PrepareExecInst);
471
472 PrepareExecInst->getOperand(i: 0).setReg(LMC.ExecReg);
473
474 LLVM_DEBUG(dbgs() << "into: " << *PrepareExecInst << '\n');
475
476 CopyToExecInst->eraseFromParent();
477 Changed = true;
478 } else if (optimizeAndN2WrExecSequence(CopyToExecInst&: *CopyToExecInst, Dst: CopyToExec)) {
479 Changed = true;
480 }
481
482 continue;
483 }
484
485 if (isLiveOut(MBB, Reg: CopyToExec)) {
486 // The copied register is live out and has a second use in another block.
487 LLVM_DEBUG(dbgs() << "Exec copy source register is live out\n");
488 continue;
489 }
490
491 Register CopyFromExec = CopyFromExecInst->getOperand(i: 0).getReg();
492 MachineInstr *SaveExecInst = nullptr;
493 SmallVector<MachineInstr *, 4> OtherUseInsts;
494
495 for (MachineBasicBlock::iterator
496 J = std::next(x: CopyFromExecInst->getIterator()),
497 JE = I->getIterator();
498 J != JE; ++J) {
499 if (J->isDebugInstr())
500 continue;
501
502 if (SaveExecInst && J->readsRegister(Reg: LMC.ExecReg, TRI)) {
503 LLVM_DEBUG(dbgs() << "exec read prevents saveexec: " << *J << '\n');
504 // Make sure this is inserted after any VALU ops that may have been
505 // scheduled in between.
506 SaveExecInst = nullptr;
507 break;
508 }
509
510 bool ReadsCopyFromExec = J->readsRegister(Reg: CopyFromExec, TRI);
511
512 if (J->modifiesRegister(Reg: CopyToExec, TRI)) {
513 if (SaveExecInst) {
514 LLVM_DEBUG(dbgs() << "Multiple instructions modify "
515 << printReg(CopyToExec, TRI) << '\n');
516 SaveExecInst = nullptr;
517 break;
518 }
519
520 unsigned SaveExecOp = getSaveExecOp(Opc: J->getOpcode());
521 if (SaveExecOp == AMDGPU::INSTRUCTION_LIST_END)
522 break;
523
524 if (ReadsCopyFromExec) {
525 SaveExecInst = &*J;
526 LLVM_DEBUG(dbgs() << "Found save exec op: " << *SaveExecInst << '\n');
527 continue;
528 }
529 LLVM_DEBUG(dbgs() << "Instruction does not read exec copy: " << *J
530 << '\n');
531 break;
532 }
533 if (ReadsCopyFromExec && !SaveExecInst) {
534 // Make sure no other instruction is trying to use this copy, before it
535 // will be rewritten by the saveexec, i.e. hasOneUse. There may have
536 // been another use, such as an inserted spill. For example:
537 //
538 // %sgpr0_sgpr1 = COPY %exec
539 // spill %sgpr0_sgpr1
540 // %sgpr2_sgpr3 = S_AND_B64 %sgpr0_sgpr1
541 //
542 LLVM_DEBUG(dbgs() << "Found second use of save inst candidate: " << *J
543 << '\n');
544 break;
545 }
546
547 if (SaveExecInst && J->readsRegister(Reg: CopyToExec, TRI)) {
548 assert(SaveExecInst != &*J);
549 OtherUseInsts.push_back(Elt: &*J);
550 }
551 }
552
553 if (!SaveExecInst)
554 continue;
555
556 LLVM_DEBUG(dbgs() << "Insert save exec op: " << *SaveExecInst << '\n');
557
558 MachineOperand &Src0 = SaveExecInst->getOperand(i: 1);
559 MachineOperand &Src1 = SaveExecInst->getOperand(i: 2);
560
561 MachineOperand *OtherOp = nullptr;
562
563 if (Src0.isReg() && Src0.getReg() == CopyFromExec) {
564 OtherOp = &Src1;
565 } else if (Src1.isReg() && Src1.getReg() == CopyFromExec) {
566 if (!SaveExecInst->isCommutable())
567 break;
568
569 OtherOp = &Src0;
570 } else
571 llvm_unreachable("unexpected");
572
573 CopyFromExecInst->eraseFromParent();
574
575 auto InsPt = SaveExecInst->getIterator();
576 const DebugLoc &DL = SaveExecInst->getDebugLoc();
577
578 BuildMI(BB&: MBB, I: InsPt, MIMD: DL, MCID: TII->get(Opcode: getSaveExecOp(Opc: SaveExecInst->getOpcode())),
579 DestReg: CopyFromExec)
580 .addReg(RegNo: OtherOp->getReg());
581 SaveExecInst->eraseFromParent();
582
583 CopyToExecInst->eraseFromParent();
584
585 for (MachineInstr *OtherInst : OtherUseInsts) {
586 OtherInst->substituteRegister(FromReg: CopyToExec, ToReg: LMC.ExecReg,
587 SubIdx: AMDGPU::NoSubRegister, RegInfo: *TRI);
588 }
589
590 Changed = true;
591 }
592
593 return Changed;
594}
595
596bool SIOptimizeExecMasking::blocksAndN2Sink(const MachineInstr &MI,
597 Register Dst) const {
598 for (const MachineOperand &MO : MI.operands()) {
599 if (!MO.isReg())
600 continue;
601 // Any access to Dst would see a stale value once the def sinks past it,
602 // and a use of SCC would see the s_andn2 result.
603 if (TRI->regsOverlap(RegA: MO.getReg(), RegB: Dst))
604 return true;
605 if (MO.isUse() && MO.getReg() == AMDGPU::SCC)
606 return true;
607 }
608 return false;
609}
610
611// Fold
612//
613// sdst = S_ANDN2_B32 ssrc, exec
614// exec = COPY sdst
615// =>
616// sdst = S_ANDN2_WREXEC_B32 ssrc
617//
618// The waterfall loop emits the two operations separately so that spill code
619// for sdst can be inserted before exec is narrowed.
620bool SIOptimizeExecMasking::optimizeAndN2WrExecSequence(
621 MachineInstr &CopyToExecInst, Register Dst) const {
622 if (!ST->hasNoSdstCMPX() || TII->pseudoToMCOpcode(Opcode: LMC.AndN2WrExecOpc) == -1)
623 return false;
624
625 MachineBasicBlock &MBB = *CopyToExecInst.getParent();
626
627 // Keep the fused instruction ahead of any trailing debug instructions, so
628 // DBG_VALUEs of Dst stay after its def.
629 MachineBasicBlock::iterator InsertPt = CopyToExecInst.getIterator();
630 if (InsertPt != MBB.begin())
631 InsertPt = std::next(x: prev_nodbg(It: InsertPt, Begin: MBB.begin()));
632
633 // Scan back for the s_andn2 computing the new exec value. The scheduler may
634 // have moved it away from the exec write, so allow instructions in between
635 // as long as sinking the s_andn2 past them is safe.
636 auto IsAndN2Def = [&](const MachineInstr &MI) {
637 return MI.getOpcode() == LMC.AndN2Opc && MI.getOperand(i: 0).getReg() == Dst;
638 };
639 MachineInstr *AndN2Inst = findInstrBackwards(
640 Origin&: CopyToExecInst,
641 Pred: [&](MachineInstr *Check) {
642 return IsAndN2Def(*Check) || blocksAndN2Sink(MI: *Check, Dst);
643 },
644 /*NonModifiableRegs=*/{});
645 if (!AndN2Inst || !IsAndN2Def(*AndN2Inst))
646 return false;
647
648 const MachineOperand &Src = AndN2Inst->getOperand(i: 1);
649 const MachineOperand &Mask = AndN2Inst->getOperand(i: 2);
650 if (!Src.isReg() || !Mask.isReg() || Mask.getReg() != LMC.ExecReg)
651 return false;
652
653 for (MachineInstr &MI : make_range(
654 x: std::next(x: MachineBasicBlock::iterator(AndN2Inst)), y: InsertPt)) {
655 if (MI.modifiesRegister(Reg: Src.getReg(), TRI))
656 return false;
657 }
658
659 // The fused form also clobbers SCC, at the point the s_andn2 is moved to.
660 if (isRegisterInUseAfter(Stop&: CopyToExecInst, Reg: AMDGPU::SCC))
661 return false;
662
663 LLVM_DEBUG(dbgs() << "Fold exec write: " << *AndN2Inst);
664
665 BuildMI(BB&: MBB, I: InsertPt, MIMD: AndN2Inst->getDebugLoc(), MCID: TII->get(Opcode: LMC.AndN2WrExecOpc),
666 DestReg: Dst)
667 .addReg(RegNo: Src.getReg());
668
669 AndN2Inst->eraseFromParent();
670 CopyToExecInst.eraseFromParent();
671 return true;
672}
673
674// Inserts the optimized s_mov_b32 / v_cmpx sequence based on the
675// operands extracted from a v_cmp ..., s_and_saveexec pattern.
676bool SIOptimizeExecMasking::optimizeVCMPSaveExecSequence(
677 MachineInstr &SaveExecInstr, MachineInstr &VCmp) const {
678 const int NewOpcode = AMDGPU::getVCMPXOpFromVCMP(Opcode: VCmp.getOpcode());
679
680 if (NewOpcode == -1)
681 return false;
682
683 MachineOperand *Src0 = TII->getNamedOperand(MI&: VCmp, OperandName: AMDGPU::OpName::src0);
684 MachineOperand *Src1 = TII->getNamedOperand(MI&: VCmp, OperandName: AMDGPU::OpName::src1);
685
686 // Kills of the sources between the v_cmp and the saveexec are no longer
687 // valid once the compare is moved to the saveexec.
688 for (MachineInstr &MI :
689 make_range(x: std::next(x: VCmp.getIterator()), y: SaveExecInstr.getIterator())) {
690 for (MachineOperand &MO : MI.all_uses()) {
691 if (MO.isKill() &&
692 any_of(Range: std::array{Src0, Src1}, P: [&](const MachineOperand *Src) {
693 return Src->isReg() && TRI->regsOverlap(RegA: MO.getReg(), RegB: Src->getReg());
694 }))
695 MO.setIsKill(false);
696 }
697 }
698
699 Register MoveDest = SaveExecInstr.getOperand(i: 0).getReg();
700
701 MachineBasicBlock::instr_iterator InsertPosIt = SaveExecInstr.getIterator();
702 if (!SaveExecInstr.uses().empty()) {
703 bool IsSGPR32 = TRI->getRegSizeInBits(Reg: MoveDest, MRI: *MRI) == 32;
704 unsigned MovOpcode = IsSGPR32 ? AMDGPU::S_MOV_B32 : AMDGPU::S_MOV_B64;
705 BuildMI(BB&: *SaveExecInstr.getParent(), I: InsertPosIt,
706 MIMD: SaveExecInstr.getDebugLoc(), MCID: TII->get(Opcode: MovOpcode), DestReg: MoveDest)
707 .addReg(RegNo: LMC.ExecReg);
708 }
709
710 // Omit dst as V_CMPX is implicitly writing to EXEC.
711 // Add dummy src and clamp modifiers, if needed.
712 auto Builder = BuildMI(BB&: *VCmp.getParent(), I: std::next(x: InsertPosIt),
713 MIMD: VCmp.getDebugLoc(), MCID: TII->get(Opcode: NewOpcode));
714
715 auto TryAddImmediateValueFromNamedOperand =
716 [&](AMDGPU::OpName OperandName) -> void {
717 if (auto *Mod = TII->getNamedOperand(MI&: VCmp, OperandName))
718 Builder.addImm(Val: Mod->getImm());
719 };
720
721 TryAddImmediateValueFromNamedOperand(AMDGPU::OpName::src0_modifiers);
722 Builder.add(MO: *Src0);
723
724 TryAddImmediateValueFromNamedOperand(AMDGPU::OpName::src1_modifiers);
725 Builder.add(MO: *Src1);
726
727 TryAddImmediateValueFromNamedOperand(AMDGPU::OpName::clamp);
728
729 TryAddImmediateValueFromNamedOperand(AMDGPU::OpName::op_sel);
730
731 SaveExecInstr.eraseFromParent();
732 VCmp.eraseFromParent();
733
734 return true;
735}
736
737// Record (on GFX10.3 and later) occurences of
738// v_cmp_* SGPR, IMM, VGPR
739// s_and_saveexec_b32 EXEC_SGPR_DEST, SGPR
740// to be replaced with
741// s_mov_b32 EXEC_SGPR_DEST, exec_lo
742// v_cmpx_* IMM, VGPR
743// to reduce pipeline stalls.
744void SIOptimizeExecMasking::tryRecordVCmpxAndSaveexecSequence(
745 MachineInstr &MI) {
746 if (!ST->hasGFX10_3Insts())
747 return;
748
749 if (MI.getOpcode() != LMC.AndSaveExecOpc)
750 return;
751
752 Register SaveExecDest = MI.getOperand(i: 0).getReg();
753 if (!TRI->isSGPRReg(MRI: *MRI, Reg: SaveExecDest))
754 return;
755
756 MachineOperand *SaveExecSrc0 = TII->getNamedOperand(MI, OperandName: AMDGPU::OpName::src0);
757 if (!SaveExecSrc0->isReg())
758 return;
759
760 // Tries to find a possibility to optimize a v_cmp ..., s_and_saveexec
761 // sequence by looking at an instance of an s_and_saveexec instruction.
762 // Returns a pointer to the v_cmp instruction if it is safe to replace the
763 // sequence (see the conditions in the function body). This is after register
764 // allocation, so some checks on operand dependencies need to be considered.
765 MachineInstr *VCmp = nullptr;
766
767 // Try to find the last v_cmp instruction that defs the saveexec input
768 // operand without any write to Exec or the saveexec input operand inbetween.
769 VCmp = findInstrBackwards(
770 Origin&: MI,
771 Pred: [&](MachineInstr *Check) {
772 return AMDGPU::getVCMPXOpFromVCMP(Opcode: Check->getOpcode()) != -1 &&
773 Check->modifiesRegister(Reg: SaveExecSrc0->getReg(), TRI);
774 },
775 NonModifiableRegs: {LMC.ExecReg, SaveExecSrc0->getReg()});
776
777 if (!VCmp)
778 return;
779
780 MachineOperand *VCmpDest = TII->getNamedOperand(MI&: *VCmp, OperandName: AMDGPU::OpName::sdst);
781 assert(VCmpDest && "Should have an sdst operand!");
782
783 // Check if any of the v_cmp source operands is written by the saveexec.
784 MachineOperand *Src0 = TII->getNamedOperand(MI&: *VCmp, OperandName: AMDGPU::OpName::src0);
785 if (Src0->isReg() && TRI->isSGPRReg(MRI: *MRI, Reg: Src0->getReg()) &&
786 MI.modifiesRegister(Reg: Src0->getReg(), TRI))
787 return;
788
789 MachineOperand *Src1 = TII->getNamedOperand(MI&: *VCmp, OperandName: AMDGPU::OpName::src1);
790 if (Src1->isReg() && TRI->isSGPRReg(MRI: *MRI, Reg: Src1->getReg()) &&
791 MI.modifiesRegister(Reg: Src1->getReg(), TRI))
792 return;
793
794 // Don't do the transformation if the destination operand is included in
795 // it's MBB Live-outs, meaning it's used in any of its successors, leading
796 // to incorrect code if the v_cmp and therefore the def of
797 // the dest operand is removed.
798 if (isLiveOut(MBB: *VCmp->getParent(), Reg: VCmpDest->getReg()))
799 return;
800
801 // If the v_cmp target is in use between v_cmp and s_and_saveexec or after the
802 // s_and_saveexec, skip the optimization.
803 if (isRegisterInUseBetween(Stop&: *VCmp, Start&: MI, Reg: VCmpDest->getReg(), UseLiveOuts: false, IgnoreStart: true) ||
804 isRegisterInUseAfter(Stop&: MI, Reg: VCmpDest->getReg()))
805 return;
806
807 // Try to determine if there is a write to any of the VCmp
808 // operands between the saveexec and the vcmp.
809 // If yes, additional VGPR spilling might need to be inserted. In this case,
810 // it's not worth replacing the instruction sequence.
811 SmallVector<MCRegister, 2> NonDefRegs;
812 if (Src0->isReg())
813 NonDefRegs.push_back(Elt: Src0->getReg());
814
815 if (Src1->isReg())
816 NonDefRegs.push_back(Elt: Src1->getReg());
817
818 if (!findInstrBackwards(
819 Origin&: MI, Pred: [&](MachineInstr *Check) { return Check == VCmp; }, NonModifiableRegs: NonDefRegs))
820 return;
821
822 SaveExecVCmpMapping[&MI] = VCmp;
823}
824
825// Record occurences of
826// s_or_saveexec s_o, s_i
827// s_xor exec, exec, s_o
828// to be replaced with
829// s_andn2_saveexec s_o, s_i.
830void SIOptimizeExecMasking::tryRecordOrSaveexecXorSequence(MachineInstr &MI) {
831 if (MI.getOpcode() == LMC.XorOpc && &MI != &MI.getParent()->front()) {
832 const MachineOperand &XorDst = MI.getOperand(i: 0);
833 const MachineOperand &XorSrc0 = MI.getOperand(i: 1);
834 const MachineOperand &XorSrc1 = MI.getOperand(i: 2);
835
836 if (XorDst.isReg() && XorDst.getReg() == LMC.ExecReg && XorSrc0.isReg() &&
837 XorSrc1.isReg() &&
838 (XorSrc0.getReg() == LMC.ExecReg || XorSrc1.getReg() == LMC.ExecReg)) {
839
840 // Peek at the previous non-debug instruction and check if this is a
841 // relevant s_or_saveexec instruction.
842 auto It = prev_nodbg(It: MI.getIterator(), Begin: MI.getParent()->instr_begin());
843 MachineInstr &PossibleOrSaveexec = *It;
844 if (PossibleOrSaveexec.getOpcode() != LMC.OrSaveExecOpc)
845 return;
846
847 const MachineOperand &OrDst = PossibleOrSaveexec.getOperand(i: 0);
848 const MachineOperand &OrSrc0 = PossibleOrSaveexec.getOperand(i: 1);
849 if (OrDst.isReg() && OrSrc0.isReg()) {
850 if ((XorSrc0.getReg() == LMC.ExecReg &&
851 XorSrc1.getReg() == OrDst.getReg()) ||
852 (XorSrc0.getReg() == OrDst.getReg() &&
853 XorSrc1.getReg() == LMC.ExecReg)) {
854 OrXors.emplace_back(Args: &PossibleOrSaveexec, Args: &MI);
855 }
856 }
857 }
858 }
859}
860
861bool SIOptimizeExecMasking::optimizeOrSaveexecXorSequences() {
862 if (OrXors.empty()) {
863 return false;
864 }
865
866 bool Changed = false;
867
868 for (const auto &Pair : OrXors) {
869 MachineInstr *Or = nullptr;
870 MachineInstr *Xor = nullptr;
871 std::tie(args&: Or, args&: Xor) = Pair;
872 BuildMI(BB&: *Or->getParent(), I: Or->getIterator(), MIMD: Or->getDebugLoc(),
873 MCID: TII->get(Opcode: LMC.AndN2SaveExecOpc), DestReg: Or->getOperand(i: 0).getReg())
874 .addReg(RegNo: Or->getOperand(i: 1).getReg());
875
876 Or->eraseFromParent();
877 Xor->eraseFromParent();
878
879 Changed = true;
880 }
881
882 return Changed;
883}
884
885bool SIOptimizeExecMaskingLegacy::runOnMachineFunction(MachineFunction &MF) {
886 if (skipFunction(F: MF.getFunction()))
887 return false;
888
889 return SIOptimizeExecMasking(&MF).run();
890}
891
892bool SIOptimizeExecMasking::run() {
893 bool Changed = optimizeExecSequence();
894
895 OrXors.clear();
896 SaveExecVCmpMapping.clear();
897 static unsigned SearchWindow = 10;
898 for (MachineBasicBlock &MBB : *MF) {
899 unsigned SearchCount = 0;
900
901 for (auto &MI : llvm::reverse(C&: MBB)) {
902 if (MI.isDebugInstr())
903 continue;
904
905 if (SearchCount >= SearchWindow) {
906 break;
907 }
908
909 tryRecordOrSaveexecXorSequence(MI);
910 tryRecordVCmpxAndSaveexecSequence(MI);
911
912 if (MI.modifiesRegister(Reg: LMC.ExecReg, TRI)) {
913 break;
914 }
915
916 ++SearchCount;
917 }
918 }
919
920 Changed |= optimizeOrSaveexecXorSequences();
921 for (const auto &Entry : SaveExecVCmpMapping) {
922 MachineInstr *SaveExecInstr = Entry.getFirst();
923 MachineInstr *VCmpInstr = Entry.getSecond();
924
925 Changed |= optimizeVCMPSaveExecSequence(SaveExecInstr&: *SaveExecInstr, VCmp&: *VCmpInstr);
926 }
927
928 return Changed;
929}
930