lib/Target/AMDGPU/SIInsertSkips.cpp

   1 //===-- SIInsertSkips.cpp - Use predicates for control flow ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// \file
  11 /// This pass inserts branches on the 0 exec mask over divergent branches
  12 /// branches when it's expected that jumping over the untaken control flow will
  13 /// be cheaper than having every workitem no-op through it.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "AMDGPU.h"
  18 #include "AMDGPUSubtarget.h"
  19 #include "SIInstrInfo.h"
  20 #include "SIMachineFunctionInfo.h"
  21 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/CodeGen/MachineBasicBlock.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/CodeGen/MachineInstr.h"
  28 #include "llvm/CodeGen/MachineInstrBuilder.h"
  29 #include "llvm/CodeGen/MachineOperand.h"
  30 #include "llvm/IR/CallingConv.h"
  31 #include "llvm/IR/DebugLoc.h"
  32 #include "llvm/MC/MCAsmInfo.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Target/TargetMachine.h"
  36 #include <cassert>
  37 #include <cstdint>
  38 #include <iterator>
  39
  40 using namespace llvm;
  41
  42 #define DEBUG_TYPE "si-insert-skips"
  43
  44 static cl::opt<unsigned> SkipThresholdFlag(
  45   "amdgpu-skip-threshold",
  46   cl::desc("Number of instructions before jumping over divergent control flow"),
  47   cl::init(12), cl::Hidden);
  48
  49 namespace {
  50
  51 class SIInsertSkips : public MachineFunctionPass {
  52 private:
  53   const SIRegisterInfo *TRI = nullptr;
  54   const SIInstrInfo *TII = nullptr;
  55   unsigned SkipThreshold = 0;
  56
  57   bool shouldSkip(const MachineBasicBlock &From,
  58                   const MachineBasicBlock &To) const;
  59
  60   bool skipIfDead(MachineInstr &MI, MachineBasicBlock &NextBB);
  61
  62   void kill(MachineInstr &MI);
  63
  64   MachineBasicBlock *insertSkipBlock(MachineBasicBlock &MBB,
  65                                      MachineBasicBlock::iterator I) const;
  66
  67   bool skipMaskBranch(MachineInstr &MI, MachineBasicBlock &MBB);
  68
  69 public:
  70   static char ID;
  71
  72   SIInsertSkips() : MachineFunctionPass(ID) {}
  73
  74   bool runOnMachineFunction(MachineFunction &MF) override;
  75
  76   StringRef getPassName() const override {
  77     return "SI insert s_cbranch_execz instructions";
  78   }
  79
  80   void getAnalysisUsage(AnalysisUsage &AU) const override {
  81     MachineFunctionPass::getAnalysisUsage(AU);
  82   }
  83 };
  84
  85 } // end anonymous namespace
  86
  87 char SIInsertSkips::ID = 0;
  88
  89 INITIALIZE_PASS(SIInsertSkips, DEBUG_TYPE,
  90                 "SI insert s_cbranch_execz instructions", false, false)
  91
  92 char &llvm::SIInsertSkipsPassID = SIInsertSkips::ID;
  93
  94 static bool opcodeEmitsNoInsts(unsigned Opc) {
  95   switch (Opc) {
  96   case TargetOpcode::IMPLICIT_DEF:
  97   case TargetOpcode::KILL:
  98   case TargetOpcode::BUNDLE:
  99   case TargetOpcode::CFI_INSTRUCTION:
 100   case TargetOpcode::EH_LABEL:
 101   case TargetOpcode::GC_LABEL:
 102   case TargetOpcode::DBG_VALUE:
 103     return true;
 104   default:
 105     return false;
 106   }
 107 }
 108
 109 bool SIInsertSkips::shouldSkip(const MachineBasicBlock &From,
 110                                const MachineBasicBlock &To) const {
 111   if (From.succ_empty())
 112     return false;
 113
 114   unsigned NumInstr = 0;
 115   const MachineFunction *MF = From.getParent();
 116
 117   for (MachineFunction::const_iterator MBBI(&From), ToI(&To), End = MF->end();
 118        MBBI != End && MBBI != ToI; ++MBBI) {
 119     const MachineBasicBlock &MBB = *MBBI;
 120
 121     for (MachineBasicBlock::const_iterator I = MBB.begin(), E = MBB.end();
 122          NumInstr < SkipThreshold && I != E; ++I) {
 123       if (opcodeEmitsNoInsts(I->getOpcode()))
 124         continue;
 125
 126       // FIXME: Since this is required for correctness, this should be inserted
 127       // during SILowerControlFlow.
 128
 129       // When a uniform loop is inside non-uniform control flow, the branch
 130       // leaving the loop might be an S_CBRANCH_VCCNZ, which is never taken
 131       // when EXEC = 0. We should skip the loop lest it becomes infinite.
 132       if (I->getOpcode() == AMDGPU::S_CBRANCH_VCCNZ ||
 133           I->getOpcode() == AMDGPU::S_CBRANCH_VCCZ)
 134         return true;
 135
 136       if (TII->hasUnwantedEffectsWhenEXECEmpty(*I))
 137         return true;
 138
 139       ++NumInstr;
 140       if (NumInstr >= SkipThreshold)
 141         return true;
 142     }
 143   }
 144
 145   return false;
 146 }
 147
 148 bool SIInsertSkips::skipIfDead(MachineInstr &MI, MachineBasicBlock &NextBB) {
 149   MachineBasicBlock &MBB = *MI.getParent();
 150   MachineFunction *MF = MBB.getParent();
 151
 152   if (MF->getFunction().getCallingConv() != CallingConv::AMDGPU_PS ||
 153       !shouldSkip(MBB, MBB.getParent()->back()))
 154     return false;
 155
 156   MachineBasicBlock *SkipBB = insertSkipBlock(MBB, MI.getIterator());
 157
 158   const DebugLoc &DL = MI.getDebugLoc();
 159
 160   // If the exec mask is non-zero, skip the next two instructions
 161   BuildMI(&MBB, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))
 162     .addMBB(&NextBB);
 163
 164   MachineBasicBlock::iterator Insert = SkipBB->begin();
 165
 166   // Exec mask is zero: Export to NULL target...
 167   BuildMI(*SkipBB, Insert, DL, TII->get(AMDGPU::EXP_DONE))
 168     .addImm(0x09) // V_008DFC_SQ_EXP_NULL
 169     .addReg(AMDGPU::VGPR0, RegState::Undef)
 170     .addReg(AMDGPU::VGPR0, RegState::Undef)
 171     .addReg(AMDGPU::VGPR0, RegState::Undef)
 172     .addReg(AMDGPU::VGPR0, RegState::Undef)
 173     .addImm(1)  // vm
 174     .addImm(0)  // compr
 175     .addImm(0); // en
 176
 177   // ... and terminate wavefront.
 178   BuildMI(*SkipBB, Insert, DL, TII->get(AMDGPU::S_ENDPGM));
 179
 180   return true;
 181 }
 182
 183 void SIInsertSkips::kill(MachineInstr &MI) {
 184   MachineBasicBlock &MBB = *MI.getParent();
 185   DebugLoc DL = MI.getDebugLoc();
 186
 187   switch (MI.getOpcode()) {
 188   case AMDGPU::SI_KILL_F32_COND_IMM_TERMINATOR: {
 189     unsigned Opcode = 0;
 190
 191     // The opcodes are inverted because the inline immediate has to be
 192     // the first operand, e.g. from "x < imm" to "imm > x"
 193     switch (MI.getOperand(2).getImm()) {
 194     case ISD::SETOEQ:
 195     case ISD::SETEQ:
 196       Opcode = AMDGPU::V_CMPX_EQ_F32_e64;
 197       break;
 198     case ISD::SETOGT:
 199     case ISD::SETGT:
 200       Opcode = AMDGPU::V_CMPX_LT_F32_e64;
 201       break;
 202     case ISD::SETOGE:
 203     case ISD::SETGE:
 204       Opcode = AMDGPU::V_CMPX_LE_F32_e64;
 205       break;
 206     case ISD::SETOLT:
 207     case ISD::SETLT:
 208       Opcode = AMDGPU::V_CMPX_GT_F32_e64;
 209       break;
 210     case ISD::SETOLE:
 211     case ISD::SETLE:
 212       Opcode = AMDGPU::V_CMPX_GE_F32_e64;
 213       break;
 214     case ISD::SETONE:
 215     case ISD::SETNE:
 216       Opcode = AMDGPU::V_CMPX_LG_F32_e64;
 217       break;
 218     case ISD::SETO:
 219       Opcode = AMDGPU::V_CMPX_O_F32_e64;
 220       break;
 221     case ISD::SETUO:
 222       Opcode = AMDGPU::V_CMPX_U_F32_e64;
 223       break;
 224     case ISD::SETUEQ:
 225       Opcode = AMDGPU::V_CMPX_NLG_F32_e64;
 226       break;
 227     case ISD::SETUGT:
 228       Opcode = AMDGPU::V_CMPX_NGE_F32_e64;
 229       break;
 230     case ISD::SETUGE:
 231       Opcode = AMDGPU::V_CMPX_NGT_F32_e64;
 232       break;
 233     case ISD::SETULT:
 234       Opcode = AMDGPU::V_CMPX_NLE_F32_e64;
 235       break;
 236     case ISD::SETULE:
 237       Opcode = AMDGPU::V_CMPX_NLT_F32_e64;
 238       break;
 239     case ISD::SETUNE:
 240       Opcode = AMDGPU::V_CMPX_NEQ_F32_e64;
 241       break;
 242     default:
 243       llvm_unreachable("invalid ISD:SET cond code");
 244     }
 245
 246     assert(MI.getOperand(0).isReg());
 247
 248     if (TRI->isVGPR(MBB.getParent()->getRegInfo(),
 249                     MI.getOperand(0).getReg())) {
 250       Opcode = AMDGPU::getVOPe32(Opcode);
 251       BuildMI(MBB, &MI, DL, TII->get(Opcode))
 252           .add(MI.getOperand(1))
 253           .add(MI.getOperand(0));
 254     } else {
 255       BuildMI(MBB, &MI, DL, TII->get(Opcode))
 256           .addReg(AMDGPU::VCC, RegState::Define)
 257           .addImm(0)  // src0 modifiers
 258           .add(MI.getOperand(1))
 259           .addImm(0)  // src1 modifiers
 260           .add(MI.getOperand(0))
 261           .addImm(0);  // omod
 262     }
 263     break;
 264   }
 265   case AMDGPU::SI_KILL_I1_TERMINATOR: {
 266     const MachineOperand &Op = MI.getOperand(0);
 267     int64_t KillVal = MI.getOperand(1).getImm();
 268     assert(KillVal == 0 || KillVal == -1);
 269
 270     // Kill all threads if Op0 is an immediate and equal to the Kill value.
 271     if (Op.isImm()) {
 272       int64_t Imm = Op.getImm();
 273       assert(Imm == 0 || Imm == -1);
 274
 275       if (Imm == KillVal)
 276         BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_MOV_B64), AMDGPU::EXEC)
 277           .addImm(0);
 278       break;
 279     }
 280
 281     unsigned Opcode = KillVal ? AMDGPU::S_ANDN2_B64 : AMDGPU::S_AND_B64;
 282     BuildMI(MBB, &MI, DL, TII->get(Opcode), AMDGPU::EXEC)
 283         .addReg(AMDGPU::EXEC)
 284         .add(Op);
 285     break;
 286   }
 287   default:
 288     llvm_unreachable("invalid opcode, expected SI_KILL_*_TERMINATOR");
 289   }
 290 }
 291
 292 MachineBasicBlock *SIInsertSkips::insertSkipBlock(
 293   MachineBasicBlock &MBB, MachineBasicBlock::iterator I) const {
 294   MachineFunction *MF = MBB.getParent();
 295
 296   MachineBasicBlock *SkipBB = MF->CreateMachineBasicBlock();
 297   MachineFunction::iterator MBBI(MBB);
 298   ++MBBI;
 299
 300   MF->insert(MBBI, SkipBB);
 301   MBB.addSuccessor(SkipBB);
 302
 303   return SkipBB;
 304 }
 305
 306 // Returns true if a branch over the block was inserted.
 307 bool SIInsertSkips::skipMaskBranch(MachineInstr &MI,
 308                                    MachineBasicBlock &SrcMBB) {
 309   MachineBasicBlock *DestBB = MI.getOperand(0).getMBB();
 310
 311   if (!shouldSkip(**SrcMBB.succ_begin(), *DestBB))
 312     return false;
 313
 314   const DebugLoc &DL = MI.getDebugLoc();
 315   MachineBasicBlock::iterator InsPt = std::next(MI.getIterator());
 316
 317   BuildMI(SrcMBB, InsPt, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
 318     .addMBB(DestBB);
 319
 320   return true;
 321 }
 322
 323 bool SIInsertSkips::runOnMachineFunction(MachineFunction &MF) {
 324   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
 325   TII = ST.getInstrInfo();
 326   TRI = &TII->getRegisterInfo();
 327   SkipThreshold = SkipThresholdFlag;
 328
 329   bool HaveKill = false;
 330   bool MadeChange = false;
 331
 332   // Track depth of exec mask, divergent branches.
 333   SmallVector<MachineBasicBlock *, 16> ExecBranchStack;
 334
 335   MachineFunction::iterator NextBB;
 336
 337   MachineBasicBlock *EmptyMBBAtEnd = nullptr;
 338
 339   for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
 340        BI != BE; BI = NextBB) {
 341     NextBB = std::next(BI);
 342     MachineBasicBlock &MBB = *BI;
 343     bool HaveSkipBlock = false;
 344
 345     if (!ExecBranchStack.empty() && ExecBranchStack.back() == &MBB) {
 346       // Reached convergence point for last divergent branch.
 347       ExecBranchStack.pop_back();
 348     }
 349
 350     if (HaveKill && ExecBranchStack.empty()) {
 351       HaveKill = false;
 352
 353       // TODO: Insert skip if exec is 0?
 354     }
 355
 356     MachineBasicBlock::iterator I, Next;
 357     for (I = MBB.begin(); I != MBB.end(); I = Next) {
 358       Next = std::next(I);
 359
 360       MachineInstr &MI = *I;
 361
 362       switch (MI.getOpcode()) {
 363       case AMDGPU::SI_MASK_BRANCH:
 364         ExecBranchStack.push_back(MI.getOperand(0).getMBB());
 365         MadeChange |= skipMaskBranch(MI, MBB);
 366         break;
 367
 368       case AMDGPU::S_BRANCH:
 369         // Optimize out branches to the next block.
 370         // FIXME: Shouldn't this be handled by BranchFolding?
 371         if (MBB.isLayoutSuccessor(MI.getOperand(0).getMBB())) {
 372           MI.eraseFromParent();
 373         } else if (HaveSkipBlock) {
 374           // Remove the given unconditional branch when a skip block has been
 375           // inserted after the current one and let skip the two instructions
 376           // performing the kill if the exec mask is non-zero.
 377           MI.eraseFromParent();
 378         }
 379         break;
 380
 381       case AMDGPU::SI_KILL_F32_COND_IMM_TERMINATOR:
 382       case AMDGPU::SI_KILL_I1_TERMINATOR:
 383         MadeChange = true;
 384         kill(MI);
 385
 386         if (ExecBranchStack.empty()) {
 387           if (skipIfDead(MI, *NextBB)) {
 388             HaveSkipBlock = true;
 389             NextBB = std::next(BI);
 390             BE = MF.end();
 391           }
 392         } else {
 393           HaveKill = true;
 394         }
 395
 396         MI.eraseFromParent();
 397         break;
 398
 399       case AMDGPU::SI_RETURN_TO_EPILOG:
 400         // FIXME: Should move somewhere else
 401         assert(!MF.getInfo<SIMachineFunctionInfo>()->returnsVoid());
 402
 403         // Graphics shaders returning non-void shouldn't contain S_ENDPGM,
 404         // because external bytecode will be appended at the end.
 405         if (BI != --MF.end() || I != MBB.getFirstTerminator()) {
 406           // SI_RETURN_TO_EPILOG is not the last instruction. Add an empty block at
 407           // the end and jump there.
 408           if (!EmptyMBBAtEnd) {
 409             EmptyMBBAtEnd = MF.CreateMachineBasicBlock();
 410             MF.insert(MF.end(), EmptyMBBAtEnd);
 411           }
 412
 413           MBB.addSuccessor(EmptyMBBAtEnd);
 414           BuildMI(*BI, I, MI.getDebugLoc(), TII->get(AMDGPU::S_BRANCH))
 415             .addMBB(EmptyMBBAtEnd);
 416           I->eraseFromParent();
 417         }
 418         break;
 419
 420       default:
 421         break;
 422       }
 423     }
 424   }
 425
 426   return MadeChange;
 427 }