LLVM  15.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 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"
77 #include "SIMachineFunctionInfo.h"
82 #include "llvm/InitializePasses.h"
83 
84 using namespace llvm;
85 
86 #define DEBUG_TYPE "si-opt-vgpr-liverange"
87 
88 namespace {
89 
90 class SIOptimizeVGPRLiveRange : public MachineFunctionPass {
91 private:
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 
99 public:
100  static char ID;
101 
102  MachineBasicBlock *getElseTarget(MachineBasicBlock *MBB) const;
103 
104  void collectElseRegionBlocks(MachineBasicBlock *Flow,
107 
108  void
109  collectCandidateRegisters(MachineBasicBlock *If, MachineBasicBlock *Flow,
112  SmallVectorImpl<Register> &CandidateRegs) const;
113 
114  void collectWaterfallCandidateRegisters(
115  MachineBasicBlock *LoopHeader, MachineBasicBlock *LoopEnd,
116  SmallSetVector<Register, 16> &CandidateRegs,
119 
120  void findNonPHIUsesInBlock(Register Reg, MachineBasicBlock *MBB,
122 
123  void updateLiveRangeInThenRegion(Register Reg, MachineBasicBlock *If,
124  MachineBasicBlock *Flow) const;
125 
126  void updateLiveRangeInElseRegion(
129  SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const;
130 
131  void
132  optimizeLiveRange(Register Reg, MachineBasicBlock *If,
134  SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const;
135 
136  void optimizeWaterfallLiveRange(
137  Register Reg, MachineBasicBlock *LoopHeader,
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 
159  MachineFunctionProperties getRequiredProperties() const override {
162  }
163 
164  MachineFunctionProperties getClearedProperties() const override {
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
175 SIOptimizeVGPRLiveRange::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 
183 void 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.
211 void 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.
222 void 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.
330 void SIOptimizeVGPRLiveRange::collectWaterfallCandidateRegisters(
331  MachineBasicBlock *LoopHeader, MachineBasicBlock *LoopEnd,
332  SmallSetVector<Register, 16> &CandidateRegs,
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
400 void 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) {
451  if (llvm::is_contained(Uses, &MI))
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 
469 void SIOptimizeVGPRLiveRange::updateLiveRangeInElseRegion(
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 
499 void SIOptimizeVGPRLiveRange::optimizeLiveRange(
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 
543 void SIOptimizeVGPRLiveRange::optimizeWaterfallLiveRange(
544  Register Reg, MachineBasicBlock *LoopHeader,
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 
563  MachineInstrBuilder PHI =
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 
609 
610 INITIALIZE_PASS_BEGIN(SIOptimizeVGPRLiveRange, DEBUG_TYPE,
611  "SI Optimize VGPR LiveRange", false, false)
615 INITIALIZE_PASS_END(SIOptimizeVGPRLiveRange, DEBUG_TYPE,
616  "SI Optimize VGPR LiveRange", false, false)
617 
618 char &llvm::SIOptimizeVGPRLiveRangeID = SIOptimizeVGPRLiveRange::ID;
619 
621  return new SIOptimizeVGPRLiveRange();
622 }
623 
624 bool 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 }
llvm::LiveVariables::VarInfo::isLiveIn
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.
Definition: LiveVariables.cpp:791
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:354
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:103
llvm::MachineRegisterInfo::createVirtualRegister
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
Definition: MachineRegisterInfo.cpp:156
SIMachineFunctionInfo.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::LiveVariables::VarInfo::Kills
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
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:116
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:551
llvm::SparseBitVector::reset
void reset(unsigned Idx)
Definition: SparseBitVector.h:487
Instructions
Code Generation Notes for reduce the size of the ISel and reduce repetition in the implementation In a small number of this can cause even when no optimisation has taken place Instructions
Definition: MSA.txt:11
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::SIOptimizeVGPRLiveRangeID
char & SIOptimizeVGPRLiveRangeID
Definition: SIOptimizeVGPRLiveRange.cpp:618
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:477
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::MachineFunctionProperties::Property::IsSSA
@ IsSSA
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:127
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::GCNSubtarget
Definition: GCNSubtarget.h:31
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:298
llvm::tgtok::Else
@ Else
Definition: TGLexer.h:76
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
llvm::MachineRegisterInfo::use_nodbg_begin
use_nodbg_iterator use_nodbg_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:526
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:585
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineBasicBlock::push_back
void push_back(MachineInstr *MI)
Definition: MachineBasicBlock.h:875
llvm::Register::isPhysical
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:338
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:666
MachineLoopInfo.h
llvm::MachineInstrBuilder::addMBB
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:146
llvm::LiveVariables::VarInfo
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:80
GCNSubtarget.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:501
llvm::createSIOptimizeVGPRLiveRangePass
FunctionPass * createSIOptimizeVGPRLiveRangePass()
Definition: SIOptimizeVGPRLiveRange.cpp:620
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
LiveVariables.h
false
Definition: StackSlotColoring.cpp:141
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:196
llvm::MachineRegisterInfo::use_nodbg_end
static use_nodbg_iterator use_nodbg_end()
Definition: MachineRegisterInfo.h:529
llvm::tgtok::If
@ If
Definition: TGLexer.h:51
llvm::SIRegisterInfo
Definition: SIRegisterInfo.h:30
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:396
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:642
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:656
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
DEBUG_TYPE
#define DEBUG_TYPE
Definition: SIOptimizeVGPRLiveRange.cpp:86
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::contains
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:209
VI
@ VI
Definition: SIInstrInfo.cpp:7824
AMDGPUMCTargetDesc.h
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:508
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::SparseBitVector::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:472
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::make_early_inc_range
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:618
llvm::MachineBasicBlock::getFirstNonPHI
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: MachineBasicBlock.cpp:196
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1682
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::succ_begin
succ_iterator succ_begin()
Definition: MachineBasicBlock.h:342
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1256
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:359
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:561
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1088
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:365
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
AMDGPU.h
llvm::tgtok::Endif
@ Endif
Definition: TGLexer.h:76
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:288
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(SIOptimizeVGPRLiveRange, DEBUG_TYPE, "SI Optimize VGPR LiveRange", false, false) INITIALIZE_PASS_END(SIOptimizeVGPRLiveRange
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:622
llvm::MachineFunctionProperties::Property::NoPHIs
@ NoPHIs
llvm::ISD::BR
@ BR
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:982
llvm::SIInstrInfo
Definition: SIInstrInfo.h:44
Flow
Annotate SI Control Flow
Definition: SIAnnotateControlFlow.cpp:118
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::LiveVariables
Definition: LiveVariables.h:47
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:111
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::pdb::PDB_SymType::Block
@ Block
InitializePasses.h
TargetRegisterInfo.h
MachineDominators.h
llvm::SmallPtrSetImpl::insert
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::LiveVariables::VarInfo::AliveBlocks
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:85
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52