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 /// Add PhysReg to the live in set and increase max pressure.
 341 void RegPressureTracker::discoverPhysLiveIn(unsigned Reg) {
 342   assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
 343   if (findRegAlias(Reg, P.LiveInRegs, TRI) == P.LiveInRegs.end())
 344     return;
 345
 346   // At live in discovery, unconditionally increase the high water mark.
 347   P.LiveInRegs.push_back(Reg);
 348   P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
 349 }
 350
 351 /// Add PhysReg to the live out set and increase max pressure.
 352 void RegPressureTracker::discoverPhysLiveOut(unsigned Reg) {
 353   assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
 354   if (findRegAlias(Reg, P.LiveOutRegs, TRI) == P.LiveOutRegs.end())
 355     return;
 356
 357   // At live out discovery, unconditionally increase the high water mark.
 358   P.LiveOutRegs.push_back(Reg);
 359   P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
 360 }
 361
 362 /// Add VirtReg to the live in set and increase max pressure.
 363 void RegPressureTracker::discoverVirtLiveIn(unsigned Reg) {
 364   assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
 365   if (std::find(P.LiveInRegs.begin(), P.LiveInRegs.end(), Reg) !=
 366       P.LiveInRegs.end())
 367     return;
 368
 369   // At live in discovery, unconditionally increase the high water mark.
 370   P.LiveInRegs.push_back(Reg);
 371   P.increase(MRI->getRegClass(Reg), TRI);
 372 }
 373
 374 /// Add VirtReg to the live out set and increase max pressure.
 375 void RegPressureTracker::discoverVirtLiveOut(unsigned Reg) {
 376   assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
 377   if (std::find(P.LiveOutRegs.begin(), P.LiveOutRegs.end(), Reg) !=
 378       P.LiveOutRegs.end())
 379     return;
 380
 381   // At live out discovery, unconditionally increase the high water mark.
 382   P.LiveOutRegs.push_back(Reg);
 383   P.increase(MRI->getRegClass(Reg), TRI);
 384 }
 385
 386 /// Recede across the previous instruction.
 387 bool RegPressureTracker::recede() {
 388   // Check for the top of the analyzable region.
 389   if (CurrPos == MBB->begin()) {
 390     closeRegion();
 391     return false;
 392   }
 393   if (!isBottomClosed())
 394     closeBottom();
 395
 396   // Open the top of the region using block iterators.
 397   if (!RequireIntervals && isTopClosed())
 398     static_cast<RegionPressure&>(P).openTop(CurrPos);
 399
 400   // Find the previous instruction.
 401   do
 402     --CurrPos;
 403   while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
 404
 405   if (CurrPos->isDebugValue()) {
 406     closeRegion();
 407     return false;
 408   }
 409   SlotIndex SlotIdx;
 410   if (RequireIntervals)
 411     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 412
 413   // Open the top of the region using slot indexes.
 414   if (RequireIntervals && isTopClosed())
 415     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
 416
 417   PhysRegOperands PhysRegOpers;
 418   VirtRegOperands VirtRegOpers;
 419   collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
 420
 421   // Boost pressure for all dead defs together.
 422   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 423   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 424   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 425   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 426
 427   // Kill liveness at live defs.
 428   // TODO: consider earlyclobbers?
 429   for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
 430     unsigned Reg = PhysRegOpers.Defs[i];
 431     if (LivePhysRegs.erase(Reg))
 432       decreasePhysRegPressure(Reg);
 433     else
 434       discoverPhysLiveOut(Reg);
 435   }
 436   for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
 437     unsigned Reg = VirtRegOpers.Defs[i];
 438     if (LiveVirtRegs.erase(Reg))
 439       decreaseVirtRegPressure(Reg);
 440     else
 441       discoverVirtLiveOut(Reg);
 442   }
 443
 444   // Generate liveness for uses.
 445   for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
 446     unsigned Reg = PhysRegOpers.Uses[i];
 447     if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
 448       increasePhysRegPressure(Reg);
 449       LivePhysRegs.insert(Reg);
 450     }
 451   }
 452   for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 453     unsigned Reg = VirtRegOpers.Uses[i];
 454     if (!LiveVirtRegs.count(Reg)) {
 455       // Adjust liveouts if LiveIntervals are available.
 456       if (RequireIntervals) {
 457         const LiveInterval *LI = &LIS->getInterval(Reg);
 458         if (!LI->killedAt(SlotIdx))
 459           discoverVirtLiveOut(Reg);
 460       }
 461       increaseVirtRegPressure(Reg);
 462       LiveVirtRegs.insert(Reg);
 463     }
 464   }
 465   return true;
 466 }
 467
 468 /// Advance across the current instruction.
 469 bool RegPressureTracker::advance() {
 470   // Check for the bottom of the analyzable region.
 471   if (CurrPos == MBB->end()) {
 472     closeRegion();
 473     return false;
 474   }
 475   if (!isTopClosed())
 476     closeTop();
 477
 478   SlotIndex SlotIdx;
 479   if (RequireIntervals)
 480     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 481
 482   // Open the bottom of the region using slot indexes.
 483   if (isBottomClosed()) {
 484     if (RequireIntervals)
 485       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
 486     else
 487       static_cast<RegionPressure&>(P).openBottom(CurrPos);
 488   }
 489
 490   PhysRegOperands PhysRegOpers;
 491   VirtRegOperands VirtRegOpers;
 492   collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
 493
 494   // Kill liveness at last uses.
 495   for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
 496     unsigned Reg = PhysRegOpers.Uses[i];
 497     if (!hasRegAlias(Reg, LivePhysRegs, TRI))
 498       discoverPhysLiveIn(Reg);
 499     else {
 500       // Allocatable physregs are always single-use before regalloc.
 501       decreasePhysRegPressure(Reg);
 502       LivePhysRegs.erase(Reg);
 503     }
 504   }
 505   for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 506     unsigned Reg = VirtRegOpers.Uses[i];
 507     if (RequireIntervals) {
 508       const LiveInterval *LI = &LIS->getInterval(Reg);
 509       if (LI->killedAt(SlotIdx)) {
 510         if (LiveVirtRegs.erase(Reg))
 511           decreaseVirtRegPressure(Reg);
 512         else
 513           discoverVirtLiveIn(Reg);
 514       }
 515     }
 516     else if (!LiveVirtRegs.count(Reg)) {
 517       discoverVirtLiveIn(Reg);
 518       increaseVirtRegPressure(Reg);
 519     }
 520   }
 521
 522   // Generate liveness for defs.
 523   for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
 524     unsigned Reg = PhysRegOpers.Defs[i];
 525     if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
 526       increasePhysRegPressure(Reg);
 527       LivePhysRegs.insert(Reg);
 528     }
 529   }
 530   for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
 531     unsigned Reg = VirtRegOpers.Defs[i];
 532     if (LiveVirtRegs.insert(Reg).second)
 533       increaseVirtRegPressure(Reg);
 534   }
 535
 536   // Boost pressure for all dead defs together.
 537   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 538   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 539   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 540   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 541
 542   // Find the next instruction.
 543   do
 544     ++CurrPos;
 545   while (CurrPos != MBB->end() && CurrPos->isDebugValue());
 546   return true;
 547 }
 548
 549 // Find the max change in excess pressure across all sets.
 550 static int computeMaxPressureDelta(ArrayRef<unsigned> OldPressureVec,
 551                                    ArrayRef<unsigned> NewPressureVec,
 552                                    unsigned &PSetID,
 553                                    const TargetRegisterInfo *TRI) {
 554   int ExcessUnits = 0;
 555   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 556     unsigned POld = OldPressureVec[i];
 557     unsigned PNew = NewPressureVec[i];
 558     int PDiff = (int)PNew - (int)POld;
 559     if (!PDiff) // No change in this set in the common case.
 560       continue;
 561     // Only consider change beyond the limit.
 562     unsigned Limit = TRI->getRegPressureSetLimit(i);
 563     if (Limit > POld) {
 564       if (Limit > PNew)
 565         PDiff = 0;          // Under the limit
 566       else
 567         PDiff = PNew - Limit; // Just exceeded limit.
 568     }
 569     else if (Limit > PNew)
 570       PDiff = Limit - POld; // Just obeyed limit.
 571
 572     if (std::abs(PDiff) > std::abs(ExcessUnits)) {
 573       ExcessUnits = PDiff;
 574       PSetID = i;
 575     }
 576   }
 577   return ExcessUnits;
 578 }
 579
 580 /// Consider the pressure increase caused by traversing this instruction
 581 /// bottom-up. Find the pressure set with the most change beyond its pressure
 582 /// limit based on the tracker's current pressure, and return the change in
 583 /// number of register units of that pressure set introduced by this
 584 /// instruction.
 585 ///
 586 /// This assumes that the current LiveOut set is sufficient.
 587 ///
 588 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
 589 /// result per-SUnit with enough information to adjust for the current
 590 /// scheduling position. But this works as a proof of concept.
 591 void RegPressureTracker::
 592 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta) {
 593   // Account for register pressure similar to RegPressureTracker::recede().
 594   PhysRegOperands PhysRegOpers;
 595   VirtRegOperands VirtRegOpers;
 596   collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
 597
 598   // Snapshot Pressure.
 599   std::vector<unsigned> SavedPressure = CurrSetPressure;
 600   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 601
 602   // Boost max pressure for all dead defs together.
 603   // Since CurrSetPressure and MaxSetPressure
 604   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 605   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 606   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 607   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 608
 609   // Kill liveness at live defs.
 610   // TODO: consider earlyclobbers?
 611   for (unsigned i = 0; i < PhysRegOpers.Defs.size(); ++i) {
 612     unsigned Reg = PhysRegOpers.Defs[i];
 613     if (LivePhysRegs.erase(Reg))
 614       decreasePhysRegPressure(Reg);
 615     else
 616       discoverPhysLiveOut(Reg);
 617   }
 618   for (unsigned i = 0; i < VirtRegOpers.Defs.size(); ++i) {
 619     unsigned Reg = VirtRegOpers.Defs[i];
 620     if (LiveVirtRegs.erase(Reg))
 621       decreaseVirtRegPressure(Reg);
 622     else
 623       discoverVirtLiveOut(Reg);
 624   }
 625
 626   // Generate liveness for uses.
 627   for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
 628     unsigned Reg = PhysRegOpers.Uses[i];
 629     if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
 630       increasePhysRegPressure(Reg);
 631       LivePhysRegs.insert(Reg);
 632     }
 633   }
 634   for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 635     unsigned Reg = VirtRegOpers.Uses[i];
 636     if (!LiveVirtRegs.count(Reg)) {
 637       increaseVirtRegPressure(Reg);
 638     }
 639   }
 640   Delta.ExcessUnits =
 641     computeMaxPressureDelta(SavedPressure, CurrSetPressure,
 642                             Delta.ExcessSetID, TRI);
 643   Delta.MaxUnitIncrease =
 644     computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure,
 645                             Delta.MaxSetID, TRI);
 646   assert(Delta.MaxUnitIncrease >= 0 && "cannot increase max pressure");
 647
 648   // Restore the tracker's state.
 649   P.MaxSetPressure.swap(SavedMaxPressure);
 650   CurrSetPressure.swap(SavedPressure);
 651 }
 652
 653 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
 654 static bool findUseBetween(unsigned Reg,
 655                            SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
 656                            const MachineRegisterInfo *MRI,
 657                            const LiveIntervals *LIS) {
 658   for (MachineRegisterInfo::use_nodbg_iterator
 659          UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
 660          UI != UE; UI.skipInstruction()) {
 661       const MachineInstr* MI = &*UI;
 662       SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
 663       if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
 664         return true;
 665   }
 666   return false;
 667 }
 668
 669 /// Consider the pressure increase caused by traversing this instruction
 670 /// top-down. Find the register class with the most change in its pressure limit
 671 /// based on the tracker's current pressure, and return the number of excess
 672 /// register units of that pressure set introduced by this instruction.
 673 ///
 674 /// This assumes that the current LiveIn set is sufficient.
 675 void RegPressureTracker::
 676 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta) {
 677   // Account for register pressure similar to RegPressureTracker::recede().
 678   PhysRegOperands PhysRegOpers;
 679   VirtRegOperands VirtRegOpers;
 680   collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
 681
 682   // Snapshot Pressure.
 683   std::vector<unsigned> SavedPressure = CurrSetPressure;
 684   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 685
 686   // Kill liveness at last uses. Assume allocatable physregs are single-use
 687   // rather than checking LiveIntervals.
 688   decreasePhysRegPressure(PhysRegOpers.Uses);
 689   if (RequireIntervals) {
 690     SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
 691     for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 692       unsigned Reg = VirtRegOpers.Uses[i];
 693       const LiveInterval *LI = &LIS->getInterval(Reg);
 694       // FIXME: allow the caller to pass in the list of vreg uses that remain to
 695       // be top-scheduled to avoid searching uses at each query.
 696       SlotIndex CurrIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 697       if (LI->killedAt(SlotIdx)
 698           && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
 699         decreaseVirtRegPressure(Reg);
 700       }
 701     }
 702   }
 703
 704   // Generate liveness for defs.
 705   increasePhysRegPressure(PhysRegOpers.Defs);
 706   increaseVirtRegPressure(VirtRegOpers.Defs);
 707
 708   // Boost pressure for all dead defs together.
 709   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 710   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 711   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 712   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 713
 714   Delta.ExcessUnits =
 715     computeMaxPressureDelta(SavedPressure, CurrSetPressure,
 716                             Delta.ExcessSetID, TRI);
 717   Delta.MaxUnitIncrease =
 718     computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure,
 719                             Delta.MaxSetID, TRI);
 720
 721   // Restore the tracker's state.
 722   P.MaxSetPressure.swap(SavedMaxPressure);
 723   CurrSetPressure.swap(SavedPressure);
 724 }