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 "RegisterClassInfo.h"
  16 #include "RegisterPressure.h"
  17 #include "llvm/CodeGen/LiveInterval.h"
  18 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  19 #include "llvm/CodeGen/MachineRegisterInfo.h"
  20 #include "llvm/Target/TargetMachine.h"
  21
  22 using namespace llvm;
  23
  24 /// Increase register pressure for each set impacted by this register class.
  25 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
  26                                 std::vector<unsigned> &MaxSetPressure,
  27                                 const TargetRegisterClass *RC,
  28                                 const TargetRegisterInfo *TRI) {
  29   unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
  30   for (const int *PSet = TRI->getRegClassPressureSets(RC);
  31        *PSet != -1; ++PSet) {
  32     CurrSetPressure[*PSet] += Weight;
  33     if (&CurrSetPressure != &MaxSetPressure
  34         && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) {
  35       MaxSetPressure[*PSet] = CurrSetPressure[*PSet];
  36     }
  37   }
  38 }
  39
  40 /// Decrease register pressure for each set impacted by this register class.
  41 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
  42                                 const TargetRegisterClass *RC,
  43                                 const TargetRegisterInfo *TRI) {
  44   unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
  45   for (const int *PSet = TRI->getRegClassPressureSets(RC);
  46        *PSet != -1; ++PSet) {
  47     assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow");
  48     CurrSetPressure[*PSet] -= Weight;
  49   }
  50 }
  51
  52 /// Directly increase pressure only within this RegisterPressure result.
  53 void RegisterPressure::increase(const TargetRegisterClass *RC,
  54                                 const TargetRegisterInfo *TRI) {
  55   increaseSetPressure(MaxSetPressure, MaxSetPressure, RC, TRI);
  56 }
  57
  58 /// Directly decrease pressure only within this RegisterPressure result.
  59 void RegisterPressure::decrease(const TargetRegisterClass *RC,
  60                                 const TargetRegisterInfo *TRI) {
  61   decreaseSetPressure(MaxSetPressure, RC, TRI);
  62 }
  63
  64 /// Increase the current pressure as impacted by these physical registers and
  65 /// bump the high water mark if needed.
  66 void RegPressureTracker::increasePhysRegPressure(ArrayRef<unsigned> Regs) {
  67   for (unsigned I = 0, E = Regs.size(); I != E; ++I)
  68     increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
  69                         TRI->getMinimalPhysRegClass(Regs[I]), TRI);
  70 }
  71
  72 /// Simply decrease the current pressure as impacted by these physcial
  73 /// registers.
  74 void RegPressureTracker::decreasePhysRegPressure(ArrayRef<unsigned> Regs) {
  75   for (unsigned I = 0, E = Regs.size(); I != E; ++I)
  76     decreaseSetPressure(CurrSetPressure, TRI->getMinimalPhysRegClass(Regs[I]),
  77                         TRI);
  78 }
  79
  80 /// Increase the current pressure as impacted by these virtual registers and
  81 /// bump the high water mark if needed.
  82 void RegPressureTracker::increaseVirtRegPressure(ArrayRef<unsigned> Regs) {
  83   for (unsigned I = 0, E = Regs.size(); I != E; ++I)
  84     increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
  85                         MRI->getRegClass(Regs[I]), TRI);
  86 }
  87
  88 /// Simply decrease the current pressure as impacted by these virtual registers.
  89 void RegPressureTracker::decreaseVirtRegPressure(ArrayRef<unsigned> Regs) {
  90   for (unsigned I = 0, E = Regs.size(); I != E; ++I)
  91     decreaseSetPressure(CurrSetPressure, MRI->getRegClass(Regs[I]), TRI);
  92 }
  93
  94 /// Clear the result so it can be used for another round of pressure tracking.
  95 void IntervalPressure::reset() {
  96   TopIdx = BottomIdx = SlotIndex();
  97   MaxSetPressure.clear();
  98   LiveInRegs.clear();
  99   LiveOutRegs.clear();
 100 }
 101
 102 /// Clear the result so it can be used for another round of pressure tracking.
 103 void RegionPressure::reset() {
 104   TopPos = BottomPos = MachineBasicBlock::const_iterator();
 105   MaxSetPressure.clear();
 106   LiveInRegs.clear();
 107   LiveOutRegs.clear();
 108 }
 109
 110 /// If the current top is not less than or equal to the next index, open it.
 111 /// We happen to need the SlotIndex for the next top for pressure update.
 112 void IntervalPressure::openTop(SlotIndex NextTop) {
 113   if (TopIdx <= NextTop)
 114     return;
 115   TopIdx = SlotIndex();
 116   LiveInRegs.clear();
 117 }
 118
 119 /// If the current top is the previous instruction (before receding), open it.
 120 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
 121   if (TopPos != PrevTop)
 122     return;
 123   TopPos = MachineBasicBlock::const_iterator();
 124   LiveInRegs.clear();
 125 }
 126
 127 /// If the current bottom is not greater than the previous index, open it.
 128 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
 129   if (BottomIdx > PrevBottom)
 130     return;
 131   BottomIdx = SlotIndex();
 132   LiveInRegs.clear();
 133 }
 134
 135 /// If the current bottom is the previous instr (before advancing), open it.
 136 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
 137   if (BottomPos != PrevBottom)
 138     return;
 139   BottomPos = MachineBasicBlock::const_iterator();
 140   LiveInRegs.clear();
 141 }
 142
 143 /// Setup the RegPressureTracker.
 144 ///
 145 /// TODO: Add support for pressure without LiveIntervals.
 146 void RegPressureTracker::init(const MachineFunction *mf,
 147                               const RegisterClassInfo *rci,
 148                               const LiveIntervals *lis,
 149                               const MachineBasicBlock *mbb,
 150                               MachineBasicBlock::const_iterator pos)
 151 {
 152   MF = mf;
 153   TRI = MF->getTarget().getRegisterInfo();
 154   RCI = rci;
 155   MRI = &MF->getRegInfo();
 156   MBB = mbb;
 157
 158   if (RequireIntervals) {
 159     assert(lis && "IntervalPressure requires LiveIntervals");
 160     LIS = lis;
 161   }
 162
 163   CurrPos = pos;
 164   while (CurrPos != MBB->end() && CurrPos->isDebugValue())
 165     ++CurrPos;
 166
 167   CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
 168
 169   if (RequireIntervals)
 170     static_cast<IntervalPressure&>(P).reset();
 171   else
 172     static_cast<RegionPressure&>(P).reset();
 173   P.MaxSetPressure = CurrSetPressure;
 174
 175   LivePhysRegs.clear();
 176   LivePhysRegs.setUniverse(TRI->getNumRegs());
 177   LiveVirtRegs.clear();
 178   LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
 179 }
 180
 181 /// Does this pressure result have a valid top position and live ins.
 182 bool RegPressureTracker::isTopClosed() const {
 183   if (RequireIntervals)
 184     return static_cast<IntervalPressure&>(P).TopIdx.isValid();
 185   return (static_cast<RegionPressure&>(P).TopPos ==
 186           MachineBasicBlock::const_iterator());
 187 }
 188
 189 /// Does this pressure result have a valid bottom position and live outs.
 190 bool RegPressureTracker::isBottomClosed() const {
 191   if (RequireIntervals)
 192     return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
 193   return (static_cast<RegionPressure&>(P).BottomPos ==
 194           MachineBasicBlock::const_iterator());
 195 }
 196
 197 /// Set the boundary for the top of the region and summarize live ins.
 198 void RegPressureTracker::closeTop() {
 199   if (RequireIntervals)
 200     static_cast<IntervalPressure&>(P).TopIdx =
 201       LIS->getInstructionIndex(CurrPos).getRegSlot();
 202   else
 203     static_cast<RegionPressure&>(P).TopPos = CurrPos;
 204
 205   assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
 206   P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
 207   P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
 208   for (SparseSet<unsigned>::const_iterator I =
 209          LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
 210     P.LiveInRegs.push_back(*I);
 211   std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
 212   P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
 213                      P.LiveInRegs.end());
 214 }
 215
 216 /// Set the boundary for the bottom of the region and summarize live outs.
 217 void RegPressureTracker::closeBottom() {
 218   if (RequireIntervals)
 219     if (CurrPos == MBB->end())
 220       static_cast<IntervalPressure&>(P).BottomIdx = LIS->getMBBEndIdx(MBB);
 221     else
 222       static_cast<IntervalPressure&>(P).BottomIdx =
 223         LIS->getInstructionIndex(CurrPos).getRegSlot();
 224   else
 225     static_cast<RegionPressure&>(P).BottomPos = CurrPos;
 226
 227   assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
 228   P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
 229   P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
 230   for (SparseSet<unsigned>::const_iterator I =
 231          LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
 232     P.LiveOutRegs.push_back(*I);
 233   std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
 234   P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
 235                       P.LiveOutRegs.end());
 236 }
 237
 238 /// Finalize the region boundaries and record live ins and live outs.
 239 void RegPressureTracker::closeRegion() {
 240   if (!isTopClosed() && !isBottomClosed()) {
 241     assert(LivePhysRegs.empty() && LiveVirtRegs.empty() &&
 242            "no region boundary");
 243     return;
 244   }
 245   if (!isBottomClosed())
 246     closeBottom();
 247   else if (!isTopClosed())
 248     closeTop();
 249   // If both top and bottom are closed, do nothing.
 250 }
 251
 252 /// Return true if Reg aliases a register in Regs SparseSet.
 253 static bool hasRegAlias(unsigned Reg, SparseSet<unsigned> &Regs,
 254                         const TargetRegisterInfo *TRI) {
 255   assert(!TargetRegisterInfo::isVirtualRegister(Reg) && "only for physregs");
 256   for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) {
 257     if (Regs.count(*Alias))
 258       return true;
 259   }
 260   return false;
 261 }
 262
 263 /// Return true if Reg aliases a register in unsorted Regs SmallVector.
 264 /// This is only valid for physical registers.
 265 static SmallVectorImpl<unsigned>::iterator
 266 findRegAlias(unsigned Reg, SmallVectorImpl<unsigned> &Regs,
 267              const TargetRegisterInfo *TRI) {
 268   for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) {
 269     SmallVectorImpl<unsigned>::iterator I =
 270       std::find(Regs.begin(), Regs.end(), *Alias);
 271     if (I != Regs.end())
 272       return I;
 273   }
 274   return Regs.end();
 275 }
 276
 277 /// Return true if Reg can be inserted into Regs SmallVector. For virtual
 278 /// register, do a linear search. For physical registers check for aliases.
 279 static SmallVectorImpl<unsigned>::iterator
 280 findReg(unsigned Reg, bool isVReg, SmallVectorImpl<unsigned> &Regs,
 281         const TargetRegisterInfo *TRI) {
 282   if(isVReg)
 283     return std::find(Regs.begin(), Regs.end(), Reg);
 284   return findRegAlias(Reg, Regs, TRI);
 285 }
 286
 287 /// Collect this instruction's unique uses and defs into SmallVectors for
 288 /// processing defs and uses in order.
 289 template<bool isVReg>
 290 struct RegisterOperands {
 291   SmallVector<unsigned, 8> Uses;
 292   SmallVector<unsigned, 8> Defs;
 293   SmallVector<unsigned, 8> DeadDefs;
 294
 295   /// Push this operand's register onto the correct vector.
 296   void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
 297     if (MO.readsReg()) {
 298       if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end())
 299       Uses.push_back(MO.getReg());
 300     }
 301     if (MO.isDef()) {
 302       if (MO.isDead()) {
 303         if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end())
 304           DeadDefs.push_back(MO.getReg());
 305       }
 306       else {
 307         if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
 308           Defs.push_back(MO.getReg());
 309       }
 310     }
 311   }
 312 };
 313 typedef RegisterOperands<false> PhysRegOperands;
 314 typedef RegisterOperands<true> VirtRegOperands;
 315
 316 /// Collect physical and virtual register operands.
 317 static void collectOperands(const MachineInstr *MI,
 318                             PhysRegOperands &PhysRegOpers,
 319                             VirtRegOperands &VirtRegOpers,
 320                             const TargetRegisterInfo *TRI,
 321                             const RegisterClassInfo *RCI) {
 322   for(ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) {
 323     const MachineOperand &MO = *OperI;
 324     if (!MO.isReg() || !MO.getReg())
 325       continue;
 326
 327     if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 328       VirtRegOpers.collect(MO, TRI);
 329     else if (RCI->isAllocatable(MO.getReg()))
 330       PhysRegOpers.collect(MO, TRI);
 331   }
 332   // Remove redundant physreg dead defs.
 333   for (unsigned i = PhysRegOpers.DeadDefs.size(); i > 0; --i) {
 334     unsigned Reg = PhysRegOpers.DeadDefs[i-1];
 335     if (findRegAlias(Reg, PhysRegOpers.Defs, TRI) != PhysRegOpers.Defs.end())
 336       PhysRegOpers.DeadDefs.erase(&PhysRegOpers.DeadDefs[i-1]);
 337   }
 338 }
 339
 340 /// Force liveness of registers.
 341 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
 342   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
 343     if (TargetRegisterInfo::isVirtualRegister(Regs[i])) {
 344       if (LiveVirtRegs.insert(Regs[i]).second)
 345         increaseVirtRegPressure(Regs[i]);
 346     }
 347     else  {
 348       if (!hasRegAlias(Regs[i], LivePhysRegs, TRI)) {
 349         LivePhysRegs.insert(Regs[i]);
 350         increasePhysRegPressure(Regs[i]);
 351       }
 352     }
 353   }
 354 }
 355
 356 /// Add PhysReg to the live in set and increase max pressure.
 357 void RegPressureTracker::discoverPhysLiveIn(unsigned Reg) {
 358   assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
 359   if (findRegAlias(Reg, P.LiveInRegs, TRI) == P.LiveInRegs.end())
 360     return;
 361
 362   // At live in discovery, unconditionally increase the high water mark.
 363   P.LiveInRegs.push_back(Reg);
 364   P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
 365 }
 366
 367 /// Add PhysReg to the live out set and increase max pressure.
 368 void RegPressureTracker::discoverPhysLiveOut(unsigned Reg) {
 369   assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
 370   if (findRegAlias(Reg, P.LiveOutRegs, TRI) == P.LiveOutRegs.end())
 371     return;
 372
 373   // At live out discovery, unconditionally increase the high water mark.
 374   P.LiveOutRegs.push_back(Reg);
 375   P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
 376 }
 377
 378 /// Add VirtReg to the live in set and increase max pressure.
 379 void RegPressureTracker::discoverVirtLiveIn(unsigned Reg) {
 380   assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
 381   if (std::find(P.LiveInRegs.begin(), P.LiveInRegs.end(), Reg) !=
 382       P.LiveInRegs.end())
 383     return;
 384
 385   // At live in discovery, unconditionally increase the high water mark.
 386   P.LiveInRegs.push_back(Reg);
 387   P.increase(MRI->getRegClass(Reg), TRI);
 388 }
 389
 390 /// Add VirtReg to the live out set and increase max pressure.
 391 void RegPressureTracker::discoverVirtLiveOut(unsigned Reg) {
 392   assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
 393   if (std::find(P.LiveOutRegs.begin(), P.LiveOutRegs.end(), Reg) !=
 394       P.LiveOutRegs.end())
 395     return;
 396
 397   // At live out discovery, unconditionally increase the high water mark.
 398   P.LiveOutRegs.push_back(Reg);
 399   P.increase(MRI->getRegClass(Reg), TRI);
 400 }
 401
 402 /// Recede across the previous instruction.
 403 bool RegPressureTracker::recede() {
 404   // Check for the top of the analyzable region.
 405   if (CurrPos == MBB->begin()) {
 406     closeRegion();
 407     return false;
 408   }
 409   if (!isBottomClosed())
 410     closeBottom();
 411
 412   // Open the top of the region using block iterators.
 413   if (!RequireIntervals && isTopClosed())
 414     static_cast<RegionPressure&>(P).openTop(CurrPos);
 415
 416   // Find the previous instruction.
 417   do
 418     --CurrPos;
 419   while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
 420
 421   if (CurrPos->isDebugValue()) {
 422     closeRegion();
 423     return false;
 424   }
 425   SlotIndex SlotIdx;
 426   if (RequireIntervals)
 427     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 428
 429   // Open the top of the region using slot indexes.
 430   if (RequireIntervals && isTopClosed())
 431     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
 432
 433   PhysRegOperands PhysRegOpers;
 434   VirtRegOperands VirtRegOpers;
 435   collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
 436
 437   // Boost pressure for all dead defs together.
 438   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 439   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 440   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 441   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 442
 443   // Kill liveness at live defs.
 444   // TODO: consider earlyclobbers?
 445   for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
 446     unsigned Reg = PhysRegOpers.Defs[i];
 447     if (LivePhysRegs.erase(Reg))
 448       decreasePhysRegPressure(Reg);
 449     else
 450       discoverPhysLiveOut(Reg);
 451   }
 452   for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
 453     unsigned Reg = VirtRegOpers.Defs[i];
 454     if (LiveVirtRegs.erase(Reg))
 455       decreaseVirtRegPressure(Reg);
 456     else
 457       discoverVirtLiveOut(Reg);
 458   }
 459
 460   // Generate liveness for uses.
 461   for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
 462     unsigned Reg = PhysRegOpers.Uses[i];
 463     if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
 464       increasePhysRegPressure(Reg);
 465       LivePhysRegs.insert(Reg);
 466     }
 467   }
 468   for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 469     unsigned Reg = VirtRegOpers.Uses[i];
 470     if (!LiveVirtRegs.count(Reg)) {
 471       // Adjust liveouts if LiveIntervals are available.
 472       if (RequireIntervals) {
 473         const LiveInterval *LI = &LIS->getInterval(Reg);
 474         if (!LI->killedAt(SlotIdx))
 475           discoverVirtLiveOut(Reg);
 476       }
 477       increaseVirtRegPressure(Reg);
 478       LiveVirtRegs.insert(Reg);
 479     }
 480   }
 481   return true;
 482 }
 483
 484 /// Advance across the current instruction.
 485 bool RegPressureTracker::advance() {
 486   // Check for the bottom of the analyzable region.
 487   if (CurrPos == MBB->end()) {
 488     closeRegion();
 489     return false;
 490   }
 491   if (!isTopClosed())
 492     closeTop();
 493
 494   SlotIndex SlotIdx;
 495   if (RequireIntervals)
 496     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 497
 498   // Open the bottom of the region using slot indexes.
 499   if (isBottomClosed()) {
 500     if (RequireIntervals)
 501       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
 502     else
 503       static_cast<RegionPressure&>(P).openBottom(CurrPos);
 504   }
 505
 506   PhysRegOperands PhysRegOpers;
 507   VirtRegOperands VirtRegOpers;
 508   collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
 509
 510   // Kill liveness at last uses.
 511   for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
 512     unsigned Reg = PhysRegOpers.Uses[i];
 513     if (!hasRegAlias(Reg, LivePhysRegs, TRI))
 514       discoverPhysLiveIn(Reg);
 515     else {
 516       // Allocatable physregs are always single-use before regalloc.
 517       decreasePhysRegPressure(Reg);
 518       LivePhysRegs.erase(Reg);
 519     }
 520   }
 521   for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 522     unsigned Reg = VirtRegOpers.Uses[i];
 523     if (RequireIntervals) {
 524       const LiveInterval *LI = &LIS->getInterval(Reg);
 525       if (LI->killedAt(SlotIdx)) {
 526         if (LiveVirtRegs.erase(Reg))
 527           decreaseVirtRegPressure(Reg);
 528         else
 529           discoverVirtLiveIn(Reg);
 530       }
 531     }
 532     else if (!LiveVirtRegs.count(Reg)) {
 533       discoverVirtLiveIn(Reg);
 534       increaseVirtRegPressure(Reg);
 535     }
 536   }
 537
 538   // Generate liveness for defs.
 539   for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
 540     unsigned Reg = PhysRegOpers.Defs[i];
 541     if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
 542       increasePhysRegPressure(Reg);
 543       LivePhysRegs.insert(Reg);
 544     }
 545   }
 546   for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
 547     unsigned Reg = VirtRegOpers.Defs[i];
 548     if (LiveVirtRegs.insert(Reg).second)
 549       increaseVirtRegPressure(Reg);
 550   }
 551
 552   // Boost pressure for all dead defs together.
 553   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 554   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 555   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 556   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 557
 558   // Find the next instruction.
 559   do
 560     ++CurrPos;
 561   while (CurrPos != MBB->end() && CurrPos->isDebugValue());
 562   return true;
 563 }
 564
 565 // Find the max change in excess pressure across all sets.
 566 static int computeMaxPressureDelta(ArrayRef<unsigned> OldPressureVec,
 567                                    ArrayRef<unsigned> NewPressureVec,
 568                                    unsigned &PSetID,
 569                                    const TargetRegisterInfo *TRI) {
 570   int ExcessUnits = 0;
 571   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 572     unsigned POld = OldPressureVec[i];
 573     unsigned PNew = NewPressureVec[i];
 574     int PDiff = (int)PNew - (int)POld;
 575     if (!PDiff) // No change in this set in the common case.
 576       continue;
 577     // Only consider change beyond the limit.
 578     unsigned Limit = TRI->getRegPressureSetLimit(i);
 579     if (Limit > POld) {
 580       if (Limit > PNew)
 581         PDiff = 0;            // Under the limit
 582       else
 583         PDiff = PNew - Limit; // Just exceeded limit.
 584     }
 585     else if (Limit > PNew)
 586       PDiff = Limit - POld;   // Just obeyed limit.
 587
 588     if (std::abs(PDiff) > std::abs(ExcessUnits)) {
 589       ExcessUnits = PDiff;
 590       PSetID = i;
 591     }
 592   }
 593   return ExcessUnits;
 594 }
 595
 596 /// Consider the pressure increase caused by traversing this instruction
 597 /// bottom-up. Find the pressure set with the most change beyond its pressure
 598 /// limit based on the tracker's current pressure, and return the change in
 599 /// number of register units of that pressure set introduced by this
 600 /// instruction.
 601 ///
 602 /// This assumes that the current LiveOut set is sufficient.
 603 ///
 604 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
 605 /// result per-SUnit with enough information to adjust for the current
 606 /// scheduling position. But this works as a proof of concept.
 607 void RegPressureTracker::
 608 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta) {
 609   // Account for register pressure similar to RegPressureTracker::recede().
 610   PhysRegOperands PhysRegOpers;
 611   VirtRegOperands VirtRegOpers;
 612   collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
 613
 614   // Snapshot Pressure.
 615   std::vector<unsigned> SavedPressure = CurrSetPressure;
 616   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 617
 618   // Boost max pressure for all dead defs together.
 619   // Since CurrSetPressure and MaxSetPressure
 620   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 621   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 622   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 623   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 624
 625   // Kill liveness at live defs.
 626   decreasePhysRegPressure(PhysRegOpers.Defs);
 627   decreaseVirtRegPressure(VirtRegOpers.Defs);
 628
 629   // Generate liveness for uses.
 630   for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
 631     unsigned Reg = PhysRegOpers.Uses[i];
 632     if (!hasRegAlias(Reg, LivePhysRegs, TRI)
 633         && (findRegAlias(Reg, PhysRegOpers.Defs, TRI)
 634             == PhysRegOpers.Defs.end())) {
 635       increasePhysRegPressure(Reg);
 636     }
 637   }
 638   for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 639     unsigned Reg = VirtRegOpers.Uses[i];
 640     if (!LiveVirtRegs.count(Reg)
 641         && (std::find(VirtRegOpers.Defs.begin(), VirtRegOpers.Defs.end(), Reg)
 642             != VirtRegOpers.Defs.end())) {
 643       increaseVirtRegPressure(Reg);
 644     }
 645   }
 646   Delta.ExcessUnits =
 647     computeMaxPressureDelta(SavedPressure, CurrSetPressure,
 648                             Delta.ExcessSetID, TRI);
 649   Delta.MaxUnitIncrease =
 650     computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure,
 651                             Delta.MaxSetID, TRI);
 652   assert(Delta.MaxUnitIncrease >= 0 && "cannot increase max pressure");
 653
 654   // Restore the tracker's state.
 655   P.MaxSetPressure.swap(SavedMaxPressure);
 656   CurrSetPressure.swap(SavedPressure);
 657 }
 658
 659 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
 660 static bool findUseBetween(unsigned Reg,
 661                            SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
 662                            const MachineRegisterInfo *MRI,
 663                            const LiveIntervals *LIS) {
 664   for (MachineRegisterInfo::use_nodbg_iterator
 665          UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
 666          UI != UE; UI.skipInstruction()) {
 667       const MachineInstr* MI = &*UI;
 668       SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
 669       if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
 670         return true;
 671   }
 672   return false;
 673 }
 674
 675 /// Consider the pressure increase caused by traversing this instruction
 676 /// top-down. Find the register class with the most change in its pressure limit
 677 /// based on the tracker's current pressure, and return the number of excess
 678 /// register units of that pressure set introduced by this instruction.
 679 ///
 680 /// This assumes that the current LiveIn set is sufficient.
 681 void RegPressureTracker::
 682 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta) {
 683   // Account for register pressure similar to RegPressureTracker::recede().
 684   PhysRegOperands PhysRegOpers;
 685   VirtRegOperands VirtRegOpers;
 686   collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
 687
 688   // Snapshot Pressure.
 689   std::vector<unsigned> SavedPressure = CurrSetPressure;
 690   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 691
 692   // Kill liveness at last uses. Assume allocatable physregs are single-use
 693   // rather than checking LiveIntervals.
 694   decreasePhysRegPressure(PhysRegOpers.Uses);
 695   if (RequireIntervals) {
 696     SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
 697     for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 698       unsigned Reg = VirtRegOpers.Uses[i];
 699       const LiveInterval *LI = &LIS->getInterval(Reg);
 700       // FIXME: allow the caller to pass in the list of vreg uses that remain to
 701       // be top-scheduled to avoid searching uses at each query.
 702       SlotIndex CurrIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 703       if (LI->killedAt(SlotIdx)
 704           && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
 705         decreaseVirtRegPressure(Reg);
 706       }
 707     }
 708   }
 709
 710   // Generate liveness for defs.
 711   increasePhysRegPressure(PhysRegOpers.Defs);
 712   increaseVirtRegPressure(VirtRegOpers.Defs);
 713
 714   // Boost pressure for all dead defs together.
 715   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 716   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 717   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 718   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 719
 720   Delta.ExcessUnits =
 721     computeMaxPressureDelta(SavedPressure, CurrSetPressure,
 722                             Delta.ExcessSetID, TRI);
 723   Delta.MaxUnitIncrease =
 724     computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure,
 725                             Delta.MaxSetID, TRI);
 726
 727   // Restore the tracker's state.
 728   P.MaxSetPressure.swap(SavedMaxPressure);
 729   CurrSetPressure.swap(SavedPressure);
 730 }