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