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