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 "AMDGPU.h"
10 #include "AMDGPUSubtarget.h"
11 #include "SIInstrInfo.h"
12 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
13 #include "llvm/ADT/SmallSet.h"
14 #include "llvm/CodeGen/MachineFunctionPass.h"
15 #include "llvm/CodeGen/MachineInstrBuilder.h"
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
17 #include "llvm/Support/Debug.h"
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "si-optimize-exec-masking"
22 
23 namespace {
24 
25 class SIOptimizeExecMasking : public MachineFunctionPass {
26 public:
27   static char ID;
28 
29 public:
30   SIOptimizeExecMasking() : MachineFunctionPass(ID) {
31     initializeSIOptimizeExecMaskingPass(*PassRegistry::getPassRegistry());
32   }
33 
34   bool runOnMachineFunction(MachineFunction &MF) override;
35 
36   StringRef getPassName() const override {
37     return "SI optimize exec mask operations";
38   }
39 
40   void getAnalysisUsage(AnalysisUsage &AU) const override {
41     AU.setPreservesCFG();
42     MachineFunctionPass::getAnalysisUsage(AU);
43   }
44 };
45 
46 } // End anonymous namespace.
47 
48 INITIALIZE_PASS_BEGIN(SIOptimizeExecMasking, DEBUG_TYPE,
49                       "SI optimize exec mask operations", false, false)
50 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
51 INITIALIZE_PASS_END(SIOptimizeExecMasking, DEBUG_TYPE,
52                     "SI optimize exec mask operations", false, false)
53 
54 char SIOptimizeExecMasking::ID = 0;
55 
56 char &llvm::SIOptimizeExecMaskingID = SIOptimizeExecMasking::ID;
57 
58 /// If \p MI is a copy from exec, return the register copied to.
59 static unsigned isCopyFromExec(const MachineInstr &MI, const GCNSubtarget &ST) {
60   switch (MI.getOpcode()) {
61   case AMDGPU::COPY:
62   case AMDGPU::S_MOV_B64:
63   case AMDGPU::S_MOV_B64_term:
64   case AMDGPU::S_MOV_B32:
65   case AMDGPU::S_MOV_B32_term: {
66     const MachineOperand &Src = MI.getOperand(1);
67     if (Src.isReg() &&
68         Src.getReg() == (ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC))
69       return MI.getOperand(0).getReg();
70   }
71   }
72 
73   return AMDGPU::NoRegister;
74 }
75 
76 /// If \p MI is a copy to exec, return the register copied from.
77 static unsigned isCopyToExec(const MachineInstr &MI, const GCNSubtarget &ST) {
78   switch (MI.getOpcode()) {
79   case AMDGPU::COPY:
80   case AMDGPU::S_MOV_B64:
81   case AMDGPU::S_MOV_B32: {
82     const MachineOperand &Dst = MI.getOperand(0);
83     if (Dst.isReg() &&
84         Dst.getReg() == (ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC) &&
85         MI.getOperand(1).isReg())
86       return MI.getOperand(1).getReg();
87     break;
88   }
89   case AMDGPU::S_MOV_B64_term:
90   case AMDGPU::S_MOV_B32_term:
91     llvm_unreachable("should have been replaced");
92   }
93 
94   return AMDGPU::NoRegister;
95 }
96 
97 /// If \p MI is a logical operation on an exec value,
98 /// return the register copied to.
99 static unsigned isLogicalOpOnExec(const MachineInstr &MI) {
100   switch (MI.getOpcode()) {
101   case AMDGPU::S_AND_B64:
102   case AMDGPU::S_OR_B64:
103   case AMDGPU::S_XOR_B64:
104   case AMDGPU::S_ANDN2_B64:
105   case AMDGPU::S_ORN2_B64:
106   case AMDGPU::S_NAND_B64:
107   case AMDGPU::S_NOR_B64:
108   case AMDGPU::S_XNOR_B64: {
109     const MachineOperand &Src1 = MI.getOperand(1);
110     if (Src1.isReg() && Src1.getReg() == AMDGPU::EXEC)
111       return MI.getOperand(0).getReg();
112     const MachineOperand &Src2 = MI.getOperand(2);
113     if (Src2.isReg() && Src2.getReg() == AMDGPU::EXEC)
114       return MI.getOperand(0).getReg();
115     break;
116   }
117   case AMDGPU::S_AND_B32:
118   case AMDGPU::S_OR_B32:
119   case AMDGPU::S_XOR_B32:
120   case AMDGPU::S_ANDN2_B32:
121   case AMDGPU::S_ORN2_B32:
122   case AMDGPU::S_NAND_B32:
123   case AMDGPU::S_NOR_B32:
124   case AMDGPU::S_XNOR_B32: {
125     const MachineOperand &Src1 = MI.getOperand(1);
126     if (Src1.isReg() && Src1.getReg() == AMDGPU::EXEC_LO)
127       return MI.getOperand(0).getReg();
128     const MachineOperand &Src2 = MI.getOperand(2);
129     if (Src2.isReg() && Src2.getReg() == AMDGPU::EXEC_LO)
130       return MI.getOperand(0).getReg();
131     break;
132   }
133   }
134 
135   return AMDGPU::NoRegister;
136 }
137 
138 static unsigned getSaveExecOp(unsigned Opc) {
139   switch (Opc) {
140   case AMDGPU::S_AND_B64:
141     return AMDGPU::S_AND_SAVEEXEC_B64;
142   case AMDGPU::S_OR_B64:
143     return AMDGPU::S_OR_SAVEEXEC_B64;
144   case AMDGPU::S_XOR_B64:
145     return AMDGPU::S_XOR_SAVEEXEC_B64;
146   case AMDGPU::S_ANDN2_B64:
147     return AMDGPU::S_ANDN2_SAVEEXEC_B64;
148   case AMDGPU::S_ORN2_B64:
149     return AMDGPU::S_ORN2_SAVEEXEC_B64;
150   case AMDGPU::S_NAND_B64:
151     return AMDGPU::S_NAND_SAVEEXEC_B64;
152   case AMDGPU::S_NOR_B64:
153     return AMDGPU::S_NOR_SAVEEXEC_B64;
154   case AMDGPU::S_XNOR_B64:
155     return AMDGPU::S_XNOR_SAVEEXEC_B64;
156   case AMDGPU::S_AND_B32:
157     return AMDGPU::S_AND_SAVEEXEC_B32;
158   case AMDGPU::S_OR_B32:
159     return AMDGPU::S_OR_SAVEEXEC_B32;
160   case AMDGPU::S_XOR_B32:
161     return AMDGPU::S_XOR_SAVEEXEC_B32;
162   case AMDGPU::S_ANDN2_B32:
163     return AMDGPU::S_ANDN2_SAVEEXEC_B32;
164   case AMDGPU::S_ORN2_B32:
165     return AMDGPU::S_ORN2_SAVEEXEC_B32;
166   case AMDGPU::S_NAND_B32:
167     return AMDGPU::S_NAND_SAVEEXEC_B32;
168   case AMDGPU::S_NOR_B32:
169     return AMDGPU::S_NOR_SAVEEXEC_B32;
170   case AMDGPU::S_XNOR_B32:
171     return AMDGPU::S_XNOR_SAVEEXEC_B32;
172   default:
173     return AMDGPU::INSTRUCTION_LIST_END;
174   }
175 }
176 
177 // These are only terminators to get correct spill code placement during
178 // register allocation, so turn them back into normal instructions. Only one of
179 // these is expected per block.
180 static bool removeTerminatorBit(const SIInstrInfo &TII, MachineInstr &MI) {
181   switch (MI.getOpcode()) {
182   case AMDGPU::S_MOV_B64_term:
183   case AMDGPU::S_MOV_B32_term: {
184     MI.setDesc(TII.get(AMDGPU::COPY));
185     return true;
186   }
187   case AMDGPU::S_XOR_B64_term: {
188     // This is only a terminator to get the correct spill code placement during
189     // register allocation.
190     MI.setDesc(TII.get(AMDGPU::S_XOR_B64));
191     return true;
192   }
193   case AMDGPU::S_XOR_B32_term: {
194     // This is only a terminator to get the correct spill code placement during
195     // register allocation.
196     MI.setDesc(TII.get(AMDGPU::S_XOR_B32));
197     return true;
198   }
199   case AMDGPU::S_OR_B32_term: {
200     // This is only a terminator to get the correct spill code placement during
201     // register allocation.
202     MI.setDesc(TII.get(AMDGPU::S_OR_B32));
203     return true;
204   }
205   case AMDGPU::S_OR_B64_term: {
206     // This is only a terminator to get the correct spill code placement during
207     // register allocation.
208     MI.setDesc(TII.get(AMDGPU::S_OR_B64));
209     return true;
210   }
211   case AMDGPU::S_ANDN2_B64_term: {
212     // This is only a terminator to get the correct spill code placement during
213     // register allocation.
214     MI.setDesc(TII.get(AMDGPU::S_ANDN2_B64));
215     return true;
216   }
217   case AMDGPU::S_ANDN2_B32_term: {
218     // This is only a terminator to get the correct spill code placement during
219     // register allocation.
220     MI.setDesc(TII.get(AMDGPU::S_ANDN2_B32));
221     return true;
222   }
223   default:
224     return false;
225   }
226 }
227 
228 static MachineBasicBlock::reverse_iterator fixTerminators(
229   const SIInstrInfo &TII,
230   MachineBasicBlock &MBB) {
231   MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend();
232   for (; I != E; ++I) {
233     if (!I->isTerminator())
234       return I;
235 
236     if (removeTerminatorBit(TII, *I))
237       return I;
238   }
239 
240   return E;
241 }
242 
243 static MachineBasicBlock::reverse_iterator findExecCopy(
244   const SIInstrInfo &TII,
245   const GCNSubtarget &ST,
246   MachineBasicBlock &MBB,
247   MachineBasicBlock::reverse_iterator I,
248   unsigned CopyToExec) {
249   const unsigned InstLimit = 25;
250 
251   auto E = MBB.rend();
252   for (unsigned N = 0; N <= InstLimit && I != E; ++I, ++N) {
253     unsigned CopyFromExec = isCopyFromExec(*I, ST);
254     if (CopyFromExec != AMDGPU::NoRegister)
255       return I;
256   }
257 
258   return E;
259 }
260 
261 // XXX - Seems LivePhysRegs doesn't work correctly since it will incorrectly
262 // report the register as unavailable because a super-register with a lane mask
263 // is unavailable.
264 static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg) {
265   for (MachineBasicBlock *Succ : MBB.successors()) {
266     if (Succ->isLiveIn(Reg))
267       return true;
268   }
269 
270   return false;
271 }
272 
273 bool SIOptimizeExecMasking::runOnMachineFunction(MachineFunction &MF) {
274   if (skipFunction(MF.getFunction()))
275     return false;
276 
277   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
278   const SIRegisterInfo *TRI = ST.getRegisterInfo();
279   const SIInstrInfo *TII = ST.getInstrInfo();
280   unsigned Exec = ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
281 
282   // Optimize sequences emitted for control flow lowering. They are originally
283   // emitted as the separate operations because spill code may need to be
284   // inserted for the saved copy of exec.
285   //
286   //     x = copy exec
287   //     z = s_<op>_b64 x, y
288   //     exec = copy z
289   // =>
290   //     x = s_<op>_saveexec_b64 y
291   //
292 
293   for (MachineBasicBlock &MBB : MF) {
294     MachineBasicBlock::reverse_iterator I = fixTerminators(*TII, MBB);
295     MachineBasicBlock::reverse_iterator E = MBB.rend();
296     if (I == E)
297       continue;
298 
299     unsigned CopyToExec = isCopyToExec(*I, ST);
300     if (CopyToExec == AMDGPU::NoRegister)
301       continue;
302 
303     // Scan backwards to find the def.
304     auto CopyToExecInst = &*I;
305     auto CopyFromExecInst = findExecCopy(*TII, ST, MBB, I, CopyToExec);
306     if (CopyFromExecInst == E) {
307       auto PrepareExecInst = std::next(I);
308       if (PrepareExecInst == E)
309         continue;
310       // Fold exec = COPY (S_AND_B64 reg, exec) -> exec = S_AND_B64 reg, exec
311       if (CopyToExecInst->getOperand(1).isKill() &&
312           isLogicalOpOnExec(*PrepareExecInst) == CopyToExec) {
313         LLVM_DEBUG(dbgs() << "Fold exec copy: " << *PrepareExecInst);
314 
315         PrepareExecInst->getOperand(0).setReg(Exec);
316 
317         LLVM_DEBUG(dbgs() << "into: " << *PrepareExecInst << '\n');
318 
319         CopyToExecInst->eraseFromParent();
320       }
321 
322       continue;
323     }
324 
325     if (isLiveOut(MBB, CopyToExec)) {
326       // The copied register is live out and has a second use in another block.
327       LLVM_DEBUG(dbgs() << "Exec copy source register is live out\n");
328       continue;
329     }
330 
331     unsigned CopyFromExec = CopyFromExecInst->getOperand(0).getReg();
332     MachineInstr *SaveExecInst = nullptr;
333     SmallVector<MachineInstr *, 4> OtherUseInsts;
334 
335     for (MachineBasicBlock::iterator J
336            = std::next(CopyFromExecInst->getIterator()), JE = I->getIterator();
337          J != JE; ++J) {
338       if (SaveExecInst && J->readsRegister(Exec, TRI)) {
339         LLVM_DEBUG(dbgs() << "exec read prevents saveexec: " << *J << '\n');
340         // Make sure this is inserted after any VALU ops that may have been
341         // scheduled in between.
342         SaveExecInst = nullptr;
343         break;
344       }
345 
346       bool ReadsCopyFromExec = J->readsRegister(CopyFromExec, TRI);
347 
348       if (J->modifiesRegister(CopyToExec, TRI)) {
349         if (SaveExecInst) {
350           LLVM_DEBUG(dbgs() << "Multiple instructions modify "
351                             << printReg(CopyToExec, TRI) << '\n');
352           SaveExecInst = nullptr;
353           break;
354         }
355 
356         unsigned SaveExecOp = getSaveExecOp(J->getOpcode());
357         if (SaveExecOp == AMDGPU::INSTRUCTION_LIST_END)
358           break;
359 
360         if (ReadsCopyFromExec) {
361           SaveExecInst = &*J;
362           LLVM_DEBUG(dbgs() << "Found save exec op: " << *SaveExecInst << '\n');
363           continue;
364         } else {
365           LLVM_DEBUG(dbgs()
366                      << "Instruction does not read exec copy: " << *J << '\n');
367           break;
368         }
369       } else if (ReadsCopyFromExec && !SaveExecInst) {
370         // Make sure no other instruction is trying to use this copy, before it
371         // will be rewritten by the saveexec, i.e. hasOneUse. There may have
372         // been another use, such as an inserted spill. For example:
373         //
374         // %sgpr0_sgpr1 = COPY %exec
375         // spill %sgpr0_sgpr1
376         // %sgpr2_sgpr3 = S_AND_B64 %sgpr0_sgpr1
377         //
378         LLVM_DEBUG(dbgs() << "Found second use of save inst candidate: " << *J
379                           << '\n');
380         break;
381       }
382 
383       if (SaveExecInst && J->readsRegister(CopyToExec, TRI)) {
384         assert(SaveExecInst != &*J);
385         OtherUseInsts.push_back(&*J);
386       }
387     }
388 
389     if (!SaveExecInst)
390       continue;
391 
392     LLVM_DEBUG(dbgs() << "Insert save exec op: " << *SaveExecInst << '\n');
393 
394     MachineOperand &Src0 = SaveExecInst->getOperand(1);
395     MachineOperand &Src1 = SaveExecInst->getOperand(2);
396 
397     MachineOperand *OtherOp = nullptr;
398 
399     if (Src0.isReg() && Src0.getReg() == CopyFromExec) {
400       OtherOp = &Src1;
401     } else if (Src1.isReg() && Src1.getReg() == CopyFromExec) {
402       if (!SaveExecInst->isCommutable())
403         break;
404 
405       OtherOp = &Src0;
406     } else
407       llvm_unreachable("unexpected");
408 
409     CopyFromExecInst->eraseFromParent();
410 
411     auto InsPt = SaveExecInst->getIterator();
412     const DebugLoc &DL = SaveExecInst->getDebugLoc();
413 
414     BuildMI(MBB, InsPt, DL, TII->get(getSaveExecOp(SaveExecInst->getOpcode())),
415             CopyFromExec)
416       .addReg(OtherOp->getReg());
417     SaveExecInst->eraseFromParent();
418 
419     CopyToExecInst->eraseFromParent();
420 
421     for (MachineInstr *OtherInst : OtherUseInsts) {
422       OtherInst->substituteRegister(CopyToExec, Exec,
423                                     AMDGPU::NoSubRegister, *TRI);
424     }
425   }
426 
427   return true;
428 
429 }
430