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