885 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file10/// This pass lowers the pseudo control flow instructions to real11/// machine instructions.12///13/// All control flow is handled using predicated instructions and14/// a predicate stack. Each Scalar ALU controls the operations of 64 Vector15/// ALUs. The Scalar ALU can update the predicate for any of the Vector ALUs16/// by writing to the 64-bit EXEC register (each bit corresponds to a17/// single vector ALU). Typically, for predicates, a vector ALU will write18/// to its bit of the VCC register (like EXEC VCC is 64-bits, one for each19/// Vector ALU) and then the ScalarALU will AND the VCC register with the20/// EXEC to update the predicates.21///22/// For example:23/// %vcc = V_CMP_GT_F32 %vgpr1, %vgpr224/// %sgpr0 = SI_IF %vcc25/// %vgpr0 = V_ADD_F32 %vgpr0, %vgpr026/// %sgpr0 = SI_ELSE %sgpr027/// %vgpr0 = V_SUB_F32 %vgpr0, %vgpr028/// SI_END_CF %sgpr029///30/// becomes:31///32/// %sgpr0 = S_AND_SAVEEXEC_B64 %vcc // Save and update the exec mask33/// %sgpr0 = S_XOR_B64 %sgpr0, %exec // Clear live bits from saved exec mask34/// S_CBRANCH_EXECZ label0 // This instruction is an optional35/// // optimization which allows us to36/// // branch if all the bits of37/// // EXEC are zero.38/// %vgpr0 = V_ADD_F32 %vgpr0, %vgpr0 // Do the IF block of the branch39///40/// label0:41/// %sgpr0 = S_OR_SAVEEXEC_B64 %sgpr0 // Restore the exec mask for the Then42/// // block43/// %exec = S_XOR_B64 %sgpr0, %exec // Update the exec mask44/// S_CBRANCH_EXECZ label1 // Use our branch optimization45/// // instruction again.46/// %vgpr0 = V_SUB_F32 %vgpr0, %vgpr // Do the ELSE block47/// label1:48/// %exec = S_OR_B64 %exec, %sgpr0 // Re-enable saved exec mask bits49//===----------------------------------------------------------------------===//50 51#include "SILowerControlFlow.h"52#include "AMDGPU.h"53#include "AMDGPULaneMaskUtils.h"54#include "GCNSubtarget.h"55#include "MCTargetDesc/AMDGPUMCTargetDesc.h"56#include "llvm/ADT/SmallSet.h"57#include "llvm/CodeGen/LiveIntervals.h"58#include "llvm/CodeGen/LiveVariables.h"59#include "llvm/CodeGen/MachineDominators.h"60#include "llvm/CodeGen/MachineFunctionPass.h"61#include "llvm/CodeGen/MachinePostDominators.h"62#include "llvm/Target/TargetMachine.h"63 64using namespace llvm;65 66#define DEBUG_TYPE "si-lower-control-flow"67 68static cl::opt<bool>69RemoveRedundantEndcf("amdgpu-remove-redundant-endcf",70 cl::init(true), cl::ReallyHidden);71 72namespace {73 74class SILowerControlFlow {75private:76 const SIRegisterInfo *TRI = nullptr;77 const SIInstrInfo *TII = nullptr;78 LiveIntervals *LIS = nullptr;79 LiveVariables *LV = nullptr;80 MachineDominatorTree *MDT = nullptr;81 MachinePostDominatorTree *PDT = nullptr;82 MachineRegisterInfo *MRI = nullptr;83 SetVector<MachineInstr*> LoweredEndCf;84 DenseSet<Register> LoweredIf;85 SmallPtrSet<MachineBasicBlock *, 4> KillBlocks;86 SmallSet<Register, 8> RecomputeRegs;87 88 const TargetRegisterClass *BoolRC = nullptr;89 const AMDGPU::LaneMaskConstants &LMC;90 91 bool EnableOptimizeEndCf = false;92 93 bool hasKill(const MachineBasicBlock *Begin, const MachineBasicBlock *End);94 95 void emitIf(MachineInstr &MI);96 void emitElse(MachineInstr &MI);97 void emitIfBreak(MachineInstr &MI);98 void emitLoop(MachineInstr &MI);99 100 MachineBasicBlock *emitEndCf(MachineInstr &MI);101 102 void findMaskOperands(MachineInstr &MI, unsigned OpNo,103 SmallVectorImpl<MachineOperand> &Src) const;104 105 void combineMasks(MachineInstr &MI);106 107 bool removeMBBifRedundant(MachineBasicBlock &MBB);108 109 MachineBasicBlock *process(MachineInstr &MI);110 111 // Skip to the next instruction, ignoring debug instructions, and trivial112 // block boundaries (blocks that have one (typically fallthrough) successor,113 // and the successor has one predecessor.114 MachineBasicBlock::iterator115 skipIgnoreExecInstsTrivialSucc(MachineBasicBlock &MBB,116 MachineBasicBlock::iterator It) const;117 118 /// Find the insertion point for a new conditional branch.119 MachineBasicBlock::iterator120 skipToUncondBrOrEnd(MachineBasicBlock &MBB,121 MachineBasicBlock::iterator I) const {122 assert(I->isTerminator());123 124 // FIXME: What if we had multiple pre-existing conditional branches?125 MachineBasicBlock::iterator End = MBB.end();126 while (I != End && !I->isUnconditionalBranch())127 ++I;128 return I;129 }130 131 // Remove redundant SI_END_CF instructions.132 void optimizeEndCf();133 134public:135 SILowerControlFlow(const GCNSubtarget *ST, LiveIntervals *LIS,136 LiveVariables *LV, MachineDominatorTree *MDT,137 MachinePostDominatorTree *PDT)138 : LIS(LIS), LV(LV), MDT(MDT), PDT(PDT),139 LMC(AMDGPU::LaneMaskConstants::get(*ST)) {}140 bool run(MachineFunction &MF);141};142 143class SILowerControlFlowLegacy : public MachineFunctionPass {144public:145 static char ID;146 147 SILowerControlFlowLegacy() : MachineFunctionPass(ID) {}148 149 bool runOnMachineFunction(MachineFunction &MF) override;150 151 StringRef getPassName() const override {152 return "SI Lower control flow pseudo instructions";153 }154 155 void getAnalysisUsage(AnalysisUsage &AU) const override {156 AU.addUsedIfAvailable<LiveIntervalsWrapperPass>();157 // Should preserve the same set that TwoAddressInstructions does.158 AU.addPreserved<MachineDominatorTreeWrapperPass>();159 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();160 AU.addPreserved<SlotIndexesWrapperPass>();161 AU.addPreserved<LiveIntervalsWrapperPass>();162 AU.addPreserved<LiveVariablesWrapperPass>();163 MachineFunctionPass::getAnalysisUsage(AU);164 }165};166 167} // end anonymous namespace168 169char SILowerControlFlowLegacy::ID = 0;170 171INITIALIZE_PASS(SILowerControlFlowLegacy, DEBUG_TYPE, "SI lower control flow",172 false, false)173 174static void setImpSCCDefDead(MachineInstr &MI, bool IsDead) {175 MachineOperand &ImpDefSCC = MI.getOperand(3);176 assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());177 178 ImpDefSCC.setIsDead(IsDead);179}180 181char &llvm::SILowerControlFlowLegacyID = SILowerControlFlowLegacy::ID;182 183bool SILowerControlFlow::hasKill(const MachineBasicBlock *Begin,184 const MachineBasicBlock *End) {185 DenseSet<const MachineBasicBlock*> Visited;186 SmallVector<MachineBasicBlock *, 4> Worklist(Begin->successors());187 188 while (!Worklist.empty()) {189 MachineBasicBlock *MBB = Worklist.pop_back_val();190 191 if (MBB == End || !Visited.insert(MBB).second)192 continue;193 if (KillBlocks.contains(MBB))194 return true;195 196 Worklist.append(MBB->succ_begin(), MBB->succ_end());197 }198 199 return false;200}201 202static bool isSimpleIf(const MachineInstr &MI, const MachineRegisterInfo *MRI) {203 Register SaveExecReg = MI.getOperand(0).getReg();204 auto U = MRI->use_instr_nodbg_begin(SaveExecReg);205 206 if (U == MRI->use_instr_nodbg_end() ||207 std::next(U) != MRI->use_instr_nodbg_end() ||208 U->getOpcode() != AMDGPU::SI_END_CF)209 return false;210 211 return true;212}213 214void SILowerControlFlow::emitIf(MachineInstr &MI) {215 MachineBasicBlock &MBB = *MI.getParent();216 const DebugLoc &DL = MI.getDebugLoc();217 MachineBasicBlock::iterator I(&MI);218 Register SaveExecReg = MI.getOperand(0).getReg();219 MachineOperand& Cond = MI.getOperand(1);220 assert(Cond.getSubReg() == AMDGPU::NoSubRegister);221 222 MachineOperand &ImpDefSCC = MI.getOperand(4);223 assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());224 225 // If there is only one use of save exec register and that use is SI_END_CF,226 // we can optimize SI_IF by returning the full saved exec mask instead of227 // just cleared bits.228 bool SimpleIf = isSimpleIf(MI, MRI);229 230 if (SimpleIf) {231 // Check for SI_KILL_*_TERMINATOR on path from if to endif.232 // if there is any such terminator simplifications are not safe.233 auto UseMI = MRI->use_instr_nodbg_begin(SaveExecReg);234 SimpleIf = !hasKill(MI.getParent(), UseMI->getParent());235 }236 237 // Add an implicit def of exec to discourage scheduling VALU after this which238 // will interfere with trying to form s_and_saveexec_b64 later.239 Register CopyReg = SimpleIf ? SaveExecReg240 : MRI->createVirtualRegister(BoolRC);241 MachineInstr *CopyExec = BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), CopyReg)242 .addReg(LMC.ExecReg)243 .addReg(LMC.ExecReg, RegState::ImplicitDefine);244 LoweredIf.insert(CopyReg);245 246 Register Tmp = MRI->createVirtualRegister(BoolRC);247 248 MachineInstr *And =249 BuildMI(MBB, I, DL, TII->get(LMC.AndOpc), Tmp).addReg(CopyReg).add(Cond);250 if (LV)251 LV->replaceKillInstruction(Cond.getReg(), MI, *And);252 253 setImpSCCDefDead(*And, true);254 255 MachineInstr *Xor = nullptr;256 if (!SimpleIf) {257 Xor = BuildMI(MBB, I, DL, TII->get(LMC.XorOpc), SaveExecReg)258 .addReg(Tmp)259 .addReg(CopyReg);260 setImpSCCDefDead(*Xor, ImpDefSCC.isDead());261 }262 263 // Use a copy that is a terminator to get correct spill code placement it with264 // fast regalloc.265 MachineInstr *SetExec =266 BuildMI(MBB, I, DL, TII->get(LMC.MovTermOpc), LMC.ExecReg)267 .addReg(Tmp, RegState::Kill);268 if (LV)269 LV->getVarInfo(Tmp).Kills.push_back(SetExec);270 271 // Skip ahead to the unconditional branch in case there are other terminators272 // present.273 I = skipToUncondBrOrEnd(MBB, I);274 275 // Insert the S_CBRANCH_EXECZ instruction which will be optimized later276 // during SIPreEmitPeephole.277 MachineInstr *NewBr = BuildMI(MBB, I, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))278 .add(MI.getOperand(2));279 280 if (!LIS) {281 MI.eraseFromParent();282 return;283 }284 285 LIS->InsertMachineInstrInMaps(*CopyExec);286 287 // Replace with and so we don't need to fix the live interval for condition288 // register.289 LIS->ReplaceMachineInstrInMaps(MI, *And);290 291 if (!SimpleIf)292 LIS->InsertMachineInstrInMaps(*Xor);293 LIS->InsertMachineInstrInMaps(*SetExec);294 LIS->InsertMachineInstrInMaps(*NewBr);295 296 MI.eraseFromParent();297 298 // FIXME: Is there a better way of adjusting the liveness? It shouldn't be299 // hard to add another def here but I'm not sure how to correctly update the300 // valno.301 RecomputeRegs.insert(SaveExecReg);302 LIS->createAndComputeVirtRegInterval(Tmp);303 if (!SimpleIf)304 LIS->createAndComputeVirtRegInterval(CopyReg);305}306 307void SILowerControlFlow::emitElse(MachineInstr &MI) {308 MachineBasicBlock &MBB = *MI.getParent();309 const DebugLoc &DL = MI.getDebugLoc();310 311 Register DstReg = MI.getOperand(0).getReg();312 Register SrcReg = MI.getOperand(1).getReg();313 314 MachineBasicBlock::iterator Start = MBB.begin();315 316 // This must be inserted before phis and any spill code inserted before the317 // else.318 Register SaveReg = MRI->createVirtualRegister(BoolRC);319 MachineInstr *OrSaveExec =320 BuildMI(MBB, Start, DL, TII->get(LMC.OrSaveExecOpc), SaveReg)321 .add(MI.getOperand(1)); // Saved EXEC322 if (LV)323 LV->replaceKillInstruction(SrcReg, MI, *OrSaveExec);324 325 MachineBasicBlock *DestBB = MI.getOperand(2).getMBB();326 327 MachineBasicBlock::iterator ElsePt(MI);328 329 // This accounts for any modification of the EXEC mask within the block and330 // can be optimized out pre-RA when not required.331 MachineInstr *And = BuildMI(MBB, ElsePt, DL, TII->get(LMC.AndOpc), DstReg)332 .addReg(LMC.ExecReg)333 .addReg(SaveReg);334 335 MachineInstr *Xor =336 BuildMI(MBB, ElsePt, DL, TII->get(LMC.XorTermOpc), LMC.ExecReg)337 .addReg(LMC.ExecReg)338 .addReg(DstReg);339 340 // Skip ahead to the unconditional branch in case there are other terminators341 // present.342 ElsePt = skipToUncondBrOrEnd(MBB, ElsePt);343 344 MachineInstr *Branch =345 BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))346 .addMBB(DestBB);347 348 if (!LIS) {349 MI.eraseFromParent();350 return;351 }352 353 LIS->RemoveMachineInstrFromMaps(MI);354 MI.eraseFromParent();355 356 LIS->InsertMachineInstrInMaps(*OrSaveExec);357 LIS->InsertMachineInstrInMaps(*And);358 359 LIS->InsertMachineInstrInMaps(*Xor);360 LIS->InsertMachineInstrInMaps(*Branch);361 362 RecomputeRegs.insert(SrcReg);363 RecomputeRegs.insert(DstReg);364 LIS->createAndComputeVirtRegInterval(SaveReg);365}366 367void SILowerControlFlow::emitIfBreak(MachineInstr &MI) {368 MachineBasicBlock &MBB = *MI.getParent();369 const DebugLoc &DL = MI.getDebugLoc();370 auto Dst = MI.getOperand(0).getReg();371 372 // Skip ANDing with exec if the break condition is already masked by exec373 // because it is a V_CMP in the same basic block. (We know the break374 // condition operand was an i1 in IR, so if it is a VALU instruction it must375 // be one with a carry-out.)376 bool SkipAnding = false;377 if (MI.getOperand(1).isReg()) {378 if (MachineInstr *Def = MRI->getUniqueVRegDef(MI.getOperand(1).getReg())) {379 SkipAnding = Def->getParent() == MI.getParent()380 && SIInstrInfo::isVALU(*Def);381 }382 }383 384 // AND the break condition operand with exec, then OR that into the "loop385 // exit" mask.386 MachineInstr *And = nullptr, *Or = nullptr;387 Register AndReg;388 if (!SkipAnding) {389 AndReg = MRI->createVirtualRegister(BoolRC);390 And = BuildMI(MBB, &MI, DL, TII->get(LMC.AndOpc), AndReg)391 .addReg(LMC.ExecReg)392 .add(MI.getOperand(1));393 if (LV)394 LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *And);395 Or = BuildMI(MBB, &MI, DL, TII->get(LMC.OrOpc), Dst)396 .addReg(AndReg)397 .add(MI.getOperand(2));398 } else {399 Or = BuildMI(MBB, &MI, DL, TII->get(LMC.OrOpc), Dst)400 .add(MI.getOperand(1))401 .add(MI.getOperand(2));402 if (LV)403 LV->replaceKillInstruction(MI.getOperand(1).getReg(), MI, *Or);404 }405 if (LV)406 LV->replaceKillInstruction(MI.getOperand(2).getReg(), MI, *Or);407 408 if (LIS) {409 LIS->ReplaceMachineInstrInMaps(MI, *Or);410 if (And) {411 // Read of original operand 1 is on And now not Or.412 RecomputeRegs.insert(And->getOperand(2).getReg());413 LIS->InsertMachineInstrInMaps(*And);414 LIS->createAndComputeVirtRegInterval(AndReg);415 }416 }417 418 MI.eraseFromParent();419}420 421void 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(LMC.AndN2TermOpc), LMC.ExecReg)427 .addReg(LMC.ExecReg)428 .add(MI.getOperand(0));429 if (LV)430 LV->replaceKillInstruction(MI.getOperand(0).getReg(), MI, *AndN2);431 432 auto BranchPt = skipToUncondBrOrEnd(MBB, MI.getIterator());433 MachineInstr *Branch =434 BuildMI(MBB, BranchPt, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))435 .add(MI.getOperand(1));436 437 if (LIS) {438 RecomputeRegs.insert(MI.getOperand(0).getReg());439 LIS->ReplaceMachineInstrInMaps(MI, *AndN2);440 LIS->InsertMachineInstrInMaps(*Branch);441 }442 443 MI.eraseFromParent();444}445 446MachineBasicBlock::iterator447SILowerControlFlow::skipIgnoreExecInstsTrivialSucc(448 MachineBasicBlock &MBB, MachineBasicBlock::iterator It) const {449 450 SmallPtrSet<const MachineBasicBlock *, 4> Visited;451 MachineBasicBlock *B = &MBB;452 do {453 if (!Visited.insert(B).second)454 return MBB.end();455 456 auto E = B->end();457 for ( ; It != E; ++It) {458 if (TII->mayReadEXEC(*MRI, *It))459 break;460 }461 462 if (It != E)463 return It;464 465 if (B->succ_size() != 1)466 return MBB.end();467 468 // If there is one trivial successor, advance to the next block.469 MachineBasicBlock *Succ = *B->succ_begin();470 471 It = Succ->begin();472 B = Succ;473 } while (true);474}475 476MachineBasicBlock *SILowerControlFlow::emitEndCf(MachineInstr &MI) {477 MachineBasicBlock &MBB = *MI.getParent();478 const DebugLoc &DL = MI.getDebugLoc();479 480 MachineBasicBlock::iterator InsPt = MBB.begin();481 482 // If we have instructions that aren't prolog instructions, split the block483 // and emit a terminator instruction. This ensures correct spill placement.484 // FIXME: We should unconditionally split the block here.485 bool NeedBlockSplit = false;486 Register DataReg = MI.getOperand(0).getReg();487 for (MachineBasicBlock::iterator I = InsPt, E = MI.getIterator();488 I != E; ++I) {489 if (I->modifiesRegister(DataReg, TRI)) {490 NeedBlockSplit = true;491 break;492 }493 }494 495 unsigned Opcode = LMC.OrOpc;496 MachineBasicBlock *SplitBB = &MBB;497 if (NeedBlockSplit) {498 SplitBB = MBB.splitAt(MI, /*UpdateLiveIns*/true, LIS);499 if (SplitBB != &MBB && (MDT || PDT)) {500 using DomTreeT = DomTreeBase<MachineBasicBlock>;501 SmallVector<DomTreeT::UpdateType, 16> DTUpdates;502 for (MachineBasicBlock *Succ : SplitBB->successors()) {503 DTUpdates.push_back({DomTreeT::Insert, SplitBB, Succ});504 DTUpdates.push_back({DomTreeT::Delete, &MBB, Succ});505 }506 DTUpdates.push_back({DomTreeT::Insert, &MBB, SplitBB});507 if (MDT)508 MDT->applyUpdates(DTUpdates);509 if (PDT)510 PDT->applyUpdates(DTUpdates);511 }512 Opcode = LMC.OrTermOpc;513 InsPt = MI;514 }515 516 MachineInstr *NewMI = BuildMI(MBB, InsPt, DL, TII->get(Opcode), LMC.ExecReg)517 .addReg(LMC.ExecReg)518 .add(MI.getOperand(0));519 if (LV) {520 LV->replaceKillInstruction(DataReg, MI, *NewMI);521 522 if (SplitBB != &MBB) {523 // Track the set of registers defined in the original block so we don't524 // accidentally add the original block to AliveBlocks. AliveBlocks only525 // includes blocks which are live through, which excludes live outs and526 // local defs.527 DenseSet<Register> DefInOrigBlock;528 529 for (MachineBasicBlock *BlockPiece : {&MBB, SplitBB}) {530 for (MachineInstr &X : *BlockPiece) {531 for (MachineOperand &Op : X.all_defs()) {532 if (Op.getReg().isVirtual())533 DefInOrigBlock.insert(Op.getReg());534 }535 }536 }537 538 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {539 Register Reg = Register::index2VirtReg(i);540 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg);541 542 if (VI.AliveBlocks.test(MBB.getNumber()))543 VI.AliveBlocks.set(SplitBB->getNumber());544 else {545 for (MachineInstr *Kill : VI.Kills) {546 if (Kill->getParent() == SplitBB && !DefInOrigBlock.contains(Reg))547 VI.AliveBlocks.set(MBB.getNumber());548 }549 }550 }551 }552 }553 554 LoweredEndCf.insert(NewMI);555 556 if (LIS)557 LIS->ReplaceMachineInstrInMaps(MI, *NewMI);558 559 MI.eraseFromParent();560 561 if (LIS)562 LIS->handleMove(*NewMI);563 return SplitBB;564}565 566// Returns replace operands for a logical operation, either single result567// for exec or two operands if source was another equivalent operation.568void SILowerControlFlow::findMaskOperands(MachineInstr &MI, unsigned OpNo,569 SmallVectorImpl<MachineOperand> &Src) const {570 MachineOperand &Op = MI.getOperand(OpNo);571 if (!Op.isReg() || !Op.getReg().isVirtual()) {572 Src.push_back(Op);573 return;574 }575 576 MachineInstr *Def = MRI->getUniqueVRegDef(Op.getReg());577 if (!Def || Def->getParent() != MI.getParent() ||578 !(Def->isFullCopy() || (Def->getOpcode() == MI.getOpcode())))579 return;580 581 // Make sure we do not modify exec between def and use.582 // A copy with implicitly defined exec inserted earlier is an exclusion, it583 // does not really modify exec.584 for (auto I = Def->getIterator(); I != MI.getIterator(); ++I)585 if (I->modifiesRegister(AMDGPU::EXEC, TRI) &&586 !(I->isCopy() && I->getOperand(0).getReg() != LMC.ExecReg))587 return;588 589 for (const auto &SrcOp : Def->explicit_operands())590 if (SrcOp.isReg() && SrcOp.isUse() &&591 (SrcOp.getReg().isVirtual() || SrcOp.getReg() == LMC.ExecReg))592 Src.push_back(SrcOp);593}594 595// Search and combine pairs of equivalent instructions, like596// S_AND_B64 x, (S_AND_B64 x, y) => S_AND_B64 x, y597// S_OR_B64 x, (S_OR_B64 x, y) => S_OR_B64 x, y598// One of the operands is exec mask.599void SILowerControlFlow::combineMasks(MachineInstr &MI) {600 assert(MI.getNumExplicitOperands() == 3);601 SmallVector<MachineOperand, 4> Ops;602 unsigned OpToReplace = 1;603 findMaskOperands(MI, 1, Ops);604 if (Ops.size() == 1) OpToReplace = 2; // First operand can be exec or its copy605 findMaskOperands(MI, 2, Ops);606 if (Ops.size() != 3) return;607 608 unsigned UniqueOpndIdx;609 if (Ops[0].isIdenticalTo(Ops[1])) UniqueOpndIdx = 2;610 else if (Ops[0].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;611 else if (Ops[1].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;612 else return;613 614 Register Reg = MI.getOperand(OpToReplace).getReg();615 MI.removeOperand(OpToReplace);616 MI.addOperand(Ops[UniqueOpndIdx]);617 if (MRI->use_empty(Reg))618 MRI->getUniqueVRegDef(Reg)->eraseFromParent();619}620 621void SILowerControlFlow::optimizeEndCf() {622 // If the only instruction immediately following this END_CF is another623 // END_CF in the only successor we can avoid emitting exec mask restore here.624 if (!EnableOptimizeEndCf)625 return;626 627 for (MachineInstr *MI : reverse(LoweredEndCf)) {628 MachineBasicBlock &MBB = *MI->getParent();629 auto Next =630 skipIgnoreExecInstsTrivialSucc(MBB, std::next(MI->getIterator()));631 if (Next == MBB.end() || !LoweredEndCf.count(&*Next))632 continue;633 // Only skip inner END_CF if outer ENDCF belongs to SI_IF.634 // If that belongs to SI_ELSE then saved mask has an inverted value.635 Register SavedExec636 = TII->getNamedOperand(*Next, AMDGPU::OpName::src1)->getReg();637 assert(SavedExec.isVirtual() && "Expected saved exec to be src1!");638 639 const MachineInstr *Def = MRI->getUniqueVRegDef(SavedExec);640 if (Def && LoweredIf.count(SavedExec)) {641 LLVM_DEBUG(dbgs() << "Skip redundant "; MI->dump());642 if (LIS)643 LIS->RemoveMachineInstrFromMaps(*MI);644 Register Reg;645 if (LV)646 Reg = TII->getNamedOperand(*MI, AMDGPU::OpName::src1)->getReg();647 MI->eraseFromParent();648 if (LV)649 LV->recomputeForSingleDefVirtReg(Reg);650 removeMBBifRedundant(MBB);651 }652 }653}654 655MachineBasicBlock *SILowerControlFlow::process(MachineInstr &MI) {656 MachineBasicBlock &MBB = *MI.getParent();657 MachineBasicBlock::iterator I(MI);658 MachineInstr *Prev = (I != MBB.begin()) ? &*(std::prev(I)) : nullptr;659 660 MachineBasicBlock *SplitBB = &MBB;661 662 switch (MI.getOpcode()) {663 case AMDGPU::SI_IF:664 emitIf(MI);665 break;666 667 case AMDGPU::SI_ELSE:668 emitElse(MI);669 break;670 671 case AMDGPU::SI_IF_BREAK:672 emitIfBreak(MI);673 break;674 675 case AMDGPU::SI_LOOP:676 emitLoop(MI);677 break;678 679 case AMDGPU::SI_WATERFALL_LOOP:680 MI.setDesc(TII->get(AMDGPU::S_CBRANCH_EXECNZ));681 break;682 683 case AMDGPU::SI_END_CF:684 SplitBB = emitEndCf(MI);685 break;686 687 default:688 assert(false && "Attempt to process unsupported instruction");689 break;690 }691 692 MachineBasicBlock::iterator Next;693 for (I = Prev ? Prev->getIterator() : MBB.begin(); I != MBB.end(); I = Next) {694 Next = std::next(I);695 MachineInstr &MaskMI = *I;696 switch (MaskMI.getOpcode()) {697 case AMDGPU::S_AND_B64:698 case AMDGPU::S_OR_B64:699 case AMDGPU::S_AND_B32:700 case AMDGPU::S_OR_B32:701 // Cleanup bit manipulations on exec mask702 combineMasks(MaskMI);703 break;704 default:705 I = MBB.end();706 break;707 }708 }709 710 return SplitBB;711}712 713bool SILowerControlFlow::removeMBBifRedundant(MachineBasicBlock &MBB) {714 for (auto &I : MBB.instrs()) {715 if (!I.isDebugInstr() && !I.isUnconditionalBranch())716 return false;717 }718 719 assert(MBB.succ_size() == 1 && "MBB has more than one successor");720 721 MachineBasicBlock *Succ = *MBB.succ_begin();722 MachineBasicBlock *FallThrough = nullptr;723 724 using DomTreeT = DomTreeBase<MachineBasicBlock>;725 SmallVector<DomTreeT::UpdateType, 8> DTUpdates;726 727 while (!MBB.predecessors().empty()) {728 MachineBasicBlock *P = *MBB.pred_begin();729 if (P->getFallThrough(false) == &MBB)730 FallThrough = P;731 P->ReplaceUsesOfBlockWith(&MBB, Succ);732 DTUpdates.push_back({DomTreeT::Insert, P, Succ});733 DTUpdates.push_back({DomTreeT::Delete, P, &MBB});734 }735 MBB.removeSuccessor(Succ);736 if (LIS) {737 for (auto &I : MBB.instrs())738 LIS->RemoveMachineInstrFromMaps(I);739 }740 if (MDT)741 MDT->applyUpdates(DTUpdates);742 if (PDT)743 PDT->applyUpdates(DTUpdates);744 745 MBB.clear();746 MBB.eraseFromParent();747 if (FallThrough && !FallThrough->isLayoutSuccessor(Succ)) {748 // Note: we cannot update block layout and preserve live intervals;749 // hence we must insert a branch.750 MachineInstr *BranchMI = BuildMI(*FallThrough, FallThrough->end(),751 FallThrough->findBranchDebugLoc(), TII->get(AMDGPU::S_BRANCH))752 .addMBB(Succ);753 if (LIS)754 LIS->InsertMachineInstrInMaps(*BranchMI);755 }756 757 return true;758}759 760bool SILowerControlFlow::run(MachineFunction &MF) {761 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();762 TII = ST.getInstrInfo();763 TRI = &TII->getRegisterInfo();764 EnableOptimizeEndCf = RemoveRedundantEndcf &&765 MF.getTarget().getOptLevel() > CodeGenOptLevel::None;766 767 MRI = &MF.getRegInfo();768 BoolRC = TRI->getBoolRC();769 770 // Compute set of blocks with kills771 const bool CanDemote =772 MF.getFunction().getCallingConv() == CallingConv::AMDGPU_PS;773 for (auto &MBB : MF) {774 bool IsKillBlock = false;775 for (auto &Term : MBB.terminators()) {776 if (TII->isKillTerminator(Term.getOpcode())) {777 KillBlocks.insert(&MBB);778 IsKillBlock = true;779 break;780 }781 }782 if (CanDemote && !IsKillBlock) {783 for (auto &MI : MBB) {784 if (MI.getOpcode() == AMDGPU::SI_DEMOTE_I1) {785 KillBlocks.insert(&MBB);786 break;787 }788 }789 }790 }791 792 bool Changed = false;793 MachineFunction::iterator NextBB;794 for (MachineFunction::iterator BI = MF.begin();795 BI != MF.end(); BI = NextBB) {796 NextBB = std::next(BI);797 MachineBasicBlock *MBB = &*BI;798 799 MachineBasicBlock::iterator I, E, Next;800 E = MBB->end();801 for (I = MBB->begin(); I != E; I = Next) {802 Next = std::next(I);803 MachineInstr &MI = *I;804 MachineBasicBlock *SplitMBB = MBB;805 806 switch (MI.getOpcode()) {807 case AMDGPU::SI_IF:808 case AMDGPU::SI_ELSE:809 case AMDGPU::SI_IF_BREAK:810 case AMDGPU::SI_WATERFALL_LOOP:811 case AMDGPU::SI_LOOP:812 case AMDGPU::SI_END_CF:813 SplitMBB = process(MI);814 Changed = true;815 break;816 }817 818 if (SplitMBB != MBB) {819 MBB = Next->getParent();820 E = MBB->end();821 }822 }823 }824 825 optimizeEndCf();826 827 if (LIS && Changed) {828 // These will need to be recomputed for insertions and removals.829 LIS->removeAllRegUnitsForPhysReg(AMDGPU::EXEC);830 LIS->removeAllRegUnitsForPhysReg(AMDGPU::SCC);831 for (Register Reg : RecomputeRegs) {832 LIS->removeInterval(Reg);833 LIS->createAndComputeVirtRegInterval(Reg);834 }835 }836 837 RecomputeRegs.clear();838 LoweredEndCf.clear();839 LoweredIf.clear();840 KillBlocks.clear();841 842 return Changed;843}844 845bool SILowerControlFlowLegacy::runOnMachineFunction(MachineFunction &MF) {846 const GCNSubtarget *ST = &MF.getSubtarget<GCNSubtarget>();847 // This doesn't actually need LiveIntervals, but we can preserve them.848 auto *LISWrapper = getAnalysisIfAvailable<LiveIntervalsWrapperPass>();849 LiveIntervals *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;850 // This doesn't actually need LiveVariables, but we can preserve them.851 auto *LVWrapper = getAnalysisIfAvailable<LiveVariablesWrapperPass>();852 LiveVariables *LV = LVWrapper ? &LVWrapper->getLV() : nullptr;853 auto *MDTWrapper = getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();854 MachineDominatorTree *MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;855 auto *PDTWrapper =856 getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>();857 MachinePostDominatorTree *PDT =858 PDTWrapper ? &PDTWrapper->getPostDomTree() : nullptr;859 return SILowerControlFlow(ST, LIS, LV, MDT, PDT).run(MF);860}861 862PreservedAnalyses863SILowerControlFlowPass::run(MachineFunction &MF,864 MachineFunctionAnalysisManager &MFAM) {865 const GCNSubtarget *ST = &MF.getSubtarget<GCNSubtarget>();866 LiveIntervals *LIS = MFAM.getCachedResult<LiveIntervalsAnalysis>(MF);867 LiveVariables *LV = MFAM.getCachedResult<LiveVariablesAnalysis>(MF);868 MachineDominatorTree *MDT =869 MFAM.getCachedResult<MachineDominatorTreeAnalysis>(MF);870 MachinePostDominatorTree *PDT =871 MFAM.getCachedResult<MachinePostDominatorTreeAnalysis>(MF);872 873 bool Changed = SILowerControlFlow(ST, LIS, LV, MDT, PDT).run(MF);874 if (!Changed)875 return PreservedAnalyses::all();876 877 auto PA = getMachineFunctionPassPreservedAnalyses();878 PA.preserve<MachineDominatorTreeAnalysis>();879 PA.preserve<MachinePostDominatorTreeAnalysis>();880 PA.preserve<SlotIndexesAnalysis>();881 PA.preserve<LiveIntervalsAnalysis>();882 PA.preserve<LiveVariablesAnalysis>();883 return PA;884}885