1//===-- SILowerControlFlow.cpp - Use predicates for control flow ----------===//
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/// \file
10/// This pass lowers the pseudo control flow instructions to real
11/// machine instructions.
12///
13/// All control flow is handled using predicated instructions and
14/// a predicate stack.  Each Scalar ALU controls the operations of 64 Vector
15/// ALUs.  The Scalar ALU can update the predicate for any of the Vector ALUs
16/// by writting to the 64-bit EXEC register (each bit corresponds to a
17/// single vector ALU).  Typically, for predicates, a vector ALU will write
18/// to its bit of the VCC register (like EXEC VCC is 64-bits, one for each
19/// Vector ALU) and then the ScalarALU will AND the VCC register with the
20/// EXEC to update the predicates.
21///
22/// For example:
23/// %vcc = V_CMP_GT_F32 %vgpr1, %vgpr2
24/// %sgpr0 = SI_IF %vcc
25///   %vgpr0 = V_ADD_F32 %vgpr0, %vgpr0
26/// %sgpr0 = SI_ELSE %sgpr0
27///   %vgpr0 = V_SUB_F32 %vgpr0, %vgpr0
28/// SI_END_CF %sgpr0
29///
30/// becomes:
31///
32/// %sgpr0 = S_AND_SAVEEXEC_B64 %vcc  // Save and update the exec mask
33/// %sgpr0 = S_XOR_B64 %sgpr0, %exec  // Clear live bits from saved exec mask
34/// S_CBRANCH_EXECZ label0            // This instruction is an optional
35///                                   // optimization which allows us to
36///                                   // branch if all the bits of
37///                                   // EXEC are zero.
38/// %vgpr0 = V_ADD_F32 %vgpr0, %vgpr0 // Do the IF block of the branch
39///
40/// label0:
41/// %sgpr0 = S_OR_SAVEEXEC_B64 %sgpr0  // Restore the exec mask for the Then block
42/// %exec = S_XOR_B64 %sgpr0, %exec    // Update the exec mask
43/// S_BRANCH_EXECZ label1              // Use our branch optimization
44///                                    // instruction again.
45/// %vgpr0 = V_SUB_F32 %vgpr0, %vgpr   // Do the THEN block
46/// label1:
47/// %exec = S_OR_B64 %exec, %sgpr0     // Re-enable saved exec mask bits
48//===----------------------------------------------------------------------===//
49
50#include "AMDGPU.h"
51#include "AMDGPUSubtarget.h"
52#include "SIInstrInfo.h"
53#include "MCTargetDesc/AMDGPUMCTargetDesc.h"
54#include "llvm/ADT/SetVector.h"
55#include "llvm/ADT/SmallSet.h"
56#include "llvm/ADT/SmallVector.h"
57#include "llvm/ADT/StringRef.h"
58#include "llvm/CodeGen/LiveIntervals.h"
59#include "llvm/CodeGen/MachineBasicBlock.h"
60#include "llvm/CodeGen/MachineFunction.h"
61#include "llvm/CodeGen/MachineFunctionPass.h"
62#include "llvm/CodeGen/MachineInstr.h"
63#include "llvm/CodeGen/MachineInstrBuilder.h"
64#include "llvm/CodeGen/MachineOperand.h"
65#include "llvm/CodeGen/MachineRegisterInfo.h"
66#include "llvm/CodeGen/Passes.h"
67#include "llvm/CodeGen/SlotIndexes.h"
68#include "llvm/CodeGen/TargetRegisterInfo.h"
69#include "llvm/MC/MCRegisterInfo.h"
70#include "llvm/Pass.h"
71#include <cassert>
72#include <iterator>
73
74using namespace llvm;
75
76#define DEBUG_TYPE "si-lower-control-flow"
77
78static cl::opt<bool>
79RemoveRedundantEndcf("amdgpu-remove-redundant-endcf",
80    cl::init(true), cl::ReallyHidden);
81
82namespace {
83
84class SILowerControlFlow : public MachineFunctionPass {
85private:
86  const SIRegisterInfo *TRI = nullptr;
87  const SIInstrInfo *TII = nullptr;
88  LiveIntervals *LIS = nullptr;
89  MachineRegisterInfo *MRI = nullptr;
90  SetVector<MachineInstr*> LoweredEndCf;
91  DenseSet<Register> LoweredIf;
92  SmallSet<MachineInstr *, 16> NeedsKillCleanup;
93
94  const TargetRegisterClass *BoolRC = nullptr;
95  bool InsertKillCleanups;
96  unsigned AndOpc;
97  unsigned OrOpc;
98  unsigned XorOpc;
99  unsigned MovTermOpc;
100  unsigned Andn2TermOpc;
101  unsigned XorTermrOpc;
102  unsigned OrSaveExecOpc;
103  unsigned Exec;
104
105  void emitIf(MachineInstr &MI);
106  void emitElse(MachineInstr &MI);
107  void emitIfBreak(MachineInstr &MI);
108  void emitLoop(MachineInstr &MI);
109  void emitEndCf(MachineInstr &MI);
110
111  void findMaskOperands(MachineInstr &MI, unsigned OpNo,
112                        SmallVectorImpl<MachineOperand> &Src) const;
113
114  void combineMasks(MachineInstr &MI);
115
116  void process(MachineInstr &MI);
117
118  // Skip to the next instruction, ignoring debug instructions, and trivial
119  // block boundaries (blocks that have one (typically fallthrough) successor,
120  // and the successor has one predecessor.
121  MachineBasicBlock::iterator
122  skipIgnoreExecInstsTrivialSucc(MachineBasicBlock &MBB,
123                                 MachineBasicBlock::iterator It) const;
124
125  // Remove redundant SI_END_CF instructions.
126  void optimizeEndCf();
127
128public:
129  static char ID;
130
131  SILowerControlFlow() : MachineFunctionPass(ID) {}
132
133  bool runOnMachineFunction(MachineFunction &MF) override;
134
135  StringRef getPassName() const override {
136    return "SI Lower control flow pseudo instructions";
137  }
138
139  void getAnalysisUsage(AnalysisUsage &AU) const override {
140    // Should preserve the same set that TwoAddressInstructions does.
141    AU.addPreserved<SlotIndexes>();
142    AU.addPreserved<LiveIntervals>();
143    AU.addPreservedID(LiveVariablesID);
144    AU.addPreservedID(MachineLoopInfoID);
145    AU.addPreservedID(MachineDominatorsID);
146    AU.setPreservesCFG();
147    MachineFunctionPass::getAnalysisUsage(AU);
148  }
149};
150
151} // end anonymous namespace
152
153char SILowerControlFlow::ID = 0;
154
155INITIALIZE_PASS(SILowerControlFlow, DEBUG_TYPE,
156               "SI lower control flow", false, false)
157
158static void setImpSCCDefDead(MachineInstr &MI, bool IsDead) {
159  MachineOperand &ImpDefSCC = MI.getOperand(3);
160  assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
161
162  ImpDefSCC.setIsDead(IsDead);
163}
164
165char &llvm::SILowerControlFlowID = SILowerControlFlow::ID;
166
167static bool hasKill(const MachineBasicBlock *Begin,
168                    const MachineBasicBlock *End, const SIInstrInfo *TII) {
169  DenseSet<const MachineBasicBlock*> Visited;
170  SmallVector<MachineBasicBlock *, 4> Worklist(Begin->succ_begin(),
171                                               Begin->succ_end());
172
173  while (!Worklist.empty()) {
174    MachineBasicBlock *MBB = Worklist.pop_back_val();
175
176    if (MBB == End || !Visited.insert(MBB).second)
177      continue;
178    for (auto &Term : MBB->terminators())
179      if (TII->isKillTerminator(Term.getOpcode()))
180        return true;
181
182    Worklist.append(MBB->succ_begin(), MBB->succ_end());
183  }
184
185  return false;
186}
187
188static bool isSimpleIf(const MachineInstr &MI, const MachineRegisterInfo *MRI) {
189  Register SaveExecReg = MI.getOperand(0).getReg();
190  auto U = MRI->use_instr_nodbg_begin(SaveExecReg);
191
192  if (U == MRI->use_instr_nodbg_end() ||
193      std::next(U) != MRI->use_instr_nodbg_end() ||
194      U->getOpcode() != AMDGPU::SI_END_CF)
195    return false;
196
197  return true;
198}
199
200void SILowerControlFlow::emitIf(MachineInstr &MI) {
201  MachineBasicBlock &MBB = *MI.getParent();
202  const DebugLoc &DL = MI.getDebugLoc();
203  MachineBasicBlock::iterator I(&MI);
204  Register SaveExecReg = MI.getOperand(0).getReg();
205  MachineOperand& Cond = MI.getOperand(1);
206  assert(Cond.getSubReg() == AMDGPU::NoSubRegister);
207
208  MachineOperand &ImpDefSCC = MI.getOperand(4);
209  assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
210
211  // If there is only one use of save exec register and that use is SI_END_CF,
212  // we can optimize SI_IF by returning the full saved exec mask instead of
213  // just cleared bits.
214  bool SimpleIf = isSimpleIf(MI, MRI);
215
216  if (InsertKillCleanups) {
217    // Check for SI_KILL_*_TERMINATOR on full path of control flow and
218    // flag the associated SI_END_CF for insertion of a kill cleanup.
219    auto UseMI = MRI->use_instr_nodbg_begin(SaveExecReg);
220    while (UseMI->getOpcode() != AMDGPU::SI_END_CF) {
221      assert(std::next(UseMI) == MRI->use_instr_nodbg_end());
222      assert(UseMI->getOpcode() == AMDGPU::SI_ELSE);
223      MachineOperand &NextExec = UseMI->getOperand(0);
224      Register NextExecReg = NextExec.getReg();
225      if (NextExec.isDead()) {
226        assert(!SimpleIf);
227        break;
228      }
229      UseMI = MRI->use_instr_nodbg_begin(NextExecReg);
230    }
231    if (UseMI->getOpcode() == AMDGPU::SI_END_CF) {
232      if (hasKill(MI.getParent(), UseMI->getParent(), TII)) {
233        NeedsKillCleanup.insert(&*UseMI);
234        SimpleIf = false;
235      }
236    }
237  } else if (SimpleIf) {
238    // Check for SI_KILL_*_TERMINATOR on path from if to endif.
239    // if there is any such terminator simplifications are not safe.
240    auto UseMI = MRI->use_instr_nodbg_begin(SaveExecReg);
241    SimpleIf = !hasKill(MI.getParent(), UseMI->getParent(), TII);
242  }
243
244  // Add an implicit def of exec to discourage scheduling VALU after this which
245  // will interfere with trying to form s_and_saveexec_b64 later.
246  Register CopyReg = SimpleIf ? SaveExecReg
247                       : MRI->createVirtualRegister(BoolRC);
248  MachineInstr *CopyExec =
249    BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), CopyReg)
250    .addReg(Exec)
251    .addReg(Exec, RegState::ImplicitDefine);
252  LoweredIf.insert(CopyReg);
253
254  Register Tmp = MRI->createVirtualRegister(BoolRC);
255
256  MachineInstr *And =
257    BuildMI(MBB, I, DL, TII->get(AndOpc), Tmp)
258    .addReg(CopyReg)
259    .add(Cond);
260
261  setImpSCCDefDead(*And, true);
262
263  MachineInstr *Xor = nullptr;
264  if (!SimpleIf) {
265    Xor =
266      BuildMI(MBB, I, DL, TII->get(XorOpc), SaveExecReg)
267      .addReg(Tmp)
268      .addReg(CopyReg);
269    setImpSCCDefDead(*Xor, ImpDefSCC.isDead());
270  }
271
272  // Use a copy that is a terminator to get correct spill code placement it with
273  // fast regalloc.
274  MachineInstr *SetExec =
275    BuildMI(MBB, I, DL, TII->get(MovTermOpc), Exec)
276    .addReg(Tmp, RegState::Kill);
277
278  // Insert the S_CBRANCH_EXECZ instruction which will be optimized later
279  // during SIRemoveShortExecBranches.
280  MachineInstr *NewBr = BuildMI(MBB, I, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
281                            .add(MI.getOperand(2));
282
283  if (!LIS) {
284    MI.eraseFromParent();
285    return;
286  }
287
288  LIS->InsertMachineInstrInMaps(*CopyExec);
289
290  // Replace with and so we don't need to fix the live interval for condition
291  // register.
292  LIS->ReplaceMachineInstrInMaps(MI, *And);
293
294  if (!SimpleIf)
295    LIS->InsertMachineInstrInMaps(*Xor);
296  LIS->InsertMachineInstrInMaps(*SetExec);
297  LIS->InsertMachineInstrInMaps(*NewBr);
298
299  LIS->removeAllRegUnitsForPhysReg(AMDGPU::EXEC);
300  MI.eraseFromParent();
301
302  // FIXME: Is there a better way of adjusting the liveness? It shouldn't be
303  // hard to add another def here but I'm not sure how to correctly update the
304  // valno.
305  LIS->removeInterval(SaveExecReg);
306  LIS->createAndComputeVirtRegInterval(SaveExecReg);
307  LIS->createAndComputeVirtRegInterval(Tmp);
308  if (!SimpleIf)
309    LIS->createAndComputeVirtRegInterval(CopyReg);
310}
311
312void SILowerControlFlow::emitElse(MachineInstr &MI) {
313  MachineBasicBlock &MBB = *MI.getParent();
314  const DebugLoc &DL = MI.getDebugLoc();
315
316  Register DstReg = MI.getOperand(0).getReg();
317
318  bool ExecModified = MI.getOperand(3).getImm() != 0;
319  MachineBasicBlock::iterator Start = MBB.begin();
320
321  // We are running before TwoAddressInstructions, and si_else's operands are
322  // tied. In order to correctly tie the registers, split this into a copy of
323  // the src like it does.
324  Register CopyReg = MRI->createVirtualRegister(BoolRC);
325  MachineInstr *CopyExec =
326    BuildMI(MBB, Start, DL, TII->get(AMDGPU::COPY), CopyReg)
327      .add(MI.getOperand(1)); // Saved EXEC
328
329  // This must be inserted before phis and any spill code inserted before the
330  // else.
331  Register SaveReg = ExecModified ?
332    MRI->createVirtualRegister(BoolRC) : DstReg;
333  MachineInstr *OrSaveExec =
334    BuildMI(MBB, Start, DL, TII->get(OrSaveExecOpc), SaveReg)
335    .addReg(CopyReg);
336
337  MachineBasicBlock *DestBB = MI.getOperand(2).getMBB();
338
339  MachineBasicBlock::iterator ElsePt(MI);
340
341  if (ExecModified) {
342    MachineInstr *And =
343      BuildMI(MBB, ElsePt, DL, TII->get(AndOpc), DstReg)
344      .addReg(Exec)
345      .addReg(SaveReg);
346
347    if (LIS)
348      LIS->InsertMachineInstrInMaps(*And);
349  }
350
351  MachineInstr *Xor =
352    BuildMI(MBB, ElsePt, DL, TII->get(XorTermrOpc), Exec)
353    .addReg(Exec)
354    .addReg(DstReg);
355
356  MachineInstr *Branch =
357      BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
358          .addMBB(DestBB);
359
360  if (!LIS) {
361    MI.eraseFromParent();
362    return;
363  }
364
365  LIS->RemoveMachineInstrFromMaps(MI);
366  MI.eraseFromParent();
367
368  LIS->InsertMachineInstrInMaps(*CopyExec);
369  LIS->InsertMachineInstrInMaps(*OrSaveExec);
370
371  LIS->InsertMachineInstrInMaps(*Xor);
372  LIS->InsertMachineInstrInMaps(*Branch);
373
374  // src reg is tied to dst reg.
375  LIS->removeInterval(DstReg);
376  LIS->createAndComputeVirtRegInterval(DstReg);
377  LIS->createAndComputeVirtRegInterval(CopyReg);
378  if (ExecModified)
379    LIS->createAndComputeVirtRegInterval(SaveReg);
380
381  // Let this be recomputed.
382  LIS->removeAllRegUnitsForPhysReg(AMDGPU::EXEC);
383}
384
385void SILowerControlFlow::emitIfBreak(MachineInstr &MI) {
386  MachineBasicBlock &MBB = *MI.getParent();
387  const DebugLoc &DL = MI.getDebugLoc();
388  auto Dst = MI.getOperand(0).getReg();
389
390  // Skip ANDing with exec if the break condition is already masked by exec
391  // because it is a V_CMP in the same basic block. (We know the break
392  // condition operand was an i1 in IR, so if it is a VALU instruction it must
393  // be one with a carry-out.)
394  bool SkipAnding = false;
395  if (MI.getOperand(1).isReg()) {
396    if (MachineInstr *Def = MRI->getUniqueVRegDef(MI.getOperand(1).getReg())) {
397      SkipAnding = Def->getParent() == MI.getParent()
398          && SIInstrInfo::isVALU(*Def);
399    }
400  }
401
402  // AND the break condition operand with exec, then OR that into the "loop
403  // exit" mask.
404  MachineInstr *And = nullptr, *Or = nullptr;
405  if (!SkipAnding) {
406    Register AndReg = MRI->createVirtualRegister(BoolRC);
407    And = BuildMI(MBB, &MI, DL, TII->get(AndOpc), AndReg)
408             .addReg(Exec)
409             .add(MI.getOperand(1));
410    Or = BuildMI(MBB, &MI, DL, TII->get(OrOpc), Dst)
411             .addReg(AndReg)
412             .add(MI.getOperand(2));
413    if (LIS)
414      LIS->createAndComputeVirtRegInterval(AndReg);
415  } else
416    Or = BuildMI(MBB, &MI, DL, TII->get(OrOpc), Dst)
417             .add(MI.getOperand(1))
418             .add(MI.getOperand(2));
419
420  if (LIS) {
421    if (And)
422      LIS->InsertMachineInstrInMaps(*And);
423    LIS->ReplaceMachineInstrInMaps(MI, *Or);
424  }
425
426  MI.eraseFromParent();
427}
428
429void SILowerControlFlow::emitLoop(MachineInstr &MI) {
430  MachineBasicBlock &MBB = *MI.getParent();
431  const DebugLoc &DL = MI.getDebugLoc();
432
433  MachineInstr *AndN2 =
434      BuildMI(MBB, &MI, DL, TII->get(Andn2TermOpc), Exec)
435          .addReg(Exec)
436          .add(MI.getOperand(0));
437
438  MachineInstr *Branch =
439      BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))
440          .add(MI.getOperand(1));
441
442  if (LIS) {
443    LIS->ReplaceMachineInstrInMaps(MI, *AndN2);
444    LIS->InsertMachineInstrInMaps(*Branch);
445  }
446
447  MI.eraseFromParent();
448}
449
450MachineBasicBlock::iterator
451SILowerControlFlow::skipIgnoreExecInstsTrivialSucc(
452  MachineBasicBlock &MBB, MachineBasicBlock::iterator It) const {
453
454  SmallSet<const MachineBasicBlock *, 4> Visited;
455  MachineBasicBlock *B = &MBB;
456  do {
457    if (!Visited.insert(B).second)
458      return MBB.end();
459
460    auto E = B->end();
461    for ( ; It != E; ++It) {
462      if (It->getOpcode() == AMDGPU::SI_KILL_CLEANUP)
463        continue;
464      if (TII->mayReadEXEC(*MRI, *It))
465        break;
466    }
467
468    if (It != E)
469      return It;
470
471    if (B->succ_size() != 1)
472      return MBB.end();
473
474    // If there is one trivial successor, advance to the next block.
475    MachineBasicBlock *Succ = *B->succ_begin();
476
477    It = Succ->begin();
478    B = Succ;
479  } while (true);
480}
481
482void SILowerControlFlow::emitEndCf(MachineInstr &MI) {
483  MachineBasicBlock &MBB = *MI.getParent();
484  MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
485  unsigned CFMask = MI.getOperand(0).getReg();
486  MachineInstr *Def = MRI.getUniqueVRegDef(CFMask);
487  const DebugLoc &DL = MI.getDebugLoc();
488
489  MachineBasicBlock::iterator InsPt =
490      Def && Def->getParent() == &MBB ? std::next(MachineBasicBlock::iterator(Def))
491                               : MBB.begin();
492  MachineInstr *NewMI = BuildMI(MBB, InsPt, DL, TII->get(OrOpc), Exec)
493                            .addReg(Exec)
494                            .add(MI.getOperand(0));
495
496  LoweredEndCf.insert(NewMI);
497
498  // If this ends control flow which contains kills (as flagged in emitIf)
499  // then insert an SI_KILL_CLEANUP immediately following the exec mask
500  // manipulation.  This can be lowered to early termination if appropriate.
501  MachineInstr *CleanUpMI = nullptr;
502  if (NeedsKillCleanup.count(&MI))
503    CleanUpMI = BuildMI(MBB, InsPt, DL, TII->get(AMDGPU::SI_KILL_CLEANUP));
504
505  if (LIS) {
506    LIS->ReplaceMachineInstrInMaps(MI, *NewMI);
507    if (CleanUpMI)
508      LIS->InsertMachineInstrInMaps(*CleanUpMI);
509  }
510
511  MI.eraseFromParent();
512
513  if (LIS)
514    LIS->handleMove(*NewMI);
515}
516
517// Returns replace operands for a logical operation, either single result
518// for exec or two operands if source was another equivalent operation.
519void SILowerControlFlow::findMaskOperands(MachineInstr &MI, unsigned OpNo,
520       SmallVectorImpl<MachineOperand> &Src) const {
521  MachineOperand &Op = MI.getOperand(OpNo);
522  if (!Op.isReg() || !Register::isVirtualRegister(Op.getReg())) {
523    Src.push_back(Op);
524    return;
525  }
526
527  MachineInstr *Def = MRI->getUniqueVRegDef(Op.getReg());
528  if (!Def || Def->getParent() != MI.getParent() ||
529      !(Def->isFullCopy() || (Def->getOpcode() == MI.getOpcode())))
530    return;
531
532  // Make sure we do not modify exec between def and use.
533  // A copy with implcitly defined exec inserted earlier is an exclusion, it
534  // does not really modify exec.
535  for (auto I = Def->getIterator(); I != MI.getIterator(); ++I)
536    if (I->modifiesRegister(AMDGPU::EXEC, TRI) &&
537        !(I->isCopy() && I->getOperand(0).getReg() != Exec))
538      return;
539
540  for (const auto &SrcOp : Def->explicit_operands())
541    if (SrcOp.isReg() && SrcOp.isUse() &&
542        (Register::isVirtualRegister(SrcOp.getReg()) || SrcOp.getReg() == Exec))
543      Src.push_back(SrcOp);
544}
545
546// Search and combine pairs of equivalent instructions, like
547// S_AND_B64 x, (S_AND_B64 x, y) => S_AND_B64 x, y
548// S_OR_B64  x, (S_OR_B64  x, y) => S_OR_B64  x, y
549// One of the operands is exec mask.
550void SILowerControlFlow::combineMasks(MachineInstr &MI) {
551  assert(MI.getNumExplicitOperands() == 3);
552  SmallVector<MachineOperand, 4> Ops;
553  unsigned OpToReplace = 1;
554  findMaskOperands(MI, 1, Ops);
555  if (Ops.size() == 1) OpToReplace = 2; // First operand can be exec or its copy
556  findMaskOperands(MI, 2, Ops);
557  if (Ops.size() != 3) return;
558
559  unsigned UniqueOpndIdx;
560  if (Ops[0].isIdenticalTo(Ops[1])) UniqueOpndIdx = 2;
561  else if (Ops[0].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;
562  else if (Ops[1].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;
563  else return;
564
565  Register Reg = MI.getOperand(OpToReplace).getReg();
566  MI.RemoveOperand(OpToReplace);
567  MI.addOperand(Ops[UniqueOpndIdx]);
568  if (MRI->use_empty(Reg))
569    MRI->getUniqueVRegDef(Reg)->eraseFromParent();
570}
571
572void SILowerControlFlow::optimizeEndCf() {
573  // If the only instruction immediately following this END_CF is an another
574  // END_CF in the only successor we can avoid emitting exec mask restore here.
575  if (!RemoveRedundantEndcf)
576    return;
577
578  for (MachineInstr *MI : LoweredEndCf) {
579    MachineBasicBlock &MBB = *MI->getParent();
580    auto Next =
581      skipIgnoreExecInstsTrivialSucc(MBB, std::next(MI->getIterator()));
582    if (Next == MBB.end() || !LoweredEndCf.count(&*Next))
583      continue;
584    // Only skip inner END_CF if outer ENDCF belongs to SI_IF.
585    // If that belongs to SI_ELSE then saved mask has an inverted value.
586    Register SavedExec
587      = TII->getNamedOperand(*Next, AMDGPU::OpName::src1)->getReg();
588    assert(SavedExec.isVirtual() && "Expected saved exec to be src1!");
589
590    const MachineInstr *Def = MRI->getUniqueVRegDef(SavedExec);
591    if (Def && LoweredIf.count(SavedExec)) {
592      LLVM_DEBUG(dbgs() << "Skip redundant "; MI->dump());
593      if (LIS)
594        LIS->RemoveMachineInstrFromMaps(*MI);
595      MI->eraseFromParent();
596    }
597  }
598}
599
600void SILowerControlFlow::process(MachineInstr &MI) {
601  MachineBasicBlock &MBB = *MI.getParent();
602  MachineBasicBlock::iterator I(MI);
603  MachineInstr *Prev = (I != MBB.begin()) ? &*(std::prev(I)) : nullptr;
604
605  switch (MI.getOpcode()) {
606  case AMDGPU::SI_IF:
607    emitIf(MI);
608    break;
609
610  case AMDGPU::SI_ELSE:
611    emitElse(MI);
612    break;
613
614  case AMDGPU::SI_IF_BREAK:
615    emitIfBreak(MI);
616    break;
617
618  case AMDGPU::SI_LOOP:
619    emitLoop(MI);
620    break;
621
622  case AMDGPU::SI_END_CF:
623    emitEndCf(MI);
624    break;
625
626  default:
627    assert(false && "Attempt to process unsupported instruction");
628    break;
629  }
630
631  MachineBasicBlock::iterator Next;
632  for (I = Prev ? Prev->getIterator() : MBB.begin(); I != MBB.end(); I = Next) {
633    Next = std::next(I);
634    MachineInstr &MaskMI = *I;
635    switch (MaskMI.getOpcode()) {
636    case AMDGPU::S_AND_B64:
637    case AMDGPU::S_OR_B64:
638    case AMDGPU::S_AND_B32:
639    case AMDGPU::S_OR_B32:
640      // Cleanup bit manipulations on exec mask
641      combineMasks(MaskMI);
642      break;
643    default:
644      I = MBB.end();
645      break;
646    }
647  }
648}
649
650bool SILowerControlFlow::runOnMachineFunction(MachineFunction &MF) {
651  const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
652  TII = ST.getInstrInfo();
653  TRI = &TII->getRegisterInfo();
654
655  // This doesn't actually need LiveIntervals, but we can preserve them.
656  LIS = getAnalysisIfAvailable<LiveIntervals>();
657  MRI = &MF.getRegInfo();
658  BoolRC = TRI->getBoolRC();
659  InsertKillCleanups =
660      MF.getFunction().getCallingConv() == CallingConv::AMDGPU_PS;
661
662  if (ST.isWave32()) {
663    AndOpc = AMDGPU::S_AND_B32;
664    OrOpc = AMDGPU::S_OR_B32;
665    XorOpc = AMDGPU::S_XOR_B32;
666    MovTermOpc = AMDGPU::S_MOV_B32_term;
667    Andn2TermOpc = AMDGPU::S_ANDN2_B32_term;
668    XorTermrOpc = AMDGPU::S_XOR_B32_term;
669    OrSaveExecOpc = AMDGPU::S_OR_SAVEEXEC_B32;
670    Exec = AMDGPU::EXEC_LO;
671  } else {
672    AndOpc = AMDGPU::S_AND_B64;
673    OrOpc = AMDGPU::S_OR_B64;
674    XorOpc = AMDGPU::S_XOR_B64;
675    MovTermOpc = AMDGPU::S_MOV_B64_term;
676    Andn2TermOpc = AMDGPU::S_ANDN2_B64_term;
677    XorTermrOpc = AMDGPU::S_XOR_B64_term;
678    OrSaveExecOpc = AMDGPU::S_OR_SAVEEXEC_B64;
679    Exec = AMDGPU::EXEC;
680  }
681
682  SmallVector<MachineInstr *, 32> Worklist;
683
684  MachineFunction::iterator NextBB;
685  for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
686       BI != BE; BI = NextBB) {
687    NextBB = std::next(BI);
688    MachineBasicBlock &MBB = *BI;
689
690    MachineBasicBlock::iterator I, Next;
691    for (I = MBB.begin(); I != MBB.end(); I = Next) {
692      Next = std::next(I);
693      MachineInstr &MI = *I;
694
695      switch (MI.getOpcode()) {
696      case AMDGPU::SI_IF:
697        process(MI);
698        break;
699
700      case AMDGPU::SI_ELSE:
701      case AMDGPU::SI_IF_BREAK:
702      case AMDGPU::SI_LOOP:
703      case AMDGPU::SI_END_CF:
704        // Only build worklist if SI_IF instructions must be processed first.
705        if (InsertKillCleanups)
706          Worklist.push_back(&MI);
707        else
708          process(MI);
709        break;
710
711      default:
712        break;
713      }
714    }
715  }
716
717  for (MachineInstr *MI : Worklist)
718    process(*MI);
719
720  optimizeEndCf();
721
722  LoweredEndCf.clear();
723  LoweredIf.clear();
724  NeedsKillCleanup.clear();
725
726  return true;
727}
728