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