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