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 void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
 567                                        ArrayRef<unsigned> NewPressureVec,
 568                                        RegPressureDelta &Delta,
 569                                        const TargetRegisterInfo *TRI) {
 570   int ExcessUnits = 0;
 571   unsigned PSetID = ~0U;
 572   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 573     unsigned POld = OldPressureVec[i];
 574     unsigned PNew = NewPressureVec[i];
 575     int PDiff = (int)PNew - (int)POld;
 576     if (!PDiff) // No change in this set in the common case.
 577       continue;
 578     // Only consider change beyond the limit.
 579     unsigned Limit = TRI->getRegPressureSetLimit(i);
 580     if (Limit > POld) {
 581       if (Limit > PNew)
 582         PDiff = 0;            // Under the limit
 583       else
 584         PDiff = PNew - Limit; // Just exceeded limit.
 585     }
 586     else if (Limit > PNew)
 587       PDiff = Limit - POld;   // Just obeyed limit.
 588
 589     if (std::abs(PDiff) > std::abs(ExcessUnits)) {
 590       ExcessUnits = PDiff;
 591       PSetID = i;
 592     }
 593   }
 594   Delta.Excess.PSetID = PSetID;
 595   Delta.Excess.UnitIncrease = ExcessUnits;
 596 }
 597
 598 /// Find the max change in max pressure that either surpasses a critical PSet
 599 /// limit or exceeds the current MaxPressureLimit.
 600 ///
 601 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
 602 /// silly. It's done now to demonstrate the concept but will go away with a
 603 /// RegPressureTracker API change to work with pressure differences.
 604 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
 605                                     ArrayRef<unsigned> NewMaxPressureVec,
 606                                     ArrayRef<PressureElement> CriticalPSets,
 607                                     ArrayRef<unsigned> MaxPressureLimit,
 608                                     RegPressureDelta &Delta) {
 609   Delta.CriticalMax = PressureElement();
 610   Delta.CurrentMax = PressureElement();
 611
 612   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 613   for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
 614     unsigned POld = OldMaxPressureVec[i];
 615     unsigned PNew = NewMaxPressureVec[i];
 616     if (PNew == POld) // No change in this set in the common case.
 617       continue;
 618
 619     while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
 620       ++CritIdx;
 621
 622     if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
 623       int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
 624       if (PDiff > Delta.CriticalMax.UnitIncrease) {
 625         Delta.CriticalMax.PSetID = i;
 626         Delta.CriticalMax.UnitIncrease = PDiff;
 627       }
 628     }
 629
 630     // Find the greatest increase above MaxPressureLimit.
 631     // (Ignores negative MDiff).
 632     int MDiff = (int)PNew - (int)MaxPressureLimit[i];
 633     if (MDiff > Delta.CurrentMax.UnitIncrease) {
 634       Delta.CurrentMax.PSetID = i;
 635       Delta.CurrentMax.UnitIncrease = PNew;
 636     }
 637   }
 638 }
 639
 640 /// Consider the pressure increase caused by traversing this instruction
 641 /// bottom-up. Find the pressure set with the most change beyond its pressure
 642 /// limit based on the tracker's current pressure, and return the change in
 643 /// number of register units of that pressure set introduced by this
 644 /// instruction.
 645 ///
 646 /// This assumes that the current LiveOut set is sufficient.
 647 ///
 648 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
 649 /// result per-SUnit with enough information to adjust for the current
 650 /// scheduling position. But this works as a proof of concept.
 651 void RegPressureTracker::
 652 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 653                           ArrayRef<PressureElement> CriticalPSets,
 654                           ArrayRef<unsigned> MaxPressureLimit) {
 655   // Account for register pressure similar to RegPressureTracker::recede().
 656   PhysRegOperands PhysRegOpers;
 657   VirtRegOperands VirtRegOpers;
 658   collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
 659
 660   // Snapshot Pressure.
 661   // FIXME: The snapshot heap space should persist. But I'm planning to
 662   // summarize the pressure effect so we don't need to snapshot at all.
 663   std::vector<unsigned> SavedPressure = CurrSetPressure;
 664   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 665
 666   // Boost max pressure for all dead defs together.
 667   // Since CurrSetPressure and MaxSetPressure
 668   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 669   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 670   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 671   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 672
 673   // Kill liveness at live defs.
 674   decreasePhysRegPressure(PhysRegOpers.Defs);
 675   decreaseVirtRegPressure(VirtRegOpers.Defs);
 676
 677   // Generate liveness for uses.
 678   for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
 679     unsigned Reg = PhysRegOpers.Uses[i];
 680     if (!hasRegAlias(Reg, LivePhysRegs, TRI)
 681         && (findRegAlias(Reg, PhysRegOpers.Defs, TRI)
 682             == PhysRegOpers.Defs.end())) {
 683       increasePhysRegPressure(Reg);
 684     }
 685   }
 686   for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 687     unsigned Reg = VirtRegOpers.Uses[i];
 688     if (!LiveVirtRegs.count(Reg)
 689         && (std::find(VirtRegOpers.Defs.begin(), VirtRegOpers.Defs.end(), Reg)
 690             != VirtRegOpers.Defs.end())) {
 691       increaseVirtRegPressure(Reg);
 692     }
 693   }
 694   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
 695   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 696                           MaxPressureLimit, Delta);
 697   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
 698          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
 699
 700   // Restore the tracker's state.
 701   P.MaxSetPressure.swap(SavedMaxPressure);
 702   CurrSetPressure.swap(SavedPressure);
 703 }
 704
 705 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
 706 static bool findUseBetween(unsigned Reg,
 707                            SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
 708                            const MachineRegisterInfo *MRI,
 709                            const LiveIntervals *LIS) {
 710   for (MachineRegisterInfo::use_nodbg_iterator
 711          UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
 712          UI != UE; UI.skipInstruction()) {
 713       const MachineInstr* MI = &*UI;
 714       SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
 715       if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
 716         return true;
 717   }
 718   return false;
 719 }
 720
 721 /// Consider the pressure increase caused by traversing this instruction
 722 /// top-down. Find the register class with the most change in its pressure limit
 723 /// based on the tracker's current pressure, and return the number of excess
 724 /// register units of that pressure set introduced by this instruction.
 725 ///
 726 /// This assumes that the current LiveIn set is sufficient.
 727 void RegPressureTracker::
 728 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 729                             ArrayRef<PressureElement> CriticalPSets,
 730                             ArrayRef<unsigned> MaxPressureLimit) {
 731   // Account for register pressure similar to RegPressureTracker::recede().
 732   PhysRegOperands PhysRegOpers;
 733   VirtRegOperands VirtRegOpers;
 734   collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
 735
 736   // Snapshot Pressure.
 737   std::vector<unsigned> SavedPressure = CurrSetPressure;
 738   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 739
 740   // Kill liveness at last uses. Assume allocatable physregs are single-use
 741   // rather than checking LiveIntervals.
 742   decreasePhysRegPressure(PhysRegOpers.Uses);
 743   if (RequireIntervals) {
 744     SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
 745     for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
 746       unsigned Reg = VirtRegOpers.Uses[i];
 747       const LiveInterval *LI = &LIS->getInterval(Reg);
 748       // FIXME: allow the caller to pass in the list of vreg uses that remain to
 749       // be bottom-scheduled to avoid searching uses at each query.
 750       SlotIndex CurrIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 751       if (LI->killedAt(SlotIdx)
 752           && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
 753         decreaseVirtRegPressure(Reg);
 754       }
 755     }
 756   }
 757
 758   // Generate liveness for defs.
 759   increasePhysRegPressure(PhysRegOpers.Defs);
 760   increaseVirtRegPressure(VirtRegOpers.Defs);
 761
 762   // Boost pressure for all dead defs together.
 763   increasePhysRegPressure(PhysRegOpers.DeadDefs);
 764   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
 765   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
 766   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
 767
 768   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
 769   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 770                           MaxPressureLimit, Delta);
 771   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
 772          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
 773
 774   // Restore the tracker's state.
 775   P.MaxSetPressure.swap(SavedMaxPressure);
 776   CurrSetPressure.swap(SavedPressure);
 777 }