LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
RegisterPressure.cpp
Go to the documentation of this file.
1 //===-- RegisterPressure.cpp - Dynamic Register Pressure ------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the RegisterPressure class which can be used to track
11 // MachineInstr level register pressure.
12 //
13 //===----------------------------------------------------------------------===//
14 
20 #include "llvm/Support/Debug.h"
23 
24 using namespace llvm;
25 
26 /// Increase pressure for each pressure set provided by TargetRegisterInfo.
27 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
28  PSetIterator PSetI) {
29  unsigned Weight = PSetI.getWeight();
30  for (; PSetI.isValid(); ++PSetI)
31  CurrSetPressure[*PSetI] += Weight;
32 }
33 
34 /// Decrease pressure for each pressure set provided by TargetRegisterInfo.
35 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
36  PSetIterator PSetI) {
37  unsigned Weight = PSetI.getWeight();
38  for (; PSetI.isValid(); ++PSetI) {
39  assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow");
40  CurrSetPressure[*PSetI] -= Weight;
41  }
42 }
43 
44 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
46  const TargetRegisterInfo *TRI) {
47  bool Empty = true;
48  for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
49  if (SetPressure[i] != 0) {
50  dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
51  Empty = false;
52  }
53  }
54  if (Empty)
55  dbgs() << "\n";
56 }
57 
59  dbgs() << "Max Pressure: ";
61  dbgs() << "Live In: ";
62  for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i)
63  dbgs() << PrintReg(LiveInRegs[i], TRI) << " ";
64  dbgs() << '\n';
65  dbgs() << "Live Out: ";
66  for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i)
67  dbgs() << PrintReg(LiveOutRegs[i], TRI) << " ";
68  dbgs() << '\n';
69 }
70 
72  if (!isTopClosed() || !isBottomClosed()) {
73  dbgs() << "Curr Pressure: ";
74  dumpRegSetPressure(CurrSetPressure, TRI);
75  }
76  P.dump(TRI);
77 }
78 #endif
79 
80 /// Increase the current pressure as impacted by these registers and bump
81 /// the high water mark if needed.
83  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
84  PSetIterator PSetI = MRI->getPressureSets(RegUnits[i]);
85  unsigned Weight = PSetI.getWeight();
86  for (; PSetI.isValid(); ++PSetI) {
87  CurrSetPressure[*PSetI] += Weight;
88  if (CurrSetPressure[*PSetI] > P.MaxSetPressure[*PSetI]) {
89  P.MaxSetPressure[*PSetI] = CurrSetPressure[*PSetI];
90  }
91  }
92  }
93 }
94 
95 /// Simply decrease the current pressure as impacted by these registers.
97  for (unsigned I = 0, E = RegUnits.size(); I != E; ++I)
98  decreaseSetPressure(CurrSetPressure, MRI->getPressureSets(RegUnits[I]));
99 }
100 
101 /// Clear the result so it can be used for another round of pressure tracking.
103  TopIdx = BottomIdx = SlotIndex();
104  MaxSetPressure.clear();
105  LiveInRegs.clear();
106  LiveOutRegs.clear();
107 }
108 
109 /// Clear the result so it can be used for another round of pressure tracking.
112  MaxSetPressure.clear();
113  LiveInRegs.clear();
114  LiveOutRegs.clear();
115 }
116 
117 /// If the current top is not less than or equal to the next index, open it.
118 /// We happen to need the SlotIndex for the next top for pressure update.
120  if (TopIdx <= NextTop)
121  return;
122  TopIdx = SlotIndex();
123  LiveInRegs.clear();
124 }
125 
126 /// If the current top is the previous instruction (before receding), open it.
128  if (TopPos != PrevTop)
129  return;
131  LiveInRegs.clear();
132 }
133 
134 /// If the current bottom is not greater than the previous index, open it.
136  if (BottomIdx > PrevBottom)
137  return;
138  BottomIdx = SlotIndex();
139  LiveInRegs.clear();
140 }
141 
142 /// If the current bottom is the previous instr (before advancing), open it.
144  if (BottomPos != PrevBottom)
145  return;
147  LiveInRegs.clear();
148 }
149 
152  return &LIS->getInterval(Reg);
153  return LIS->getCachedRegUnit(Reg);
154 }
155 
157  MBB = 0;
158  LIS = 0;
159 
160  CurrSetPressure.clear();
161  LiveThruPressure.clear();
162  P.MaxSetPressure.clear();
163 
164  if (RequireIntervals)
165  static_cast<IntervalPressure&>(P).reset();
166  else
167  static_cast<RegionPressure&>(P).reset();
168 
169  LiveRegs.PhysRegs.clear();
170  LiveRegs.VirtRegs.clear();
171  UntiedDefs.clear();
172 }
173 
174 /// Setup the RegPressureTracker.
175 ///
176 /// TODO: Add support for pressure without LiveIntervals.
178  const RegisterClassInfo *rci,
179  const LiveIntervals *lis,
180  const MachineBasicBlock *mbb,
182  bool ShouldTrackUntiedDefs)
183 {
184  reset();
185 
186  MF = mf;
187  TRI = MF->getTarget().getRegisterInfo();
188  RCI = rci;
189  MRI = &MF->getRegInfo();
190  MBB = mbb;
191  TrackUntiedDefs = ShouldTrackUntiedDefs;
192 
193  if (RequireIntervals) {
194  assert(lis && "IntervalPressure requires LiveIntervals");
195  LIS = lis;
196  }
197 
198  CurrPos = pos;
199  CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
200 
201  P.MaxSetPressure = CurrSetPressure;
202 
203  LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs());
204  LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs());
205  if (TrackUntiedDefs)
206  UntiedDefs.setUniverse(MRI->getNumVirtRegs());
207 }
208 
209 /// Does this pressure result have a valid top position and live ins.
211  if (RequireIntervals)
212  return static_cast<IntervalPressure&>(P).TopIdx.isValid();
213  return (static_cast<RegionPressure&>(P).TopPos ==
215 }
216 
217 /// Does this pressure result have a valid bottom position and live outs.
219  if (RequireIntervals)
220  return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
221  return (static_cast<RegionPressure&>(P).BottomPos ==
223 }
224 
225 
227  MachineBasicBlock::const_iterator IdxPos = CurrPos;
228  while (IdxPos != MBB->end() && IdxPos->isDebugValue())
229  ++IdxPos;
230  if (IdxPos == MBB->end())
231  return LIS->getMBBEndIdx(MBB);
232  return LIS->getInstructionIndex(IdxPos).getRegSlot();
233 }
234 
235 /// Set the boundary for the top of the region and summarize live ins.
237  if (RequireIntervals)
238  static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
239  else
240  static_cast<RegionPressure&>(P).TopPos = CurrPos;
241 
242  assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
243  P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
244  P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
246  LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
247  P.LiveInRegs.push_back(*I);
248  std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
249  P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
250  P.LiveInRegs.end());
251 }
252 
253 /// Set the boundary for the bottom of the region and summarize live outs.
255  if (RequireIntervals)
256  static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
257  else
258  static_cast<RegionPressure&>(P).BottomPos = CurrPos;
259 
260  assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
261  P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
262  P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
264  LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
265  P.LiveOutRegs.push_back(*I);
266  std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
267  P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
268  P.LiveOutRegs.end());
269 }
270 
271 /// Finalize the region boundaries and record live ins and live outs.
273  if (!isTopClosed() && !isBottomClosed()) {
274  assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() &&
275  "no region boundary");
276  return;
277  }
278  if (!isBottomClosed())
279  closeBottom();
280  else if (!isTopClosed())
281  closeTop();
282  // If both top and bottom are closed, do nothing.
283 }
284 
285 /// The register tracker is unaware of global liveness so ignores normal
286 /// live-thru ranges. However, two-address or coalesced chains can also lead
287 /// to live ranges with no holes. Count these to inform heuristics that we
288 /// can never drop below this pressure.
290  LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
291  assert(isBottomClosed() && "need bottom-up tracking to intialize.");
292  for (unsigned i = 0, e = P.LiveOutRegs.size(); i < e; ++i) {
293  unsigned Reg = P.LiveOutRegs[i];
295  && !RPTracker.hasUntiedDef(Reg)) {
296  increaseSetPressure(LiveThruPressure, MRI->getPressureSets(Reg));
297  }
298  }
299 }
300 
301 /// \brief Convenient wrapper for checking membership in RegisterOperands.
302 /// (std::count() doesn't have an early exit).
303 static bool containsReg(ArrayRef<unsigned> RegUnits, unsigned RegUnit) {
304  return std::find(RegUnits.begin(), RegUnits.end(), RegUnit) != RegUnits.end();
305 }
306 
307 /// Collect this instruction's unique uses and defs into SmallVectors for
308 /// processing defs and uses in order.
309 ///
310 /// FIXME: always ignore tied opers
312  const TargetRegisterInfo *TRI;
313  const MachineRegisterInfo *MRI;
314  bool IgnoreDead;
315 
316 public:
320 
322  const MachineRegisterInfo *mri, bool ID = false):
323  TRI(tri), MRI(mri), IgnoreDead(ID) {}
324 
325  /// Push this operand's register onto the correct vector.
326  void collect(const MachineOperand &MO) {
327  if (!MO.isReg() || !MO.getReg())
328  return;
329  if (MO.readsReg())
330  pushRegUnits(MO.getReg(), Uses);
331  if (MO.isDef()) {
332  if (MO.isDead()) {
333  if (!IgnoreDead)
334  pushRegUnits(MO.getReg(), DeadDefs);
335  }
336  else
337  pushRegUnits(MO.getReg(), Defs);
338  }
339  }
340 
341 protected:
342  void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &RegUnits) {
344  if (containsReg(RegUnits, Reg))
345  return;
346  RegUnits.push_back(Reg);
347  }
348  else if (MRI->isAllocatable(Reg)) {
349  for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
350  if (containsReg(RegUnits, *Units))
351  continue;
352  RegUnits.push_back(*Units);
353  }
354  }
355  }
356 };
357 
358 /// Collect physical and virtual register operands.
359 static void collectOperands(const MachineInstr *MI,
360  RegisterOperands &RegOpers) {
361  for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
362  RegOpers.collect(*OperI);
363 
364  // Remove redundant physreg dead defs.
366  std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(),
367  std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs));
368  RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end());
369 }
370 
371 /// Initialize an array of N PressureDiffs.
372 void PressureDiffs::init(unsigned N) {
373  Size = N;
374  if (N <= Max) {
375  memset(PDiffArray, 0, N * sizeof(PressureDiff));
376  return;
377  }
378  Max = Size;
379  free(PDiffArray);
380  PDiffArray = reinterpret_cast<PressureDiff*>(calloc(N, sizeof(PressureDiff)));
381 }
382 
383 /// Add a change in pressure to the pressure diff of a given instruction.
384 void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec,
385  const MachineRegisterInfo *MRI) {
386  PSetIterator PSetI = MRI->getPressureSets(RegUnit);
387  int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight();
388  for (; PSetI.isValid(); ++PSetI) {
389  // Find an existing entry in the pressure diff for this PSet.
390  PressureDiff::iterator I = begin(), E = end();
391  for (; I != E && I->isValid(); ++I) {
392  if (I->getPSet() >= *PSetI)
393  break;
394  }
395  // If all pressure sets are more constrained, skip the remaining PSets.
396  if (I == E)
397  break;
398  // Insert this PressureChange.
399  if (!I->isValid() || I->getPSet() != *PSetI) {
400  PressureChange PTmp = PressureChange(*PSetI);
401  for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J)
402  std::swap(*J,PTmp);
403  }
404  // Update the units for this pressure set.
405  I->setUnitInc(I->getUnitInc() + Weight);
406  }
407 }
408 
409 /// Record the pressure difference induced by the given operand list.
410 static void collectPDiff(PressureDiff &PDiff, RegisterOperands &RegOpers,
411  const MachineRegisterInfo *MRI) {
412  assert(!PDiff.begin()->isValid() && "stale PDiff");
413 
414  for (unsigned i = 0, e = RegOpers.Defs.size(); i != e; ++i)
415  PDiff.addPressureChange(RegOpers.Defs[i], true, MRI);
416 
417  for (unsigned i = 0, e = RegOpers.Uses.size(); i != e; ++i)
418  PDiff.addPressureChange(RegOpers.Uses[i], false, MRI);
419 }
420 
421 /// Force liveness of registers.
423  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
424  if (LiveRegs.insert(Regs[i]))
425  increaseRegPressure(Regs[i]);
426  }
427 }
428 
429 /// Add Reg to the live in set and increase max pressure.
431  assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
432  if (containsReg(P.LiveInRegs, Reg))
433  return;
434 
435  // At live in discovery, unconditionally increase the high water mark.
436  P.LiveInRegs.push_back(Reg);
438 }
439 
440 /// Add Reg to the live out set and increase max pressure.
442  assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
443  if (containsReg(P.LiveOutRegs, Reg))
444  return;
445 
446  // At live out discovery, unconditionally increase the high water mark.
447  P.LiveOutRegs.push_back(Reg);
449 }
450 
451 /// Recede across the previous instruction. If LiveUses is provided, record any
452 /// RegUnits that are made live by the current instruction's uses. This includes
453 /// registers that are both defined and used by the instruction. If a pressure
454 /// difference pointer is provided record the changes is pressure caused by this
455 /// instruction independent of liveness.
457  PressureDiff *PDiff) {
458  // Check for the top of the analyzable region.
459  if (CurrPos == MBB->begin()) {
460  closeRegion();
461  return false;
462  }
463  if (!isBottomClosed())
464  closeBottom();
465 
466  // Open the top of the region using block iterators.
467  if (!RequireIntervals && isTopClosed())
468  static_cast<RegionPressure&>(P).openTop(CurrPos);
469 
470  // Find the previous instruction.
471  do
472  --CurrPos;
473  while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
474 
475  if (CurrPos->isDebugValue()) {
476  closeRegion();
477  return false;
478  }
479  SlotIndex SlotIdx;
480  if (RequireIntervals)
481  SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
482 
483  // Open the top of the region using slot indexes.
484  if (RequireIntervals && isTopClosed())
485  static_cast<IntervalPressure&>(P).openTop(SlotIdx);
486 
487  RegisterOperands RegOpers(TRI, MRI);
488  collectOperands(CurrPos, RegOpers);
489 
490  if (PDiff)
491  collectPDiff(*PDiff, RegOpers, MRI);
492 
493  // Boost pressure for all dead defs together.
494  increaseRegPressure(RegOpers.DeadDefs);
495  decreaseRegPressure(RegOpers.DeadDefs);
496 
497  // Kill liveness at live defs.
498  // TODO: consider earlyclobbers?
499  for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
500  unsigned Reg = RegOpers.Defs[i];
501  bool DeadDef = false;
502  if (RequireIntervals) {
503  const LiveRange *LR = getLiveRange(Reg);
504  if (LR) {
505  LiveQueryResult LRQ = LR->Query(SlotIdx);
506  DeadDef = LRQ.isDeadDef();
507  }
508  }
509  if (!DeadDef) {
510  if (LiveRegs.erase(Reg))
511  decreaseRegPressure(Reg);
512  else
513  discoverLiveOut(Reg);
514  }
515  }
516 
517  // Generate liveness for uses.
518  for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
519  unsigned Reg = RegOpers.Uses[i];
520  if (!LiveRegs.contains(Reg)) {
521  // Adjust liveouts if LiveIntervals are available.
522  if (RequireIntervals) {
523  const LiveRange *LR = getLiveRange(Reg);
524  if (LR) {
525  LiveQueryResult LRQ = LR->Query(SlotIdx);
526  if (!LRQ.isKill() && !LRQ.valueDefined())
527  discoverLiveOut(Reg);
528  }
529  }
530  increaseRegPressure(Reg);
531  LiveRegs.insert(Reg);
532  if (LiveUses && !containsReg(*LiveUses, Reg))
533  LiveUses->push_back(Reg);
534  }
535  }
536  if (TrackUntiedDefs) {
537  for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
538  unsigned Reg = RegOpers.Defs[i];
539  if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg))
540  UntiedDefs.insert(Reg);
541  }
542  }
543  return true;
544 }
545 
546 /// Advance across the current instruction.
548  assert(!TrackUntiedDefs && "unsupported mode");
549 
550  // Check for the bottom of the analyzable region.
551  if (CurrPos == MBB->end()) {
552  closeRegion();
553  return false;
554  }
555  if (!isTopClosed())
556  closeTop();
557 
558  SlotIndex SlotIdx;
559  if (RequireIntervals)
560  SlotIdx = getCurrSlot();
561 
562  // Open the bottom of the region using slot indexes.
563  if (isBottomClosed()) {
564  if (RequireIntervals)
565  static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
566  else
567  static_cast<RegionPressure&>(P).openBottom(CurrPos);
568  }
569 
570  RegisterOperands RegOpers(TRI, MRI);
571  collectOperands(CurrPos, RegOpers);
572 
573  for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
574  unsigned Reg = RegOpers.Uses[i];
575  // Discover live-ins.
576  bool isLive = LiveRegs.contains(Reg);
577  if (!isLive)
578  discoverLiveIn(Reg);
579  // Kill liveness at last uses.
580  bool lastUse = false;
581  if (RequireIntervals) {
582  const LiveRange *LR = getLiveRange(Reg);
583  lastUse = LR && LR->Query(SlotIdx).isKill();
584  }
585  else {
586  // Allocatable physregs are always single-use before register rewriting.
588  }
589  if (lastUse && isLive) {
590  LiveRegs.erase(Reg);
591  decreaseRegPressure(Reg);
592  }
593  else if (!lastUse && !isLive)
594  increaseRegPressure(Reg);
595  }
596 
597  // Generate liveness for defs.
598  for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
599  unsigned Reg = RegOpers.Defs[i];
600  if (LiveRegs.insert(Reg))
601  increaseRegPressure(Reg);
602  }
603 
604  // Boost pressure for all dead defs together.
605  increaseRegPressure(RegOpers.DeadDefs);
606  decreaseRegPressure(RegOpers.DeadDefs);
607 
608  // Find the next instruction.
609  do
610  ++CurrPos;
611  while (CurrPos != MBB->end() && CurrPos->isDebugValue());
612  return true;
613 }
614 
615 /// Find the max change in excess pressure across all sets.
617  ArrayRef<unsigned> NewPressureVec,
618  RegPressureDelta &Delta,
619  const RegisterClassInfo *RCI,
620  ArrayRef<unsigned> LiveThruPressureVec) {
621  Delta.Excess = PressureChange();
622  for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
623  unsigned POld = OldPressureVec[i];
624  unsigned PNew = NewPressureVec[i];
625  int PDiff = (int)PNew - (int)POld;
626  if (!PDiff) // No change in this set in the common case.
627  continue;
628  // Only consider change beyond the limit.
629  unsigned Limit = RCI->getRegPressureSetLimit(i);
630  if (!LiveThruPressureVec.empty())
631  Limit += LiveThruPressureVec[i];
632 
633  if (Limit > POld) {
634  if (Limit > PNew)
635  PDiff = 0; // Under the limit
636  else
637  PDiff = PNew - Limit; // Just exceeded limit.
638  }
639  else if (Limit > PNew)
640  PDiff = Limit - POld; // Just obeyed limit.
641 
642  if (PDiff) {
643  Delta.Excess = PressureChange(i);
644  Delta.Excess.setUnitInc(PDiff);
645  break;
646  }
647  }
648 }
649 
650 /// Find the max change in max pressure that either surpasses a critical PSet
651 /// limit or exceeds the current MaxPressureLimit.
652 ///
653 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
654 /// silly. It's done now to demonstrate the concept but will go away with a
655 /// RegPressureTracker API change to work with pressure differences.
656 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
657  ArrayRef<unsigned> NewMaxPressureVec,
658  ArrayRef<PressureChange> CriticalPSets,
659  ArrayRef<unsigned> MaxPressureLimit,
660  RegPressureDelta &Delta) {
661  Delta.CriticalMax = PressureChange();
662  Delta.CurrentMax = PressureChange();
663 
664  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
665  for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
666  unsigned POld = OldMaxPressureVec[i];
667  unsigned PNew = NewMaxPressureVec[i];
668  if (PNew == POld) // No change in this set in the common case.
669  continue;
670 
671  if (!Delta.CriticalMax.isValid()) {
672  while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
673  ++CritIdx;
674 
675  if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
676  int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
677  if (PDiff > 0) {
678  Delta.CriticalMax = PressureChange(i);
679  Delta.CriticalMax.setUnitInc(PDiff);
680  }
681  }
682  }
683  // Find the first increase above MaxPressureLimit.
684  // (Ignores negative MDiff).
685  if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
686  Delta.CurrentMax = PressureChange(i);
687  Delta.CurrentMax.setUnitInc(PNew - POld);
688  if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
689  break;
690  }
691  }
692 }
693 
694 /// Record the upward impact of a single instruction on current register
695 /// pressure. Unlike the advance/recede pressure tracking interface, this does
696 /// not discover live in/outs.
697 ///
698 /// This is intended for speculative queries. It leaves pressure inconsistent
699 /// with the current position, so must be restored by the caller.
701  assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
702 
703  // Account for register pressure similar to RegPressureTracker::recede().
704  RegisterOperands RegOpers(TRI, MRI, /*IgnoreDead=*/true);
705  collectOperands(MI, RegOpers);
706 
707  // Boost max pressure for all dead defs together.
708  // Since CurrSetPressure and MaxSetPressure
709  increaseRegPressure(RegOpers.DeadDefs);
710  decreaseRegPressure(RegOpers.DeadDefs);
711 
712  // Kill liveness at live defs.
713  for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
714  unsigned Reg = RegOpers.Defs[i];
715  bool DeadDef = false;
716  if (RequireIntervals) {
717  const LiveRange *LR = getLiveRange(Reg);
718  if (LR) {
719  SlotIndex SlotIdx = LIS->getInstructionIndex(MI);
720  LiveQueryResult LRQ = LR->Query(SlotIdx);
721  DeadDef = LRQ.isDeadDef();
722  }
723  }
724  if (!DeadDef) {
725  if (!containsReg(RegOpers.Uses, Reg))
726  decreaseRegPressure(Reg);
727  }
728  }
729  // Generate liveness for uses.
730  for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
731  unsigned Reg = RegOpers.Uses[i];
732  if (!LiveRegs.contains(Reg))
733  increaseRegPressure(Reg);
734  }
735 }
736 
737 /// Consider the pressure increase caused by traversing this instruction
738 /// bottom-up. Find the pressure set with the most change beyond its pressure
739 /// limit based on the tracker's current pressure, and return the change in
740 /// number of register units of that pressure set introduced by this
741 /// instruction.
742 ///
743 /// This assumes that the current LiveOut set is sufficient.
744 ///
745 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
746 /// result per-SUnit with enough information to adjust for the current
747 /// scheduling position. But this works as a proof of concept.
750  RegPressureDelta &Delta,
751  ArrayRef<PressureChange> CriticalPSets,
752  ArrayRef<unsigned> MaxPressureLimit) {
753  // Snapshot Pressure.
754  // FIXME: The snapshot heap space should persist. But I'm planning to
755  // summarize the pressure effect so we don't need to snapshot at all.
756  std::vector<unsigned> SavedPressure = CurrSetPressure;
757  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
758 
759  bumpUpwardPressure(MI);
760 
761  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
762  LiveThruPressure);
763  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
764  MaxPressureLimit, Delta);
765  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
766  Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
767 
768  // Restore the tracker's state.
769  P.MaxSetPressure.swap(SavedMaxPressure);
770  CurrSetPressure.swap(SavedPressure);
771 
772 #ifndef NDEBUG
773  if (!PDiff)
774  return;
775 
776  // Check if the alternate algorithm yields the same result.
777  RegPressureDelta Delta2;
778  getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
779  if (Delta != Delta2) {
780  dbgs() << "DELTA: " << *MI;
781  if (Delta.Excess.isValid())
782  dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
783  << " " << Delta.Excess.getUnitInc() << "\n";
784  if (Delta.CriticalMax.isValid())
785  dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
786  << " " << Delta.CriticalMax.getUnitInc() << "\n";
787  if (Delta.CurrentMax.isValid())
788  dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
789  << " " << Delta.CurrentMax.getUnitInc() << "\n";
790  if (Delta2.Excess.isValid())
791  dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
792  << " " << Delta2.Excess.getUnitInc() << "\n";
793  if (Delta2.CriticalMax.isValid())
794  dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
795  << " " << Delta2.CriticalMax.getUnitInc() << "\n";
796  if (Delta2.CurrentMax.isValid())
797  dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
798  << " " << Delta2.CurrentMax.getUnitInc() << "\n";
799  llvm_unreachable("RegP Delta Mismatch");
800  }
801 #endif
802 }
803 
804 /// This is a prototype of the fast version of querying register pressure that
805 /// does not directly depend on current liveness. It's still slow because we
806 /// recompute pressure change on-the-fly. This implementation only exists to
807 /// prove correctness.
808 ///
809 /// @param Delta captures information needed for heuristics.
810 ///
811 /// @param CriticalPSets Are the pressure sets that are known to exceed some
812 /// limit within the region, not necessarily at the current position.
813 ///
814 /// @param MaxPressureLimit Is the max pressure within the region, not
815 /// necessarily at the current position.
818  RegPressureDelta &Delta,
819  ArrayRef<PressureChange> CriticalPSets,
820  ArrayRef<unsigned> MaxPressureLimit) const {
821  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
823  PDiffI = PDiff.begin(), PDiffE = PDiff.end();
824  PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
825 
826  unsigned PSetID = PDiffI->getPSet();
827  unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
828  if (!LiveThruPressure.empty())
829  Limit += LiveThruPressure[PSetID];
830 
831  unsigned POld = CurrSetPressure[PSetID];
832  unsigned MOld = P.MaxSetPressure[PSetID];
833  unsigned MNew = MOld;
834  // Ignore DeadDefs here because they aren't captured by PressureChange.
835  unsigned PNew = POld + PDiffI->getUnitInc();
836  assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld) && "PSet overflow");
837  if (PNew > MOld)
838  MNew = PNew;
839  // Check if current pressure has exceeded the limit.
840  if (!Delta.Excess.isValid()) {
841  unsigned ExcessInc = 0;
842  if (PNew > Limit)
843  ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
844  else if (POld > Limit)
845  ExcessInc = Limit - POld;
846  if (ExcessInc) {
847  Delta.Excess = PressureChange(PSetID);
848  Delta.Excess.setUnitInc(ExcessInc);
849  }
850  }
851  // Check if max pressure has exceeded a critical pressure set max.
852  if (MNew == MOld)
853  continue;
854  if (!Delta.CriticalMax.isValid()) {
855  while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
856  ++CritIdx;
857 
858  if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
859  int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
860  if (CritInc > 0 && CritInc <= INT16_MAX) {
861  Delta.CriticalMax = PressureChange(PSetID);
862  Delta.CriticalMax.setUnitInc(CritInc);
863  }
864  }
865  }
866  // Check if max pressure has exceeded the current max.
867  if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
868  Delta.CurrentMax = PressureChange(PSetID);
869  Delta.CurrentMax.setUnitInc(MNew - MOld);
870  }
871  }
872 }
873 
874 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
875 static bool findUseBetween(unsigned Reg,
876  SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
877  const MachineRegisterInfo *MRI,
878  const LiveIntervals *LIS) {
880  UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
881  UI != UE; UI.skipInstruction()) {
882  const MachineInstr* MI = &*UI;
883  if (MI->isDebugValue())
884  continue;
885  SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
886  if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
887  return true;
888  }
889  return false;
890 }
891 
892 /// Record the downward impact of a single instruction on current register
893 /// pressure. Unlike the advance/recede pressure tracking interface, this does
894 /// not discover live in/outs.
895 ///
896 /// This is intended for speculative queries. It leaves pressure inconsistent
897 /// with the current position, so must be restored by the caller.
899  assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
900 
901  // Account for register pressure similar to RegPressureTracker::recede().
902  RegisterOperands RegOpers(TRI, MRI);
903  collectOperands(MI, RegOpers);
904 
905  // Kill liveness at last uses. Assume allocatable physregs are single-use
906  // rather than checking LiveIntervals.
907  SlotIndex SlotIdx;
908  if (RequireIntervals)
909  SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
910 
911  for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
912  unsigned Reg = RegOpers.Uses[i];
913  if (RequireIntervals) {
914  // FIXME: allow the caller to pass in the list of vreg uses that remain
915  // to be bottom-scheduled to avoid searching uses at each query.
916  SlotIndex CurrIdx = getCurrSlot();
917  const LiveRange *LR = getLiveRange(Reg);
918  if (LR) {
919  LiveQueryResult LRQ = LR->Query(SlotIdx);
920  if (LRQ.isKill() && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
921  decreaseRegPressure(Reg);
922  }
923  }
924  }
925  else if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
926  // Allocatable physregs are always single-use before register rewriting.
927  decreaseRegPressure(Reg);
928  }
929  }
930 
931  // Generate liveness for defs.
932  increaseRegPressure(RegOpers.Defs);
933 
934  // Boost pressure for all dead defs together.
935  increaseRegPressure(RegOpers.DeadDefs);
936  decreaseRegPressure(RegOpers.DeadDefs);
937 }
938 
939 /// Consider the pressure increase caused by traversing this instruction
940 /// top-down. Find the register class with the most change in its pressure limit
941 /// based on the tracker's current pressure, and return the number of excess
942 /// register units of that pressure set introduced by this instruction.
943 ///
944 /// This assumes that the current LiveIn set is sufficient.
947  ArrayRef<PressureChange> CriticalPSets,
948  ArrayRef<unsigned> MaxPressureLimit) {
949  // Snapshot Pressure.
950  std::vector<unsigned> SavedPressure = CurrSetPressure;
951  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
952 
954 
955  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
956  LiveThruPressure);
957  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
958  MaxPressureLimit, Delta);
959  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
960  Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
961 
962  // Restore the tracker's state.
963  P.MaxSetPressure.swap(SavedMaxPressure);
964  CurrSetPressure.swap(SavedPressure);
965 }
966 
967 /// Get the pressure of each PSet after traversing this instruction bottom-up.
970  std::vector<unsigned> &PressureResult,
971  std::vector<unsigned> &MaxPressureResult) {
972  // Snapshot pressure.
973  PressureResult = CurrSetPressure;
974  MaxPressureResult = P.MaxSetPressure;
975 
976  bumpUpwardPressure(MI);
977 
978  // Current pressure becomes the result. Restore current pressure.
979  P.MaxSetPressure.swap(MaxPressureResult);
980  CurrSetPressure.swap(PressureResult);
981 }
982 
983 /// Get the pressure of each PSet after traversing this instruction top-down.
986  std::vector<unsigned> &PressureResult,
987  std::vector<unsigned> &MaxPressureResult) {
988  // Snapshot pressure.
989  PressureResult = CurrSetPressure;
990  MaxPressureResult = P.MaxSetPressure;
991 
993 
994  // Current pressure becomes the result. Restore current pressure.
995  P.MaxSetPressure.swap(MaxPressureResult);
996  CurrSetPressure.swap(PressureResult);
997 }
void push_back(const T &Elt)
Definition: SmallVector.h:236
void dump(const TargetRegisterInfo *TRI) const
bool advance()
Advance across the current instruction.
void increaseRegPressure(ArrayRef< unsigned > Regs)
void reserve(unsigned N)
Definition: SmallVector.h:425
virtual unsigned getNumRegPressureSets() const =0
Get the number of dimensions of register pressure.
static void increaseSetPressure(std::vector< unsigned > &CurrSetPressure, PSetIterator PSetI)
Increase pressure for each pressure set provided by TargetRegisterInfo.
void addPressureChange(unsigned RegUnit, bool IsDec, const MachineRegisterInfo *MRI)
Add a change in pressure to the pressure diff of a given instruction.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void init(unsigned N)
Initialize an array of N PressureDiffs.
unsigned size() const
Definition: SparseSet.h:185
iterator end() const
Definition: ArrayRef.h:98
bool isDead() const
SlotIndex getInstructionIndex(const MachineInstr *instr) const
Returns the base index of the given instruction.
void setUnitInc(int Inc)
static bool isVirtualRegister(unsigned Reg)
const LiveRange * getLiveRange(unsigned Reg) const
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
bool isKill() const
Definition: LiveInterval.h:107
void closeRegion()
Finalize the region boundaries and recored live ins and live outs.
bool isTopClosed() const
Does this pressure result have a valid top position and live ins.
void openBottom(MachineBasicBlock::const_iterator PrevBottom)
If the current bottom is the previous instr (before advancing), open it.
static use_nodbg_iterator use_nodbg_end()
bool empty() const
Definition: SparseSet.h:178
unsigned getNumVirtRegs() const
SlotIndex TopIdx
Record the boundary of the region being tracked.
void closeBottom()
Set the boundary for the bottom of the region and summarize live outs.
#define llvm_unreachable(msg)
virtual const char * getRegPressureSetName(unsigned Idx) const =0
Get the name of this register unit pressure set.
unsigned getPSet() const
static void collectOperands(const MachineInstr *MI, RegisterOperands &RegOpers)
Collect physical and virtual register operands.
void openBottom(SlotIndex PrevBottom)
If the current bottom is not greater than the previous index, open it.
MachineBasicBlock::const_iterator TopPos
Record the boundary of the region being tracked.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const_iterator end() const
Definition: SparseSet.h:170
void discoverLiveOut(unsigned Reg)
Add Reg to the live out set and increase max pressure.
ID
LLVM Calling Convention Representation.
Definition: CallingConv.h:26
bool recede(SmallVectorImpl< unsigned > *LiveUses=0, PressureDiff *PDiff=0)
Recede across the previous instruction.
SlotIndex getCurrSlot() const
Get the SlotIndex for the first nondebug instruction including or after the current position...
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
void openTop(SlotIndex NextTop)
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
Definition: SmallVector.h:56
SparseSet< unsigned, VirtReg2IndexFunctor > VirtRegs
SmallVector< unsigned, 8 > DeadDefs
bool hasUntiedDef(unsigned VirtReg) const
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:109
LiveRange * getCachedRegUnit(unsigned Unit)
static bool containsReg(ArrayRef< unsigned > RegUnits, unsigned RegUnit)
Convenient wrapper for checking membership in RegisterOperands. (std::count() doesn't have an early e...
bool isDebugValue() const
Definition: MachineInstr.h:639
bool isDeadDef() const
Return true if this instruction has a dead def.
Definition: LiveInterval.h:112
void decreaseRegPressure(ArrayRef< unsigned > Regs)
Simply decrease the current pressure as impacted by these registers.
void getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
LiveQueryResult Query(SlotIndex Idx) const
Definition: LiveInterval.h:441
void bumpDownwardPressure(const MachineInstr *MI)
SparseSet< unsigned > PhysRegs
void free(void *ptr);
void openTop(MachineBasicBlock::const_iterator PrevTop)
If the current top is the previous instruction (before receding), open it.
iterator begin() const
Definition: ArrayRef.h:97
SmallVector< unsigned, 8 > LiveOutRegs
VNInfo * valueDefined() const
Definition: LiveInterval.h:124
unsigned getRegPressureSetLimit(unsigned Idx) const
void setUniverse(unsigned U)
Definition: SparseSet.h:150
void dumpRegSetPressure(ArrayRef< unsigned > SetPressure, const TargetRegisterInfo *TRI)
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:104
void append(in_iter in_start, in_iter in_end)
Definition: SmallVector.h:445
static void collectPDiff(PressureDiff &PDiff, RegisterOperands &RegOpers, const MachineRegisterInfo *MRI)
Record the pressure difference induced by the given operand list.
iterator erase(iterator I)
Definition: SmallVector.h:478
void initLiveThru(const RegPressureTracker &RPTracker)
const_iterator begin() const
Definition: SparseSet.h:169
std::vector< unsigned > MaxSetPressure
Map of max reg pressure indexed by pressure set ID, not class ID.
void collect(const MachineOperand &MO)
Push this operand's register onto the correct vector.
void discoverLiveIn(unsigned Reg)
Add Reg to the live in set and increase max pressure.
bool insert(unsigned Reg)
unsigned getWeight() const
void reset()
Clear the result so it can be used for another round of pressure tracking.
LiveInterval & getInterval(unsigned Reg)
bool contains(unsigned Reg) const
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
Definition: Debug.cpp:101
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:591
RegisterOperands(const TargetRegisterInfo *tri, const MachineRegisterInfo *mri, bool ID=false)
PressureChange CriticalMax
bool erase(unsigned Reg)
void init(const MachineFunction *mf, const RegisterClassInfo *rci, const LiveIntervals *lis, const MachineBasicBlock *mbb, MachineBasicBlock::const_iterator pos, bool ShouldTrackUntiedDefs=false)
void closeTop()
Set the boundary for the top of the region and summarize live ins.
static void decreaseSetPressure(std::vector< unsigned > &CurrSetPressure, PSetIterator PSetI)
Decrease pressure for each pressure set provided by TargetRegisterInfo.
bundle_iterator< const MachineInstr, const_instr_iterator > const_iterator
MachineRegisterInfo & getRegInfo()
PSetIterator getPressureSets(unsigned RegUnit) const
#define I(x, y, z)
Definition: MD5.cpp:54
#define N
SmallVector< unsigned, 8 > Defs
void getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
const TargetMachine & getTarget() const
void getUpwardPressure(const MachineInstr *MI, std::vector< unsigned > &PressureResult, std::vector< unsigned > &MaxPressureResult)
Get the pressure of each PSet after traversing this instruction bottom-up.
virtual const TargetRegisterInfo * getRegisterInfo() const
bool isBottomClosed() const
Does this pressure result have a valid bottom position and live outs.
void bumpUpwardPressure(const MachineInstr *MI)
SlotIndex getRegSlot(bool EC=false) const
Definition: SlotIndexes.h:257
unsigned getReg() const
getReg - Returns the register number.
bool isValid() const
isValid - Returns true until all the operands have been visited.
void addLiveRegs(ArrayRef< unsigned > Regs)
Force liveness of registers.
static bool findUseBetween(unsigned Reg, SlotIndex PriorUseIdx, SlotIndex NextUseIdx, const MachineRegisterInfo *MRI, const LiveIntervals *LIS)
Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
static void computeMaxPressureDelta(ArrayRef< unsigned > OldMaxPressureVec, ArrayRef< unsigned > NewMaxPressureVec, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit, RegPressureDelta &Delta)
void reset()
Clear the result so it can be used for another round of pressure tracking.
SmallVector< unsigned, 8 > Uses
SmallVector< unsigned, 8 > LiveInRegs
List of live in virtual registers or physical register units.
void getDownwardPressure(const MachineInstr *MI, std::vector< unsigned > &PressureResult, std::vector< unsigned > &MaxPressureResult)
Get the pressure of each PSet after traversing this instruction top-down.
const MCRegisterInfo & MRI
bool readsReg() const
MachineBasicBlock::const_iterator BottomPos
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:92
void *calloc(size_t count, size_t size);
void pushRegUnits(unsigned Reg, SmallVectorImpl< unsigned > &RegUnits)
use_nodbg_iterator use_nodbg_begin(unsigned RegNo) const
void getUpwardPressureDelta(const MachineInstr *MI, PressureDiff &PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit) const
static void computeExcessPressureDelta(ArrayRef< unsigned > OldPressureVec, ArrayRef< unsigned > NewPressureVec, RegPressureDelta &Delta, const RegisterClassInfo *RCI, ArrayRef< unsigned > LiveThruPressureVec)
Find the max change in excess pressure across all sets.