1//===--------------------- SIOptimizeVGPRLiveRange.cpp -------------------===//
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 tries to remove unnecessary VGPR live ranges in divergent if-else
11/// structures and waterfall loops.
12///
13/// When we do structurization, we usually transform an if-else into two
14/// successive if-then (with a flow block to do predicate inversion). Consider a
15/// simple case after structurization: A divergent value %a was defined before
16/// if-else and used in both THEN (use in THEN is optional) and ELSE part:
17/// bb.if:
18/// %a = ...
19/// ...
20/// bb.then:
21/// ... = op %a
22/// ... // %a can be dead here
23/// bb.flow:
24/// ...
25/// bb.else:
26/// ... = %a
27/// ...
28/// bb.endif
29///
30/// As register allocator has no idea of the thread-control-flow, it will just
31/// assume %a would be alive in the whole range of bb.then because of a later
32/// use in bb.else. On AMDGPU architecture, the VGPR is accessed with respect
33/// to exec mask. For this if-else case, the lanes active in bb.then will be
34/// inactive in bb.else, and vice-versa. So we are safe to say that %a was dead
35/// after the last use in bb.then until the end of the block. The reason is
36/// the instructions in bb.then will only overwrite lanes that will never be
37/// accessed in bb.else.
38///
39/// This pass aims to tell register allocator that %a is in-fact dead,
40/// through inserting a phi-node in bb.flow saying that %a is undef when coming
41/// from bb.then, and then replace the uses in the bb.else with the result of
42/// newly inserted phi.
43///
44/// Two key conditions must be met to ensure correctness:
45/// 1.) The def-point should be in the same loop-level as if-else-endif to make
46/// sure the second loop iteration still get correct data.
47/// 2.) There should be no further uses after the IF-ELSE region.
48///
49///
50/// Waterfall loops get inserted around instructions that use divergent values
51/// but can only be executed with a uniform value. For example an indirect call
52/// to a divergent address:
53/// bb.start:
54/// %a = ...
55/// %fun = ...
56/// ...
57/// bb.loop:
58/// call %fun (%a)
59/// ... // %a can be dead here
60/// loop %bb.loop
61///
62/// The loop block is executed multiple times, but it is run exactly once for
63/// each active lane. Similar to the if-else case, the register allocator
64/// assumes that %a is live throughout the loop as it is used again in the next
65/// iteration. If %a is a VGPR that is unused after the loop, it does not need
66/// to be live after its last use in the loop block. By inserting a phi-node at
67/// the start of bb.loop that is undef when coming from bb.loop, the register
68/// allocation knows that the value of %a does not need to be preserved through
69/// iterations of the loop.
70///
71//
72//===----------------------------------------------------------------------===//
73
74#include "SIOptimizeVGPRLiveRange.h"
75#include "AMDGPU.h"
76#include "GCNSubtarget.h"
77#include "MCTargetDesc/AMDGPUMCTargetDesc.h"
78#include "SIMachineFunctionInfo.h"
79#include "llvm/CodeGen/LiveVariables.h"
80#include "llvm/CodeGen/MachineDominators.h"
81#include "llvm/CodeGen/MachineLoopInfo.h"
82#include "llvm/CodeGen/RegisterClassInfo.h"
83#include "llvm/CodeGen/TargetRegisterInfo.h"
84#include "llvm/IR/Dominators.h"
85#include "llvm/InitializePasses.h"
86
87using namespace llvm;
88
89#define DEBUG_TYPE "si-opt-vgpr-liverange"
90
91namespace {
92
93class SIOptimizeVGPRLiveRange {
94private:
95 const SIRegisterInfo *TRI = nullptr;
96 const SIInstrInfo *TII = nullptr;
97 LiveVariables *LV = nullptr;
98 MachineDominatorTree *MDT = nullptr;
99 const MachineLoopInfo *Loops = nullptr;
100 MachineRegisterInfo *MRI = nullptr;
101
102public:
103 SIOptimizeVGPRLiveRange(LiveVariables *LV, MachineDominatorTree *MDT,
104 MachineLoopInfo *Loops)
105 : LV(LV), MDT(MDT), Loops(Loops) {}
106 bool run(MachineFunction &MF);
107
108 MachineBasicBlock *getElseTarget(MachineBasicBlock *MBB) const;
109
110 void collectElseRegionBlocks(MachineBasicBlock *Flow,
111 MachineBasicBlock *Endif,
112 SmallSetVector<MachineBasicBlock *, 16> &) const;
113
114 void
115 collectCandidateRegisters(MachineBasicBlock *If, MachineBasicBlock *Flow,
116 MachineBasicBlock *Endif,
117 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks,
118 SmallVectorImpl<Register> &CandidateRegs) const;
119
120 void collectWaterfallCandidateRegisters(
121 MachineBasicBlock *LoopHeader, MachineBasicBlock *LoopEnd,
122 SmallSetVector<Register, 16> &CandidateRegs,
123 SmallSetVector<MachineBasicBlock *, 2> &Blocks,
124 SmallVectorImpl<MachineInstr *> &Instructions) const;
125
126 void findNonPHIUsesInBlock(Register Reg, MachineBasicBlock *MBB,
127 SmallVectorImpl<MachineInstr *> &Uses) const;
128
129 void updateLiveRangeInThenRegion(Register Reg, MachineBasicBlock *If,
130 MachineBasicBlock *Flow) const;
131
132 void updateLiveRangeInElseRegion(
133 Register Reg, Register NewReg, MachineBasicBlock *Flow,
134 MachineBasicBlock *Endif,
135 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const;
136
137 void
138 optimizeLiveRange(Register Reg, MachineBasicBlock *If,
139 MachineBasicBlock *Flow, MachineBasicBlock *Endif,
140 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const;
141
142 void optimizeWaterfallLiveRange(
143 Register Reg, MachineBasicBlock *LoopHeader,
144 SmallSetVector<MachineBasicBlock *, 2> &LoopBlocks,
145 SmallVectorImpl<MachineInstr *> &Instructions) const;
146};
147
148class SIOptimizeVGPRLiveRangeLegacy : public MachineFunctionPass {
149public:
150 static char ID;
151
152 SIOptimizeVGPRLiveRangeLegacy() : MachineFunctionPass(ID) {}
153
154 bool runOnMachineFunction(MachineFunction &MF) override;
155
156 StringRef getPassName() const override {
157 return "SI Optimize VGPR LiveRange";
158 }
159
160 void getAnalysisUsage(AnalysisUsage &AU) const override {
161 AU.setPreservesCFG();
162 AU.addRequired<LiveVariablesWrapperPass>();
163 AU.addRequired<MachineDominatorTreeWrapperPass>();
164 AU.addRequired<MachineLoopInfoWrapperPass>();
165 AU.addPreserved<LiveVariablesWrapperPass>();
166 MachineFunctionPass::getAnalysisUsage(AU);
167 }
168
169 MachineFunctionProperties getRequiredProperties() const override {
170 return MachineFunctionProperties().setIsSSA();
171 }
172
173 MachineFunctionProperties getClearedProperties() const override {
174 return MachineFunctionProperties().setNoPHIs();
175 }
176};
177
178} // end anonymous namespace
179
180// Check whether the MBB is a else flow block and get the branching target which
181// is the Endif block
182MachineBasicBlock *
183SIOptimizeVGPRLiveRange::getElseTarget(MachineBasicBlock *MBB) const {
184 for (auto &BR : MBB->terminators()) {
185 if (BR.getOpcode() == AMDGPU::SI_ELSE)
186 return BR.getOperand(i: 2).getMBB();
187 }
188 return nullptr;
189}
190
191void SIOptimizeVGPRLiveRange::collectElseRegionBlocks(
192 MachineBasicBlock *Flow, MachineBasicBlock *Endif,
193 SmallSetVector<MachineBasicBlock *, 16> &Blocks) const {
194 assert(Flow != Endif);
195
196 MachineBasicBlock *MBB = Endif;
197 unsigned Cur = 0;
198 while (MBB) {
199 for (auto *Pred : MBB->predecessors()) {
200 if (Pred != Flow)
201 Blocks.insert(X: Pred);
202 }
203
204 if (Cur < Blocks.size())
205 MBB = Blocks[Cur++];
206 else
207 MBB = nullptr;
208 }
209
210 LLVM_DEBUG({
211 dbgs() << "Found Else blocks: ";
212 for (auto *MBB : Blocks)
213 dbgs() << printMBBReference(*MBB) << ' ';
214 dbgs() << '\n';
215 });
216}
217
218/// Find the instructions(excluding phi) in \p MBB that uses the \p Reg.
219void SIOptimizeVGPRLiveRange::findNonPHIUsesInBlock(
220 Register Reg, MachineBasicBlock *MBB,
221 SmallVectorImpl<MachineInstr *> &Uses) const {
222 for (auto &UseMI : MRI->use_nodbg_instructions(Reg)) {
223 if (UseMI.getParent() == MBB && !UseMI.isPHI() &&
224 UseMI.readsVirtualRegister(Reg))
225 Uses.push_back(Elt: &UseMI);
226 }
227}
228
229/// Collect the killed registers in the ELSE region which are not alive through
230/// the whole THEN region.
231void SIOptimizeVGPRLiveRange::collectCandidateRegisters(
232 MachineBasicBlock *If, MachineBasicBlock *Flow, MachineBasicBlock *Endif,
233 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks,
234 SmallVectorImpl<Register> &CandidateRegs) const {
235
236 SmallSet<Register, 8> KillsInElse;
237
238 for (auto *Else : ElseBlocks) {
239 for (auto &MI : Else->instrs()) {
240 if (MI.isDebugInstr())
241 continue;
242
243 for (auto &MO : MI.operands()) {
244 if (!MO.isReg() || !MO.getReg() || MO.isDef())
245 continue;
246
247 Register MOReg = MO.getReg();
248 // We can only optimize AGPR/VGPR virtual register
249 if (MOReg.isPhysical() || !TRI->isVectorRegister(MRI: *MRI, Reg: MOReg))
250 continue;
251
252 if (MO.readsReg()) {
253 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg: MOReg);
254 const MachineBasicBlock *DefMBB = MRI->getDefBlock(Reg: MOReg);
255 // Make sure two conditions are met:
256 // a.) the value is defined before/in the IF block
257 // b.) should be defined in the same loop-level.
258 if ((VI.AliveBlocks.test(Idx: If->getNumber()) || DefMBB == If) &&
259 Loops->getLoopFor(BB: DefMBB) == Loops->getLoopFor(BB: If)) {
260 // Check if the register is live into the endif block. If not,
261 // consider it killed in the else region.
262 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg: MOReg);
263 if (!VI.isLiveIn(MBB: *Endif, Reg: MOReg, MRI&: *MRI)) {
264 KillsInElse.insert(V: MOReg);
265 } else {
266 LLVM_DEBUG(dbgs() << "Excluding " << printReg(MOReg, TRI)
267 << " as Live in Endif\n");
268 }
269 }
270 }
271 }
272 }
273 }
274
275 // Check the phis in the Endif, looking for value coming from the ELSE
276 // region. Make sure the phi-use is the last use.
277 for (auto &MI : Endif->phis()) {
278 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
279 auto &MO = MI.getOperand(i: Idx);
280 auto *Pred = MI.getOperand(i: Idx + 1).getMBB();
281 if (Pred == Flow)
282 continue;
283 assert(ElseBlocks.contains(Pred) && "Should be from Else region\n");
284
285 if (!MO.isReg() || !MO.getReg() || MO.isUndef())
286 continue;
287
288 Register Reg = MO.getReg();
289 if (Reg.isPhysical() || !TRI->isVectorRegister(MRI: *MRI, Reg))
290 continue;
291
292 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg);
293
294 if (VI.isLiveIn(MBB: *Endif, Reg, MRI&: *MRI)) {
295 LLVM_DEBUG(dbgs() << "Excluding " << printReg(Reg, TRI)
296 << " as Live in Endif\n");
297 continue;
298 }
299 // Make sure two conditions are met:
300 // a.) the value is defined before/in the IF block
301 // b.) should be defined in the same loop-level.
302 const MachineBasicBlock *DefMBB = MRI->getDefBlock(Reg);
303 if ((VI.AliveBlocks.test(Idx: If->getNumber()) || DefMBB == If) &&
304 Loops->getLoopFor(BB: DefMBB) == Loops->getLoopFor(BB: If))
305 KillsInElse.insert(V: Reg);
306 }
307 }
308
309 auto IsLiveThroughThen = [&](Register Reg) {
310 for (auto I = MRI->use_nodbg_begin(RegNo: Reg), E = MRI->use_nodbg_end(); I != E;
311 ++I) {
312 if (!I->readsReg())
313 continue;
314 auto *UseMI = I->getParent();
315 auto *UseMBB = UseMI->getParent();
316 if (UseMBB == Flow || UseMBB == Endif) {
317 if (!UseMI->isPHI())
318 return true;
319
320 auto *IncomingMBB = UseMI->getOperand(i: I.getOperandNo() + 1).getMBB();
321 // The register is live through the path If->Flow or Flow->Endif.
322 // we should not optimize for such cases.
323 if ((UseMBB == Flow && IncomingMBB != If) ||
324 (UseMBB == Endif && IncomingMBB == Flow))
325 return true;
326 }
327 }
328 return false;
329 };
330
331 for (auto Reg : KillsInElse) {
332 if (!IsLiveThroughThen(Reg))
333 CandidateRegs.push_back(Elt: Reg);
334 }
335}
336
337/// Collect the registers used in the waterfall loop block that are defined
338/// before.
339void SIOptimizeVGPRLiveRange::collectWaterfallCandidateRegisters(
340 MachineBasicBlock *LoopHeader, MachineBasicBlock *LoopEnd,
341 SmallSetVector<Register, 16> &CandidateRegs,
342 SmallSetVector<MachineBasicBlock *, 2> &Blocks,
343 SmallVectorImpl<MachineInstr *> &Instructions) const {
344
345 // Collect loop instructions, potentially spanning multiple blocks
346 auto *MBB = LoopHeader;
347 for (;;) {
348 Blocks.insert(X: MBB);
349 for (auto &MI : *MBB) {
350 if (MI.isDebugInstr())
351 continue;
352 Instructions.push_back(Elt: &MI);
353 }
354 if (MBB == LoopEnd)
355 break;
356
357 if ((MBB != LoopHeader && MBB->pred_size() != 1) ||
358 (MBB == LoopHeader && MBB->pred_size() != 2) || MBB->succ_size() != 1) {
359 LLVM_DEBUG(dbgs() << "Unexpected edges in CFG, ignoring loop\n");
360 return;
361 }
362
363 MBB = *MBB->succ_begin();
364 }
365
366 for (auto *I : Instructions) {
367 auto &MI = *I;
368
369 for (auto &MO : MI.all_uses()) {
370 if (!MO.getReg())
371 continue;
372
373 Register MOReg = MO.getReg();
374 // We can only optimize AGPR/VGPR virtual register
375 if (MOReg.isPhysical() || !TRI->isVectorRegister(MRI: *MRI, Reg: MOReg))
376 continue;
377
378 if (MO.readsReg()) {
379 MachineBasicBlock *DefMBB = MRI->getDefBlock(Reg: MOReg);
380 // Make sure the value is defined before the LOOP block
381 if (!Blocks.contains(key: DefMBB) && !CandidateRegs.contains(key: MOReg)) {
382 // If the variable is used after the loop, the register coalescer will
383 // merge the newly created register and remove the phi node again.
384 // Just do nothing in that case.
385 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg: MOReg);
386 bool IsUsed = false;
387 for (auto *Succ : LoopEnd->successors()) {
388 if (!Blocks.contains(key: Succ) &&
389 OldVarInfo.isLiveIn(MBB: *Succ, Reg: MOReg, MRI&: *MRI)) {
390 IsUsed = true;
391 break;
392 }
393 }
394 if (!IsUsed) {
395 LLVM_DEBUG(dbgs() << "Found candidate reg: "
396 << printReg(MOReg, TRI, 0, MRI) << '\n');
397 CandidateRegs.insert(X: MOReg);
398 } else {
399 LLVM_DEBUG(dbgs() << "Reg is used after loop, ignoring: "
400 << printReg(MOReg, TRI, 0, MRI) << '\n');
401 }
402 }
403 }
404 }
405 }
406}
407
408// Re-calculate the liveness of \p Reg in the THEN-region
409void SIOptimizeVGPRLiveRange::updateLiveRangeInThenRegion(
410 Register Reg, MachineBasicBlock *If, MachineBasicBlock *Flow) const {
411 SetVector<MachineBasicBlock *> Blocks;
412 SmallVector<MachineBasicBlock *> WorkList({If});
413
414 // Collect all successors until we see the flow block, where we should
415 // reconverge.
416 while (!WorkList.empty()) {
417 auto *MBB = WorkList.pop_back_val();
418 for (auto *Succ : MBB->successors()) {
419 if (Succ != Flow && Blocks.insert(X: Succ))
420 WorkList.push_back(Elt: Succ);
421 }
422 }
423
424 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
425 for (MachineBasicBlock *MBB : Blocks) {
426 // Clear Live bit, as we will recalculate afterwards
427 LLVM_DEBUG(dbgs() << "Clear AliveBlock " << printMBBReference(*MBB)
428 << '\n');
429 OldVarInfo.AliveBlocks.reset(Idx: MBB->getNumber());
430 }
431
432 SmallPtrSet<MachineBasicBlock *, 4> PHIIncoming;
433
434 // Get the blocks the Reg should be alive through
435 for (auto I = MRI->use_nodbg_begin(RegNo: Reg), E = MRI->use_nodbg_end(); I != E;
436 ++I) {
437 auto *UseMI = I->getParent();
438 if (UseMI->isPHI() && I->readsReg()) {
439 if (Blocks.contains(key: UseMI->getParent()))
440 PHIIncoming.insert(Ptr: UseMI->getOperand(i: I.getOperandNo() + 1).getMBB());
441 }
442 }
443
444 for (MachineBasicBlock *MBB : Blocks) {
445 SmallVector<MachineInstr *> Uses;
446 // PHI instructions has been processed before.
447 findNonPHIUsesInBlock(Reg, MBB, Uses);
448
449 if (Uses.size() == 1) {
450 LLVM_DEBUG(dbgs() << "Found one Non-PHI use in "
451 << printMBBReference(*MBB) << '\n');
452 LV->HandleVirtRegUse(reg: Reg, MBB, MI&: *(*Uses.begin()));
453 } else if (Uses.size() > 1) {
454 // Process the instructions in-order
455 LLVM_DEBUG(dbgs() << "Found " << Uses.size() << " Non-PHI uses in "
456 << printMBBReference(*MBB) << '\n');
457 for (MachineInstr &MI : *MBB) {
458 if (llvm::is_contained(Range&: Uses, Element: &MI))
459 LV->HandleVirtRegUse(reg: Reg, MBB, MI);
460 }
461 }
462
463 // Mark Reg alive through the block if this is a PHI incoming block
464 if (PHIIncoming.contains(Ptr: MBB))
465 LV->MarkVirtRegAliveInBlock(VRInfo&: OldVarInfo, DefBlock: MRI->getDefBlock(Reg), BB: MBB);
466 }
467
468 // Set the isKilled flag if we get new Kills in the THEN region.
469 for (auto *MI : OldVarInfo.Kills) {
470 if (Blocks.contains(key: MI->getParent()))
471 MI->addRegisterKilled(IncomingReg: Reg, RegInfo: TRI);
472 }
473}
474
475void SIOptimizeVGPRLiveRange::updateLiveRangeInElseRegion(
476 Register Reg, Register NewReg, MachineBasicBlock *Flow,
477 MachineBasicBlock *Endif,
478 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {
479 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(Reg: NewReg);
480 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
481
482 // Transfer aliveBlocks from Reg to NewReg
483 for (auto *MBB : ElseBlocks) {
484 unsigned BBNum = MBB->getNumber();
485 if (OldVarInfo.AliveBlocks.test(Idx: BBNum)) {
486 NewVarInfo.AliveBlocks.set(BBNum);
487 LLVM_DEBUG(dbgs() << "Removing AliveBlock " << printMBBReference(*MBB)
488 << '\n');
489 OldVarInfo.AliveBlocks.reset(Idx: BBNum);
490 }
491 }
492
493 // Transfer the possible Kills in ElseBlocks from Reg to NewReg
494 llvm::erase_if(C&: OldVarInfo.Kills, P: [&](MachineInstr *MI) {
495 if (!ElseBlocks.contains(key: MI->getParent()))
496 return false;
497 NewVarInfo.Kills.push_back(x: MI);
498 return true;
499 });
500}
501
502void SIOptimizeVGPRLiveRange::optimizeLiveRange(
503 Register Reg, MachineBasicBlock *If, MachineBasicBlock *Flow,
504 MachineBasicBlock *Endif,
505 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {
506 // Insert a new PHI, marking the value from the THEN region being
507 // undef.
508 LLVM_DEBUG(dbgs() << "Optimizing " << printReg(Reg, TRI) << '\n');
509 const auto *RC = MRI->getRegClass(Reg);
510 Register NewReg = MRI->createVirtualRegister(RegClass: RC);
511 Register UndefReg = MRI->createVirtualRegister(RegClass: RC);
512 MachineInstrBuilder PHI = BuildMI(BB&: *Flow, I: Flow->getFirstNonPHI(), MIMD: DebugLoc(),
513 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NewReg);
514 for (auto *Pred : Flow->predecessors()) {
515 if (Pred == If)
516 PHI.addReg(RegNo: Reg).addMBB(MBB: Pred);
517 else
518 PHI.addReg(RegNo: UndefReg, Flags: RegState::Undef).addMBB(MBB: Pred);
519 }
520
521 // Replace all uses in the ELSE region or the PHIs in ENDIF block
522 // Use early increment range because setReg() will update the linked list.
523 for (auto &O : make_early_inc_range(Range: MRI->use_operands(Reg))) {
524 auto *UseMI = O.getParent();
525 auto *UseBlock = UseMI->getParent();
526 // Replace uses in Endif block
527 if (UseBlock == Endif) {
528 if (UseMI->isPHI())
529 O.setReg(NewReg);
530 else if (UseMI->isDebugInstr())
531 continue;
532 else {
533 // DetectDeadLanes may mark register uses as undef without removing
534 // them, in which case a non-phi instruction using the original register
535 // may exist in the Endif block even though the register is not live
536 // into it.
537 assert(!O.readsReg());
538 }
539 continue;
540 }
541
542 // Replace uses in Else region
543 if (ElseBlocks.contains(key: UseBlock))
544 O.setReg(NewReg);
545 }
546
547 // The optimized Reg is not alive through Flow blocks anymore.
548 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
549 OldVarInfo.AliveBlocks.reset(Idx: Flow->getNumber());
550
551 updateLiveRangeInElseRegion(Reg, NewReg, Flow, Endif, ElseBlocks);
552 updateLiveRangeInThenRegion(Reg, If, Flow);
553}
554
555void SIOptimizeVGPRLiveRange::optimizeWaterfallLiveRange(
556 Register Reg, MachineBasicBlock *LoopHeader,
557 SmallSetVector<MachineBasicBlock *, 2> &Blocks,
558 SmallVectorImpl<MachineInstr *> &Instructions) const {
559 // Insert a new PHI, marking the value from the last loop iteration undef.
560 LLVM_DEBUG(dbgs() << "Optimizing " << printReg(Reg, TRI) << '\n');
561 const auto *RC = MRI->getRegClass(Reg);
562 Register NewReg = MRI->createVirtualRegister(RegClass: RC);
563 Register UndefReg = MRI->createVirtualRegister(RegClass: RC);
564
565 // Replace all uses in the LOOP region
566 // Use early increment range because setReg() will update the linked list.
567 for (auto &O : make_early_inc_range(Range: MRI->use_operands(Reg))) {
568 auto *UseMI = O.getParent();
569 auto *UseBlock = UseMI->getParent();
570 // Replace uses in Loop blocks
571 if (Blocks.contains(key: UseBlock))
572 O.setReg(NewReg);
573 }
574
575 MachineInstrBuilder PHI =
576 BuildMI(BB&: *LoopHeader, I: LoopHeader->getFirstNonPHI(), MIMD: DebugLoc(),
577 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NewReg);
578 for (auto *Pred : LoopHeader->predecessors()) {
579 if (Blocks.contains(key: Pred))
580 PHI.addReg(RegNo: UndefReg, Flags: RegState::Undef).addMBB(MBB: Pred);
581 else
582 PHI.addReg(RegNo: Reg).addMBB(MBB: Pred);
583 }
584
585 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(Reg: NewReg);
586 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
587
588 // Find last use and mark as kill
589 MachineInstr *Kill = nullptr;
590 for (auto *MI : reverse(C&: Instructions)) {
591 if (MI->readsRegister(Reg: NewReg, TRI)) {
592 MI->addRegisterKilled(IncomingReg: NewReg, RegInfo: TRI);
593 NewVarInfo.Kills.push_back(x: MI);
594 Kill = MI;
595 break;
596 }
597 }
598 assert(Kill && "Failed to find last usage of register in loop");
599
600 MachineBasicBlock *KillBlock = Kill->getParent();
601 bool PostKillBlock = false;
602 for (auto *Block : Blocks) {
603 auto BBNum = Block->getNumber();
604
605 // collectWaterfallCandidateRegisters only collects registers that are dead
606 // after the loop. So we know that the old reg is no longer live throughout
607 // the waterfall loop.
608 OldVarInfo.AliveBlocks.reset(Idx: BBNum);
609
610 // The new register is live up to (and including) the block that kills it.
611 PostKillBlock |= (Block == KillBlock);
612 if (PostKillBlock) {
613 NewVarInfo.AliveBlocks.reset(Idx: BBNum);
614 } else if (Block != LoopHeader) {
615 NewVarInfo.AliveBlocks.set(BBNum);
616 }
617 }
618}
619
620char SIOptimizeVGPRLiveRangeLegacy::ID = 0;
621
622INITIALIZE_PASS_BEGIN(SIOptimizeVGPRLiveRangeLegacy, DEBUG_TYPE,
623 "SI Optimize VGPR LiveRange", false, false)
624INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
625INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
626INITIALIZE_PASS_DEPENDENCY(LiveVariablesWrapperPass)
627INITIALIZE_PASS_END(SIOptimizeVGPRLiveRangeLegacy, DEBUG_TYPE,
628 "SI Optimize VGPR LiveRange", false, false)
629
630char &llvm::SIOptimizeVGPRLiveRangeLegacyID = SIOptimizeVGPRLiveRangeLegacy::ID;
631
632FunctionPass *llvm::createSIOptimizeVGPRLiveRangeLegacyPass() {
633 return new SIOptimizeVGPRLiveRangeLegacy();
634}
635
636bool SIOptimizeVGPRLiveRangeLegacy::runOnMachineFunction(MachineFunction &MF) {
637 if (skipFunction(F: MF.getFunction()))
638 return false;
639
640 LiveVariables *LV = &getAnalysis<LiveVariablesWrapperPass>().getLV();
641 MachineDominatorTree *MDT =
642 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
643 MachineLoopInfo *Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
644 return SIOptimizeVGPRLiveRange(LV, MDT, Loops).run(MF);
645}
646
647PreservedAnalyses
648SIOptimizeVGPRLiveRangePass::run(MachineFunction &MF,
649 MachineFunctionAnalysisManager &MFAM) {
650 MFPropsModifier _(*this, MF);
651 LiveVariables *LV = &MFAM.getResult<LiveVariablesAnalysis>(IR&: MF);
652 MachineDominatorTree *MDT = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
653 MachineLoopInfo *Loops = &MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
654
655 bool Changed = SIOptimizeVGPRLiveRange(LV, MDT, Loops).run(MF);
656 if (!Changed)
657 return PreservedAnalyses::all();
658
659 auto PA = getMachineFunctionPassPreservedAnalyses();
660 PA.preserve<LiveVariablesAnalysis>();
661 PA.preserveSet<CFGAnalyses>();
662 return PA;
663}
664
665bool SIOptimizeVGPRLiveRange::run(MachineFunction &MF) {
666 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
667 TII = ST.getInstrInfo();
668 TRI = &TII->getRegisterInfo();
669 MRI = &MF.getRegInfo();
670
671 bool MadeChange = false;
672
673 // TODO: we need to think about the order of visiting the blocks to get
674 // optimal result for nesting if-else cases.
675 for (MachineBasicBlock &MBB : MF) {
676 for (auto &MI : MBB.terminators()) {
677 // Detect the if-else blocks
678 if (MI.getOpcode() == AMDGPU::SI_IF) {
679 MachineBasicBlock *IfTarget = MI.getOperand(i: 2).getMBB();
680 auto *Endif = getElseTarget(MBB: IfTarget);
681 if (!Endif)
682 continue;
683
684 // Skip unexpected control flow.
685 if (!MDT->dominates(A: &MBB, B: IfTarget) || !MDT->dominates(A: IfTarget, B: Endif))
686 continue;
687
688 SmallSetVector<MachineBasicBlock *, 16> ElseBlocks;
689 SmallVector<Register> CandidateRegs;
690
691 LLVM_DEBUG(dbgs() << "Checking IF-ELSE-ENDIF: "
692 << printMBBReference(MBB) << ' '
693 << printMBBReference(*IfTarget) << ' '
694 << printMBBReference(*Endif) << '\n');
695
696 // Collect all the blocks in the ELSE region
697 collectElseRegionBlocks(Flow: IfTarget, Endif, Blocks&: ElseBlocks);
698
699 // Collect the registers can be optimized
700 collectCandidateRegisters(If: &MBB, Flow: IfTarget, Endif, ElseBlocks,
701 CandidateRegs);
702 MadeChange |= !CandidateRegs.empty();
703 // Now we are safe to optimize.
704 for (auto Reg : CandidateRegs)
705 optimizeLiveRange(Reg, If: &MBB, Flow: IfTarget, Endif, ElseBlocks);
706 } else if (MI.getOpcode() == AMDGPU::SI_WATERFALL_LOOP) {
707 auto *LoopHeader = MI.getOperand(i: 0).getMBB();
708 auto *LoopEnd = &MBB;
709
710 LLVM_DEBUG(dbgs() << "Checking Waterfall loop: "
711 << printMBBReference(*LoopHeader) << '\n');
712
713 SmallSetVector<Register, 16> CandidateRegs;
714 SmallVector<MachineInstr *, 16> Instructions;
715 SmallSetVector<MachineBasicBlock *, 2> Blocks;
716
717 collectWaterfallCandidateRegisters(LoopHeader, LoopEnd, CandidateRegs,
718 Blocks, Instructions);
719 MadeChange |= !CandidateRegs.empty();
720 // Now we are safe to optimize.
721 for (auto Reg : CandidateRegs)
722 optimizeWaterfallLiveRange(Reg, LoopHeader, Blocks, Instructions);
723 }
724 }
725 }
726
727 return MadeChange;
728}
729