contrib/llvm-project/llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

   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
  74 using namespace llvm;
  75
  76 #define DEBUG_TYPE "si-lower-control-flow"
  77
  78 static cl::opt<bool>
  79 RemoveRedundantEndcf("amdgpu-remove-redundant-endcf",
  80     cl::init(true), cl::ReallyHidden);
  81
  82 namespace {
  83
  84 class SILowerControlFlow : public MachineFunctionPass {
  85 private:
  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
 128 public:
 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
 153 char SILowerControlFlow::ID = 0;
 154
 155 INITIALIZE_PASS(SILowerControlFlow, DEBUG_TYPE,
 156                "SI lower control flow", false, false)
 157
 158 static 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
 165 char &llvm::SILowerControlFlowID = SILowerControlFlow::ID;
 166
 167 static 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
 188 static 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
 200 void 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
 312 void 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
 385 void 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
 429 void 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
 450 MachineBasicBlock::iterator
 451 SILowerControlFlow::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
 482 void 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.
 519 void 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.
 550 void 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
 572 void 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
 600 void 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
 650 bool 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 }