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