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