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