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