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