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