lib/CodeGen/RegisterPressure.cpp

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