contrib/llvm/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 #include "llvm/Target/TargetMachine.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)
  45 void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
  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
  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() << 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
  71 void RegPressureTracker::dump() const {
  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.
  82 void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> RegUnits) {
  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.
  96 void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> RegUnits) {
  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.
 102 void IntervalPressure::reset() {
 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.
 110 void RegionPressure::reset() {
 111   TopPos = BottomPos = MachineBasicBlock::const_iterator();
 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.
 119 void IntervalPressure::openTop(SlotIndex NextTop) {
 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.
 127 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
 128   if (TopPos != PrevTop)
 129     return;
 130   TopPos = MachineBasicBlock::const_iterator();
 131   LiveInRegs.clear();
 132 }
 133
 134 /// If the current bottom is not greater than the previous index, open it.
 135 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
 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.
 143 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
 144   if (BottomPos != PrevBottom)
 145     return;
 146   BottomPos = MachineBasicBlock::const_iterator();
 147   LiveInRegs.clear();
 148 }
 149
 150 const LiveRange *RegPressureTracker::getLiveRange(unsigned Reg) const {
 151   if (TargetRegisterInfo::isVirtualRegister(Reg))
 152     return &LIS->getInterval(Reg);
 153   return LIS->getCachedRegUnit(Reg);
 154 }
 155
 156 void RegPressureTracker::reset() {
 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.
 177 void RegPressureTracker::init(const MachineFunction *mf,
 178                               const RegisterClassInfo *rci,
 179                               const LiveIntervals *lis,
 180                               const MachineBasicBlock *mbb,
 181                               MachineBasicBlock::const_iterator pos,
 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.
 210 bool RegPressureTracker::isTopClosed() const {
 211   if (RequireIntervals)
 212     return static_cast<IntervalPressure&>(P).TopIdx.isValid();
 213   return (static_cast<RegionPressure&>(P).TopPos ==
 214           MachineBasicBlock::const_iterator());
 215 }
 216
 217 /// Does this pressure result have a valid bottom position and live outs.
 218 bool RegPressureTracker::isBottomClosed() const {
 219   if (RequireIntervals)
 220     return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
 221   return (static_cast<RegionPressure&>(P).BottomPos ==
 222           MachineBasicBlock::const_iterator());
 223 }
 224
 225
 226 SlotIndex RegPressureTracker::getCurrSlot() const {
 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.
 236 void RegPressureTracker::closeTop() {
 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());
 245   for (SparseSet<unsigned>::const_iterator I =
 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.
 254 void RegPressureTracker::closeBottom() {
 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());
 263   for (SparseSet<unsigned>::const_iterator I =
 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.
 272 void RegPressureTracker::closeRegion() {
 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.
 289 void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
 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];
 294     if (TargetRegisterInfo::isVirtualRegister(Reg)
 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
 311 class RegisterOperands {
 312   const TargetRegisterInfo *TRI;
 313   const MachineRegisterInfo *MRI;
 314   bool IgnoreDead;
 315
 316 public:
 317   SmallVector<unsigned, 8> Uses;
 318   SmallVector<unsigned, 8> Defs;
 319   SmallVector<unsigned, 8> DeadDefs;
 320
 321   RegisterOperands(const TargetRegisterInfo *tri,
 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) {
 343     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 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.
 365   SmallVectorImpl<unsigned>::iterator I =
 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.
 422 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
 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.
 430 void RegPressureTracker::discoverLiveIn(unsigned Reg) {
 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);
 437   increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg));
 438 }
 439
 440 /// Add Reg to the live out set and increase max pressure.
 441 void RegPressureTracker::discoverLiveOut(unsigned Reg) {
 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);
 448   increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(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.
 456 bool RegPressureTracker::recede(SmallVectorImpl<unsigned> *LiveUses,
 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.
 547 bool RegPressureTracker::advance() {
 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.
 587       lastUse = !TargetRegisterInfo::isVirtualRegister(Reg);
 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.
 616 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
 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.
 700 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
 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.
 748 void RegPressureTracker::
 749 getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
 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.
 816 void RegPressureTracker::
 817 getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
 818                        RegPressureDelta &Delta,
 819                        ArrayRef<PressureChange> CriticalPSets,
 820                        ArrayRef<unsigned> MaxPressureLimit) const {
 821   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 822   for (PressureDiff::const_iterator
 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) {
 879   for (MachineRegisterInfo::use_nodbg_iterator
 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.
 898 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
 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.
 945 void RegPressureTracker::
 946 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 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
 953   bumpDownwardPressure(MI);
 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.
 968 void RegPressureTracker::
 969 getUpwardPressure(const MachineInstr *MI,
 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.
 984 void RegPressureTracker::
 985 getDownwardPressure(const MachineInstr *MI,
 986                     std::vector<unsigned> &PressureResult,
 987                     std::vector<unsigned> &MaxPressureResult) {
 988   // Snapshot pressure.
 989   PressureResult = CurrSetPressure;
 990   MaxPressureResult = P.MaxSetPressure;
 991
 992   bumpDownwardPressure(MI);
 993
 994   // Current pressure becomes the result. Restore current pressure.
 995   P.MaxSetPressure.swap(MaxPressureResult);
 996   CurrSetPressure.swap(PressureResult);
 997 }