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                                 std::vector<unsigned> &MaxSetPressure,
  29                                 const int *PSet, unsigned Weight) {
  30   for (; *PSet != -1; ++PSet) {
  31     CurrSetPressure[*PSet] += Weight;
  32     if (&CurrSetPressure != &MaxSetPressure
  33         && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) {
  34       MaxSetPressure[*PSet] = CurrSetPressure[*PSet];
  35     }
  36   }
  37 }
  38
  39 /// Decrease pressure for each pressure set provided by TargetRegisterInfo.
  40 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
  41                                 const int *PSet, unsigned Weight) {
  42   for (; *PSet != -1; ++PSet) {
  43     assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow");
  44     CurrSetPressure[*PSet] -= Weight;
  45   }
  46 }
  47
  48 /// Directly increase pressure only within this RegisterPressure result.
  49 void RegisterPressure::increase(unsigned Reg, const TargetRegisterInfo *TRI,
  50                                 const MachineRegisterInfo *MRI) {
  51   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
  52     const TargetRegisterClass *RC = MRI->getRegClass(Reg);
  53     increaseSetPressure(MaxSetPressure, MaxSetPressure,
  54                         TRI->getRegClassPressureSets(RC),
  55                         TRI->getRegClassWeight(RC).RegWeight);
  56   }
  57   else {
  58     increaseSetPressure(MaxSetPressure, MaxSetPressure,
  59                         TRI->getRegUnitPressureSets(Reg),
  60                         TRI->getRegUnitWeight(Reg));
  61   }
  62 }
  63
  64 /// Directly decrease pressure only within this RegisterPressure result.
  65 void RegisterPressure::decrease(unsigned Reg, const TargetRegisterInfo *TRI,
  66                                 const MachineRegisterInfo *MRI) {
  67   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
  68     const TargetRegisterClass *RC = MRI->getRegClass(Reg);
  69     decreaseSetPressure(MaxSetPressure, TRI->getRegClassPressureSets(RC),
  70                         TRI->getRegClassWeight(RC).RegWeight);
  71   }
  72   else {
  73     decreaseSetPressure(MaxSetPressure, TRI->getRegUnitPressureSets(Reg),
  74                         TRI->getRegUnitWeight(Reg));
  75   }
  76 }
  77
  78 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  79 void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
  80                               const TargetRegisterInfo *TRI) {
  81   bool Empty = true;
  82   for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
  83     if (SetPressure[i] != 0) {
  84       dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
  85       Empty = false;
  86     }
  87   }
  88   if (Empty)
  89     dbgs() << "\n";
  90 }
  91
  92 void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
  93   dbgs() << "Max Pressure: ";
  94   dumpRegSetPressure(MaxSetPressure, TRI);
  95   dbgs() << "Live In: ";
  96   for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i)
  97     dbgs() << PrintReg(LiveInRegs[i], TRI) << " ";
  98   dbgs() << '\n';
  99   dbgs() << "Live Out: ";
 100   for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i)
 101     dbgs() << PrintReg(LiveOutRegs[i], TRI) << " ";
 102   dbgs() << '\n';
 103 }
 104
 105 void RegPressureTracker::dump() const {
 106   if (!isTopClosed() || !isBottomClosed()) {
 107     dbgs() << "Curr Pressure: ";
 108     dumpRegSetPressure(CurrSetPressure, TRI);
 109   }
 110   P.dump(TRI);
 111 }
 112 #endif
 113
 114 /// Increase the current pressure as impacted by these registers and bump
 115 /// the high water mark if needed.
 116 void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> Regs) {
 117   for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
 118     if (TargetRegisterInfo::isVirtualRegister(Regs[I])) {
 119       const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
 120       increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
 121                           TRI->getRegClassPressureSets(RC),
 122                           TRI->getRegClassWeight(RC).RegWeight);
 123     }
 124     else {
 125       increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
 126                           TRI->getRegUnitPressureSets(Regs[I]),
 127                           TRI->getRegUnitWeight(Regs[I]));
 128     }
 129   }
 130 }
 131
 132 /// Simply decrease the current pressure as impacted by these registers.
 133 void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> Regs) {
 134   for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
 135     if (TargetRegisterInfo::isVirtualRegister(Regs[I])) {
 136       const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
 137       decreaseSetPressure(CurrSetPressure,
 138                           TRI->getRegClassPressureSets(RC),
 139                           TRI->getRegClassWeight(RC).RegWeight);
 140     }
 141     else {
 142       decreaseSetPressure(CurrSetPressure, TRI->getRegUnitPressureSets(Regs[I]),
 143                           TRI->getRegUnitWeight(Regs[I]));
 144     }
 145   }
 146 }
 147
 148 /// Clear the result so it can be used for another round of pressure tracking.
 149 void IntervalPressure::reset() {
 150   TopIdx = BottomIdx = SlotIndex();
 151   MaxSetPressure.clear();
 152   LiveInRegs.clear();
 153   LiveOutRegs.clear();
 154 }
 155
 156 /// Clear the result so it can be used for another round of pressure tracking.
 157 void RegionPressure::reset() {
 158   TopPos = BottomPos = MachineBasicBlock::const_iterator();
 159   MaxSetPressure.clear();
 160   LiveInRegs.clear();
 161   LiveOutRegs.clear();
 162 }
 163
 164 /// If the current top is not less than or equal to the next index, open it.
 165 /// We happen to need the SlotIndex for the next top for pressure update.
 166 void IntervalPressure::openTop(SlotIndex NextTop) {
 167   if (TopIdx <= NextTop)
 168     return;
 169   TopIdx = SlotIndex();
 170   LiveInRegs.clear();
 171 }
 172
 173 /// If the current top is the previous instruction (before receding), open it.
 174 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
 175   if (TopPos != PrevTop)
 176     return;
 177   TopPos = MachineBasicBlock::const_iterator();
 178   LiveInRegs.clear();
 179 }
 180
 181 /// If the current bottom is not greater than the previous index, open it.
 182 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
 183   if (BottomIdx > PrevBottom)
 184     return;
 185   BottomIdx = SlotIndex();
 186   LiveInRegs.clear();
 187 }
 188
 189 /// If the current bottom is the previous instr (before advancing), open it.
 190 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
 191   if (BottomPos != PrevBottom)
 192     return;
 193   BottomPos = MachineBasicBlock::const_iterator();
 194   LiveInRegs.clear();
 195 }
 196
 197 const LiveInterval *RegPressureTracker::getInterval(unsigned Reg) const {
 198   if (TargetRegisterInfo::isVirtualRegister(Reg))
 199     return &LIS->getInterval(Reg);
 200   return LIS->getCachedRegUnit(Reg);
 201 }
 202
 203 /// Setup the RegPressureTracker.
 204 ///
 205 /// TODO: Add support for pressure without LiveIntervals.
 206 void RegPressureTracker::init(const MachineFunction *mf,
 207                               const RegisterClassInfo *rci,
 208                               const LiveIntervals *lis,
 209                               const MachineBasicBlock *mbb,
 210                               MachineBasicBlock::const_iterator pos,
 211                               bool ShouldTrackUntiedDefs)
 212 {
 213   MF = mf;
 214   TRI = MF->getTarget().getRegisterInfo();
 215   RCI = rci;
 216   MRI = &MF->getRegInfo();
 217   MBB = mbb;
 218   TrackUntiedDefs = ShouldTrackUntiedDefs;
 219
 220   if (RequireIntervals) {
 221     assert(lis && "IntervalPressure requires LiveIntervals");
 222     LIS = lis;
 223   }
 224
 225   CurrPos = pos;
 226   CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
 227   LiveThruPressure.clear();
 228
 229   if (RequireIntervals)
 230     static_cast<IntervalPressure&>(P).reset();
 231   else
 232     static_cast<RegionPressure&>(P).reset();
 233   P.MaxSetPressure = CurrSetPressure;
 234
 235   LiveRegs.PhysRegs.clear();
 236   LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs());
 237   LiveRegs.VirtRegs.clear();
 238   LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs());
 239   UntiedDefs.clear();
 240   if (TrackUntiedDefs)
 241     UntiedDefs.setUniverse(MRI->getNumVirtRegs());
 242 }
 243
 244 /// Does this pressure result have a valid top position and live ins.
 245 bool RegPressureTracker::isTopClosed() const {
 246   if (RequireIntervals)
 247     return static_cast<IntervalPressure&>(P).TopIdx.isValid();
 248   return (static_cast<RegionPressure&>(P).TopPos ==
 249           MachineBasicBlock::const_iterator());
 250 }
 251
 252 /// Does this pressure result have a valid bottom position and live outs.
 253 bool RegPressureTracker::isBottomClosed() const {
 254   if (RequireIntervals)
 255     return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
 256   return (static_cast<RegionPressure&>(P).BottomPos ==
 257           MachineBasicBlock::const_iterator());
 258 }
 259
 260
 261 SlotIndex RegPressureTracker::getCurrSlot() const {
 262   MachineBasicBlock::const_iterator IdxPos = CurrPos;
 263   while (IdxPos != MBB->end() && IdxPos->isDebugValue())
 264     ++IdxPos;
 265   if (IdxPos == MBB->end())
 266     return LIS->getMBBEndIdx(MBB);
 267   return LIS->getInstructionIndex(IdxPos).getRegSlot();
 268 }
 269
 270 /// Set the boundary for the top of the region and summarize live ins.
 271 void RegPressureTracker::closeTop() {
 272   if (RequireIntervals)
 273     static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
 274   else
 275     static_cast<RegionPressure&>(P).TopPos = CurrPos;
 276
 277   assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
 278   P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
 279   P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
 280   for (SparseSet<unsigned>::const_iterator I =
 281          LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
 282     P.LiveInRegs.push_back(*I);
 283   std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
 284   P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
 285                      P.LiveInRegs.end());
 286 }
 287
 288 /// Set the boundary for the bottom of the region and summarize live outs.
 289 void RegPressureTracker::closeBottom() {
 290   if (RequireIntervals)
 291     static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
 292   else
 293     static_cast<RegionPressure&>(P).BottomPos = CurrPos;
 294
 295   assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
 296   P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
 297   P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
 298   for (SparseSet<unsigned>::const_iterator I =
 299          LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
 300     P.LiveOutRegs.push_back(*I);
 301   std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
 302   P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
 303                       P.LiveOutRegs.end());
 304 }
 305
 306 /// Finalize the region boundaries and record live ins and live outs.
 307 void RegPressureTracker::closeRegion() {
 308   if (!isTopClosed() && !isBottomClosed()) {
 309     assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() &&
 310            "no region boundary");
 311     return;
 312   }
 313   if (!isBottomClosed())
 314     closeBottom();
 315   else if (!isTopClosed())
 316     closeTop();
 317   // If both top and bottom are closed, do nothing.
 318 }
 319
 320 /// The register tracker is unaware of global liveness so ignores normal
 321 /// live-thru ranges. However, two-address or coalesced chains can also lead
 322 /// to live ranges with no holes. Count these to inform heuristics that we
 323 /// can never drop below this pressure.
 324 void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
 325   LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
 326   assert(isBottomClosed() && "need bottom-up tracking to intialize.");
 327   for (unsigned i = 0, e = P.LiveOutRegs.size(); i < e; ++i) {
 328     unsigned Reg = P.LiveOutRegs[i];
 329     if (TargetRegisterInfo::isVirtualRegister(Reg)
 330         && !RPTracker.hasUntiedDef(Reg)) {
 331       const TargetRegisterClass *RC = MRI->getRegClass(Reg);
 332       increaseSetPressure(LiveThruPressure, LiveThruPressure,
 333                           TRI->getRegClassPressureSets(RC),
 334                           TRI->getRegClassWeight(RC).RegWeight);
 335     }
 336   }
 337 }
 338
 339 /// \brief Convenient wrapper for checking membership in RegisterOperands.
 340 static bool containsReg(ArrayRef<unsigned> Regs, unsigned Reg) {
 341   return std::find(Regs.begin(), Regs.end(), Reg) != Regs.end();
 342 }
 343
 344 /// Collect this instruction's unique uses and defs into SmallVectors for
 345 /// processing defs and uses in order.
 346 class RegisterOperands {
 347   const TargetRegisterInfo *TRI;
 348   const MachineRegisterInfo *MRI;
 349
 350 public:
 351   SmallVector<unsigned, 8> Uses;
 352   SmallVector<unsigned, 8> Defs;
 353   SmallVector<unsigned, 8> DeadDefs;
 354
 355   RegisterOperands(const TargetRegisterInfo *tri,
 356                    const MachineRegisterInfo *mri): TRI(tri), MRI(mri) {}
 357
 358   /// Push this operand's register onto the correct vector.
 359   void collect(const MachineOperand &MO) {
 360     if (!MO.isReg() || !MO.getReg())
 361       return;
 362     if (MO.readsReg())
 363       pushRegUnits(MO.getReg(), Uses);
 364     if (MO.isDef()) {
 365       if (MO.isDead())
 366         pushRegUnits(MO.getReg(), DeadDefs);
 367       else
 368         pushRegUnits(MO.getReg(), Defs);
 369     }
 370   }
 371
 372 protected:
 373   void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &Regs) {
 374     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 375       if (containsReg(Regs, Reg))
 376         return;
 377       Regs.push_back(Reg);
 378     }
 379     else if (MRI->isAllocatable(Reg)) {
 380       for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
 381         if (containsReg(Regs, *Units))
 382           continue;
 383         Regs.push_back(*Units);
 384       }
 385     }
 386   }
 387 };
 388
 389 /// Collect physical and virtual register operands.
 390 static void collectOperands(const MachineInstr *MI,
 391                             RegisterOperands &RegOpers) {
 392   for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
 393     RegOpers.collect(*OperI);
 394
 395   // Remove redundant physreg dead defs.
 396   SmallVectorImpl<unsigned>::iterator I =
 397     std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(),
 398                    std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs));
 399   RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end());
 400 }
 401
 402 /// Force liveness of registers.
 403 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
 404   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
 405     if (LiveRegs.insert(Regs[i]))
 406       increaseRegPressure(Regs[i]);
 407   }
 408 }
 409
 410 /// Add Reg to the live in set and increase max pressure.
 411 void RegPressureTracker::discoverLiveIn(unsigned Reg) {
 412   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
 413   if (containsReg(P.LiveInRegs, Reg))
 414     return;
 415
 416   // At live in discovery, unconditionally increase the high water mark.
 417   P.LiveInRegs.push_back(Reg);
 418   P.increase(Reg, TRI, MRI);
 419 }
 420
 421 /// Add Reg to the live out set and increase max pressure.
 422 void RegPressureTracker::discoverLiveOut(unsigned Reg) {
 423   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
 424   if (containsReg(P.LiveOutRegs, Reg))
 425     return;
 426
 427   // At live out discovery, unconditionally increase the high water mark.
 428   P.LiveOutRegs.push_back(Reg);
 429   P.increase(Reg, TRI, MRI);
 430 }
 431
 432 /// Recede across the previous instruction.
 433 bool RegPressureTracker::recede() {
 434   // Check for the top of the analyzable region.
 435   if (CurrPos == MBB->begin()) {
 436     closeRegion();
 437     return false;
 438   }
 439   if (!isBottomClosed())
 440     closeBottom();
 441
 442   // Open the top of the region using block iterators.
 443   if (!RequireIntervals && isTopClosed())
 444     static_cast<RegionPressure&>(P).openTop(CurrPos);
 445
 446   // Find the previous instruction.
 447   do
 448     --CurrPos;
 449   while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
 450
 451   if (CurrPos->isDebugValue()) {
 452     closeRegion();
 453     return false;
 454   }
 455   SlotIndex SlotIdx;
 456   if (RequireIntervals)
 457     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 458
 459   // Open the top of the region using slot indexes.
 460   if (RequireIntervals && isTopClosed())
 461     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
 462
 463   RegisterOperands RegOpers(TRI, MRI);
 464   collectOperands(CurrPos, RegOpers);
 465
 466   // Boost pressure for all dead defs together.
 467   increaseRegPressure(RegOpers.DeadDefs);
 468   decreaseRegPressure(RegOpers.DeadDefs);
 469
 470   // Kill liveness at live defs.
 471   // TODO: consider earlyclobbers?
 472   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
 473     unsigned Reg = RegOpers.Defs[i];
 474     if (LiveRegs.erase(Reg))
 475       decreaseRegPressure(Reg);
 476     else
 477       discoverLiveOut(Reg);
 478   }
 479
 480   // Generate liveness for uses.
 481   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 482     unsigned Reg = RegOpers.Uses[i];
 483     if (!LiveRegs.contains(Reg)) {
 484       // Adjust liveouts if LiveIntervals are available.
 485       if (RequireIntervals) {
 486         const LiveInterval *LI = getInterval(Reg);
 487         if (LI && !LI->killedAt(SlotIdx))
 488           discoverLiveOut(Reg);
 489       }
 490       increaseRegPressure(Reg);
 491       LiveRegs.insert(Reg);
 492     }
 493   }
 494   if (TrackUntiedDefs) {
 495     for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
 496       unsigned Reg = RegOpers.Defs[i];
 497       if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg))
 498         UntiedDefs.insert(Reg);
 499     }
 500   }
 501   return true;
 502 }
 503
 504 /// Advance across the current instruction.
 505 bool RegPressureTracker::advance() {
 506   assert(!TrackUntiedDefs && "unsupported mode");
 507
 508   // Check for the bottom of the analyzable region.
 509   if (CurrPos == MBB->end()) {
 510     closeRegion();
 511     return false;
 512   }
 513   if (!isTopClosed())
 514     closeTop();
 515
 516   SlotIndex SlotIdx;
 517   if (RequireIntervals)
 518     SlotIdx = getCurrSlot();
 519
 520   // Open the bottom of the region using slot indexes.
 521   if (isBottomClosed()) {
 522     if (RequireIntervals)
 523       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
 524     else
 525       static_cast<RegionPressure&>(P).openBottom(CurrPos);
 526   }
 527
 528   RegisterOperands RegOpers(TRI, MRI);
 529   collectOperands(CurrPos, RegOpers);
 530
 531   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 532     unsigned Reg = RegOpers.Uses[i];
 533     // Discover live-ins.
 534     bool isLive = LiveRegs.contains(Reg);
 535     if (!isLive)
 536       discoverLiveIn(Reg);
 537     // Kill liveness at last uses.
 538     bool lastUse = false;
 539     if (RequireIntervals) {
 540       const LiveInterval *LI = getInterval(Reg);
 541       lastUse = LI && LI->killedAt(SlotIdx);
 542     }
 543     else {
 544       // Allocatable physregs are always single-use before register rewriting.
 545       lastUse = !TargetRegisterInfo::isVirtualRegister(Reg);
 546     }
 547     if (lastUse && isLive) {
 548       LiveRegs.erase(Reg);
 549       decreaseRegPressure(Reg);
 550     }
 551     else if (!lastUse && !isLive)
 552       increaseRegPressure(Reg);
 553   }
 554
 555   // Generate liveness for defs.
 556   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
 557     unsigned Reg = RegOpers.Defs[i];
 558     if (LiveRegs.insert(Reg))
 559       increaseRegPressure(Reg);
 560   }
 561
 562   // Boost pressure for all dead defs together.
 563   increaseRegPressure(RegOpers.DeadDefs);
 564   decreaseRegPressure(RegOpers.DeadDefs);
 565
 566   // Find the next instruction.
 567   do
 568     ++CurrPos;
 569   while (CurrPos != MBB->end() && CurrPos->isDebugValue());
 570   return true;
 571 }
 572
 573 /// Find the max change in excess pressure across all sets.
 574 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
 575                                        ArrayRef<unsigned> NewPressureVec,
 576                                        RegPressureDelta &Delta,
 577                                        const RegisterClassInfo *RCI,
 578                                        ArrayRef<unsigned> LiveThruPressureVec) {
 579   int ExcessUnits = 0;
 580   unsigned PSetID = ~0U;
 581   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 582     unsigned POld = OldPressureVec[i];
 583     unsigned PNew = NewPressureVec[i];
 584     int PDiff = (int)PNew - (int)POld;
 585     if (!PDiff) // No change in this set in the common case.
 586       continue;
 587     // Only consider change beyond the limit.
 588     unsigned Limit = RCI->getRegPressureSetLimit(i);
 589     if (!LiveThruPressureVec.empty())
 590       Limit += LiveThruPressureVec[i];
 591
 592     if (Limit > POld) {
 593       if (Limit > PNew)
 594         PDiff = 0;            // Under the limit
 595       else
 596         PDiff = PNew - Limit; // Just exceeded limit.
 597     }
 598     else if (Limit > PNew)
 599       PDiff = Limit - POld;   // Just obeyed limit.
 600
 601     if (PDiff) {
 602       ExcessUnits = PDiff;
 603       PSetID = i;
 604       break;
 605     }
 606   }
 607   Delta.Excess.PSetID = PSetID;
 608   Delta.Excess.UnitIncrease = ExcessUnits;
 609 }
 610
 611 /// Find the max change in max pressure that either surpasses a critical PSet
 612 /// limit or exceeds the current MaxPressureLimit.
 613 ///
 614 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
 615 /// silly. It's done now to demonstrate the concept but will go away with a
 616 /// RegPressureTracker API change to work with pressure differences.
 617 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
 618                                     ArrayRef<unsigned> NewMaxPressureVec,
 619                                     ArrayRef<PressureElement> CriticalPSets,
 620                                     ArrayRef<unsigned> MaxPressureLimit,
 621                                     RegPressureDelta &Delta) {
 622   Delta.CriticalMax = PressureElement();
 623   Delta.CurrentMax = PressureElement();
 624
 625   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 626   for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
 627     unsigned POld = OldMaxPressureVec[i];
 628     unsigned PNew = NewMaxPressureVec[i];
 629     if (PNew == POld) // No change in this set in the common case.
 630       continue;
 631
 632     if (!Delta.CriticalMax.isValid()) {
 633       while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
 634         ++CritIdx;
 635
 636       if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
 637         int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
 638         if (PDiff > 0) {
 639           Delta.CriticalMax.PSetID = i;
 640           Delta.CriticalMax.UnitIncrease = PDiff;
 641         }
 642       }
 643     }
 644     // Find the first increase above MaxPressureLimit.
 645     // (Ignores negative MDiff).
 646     if (!Delta.CurrentMax.isValid()) {
 647       int MDiff = (int)PNew - (int)MaxPressureLimit[i];
 648       if (MDiff > 0) {
 649         Delta.CurrentMax.PSetID = i;
 650         Delta.CurrentMax.UnitIncrease = MDiff;
 651         if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
 652           break;
 653       }
 654     }
 655   }
 656 }
 657
 658 /// Record the upward impact of a single instruction on current register
 659 /// pressure. Unlike the advance/recede pressure tracking interface, this does
 660 /// not discover live in/outs.
 661 ///
 662 /// This is intended for speculative queries. It leaves pressure inconsistent
 663 /// with the current position, so must be restored by the caller.
 664 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
 665   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
 666
 667   // Account for register pressure similar to RegPressureTracker::recede().
 668   RegisterOperands RegOpers(TRI, MRI);
 669   collectOperands(MI, RegOpers);
 670
 671   // Boost max pressure for all dead defs together.
 672   // Since CurrSetPressure and MaxSetPressure
 673   increaseRegPressure(RegOpers.DeadDefs);
 674   decreaseRegPressure(RegOpers.DeadDefs);
 675
 676   // Kill liveness at live defs.
 677   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
 678     unsigned Reg = RegOpers.Defs[i];
 679     if (!containsReg(RegOpers.Uses, Reg))
 680       decreaseRegPressure(Reg);
 681   }
 682   // Generate liveness for uses.
 683   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 684     unsigned Reg = RegOpers.Uses[i];
 685     if (!LiveRegs.contains(Reg))
 686       increaseRegPressure(Reg);
 687   }
 688 }
 689
 690 /// Consider the pressure increase caused by traversing this instruction
 691 /// bottom-up. Find the pressure set with the most change beyond its pressure
 692 /// limit based on the tracker's current pressure, and return the change in
 693 /// number of register units of that pressure set introduced by this
 694 /// instruction.
 695 ///
 696 /// This assumes that the current LiveOut set is sufficient.
 697 ///
 698 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
 699 /// result per-SUnit with enough information to adjust for the current
 700 /// scheduling position. But this works as a proof of concept.
 701 void RegPressureTracker::
 702 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 703                           ArrayRef<PressureElement> CriticalPSets,
 704                           ArrayRef<unsigned> MaxPressureLimit) {
 705   // Snapshot Pressure.
 706   // FIXME: The snapshot heap space should persist. But I'm planning to
 707   // summarize the pressure effect so we don't need to snapshot at all.
 708   std::vector<unsigned> SavedPressure = CurrSetPressure;
 709   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 710
 711   bumpUpwardPressure(MI);
 712
 713   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
 714                              LiveThruPressure);
 715   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 716                           MaxPressureLimit, Delta);
 717   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
 718          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
 719
 720   // Restore the tracker's state.
 721   P.MaxSetPressure.swap(SavedMaxPressure);
 722   CurrSetPressure.swap(SavedPressure);
 723 }
 724
 725 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
 726 static bool findUseBetween(unsigned Reg,
 727                            SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
 728                            const MachineRegisterInfo *MRI,
 729                            const LiveIntervals *LIS) {
 730   for (MachineRegisterInfo::use_nodbg_iterator
 731          UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
 732          UI != UE; UI.skipInstruction()) {
 733       const MachineInstr* MI = &*UI;
 734       if (MI->isDebugValue())
 735         continue;
 736       SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
 737       if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
 738         return true;
 739   }
 740   return false;
 741 }
 742
 743 /// Record the downward impact of a single instruction on current register
 744 /// pressure. Unlike the advance/recede pressure tracking interface, this does
 745 /// not discover live in/outs.
 746 ///
 747 /// This is intended for speculative queries. It leaves pressure inconsistent
 748 /// with the current position, so must be restored by the caller.
 749 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
 750   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
 751
 752   // Account for register pressure similar to RegPressureTracker::recede().
 753   RegisterOperands RegOpers(TRI, MRI);
 754   collectOperands(MI, RegOpers);
 755
 756   // Kill liveness at last uses. Assume allocatable physregs are single-use
 757   // rather than checking LiveIntervals.
 758   SlotIndex SlotIdx;
 759   if (RequireIntervals)
 760     SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
 761
 762   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 763     unsigned Reg = RegOpers.Uses[i];
 764     if (RequireIntervals) {
 765       // FIXME: allow the caller to pass in the list of vreg uses that remain
 766       // to be bottom-scheduled to avoid searching uses at each query.
 767       SlotIndex CurrIdx = getCurrSlot();
 768       const LiveInterval *LI = getInterval(Reg);
 769       if (LI && LI->killedAt(SlotIdx)
 770           && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
 771         decreaseRegPressure(Reg);
 772       }
 773     }
 774     else if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
 775       // Allocatable physregs are always single-use before register rewriting.
 776       decreaseRegPressure(Reg);
 777     }
 778   }
 779
 780   // Generate liveness for defs.
 781   increaseRegPressure(RegOpers.Defs);
 782
 783   // Boost pressure for all dead defs together.
 784   increaseRegPressure(RegOpers.DeadDefs);
 785   decreaseRegPressure(RegOpers.DeadDefs);
 786 }
 787
 788 /// Consider the pressure increase caused by traversing this instruction
 789 /// top-down. Find the register class with the most change in its pressure limit
 790 /// based on the tracker's current pressure, and return the number of excess
 791 /// register units of that pressure set introduced by this instruction.
 792 ///
 793 /// This assumes that the current LiveIn set is sufficient.
 794 void RegPressureTracker::
 795 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 796                             ArrayRef<PressureElement> CriticalPSets,
 797                             ArrayRef<unsigned> MaxPressureLimit) {
 798   // Snapshot Pressure.
 799   std::vector<unsigned> SavedPressure = CurrSetPressure;
 800   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 801
 802   bumpDownwardPressure(MI);
 803
 804   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
 805                              LiveThruPressure);
 806   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 807                           MaxPressureLimit, Delta);
 808   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
 809          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
 810
 811   // Restore the tracker's state.
 812   P.MaxSetPressure.swap(SavedMaxPressure);
 813   CurrSetPressure.swap(SavedPressure);
 814 }
 815
 816 /// Get the pressure of each PSet after traversing this instruction bottom-up.
 817 void RegPressureTracker::
 818 getUpwardPressure(const MachineInstr *MI,
 819                   std::vector<unsigned> &PressureResult,
 820                   std::vector<unsigned> &MaxPressureResult) {
 821   // Snapshot pressure.
 822   PressureResult = CurrSetPressure;
 823   MaxPressureResult = P.MaxSetPressure;
 824
 825   bumpUpwardPressure(MI);
 826
 827   // Current pressure becomes the result. Restore current pressure.
 828   P.MaxSetPressure.swap(MaxPressureResult);
 829   CurrSetPressure.swap(PressureResult);
 830 }
 831
 832 /// Get the pressure of each PSet after traversing this instruction top-down.
 833 void RegPressureTracker::
 834 getDownwardPressure(const MachineInstr *MI,
 835                     std::vector<unsigned> &PressureResult,
 836                     std::vector<unsigned> &MaxPressureResult) {
 837   // Snapshot pressure.
 838   PressureResult = CurrSetPressure;
 839   MaxPressureResult = P.MaxSetPressure;
 840
 841   bumpDownwardPressure(MI);
 842
 843   // Current pressure becomes the result. Restore current pressure.
 844   P.MaxSetPressure.swap(MaxPressureResult);
 845   CurrSetPressure.swap(PressureResult);
 846 }