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   for (unsigned i = RegOpers.DeadDefs.size(); i > 0; --i) {
 365     unsigned Reg = RegOpers.DeadDefs[i-1];
 366     if (containsReg(RegOpers.Defs, Reg))
 367       RegOpers.DeadDefs.erase(&RegOpers.DeadDefs[i-1]);
 368   }
 369 }
 370
 371 /// Force liveness of registers.
 372 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
 373   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
 374     if (LiveRegs.insert(Regs[i]))
 375       increaseRegPressure(Regs[i]);
 376   }
 377 }
 378
 379 /// Add Reg to the live in set and increase max pressure.
 380 void RegPressureTracker::discoverLiveIn(unsigned Reg) {
 381   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
 382   if (containsReg(P.LiveInRegs, Reg))
 383     return;
 384
 385   // At live in discovery, unconditionally increase the high water mark.
 386   P.LiveInRegs.push_back(Reg);
 387   P.increase(Reg, TRI, MRI);
 388 }
 389
 390 /// Add Reg to the live out set and increase max pressure.
 391 void RegPressureTracker::discoverLiveOut(unsigned Reg) {
 392   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
 393   if (containsReg(P.LiveOutRegs, Reg))
 394     return;
 395
 396   // At live out discovery, unconditionally increase the high water mark.
 397   P.LiveOutRegs.push_back(Reg);
 398   P.increase(Reg, TRI, MRI);
 399 }
 400
 401 /// Recede across the previous instruction.
 402 bool RegPressureTracker::recede() {
 403   // Check for the top of the analyzable region.
 404   if (CurrPos == MBB->begin()) {
 405     closeRegion();
 406     return false;
 407   }
 408   if (!isBottomClosed())
 409     closeBottom();
 410
 411   // Open the top of the region using block iterators.
 412   if (!RequireIntervals && isTopClosed())
 413     static_cast<RegionPressure&>(P).openTop(CurrPos);
 414
 415   // Find the previous instruction.
 416   do
 417     --CurrPos;
 418   while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
 419
 420   if (CurrPos->isDebugValue()) {
 421     closeRegion();
 422     return false;
 423   }
 424   SlotIndex SlotIdx;
 425   if (RequireIntervals)
 426     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 427
 428   // Open the top of the region using slot indexes.
 429   if (RequireIntervals && isTopClosed())
 430     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
 431
 432   RegisterOperands RegOpers(TRI, MRI);
 433   collectOperands(CurrPos, RegOpers);
 434
 435   // Boost pressure for all dead defs together.
 436   increaseRegPressure(RegOpers.DeadDefs);
 437   decreaseRegPressure(RegOpers.DeadDefs);
 438
 439   // Kill liveness at live defs.
 440   // TODO: consider earlyclobbers?
 441   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
 442     unsigned Reg = RegOpers.Defs[i];
 443     if (LiveRegs.erase(Reg))
 444       decreaseRegPressure(Reg);
 445     else
 446       discoverLiveOut(Reg);
 447   }
 448
 449   // Generate liveness for uses.
 450   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 451     unsigned Reg = RegOpers.Uses[i];
 452     if (!LiveRegs.contains(Reg)) {
 453       // Adjust liveouts if LiveIntervals are available.
 454       if (RequireIntervals) {
 455         const LiveInterval *LI = getInterval(Reg);
 456         if (LI && !LI->killedAt(SlotIdx))
 457           discoverLiveOut(Reg);
 458       }
 459       increaseRegPressure(Reg);
 460       LiveRegs.insert(Reg);
 461     }
 462   }
 463   return true;
 464 }
 465
 466 /// Advance across the current instruction.
 467 bool RegPressureTracker::advance() {
 468   // Check for the bottom of the analyzable region.
 469   if (CurrPos == MBB->end()) {
 470     closeRegion();
 471     return false;
 472   }
 473   if (!isTopClosed())
 474     closeTop();
 475
 476   SlotIndex SlotIdx;
 477   if (RequireIntervals)
 478     SlotIdx = getCurrSlot();
 479
 480   // Open the bottom of the region using slot indexes.
 481   if (isBottomClosed()) {
 482     if (RequireIntervals)
 483       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
 484     else
 485       static_cast<RegionPressure&>(P).openBottom(CurrPos);
 486   }
 487
 488   RegisterOperands RegOpers(TRI, MRI);
 489   collectOperands(CurrPos, RegOpers);
 490
 491   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 492     unsigned Reg = RegOpers.Uses[i];
 493     // Discover live-ins.
 494     bool isLive = LiveRegs.contains(Reg);
 495     if (!isLive)
 496       discoverLiveIn(Reg);
 497     // Kill liveness at last uses.
 498     bool lastUse = false;
 499     if (RequireIntervals) {
 500       const LiveInterval *LI = getInterval(Reg);
 501       lastUse = LI && LI->killedAt(SlotIdx);
 502     }
 503     else {
 504       // Allocatable physregs are always single-use before register rewriting.
 505       lastUse = !TargetRegisterInfo::isVirtualRegister(Reg);
 506     }
 507     if (lastUse && isLive) {
 508       LiveRegs.erase(Reg);
 509       decreaseRegPressure(Reg);
 510     }
 511     else if (!lastUse && !isLive)
 512       increaseRegPressure(Reg);
 513   }
 514
 515   // Generate liveness for defs.
 516   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
 517     unsigned Reg = RegOpers.Defs[i];
 518     if (LiveRegs.insert(Reg))
 519       increaseRegPressure(Reg);
 520   }
 521
 522   // Boost pressure for all dead defs together.
 523   increaseRegPressure(RegOpers.DeadDefs);
 524   decreaseRegPressure(RegOpers.DeadDefs);
 525
 526   // Find the next instruction.
 527   do
 528     ++CurrPos;
 529   while (CurrPos != MBB->end() && CurrPos->isDebugValue());
 530   return true;
 531 }
 532
 533 /// Find the max change in excess pressure across all sets.
 534 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
 535                                        ArrayRef<unsigned> NewPressureVec,
 536                                        RegPressureDelta &Delta,
 537                                        const TargetRegisterInfo *TRI) {
 538   int ExcessUnits = 0;
 539   unsigned PSetID = ~0U;
 540   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 541     unsigned POld = OldPressureVec[i];
 542     unsigned PNew = NewPressureVec[i];
 543     int PDiff = (int)PNew - (int)POld;
 544     if (!PDiff) // No change in this set in the common case.
 545       continue;
 546     // Only consider change beyond the limit.
 547     unsigned Limit = TRI->getRegPressureSetLimit(i);
 548     if (Limit > POld) {
 549       if (Limit > PNew)
 550         PDiff = 0;            // Under the limit
 551       else
 552         PDiff = PNew - Limit; // Just exceeded limit.
 553     }
 554     else if (Limit > PNew)
 555       PDiff = Limit - POld;   // Just obeyed limit.
 556
 557     if (std::abs(PDiff) > std::abs(ExcessUnits)) {
 558       ExcessUnits = PDiff;
 559       PSetID = i;
 560     }
 561   }
 562   Delta.Excess.PSetID = PSetID;
 563   Delta.Excess.UnitIncrease = ExcessUnits;
 564 }
 565
 566 /// Find the max change in max pressure that either surpasses a critical PSet
 567 /// limit or exceeds the current MaxPressureLimit.
 568 ///
 569 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
 570 /// silly. It's done now to demonstrate the concept but will go away with a
 571 /// RegPressureTracker API change to work with pressure differences.
 572 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
 573                                     ArrayRef<unsigned> NewMaxPressureVec,
 574                                     ArrayRef<PressureElement> CriticalPSets,
 575                                     ArrayRef<unsigned> MaxPressureLimit,
 576                                     RegPressureDelta &Delta) {
 577   Delta.CriticalMax = PressureElement();
 578   Delta.CurrentMax = PressureElement();
 579
 580   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 581   for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
 582     unsigned POld = OldMaxPressureVec[i];
 583     unsigned PNew = NewMaxPressureVec[i];
 584     if (PNew == POld) // No change in this set in the common case.
 585       continue;
 586
 587     while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
 588       ++CritIdx;
 589
 590     if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
 591       int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
 592       if (PDiff > Delta.CriticalMax.UnitIncrease) {
 593         Delta.CriticalMax.PSetID = i;
 594         Delta.CriticalMax.UnitIncrease = PDiff;
 595       }
 596     }
 597
 598     // Find the greatest increase above MaxPressureLimit.
 599     // (Ignores negative MDiff).
 600     int MDiff = (int)PNew - (int)MaxPressureLimit[i];
 601     if (MDiff > Delta.CurrentMax.UnitIncrease) {
 602       Delta.CurrentMax.PSetID = i;
 603       Delta.CurrentMax.UnitIncrease = PNew;
 604     }
 605   }
 606 }
 607
 608 /// Record the upward impact of a single instruction on current register
 609 /// pressure. Unlike the advance/recede pressure tracking interface, this does
 610 /// not discover live in/outs.
 611 ///
 612 /// This is intended for speculative queries. It leaves pressure inconsistent
 613 /// with the current position, so must be restored by the caller.
 614 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
 615   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
 616
 617   // Account for register pressure similar to RegPressureTracker::recede().
 618   RegisterOperands RegOpers(TRI, MRI);
 619   collectOperands(MI, RegOpers);
 620
 621   // Boost max pressure for all dead defs together.
 622   // Since CurrSetPressure and MaxSetPressure
 623   increaseRegPressure(RegOpers.DeadDefs);
 624   decreaseRegPressure(RegOpers.DeadDefs);
 625
 626   // Kill liveness at live defs.
 627   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
 628     unsigned Reg = RegOpers.Defs[i];
 629     if (!containsReg(RegOpers.Uses, Reg))
 630       decreaseRegPressure(Reg);
 631   }
 632   // Generate liveness for uses.
 633   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 634     unsigned Reg = RegOpers.Uses[i];
 635     if (!LiveRegs.contains(Reg))
 636       increaseRegPressure(Reg);
 637   }
 638 }
 639
 640 /// Consider the pressure increase caused by traversing this instruction
 641 /// bottom-up. Find the pressure set with the most change beyond its pressure
 642 /// limit based on the tracker's current pressure, and return the change in
 643 /// number of register units of that pressure set introduced by this
 644 /// instruction.
 645 ///
 646 /// This assumes that the current LiveOut set is sufficient.
 647 ///
 648 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
 649 /// result per-SUnit with enough information to adjust for the current
 650 /// scheduling position. But this works as a proof of concept.
 651 void RegPressureTracker::
 652 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 653                           ArrayRef<PressureElement> CriticalPSets,
 654                           ArrayRef<unsigned> MaxPressureLimit) {
 655   // Snapshot Pressure.
 656   // FIXME: The snapshot heap space should persist. But I'm planning to
 657   // summarize the pressure effect so we don't need to snapshot at all.
 658   std::vector<unsigned> SavedPressure = CurrSetPressure;
 659   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 660
 661   bumpUpwardPressure(MI);
 662
 663   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
 664   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 665                           MaxPressureLimit, Delta);
 666   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
 667          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
 668
 669   // Restore the tracker's state.
 670   P.MaxSetPressure.swap(SavedMaxPressure);
 671   CurrSetPressure.swap(SavedPressure);
 672 }
 673
 674 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
 675 static bool findUseBetween(unsigned Reg,
 676                            SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
 677                            const MachineRegisterInfo *MRI,
 678                            const LiveIntervals *LIS) {
 679   for (MachineRegisterInfo::use_nodbg_iterator
 680          UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
 681          UI != UE; UI.skipInstruction()) {
 682       const MachineInstr* MI = &*UI;
 683       if (MI->isDebugValue())
 684         continue;
 685       SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
 686       if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
 687         return true;
 688   }
 689   return false;
 690 }
 691
 692 /// Record the downward impact of a single instruction on current register
 693 /// pressure. Unlike the advance/recede pressure tracking interface, this does
 694 /// not discover live in/outs.
 695 ///
 696 /// This is intended for speculative queries. It leaves pressure inconsistent
 697 /// with the current position, so must be restored by the caller.
 698 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
 699   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
 700
 701   // Account for register pressure similar to RegPressureTracker::recede().
 702   RegisterOperands RegOpers(TRI, MRI);
 703   collectOperands(MI, RegOpers);
 704
 705   // Kill liveness at last uses. Assume allocatable physregs are single-use
 706   // rather than checking LiveIntervals.
 707   SlotIndex SlotIdx;
 708   if (RequireIntervals)
 709     SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
 710
 711   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
 712     unsigned Reg = RegOpers.Uses[i];
 713     if (RequireIntervals) {
 714       // FIXME: allow the caller to pass in the list of vreg uses that remain
 715       // to be bottom-scheduled to avoid searching uses at each query.
 716       SlotIndex CurrIdx = getCurrSlot();
 717       const LiveInterval *LI = getInterval(Reg);
 718       if (LI && LI->killedAt(SlotIdx)
 719           && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
 720         decreaseRegPressure(Reg);
 721       }
 722     }
 723     else if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
 724       // Allocatable physregs are always single-use before register rewriting.
 725       decreaseRegPressure(Reg);
 726     }
 727   }
 728
 729   // Generate liveness for defs.
 730   increaseRegPressure(RegOpers.Defs);
 731
 732   // Boost pressure for all dead defs together.
 733   increaseRegPressure(RegOpers.DeadDefs);
 734   decreaseRegPressure(RegOpers.DeadDefs);
 735 }
 736
 737 /// Consider the pressure increase caused by traversing this instruction
 738 /// top-down. Find the register class with the most change in its pressure limit
 739 /// based on the tracker's current pressure, and return the number of excess
 740 /// register units of that pressure set introduced by this instruction.
 741 ///
 742 /// This assumes that the current LiveIn set is sufficient.
 743 void RegPressureTracker::
 744 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 745                             ArrayRef<PressureElement> CriticalPSets,
 746                             ArrayRef<unsigned> MaxPressureLimit) {
 747   // Snapshot Pressure.
 748   std::vector<unsigned> SavedPressure = CurrSetPressure;
 749   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 750
 751   bumpDownwardPressure(MI);
 752
 753   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
 754   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 755                           MaxPressureLimit, Delta);
 756   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
 757          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
 758
 759   // Restore the tracker's state.
 760   P.MaxSetPressure.swap(SavedMaxPressure);
 761   CurrSetPressure.swap(SavedPressure);
 762 }
 763
 764 /// Get the pressure of each PSet after traversing this instruction bottom-up.
 765 void RegPressureTracker::
 766 getUpwardPressure(const MachineInstr *MI,
 767                   std::vector<unsigned> &PressureResult,
 768                   std::vector<unsigned> &MaxPressureResult) {
 769   // Snapshot pressure.
 770   PressureResult = CurrSetPressure;
 771   MaxPressureResult = P.MaxSetPressure;
 772
 773   bumpUpwardPressure(MI);
 774
 775   // Current pressure becomes the result. Restore current pressure.
 776   P.MaxSetPressure.swap(MaxPressureResult);
 777   CurrSetPressure.swap(PressureResult);
 778 }
 779
 780 /// Get the pressure of each PSet after traversing this instruction top-down.
 781 void RegPressureTracker::
 782 getDownwardPressure(const MachineInstr *MI,
 783                     std::vector<unsigned> &PressureResult,
 784                     std::vector<unsigned> &MaxPressureResult) {
 785   // Snapshot pressure.
 786   PressureResult = CurrSetPressure;
 787   MaxPressureResult = P.MaxSetPressure;
 788
 789   bumpDownwardPressure(MI);
 790
 791   // Current pressure becomes the result. Restore current pressure.
 792   P.MaxSetPressure.swap(MaxPressureResult);
 793   CurrSetPressure.swap(PressureResult);
 794 }