LLVM 17.0.0git
SIOptimizeVGPRLiveRange.cpp
Go to the documentation of this file.
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 "AMDGPU.h"
75#include "GCNSubtarget.h"
83
84using namespace llvm;
85
86#define DEBUG_TYPE "si-opt-vgpr-liverange"
87
88namespace {
89
90class SIOptimizeVGPRLiveRange : public MachineFunctionPass {
91private:
92 const SIRegisterInfo *TRI = nullptr;
93 const SIInstrInfo *TII = nullptr;
94 LiveVariables *LV = nullptr;
95 MachineDominatorTree *MDT = nullptr;
96 const MachineLoopInfo *Loops = nullptr;
97 MachineRegisterInfo *MRI = nullptr;
98
99public:
100 static char ID;
101
102 MachineBasicBlock *getElseTarget(MachineBasicBlock *MBB) const;
103
104 void collectElseRegionBlocks(MachineBasicBlock *Flow,
105 MachineBasicBlock *Endif,
107
108 void
109 collectCandidateRegisters(MachineBasicBlock *If, MachineBasicBlock *Flow,
110 MachineBasicBlock *Endif,
112 SmallVectorImpl<Register> &CandidateRegs) const;
113
114 void collectWaterfallCandidateRegisters(
115 MachineBasicBlock *LoopHeader, MachineBasicBlock *LoopEnd,
116 SmallSetVector<Register, 16> &CandidateRegs,
118 SmallVectorImpl<MachineInstr *> &Instructions) const;
119
120 void findNonPHIUsesInBlock(Register Reg, MachineBasicBlock *MBB,
122
123 void updateLiveRangeInThenRegion(Register Reg, MachineBasicBlock *If,
124 MachineBasicBlock *Flow) const;
125
126 void updateLiveRangeInElseRegion(
128 MachineBasicBlock *Endif,
130
131 void
132 optimizeLiveRange(Register Reg, MachineBasicBlock *If,
135
136 void optimizeWaterfallLiveRange(
137 Register Reg, MachineBasicBlock *LoopHeader,
139 SmallVectorImpl<MachineInstr *> &Instructions) const;
140
141 SIOptimizeVGPRLiveRange() : MachineFunctionPass(ID) {}
142
143 bool runOnMachineFunction(MachineFunction &MF) override;
144
145 StringRef getPassName() const override {
146 return "SI Optimize VGPR LiveRange";
147 }
148
149 void getAnalysisUsage(AnalysisUsage &AU) const override {
157 }
158
161 MachineFunctionProperties::Property::IsSSA);
162 }
163
166 MachineFunctionProperties::Property::NoPHIs);
167 }
168};
169
170} // end anonymous namespace
171
172// Check whether the MBB is a else flow block and get the branching target which
173// is the Endif block
175SIOptimizeVGPRLiveRange::getElseTarget(MachineBasicBlock *MBB) const {
176 for (auto &BR : MBB->terminators()) {
177 if (BR.getOpcode() == AMDGPU::SI_ELSE)
178 return BR.getOperand(2).getMBB();
179 }
180 return nullptr;
181}
182
183void SIOptimizeVGPRLiveRange::collectElseRegionBlocks(
186 assert(Flow != Endif);
187
189 unsigned Cur = 0;
190 while (MBB) {
191 for (auto *Pred : MBB->predecessors()) {
192 if (Pred != Flow && !Blocks.contains(Pred))
193 Blocks.insert(Pred);
194 }
195
196 if (Cur < Blocks.size())
197 MBB = Blocks[Cur++];
198 else
199 MBB = nullptr;
200 }
201
202 LLVM_DEBUG({
203 dbgs() << "Found Else blocks: ";
204 for (auto *MBB : Blocks)
205 dbgs() << printMBBReference(*MBB) << ' ';
206 dbgs() << '\n';
207 });
208}
209
210/// Find the instructions(excluding phi) in \p MBB that uses the \p Reg.
211void SIOptimizeVGPRLiveRange::findNonPHIUsesInBlock(
214 for (auto &UseMI : MRI->use_nodbg_instructions(Reg)) {
215 if (UseMI.getParent() == MBB && !UseMI.isPHI())
216 Uses.push_back(&UseMI);
217 }
218}
219
220/// Collect the killed registers in the ELSE region which are not alive through
221/// the whole THEN region.
222void SIOptimizeVGPRLiveRange::collectCandidateRegisters(
225 SmallVectorImpl<Register> &CandidateRegs) const {
226
227 SmallSet<Register, 8> KillsInElse;
228
229 for (auto *Else : ElseBlocks) {
230 for (auto &MI : Else->instrs()) {
231 if (MI.isDebugInstr())
232 continue;
233
234 for (auto &MO : MI.operands()) {
235 if (!MO.isReg() || !MO.getReg() || MO.isDef())
236 continue;
237
238 Register MOReg = MO.getReg();
239 // We can only optimize AGPR/VGPR virtual register
240 if (MOReg.isPhysical() || !TRI->isVectorRegister(*MRI, MOReg))
241 continue;
242
243 if (MO.readsReg()) {
244 LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg);
245 const MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent();
246 // Make sure two conditions are met:
247 // a.) the value is defined before/in the IF block
248 // b.) should be defined in the same loop-level.
249 if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) &&
250 Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If)) {
251 // Check if the register is live into the endif block. If not,
252 // consider it killed in the else region.
253 LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg);
254 if (!VI.isLiveIn(*Endif, MOReg, *MRI)) {
255 KillsInElse.insert(MOReg);
256 } else {
257 LLVM_DEBUG(dbgs() << "Excluding " << printReg(MOReg, TRI)
258 << " as Live in Endif\n");
259 }
260 }
261 }
262 }
263 }
264 }
265
266 // Check the phis in the Endif, looking for value coming from the ELSE
267 // region. Make sure the phi-use is the last use.
268 for (auto &MI : Endif->phis()) {
269 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
270 auto &MO = MI.getOperand(Idx);
271 auto *Pred = MI.getOperand(Idx + 1).getMBB();
272 if (Pred == Flow)
273 continue;
274 assert(ElseBlocks.contains(Pred) && "Should be from Else region\n");
275
276 if (!MO.isReg() || !MO.getReg() || MO.isUndef())
277 continue;
278
279 Register Reg = MO.getReg();
280 if (Reg.isPhysical() || !TRI->isVectorRegister(*MRI, Reg))
281 continue;
282
283 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg);
284
285 if (VI.isLiveIn(*Endif, Reg, *MRI)) {
286 LLVM_DEBUG(dbgs() << "Excluding " << printReg(Reg, TRI)
287 << " as Live in Endif\n");
288 continue;
289 }
290 // Make sure two conditions are met:
291 // a.) the value is defined before/in the IF block
292 // b.) should be defined in the same loop-level.
293 const MachineBasicBlock *DefMBB = MRI->getVRegDef(Reg)->getParent();
294 if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) &&
295 Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If))
296 KillsInElse.insert(Reg);
297 }
298 }
299
300 auto IsLiveThroughThen = [&](Register Reg) {
301 for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E;
302 ++I) {
303 if (!I->readsReg())
304 continue;
305 auto *UseMI = I->getParent();
306 auto *UseMBB = UseMI->getParent();
307 if (UseMBB == Flow || UseMBB == Endif) {
308 if (!UseMI->isPHI())
309 return true;
310
311 auto *IncomingMBB = UseMI->getOperand(I.getOperandNo() + 1).getMBB();
312 // The register is live through the path If->Flow or Flow->Endif.
313 // we should not optimize for such cases.
314 if ((UseMBB == Flow && IncomingMBB != If) ||
315 (UseMBB == Endif && IncomingMBB == Flow))
316 return true;
317 }
318 }
319 return false;
320 };
321
322 for (auto Reg : KillsInElse) {
323 if (!IsLiveThroughThen(Reg))
324 CandidateRegs.push_back(Reg);
325 }
326}
327
328/// Collect the registers used in the waterfall loop block that are defined
329/// before.
330void SIOptimizeVGPRLiveRange::collectWaterfallCandidateRegisters(
331 MachineBasicBlock *LoopHeader, MachineBasicBlock *LoopEnd,
332 SmallSetVector<Register, 16> &CandidateRegs,
334 SmallVectorImpl<MachineInstr *> &Instructions) const {
335
336 // Collect loop instructions, potentially spanning multiple blocks
337 auto *MBB = LoopHeader;
338 for (;;) {
339 Blocks.insert(MBB);
340 for (auto &MI : *MBB) {
341 if (MI.isDebugInstr())
342 continue;
343 Instructions.push_back(&MI);
344 }
345 if (MBB == LoopEnd)
346 break;
347
348 if ((MBB != LoopHeader && MBB->pred_size() != 1) ||
349 (MBB == LoopHeader && MBB->pred_size() != 2) || MBB->succ_size() != 1) {
350 LLVM_DEBUG(dbgs() << "Unexpected edges in CFG, ignoring loop\n");
351 return;
352 }
353
354 MBB = *MBB->succ_begin();
355 }
356
357 for (auto *I : Instructions) {
358 auto &MI = *I;
359
360 for (auto &MO : MI.operands()) {
361 if (!MO.isReg() || !MO.getReg() || MO.isDef())
362 continue;
363
364 Register MOReg = MO.getReg();
365 // We can only optimize AGPR/VGPR virtual register
366 if (MOReg.isPhysical() || !TRI->isVectorRegister(*MRI, MOReg))
367 continue;
368
369 if (MO.readsReg()) {
370 MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent();
371 // Make sure the value is defined before the LOOP block
372 if (!Blocks.contains(DefMBB) && !CandidateRegs.contains(MOReg)) {
373 // If the variable is used after the loop, the register coalescer will
374 // merge the newly created register and remove the phi node again.
375 // Just do nothing in that case.
376 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(MOReg);
377 bool IsUsed = false;
378 for (auto *Succ : LoopEnd->successors()) {
379 if (!Blocks.contains(Succ) &&
380 OldVarInfo.isLiveIn(*Succ, MOReg, *MRI)) {
381 IsUsed = true;
382 break;
383 }
384 }
385 if (!IsUsed) {
386 LLVM_DEBUG(dbgs() << "Found candidate reg: "
387 << printReg(MOReg, TRI, 0, MRI) << '\n');
388 CandidateRegs.insert(MOReg);
389 } else {
390 LLVM_DEBUG(dbgs() << "Reg is used after loop, ignoring: "
391 << printReg(MOReg, TRI, 0, MRI) << '\n');
392 }
393 }
394 }
395 }
396 }
397}
398
399// Re-calculate the liveness of \p Reg in the THEN-region
400void SIOptimizeVGPRLiveRange::updateLiveRangeInThenRegion(
404
405 // Collect all successors until we see the flow block, where we should
406 // reconverge.
407 while (!WorkList.empty()) {
408 auto *MBB = WorkList.pop_back_val();
409 for (auto *Succ : MBB->successors()) {
410 if (Succ != Flow && !Blocks.contains(Succ)) {
411 WorkList.push_back(Succ);
412 Blocks.insert(Succ);
413 }
414 }
415 }
416
417 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
418 for (MachineBasicBlock *MBB : Blocks) {
419 // Clear Live bit, as we will recalculate afterwards
420 LLVM_DEBUG(dbgs() << "Clear AliveBlock " << printMBBReference(*MBB)
421 << '\n');
422 OldVarInfo.AliveBlocks.reset(MBB->getNumber());
423 }
424
426
427 // Get the blocks the Reg should be alive through
428 for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E;
429 ++I) {
430 auto *UseMI = I->getParent();
431 if (UseMI->isPHI() && I->readsReg()) {
432 if (Blocks.contains(UseMI->getParent()))
433 PHIIncoming.insert(UseMI->getOperand(I.getOperandNo() + 1).getMBB());
434 }
435 }
436
437 for (MachineBasicBlock *MBB : Blocks) {
439 // PHI instructions has been processed before.
440 findNonPHIUsesInBlock(Reg, MBB, Uses);
441
442 if (Uses.size() == 1) {
443 LLVM_DEBUG(dbgs() << "Found one Non-PHI use in "
444 << printMBBReference(*MBB) << '\n');
445 LV->HandleVirtRegUse(Reg, MBB, *(*Uses.begin()));
446 } else if (Uses.size() > 1) {
447 // Process the instructions in-order
448 LLVM_DEBUG(dbgs() << "Found " << Uses.size() << " Non-PHI uses in "
449 << printMBBReference(*MBB) << '\n');
450 for (MachineInstr &MI : *MBB) {
452 LV->HandleVirtRegUse(Reg, MBB, MI);
453 }
454 }
455
456 // Mark Reg alive through the block if this is a PHI incoming block
457 if (PHIIncoming.contains(MBB))
458 LV->MarkVirtRegAliveInBlock(OldVarInfo, MRI->getVRegDef(Reg)->getParent(),
459 MBB);
460 }
461
462 // Set the isKilled flag if we get new Kills in the THEN region.
463 for (auto *MI : OldVarInfo.Kills) {
464 if (Blocks.contains(MI->getParent()))
465 MI->addRegisterKilled(Reg, TRI);
466 }
467}
468
469void SIOptimizeVGPRLiveRange::updateLiveRangeInElseRegion(
471 MachineBasicBlock *Endif,
472 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {
473 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg);
474 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
475
476 // Transfer aliveBlocks from Reg to NewReg
477 for (auto *MBB : ElseBlocks) {
478 unsigned BBNum = MBB->getNumber();
479 if (OldVarInfo.AliveBlocks.test(BBNum)) {
480 NewVarInfo.AliveBlocks.set(BBNum);
481 LLVM_DEBUG(dbgs() << "Removing AliveBlock " << printMBBReference(*MBB)
482 << '\n');
483 OldVarInfo.AliveBlocks.reset(BBNum);
484 }
485 }
486
487 // Transfer the possible Kills in ElseBlocks from Reg to NewReg
488 auto I = OldVarInfo.Kills.begin();
489 while (I != OldVarInfo.Kills.end()) {
490 if (ElseBlocks.contains((*I)->getParent())) {
491 NewVarInfo.Kills.push_back(*I);
492 I = OldVarInfo.Kills.erase(I);
493 } else {
494 ++I;
495 }
496 }
497}
498
499void SIOptimizeVGPRLiveRange::optimizeLiveRange(
501 MachineBasicBlock *Endif,
502 SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {
503 // Insert a new PHI, marking the value from the THEN region being
504 // undef.
505 LLVM_DEBUG(dbgs() << "Optimizing " << printReg(Reg, TRI) << '\n');
506 const auto *RC = MRI->getRegClass(Reg);
507 Register NewReg = MRI->createVirtualRegister(RC);
508 Register UndefReg = MRI->createVirtualRegister(RC);
509 MachineInstrBuilder PHI = BuildMI(*Flow, Flow->getFirstNonPHI(), DebugLoc(),
510 TII->get(TargetOpcode::PHI), NewReg);
511 for (auto *Pred : Flow->predecessors()) {
512 if (Pred == If)
513 PHI.addReg(Reg).addMBB(Pred);
514 else
515 PHI.addReg(UndefReg, RegState::Undef).addMBB(Pred);
516 }
517
518 // Replace all uses in the ELSE region or the PHIs in ENDIF block
519 // Use early increment range because setReg() will update the linked list.
520 for (auto &O : make_early_inc_range(MRI->use_operands(Reg))) {
521 auto *UseMI = O.getParent();
522 auto *UseBlock = UseMI->getParent();
523 // Replace uses in Endif block
524 if (UseBlock == Endif) {
525 assert(UseMI->isPHI() && "Uses should be PHI in Endif block");
526 O.setReg(NewReg);
527 continue;
528 }
529
530 // Replace uses in Else region
531 if (ElseBlocks.contains(UseBlock))
532 O.setReg(NewReg);
533 }
534
535 // The optimized Reg is not alive through Flow blocks anymore.
536 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
537 OldVarInfo.AliveBlocks.reset(Flow->getNumber());
538
539 updateLiveRangeInElseRegion(Reg, NewReg, Flow, Endif, ElseBlocks);
540 updateLiveRangeInThenRegion(Reg, If, Flow);
541}
542
543void SIOptimizeVGPRLiveRange::optimizeWaterfallLiveRange(
544 Register Reg, MachineBasicBlock *LoopHeader,
546 SmallVectorImpl<MachineInstr *> &Instructions) const {
547 // Insert a new PHI, marking the value from the last loop iteration undef.
548 LLVM_DEBUG(dbgs() << "Optimizing " << printReg(Reg, TRI) << '\n');
549 const auto *RC = MRI->getRegClass(Reg);
550 Register NewReg = MRI->createVirtualRegister(RC);
551 Register UndefReg = MRI->createVirtualRegister(RC);
552
553 // Replace all uses in the LOOP region
554 // Use early increment range because setReg() will update the linked list.
555 for (auto &O : make_early_inc_range(MRI->use_operands(Reg))) {
556 auto *UseMI = O.getParent();
557 auto *UseBlock = UseMI->getParent();
558 // Replace uses in Loop blocks
559 if (Blocks.contains(UseBlock))
560 O.setReg(NewReg);
561 }
562
564 BuildMI(*LoopHeader, LoopHeader->getFirstNonPHI(), DebugLoc(),
565 TII->get(TargetOpcode::PHI), NewReg);
566 for (auto *Pred : LoopHeader->predecessors()) {
567 if (Blocks.contains(Pred))
568 PHI.addReg(UndefReg, RegState::Undef).addMBB(Pred);
569 else
570 PHI.addReg(Reg).addMBB(Pred);
571 }
572
573 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg);
574 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
575
576 // Find last use and mark as kill
577 MachineInstr *Kill = nullptr;
578 for (auto *MI : reverse(Instructions)) {
579 if (MI->readsRegister(NewReg, TRI)) {
580 MI->addRegisterKilled(NewReg, TRI);
581 NewVarInfo.Kills.push_back(MI);
582 Kill = MI;
583 break;
584 }
585 }
586 assert(Kill && "Failed to find last usage of register in loop");
587
588 MachineBasicBlock *KillBlock = Kill->getParent();
589 bool PostKillBlock = false;
590 for (auto *Block : Blocks) {
591 auto BBNum = Block->getNumber();
592
593 // collectWaterfallCandidateRegisters only collects registers that are dead
594 // after the loop. So we know that the old reg is no longer live throughout
595 // the waterfall loop.
596 OldVarInfo.AliveBlocks.reset(BBNum);
597
598 // The new register is live up to (and including) the block that kills it.
599 PostKillBlock |= (Block == KillBlock);
600 if (PostKillBlock) {
601 NewVarInfo.AliveBlocks.reset(BBNum);
602 } else if (Block != LoopHeader) {
603 NewVarInfo.AliveBlocks.set(BBNum);
604 }
605 }
606}
607
608char SIOptimizeVGPRLiveRange::ID = 0;
609
610INITIALIZE_PASS_BEGIN(SIOptimizeVGPRLiveRange, DEBUG_TYPE,
611 "SI Optimize VGPR LiveRange", false, false)
615INITIALIZE_PASS_END(SIOptimizeVGPRLiveRange, DEBUG_TYPE,
616 "SI Optimize VGPR LiveRange", false, false)
617
618char &llvm::SIOptimizeVGPRLiveRangeID = SIOptimizeVGPRLiveRange::ID;
619
621 return new SIOptimizeVGPRLiveRange();
622}
623
624bool SIOptimizeVGPRLiveRange::runOnMachineFunction(MachineFunction &MF) {
625
626 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
627 TII = ST.getInstrInfo();
628 TRI = &TII->getRegisterInfo();
629 MDT = &getAnalysis<MachineDominatorTree>();
630 Loops = &getAnalysis<MachineLoopInfo>();
631 LV = &getAnalysis<LiveVariables>();
632 MRI = &MF.getRegInfo();
633
634 if (skipFunction(MF.getFunction()))
635 return false;
636
637 bool MadeChange = false;
638
639 // TODO: we need to think about the order of visiting the blocks to get
640 // optimal result for nesting if-else cases.
641 for (MachineBasicBlock &MBB : MF) {
642 for (auto &MI : MBB.terminators()) {
643 // Detect the if-else blocks
644 if (MI.getOpcode() == AMDGPU::SI_IF) {
645 MachineBasicBlock *IfTarget = MI.getOperand(2).getMBB();
646 auto *Endif = getElseTarget(IfTarget);
647 if (!Endif)
648 continue;
649
650 // Skip unexpected control flow.
651 if (!MDT->dominates(&MBB, IfTarget) || !MDT->dominates(IfTarget, Endif))
652 continue;
653
655 SmallVector<Register> CandidateRegs;
656
657 LLVM_DEBUG(dbgs() << "Checking IF-ELSE-ENDIF: "
658 << printMBBReference(MBB) << ' '
659 << printMBBReference(*IfTarget) << ' '
660 << printMBBReference(*Endif) << '\n');
661
662 // Collect all the blocks in the ELSE region
663 collectElseRegionBlocks(IfTarget, Endif, ElseBlocks);
664
665 // Collect the registers can be optimized
666 collectCandidateRegisters(&MBB, IfTarget, Endif, ElseBlocks,
667 CandidateRegs);
668 MadeChange |= !CandidateRegs.empty();
669 // Now we are safe to optimize.
670 for (auto Reg : CandidateRegs)
671 optimizeLiveRange(Reg, &MBB, IfTarget, Endif, ElseBlocks);
672 } else if (MI.getOpcode() == AMDGPU::SI_WATERFALL_LOOP) {
673 auto *LoopHeader = MI.getOperand(0).getMBB();
674 auto *LoopEnd = &MBB;
675
676 LLVM_DEBUG(dbgs() << "Checking Waterfall loop: "
677 << printMBBReference(*LoopHeader) << '\n');
678
679 SmallSetVector<Register, 16> CandidateRegs;
682
683 collectWaterfallCandidateRegisters(LoopHeader, LoopEnd, CandidateRegs,
684 Blocks, Instructions);
685 MadeChange |= !CandidateRegs.empty();
686 // Now we are safe to optimize.
687 for (auto Reg : CandidateRegs)
688 optimizeWaterfallLiveRange(Reg, LoopHeader, Blocks, Instructions);
689 }
690 }
691 }
692
693 return MadeChange;
694}
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineBasicBlock & MBB
Provides AMDGPU specific target descriptions.
Rewrite undef for PHI
SmallPtrSet< MachineInstr *, 2 > Uses
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
AMD GCN specific subclass of TargetSubtarget.
const HexagonInstrInfo * TII
Hexagon Hardware Loops
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
Annotate SI Control Flow
@ VI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define DEBUG_TYPE
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
A debug info location.
Definition: DebugLoc.h:33
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
unsigned pred_size() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void push_back(MachineInstr *MI)
unsigned succ_size() const
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
iterator_range< iterator > terminators()
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual MachineFunctionProperties getClearedProperties() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:68
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
MachineBasicBlock * getMBB() const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
A vector that has set insertion semantics.
Definition: SetVector.h:40
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:202
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:177
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
void set(unsigned Idx)
bool test(unsigned Idx) const
void reset(unsigned Idx)
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ BR
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:994
@ Kill
The last use of a register.
@ Undef
Value of the register doesn't matter.
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:732
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:495
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
char & SIOptimizeVGPRLiveRangeID
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1939
FunctionPass * createSIOptimizeVGPRLiveRangePass()
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:80
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:90
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:85
bool isLiveIn(const MachineBasicBlock &MBB, Register Reg, MachineRegisterInfo &MRI)
isLiveIn - Is Reg live in to MBB? This means that Reg is live through MBB, or it is killed in MBB.