1 //===-- SILowerControlFlow.cpp - Use predicates for control flow ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This pass lowers the pseudo control flow instructions to real
12 /// machine instructions.
14 /// All control flow is handled using predicated instructions and
15 /// a predicate stack. Each Scalar ALU controls the operations of 64 Vector
16 /// ALUs. The Scalar ALU can update the predicate for any of the Vector ALUs
17 /// by writting to the 64-bit EXEC register (each bit corresponds to a
18 /// single vector ALU). Typically, for predicates, a vector ALU will write
19 /// to its bit of the VCC register (like EXEC VCC is 64-bits, one for each
20 /// Vector ALU) and then the ScalarALU will AND the VCC register with the
21 /// EXEC to update the predicates.
24 /// %vcc = V_CMP_GT_F32 %vgpr1, %vgpr2
25 /// %sgpr0 = SI_IF %vcc
26 /// %vgpr0 = V_ADD_F32 %vgpr0, %vgpr0
27 /// %sgpr0 = SI_ELSE %sgpr0
28 /// %vgpr0 = V_SUB_F32 %vgpr0, %vgpr0
33 /// %sgpr0 = S_AND_SAVEEXEC_B64 %vcc // Save and update the exec mask
34 /// %sgpr0 = S_XOR_B64 %sgpr0, %exec // Clear live bits from saved exec mask
35 /// S_CBRANCH_EXECZ label0 // This instruction is an optional
36 /// // optimization which allows us to
37 /// // branch if all the bits of
39 /// %vgpr0 = V_ADD_F32 %vgpr0, %vgpr0 // Do the IF block of the branch
42 /// %sgpr0 = S_OR_SAVEEXEC_B64 %exec // Restore the exec mask for the Then block
43 /// %exec = S_XOR_B64 %sgpr0, %exec // Clear live bits from saved exec mask
44 /// S_BRANCH_EXECZ label1 // Use our branch optimization
45 /// // instruction again.
46 /// %vgpr0 = V_SUB_F32 %vgpr0, %vgpr // Do the THEN block
48 /// %exec = S_OR_B64 %exec, %sgpr0 // Re-enable saved exec mask bits
49 //===----------------------------------------------------------------------===//
52 #include "AMDGPUSubtarget.h"
53 #include "SIInstrInfo.h"
54 #include "llvm/ADT/SmallVector.h"
55 #include "llvm/ADT/StringRef.h"
56 #include "llvm/CodeGen/LiveIntervals.h"
57 #include "llvm/CodeGen/MachineBasicBlock.h"
58 #include "llvm/CodeGen/MachineFunction.h"
59 #include "llvm/CodeGen/MachineFunctionPass.h"
60 #include "llvm/CodeGen/MachineInstr.h"
61 #include "llvm/CodeGen/MachineInstrBuilder.h"
62 #include "llvm/CodeGen/MachineOperand.h"
63 #include "llvm/CodeGen/MachineRegisterInfo.h"
64 #include "llvm/CodeGen/Passes.h"
65 #include "llvm/CodeGen/SlotIndexes.h"
66 #include "llvm/CodeGen/TargetRegisterInfo.h"
67 #include "llvm/MC/MCRegisterInfo.h"
68 #include "llvm/Pass.h"
74 #define DEBUG_TYPE "si-lower-control-flow"
78 class SILowerControlFlow : public MachineFunctionPass {
80 const SIRegisterInfo *TRI = nullptr;
81 const SIInstrInfo *TII = nullptr;
82 LiveIntervals *LIS = nullptr;
83 MachineRegisterInfo *MRI = nullptr;
85 void emitIf(MachineInstr &MI);
86 void emitElse(MachineInstr &MI);
87 void emitBreak(MachineInstr &MI);
88 void emitIfBreak(MachineInstr &MI);
89 void emitElseBreak(MachineInstr &MI);
90 void emitLoop(MachineInstr &MI);
91 void emitEndCf(MachineInstr &MI);
93 void findMaskOperands(MachineInstr &MI, unsigned OpNo,
94 SmallVectorImpl<MachineOperand> &Src) const;
96 void combineMasks(MachineInstr &MI);
101 SILowerControlFlow() : MachineFunctionPass(ID) {}
103 bool runOnMachineFunction(MachineFunction &MF) override;
105 StringRef getPassName() const override {
106 return "SI Lower control flow pseudo instructions";
109 void getAnalysisUsage(AnalysisUsage &AU) const override {
110 // Should preserve the same set that TwoAddressInstructions does.
111 AU.addPreserved<SlotIndexes>();
112 AU.addPreserved<LiveIntervals>();
113 AU.addPreservedID(LiveVariablesID);
114 AU.addPreservedID(MachineLoopInfoID);
115 AU.addPreservedID(MachineDominatorsID);
116 AU.setPreservesCFG();
117 MachineFunctionPass::getAnalysisUsage(AU);
121 } // end anonymous namespace
123 char SILowerControlFlow::ID = 0;
125 INITIALIZE_PASS(SILowerControlFlow, DEBUG_TYPE,
126 "SI lower control flow", false, false)
128 static void setImpSCCDefDead(MachineInstr &MI, bool IsDead) {
129 MachineOperand &ImpDefSCC = MI.getOperand(3);
130 assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
132 ImpDefSCC.setIsDead(IsDead);
135 char &llvm::SILowerControlFlowID = SILowerControlFlow::ID;
137 static bool isSimpleIf(const MachineInstr &MI, const MachineRegisterInfo *MRI,
138 const SIInstrInfo *TII) {
139 unsigned SaveExecReg = MI.getOperand(0).getReg();
140 auto U = MRI->use_instr_nodbg_begin(SaveExecReg);
142 if (U == MRI->use_instr_nodbg_end() ||
143 std::next(U) != MRI->use_instr_nodbg_end() ||
144 U->getOpcode() != AMDGPU::SI_END_CF)
147 // Check for SI_KILL_*_TERMINATOR on path from if to endif.
148 // if there is any such terminator simplififcations are not safe.
149 auto SMBB = MI.getParent();
150 auto EMBB = U->getParent();
151 DenseSet<const MachineBasicBlock*> Visited;
152 SmallVector<MachineBasicBlock*, 4> Worklist(SMBB->succ_begin(),
155 while (!Worklist.empty()) {
156 MachineBasicBlock *MBB = Worklist.pop_back_val();
158 if (MBB == EMBB || !Visited.insert(MBB).second)
160 for(auto &Term : MBB->terminators())
161 if (TII->isKillTerminator(Term.getOpcode()))
164 Worklist.append(MBB->succ_begin(), MBB->succ_end());
170 void SILowerControlFlow::emitIf(MachineInstr &MI) {
171 MachineBasicBlock &MBB = *MI.getParent();
172 const DebugLoc &DL = MI.getDebugLoc();
173 MachineBasicBlock::iterator I(&MI);
175 MachineOperand &SaveExec = MI.getOperand(0);
176 MachineOperand &Cond = MI.getOperand(1);
177 assert(SaveExec.getSubReg() == AMDGPU::NoSubRegister &&
178 Cond.getSubReg() == AMDGPU::NoSubRegister);
180 unsigned SaveExecReg = SaveExec.getReg();
182 MachineOperand &ImpDefSCC = MI.getOperand(4);
183 assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
185 // If there is only one use of save exec register and that use is SI_END_CF,
186 // we can optimize SI_IF by returning the full saved exec mask instead of
187 // just cleared bits.
188 bool SimpleIf = isSimpleIf(MI, MRI, TII);
190 // Add an implicit def of exec to discourage scheduling VALU after this which
191 // will interfere with trying to form s_and_saveexec_b64 later.
192 unsigned CopyReg = SimpleIf ? SaveExecReg
193 : MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass);
194 MachineInstr *CopyExec =
195 BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), CopyReg)
196 .addReg(AMDGPU::EXEC)
197 .addReg(AMDGPU::EXEC, RegState::ImplicitDefine);
199 unsigned Tmp = MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass);
202 BuildMI(MBB, I, DL, TII->get(AMDGPU::S_AND_B64), Tmp)
204 //.addReg(AMDGPU::EXEC)
205 .addReg(Cond.getReg());
206 setImpSCCDefDead(*And, true);
208 MachineInstr *Xor = nullptr;
211 BuildMI(MBB, I, DL, TII->get(AMDGPU::S_XOR_B64), SaveExecReg)
214 setImpSCCDefDead(*Xor, ImpDefSCC.isDead());
217 // Use a copy that is a terminator to get correct spill code placement it with
219 MachineInstr *SetExec =
220 BuildMI(MBB, I, DL, TII->get(AMDGPU::S_MOV_B64_term), AMDGPU::EXEC)
221 .addReg(Tmp, RegState::Kill);
223 // Insert a pseudo terminator to help keep the verifier happy. This will also
224 // be used later when inserting skips.
225 MachineInstr *NewBr = BuildMI(MBB, I, DL, TII->get(AMDGPU::SI_MASK_BRANCH))
226 .add(MI.getOperand(2));
229 MI.eraseFromParent();
233 LIS->InsertMachineInstrInMaps(*CopyExec);
235 // Replace with and so we don't need to fix the live interval for condition
237 LIS->ReplaceMachineInstrInMaps(MI, *And);
240 LIS->InsertMachineInstrInMaps(*Xor);
241 LIS->InsertMachineInstrInMaps(*SetExec);
242 LIS->InsertMachineInstrInMaps(*NewBr);
244 LIS->removeRegUnit(*MCRegUnitIterator(AMDGPU::EXEC, TRI));
245 MI.eraseFromParent();
247 // FIXME: Is there a better way of adjusting the liveness? It shouldn't be
248 // hard to add another def here but I'm not sure how to correctly update the
250 LIS->removeInterval(SaveExecReg);
251 LIS->createAndComputeVirtRegInterval(SaveExecReg);
252 LIS->createAndComputeVirtRegInterval(Tmp);
254 LIS->createAndComputeVirtRegInterval(CopyReg);
257 void SILowerControlFlow::emitElse(MachineInstr &MI) {
258 MachineBasicBlock &MBB = *MI.getParent();
259 const DebugLoc &DL = MI.getDebugLoc();
261 unsigned DstReg = MI.getOperand(0).getReg();
262 assert(MI.getOperand(0).getSubReg() == AMDGPU::NoSubRegister);
264 bool ExecModified = MI.getOperand(3).getImm() != 0;
265 MachineBasicBlock::iterator Start = MBB.begin();
267 // We are running before TwoAddressInstructions, and si_else's operands are
268 // tied. In order to correctly tie the registers, split this into a copy of
269 // the src like it does.
270 unsigned CopyReg = MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass);
271 MachineInstr *CopyExec =
272 BuildMI(MBB, Start, DL, TII->get(AMDGPU::COPY), CopyReg)
273 .add(MI.getOperand(1)); // Saved EXEC
275 // This must be inserted before phis and any spill code inserted before the
277 unsigned SaveReg = ExecModified ?
278 MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass) : DstReg;
279 MachineInstr *OrSaveExec =
280 BuildMI(MBB, Start, DL, TII->get(AMDGPU::S_OR_SAVEEXEC_B64), SaveReg)
283 MachineBasicBlock *DestBB = MI.getOperand(2).getMBB();
285 MachineBasicBlock::iterator ElsePt(MI);
289 BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_AND_B64), DstReg)
290 .addReg(AMDGPU::EXEC)
294 LIS->InsertMachineInstrInMaps(*And);
298 BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_XOR_B64_term), AMDGPU::EXEC)
299 .addReg(AMDGPU::EXEC)
302 MachineInstr *Branch =
303 BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::SI_MASK_BRANCH))
307 MI.eraseFromParent();
311 LIS->RemoveMachineInstrFromMaps(MI);
312 MI.eraseFromParent();
314 LIS->InsertMachineInstrInMaps(*CopyExec);
315 LIS->InsertMachineInstrInMaps(*OrSaveExec);
317 LIS->InsertMachineInstrInMaps(*Xor);
318 LIS->InsertMachineInstrInMaps(*Branch);
320 // src reg is tied to dst reg.
321 LIS->removeInterval(DstReg);
322 LIS->createAndComputeVirtRegInterval(DstReg);
323 LIS->createAndComputeVirtRegInterval(CopyReg);
325 LIS->createAndComputeVirtRegInterval(SaveReg);
327 // Let this be recomputed.
328 LIS->removeRegUnit(*MCRegUnitIterator(AMDGPU::EXEC, TRI));
331 void SILowerControlFlow::emitBreak(MachineInstr &MI) {
332 MachineBasicBlock &MBB = *MI.getParent();
333 const DebugLoc &DL = MI.getDebugLoc();
334 unsigned Dst = MI.getOperand(0).getReg();
336 MachineInstr *Or = BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_OR_B64), Dst)
337 .addReg(AMDGPU::EXEC)
338 .add(MI.getOperand(1));
341 LIS->ReplaceMachineInstrInMaps(MI, *Or);
342 MI.eraseFromParent();
345 void SILowerControlFlow::emitIfBreak(MachineInstr &MI) {
346 MI.setDesc(TII->get(AMDGPU::S_OR_B64));
349 void SILowerControlFlow::emitElseBreak(MachineInstr &MI) {
350 MI.setDesc(TII->get(AMDGPU::S_OR_B64));
353 void SILowerControlFlow::emitLoop(MachineInstr &MI) {
354 MachineBasicBlock &MBB = *MI.getParent();
355 const DebugLoc &DL = MI.getDebugLoc();
357 MachineInstr *AndN2 =
358 BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_ANDN2_B64_term), AMDGPU::EXEC)
359 .addReg(AMDGPU::EXEC)
360 .add(MI.getOperand(0));
362 MachineInstr *Branch =
363 BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))
364 .add(MI.getOperand(1));
367 LIS->ReplaceMachineInstrInMaps(MI, *AndN2);
368 LIS->InsertMachineInstrInMaps(*Branch);
371 MI.eraseFromParent();
374 void SILowerControlFlow::emitEndCf(MachineInstr &MI) {
375 MachineBasicBlock &MBB = *MI.getParent();
376 const DebugLoc &DL = MI.getDebugLoc();
378 MachineBasicBlock::iterator InsPt = MBB.begin();
379 MachineInstr *NewMI =
380 BuildMI(MBB, InsPt, DL, TII->get(AMDGPU::S_OR_B64), AMDGPU::EXEC)
381 .addReg(AMDGPU::EXEC)
382 .add(MI.getOperand(0));
385 LIS->ReplaceMachineInstrInMaps(MI, *NewMI);
387 MI.eraseFromParent();
390 LIS->handleMove(*NewMI);
393 // Returns replace operands for a logical operation, either single result
394 // for exec or two operands if source was another equivalent operation.
395 void SILowerControlFlow::findMaskOperands(MachineInstr &MI, unsigned OpNo,
396 SmallVectorImpl<MachineOperand> &Src) const {
397 MachineOperand &Op = MI.getOperand(OpNo);
398 if (!Op.isReg() || !TargetRegisterInfo::isVirtualRegister(Op.getReg())) {
403 MachineInstr *Def = MRI->getUniqueVRegDef(Op.getReg());
404 if (!Def || Def->getParent() != MI.getParent() ||
405 !(Def->isFullCopy() || (Def->getOpcode() == MI.getOpcode())))
408 // Make sure we do not modify exec between def and use.
409 // A copy with implcitly defined exec inserted earlier is an exclusion, it
410 // does not really modify exec.
411 for (auto I = Def->getIterator(); I != MI.getIterator(); ++I)
412 if (I->modifiesRegister(AMDGPU::EXEC, TRI) &&
413 !(I->isCopy() && I->getOperand(0).getReg() != AMDGPU::EXEC))
416 for (const auto &SrcOp : Def->explicit_operands())
417 if (SrcOp.isUse() && (!SrcOp.isReg() ||
418 TargetRegisterInfo::isVirtualRegister(SrcOp.getReg()) ||
419 SrcOp.getReg() == AMDGPU::EXEC))
420 Src.push_back(SrcOp);
423 // Search and combine pairs of equivalent instructions, like
424 // S_AND_B64 x, (S_AND_B64 x, y) => S_AND_B64 x, y
425 // S_OR_B64 x, (S_OR_B64 x, y) => S_OR_B64 x, y
426 // One of the operands is exec mask.
427 void SILowerControlFlow::combineMasks(MachineInstr &MI) {
428 assert(MI.getNumExplicitOperands() == 3);
429 SmallVector<MachineOperand, 4> Ops;
430 unsigned OpToReplace = 1;
431 findMaskOperands(MI, 1, Ops);
432 if (Ops.size() == 1) OpToReplace = 2; // First operand can be exec or its copy
433 findMaskOperands(MI, 2, Ops);
434 if (Ops.size() != 3) return;
436 unsigned UniqueOpndIdx;
437 if (Ops[0].isIdenticalTo(Ops[1])) UniqueOpndIdx = 2;
438 else if (Ops[0].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;
439 else if (Ops[1].isIdenticalTo(Ops[2])) UniqueOpndIdx = 1;
442 unsigned Reg = MI.getOperand(OpToReplace).getReg();
443 MI.RemoveOperand(OpToReplace);
444 MI.addOperand(Ops[UniqueOpndIdx]);
445 if (MRI->use_empty(Reg))
446 MRI->getUniqueVRegDef(Reg)->eraseFromParent();
449 bool SILowerControlFlow::runOnMachineFunction(MachineFunction &MF) {
450 const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
451 TII = ST.getInstrInfo();
452 TRI = &TII->getRegisterInfo();
454 // This doesn't actually need LiveIntervals, but we can preserve them.
455 LIS = getAnalysisIfAvailable<LiveIntervals>();
456 MRI = &MF.getRegInfo();
458 MachineFunction::iterator NextBB;
459 for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
460 BI != BE; BI = NextBB) {
461 NextBB = std::next(BI);
462 MachineBasicBlock &MBB = *BI;
464 MachineBasicBlock::iterator I, Next, Last;
466 for (I = MBB.begin(), Last = MBB.end(); I != MBB.end(); I = Next) {
468 MachineInstr &MI = *I;
470 switch (MI.getOpcode()) {
475 case AMDGPU::SI_ELSE:
479 case AMDGPU::SI_BREAK:
483 case AMDGPU::SI_IF_BREAK:
487 case AMDGPU::SI_ELSE_BREAK:
491 case AMDGPU::SI_LOOP:
495 case AMDGPU::SI_END_CF:
499 case AMDGPU::S_AND_B64:
500 case AMDGPU::S_OR_B64:
501 // Cleanup bit manipulations on exec mask
511 // Replay newly inserted code to combine masks
512 Next = (Last == MBB.end()) ? MBB.begin() : Last;