Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 1 | //===-- SIInsertSkips.cpp - Use predicates for control flow ---------------===// |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 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 | /// \brief 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 | // |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 15 | //===----------------------------------------------------------------------===// |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 16 | |
| 17 | #include "AMDGPU.h" |
| 18 | #include "AMDGPUSubtarget.h" |
| 19 | #include "SIInstrInfo.h" |
| 20 | #include "SIMachineFunctionInfo.h" |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 21 | #include "llvm/ADT/SmallVector.h" |
| 22 | #include "llvm/ADT/StringRef.h" |
| 23 | #include "llvm/CodeGen/MachineBasicBlock.h" |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/MachineFunction.h" |
| 25 | #include "llvm/CodeGen/MachineFunctionPass.h" |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 26 | #include "llvm/CodeGen/MachineInstr.h" |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 27 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 28 | #include "llvm/CodeGen/MachineOperand.h" |
| 29 | #include "llvm/IR/CallingConv.h" |
| 30 | #include "llvm/IR/DebugLoc.h" |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 31 | #include "llvm/MC/MCAsmInfo.h" |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 32 | #include "llvm/Pass.h" |
| 33 | #include "llvm/Support/CommandLine.h" |
| 34 | #include "llvm/Target/TargetMachine.h" |
| 35 | #include <cassert> |
| 36 | #include <cstdint> |
| 37 | #include <iterator> |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 38 | |
| 39 | using namespace llvm; |
| 40 | |
| 41 | #define DEBUG_TYPE "si-insert-skips" |
| 42 | |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 43 | static cl::opt<unsigned> SkipThresholdFlag( |
| 44 | "amdgpu-skip-threshold", |
| 45 | cl::desc("Number of instructions before jumping over divergent control flow"), |
| 46 | cl::init(12), cl::Hidden); |
| 47 | |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 48 | namespace { |
| 49 | |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 50 | class SIInsertSkips : public MachineFunctionPass { |
| 51 | private: |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 52 | const SIRegisterInfo *TRI = nullptr; |
| 53 | const SIInstrInfo *TII = nullptr; |
| 54 | unsigned SkipThreshold = 0; |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 55 | |
| 56 | bool shouldSkip(const MachineBasicBlock &From, |
| 57 | const MachineBasicBlock &To) const; |
| 58 | |
| 59 | bool skipIfDead(MachineInstr &MI, MachineBasicBlock &NextBB); |
| 60 | |
| 61 | void kill(MachineInstr &MI); |
| 62 | |
| 63 | MachineBasicBlock *insertSkipBlock(MachineBasicBlock &MBB, |
| 64 | MachineBasicBlock::iterator I) const; |
| 65 | |
| 66 | bool skipMaskBranch(MachineInstr &MI, MachineBasicBlock &MBB); |
| 67 | |
| 68 | public: |
| 69 | static char ID; |
| 70 | |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 71 | SIInsertSkips() : MachineFunctionPass(ID) {} |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 72 | |
| 73 | bool runOnMachineFunction(MachineFunction &MF) override; |
| 74 | |
Mehdi Amini | 117296c | 2016-10-01 02:56:57 +0000 | [diff] [blame] | 75 | StringRef getPassName() const override { |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 76 | return "SI insert s_cbranch_execz instructions"; |
| 77 | } |
| 78 | |
| 79 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 80 | MachineFunctionPass::getAnalysisUsage(AU); |
| 81 | } |
| 82 | }; |
| 83 | |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 84 | } // end anonymous namespace |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 85 | |
| 86 | char SIInsertSkips::ID = 0; |
| 87 | |
| 88 | INITIALIZE_PASS(SIInsertSkips, DEBUG_TYPE, |
| 89 | "SI insert s_cbranch_execz instructions", false, false) |
| 90 | |
| 91 | char &llvm::SIInsertSkipsPassID = SIInsertSkips::ID; |
| 92 | |
| 93 | static bool opcodeEmitsNoInsts(unsigned Opc) { |
| 94 | switch (Opc) { |
| 95 | case TargetOpcode::IMPLICIT_DEF: |
| 96 | case TargetOpcode::KILL: |
| 97 | case TargetOpcode::BUNDLE: |
| 98 | case TargetOpcode::CFI_INSTRUCTION: |
| 99 | case TargetOpcode::EH_LABEL: |
| 100 | case TargetOpcode::GC_LABEL: |
| 101 | case TargetOpcode::DBG_VALUE: |
| 102 | return true; |
| 103 | default: |
| 104 | return false; |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | bool SIInsertSkips::shouldSkip(const MachineBasicBlock &From, |
| 109 | const MachineBasicBlock &To) const { |
| 110 | if (From.succ_empty()) |
| 111 | return false; |
| 112 | |
| 113 | unsigned NumInstr = 0; |
| 114 | const MachineFunction *MF = From.getParent(); |
| 115 | |
| 116 | for (MachineFunction::const_iterator MBBI(&From), ToI(&To), End = MF->end(); |
| 117 | MBBI != End && MBBI != ToI; ++MBBI) { |
| 118 | const MachineBasicBlock &MBB = *MBBI; |
| 119 | |
| 120 | for (MachineBasicBlock::const_iterator I = MBB.begin(), E = MBB.end(); |
| 121 | NumInstr < SkipThreshold && I != E; ++I) { |
| 122 | if (opcodeEmitsNoInsts(I->getOpcode())) |
| 123 | continue; |
| 124 | |
| 125 | // FIXME: Since this is required for correctness, this should be inserted |
| 126 | // during SILowerControlFlow. |
| 127 | |
| 128 | // When a uniform loop is inside non-uniform control flow, the branch |
| 129 | // leaving the loop might be an S_CBRANCH_VCCNZ, which is never taken |
| 130 | // when EXEC = 0. We should skip the loop lest it becomes infinite. |
| 131 | if (I->getOpcode() == AMDGPU::S_CBRANCH_VCCNZ || |
| 132 | I->getOpcode() == AMDGPU::S_CBRANCH_VCCZ) |
| 133 | return true; |
| 134 | |
| 135 | if (I->isInlineAsm()) { |
| 136 | const MCAsmInfo *MAI = MF->getTarget().getMCAsmInfo(); |
| 137 | const char *AsmStr = I->getOperand(0).getSymbolName(); |
| 138 | |
| 139 | // inlineasm length estimate is number of bytes assuming the longest |
| 140 | // instruction. |
| 141 | uint64_t MaxAsmSize = TII->getInlineAsmLength(AsmStr, *MAI); |
| 142 | NumInstr += MaxAsmSize / MAI->getMaxInstLength(); |
| 143 | } else { |
| 144 | ++NumInstr; |
| 145 | } |
| 146 | |
| 147 | if (NumInstr >= SkipThreshold) |
| 148 | return true; |
| 149 | } |
| 150 | } |
| 151 | |
| 152 | return false; |
| 153 | } |
| 154 | |
| 155 | bool SIInsertSkips::skipIfDead(MachineInstr &MI, MachineBasicBlock &NextBB) { |
| 156 | MachineBasicBlock &MBB = *MI.getParent(); |
| 157 | MachineFunction *MF = MBB.getParent(); |
| 158 | |
| 159 | if (MF->getFunction()->getCallingConv() != CallingConv::AMDGPU_PS || |
| 160 | !shouldSkip(MBB, MBB.getParent()->back())) |
| 161 | return false; |
| 162 | |
| 163 | MachineBasicBlock *SkipBB = insertSkipBlock(MBB, MI.getIterator()); |
| 164 | |
| 165 | const DebugLoc &DL = MI.getDebugLoc(); |
| 166 | |
| 167 | // If the exec mask is non-zero, skip the next two instructions |
| 168 | BuildMI(&MBB, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ)) |
| 169 | .addMBB(&NextBB); |
| 170 | |
| 171 | MachineBasicBlock::iterator Insert = SkipBB->begin(); |
| 172 | |
| 173 | // Exec mask is zero: Export to NULL target... |
Matt Arsenault | 7bee6ac | 2016-12-05 20:23:10 +0000 | [diff] [blame] | 174 | BuildMI(*SkipBB, Insert, DL, TII->get(AMDGPU::EXP_DONE)) |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 175 | .addImm(0x09) // V_008DFC_SQ_EXP_NULL |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 176 | .addReg(AMDGPU::VGPR0, RegState::Undef) |
| 177 | .addReg(AMDGPU::VGPR0, RegState::Undef) |
| 178 | .addReg(AMDGPU::VGPR0, RegState::Undef) |
Matt Arsenault | 7bee6ac | 2016-12-05 20:23:10 +0000 | [diff] [blame] | 179 | .addReg(AMDGPU::VGPR0, RegState::Undef) |
| 180 | .addImm(1) // vm |
| 181 | .addImm(0) // compr |
| 182 | .addImm(0); // en |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 183 | |
| 184 | // ... and terminate wavefront. |
| 185 | BuildMI(*SkipBB, Insert, DL, TII->get(AMDGPU::S_ENDPGM)); |
| 186 | |
| 187 | return true; |
| 188 | } |
| 189 | |
| 190 | void SIInsertSkips::kill(MachineInstr &MI) { |
| 191 | MachineBasicBlock &MBB = *MI.getParent(); |
| 192 | DebugLoc DL = MI.getDebugLoc(); |
| 193 | const MachineOperand &Op = MI.getOperand(0); |
| 194 | |
| 195 | #ifndef NDEBUG |
| 196 | CallingConv::ID CallConv = MBB.getParent()->getFunction()->getCallingConv(); |
| 197 | // Kill is only allowed in pixel / geometry shaders. |
| 198 | assert(CallConv == CallingConv::AMDGPU_PS || |
| 199 | CallConv == CallingConv::AMDGPU_GS); |
| 200 | #endif |
| 201 | // Clear this thread from the exec mask if the operand is negative. |
| 202 | if (Op.isImm()) { |
| 203 | // Constant operand: Set exec mask to 0 or do nothing |
| 204 | if (Op.getImm() & 0x80000000) { |
| 205 | BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_MOV_B64), AMDGPU::EXEC) |
| 206 | .addImm(0); |
| 207 | } |
| 208 | } else { |
| 209 | BuildMI(MBB, &MI, DL, TII->get(AMDGPU::V_CMPX_LE_F32_e32)) |
Diana Picus | 116bbab | 2017-01-13 09:58:52 +0000 | [diff] [blame] | 210 | .addImm(0) |
| 211 | .add(Op); |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 212 | } |
| 213 | } |
| 214 | |
| 215 | MachineBasicBlock *SIInsertSkips::insertSkipBlock( |
| 216 | MachineBasicBlock &MBB, MachineBasicBlock::iterator I) const { |
| 217 | MachineFunction *MF = MBB.getParent(); |
| 218 | |
| 219 | MachineBasicBlock *SkipBB = MF->CreateMachineBasicBlock(); |
| 220 | MachineFunction::iterator MBBI(MBB); |
| 221 | ++MBBI; |
| 222 | |
| 223 | MF->insert(MBBI, SkipBB); |
| 224 | MBB.addSuccessor(SkipBB); |
| 225 | |
| 226 | return SkipBB; |
| 227 | } |
| 228 | |
| 229 | // Returns true if a branch over the block was inserted. |
| 230 | bool SIInsertSkips::skipMaskBranch(MachineInstr &MI, |
| 231 | MachineBasicBlock &SrcMBB) { |
| 232 | MachineBasicBlock *DestBB = MI.getOperand(0).getMBB(); |
| 233 | |
| 234 | if (!shouldSkip(**SrcMBB.succ_begin(), *DestBB)) |
| 235 | return false; |
| 236 | |
| 237 | const DebugLoc &DL = MI.getDebugLoc(); |
| 238 | MachineBasicBlock::iterator InsPt = std::next(MI.getIterator()); |
| 239 | |
| 240 | BuildMI(SrcMBB, InsPt, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ)) |
| 241 | .addMBB(DestBB); |
| 242 | |
| 243 | return true; |
| 244 | } |
| 245 | |
| 246 | bool SIInsertSkips::runOnMachineFunction(MachineFunction &MF) { |
| 247 | const SISubtarget &ST = MF.getSubtarget<SISubtarget>(); |
| 248 | TII = ST.getInstrInfo(); |
| 249 | TRI = &TII->getRegisterInfo(); |
| 250 | SkipThreshold = SkipThresholdFlag; |
| 251 | |
| 252 | bool HaveKill = false; |
| 253 | bool MadeChange = false; |
| 254 | |
| 255 | // Track depth of exec mask, divergent branches. |
| 256 | SmallVector<MachineBasicBlock *, 16> ExecBranchStack; |
| 257 | |
| 258 | MachineFunction::iterator NextBB; |
| 259 | |
| 260 | MachineBasicBlock *EmptyMBBAtEnd = nullptr; |
| 261 | |
| 262 | for (MachineFunction::iterator BI = MF.begin(), BE = MF.end(); |
| 263 | BI != BE; BI = NextBB) { |
| 264 | NextBB = std::next(BI); |
| 265 | MachineBasicBlock &MBB = *BI; |
Matt Arsenault | bf67cf7 | 2017-01-24 22:18:39 +0000 | [diff] [blame] | 266 | bool HaveSkipBlock = false; |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 267 | |
| 268 | if (!ExecBranchStack.empty() && ExecBranchStack.back() == &MBB) { |
| 269 | // Reached convergence point for last divergent branch. |
| 270 | ExecBranchStack.pop_back(); |
| 271 | } |
| 272 | |
| 273 | if (HaveKill && ExecBranchStack.empty()) { |
| 274 | HaveKill = false; |
| 275 | |
| 276 | // TODO: Insert skip if exec is 0? |
| 277 | } |
| 278 | |
| 279 | MachineBasicBlock::iterator I, Next; |
| 280 | for (I = MBB.begin(); I != MBB.end(); I = Next) { |
| 281 | Next = std::next(I); |
| 282 | |
| 283 | MachineInstr &MI = *I; |
| 284 | |
| 285 | switch (MI.getOpcode()) { |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 286 | case AMDGPU::SI_MASK_BRANCH: |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 287 | ExecBranchStack.push_back(MI.getOperand(0).getMBB()); |
| 288 | MadeChange |= skipMaskBranch(MI, MBB); |
| 289 | break; |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 290 | |
| 291 | case AMDGPU::S_BRANCH: |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 292 | // Optimize out branches to the next block. |
| 293 | // FIXME: Shouldn't this be handled by BranchFolding? |
Matt Arsenault | bf67cf7 | 2017-01-24 22:18:39 +0000 | [diff] [blame] | 294 | if (MBB.isLayoutSuccessor(MI.getOperand(0).getMBB())) { |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 295 | MI.eraseFromParent(); |
Matt Arsenault | bf67cf7 | 2017-01-24 22:18:39 +0000 | [diff] [blame] | 296 | } else if (HaveSkipBlock) { |
| 297 | // Remove the given unconditional branch when a skip block has been |
| 298 | // inserted after the current one and let skip the two instructions |
| 299 | // performing the kill if the exec mask is non-zero. |
| 300 | MI.eraseFromParent(); |
| 301 | } |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 302 | break; |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 303 | |
| 304 | case AMDGPU::SI_KILL_TERMINATOR: |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 305 | MadeChange = true; |
| 306 | kill(MI); |
| 307 | |
| 308 | if (ExecBranchStack.empty()) { |
| 309 | if (skipIfDead(MI, *NextBB)) { |
Matt Arsenault | bf67cf7 | 2017-01-24 22:18:39 +0000 | [diff] [blame] | 310 | HaveSkipBlock = true; |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 311 | NextBB = std::next(BI); |
| 312 | BE = MF.end(); |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 313 | } |
| 314 | } else { |
| 315 | HaveKill = true; |
| 316 | } |
| 317 | |
| 318 | MI.eraseFromParent(); |
| 319 | break; |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 320 | |
| 321 | case AMDGPU::SI_RETURN: |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 322 | // FIXME: Should move somewhere else |
| 323 | assert(!MF.getInfo<SIMachineFunctionInfo>()->returnsVoid()); |
| 324 | |
| 325 | // Graphics shaders returning non-void shouldn't contain S_ENDPGM, |
| 326 | // because external bytecode will be appended at the end. |
| 327 | if (BI != --MF.end() || I != MBB.getFirstTerminator()) { |
| 328 | // SI_RETURN is not the last instruction. Add an empty block at |
| 329 | // the end and jump there. |
| 330 | if (!EmptyMBBAtEnd) { |
| 331 | EmptyMBBAtEnd = MF.CreateMachineBasicBlock(); |
| 332 | MF.insert(MF.end(), EmptyMBBAtEnd); |
| 333 | } |
| 334 | |
| 335 | MBB.addSuccessor(EmptyMBBAtEnd); |
| 336 | BuildMI(*BI, I, MI.getDebugLoc(), TII->get(AMDGPU::S_BRANCH)) |
| 337 | .addMBB(EmptyMBBAtEnd); |
| 338 | I->eraseFromParent(); |
| 339 | } |
Eugene Zelenko | 6620376 | 2017-01-21 00:53:49 +0000 | [diff] [blame] | 340 | break; |
| 341 | |
Matt Arsenault | 78fc9da | 2016-08-22 19:33:16 +0000 | [diff] [blame] | 342 | default: |
| 343 | break; |
| 344 | } |
| 345 | } |
| 346 | } |
| 347 | |
| 348 | return MadeChange; |
| 349 | } |