xref: /freebsd/contrib/llvm-project/llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp (revision 744bfb213144c63cbaf38d91a1c4f7aebb9b9fbc)
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 writing 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
42 ///                                    // block
43 /// %exec = S_XOR_B64 %sgpr0, %exec    // Update the exec mask
44 /// S_BRANCH_EXECZ label1              // Use our branch optimization
45 ///                                    // instruction again.
46 /// %vgpr0 = V_SUB_F32 %vgpr0, %vgpr   // Do the THEN block
47 /// label1:
48 /// %exec = S_OR_B64 %exec, %sgpr0     // Re-enable saved exec mask bits
49 //===----------------------------------------------------------------------===//
50 
51 #include "AMDGPU.h"
52 #include "GCNSubtarget.h"
53 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
54 #include "llvm/ADT/SmallSet.h"
55 #include "llvm/CodeGen/LiveIntervals.h"
56 #include "llvm/CodeGen/LiveVariables.h"
57 #include "llvm/CodeGen/MachineDominators.h"
58 #include "llvm/CodeGen/MachineFunctionPass.h"
59 #include "llvm/Target/TargetMachine.h"
60 
61 using namespace llvm;
62 
63 #define DEBUG_TYPE "si-lower-control-flow"
64 
65 static cl::opt<bool>
66 RemoveRedundantEndcf("amdgpu-remove-redundant-endcf",
67     cl::init(true), cl::ReallyHidden);
68 
69 namespace {
70 
71 class SILowerControlFlow : public MachineFunctionPass {
72 private:
73   const SIRegisterInfo *TRI = nullptr;
74   const SIInstrInfo *TII = nullptr;
75   LiveIntervals *LIS = nullptr;
76   LiveVariables *LV = nullptr;
77   MachineDominatorTree *MDT = nullptr;
78   MachineRegisterInfo *MRI = nullptr;
79   SetVector<MachineInstr*> LoweredEndCf;
80   DenseSet<Register> LoweredIf;
81   SmallSet<MachineBasicBlock *, 4> KillBlocks;
82 
83   const TargetRegisterClass *BoolRC = nullptr;
84   unsigned AndOpc;
85   unsigned OrOpc;
86   unsigned XorOpc;
87   unsigned MovTermOpc;
88   unsigned Andn2TermOpc;
89   unsigned XorTermrOpc;
90   unsigned OrTermrOpc;
91   unsigned OrSaveExecOpc;
92   unsigned Exec;
93 
94   bool EnableOptimizeEndCf = false;
95 
96   bool hasKill(const MachineBasicBlock *Begin, const MachineBasicBlock *End);
97 
98   void emitIf(MachineInstr &MI);
99   void emitElse(MachineInstr &MI);
100   void emitIfBreak(MachineInstr &MI);
101   void emitLoop(MachineInstr &MI);
102 
103   MachineBasicBlock *emitEndCf(MachineInstr &MI);
104 
105   void lowerInitExec(MachineBasicBlock *MBB, MachineInstr &MI);
106 
107   void findMaskOperands(MachineInstr &MI, unsigned OpNo,
108                         SmallVectorImpl<MachineOperand> &Src) const;
109 
110   void combineMasks(MachineInstr &MI);
111 
112   bool removeMBBifRedundant(MachineBasicBlock &MBB);
113 
114   MachineBasicBlock *process(MachineInstr &MI);
115 
116   // Skip to the next instruction, ignoring debug instructions, and trivial
117   // block boundaries (blocks that have one (typically fallthrough) successor,
118   // and the successor has one predecessor.
119   MachineBasicBlock::iterator
120   skipIgnoreExecInstsTrivialSucc(MachineBasicBlock &MBB,
121                                  MachineBasicBlock::iterator It) const;
122 
123   /// Find the insertion point for a new conditional branch.
124   MachineBasicBlock::iterator
125   skipToUncondBrOrEnd(MachineBasicBlock &MBB,
126                       MachineBasicBlock::iterator I) const {
127     assert(I->isTerminator());
128 
129     // FIXME: What if we had multiple pre-existing conditional branches?
130     MachineBasicBlock::iterator End = MBB.end();
131     while (I != End && !I->isUnconditionalBranch())
132       ++I;
133     return I;
134   }
135 
136   // Remove redundant SI_END_CF instructions.
137   void optimizeEndCf();
138 
139 public:
140   static char ID;
141 
142   SILowerControlFlow() : MachineFunctionPass(ID) {}
143 
144   bool runOnMachineFunction(MachineFunction &MF) override;
145 
146   StringRef getPassName() const override {
147     return "SI Lower control flow pseudo instructions";
148   }
149 
150   void getAnalysisUsage(AnalysisUsage &AU) const override {
151     // Should preserve the same set that TwoAddressInstructions does.
152     AU.addPreserved<MachineDominatorTree>();
153     AU.addPreserved<SlotIndexes>();
154     AU.addPreserved<LiveIntervals>();
155     AU.addPreservedID(LiveVariablesID);
156     MachineFunctionPass::getAnalysisUsage(AU);
157   }
158 };
159 
160 } // end anonymous namespace
161 
162 char SILowerControlFlow::ID = 0;
163 
164 INITIALIZE_PASS(SILowerControlFlow, DEBUG_TYPE,
165                "SI lower control flow", false, false)
166 
167 static void setImpSCCDefDead(MachineInstr &MI, bool IsDead) {
168   MachineOperand &ImpDefSCC = MI.getOperand(3);
169   assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
170 
171   ImpDefSCC.setIsDead(IsDead);
172 }
173 
174 char &llvm::SILowerControlFlowID = SILowerControlFlow::ID;
175 
176 bool SILowerControlFlow::hasKill(const MachineBasicBlock *Begin,
177                                  const MachineBasicBlock *End) {
178   DenseSet<const MachineBasicBlock*> Visited;
179   SmallVector<MachineBasicBlock *, 4> Worklist(Begin->successors());
180 
181   while (!Worklist.empty()) {
182     MachineBasicBlock *MBB = Worklist.pop_back_val();
183 
184     if (MBB == End || !Visited.insert(MBB).second)
185       continue;
186     if (KillBlocks.contains(MBB))
187       return true;
188 
189     Worklist.append(MBB->succ_begin(), MBB->succ_end());
190   }
191 
192   return false;
193 }
194 
195 static bool isSimpleIf(const MachineInstr &MI, const MachineRegisterInfo *MRI) {
196   Register SaveExecReg = MI.getOperand(0).getReg();
197   auto U = MRI->use_instr_nodbg_begin(SaveExecReg);
198 
199   if (U == MRI->use_instr_nodbg_end() ||
200       std::next(U) != MRI->use_instr_nodbg_end() ||
201       U->getOpcode() != AMDGPU::SI_END_CF)
202     return false;
203 
204   return true;
205 }
206 
207 void SILowerControlFlow::emitIf(MachineInstr &MI) {
208   MachineBasicBlock &MBB = *MI.getParent();
209   const DebugLoc &DL = MI.getDebugLoc();
210   MachineBasicBlock::iterator I(&MI);
211   Register SaveExecReg = MI.getOperand(0).getReg();
212   MachineOperand& Cond = MI.getOperand(1);
213   assert(Cond.getSubReg() == AMDGPU::NoSubRegister);
214 
215   MachineOperand &ImpDefSCC = MI.getOperand(4);
216   assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
217 
218   // If there is only one use of save exec register and that use is SI_END_CF,
219   // we can optimize SI_IF by returning the full saved exec mask instead of
220   // just cleared bits.
221   bool SimpleIf = isSimpleIf(MI, MRI);
222 
223   if (SimpleIf) {
224     // Check for SI_KILL_*_TERMINATOR on path from if to endif.
225     // if there is any such terminator simplifications are not safe.
226     auto UseMI = MRI->use_instr_nodbg_begin(SaveExecReg);
227     SimpleIf = !hasKill(MI.getParent(), UseMI->getParent());
228   }
229 
230   // Add an implicit def of exec to discourage scheduling VALU after this which
231   // will interfere with trying to form s_and_saveexec_b64 later.
232   Register CopyReg = SimpleIf ? SaveExecReg
233                        : MRI->createVirtualRegister(BoolRC);
234   MachineInstr *CopyExec =
235     BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), CopyReg)
236     .addReg(Exec)
237     .addReg(Exec, RegState::ImplicitDefine);
238   LoweredIf.insert(CopyReg);
239 
240   Register Tmp = MRI->createVirtualRegister(BoolRC);
241 
242   MachineInstr *And =
243     BuildMI(MBB, I, DL, TII->get(AndOpc), Tmp)
244     .addReg(CopyReg)
245     .add(Cond);
246   if (LV)
247     LV->replaceKillInstruction(Cond.getReg(), MI, *And);
248 
249   setImpSCCDefDead(*And, true);
250 
251   MachineInstr *Xor = nullptr;
252   if (!SimpleIf) {
253     Xor =
254       BuildMI(MBB, I, DL, TII->get(XorOpc), SaveExecReg)
255       .addReg(Tmp)
256       .addReg(CopyReg);
257     setImpSCCDefDead(*Xor, ImpDefSCC.isDead());
258   }
259 
260   // Use a copy that is a terminator to get correct spill code placement it with
261   // fast regalloc.
262   MachineInstr *SetExec =
263     BuildMI(MBB, I, DL, TII->get(MovTermOpc), Exec)
264     .addReg(Tmp, RegState::Kill);
265   if (LV)
266     LV->getVarInfo(Tmp).Kills.push_back(SetExec);
267 
268   // Skip ahead to the unconditional branch in case there are other terminators
269   // present.
270   I = skipToUncondBrOrEnd(MBB, I);
271 
272   // Insert the S_CBRANCH_EXECZ instruction which will be optimized later
273   // during SIRemoveShortExecBranches.
274   MachineInstr *NewBr = BuildMI(MBB, I, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
275                             .add(MI.getOperand(2));
276 
277   if (!LIS) {
278     MI.eraseFromParent();
279     return;
280   }
281 
282   LIS->InsertMachineInstrInMaps(*CopyExec);
283 
284   // Replace with and so we don't need to fix the live interval for condition
285   // register.
286   LIS->ReplaceMachineInstrInMaps(MI, *And);
287 
288   if (!SimpleIf)
289     LIS->InsertMachineInstrInMaps(*Xor);
290   LIS->InsertMachineInstrInMaps(*SetExec);
291   LIS->InsertMachineInstrInMaps(*NewBr);
292 
293   LIS->removeAllRegUnitsForPhysReg(AMDGPU::EXEC);
294   MI.eraseFromParent();
295 
296   // FIXME: Is there a better way of adjusting the liveness? It shouldn't be
297   // hard to add another def here but I'm not sure how to correctly update the
298   // valno.
299   LIS->removeInterval(SaveExecReg);
300   LIS->createAndComputeVirtRegInterval(SaveExecReg);
301   LIS->createAndComputeVirtRegInterval(Tmp);
302   if (!SimpleIf)
303     LIS->createAndComputeVirtRegInterval(CopyReg);
304 }
305 
306 void SILowerControlFlow::emitElse(MachineInstr &MI) {
307   MachineBasicBlock &MBB = *MI.getParent();
308   const DebugLoc &DL = MI.getDebugLoc();
309 
310   Register DstReg = MI.getOperand(0).getReg();
311 
312   MachineBasicBlock::iterator Start = MBB.begin();
313 
314   // This must be inserted before phis and any spill code inserted before the
315   // else.
316   Register SaveReg = MRI->createVirtualRegister(BoolRC);
317   MachineInstr *OrSaveExec =
318     BuildMI(MBB, Start, DL, TII->get(OrSaveExecOpc), SaveReg)
319     .add(MI.getOperand(1)); // Saved EXEC
320   if (LV)
321     LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *OrSaveExec);
322 
323   MachineBasicBlock *DestBB = MI.getOperand(2).getMBB();
324 
325   MachineBasicBlock::iterator ElsePt(MI);
326 
327   // This accounts for any modification of the EXEC mask within the block and
328   // can be optimized out pre-RA when not required.
329   MachineInstr *And = BuildMI(MBB, ElsePt, DL, TII->get(AndOpc), DstReg)
330                           .addReg(Exec)
331                           .addReg(SaveReg);
332 
333   if (LIS)
334     LIS->InsertMachineInstrInMaps(*And);
335 
336   MachineInstr *Xor =
337     BuildMI(MBB, ElsePt, DL, TII->get(XorTermrOpc), Exec)
338     .addReg(Exec)
339     .addReg(DstReg);
340 
341   // Skip ahead to the unconditional branch in case there are other terminators
342   // present.
343   ElsePt = skipToUncondBrOrEnd(MBB, ElsePt);
344 
345   MachineInstr *Branch =
346       BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
347           .addMBB(DestBB);
348 
349   if (!LIS) {
350     MI.eraseFromParent();
351     return;
352   }
353 
354   LIS->RemoveMachineInstrFromMaps(MI);
355   MI.eraseFromParent();
356 
357   LIS->InsertMachineInstrInMaps(*OrSaveExec);
358 
359   LIS->InsertMachineInstrInMaps(*Xor);
360   LIS->InsertMachineInstrInMaps(*Branch);
361 
362   LIS->removeInterval(DstReg);
363   LIS->createAndComputeVirtRegInterval(DstReg);
364   LIS->createAndComputeVirtRegInterval(SaveReg);
365 
366   // Let this be recomputed.
367   LIS->removeAllRegUnitsForPhysReg(AMDGPU::EXEC);
368 }
369 
370 void SILowerControlFlow::emitIfBreak(MachineInstr &MI) {
371   MachineBasicBlock &MBB = *MI.getParent();
372   const DebugLoc &DL = MI.getDebugLoc();
373   auto Dst = MI.getOperand(0).getReg();
374 
375   // Skip ANDing with exec if the break condition is already masked by exec
376   // because it is a V_CMP in the same basic block. (We know the break
377   // condition operand was an i1 in IR, so if it is a VALU instruction it must
378   // be one with a carry-out.)
379   bool SkipAnding = false;
380   if (MI.getOperand(1).isReg()) {
381     if (MachineInstr *Def = MRI->getUniqueVRegDef(MI.getOperand(1).getReg())) {
382       SkipAnding = Def->getParent() == MI.getParent()
383           && SIInstrInfo::isVALU(*Def);
384     }
385   }
386 
387   // AND the break condition operand with exec, then OR that into the "loop
388   // exit" mask.
389   MachineInstr *And = nullptr, *Or = nullptr;
390   if (!SkipAnding) {
391     Register AndReg = MRI->createVirtualRegister(BoolRC);
392     And = BuildMI(MBB, &MI, DL, TII->get(AndOpc), AndReg)
393              .addReg(Exec)
394              .add(MI.getOperand(1));
395     if (LV)
396       LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *And);
397     Or = BuildMI(MBB, &MI, DL, TII->get(OrOpc), Dst)
398              .addReg(AndReg)
399              .add(MI.getOperand(2));
400     if (LIS)
401       LIS->createAndComputeVirtRegInterval(AndReg);
402   } else {
403     Or = BuildMI(MBB, &MI, DL, TII->get(OrOpc), Dst)
404              .add(MI.getOperand(1))
405              .add(MI.getOperand(2));
406     if (LV)
407       LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *Or);
408   }
409   if (LV)
410     LV->replaceKillInstruction(MI.getOperand(2).getReg(), MI, *Or);
411 
412   if (LIS) {
413     if (And)
414       LIS->InsertMachineInstrInMaps(*And);
415     LIS->ReplaceMachineInstrInMaps(MI, *Or);
416   }
417 
418   MI.eraseFromParent();
419 }
420 
421 void SILowerControlFlow::emitLoop(MachineInstr &MI) {
422   MachineBasicBlock &MBB = *MI.getParent();
423   const DebugLoc &DL = MI.getDebugLoc();
424 
425   MachineInstr *AndN2 =
426       BuildMI(MBB, &MI, DL, TII->get(Andn2TermOpc), Exec)
427           .addReg(Exec)
428           .add(MI.getOperand(0));
429 
430   auto BranchPt = skipToUncondBrOrEnd(MBB, MI.getIterator());
431   MachineInstr *Branch =
432       BuildMI(MBB, BranchPt, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))
433           .add(MI.getOperand(1));
434 
435   if (LIS) {
436     LIS->ReplaceMachineInstrInMaps(MI, *AndN2);
437     LIS->InsertMachineInstrInMaps(*Branch);
438   }
439 
440   MI.eraseFromParent();
441 }
442 
443 MachineBasicBlock::iterator
444 SILowerControlFlow::skipIgnoreExecInstsTrivialSucc(
445   MachineBasicBlock &MBB, MachineBasicBlock::iterator It) const {
446 
447   SmallSet<const MachineBasicBlock *, 4> Visited;
448   MachineBasicBlock *B = &MBB;
449   do {
450     if (!Visited.insert(B).second)
451       return MBB.end();
452 
453     auto E = B->end();
454     for ( ; It != E; ++It) {
455       if (TII->mayReadEXEC(*MRI, *It))
456         break;
457     }
458 
459     if (It != E)
460       return It;
461 
462     if (B->succ_size() != 1)
463       return MBB.end();
464 
465     // If there is one trivial successor, advance to the next block.
466     MachineBasicBlock *Succ = *B->succ_begin();
467 
468     It = Succ->begin();
469     B = Succ;
470   } while (true);
471 }
472 
473 MachineBasicBlock *SILowerControlFlow::emitEndCf(MachineInstr &MI) {
474   MachineBasicBlock &MBB = *MI.getParent();
475   const DebugLoc &DL = MI.getDebugLoc();
476 
477   MachineBasicBlock::iterator InsPt = MBB.begin();
478 
479   // If we have instructions that aren't prolog instructions, split the block
480   // and emit a terminator instruction. This ensures correct spill placement.
481   // FIXME: We should unconditionally split the block here.
482   bool NeedBlockSplit = false;
483   Register DataReg = MI.getOperand(0).getReg();
484   for (MachineBasicBlock::iterator I = InsPt, E = MI.getIterator();
485        I != E; ++I) {
486     if (I->modifiesRegister(DataReg, TRI)) {
487       NeedBlockSplit = true;
488       break;
489     }
490   }
491 
492   unsigned Opcode = OrOpc;
493   MachineBasicBlock *SplitBB = &MBB;
494   if (NeedBlockSplit) {
495     SplitBB = MBB.splitAt(MI, /*UpdateLiveIns*/true, LIS);
496     if (MDT && SplitBB != &MBB) {
497       MachineDomTreeNode *MBBNode = (*MDT)[&MBB];
498       SmallVector<MachineDomTreeNode *> Children(MBBNode->begin(),
499                                                  MBBNode->end());
500       MachineDomTreeNode *SplitBBNode = MDT->addNewBlock(SplitBB, &MBB);
501       for (MachineDomTreeNode *Child : Children)
502         MDT->changeImmediateDominator(Child, SplitBBNode);
503     }
504     Opcode = OrTermrOpc;
505     InsPt = MI;
506   }
507 
508   MachineInstr *NewMI =
509     BuildMI(MBB, InsPt, DL, TII->get(Opcode), Exec)
510     .addReg(Exec)
511     .add(MI.getOperand(0));
512   if (LV)
513     LV->replaceKillInstruction(MI.getOperand(0).getReg(), MI, *NewMI);
514 
515   LoweredEndCf.insert(NewMI);
516 
517   if (LIS)
518     LIS->ReplaceMachineInstrInMaps(MI, *NewMI);
519 
520   MI.eraseFromParent();
521 
522   if (LIS)
523     LIS->handleMove(*NewMI);
524   return SplitBB;
525 }
526 
527 // Returns replace operands for a logical operation, either single result
528 // for exec or two operands if source was another equivalent operation.
529 void SILowerControlFlow::findMaskOperands(MachineInstr &MI, unsigned OpNo,
530        SmallVectorImpl<MachineOperand> &Src) const {
531   MachineOperand &Op = MI.getOperand(OpNo);
532   if (!Op.isReg() || !Op.getReg().isVirtual()) {
533     Src.push_back(Op);
534     return;
535   }
536 
537   MachineInstr *Def = MRI->getUniqueVRegDef(Op.getReg());
538   if (!Def || Def->getParent() != MI.getParent() ||
539       !(Def->isFullCopy() || (Def->getOpcode() == MI.getOpcode())))
540     return;
541 
542   // Make sure we do not modify exec between def and use.
543   // A copy with implcitly defined exec inserted earlier is an exclusion, it
544   // does not really modify exec.
545   for (auto I = Def->getIterator(); I != MI.getIterator(); ++I)
546     if (I->modifiesRegister(AMDGPU::EXEC, TRI) &&
547         !(I->isCopy() && I->getOperand(0).getReg() != Exec))
548       return;
549 
550   for (const auto &SrcOp : Def->explicit_operands())
551     if (SrcOp.isReg() && SrcOp.isUse() &&
552         (SrcOp.getReg().isVirtual() || SrcOp.getReg() == Exec))
553       Src.push_back(SrcOp);
554 }
555 
556 // Search and combine pairs of equivalent instructions, like
557 // S_AND_B64 x, (S_AND_B64 x, y) => S_AND_B64 x, y
558 // S_OR_B64  x, (S_OR_B64  x, y) => S_OR_B64  x, y
559 // One of the operands is exec mask.
560 void SILowerControlFlow::combineMasks(MachineInstr &MI) {
561   assert(MI.getNumExplicitOperands() == 3);
562   SmallVector<MachineOperand, 4> Ops;
563   unsigned OpToReplace = 1;
564   findMaskOperands(MI, 1, Ops);
565   if (Ops.size() == 1) OpToReplace = 2; // First operand can be exec or its copy
566   findMaskOperands(MI, 2, Ops);
567   if (Ops.size() != 3) return;
568 
569   unsigned UniqueOpndIdx;
570   if (Ops[0].isIdenticalTo(Ops[1])) UniqueOpndIdx = 2;
571   else if (Ops[0].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;
572   else if (Ops[1].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;
573   else return;
574 
575   Register Reg = MI.getOperand(OpToReplace).getReg();
576   MI.RemoveOperand(OpToReplace);
577   MI.addOperand(Ops[UniqueOpndIdx]);
578   if (MRI->use_empty(Reg))
579     MRI->getUniqueVRegDef(Reg)->eraseFromParent();
580 }
581 
582 void SILowerControlFlow::optimizeEndCf() {
583   // If the only instruction immediately following this END_CF is an another
584   // END_CF in the only successor we can avoid emitting exec mask restore here.
585   if (!EnableOptimizeEndCf)
586     return;
587 
588   for (MachineInstr *MI : reverse(LoweredEndCf)) {
589     MachineBasicBlock &MBB = *MI->getParent();
590     auto Next =
591       skipIgnoreExecInstsTrivialSucc(MBB, std::next(MI->getIterator()));
592     if (Next == MBB.end() || !LoweredEndCf.count(&*Next))
593       continue;
594     // Only skip inner END_CF if outer ENDCF belongs to SI_IF.
595     // If that belongs to SI_ELSE then saved mask has an inverted value.
596     Register SavedExec
597       = TII->getNamedOperand(*Next, AMDGPU::OpName::src1)->getReg();
598     assert(SavedExec.isVirtual() && "Expected saved exec to be src1!");
599 
600     const MachineInstr *Def = MRI->getUniqueVRegDef(SavedExec);
601     if (Def && LoweredIf.count(SavedExec)) {
602       LLVM_DEBUG(dbgs() << "Skip redundant "; MI->dump());
603       if (LIS)
604         LIS->RemoveMachineInstrFromMaps(*MI);
605       Register Reg;
606       if (LV)
607         Reg = TII->getNamedOperand(*MI, AMDGPU::OpName::src1)->getReg();
608       MI->eraseFromParent();
609       if (LV)
610         LV->recomputeForSingleDefVirtReg(Reg);
611       removeMBBifRedundant(MBB);
612     }
613   }
614 }
615 
616 MachineBasicBlock *SILowerControlFlow::process(MachineInstr &MI) {
617   MachineBasicBlock &MBB = *MI.getParent();
618   MachineBasicBlock::iterator I(MI);
619   MachineInstr *Prev = (I != MBB.begin()) ? &*(std::prev(I)) : nullptr;
620 
621   MachineBasicBlock *SplitBB = &MBB;
622 
623   switch (MI.getOpcode()) {
624   case AMDGPU::SI_IF:
625     emitIf(MI);
626     break;
627 
628   case AMDGPU::SI_ELSE:
629     emitElse(MI);
630     break;
631 
632   case AMDGPU::SI_IF_BREAK:
633     emitIfBreak(MI);
634     break;
635 
636   case AMDGPU::SI_LOOP:
637     emitLoop(MI);
638     break;
639 
640   case AMDGPU::SI_WATERFALL_LOOP:
641     MI.setDesc(TII->get(AMDGPU::S_CBRANCH_EXECNZ));
642     break;
643 
644   case AMDGPU::SI_END_CF:
645     SplitBB = emitEndCf(MI);
646     break;
647 
648   default:
649     assert(false && "Attempt to process unsupported instruction");
650     break;
651   }
652 
653   MachineBasicBlock::iterator Next;
654   for (I = Prev ? Prev->getIterator() : MBB.begin(); I != MBB.end(); I = Next) {
655     Next = std::next(I);
656     MachineInstr &MaskMI = *I;
657     switch (MaskMI.getOpcode()) {
658     case AMDGPU::S_AND_B64:
659     case AMDGPU::S_OR_B64:
660     case AMDGPU::S_AND_B32:
661     case AMDGPU::S_OR_B32:
662       // Cleanup bit manipulations on exec mask
663       combineMasks(MaskMI);
664       break;
665     default:
666       I = MBB.end();
667       break;
668     }
669   }
670 
671   return SplitBB;
672 }
673 
674 void SILowerControlFlow::lowerInitExec(MachineBasicBlock *MBB,
675                                        MachineInstr &MI) {
676   MachineFunction &MF = *MBB->getParent();
677   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
678   bool IsWave32 = ST.isWave32();
679 
680   if (MI.getOpcode() == AMDGPU::SI_INIT_EXEC) {
681     // This should be before all vector instructions.
682     BuildMI(*MBB, MBB->begin(), MI.getDebugLoc(),
683             TII->get(IsWave32 ? AMDGPU::S_MOV_B32 : AMDGPU::S_MOV_B64), Exec)
684         .addImm(MI.getOperand(0).getImm());
685     if (LIS)
686       LIS->RemoveMachineInstrFromMaps(MI);
687     MI.eraseFromParent();
688     return;
689   }
690 
691   // Extract the thread count from an SGPR input and set EXEC accordingly.
692   // Since BFM can't shift by 64, handle that case with CMP + CMOV.
693   //
694   // S_BFE_U32 count, input, {shift, 7}
695   // S_BFM_B64 exec, count, 0
696   // S_CMP_EQ_U32 count, 64
697   // S_CMOV_B64 exec, -1
698   Register InputReg = MI.getOperand(0).getReg();
699   MachineInstr *FirstMI = &*MBB->begin();
700   if (InputReg.isVirtual()) {
701     MachineInstr *DefInstr = MRI->getVRegDef(InputReg);
702     assert(DefInstr && DefInstr->isCopy());
703     if (DefInstr->getParent() == MBB) {
704       if (DefInstr != FirstMI) {
705         // If the `InputReg` is defined in current block, we also need to
706         // move that instruction to the beginning of the block.
707         DefInstr->removeFromParent();
708         MBB->insert(FirstMI, DefInstr);
709         if (LIS)
710           LIS->handleMove(*DefInstr);
711       } else {
712         // If first instruction is definition then move pointer after it.
713         FirstMI = &*std::next(FirstMI->getIterator());
714       }
715     }
716   }
717 
718   // Insert instruction sequence at block beginning (before vector operations).
719   const DebugLoc DL = MI.getDebugLoc();
720   const unsigned WavefrontSize = ST.getWavefrontSize();
721   const unsigned Mask = (WavefrontSize << 1) - 1;
722   Register CountReg = MRI->createVirtualRegister(&AMDGPU::SGPR_32RegClass);
723   auto BfeMI = BuildMI(*MBB, FirstMI, DL, TII->get(AMDGPU::S_BFE_U32), CountReg)
724                    .addReg(InputReg)
725                    .addImm((MI.getOperand(1).getImm() & Mask) | 0x70000);
726   if (LV)
727     LV->recomputeForSingleDefVirtReg(InputReg);
728   auto BfmMI =
729       BuildMI(*MBB, FirstMI, DL,
730               TII->get(IsWave32 ? AMDGPU::S_BFM_B32 : AMDGPU::S_BFM_B64), Exec)
731           .addReg(CountReg)
732           .addImm(0);
733   auto CmpMI = BuildMI(*MBB, FirstMI, DL, TII->get(AMDGPU::S_CMP_EQ_U32))
734                    .addReg(CountReg, RegState::Kill)
735                    .addImm(WavefrontSize);
736   if (LV)
737     LV->getVarInfo(CountReg).Kills.push_back(CmpMI);
738   auto CmovMI =
739       BuildMI(*MBB, FirstMI, DL,
740               TII->get(IsWave32 ? AMDGPU::S_CMOV_B32 : AMDGPU::S_CMOV_B64),
741               Exec)
742           .addImm(-1);
743 
744   if (!LIS) {
745     MI.eraseFromParent();
746     return;
747   }
748 
749   LIS->RemoveMachineInstrFromMaps(MI);
750   MI.eraseFromParent();
751 
752   LIS->InsertMachineInstrInMaps(*BfeMI);
753   LIS->InsertMachineInstrInMaps(*BfmMI);
754   LIS->InsertMachineInstrInMaps(*CmpMI);
755   LIS->InsertMachineInstrInMaps(*CmovMI);
756 
757   LIS->removeInterval(InputReg);
758   LIS->createAndComputeVirtRegInterval(InputReg);
759   LIS->createAndComputeVirtRegInterval(CountReg);
760 }
761 
762 bool SILowerControlFlow::removeMBBifRedundant(MachineBasicBlock &MBB) {
763   for (auto &I : MBB.instrs()) {
764     if (!I.isDebugInstr() && !I.isUnconditionalBranch())
765       return false;
766   }
767 
768   assert(MBB.succ_size() == 1 && "MBB has more than one successor");
769 
770   MachineBasicBlock *Succ = *MBB.succ_begin();
771   MachineBasicBlock *FallThrough = nullptr;
772 
773   while (!MBB.predecessors().empty()) {
774     MachineBasicBlock *P = *MBB.pred_begin();
775     if (P->getFallThrough() == &MBB)
776       FallThrough = P;
777     P->ReplaceUsesOfBlockWith(&MBB, Succ);
778   }
779   MBB.removeSuccessor(Succ);
780   if (LIS) {
781     for (auto &I : MBB.instrs())
782       LIS->RemoveMachineInstrFromMaps(I);
783   }
784   if (MDT) {
785     // If Succ, the single successor of MBB, is dominated by MBB, MDT needs
786     // updating by changing Succ's idom to the one of MBB; otherwise, MBB must
787     // be a leaf node in MDT and could be erased directly.
788     if (MDT->dominates(&MBB, Succ))
789       MDT->changeImmediateDominator(MDT->getNode(Succ),
790                                     MDT->getNode(&MBB)->getIDom());
791     MDT->eraseNode(&MBB);
792   }
793   MBB.clear();
794   MBB.eraseFromParent();
795   if (FallThrough && !FallThrough->isLayoutSuccessor(Succ)) {
796     if (!Succ->canFallThrough()) {
797       MachineFunction *MF = FallThrough->getParent();
798       MachineFunction::iterator FallThroughPos(FallThrough);
799       MF->splice(std::next(FallThroughPos), Succ);
800     } else
801       BuildMI(*FallThrough, FallThrough->end(),
802               FallThrough->findBranchDebugLoc(), TII->get(AMDGPU::S_BRANCH))
803           .addMBB(Succ);
804   }
805 
806   return true;
807 }
808 
809 bool SILowerControlFlow::runOnMachineFunction(MachineFunction &MF) {
810   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
811   TII = ST.getInstrInfo();
812   TRI = &TII->getRegisterInfo();
813   EnableOptimizeEndCf =
814       RemoveRedundantEndcf && MF.getTarget().getOptLevel() > CodeGenOpt::None;
815 
816   // This doesn't actually need LiveIntervals, but we can preserve them.
817   LIS = getAnalysisIfAvailable<LiveIntervals>();
818   // This doesn't actually need LiveVariables, but we can preserve them.
819   LV = getAnalysisIfAvailable<LiveVariables>();
820   MDT = getAnalysisIfAvailable<MachineDominatorTree>();
821   MRI = &MF.getRegInfo();
822   BoolRC = TRI->getBoolRC();
823 
824   if (ST.isWave32()) {
825     AndOpc = AMDGPU::S_AND_B32;
826     OrOpc = AMDGPU::S_OR_B32;
827     XorOpc = AMDGPU::S_XOR_B32;
828     MovTermOpc = AMDGPU::S_MOV_B32_term;
829     Andn2TermOpc = AMDGPU::S_ANDN2_B32_term;
830     XorTermrOpc = AMDGPU::S_XOR_B32_term;
831     OrTermrOpc = AMDGPU::S_OR_B32_term;
832     OrSaveExecOpc = AMDGPU::S_OR_SAVEEXEC_B32;
833     Exec = AMDGPU::EXEC_LO;
834   } else {
835     AndOpc = AMDGPU::S_AND_B64;
836     OrOpc = AMDGPU::S_OR_B64;
837     XorOpc = AMDGPU::S_XOR_B64;
838     MovTermOpc = AMDGPU::S_MOV_B64_term;
839     Andn2TermOpc = AMDGPU::S_ANDN2_B64_term;
840     XorTermrOpc = AMDGPU::S_XOR_B64_term;
841     OrTermrOpc = AMDGPU::S_OR_B64_term;
842     OrSaveExecOpc = AMDGPU::S_OR_SAVEEXEC_B64;
843     Exec = AMDGPU::EXEC;
844   }
845 
846   // Compute set of blocks with kills
847   const bool CanDemote =
848       MF.getFunction().getCallingConv() == CallingConv::AMDGPU_PS;
849   for (auto &MBB : MF) {
850     bool IsKillBlock = false;
851     for (auto &Term : MBB.terminators()) {
852       if (TII->isKillTerminator(Term.getOpcode())) {
853         KillBlocks.insert(&MBB);
854         IsKillBlock = true;
855         break;
856       }
857     }
858     if (CanDemote && !IsKillBlock) {
859       for (auto &MI : MBB) {
860         if (MI.getOpcode() == AMDGPU::SI_DEMOTE_I1) {
861           KillBlocks.insert(&MBB);
862           break;
863         }
864       }
865     }
866   }
867 
868   MachineFunction::iterator NextBB;
869   for (MachineFunction::iterator BI = MF.begin();
870        BI != MF.end(); BI = NextBB) {
871     NextBB = std::next(BI);
872     MachineBasicBlock *MBB = &*BI;
873 
874     MachineBasicBlock::iterator I, E, Next;
875     E = MBB->end();
876     for (I = MBB->begin(); I != E; I = Next) {
877       Next = std::next(I);
878       MachineInstr &MI = *I;
879       MachineBasicBlock *SplitMBB = MBB;
880 
881       switch (MI.getOpcode()) {
882       case AMDGPU::SI_IF:
883       case AMDGPU::SI_ELSE:
884       case AMDGPU::SI_IF_BREAK:
885       case AMDGPU::SI_WATERFALL_LOOP:
886       case AMDGPU::SI_LOOP:
887       case AMDGPU::SI_END_CF:
888         SplitMBB = process(MI);
889         break;
890 
891       // FIXME: find a better place for this
892       case AMDGPU::SI_INIT_EXEC:
893       case AMDGPU::SI_INIT_EXEC_FROM_INPUT:
894         lowerInitExec(MBB, MI);
895         if (LIS)
896           LIS->removeAllRegUnitsForPhysReg(AMDGPU::EXEC);
897         break;
898 
899       default:
900         break;
901       }
902 
903       if (SplitMBB != MBB) {
904         MBB = Next->getParent();
905         E = MBB->end();
906       }
907     }
908   }
909 
910   optimizeEndCf();
911 
912   LoweredEndCf.clear();
913   LoweredIf.clear();
914   KillBlocks.clear();
915 
916   return true;
917 }
918