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/Target/TargetMachine.h"
64
65using namespace llvm;
66
67#define DEBUG_TYPE "si-lower-control-flow"
68
69static cl::opt<bool>
70RemoveRedundantEndcf("amdgpu-remove-redundant-endcf",
71 cl::init(Val: true), cl::ReallyHidden);
72
73namespace {
74
75class SILowerControlFlow {
76private:
77 const SIRegisterInfo *TRI = nullptr;
78 const SIInstrInfo *TII = nullptr;
79 LiveIntervals *LIS = nullptr;
80 LiveVariables *LV = nullptr;
81 MachineDominatorTree *MDT = nullptr;
82 MachinePostDominatorTree *PDT = nullptr;
83 MachineRegisterInfo *MRI = nullptr;
84 SetVector<MachineInstr*> LoweredEndCf;
85 DenseSet<Register> LoweredIf;
86 SmallPtrSet<MachineBasicBlock *, 4> KillBlocks;
87 SmallSet<Register, 8> RecomputeRegs;
88
89 const TargetRegisterClass *BoolRC = nullptr;
90 const AMDGPU::LaneMaskConstants &LMC;
91
92 bool EnableOptimizeEndCf = false;
93
94 bool hasKill(const MachineBasicBlock *Begin, const MachineBasicBlock *End);
95
96 void emitIf(MachineInstr &MI);
97 void emitElse(MachineInstr &MI);
98 void emitIfBreak(MachineInstr &MI);
99 void emitLoop(MachineInstr &MI);
100
101 MachineBasicBlock *emitEndCf(MachineInstr &MI);
102
103 void findMaskOperands(MachineInstr &MI, unsigned OpNo,
104 SmallVectorImpl<MachineOperand> &Src) const;
105
106 void combineMasks(MachineInstr &MI);
107
108 bool removeMBBifRedundant(MachineBasicBlock &MBB);
109
110 MachineBasicBlock *process(MachineInstr &MI);
111
112 // Skip to the next instruction, ignoring debug instructions, and trivial
113 // block boundaries (blocks that have one (typically fallthrough) successor,
114 // and the successor has one predecessor.
115 MachineBasicBlock::iterator
116 skipIgnoreExecInstsTrivialSucc(MachineBasicBlock &MBB,
117 MachineBasicBlock::iterator It) const;
118
119 /// Find the insertion point for a new conditional branch.
120 MachineBasicBlock::iterator
121 skipToUncondBrOrEnd(MachineBasicBlock &MBB,
122 MachineBasicBlock::iterator I) const {
123 assert(I->isTerminator());
124
125 // FIXME: What if we had multiple pre-existing conditional branches?
126 MachineBasicBlock::iterator End = MBB.end();
127 while (I != End && !I->isUnconditionalBranch())
128 ++I;
129 return I;
130 }
131
132 // Remove redundant SI_END_CF instructions.
133 void optimizeEndCf();
134
135public:
136 SILowerControlFlow(const GCNSubtarget *ST, LiveIntervals *LIS,
137 LiveVariables *LV, MachineDominatorTree *MDT,
138 MachinePostDominatorTree *PDT)
139 : LIS(LIS), LV(LV), MDT(MDT), PDT(PDT),
140 LMC(AMDGPU::LaneMaskConstants::get(ST: *ST)) {}
141 bool run(MachineFunction &MF);
142};
143
144class SILowerControlFlowLegacy : public MachineFunctionPass {
145public:
146 static char ID;
147
148 SILowerControlFlowLegacy() : MachineFunctionPass(ID) {}
149
150 bool runOnMachineFunction(MachineFunction &MF) override;
151
152 StringRef getPassName() const override {
153 return "SI Lower control flow pseudo instructions";
154 }
155
156 void getAnalysisUsage(AnalysisUsage &AU) const override {
157 AU.addUsedIfAvailable<LiveIntervalsWrapperPass>();
158 // Should preserve the same set that TwoAddressInstructions does.
159 AU.addPreserved<MachineDominatorTreeWrapperPass>();
160 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();
161 AU.addPreserved<SlotIndexesWrapperPass>();
162 AU.addPreserved<LiveIntervalsWrapperPass>();
163 AU.addPreserved<LiveVariablesWrapperPass>();
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);
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(MachineInstr &MI, unsigned OpNo,
571 SmallVectorImpl<MachineOperand> &Src) const {
572 MachineOperand &Op = MI.getOperand(i: OpNo);
573 if (!Op.isReg() || !Op.getReg().isVirtual()) {
574 Src.push_back(Elt: Op);
575 return;
576 }
577
578 MachineInstr *Def = MRI->getUniqueVRegDef(Reg: Op.getReg());
579 if (!Def || Def->getParent() != MI.getParent() ||
580 !(Def->isFullCopy() || (Def->getOpcode() == MI.getOpcode())))
581 return;
582
583 // Make sure we do not modify exec between def and use.
584 // A copy with implicitly defined exec inserted earlier is an exclusion, it
585 // does not really modify exec.
586 for (auto I = Def->getIterator(); I != MI.getIterator(); ++I)
587 if (I->modifiesRegister(Reg: AMDGPU::EXEC, TRI) &&
588 !(I->isCopy() && I->getOperand(i: 0).getReg() != LMC.ExecReg))
589 return;
590
591 for (const auto &SrcOp : Def->explicit_operands())
592 if (SrcOp.isReg() && SrcOp.isUse() &&
593 (SrcOp.getReg().isVirtual() || SrcOp.getReg() == LMC.ExecReg))
594 Src.push_back(Elt: SrcOp);
595}
596
597// Search and combine pairs of equivalent instructions, like
598// S_AND_B64 x, (S_AND_B64 x, y) => S_AND_B64 x, y
599// S_OR_B64 x, (S_OR_B64 x, y) => S_OR_B64 x, y
600// One of the operands is exec mask.
601void SILowerControlFlow::combineMasks(MachineInstr &MI) {
602 assert(MI.getNumExplicitOperands() == 3);
603 SmallVector<MachineOperand, 4> Ops;
604 unsigned OpToReplace = 1;
605 findMaskOperands(MI, OpNo: 1, Src&: Ops);
606 if (Ops.size() == 1) OpToReplace = 2; // First operand can be exec or its copy
607 findMaskOperands(MI, OpNo: 2, Src&: Ops);
608 if (Ops.size() != 3) return;
609
610 unsigned UniqueOpndIdx;
611 if (Ops[0].isIdenticalTo(Other: Ops[1])) UniqueOpndIdx = 2;
612 else if (Ops[0].isIdenticalTo(Other: Ops[2])) UniqueOpndIdx = 1;
613 else if (Ops[1].isIdenticalTo(Other: Ops[2])) UniqueOpndIdx = 1;
614 else return;
615
616 Register Reg = MI.getOperand(i: OpToReplace).getReg();
617 MI.removeOperand(OpNo: OpToReplace);
618 MI.addOperand(Op: Ops[UniqueOpndIdx]);
619 if (MRI->use_empty(RegNo: Reg))
620 MRI->getUniqueVRegDef(Reg)->eraseFromParent();
621}
622
623void SILowerControlFlow::optimizeEndCf() {
624 // If the only instruction immediately following this END_CF is another
625 // END_CF in the only successor we can avoid emitting exec mask restore here.
626 if (!EnableOptimizeEndCf)
627 return;
628
629 for (MachineInstr *MI : reverse(C&: LoweredEndCf)) {
630 MachineBasicBlock &MBB = *MI->getParent();
631 auto Next =
632 skipIgnoreExecInstsTrivialSucc(MBB, It: std::next(x: MI->getIterator()));
633 if (Next == MBB.end() || !LoweredEndCf.count(key: &*Next))
634 continue;
635 // Only skip inner END_CF if outer ENDCF belongs to SI_IF.
636 // If that belongs to SI_ELSE then saved mask has an inverted value.
637 Register SavedExec
638 = TII->getNamedOperand(MI&: *Next, OperandName: AMDGPU::OpName::src1)->getReg();
639 assert(SavedExec.isVirtual() && "Expected saved exec to be src1!");
640
641 const MachineInstr *Def = MRI->getUniqueVRegDef(Reg: SavedExec);
642 if (Def && LoweredIf.count(V: SavedExec)) {
643 LLVM_DEBUG(dbgs() << "Skip redundant "; MI->dump());
644 if (LIS)
645 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
646 Register Reg;
647 if (LV)
648 Reg = TII->getNamedOperand(MI&: *MI, OperandName: AMDGPU::OpName::src1)->getReg();
649 MI->eraseFromParent();
650 if (LV)
651 LV->recomputeForSingleDefVirtReg(Reg);
652 removeMBBifRedundant(MBB);
653 }
654 }
655}
656
657MachineBasicBlock *SILowerControlFlow::process(MachineInstr &MI) {
658 MachineBasicBlock &MBB = *MI.getParent();
659 MachineBasicBlock::iterator I(MI);
660 MachineInstr *Prev = (I != MBB.begin()) ? &*(std::prev(x: I)) : nullptr;
661
662 MachineBasicBlock *SplitBB = &MBB;
663
664 switch (MI.getOpcode()) {
665 case AMDGPU::SI_IF:
666 emitIf(MI);
667 break;
668
669 case AMDGPU::SI_ELSE:
670 emitElse(MI);
671 break;
672
673 case AMDGPU::SI_IF_BREAK:
674 emitIfBreak(MI);
675 break;
676
677 case AMDGPU::SI_LOOP:
678 emitLoop(MI);
679 break;
680
681 case AMDGPU::SI_WATERFALL_LOOP:
682 MI.setDesc(TII->get(Opcode: AMDGPU::S_CBRANCH_EXECNZ));
683 break;
684
685 case AMDGPU::SI_END_CF:
686 SplitBB = emitEndCf(MI);
687 break;
688
689 default:
690 assert(false && "Attempt to process unsupported instruction");
691 break;
692 }
693
694 MachineBasicBlock::iterator Next;
695 for (I = Prev ? Prev->getIterator() : MBB.begin(); I != MBB.end(); I = Next) {
696 Next = std::next(x: I);
697 MachineInstr &MaskMI = *I;
698 switch (MaskMI.getOpcode()) {
699 case AMDGPU::S_AND_B64:
700 case AMDGPU::S_OR_B64:
701 case AMDGPU::S_AND_B32:
702 case AMDGPU::S_OR_B32:
703 // Cleanup bit manipulations on exec mask
704 combineMasks(MI&: MaskMI);
705 break;
706 default:
707 I = MBB.end();
708 break;
709 }
710 }
711
712 return SplitBB;
713}
714
715bool SILowerControlFlow::removeMBBifRedundant(MachineBasicBlock &MBB) {
716 for (auto &I : MBB.instrs()) {
717 if (!I.isDebugInstr() && !I.isUnconditionalBranch())
718 return false;
719 }
720
721 assert(MBB.succ_size() == 1 && "MBB has more than one successor");
722
723 MachineBasicBlock *Succ = *MBB.succ_begin();
724 MachineBasicBlock *FallThrough = nullptr;
725
726 using DomTreeT = DomTreeBase<MachineBasicBlock>;
727 SmallVector<DomTreeT::UpdateType, 8> DTUpdates;
728
729 while (!MBB.predecessors().empty()) {
730 MachineBasicBlock *P = *MBB.pred_begin();
731 if (P->getFallThrough(JumpToFallThrough: false) == &MBB)
732 FallThrough = P;
733 P->ReplaceUsesOfBlockWith(Old: &MBB, New: Succ);
734 DTUpdates.push_back(Elt: {DomTreeT::Insert, P, Succ});
735 DTUpdates.push_back(Elt: {DomTreeT::Delete, P, &MBB});
736 }
737 MBB.removeSuccessor(Succ);
738 if (LIS) {
739 for (auto &I : MBB.instrs())
740 LIS->RemoveMachineInstrFromMaps(MI&: I);
741 }
742 if (MDT)
743 MDT->applyUpdates(Updates: DTUpdates);
744 if (PDT)
745 PDT->applyUpdates(Updates: DTUpdates);
746
747 if (MDT && MDT->getNode(BB: &MBB))
748 MDT->eraseNode(BB: &MBB);
749 if (PDT && PDT->getNode(BB: &MBB))
750 PDT->eraseNode(BB: &MBB);
751
752 MBB.clear();
753 MBB.eraseFromParent();
754 if (FallThrough && !FallThrough->isLayoutSuccessor(MBB: Succ)) {
755 // Note: we cannot update block layout and preserve live intervals;
756 // hence we must insert a branch.
757 MachineInstr *BranchMI = BuildMI(BB&: *FallThrough, I: FallThrough->end(),
758 MIMD: FallThrough->findBranchDebugLoc(), MCID: TII->get(Opcode: AMDGPU::S_BRANCH))
759 .addMBB(MBB: Succ);
760 if (LIS)
761 LIS->InsertMachineInstrInMaps(MI&: *BranchMI);
762 }
763
764 return true;
765}
766
767bool SILowerControlFlow::run(MachineFunction &MF) {
768 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
769 TII = ST.getInstrInfo();
770 TRI = &TII->getRegisterInfo();
771 EnableOptimizeEndCf = RemoveRedundantEndcf &&
772 MF.getTarget().getOptLevel() > CodeGenOptLevel::None;
773
774 MRI = &MF.getRegInfo();
775 BoolRC = TRI->getBoolRC();
776
777 // Compute set of blocks with kills
778 const bool CanDemote =
779 MF.getFunction().getCallingConv() == CallingConv::AMDGPU_PS;
780 for (auto &MBB : MF) {
781 bool IsKillBlock = false;
782 for (auto &Term : MBB.terminators()) {
783 if (TII->isKillTerminator(Opcode: Term.getOpcode())) {
784 KillBlocks.insert(Ptr: &MBB);
785 IsKillBlock = true;
786 break;
787 }
788 }
789 if (CanDemote && !IsKillBlock) {
790 for (auto &MI : MBB) {
791 if (MI.getOpcode() == AMDGPU::SI_DEMOTE_I1) {
792 KillBlocks.insert(Ptr: &MBB);
793 break;
794 }
795 }
796 }
797 }
798
799 bool Changed = false;
800 MachineFunction::iterator NextBB;
801 for (MachineFunction::iterator BI = MF.begin();
802 BI != MF.end(); BI = NextBB) {
803 NextBB = std::next(x: BI);
804 MachineBasicBlock *MBB = &*BI;
805
806 MachineBasicBlock::iterator I, E, Next;
807 E = MBB->end();
808 for (I = MBB->begin(); I != E; I = Next) {
809 Next = std::next(x: I);
810 MachineInstr &MI = *I;
811 MachineBasicBlock *SplitMBB = MBB;
812
813 switch (MI.getOpcode()) {
814 case AMDGPU::SI_IF:
815 case AMDGPU::SI_ELSE:
816 case AMDGPU::SI_IF_BREAK:
817 case AMDGPU::SI_WATERFALL_LOOP:
818 case AMDGPU::SI_LOOP:
819 case AMDGPU::SI_END_CF:
820 SplitMBB = process(MI);
821 Changed = true;
822 break;
823 }
824
825 if (SplitMBB != MBB) {
826 MBB = Next->getParent();
827 E = MBB->end();
828 }
829 }
830 }
831
832 optimizeEndCf();
833
834 if (LIS && Changed) {
835 // These will need to be recomputed for insertions and removals.
836 LIS->removeAllRegUnitsForPhysReg(Reg: AMDGPU::EXEC);
837 LIS->removeAllRegUnitsForPhysReg(Reg: AMDGPU::SCC);
838 for (Register Reg : RecomputeRegs) {
839 LIS->removeInterval(Reg);
840 LIS->createAndComputeVirtRegInterval(Reg);
841 }
842 }
843
844 RecomputeRegs.clear();
845 LoweredEndCf.clear();
846 LoweredIf.clear();
847 KillBlocks.clear();
848
849 return Changed;
850}
851
852bool SILowerControlFlowLegacy::runOnMachineFunction(MachineFunction &MF) {
853 const GCNSubtarget *ST = &MF.getSubtarget<GCNSubtarget>();
854 // This doesn't actually need LiveIntervals, but we can preserve them.
855 auto *LISWrapper = getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
856 LiveIntervals *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
857 // This doesn't actually need LiveVariables, but we can preserve them.
858 auto *LVWrapper = getAnalysisIfAvailable<LiveVariablesWrapperPass>();
859 LiveVariables *LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
860 auto *MDTWrapper = getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();
861 MachineDominatorTree *MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;
862 auto *PDTWrapper =
863 getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>();
864 MachinePostDominatorTree *PDT =
865 PDTWrapper ? &PDTWrapper->getPostDomTree() : nullptr;
866 return SILowerControlFlow(ST, LIS, LV, MDT, PDT).run(MF);
867}
868
869PreservedAnalyses
870SILowerControlFlowPass::run(MachineFunction &MF,
871 MachineFunctionAnalysisManager &MFAM) {
872 const GCNSubtarget *ST = &MF.getSubtarget<GCNSubtarget>();
873 LiveIntervals *LIS = MFAM.getCachedResult<LiveIntervalsAnalysis>(IR&: MF);
874 LiveVariables *LV = MFAM.getCachedResult<LiveVariablesAnalysis>(IR&: MF);
875 MachineDominatorTree *MDT =
876 MFAM.getCachedResult<MachineDominatorTreeAnalysis>(IR&: MF);
877 MachinePostDominatorTree *PDT =
878 MFAM.getCachedResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
879
880 bool Changed = SILowerControlFlow(ST, LIS, LV, MDT, PDT).run(MF);
881 if (!Changed)
882 return PreservedAnalyses::all();
883
884 auto PA = getMachineFunctionPassPreservedAnalyses();
885 PA.preserve<MachineDominatorTreeAnalysis>();
886 PA.preserve<MachinePostDominatorTreeAnalysis>();
887 PA.preserve<SlotIndexesAnalysis>();
888 PA.preserve<LiveIntervalsAnalysis>();
889 PA.preserve<LiveVariablesAnalysis>();
890 PA.preserve<MachineBlockFrequencyAnalysis>();
891 return PA;
892}
893