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