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