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