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