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 writing 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
42/// // block
43/// %exec = S_XOR_B64 %sgpr0, %exec // Update the exec mask
44/// S_CBRANCH_EXECZ label1 // Use our branch optimization
45/// // instruction again.
46/// %vgpr0 = V_SUB_F32 %vgpr0, %vgpr // Do the ELSE block
47/// label1:
48/// %exec = S_OR_B64 %exec, %sgpr0 // Re-enable saved exec mask bits
49//===----------------------------------------------------------------------===//
50
51#include "SILowerControlFlow.h"
52#include "AMDGPU.h"
53#include "AMDGPULaneMaskUtils.h"
54#include "GCNSubtarget.h"
55#include "llvm/CodeGen/LiveIntervals.h"
56#include "llvm/CodeGen/LiveVariables.h"
57#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
58#include "llvm/CodeGen/MachineDominators.h"
59#include "llvm/CodeGen/MachineFunctionPass.h"
60#include "llvm/CodeGen/MachinePostDominators.h"
61#include "llvm/CodeGen/RegisterClassInfo.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(Val: 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 trivial
112 // block boundaries (blocks that have one (typically fallthrough) successor,
113 // and the successor has one predecessor.
114 MachineBasicBlock::iterator
115 skipIgnoreExecInstsTrivialSucc(MachineBasicBlock &MBB,
116 MachineBasicBlock::iterator It) const;
117
118 /// Find the insertion point for a new conditional branch.
119 MachineBasicBlock::iterator
120 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: *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 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
164 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
165 MachineFunctionPass::getAnalysisUsage(AU);
166 }
167};
168
169} // end anonymous namespace
170
171char SILowerControlFlowLegacy::ID = 0;
172
173INITIALIZE_PASS(SILowerControlFlowLegacy, DEBUG_TYPE, "SI lower control flow",
174 false, false)
175
176static void setImpSCCDefDead(MachineInstr &MI, bool IsDead) {
177 MachineOperand &ImpDefSCC = MI.getOperand(i: 3);
178 assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
179
180 ImpDefSCC.setIsDead(IsDead);
181}
182
183char &llvm::SILowerControlFlowLegacyID = SILowerControlFlowLegacy::ID;
184
185bool SILowerControlFlow::hasKill(const MachineBasicBlock *Begin,
186 const MachineBasicBlock *End) {
187 DenseSet<const MachineBasicBlock*> Visited;
188 SmallVector<MachineBasicBlock *, 4> Worklist(Begin->successors());
189
190 while (!Worklist.empty()) {
191 MachineBasicBlock *MBB = Worklist.pop_back_val();
192
193 if (MBB == End || !Visited.insert(V: MBB).second)
194 continue;
195 if (KillBlocks.contains(Ptr: MBB))
196 return true;
197
198 Worklist.append(in_start: MBB->succ_begin(), in_end: MBB->succ_end());
199 }
200
201 return false;
202}
203
204static bool isSimpleIf(const MachineInstr &MI, const MachineRegisterInfo *MRI) {
205 Register SaveExecReg = MI.getOperand(i: 0).getReg();
206 auto U = MRI->use_instr_nodbg_begin(RegNo: SaveExecReg);
207
208 if (U == MRI->use_instr_nodbg_end() ||
209 std::next(x: U) != MRI->use_instr_nodbg_end() ||
210 U->getOpcode() != AMDGPU::SI_END_CF)
211 return false;
212
213 return true;
214}
215
216void SILowerControlFlow::emitIf(MachineInstr &MI) {
217 MachineBasicBlock &MBB = *MI.getParent();
218 const DebugLoc &DL = MI.getDebugLoc();
219 MachineBasicBlock::iterator I(&MI);
220 Register SaveExecReg = MI.getOperand(i: 0).getReg();
221 MachineOperand& Cond = MI.getOperand(i: 1);
222 assert(Cond.getSubReg() == AMDGPU::NoSubRegister);
223
224 MachineOperand &ImpDefSCC = MI.getOperand(i: 4);
225 assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
226
227 // If there is only one use of save exec register and that use is SI_END_CF,
228 // we can optimize SI_IF by returning the full saved exec mask instead of
229 // just cleared bits.
230 bool SimpleIf = isSimpleIf(MI, MRI);
231
232 if (SimpleIf) {
233 // Check for SI_KILL_*_TERMINATOR on path from if to endif.
234 // if there is any such terminator simplifications are not safe.
235 auto UseMI = MRI->use_instr_nodbg_begin(RegNo: SaveExecReg);
236 SimpleIf = !hasKill(Begin: MI.getParent(), End: UseMI->getParent());
237 }
238
239 // Add an implicit def of exec to discourage scheduling VALU after this which
240 // will interfere with trying to form s_and_saveexec_b64 later.
241 Register CopyReg = SimpleIf ? SaveExecReg
242 : MRI->createVirtualRegister(RegClass: BoolRC);
243 MachineInstr *CopyExec = BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: CopyReg)
244 .addReg(RegNo: LMC.ExecReg)
245 .addReg(RegNo: LMC.ExecReg, Flags: RegState::ImplicitDefine);
246 LoweredIf.insert(V: CopyReg);
247
248 Register Tmp = MRI->createVirtualRegister(RegClass: BoolRC);
249
250 MachineInstr *And =
251 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC.AndOpc), DestReg: Tmp).addReg(RegNo: CopyReg).add(MO: Cond);
252 if (LV)
253 LV->replaceKillInstruction(Reg: Cond.getReg(), OldMI&: MI, NewMI&: *And);
254
255 setImpSCCDefDead(MI&: *And, IsDead: true);
256
257 MachineInstr *Xor = nullptr;
258 if (!SimpleIf) {
259 Xor = BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC.XorOpc), DestReg: SaveExecReg)
260 .addReg(RegNo: Tmp)
261 .addReg(RegNo: CopyReg);
262 setImpSCCDefDead(MI&: *Xor, IsDead: ImpDefSCC.isDead());
263 }
264
265 // Use a copy that is a terminator to get correct spill code placement it with
266 // fast regalloc.
267 MachineInstr *SetExec =
268 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC.MovTermOpc), DestReg: LMC.ExecReg)
269 .addReg(RegNo: Tmp, Flags: RegState::Kill);
270 if (LV)
271 LV->getVarInfo(Reg: Tmp).Kills.push_back(x: SetExec);
272
273 // Skip ahead to the unconditional branch in case there are other terminators
274 // present.
275 I = skipToUncondBrOrEnd(MBB, I);
276
277 // Insert the S_CBRANCH_EXECZ instruction which will be optimized later
278 // during SIPreEmitPeephole.
279 MachineInstr *NewBr = BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::S_CBRANCH_EXECZ))
280 .add(MO: MI.getOperand(i: 2));
281
282 if (!LIS) {
283 MI.eraseFromParent();
284 return;
285 }
286
287 LIS->InsertMachineInstrInMaps(MI&: *CopyExec);
288
289 // Replace with and so we don't need to fix the live interval for condition
290 // register.
291 LIS->ReplaceMachineInstrInMaps(MI, NewMI&: *And);
292
293 if (!SimpleIf)
294 LIS->InsertMachineInstrInMaps(MI&: *Xor);
295 LIS->InsertMachineInstrInMaps(MI&: *SetExec);
296 LIS->InsertMachineInstrInMaps(MI&: *NewBr);
297
298 MI.eraseFromParent();
299
300 // FIXME: Is there a better way of adjusting the liveness? It shouldn't be
301 // hard to add another def here but I'm not sure how to correctly update the
302 // valno.
303 RecomputeRegs.insert(V: SaveExecReg);
304 LIS->createAndComputeVirtRegInterval(Reg: Tmp);
305 if (!SimpleIf)
306 LIS->createAndComputeVirtRegInterval(Reg: CopyReg);
307}
308
309void SILowerControlFlow::emitElse(MachineInstr &MI) {
310 MachineBasicBlock &MBB = *MI.getParent();
311 const DebugLoc &DL = MI.getDebugLoc();
312
313 Register DstReg = MI.getOperand(i: 0).getReg();
314 Register SrcReg = MI.getOperand(i: 1).getReg();
315
316 MachineBasicBlock::iterator Start = MBB.begin();
317
318 // This must be inserted before phis and any spill code inserted before the
319 // else.
320 Register SaveReg = MRI->createVirtualRegister(RegClass: BoolRC);
321 MachineInstr *OrSaveExec =
322 BuildMI(BB&: MBB, I: Start, MIMD: DL, MCID: TII->get(Opcode: LMC.OrSaveExecOpc), DestReg: SaveReg)
323 .add(MO: MI.getOperand(i: 1)); // Saved EXEC
324 if (LV)
325 LV->replaceKillInstruction(Reg: SrcReg, OldMI&: MI, NewMI&: *OrSaveExec);
326
327 MachineBasicBlock *DestBB = MI.getOperand(i: 2).getMBB();
328
329 MachineBasicBlock::iterator ElsePt(MI);
330
331 // This accounts for any modification of the EXEC mask within the block and
332 // can be optimized out pre-RA when not required.
333 MachineInstr *And = BuildMI(BB&: MBB, I: ElsePt, MIMD: DL, MCID: TII->get(Opcode: LMC.AndOpc), DestReg: DstReg)
334 .addReg(RegNo: LMC.ExecReg)
335 .addReg(RegNo: SaveReg);
336
337 MachineInstr *Xor =
338 BuildMI(BB&: MBB, I: ElsePt, MIMD: DL, MCID: TII->get(Opcode: LMC.XorTermOpc), DestReg: LMC.ExecReg)
339 .addReg(RegNo: LMC.ExecReg)
340 .addReg(RegNo: DstReg);
341
342 // Skip ahead to the unconditional branch in case there are other terminators
343 // present.
344 ElsePt = skipToUncondBrOrEnd(MBB, I: ElsePt);
345
346 MachineInstr *Branch =
347 BuildMI(BB&: MBB, I: ElsePt, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::S_CBRANCH_EXECZ))
348 .addMBB(MBB: DestBB);
349
350 if (!LIS) {
351 MI.eraseFromParent();
352 return;
353 }
354
355 LIS->RemoveMachineInstrFromMaps(MI);
356 MI.eraseFromParent();
357
358 LIS->InsertMachineInstrInMaps(MI&: *OrSaveExec);
359 LIS->InsertMachineInstrInMaps(MI&: *And);
360
361 LIS->InsertMachineInstrInMaps(MI&: *Xor);
362 LIS->InsertMachineInstrInMaps(MI&: *Branch);
363
364 RecomputeRegs.insert(V: SrcReg);
365 RecomputeRegs.insert(V: DstReg);
366 LIS->createAndComputeVirtRegInterval(Reg: SaveReg);
367}
368
369void SILowerControlFlow::emitIfBreak(MachineInstr &MI) {
370 MachineBasicBlock &MBB = *MI.getParent();
371 const DebugLoc &DL = MI.getDebugLoc();
372 auto Dst = MI.getOperand(i: 0).getReg();
373
374 // Skip ANDing with exec if the break condition is already masked by exec
375 // because it is a V_CMP in the same basic block. (We know the break
376 // condition operand was an i1 in IR, so if it is a VALU instruction it must
377 // be one with a carry-out.)
378 bool SkipAnding = false;
379 if (MI.getOperand(i: 1).isReg()) {
380 if (MachineInstr *Def = MRI->getUniqueVRegDef(Reg: MI.getOperand(i: 1).getReg())) {
381 SkipAnding = Def->getParent() == MI.getParent() &&
382 SIInstrInfo::isVALU(MI: *Def, /*AllowLDSDMA=*/false);
383 }
384 }
385
386 // AND the break condition operand with exec, then OR that into the "loop
387 // exit" mask.
388 MachineInstr *And = nullptr, *Or = nullptr;
389 Register AndReg;
390 if (!SkipAnding) {
391 AndReg = MRI->createVirtualRegister(RegClass: BoolRC);
392 And = BuildMI(BB&: MBB, I: &MI, MIMD: DL, MCID: TII->get(Opcode: LMC.AndOpc), DestReg: AndReg)
393 .addReg(RegNo: LMC.ExecReg)
394 .add(MO: MI.getOperand(i: 1));
395 if (LV)
396 LV->replaceKillInstruction(Reg: MI.getOperand(i: 1).getReg(), OldMI&: MI, NewMI&: *And);
397 Or = BuildMI(BB&: MBB, I: &MI, MIMD: DL, MCID: TII->get(Opcode: LMC.OrOpc), DestReg: Dst)
398 .addReg(RegNo: AndReg)
399 .add(MO: MI.getOperand(i: 2));
400 } else {
401 Or = BuildMI(BB&: MBB, I: &MI, MIMD: DL, MCID: TII->get(Opcode: LMC.OrOpc), DestReg: Dst)
402 .add(MO: MI.getOperand(i: 1))
403 .add(MO: MI.getOperand(i: 2));
404 if (LV)
405 LV->replaceKillInstruction(Reg: MI.getOperand(i: 1).getReg(), OldMI&: MI, NewMI&: *Or);
406 }
407 if (LV)
408 LV->replaceKillInstruction(Reg: MI.getOperand(i: 2).getReg(), OldMI&: MI, NewMI&: *Or);
409
410 if (LIS) {
411 LIS->ReplaceMachineInstrInMaps(MI, NewMI&: *Or);
412 if (And) {
413 // Read of original operand 1 is on And now not Or.
414 RecomputeRegs.insert(V: And->getOperand(i: 2).getReg());
415 LIS->InsertMachineInstrInMaps(MI&: *And);
416 LIS->createAndComputeVirtRegInterval(Reg: AndReg);
417 }
418 }
419
420 MI.eraseFromParent();
421}
422
423void SILowerControlFlow::emitLoop(MachineInstr &MI) {
424 MachineBasicBlock &MBB = *MI.getParent();
425 const DebugLoc &DL = MI.getDebugLoc();
426
427 MachineInstr *AndN2 =
428 BuildMI(BB&: MBB, I: &MI, MIMD: DL, MCID: TII->get(Opcode: LMC.AndN2TermOpc), DestReg: LMC.ExecReg)
429 .addReg(RegNo: LMC.ExecReg)
430 .add(MO: MI.getOperand(i: 0));
431 if (LV)
432 LV->replaceKillInstruction(Reg: MI.getOperand(i: 0).getReg(), OldMI&: MI, NewMI&: *AndN2);
433
434 auto BranchPt = skipToUncondBrOrEnd(MBB, I: MI.getIterator());
435 MachineInstr *Branch =
436 BuildMI(BB&: MBB, I: BranchPt, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::S_CBRANCH_EXECNZ))
437 .add(MO: MI.getOperand(i: 1));
438
439 if (LIS) {
440 RecomputeRegs.insert(V: MI.getOperand(i: 0).getReg());
441 LIS->ReplaceMachineInstrInMaps(MI, NewMI&: *AndN2);
442 LIS->InsertMachineInstrInMaps(MI&: *Branch);
443 }
444
445 MI.eraseFromParent();
446}
447
448MachineBasicBlock::iterator
449SILowerControlFlow::skipIgnoreExecInstsTrivialSucc(
450 MachineBasicBlock &MBB, MachineBasicBlock::iterator It) const {
451
452 SmallPtrSet<const MachineBasicBlock *, 4> Visited;
453 MachineBasicBlock *B = &MBB;
454 do {
455 if (!Visited.insert(Ptr: B).second)
456 return MBB.end();
457
458 auto E = B->end();
459 for ( ; It != E; ++It) {
460 if (TII->mayReadEXEC(MRI: *MRI, MI: *It))
461 break;
462 }
463
464 if (It != E)
465 return It;
466
467 if (B->succ_size() != 1)
468 return MBB.end();
469
470 // If there is one trivial successor, advance to the next block.
471 MachineBasicBlock *Succ = *B->succ_begin();
472
473 It = Succ->begin();
474 B = Succ;
475 } while (true);
476}
477
478MachineBasicBlock *SILowerControlFlow::emitEndCf(MachineInstr &MI) {
479 MachineBasicBlock &MBB = *MI.getParent();
480 const DebugLoc &DL = MI.getDebugLoc();
481
482 MachineBasicBlock::iterator InsPt = MBB.begin();
483
484 // If we have instructions that aren't prolog instructions, split the block
485 // and emit a terminator instruction. This ensures correct spill placement.
486 // FIXME: We should unconditionally split the block here.
487 bool NeedBlockSplit = false;
488 Register DataReg = MI.getOperand(i: 0).getReg();
489 for (MachineBasicBlock::iterator I = InsPt, E = MI.getIterator();
490 I != E; ++I) {
491 if (I->modifiesRegister(Reg: DataReg, TRI)) {
492 NeedBlockSplit = true;
493 break;
494 }
495 }
496
497 unsigned Opcode = LMC.OrOpc;
498 MachineBasicBlock *SplitBB = &MBB;
499 if (NeedBlockSplit) {
500 SplitBB = MBB.splitAt(SplitInst&: MI, /*UpdateLiveIns*/true, LIS);
501 if (SplitBB != &MBB && (MDT || PDT)) {
502 using DomTreeT = DomTreeBase<MachineBasicBlock>;
503 SmallVector<DomTreeT::UpdateType, 16> DTUpdates;
504 for (MachineBasicBlock *Succ : SplitBB->successors()) {
505 DTUpdates.push_back(Elt: {DomTreeT::Insert, SplitBB, Succ});
506 DTUpdates.push_back(Elt: {DomTreeT::Delete, &MBB, Succ});
507 }
508 DTUpdates.push_back(Elt: {DomTreeT::Insert, &MBB, SplitBB});
509 if (MDT)
510 MDT->applyUpdates(Updates: DTUpdates);
511 if (PDT)
512 PDT->applyUpdates(Updates: DTUpdates);
513 }
514 Opcode = LMC.OrTermOpc;
515 InsPt = MI;
516 }
517
518 MachineInstr *NewMI = BuildMI(BB&: MBB, I: InsPt, MIMD: DL, MCID: TII->get(Opcode), DestReg: LMC.ExecReg)
519 .addReg(RegNo: LMC.ExecReg)
520 .add(MO: MI.getOperand(i: 0));
521 if (LV) {
522 LV->replaceKillInstruction(Reg: DataReg, OldMI&: MI, NewMI&: *NewMI);
523
524 if (SplitBB != &MBB) {
525 // Track the set of registers defined in the original block so we don't
526 // accidentally add the original block to AliveBlocks. AliveBlocks only
527 // includes blocks which are live through, which excludes live outs and
528 // local defs.
529 DenseSet<Register> DefInOrigBlock;
530
531 for (MachineBasicBlock *BlockPiece : {&MBB, SplitBB}) {
532 for (MachineInstr &X : *BlockPiece) {
533 for (MachineOperand &Op : X.all_defs()) {
534 if (Op.getReg().isVirtual())
535 DefInOrigBlock.insert(V: Op.getReg());
536 }
537 }
538 }
539
540 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
541 Register Reg = Register::index2VirtReg(Index: i);
542 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg);
543
544 if (VI.AliveBlocks.test(Idx: MBB.getNumber()))
545 VI.AliveBlocks.set(SplitBB->getNumber());
546 else {
547 for (MachineInstr *Kill : VI.Kills) {
548 if (Kill->getParent() == SplitBB && !DefInOrigBlock.contains(V: Reg))
549 VI.AliveBlocks.set(MBB.getNumber());
550 }
551 }
552 }
553 }
554 }
555
556 LoweredEndCf.insert(X: NewMI);
557
558 if (LIS)
559 LIS->ReplaceMachineInstrInMaps(MI, NewMI&: *NewMI);
560
561 MI.eraseFromParent();
562
563 if (LIS)
564 LIS->handleMove(MI&: *NewMI);
565 return SplitBB;
566}
567
568// Returns replace operands for a logical operation, either single result
569// for exec or two operands if source was another equivalent operation.
570void SILowerControlFlow::findMaskOperands(
571 MachineInstr &MI, unsigned OpNo,
572 SmallVectorImpl<MachineOperand *> &Src) const {
573 MachineOperand &Op = MI.getOperand(i: OpNo);
574 if (!Op.isReg() || !Op.getReg().isVirtual()) {
575 Src.push_back(Elt: &Op);
576 return;
577 }
578
579 MachineInstr *Def = MRI->getUniqueVRegDef(Reg: Op.getReg());
580 if (!Def || Def->getParent() != MI.getParent() ||
581 !(Def->isFullCopy() || (Def->getOpcode() == MI.getOpcode())))
582 return;
583
584 // Make sure we do not modify exec between def and use.
585 // A copy with implicitly defined exec inserted earlier is an exclusion, it
586 // does not really modify exec.
587 for (auto I = Def->getIterator(); I != MI.getIterator(); ++I)
588 if (I->modifiesRegister(Reg: AMDGPU::EXEC, TRI) &&
589 !(I->isCopy() && I->getOperand(i: 0).getReg() != LMC.ExecReg))
590 return;
591
592 for (MachineOperand &SrcOp : Def->explicit_operands())
593 if (SrcOp.isReg() && SrcOp.isUse() &&
594 (SrcOp.getReg().isVirtual() || SrcOp.getReg() == LMC.ExecReg))
595 Src.push_back(Elt: &SrcOp);
596}
597
598// Search and combine pairs of equivalent instructions, like
599// S_AND_B64 x, (S_AND_B64 x, y) => S_AND_B64 x, y
600// S_OR_B64 x, (S_OR_B64 x, y) => S_OR_B64 x, y
601// One of the operands is exec mask.
602void SILowerControlFlow::combineMasks(MachineInstr &MI) {
603 assert(MI.getNumExplicitOperands() == 3);
604 SmallVector<MachineOperand *, 2> Src1, Src2;
605 findMaskOperands(MI, OpNo: 1, Src&: Src1);
606 findMaskOperands(MI, OpNo: 2, Src&: Src2);
607
608 // Exactly one of the two operands must resolve to the nested LHS and RHS.
609 // Another one must resolve to a single value, exec or its copy.
610 unsigned OpToReplace;
611 MachineOperand *Leaf, *NestedLHS, *NestedRHS;
612 if (Src1.size() == 2 && Src2.size() == 1) {
613 OpToReplace = 1;
614 NestedLHS = Src1[0];
615 NestedRHS = Src1[1];
616 Leaf = Src2[0];
617 } else if (Src1.size() == 1 && Src2.size() == 2) {
618 OpToReplace = 2;
619 Leaf = Src1[0];
620 NestedLHS = Src2[0];
621 NestedRHS = Src2[1];
622 } else {
623 return;
624 }
625
626 // Always keep a nested operand, never the leaf operand.
627 MachineOperand *KeepOp;
628 if (Leaf->isIdenticalTo(Other: *NestedLHS))
629 KeepOp = NestedRHS;
630 else if (Leaf->isIdenticalTo(Other: *NestedRHS) ||
631 NestedLHS->isIdenticalTo(Other: *NestedRHS))
632 KeepOp = NestedLHS;
633 else
634 return;
635
636 Register Reg = MI.getOperand(i: OpToReplace).getReg();
637 MI.removeOperand(OpNo: OpToReplace);
638 MI.addOperand(Op: *KeepOp);
639 if (MRI->use_empty(RegNo: Reg))
640 MRI->getUniqueVRegDef(Reg)->eraseFromParent();
641}
642
643void SILowerControlFlow::optimizeEndCf() {
644 // If the only instruction immediately following this END_CF is another
645 // END_CF in the only successor we can avoid emitting exec mask restore here.
646 if (!EnableOptimizeEndCf)
647 return;
648
649 for (MachineInstr *MI : reverse(C&: LoweredEndCf)) {
650 MachineBasicBlock &MBB = *MI->getParent();
651 auto Next =
652 skipIgnoreExecInstsTrivialSucc(MBB, It: std::next(x: MI->getIterator()));
653 if (Next == MBB.end() || !LoweredEndCf.count(key: &*Next))
654 continue;
655 // Only skip inner END_CF if outer ENDCF belongs to SI_IF.
656 // If that belongs to SI_ELSE then saved mask has an inverted value.
657 Register SavedExec
658 = TII->getNamedOperand(MI&: *Next, OperandName: AMDGPU::OpName::src1)->getReg();
659 assert(SavedExec.isVirtual() && "Expected saved exec to be src1!");
660
661 const MachineInstr *Def = MRI->getUniqueVRegDef(Reg: SavedExec);
662 if (Def && LoweredIf.count(V: SavedExec)) {
663 LLVM_DEBUG(dbgs() << "Skip redundant "; MI->dump());
664 if (LIS)
665 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
666 Register Reg;
667 if (LV)
668 Reg = TII->getNamedOperand(MI&: *MI, OperandName: AMDGPU::OpName::src1)->getReg();
669 MI->eraseFromParent();
670 if (LV)
671 LV->recomputeForSingleDefVirtReg(Reg);
672 removeMBBifRedundant(MBB);
673 }
674 }
675}
676
677MachineBasicBlock *SILowerControlFlow::process(MachineInstr &MI) {
678 MachineBasicBlock &MBB = *MI.getParent();
679 MachineBasicBlock::iterator I(MI);
680 MachineInstr *Prev = (I != MBB.begin()) ? &*(std::prev(x: I)) : nullptr;
681
682 MachineBasicBlock *SplitBB = &MBB;
683
684 switch (MI.getOpcode()) {
685 case AMDGPU::SI_IF:
686 emitIf(MI);
687 break;
688
689 case AMDGPU::SI_ELSE:
690 emitElse(MI);
691 break;
692
693 case AMDGPU::SI_IF_BREAK:
694 emitIfBreak(MI);
695 break;
696
697 case AMDGPU::SI_LOOP:
698 emitLoop(MI);
699 break;
700
701 case AMDGPU::SI_WATERFALL_LOOP:
702 MI.setDesc(TII->get(Opcode: AMDGPU::S_CBRANCH_EXECNZ));
703 break;
704
705 case AMDGPU::SI_END_CF:
706 SplitBB = emitEndCf(MI);
707 break;
708
709 default:
710 assert(false && "Attempt to process unsupported instruction");
711 break;
712 }
713
714 MachineBasicBlock::iterator Next;
715 for (I = Prev ? Prev->getIterator() : MBB.begin(); I != MBB.end(); I = Next) {
716 Next = std::next(x: I);
717 MachineInstr &MaskMI = *I;
718 switch (MaskMI.getOpcode()) {
719 case AMDGPU::S_AND_B64:
720 case AMDGPU::S_OR_B64:
721 case AMDGPU::S_AND_B32:
722 case AMDGPU::S_OR_B32:
723 // Cleanup bit manipulations on exec mask
724 combineMasks(MI&: MaskMI);
725 break;
726 default:
727 I = MBB.end();
728 break;
729 }
730 }
731
732 return SplitBB;
733}
734
735bool SILowerControlFlow::removeMBBifRedundant(MachineBasicBlock &MBB) {
736 for (auto &I : MBB.instrs()) {
737 if (!I.isDebugInstr() && !I.isUnconditionalBranch())
738 return false;
739 }
740
741 assert(MBB.succ_size() == 1 && "MBB has more than one successor");
742
743 MachineBasicBlock *Succ = *MBB.succ_begin();
744 MachineBasicBlock *FallThrough = nullptr;
745
746 using DomTreeT = DomTreeBase<MachineBasicBlock>;
747 SmallVector<DomTreeT::UpdateType, 8> DTUpdates;
748
749 while (!MBB.predecessors().empty()) {
750 MachineBasicBlock *P = *MBB.pred_begin();
751 if (P->getFallThrough(JumpToFallThrough: false) == &MBB)
752 FallThrough = P;
753 P->ReplaceUsesOfBlockWith(Old: &MBB, New: Succ);
754 DTUpdates.push_back(Elt: {DomTreeT::Insert, P, Succ});
755 DTUpdates.push_back(Elt: {DomTreeT::Delete, P, &MBB});
756 }
757 MBB.removeSuccessor(Succ);
758 if (LIS) {
759 // Registers live across MBB have intervals spanning it, which must be
760 // recomputed once it is erased. removeMBBifRedundant only runs from
761 // optimizeEndCf, so defer to the pass-wide RecomputeRegs handling.
762 SlotIndex StartIdx = LIS->getMBBStartIdx(mbb: &MBB);
763 for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) {
764 Register Reg = Register::index2VirtReg(Index: I);
765 if (!LIS->hasInterval(Reg))
766 continue;
767 const LiveInterval &LI = LIS->getInterval(Reg);
768 if (LI.liveAt(index: StartIdx) || LI.liveAt(index: StartIdx.getPrevSlot()))
769 RecomputeRegs.insert(V: Reg);
770 }
771
772 for (auto &I : MBB.instrs())
773 LIS->RemoveMachineInstrFromMaps(MI&: I);
774
775 // Drop MBB from the slot index maps before it is erased.
776 LIS->getSlotIndexes()->removeMBBFromMaps(MBB);
777 }
778 if (MDT)
779 MDT->applyUpdates(Updates: DTUpdates);
780 if (PDT)
781 PDT->applyUpdates(Updates: DTUpdates);
782
783 if (MDT && MDT->getNode(BB: &MBB))
784 MDT->eraseNode(BB: &MBB);
785 if (PDT && PDT->getNode(BB: &MBB))
786 PDT->eraseNode(BB: &MBB);
787
788 MBB.clear();
789 MBB.eraseFromParent();
790 if (FallThrough && !FallThrough->isLayoutSuccessor(MBB: Succ)) {
791 // Note: we cannot update block layout and preserve live intervals;
792 // hence we must insert a branch.
793 MachineInstr *BranchMI = BuildMI(BB&: *FallThrough, I: FallThrough->end(),
794 MIMD: FallThrough->findBranchDebugLoc(), MCID: TII->get(Opcode: AMDGPU::S_BRANCH))
795 .addMBB(MBB: Succ);
796 if (LIS)
797 LIS->InsertMachineInstrInMaps(MI&: *BranchMI);
798 }
799
800 return true;
801}
802
803bool SILowerControlFlow::run(MachineFunction &MF) {
804 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
805 TII = ST.getInstrInfo();
806 TRI = &TII->getRegisterInfo();
807 EnableOptimizeEndCf = RemoveRedundantEndcf &&
808 MF.getTarget().getOptLevel() > CodeGenOptLevel::None;
809
810 MRI = &MF.getRegInfo();
811 BoolRC = TRI->getBoolRC();
812
813 // Compute set of blocks with kills
814 const bool CanDemote =
815 MF.getFunction().getCallingConv() == CallingConv::AMDGPU_PS;
816 for (auto &MBB : MF) {
817 bool IsKillBlock = false;
818 for (auto &Term : MBB.terminators()) {
819 if (TII->isKillTerminator(Opcode: Term.getOpcode())) {
820 KillBlocks.insert(Ptr: &MBB);
821 IsKillBlock = true;
822 break;
823 }
824 }
825 if (CanDemote && !IsKillBlock) {
826 for (auto &MI : MBB) {
827 if (MI.getOpcode() == AMDGPU::SI_DEMOTE_I1) {
828 KillBlocks.insert(Ptr: &MBB);
829 break;
830 }
831 }
832 }
833 }
834
835 bool Changed = false;
836 MachineFunction::iterator NextBB;
837 for (MachineFunction::iterator BI = MF.begin();
838 BI != MF.end(); BI = NextBB) {
839 NextBB = std::next(x: BI);
840 MachineBasicBlock *MBB = &*BI;
841
842 MachineBasicBlock::iterator I, E, Next;
843 E = MBB->end();
844 for (I = MBB->begin(); I != E; I = Next) {
845 Next = std::next(x: I);
846 MachineInstr &MI = *I;
847 MachineBasicBlock *SplitMBB = MBB;
848
849 switch (MI.getOpcode()) {
850 case AMDGPU::SI_IF:
851 case AMDGPU::SI_ELSE:
852 case AMDGPU::SI_IF_BREAK:
853 case AMDGPU::SI_WATERFALL_LOOP:
854 case AMDGPU::SI_LOOP:
855 case AMDGPU::SI_END_CF:
856 SplitMBB = process(MI);
857 Changed = true;
858 break;
859 }
860
861 if (SplitMBB != MBB) {
862 MBB = Next->getParent();
863 E = MBB->end();
864 }
865 }
866 }
867
868 optimizeEndCf();
869
870 if (LIS && Changed) {
871 // These will need to be recomputed for insertions and removals.
872 LIS->removeAllRegUnitsForPhysReg(Reg: AMDGPU::EXEC);
873 LIS->removeAllRegUnitsForPhysReg(Reg: AMDGPU::SCC);
874 for (Register Reg : RecomputeRegs) {
875 LIS->removeInterval(Reg);
876 LIS->createAndComputeVirtRegInterval(Reg);
877 }
878 }
879
880 RecomputeRegs.clear();
881 LoweredEndCf.clear();
882 LoweredIf.clear();
883 KillBlocks.clear();
884
885 return Changed;
886}
887
888bool SILowerControlFlowLegacy::runOnMachineFunction(MachineFunction &MF) {
889 const GCNSubtarget *ST = &MF.getSubtarget<GCNSubtarget>();
890 // This doesn't actually need LiveIntervals, but we can preserve them.
891 auto *LISWrapper = getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
892 LiveIntervals *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
893 // This doesn't actually need LiveVariables, but we can preserve them.
894 auto *LVWrapper = getAnalysisIfAvailable<LiveVariablesWrapperPass>();
895 LiveVariables *LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
896 auto *MDTWrapper = getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();
897 MachineDominatorTree *MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;
898 auto *PDTWrapper =
899 getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>();
900 MachinePostDominatorTree *PDT =
901 PDTWrapper ? &PDTWrapper->getPostDomTree() : nullptr;
902 return SILowerControlFlow(ST, LIS, LV, MDT, PDT).run(MF);
903}
904
905PreservedAnalyses
906SILowerControlFlowPass::run(MachineFunction &MF,
907 MachineFunctionAnalysisManager &MFAM) {
908 const GCNSubtarget *ST = &MF.getSubtarget<GCNSubtarget>();
909 LiveIntervals *LIS = MFAM.getCachedResult<LiveIntervalsAnalysis>(IR&: MF);
910 LiveVariables *LV = MFAM.getCachedResult<LiveVariablesAnalysis>(IR&: MF);
911 MachineDominatorTree *MDT =
912 MFAM.getCachedResult<MachineDominatorTreeAnalysis>(IR&: MF);
913 MachinePostDominatorTree *PDT =
914 MFAM.getCachedResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
915
916 bool Changed = SILowerControlFlow(ST, LIS, LV, MDT, PDT).run(MF);
917 if (!Changed)
918 return PreservedAnalyses::all();
919
920 auto PA = getMachineFunctionPassPreservedAnalyses();
921 PA.preserve<MachineDominatorTreeAnalysis>();
922 PA.preserve<MachinePostDominatorTreeAnalysis>();
923 PA.preserve<SlotIndexesAnalysis>();
924 PA.preserve<LiveIntervalsAnalysis>();
925 PA.preserve<LiveVariablesAnalysis>();
926 PA.preserve<MachineBlockFrequencyAnalysis>();
927 return PA;
928}
929