LLVM  14.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 /// sucessive 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(
116  SmallSetVector<Register, 16> &CandidateRegs) const;
117 
118  void findNonPHIUsesInBlock(Register Reg, MachineBasicBlock *MBB,
120 
121  void updateLiveRangeInThenRegion(Register Reg, MachineBasicBlock *If,
122  MachineBasicBlock *Flow) const;
123 
124  void updateLiveRangeInElseRegion(
127  SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const;
128 
129  void
130  optimizeLiveRange(Register Reg, MachineBasicBlock *If,
132  SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const;
133 
134  void optimizeWaterfallLiveRange(Register Reg, MachineBasicBlock *If) const;
135 
136  SIOptimizeVGPRLiveRange() : MachineFunctionPass(ID) {}
137 
138  bool runOnMachineFunction(MachineFunction &MF) override;
139 
140  StringRef getPassName() const override {
141  return "SI Optimize VGPR LiveRange";
142  }
143 
144  void getAnalysisUsage(AnalysisUsage &AU) const override {
152  }
153 
154  MachineFunctionProperties getRequiredProperties() const override {
157  }
158 };
159 
160 } // end anonymous namespace
161 
162 // Check whether the MBB is a else flow block and get the branching target which
163 // is the Endif block
165 SIOptimizeVGPRLiveRange::getElseTarget(MachineBasicBlock *MBB) const {
166  for (auto &BR : MBB->terminators()) {
167  if (BR.getOpcode() == AMDGPU::SI_ELSE)
168  return BR.getOperand(2).getMBB();
169  }
170  return nullptr;
171 }
172 
173 void SIOptimizeVGPRLiveRange::collectElseRegionBlocks(
176  assert(Flow != Endif);
177 
179  unsigned Cur = 0;
180  while (MBB) {
181  for (auto *Pred : MBB->predecessors()) {
182  if (Pred != Flow && !Blocks.contains(Pred))
183  Blocks.insert(Pred);
184  }
185 
186  if (Cur < Blocks.size())
187  MBB = Blocks[Cur++];
188  else
189  MBB = nullptr;
190  }
191 
192  LLVM_DEBUG({
193  dbgs() << "Found Else blocks: ";
194  for (auto *MBB : Blocks)
195  dbgs() << printMBBReference(*MBB) << ' ';
196  dbgs() << '\n';
197  });
198 }
199 
200 /// Find the instructions(excluding phi) in \p MBB that uses the \p Reg.
201 void SIOptimizeVGPRLiveRange::findNonPHIUsesInBlock(
204  for (auto &UseMI : MRI->use_nodbg_instructions(Reg)) {
205  if (UseMI.getParent() == MBB && !UseMI.isPHI())
206  Uses.push_back(&UseMI);
207  }
208 }
209 
210 /// Collect the killed registers in the ELSE region which are not alive through
211 /// the whole THEN region.
212 void SIOptimizeVGPRLiveRange::collectCandidateRegisters(
215  SmallVectorImpl<Register> &CandidateRegs) const {
216 
217  SmallSet<Register, 8> KillsInElse;
218 
219  for (auto *Else : ElseBlocks) {
220  for (auto &MI : Else->instrs()) {
221  if (MI.isDebugInstr())
222  continue;
223 
224  for (auto &MO : MI.operands()) {
225  if (!MO.isReg() || !MO.getReg() || MO.isDef())
226  continue;
227 
228  Register MOReg = MO.getReg();
229  // We can only optimize AGPR/VGPR virtual register
230  if (MOReg.isPhysical() || !TRI->isVectorRegister(*MRI, MOReg))
231  continue;
232 
233  if (MO.readsReg()) {
234  LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg);
235  const MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent();
236  // Make sure two conditions are met:
237  // a.) the value is defined before/in the IF block
238  // b.) should be defined in the same loop-level.
239  if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) &&
240  Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If)) {
241  // Check if the register is live into the endif block. If not,
242  // consider it killed in the else region.
243  LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg);
244  if (!VI.isLiveIn(*Endif, MOReg, *MRI)) {
245  KillsInElse.insert(MOReg);
246  } else {
247  LLVM_DEBUG(dbgs() << "Excluding " << printReg(MOReg, TRI)
248  << " as Live in Endif\n");
249  }
250  }
251  }
252  }
253  }
254  }
255 
256  // Check the phis in the Endif, looking for value coming from the ELSE
257  // region. Make sure the phi-use is the last use.
258  for (auto &MI : Endif->phis()) {
259  for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
260  auto &MO = MI.getOperand(Idx);
261  auto *Pred = MI.getOperand(Idx + 1).getMBB();
262  if (Pred == Flow)
263  continue;
264  assert(ElseBlocks.contains(Pred) && "Should be from Else region\n");
265 
266  if (!MO.isReg() || !MO.getReg() || MO.isUndef())
267  continue;
268 
269  Register Reg = MO.getReg();
270  if (Reg.isPhysical() || !TRI->isVectorRegister(*MRI, Reg))
271  continue;
272 
273  LiveVariables::VarInfo &VI = LV->getVarInfo(Reg);
274 
275  if (VI.isLiveIn(*Endif, Reg, *MRI)) {
276  LLVM_DEBUG(dbgs() << "Excluding " << printReg(Reg, TRI)
277  << " as Live in Endif\n");
278  continue;
279  }
280  // Make sure two conditions are met:
281  // a.) the value is defined before/in the IF block
282  // b.) should be defined in the same loop-level.
283  const MachineBasicBlock *DefMBB = MRI->getVRegDef(Reg)->getParent();
284  if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) &&
285  Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If))
286  KillsInElse.insert(Reg);
287  }
288  }
289 
290  auto IsLiveThroughThen = [&](Register Reg) {
291  for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E;
292  ++I) {
293  if (!I->readsReg())
294  continue;
295  auto *UseMI = I->getParent();
296  auto *UseMBB = UseMI->getParent();
297  if (UseMBB == Flow || UseMBB == Endif) {
298  if (!UseMI->isPHI())
299  return true;
300 
301  auto *IncomingMBB = UseMI->getOperand(I.getOperandNo() + 1).getMBB();
302  // The register is live through the path If->Flow or Flow->Endif.
303  // we should not optimize for such cases.
304  if ((UseMBB == Flow && IncomingMBB != If) ||
305  (UseMBB == Endif && IncomingMBB == Flow))
306  return true;
307  }
308  }
309  return false;
310  };
311 
312  for (auto Reg : KillsInElse) {
313  if (!IsLiveThroughThen(Reg))
314  CandidateRegs.push_back(Reg);
315  }
316 }
317 
318 /// Collect the registers used in the waterfall loop block that are defined
319 /// before.
320 void SIOptimizeVGPRLiveRange::collectWaterfallCandidateRegisters(
322  SmallSetVector<Register, 16> &CandidateRegs) const {
323 
324  for (auto &MI : Loop->instrs()) {
325  if (MI.isDebugInstr())
326  continue;
327 
328  for (auto &MO : MI.operands()) {
329  if (!MO.isReg() || !MO.getReg() || MO.isDef())
330  continue;
331 
332  Register MOReg = MO.getReg();
333  // We can only optimize AGPR/VGPR virtual register
334  if (MOReg.isPhysical() || !TRI->isVectorRegister(*MRI, MOReg))
335  continue;
336 
337  if (MO.readsReg()) {
338  const MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent();
339  // Make sure the value is defined before the LOOP block
340  if (DefMBB != Loop && !CandidateRegs.contains(MOReg)) {
341  // If the variable is used after the loop, the register coalescer will
342  // merge the newly created register and remove the phi node again.
343  // Just do nothing in that case.
344  LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(MOReg);
345  bool IsUsed = false;
346  for (auto *Succ : Loop->successors()) {
347  if (Succ != Loop && OldVarInfo.isLiveIn(*Succ, MOReg, *MRI)) {
348  IsUsed = true;
349  break;
350  }
351  }
352  if (!IsUsed) {
353  LLVM_DEBUG(dbgs() << "Found candidate reg: "
354  << printReg(MOReg, TRI, 0, MRI) << '\n');
355  CandidateRegs.insert(MOReg);
356  } else {
357  LLVM_DEBUG(dbgs() << "Reg is used after loop, ignoring: "
358  << printReg(MOReg, TRI, 0, MRI) << '\n');
359  }
360  }
361  }
362  }
363  }
364 }
365 
366 // Re-calculate the liveness of \p Reg in the THEN-region
367 void SIOptimizeVGPRLiveRange::updateLiveRangeInThenRegion(
369 
371 
372  MachineBasicBlock *ThenEntry = nullptr;
373  for (auto *Succ : If->successors()) {
374  if (Succ != Flow) {
375  ThenEntry = Succ;
376  break;
377  }
378  }
379  assert(ThenEntry && "No successor in Then region?");
380 
381  LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
383 
384  for (MachineBasicBlock *MBB : depth_first_ext(ThenEntry, Visited)) {
385  if (MBB == Flow)
386  break;
387 
388  // Clear Live bit, as we will recalculate afterwards
389  LLVM_DEBUG(dbgs() << "Clear AliveBlock " << printMBBReference(*MBB)
390  << '\n');
391  OldVarInfo.AliveBlocks.reset(MBB->getNumber());
392  }
393 
394  // Get the blocks the Reg should be alive through
395  for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E;
396  ++I) {
397  auto *UseMI = I->getParent();
398  if (UseMI->isPHI() && I->readsReg()) {
399  if (Visited.contains(UseMI->getParent()))
400  PHIIncoming.insert(UseMI->getOperand(I.getOperandNo() + 1).getMBB());
401  }
402  }
403 
404  Visited.clear();
405 
406  for (MachineBasicBlock *MBB : depth_first_ext(ThenEntry, Visited)) {
407  if (MBB == Flow)
408  break;
409 
411  // PHI instructions has been processed before.
412  findNonPHIUsesInBlock(Reg, MBB, Uses);
413 
414  if (Uses.size() == 1) {
415  LLVM_DEBUG(dbgs() << "Found one Non-PHI use in "
416  << printMBBReference(*MBB) << '\n');
417  LV->HandleVirtRegUse(Reg, MBB, *(*Uses.begin()));
418  } else if (Uses.size() > 1) {
419  // Process the instructions in-order
420  LLVM_DEBUG(dbgs() << "Found " << Uses.size() << " Non-PHI uses in "
421  << printMBBReference(*MBB) << '\n');
422  for (MachineInstr &MI : *MBB) {
423  if (llvm::is_contained(Uses, &MI))
424  LV->HandleVirtRegUse(Reg, MBB, MI);
425  }
426  }
427 
428  // Mark Reg alive through the block if this is a PHI incoming block
429  if (PHIIncoming.contains(MBB))
430  LV->MarkVirtRegAliveInBlock(OldVarInfo, MRI->getVRegDef(Reg)->getParent(),
431  MBB);
432  }
433 
434  // Set the isKilled flag if we get new Kills in the THEN region.
435  for (auto *MI : OldVarInfo.Kills) {
436  if (Visited.contains(MI->getParent()))
437  MI->addRegisterKilled(Reg, TRI);
438  }
439 }
440 
441 void SIOptimizeVGPRLiveRange::updateLiveRangeInElseRegion(
444  SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {
445  LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg);
446  LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
447 
448  // Transfer aliveBlocks from Reg to NewReg
449  for (auto *MBB : ElseBlocks) {
450  unsigned BBNum = MBB->getNumber();
451  if (OldVarInfo.AliveBlocks.test(BBNum)) {
452  NewVarInfo.AliveBlocks.set(BBNum);
453  LLVM_DEBUG(dbgs() << "Removing AliveBlock " << printMBBReference(*MBB)
454  << '\n');
455  OldVarInfo.AliveBlocks.reset(BBNum);
456  }
457  }
458 
459  // Transfer the possible Kills in ElseBlocks from Reg to NewReg
460  auto I = OldVarInfo.Kills.begin();
461  while (I != OldVarInfo.Kills.end()) {
462  if (ElseBlocks.contains((*I)->getParent())) {
463  NewVarInfo.Kills.push_back(*I);
464  I = OldVarInfo.Kills.erase(I);
465  } else {
466  ++I;
467  }
468  }
469 }
470 
471 void SIOptimizeVGPRLiveRange::optimizeLiveRange(
474  SmallSetVector<MachineBasicBlock *, 16> &ElseBlocks) const {
475  // Insert a new PHI, marking the value from the THEN region being
476  // undef.
477  LLVM_DEBUG(dbgs() << "Optimizing " << printReg(Reg, TRI) << '\n');
478  const auto *RC = MRI->getRegClass(Reg);
479  Register NewReg = MRI->createVirtualRegister(RC);
480  Register UndefReg = MRI->createVirtualRegister(RC);
481  MachineInstrBuilder PHI = BuildMI(*Flow, Flow->getFirstNonPHI(), DebugLoc(),
482  TII->get(TargetOpcode::PHI), NewReg);
483  for (auto *Pred : Flow->predecessors()) {
484  if (Pred == If)
485  PHI.addReg(Reg).addMBB(Pred);
486  else
487  PHI.addReg(UndefReg, RegState::Undef).addMBB(Pred);
488  }
489 
490  // Replace all uses in the ELSE region or the PHIs in ENDIF block
491  // Use early increment range because setReg() will update the linked list.
492  for (auto &O : make_early_inc_range(MRI->use_operands(Reg))) {
493  auto *UseMI = O.getParent();
494  auto *UseBlock = UseMI->getParent();
495  // Replace uses in Endif block
496  if (UseBlock == Endif) {
497  assert(UseMI->isPHI() && "Uses should be PHI in Endif block");
498  O.setReg(NewReg);
499  continue;
500  }
501 
502  // Replace uses in Else region
503  if (ElseBlocks.contains(UseBlock))
504  O.setReg(NewReg);
505  }
506 
507  // The optimized Reg is not alive through Flow blocks anymore.
508  LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
509  OldVarInfo.AliveBlocks.reset(Flow->getNumber());
510 
511  updateLiveRangeInElseRegion(Reg, NewReg, Flow, Endif, ElseBlocks);
512  updateLiveRangeInThenRegion(Reg, If, Flow);
513 }
514 
515 void SIOptimizeVGPRLiveRange::optimizeWaterfallLiveRange(
517  // Insert a new PHI, marking the value from the last loop iteration undef.
518  LLVM_DEBUG(dbgs() << "Optimizing " << printReg(Reg, TRI) << '\n');
519  const auto *RC = MRI->getRegClass(Reg);
520  Register NewReg = MRI->createVirtualRegister(RC);
521  Register UndefReg = MRI->createVirtualRegister(RC);
522 
523  // Replace all uses in the LOOP region
524  // Use early increment range because setReg() will update the linked list.
525  for (auto &O : make_early_inc_range(MRI->use_operands(Reg))) {
526  auto *UseMI = O.getParent();
527  auto *UseBlock = UseMI->getParent();
528  // Replace uses in Loop block
529  if (UseBlock == Loop)
530  O.setReg(NewReg);
531  }
532 
533  MachineInstrBuilder PHI = BuildMI(*Loop, Loop->getFirstNonPHI(), DebugLoc(),
534  TII->get(TargetOpcode::PHI), NewReg);
535  for (auto *Pred : Loop->predecessors()) {
536  if (Pred == Loop)
537  PHI.addReg(UndefReg, RegState::Undef).addMBB(Pred);
538  else
539  PHI.addReg(Reg).addMBB(Pred);
540  }
541 
542  LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg);
543  LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg);
544 
545  // collectWaterfallCandidateRegisters only collects registers that are dead
546  // after the loop. So we know that the old reg is not live throughout the
547  // whole block anymore.
548  OldVarInfo.AliveBlocks.reset(Loop->getNumber());
549 
550  // Mark the last use as kill
551  for (auto &MI : reverse(Loop->instrs())) {
552  if (MI.readsRegister(NewReg, TRI)) {
553  MI.addRegisterKilled(NewReg, TRI);
554  NewVarInfo.Kills.push_back(&MI);
555  break;
556  }
557  }
558  assert(!NewVarInfo.Kills.empty() &&
559  "Failed to find last usage of register in loop");
560 }
561 
563 
564 INITIALIZE_PASS_BEGIN(SIOptimizeVGPRLiveRange, DEBUG_TYPE,
565  "SI Optimize VGPR LiveRange", false, false)
569 INITIALIZE_PASS_END(SIOptimizeVGPRLiveRange, DEBUG_TYPE,
570  "SI Optimize VGPR LiveRange", false, false)
571 
572 char &llvm::SIOptimizeVGPRLiveRangeID = SIOptimizeVGPRLiveRange::ID;
573 
575  return new SIOptimizeVGPRLiveRange();
576 }
577 
578 bool SIOptimizeVGPRLiveRange::runOnMachineFunction(MachineFunction &MF) {
579 
580  const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
581  TII = ST.getInstrInfo();
582  TRI = &TII->getRegisterInfo();
583  MDT = &getAnalysis<MachineDominatorTree>();
584  Loops = &getAnalysis<MachineLoopInfo>();
585  LV = &getAnalysis<LiveVariables>();
586  MRI = &MF.getRegInfo();
587 
588  if (skipFunction(MF.getFunction()))
589  return false;
590 
591  bool MadeChange = false;
592 
593  // TODO: we need to think about the order of visiting the blocks to get
594  // optimal result for nesting if-else cases.
595  for (MachineBasicBlock &MBB : MF) {
596  for (auto &MI : MBB.terminators()) {
597  // Detect the if-else blocks
598  if (MI.getOpcode() == AMDGPU::SI_IF) {
599  MachineBasicBlock *IfTarget = MI.getOperand(2).getMBB();
600  auto *Endif = getElseTarget(IfTarget);
601  if (!Endif)
602  continue;
603 
605  SmallVector<Register> CandidateRegs;
606 
607  LLVM_DEBUG(dbgs() << "Checking IF-ELSE-ENDIF: "
608  << printMBBReference(MBB) << ' '
609  << printMBBReference(*IfTarget) << ' '
610  << printMBBReference(*Endif) << '\n');
611 
612  // Collect all the blocks in the ELSE region
613  collectElseRegionBlocks(IfTarget, Endif, ElseBlocks);
614 
615  // Collect the registers can be optimized
616  collectCandidateRegisters(&MBB, IfTarget, Endif, ElseBlocks,
617  CandidateRegs);
618  MadeChange |= !CandidateRegs.empty();
619  // Now we are safe to optimize.
620  for (auto Reg : CandidateRegs)
621  optimizeLiveRange(Reg, &MBB, IfTarget, Endif, ElseBlocks);
622  } else if (MI.getOpcode() == AMDGPU::SI_WATERFALL_LOOP) {
623  LLVM_DEBUG(dbgs() << "Checking Waterfall loop: "
624  << printMBBReference(MBB) << '\n');
625 
626  SmallSetVector<Register, 16> CandidateRegs;
627  collectWaterfallCandidateRegisters(&MBB, CandidateRegs);
628  MadeChange |= !CandidateRegs.empty();
629  // Now we are safe to optimize.
630  for (auto Reg : CandidateRegs)
631  optimizeWaterfallLiveRange(Reg, &MBB);
632  }
633  }
634  }
635 
636  return MadeChange;
637 }
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:713
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:102
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:158
SIMachineFunctionInfo.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:89
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
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:543
llvm::SparseBitVector::reset
void reset(unsigned Idx)
Definition: SparseBitVector.h:486
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
llvm::SIOptimizeVGPRLiveRangeID
char & SIOptimizeVGPRLiveRangeID
Definition: SIOptimizeVGPRLiveRange.cpp:572
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:469
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::MachineFunctionProperties::Property::IsSSA
@ IsSSA
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::GCNSubtarget
Definition: GCNSubtarget.h:31
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:288
llvm::tgtok::Else
@ Else
Definition: TGLexer.h:75
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::MachineRegisterInfo::use_nodbg_begin
use_nodbg_iterator use_nodbg_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:518
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:589
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::Register::isPhysical
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:644
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:79
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52
GCNSubtarget.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::createSIOptimizeVGPRLiveRangePass
FunctionPass * createSIOptimizeVGPRLiveRangePass()
Definition: SIOptimizeVGPRLiveRange.cpp:574
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
LiveVariables.h
false
Definition: StackSlotColoring.cpp:142
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:251
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:173
llvm::MachineRegisterInfo::use_nodbg_end
static use_nodbg_iterator use_nodbg_end()
Definition: MachineRegisterInfo.h:521
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:400
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::MachineBasicBlock
Definition: MachineBasicBlock.h:95
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:634
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:634
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
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:7689
AMDGPUMCTargetDesc.h
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:507
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
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:471
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:576
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:1616
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1255
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:349
llvm::MachineFunction
Definition: MachineFunction.h:234
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::df_iterator_default_set
Definition: DepthFirstIterator.h:69
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:552
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1056
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:75
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:180
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
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:600
llvm::ISD::BR
@ BR
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:937
llvm::SIInstrInfo
Definition: SIInstrInfo.h:38
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:43
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:298
llvm::LiveVariables
Definition: LiveVariables.h:46
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:45
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:110
llvm::SmallPtrSetImpl< NodeRef >::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::LiveVariables::VarInfo::AliveBlocks
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:84