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