lib/CodeGen/RegisterPressure.cpp

   1 //===-- RegisterPressure.cpp - Dynamic Register Pressure ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the RegisterPressure class which can be used to track
  11 // MachineInstr level register pressure.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/CodeGen/RegisterPressure.h"
  16 #include "llvm/CodeGen/LiveInterval.h"
  17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/RegisterClassInfo.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22
  23 using namespace llvm;
  24
  25 /// Increase pressure for each pressure set provided by TargetRegisterInfo.
  26 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
  27                                 PSetIterator PSetI) {
  28   unsigned Weight = PSetI.getWeight();
  29   for (; PSetI.isValid(); ++PSetI)
  30     CurrSetPressure[*PSetI] += Weight;
  31 }
  32
  33 /// Decrease pressure for each pressure set provided by TargetRegisterInfo.
  34 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
  35                                 PSetIterator PSetI) {
  36   unsigned Weight = PSetI.getWeight();
  37   for (; PSetI.isValid(); ++PSetI) {
  38     assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow");
  39     CurrSetPressure[*PSetI] -= Weight;
  40   }
  41 }
  42
  43 LLVM_DUMP_METHOD
  44 void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
  45                               const TargetRegisterInfo *TRI) {
  46   bool Empty = true;
  47   for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
  48     if (SetPressure[i] != 0) {
  49       dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
  50       Empty = false;
  51     }
  52   }
  53   if (Empty)
  54     dbgs() << "\n";
  55 }
  56
  57 LLVM_DUMP_METHOD
  58 void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
  59   dbgs() << "Max Pressure: ";
  60   dumpRegSetPressure(MaxSetPressure, TRI);
  61   dbgs() << "Live In: ";
  62   for (unsigned Reg : LiveInRegs)
  63     dbgs() << PrintVRegOrUnit(Reg, TRI) << " ";
  64   dbgs() << '\n';
  65   dbgs() << "Live Out: ";
  66   for (unsigned Reg : LiveOutRegs)
  67     dbgs() << PrintVRegOrUnit(Reg, TRI) << " ";
  68   dbgs() << '\n';
  69 }
  70
  71 LLVM_DUMP_METHOD
  72 void RegPressureTracker::dump() const {
  73   if (!isTopClosed() || !isBottomClosed()) {
  74     dbgs() << "Curr Pressure: ";
  75     dumpRegSetPressure(CurrSetPressure, TRI);
  76   }
  77   P.dump(TRI);
  78 }
  79
  80 void PressureDiff::dump(const TargetRegisterInfo &TRI) const {
  81   const char *sep = "";
  82   for (const PressureChange &Change : *this) {
  83     if (!Change.isValid())
  84       break;
  85     dbgs() << sep << TRI.getRegPressureSetName(Change.getPSet())
  86            << " " << Change.getUnitInc();
  87     sep = "    ";
  88   }
  89   dbgs() << '\n';
  90 }
  91
  92 /// Increase the current pressure as impacted by these registers and bump
  93 /// the high water mark if needed.
  94 void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> RegUnits) {
  95   for (unsigned RegUnit : RegUnits) {
  96     PSetIterator PSetI = MRI->getPressureSets(RegUnit);
  97     unsigned Weight = PSetI.getWeight();
  98     for (; PSetI.isValid(); ++PSetI) {
  99       CurrSetPressure[*PSetI] += Weight;
 100       P.MaxSetPressure[*PSetI] =
 101           std::max(P.MaxSetPressure[*PSetI], CurrSetPressure[*PSetI]);
 102     }
 103   }
 104 }
 105
 106 /// Simply decrease the current pressure as impacted by these registers.
 107 void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> RegUnits) {
 108   for (unsigned RegUnit : RegUnits)
 109     decreaseSetPressure(CurrSetPressure, MRI->getPressureSets(RegUnit));
 110 }
 111
 112 /// Clear the result so it can be used for another round of pressure tracking.
 113 void IntervalPressure::reset() {
 114   TopIdx = BottomIdx = SlotIndex();
 115   MaxSetPressure.clear();
 116   LiveInRegs.clear();
 117   LiveOutRegs.clear();
 118 }
 119
 120 /// Clear the result so it can be used for another round of pressure tracking.
 121 void RegionPressure::reset() {
 122   TopPos = BottomPos = MachineBasicBlock::const_iterator();
 123   MaxSetPressure.clear();
 124   LiveInRegs.clear();
 125   LiveOutRegs.clear();
 126 }
 127
 128 /// If the current top is not less than or equal to the next index, open it.
 129 /// We happen to need the SlotIndex for the next top for pressure update.
 130 void IntervalPressure::openTop(SlotIndex NextTop) {
 131   if (TopIdx <= NextTop)
 132     return;
 133   TopIdx = SlotIndex();
 134   LiveInRegs.clear();
 135 }
 136
 137 /// If the current top is the previous instruction (before receding), open it.
 138 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
 139   if (TopPos != PrevTop)
 140     return;
 141   TopPos = MachineBasicBlock::const_iterator();
 142   LiveInRegs.clear();
 143 }
 144
 145 /// If the current bottom is not greater than the previous index, open it.
 146 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
 147   if (BottomIdx > PrevBottom)
 148     return;
 149   BottomIdx = SlotIndex();
 150   LiveInRegs.clear();
 151 }
 152
 153 /// If the current bottom is the previous instr (before advancing), open it.
 154 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
 155   if (BottomPos != PrevBottom)
 156     return;
 157   BottomPos = MachineBasicBlock::const_iterator();
 158   LiveInRegs.clear();
 159 }
 160
 161 void LiveRegSet::init(const MachineRegisterInfo &MRI) {
 162   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 163   unsigned NumRegUnits = TRI.getNumRegs();
 164   unsigned NumVirtRegs = MRI.getNumVirtRegs();
 165   Regs.setUniverse(NumRegUnits + NumVirtRegs);
 166   this->NumRegUnits = NumRegUnits;
 167 }
 168
 169 void LiveRegSet::clear() {
 170   Regs.clear();
 171 }
 172
 173 static const LiveRange *getLiveRange(const LiveIntervals &LIS, unsigned Reg) {
 174   if (TargetRegisterInfo::isVirtualRegister(Reg))
 175     return &LIS.getInterval(Reg);
 176   return LIS.getCachedRegUnit(Reg);
 177 }
 178
 179 void RegPressureTracker::reset() {
 180   MBB = nullptr;
 181   LIS = nullptr;
 182
 183   CurrSetPressure.clear();
 184   LiveThruPressure.clear();
 185   P.MaxSetPressure.clear();
 186
 187   if (RequireIntervals)
 188     static_cast<IntervalPressure&>(P).reset();
 189   else
 190     static_cast<RegionPressure&>(P).reset();
 191
 192   LiveRegs.clear();
 193   UntiedDefs.clear();
 194 }
 195
 196 /// Setup the RegPressureTracker.
 197 ///
 198 /// TODO: Add support for pressure without LiveIntervals.
 199 void RegPressureTracker::init(const MachineFunction *mf,
 200                               const RegisterClassInfo *rci,
 201                               const LiveIntervals *lis,
 202                               const MachineBasicBlock *mbb,
 203                               MachineBasicBlock::const_iterator pos,
 204                               bool ShouldTrackUntiedDefs)
 205 {
 206   reset();
 207
 208   MF = mf;
 209   TRI = MF->getSubtarget().getRegisterInfo();
 210   RCI = rci;
 211   MRI = &MF->getRegInfo();
 212   MBB = mbb;
 213   TrackUntiedDefs = ShouldTrackUntiedDefs;
 214
 215   if (RequireIntervals) {
 216     assert(lis && "IntervalPressure requires LiveIntervals");
 217     LIS = lis;
 218   }
 219
 220   CurrPos = pos;
 221   CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
 222
 223   P.MaxSetPressure = CurrSetPressure;
 224
 225   LiveRegs.init(*MRI);
 226   if (TrackUntiedDefs)
 227     UntiedDefs.setUniverse(MRI->getNumVirtRegs());
 228 }
 229
 230 /// Does this pressure result have a valid top position and live ins.
 231 bool RegPressureTracker::isTopClosed() const {
 232   if (RequireIntervals)
 233     return static_cast<IntervalPressure&>(P).TopIdx.isValid();
 234   return (static_cast<RegionPressure&>(P).TopPos ==
 235           MachineBasicBlock::const_iterator());
 236 }
 237
 238 /// Does this pressure result have a valid bottom position and live outs.
 239 bool RegPressureTracker::isBottomClosed() const {
 240   if (RequireIntervals)
 241     return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
 242   return (static_cast<RegionPressure&>(P).BottomPos ==
 243           MachineBasicBlock::const_iterator());
 244 }
 245
 246
 247 SlotIndex RegPressureTracker::getCurrSlot() const {
 248   MachineBasicBlock::const_iterator IdxPos = CurrPos;
 249   while (IdxPos != MBB->end() && IdxPos->isDebugValue())
 250     ++IdxPos;
 251   if (IdxPos == MBB->end())
 252     return LIS->getMBBEndIdx(MBB);
 253   return LIS->getInstructionIndex(IdxPos).getRegSlot();
 254 }
 255
 256 /// Set the boundary for the top of the region and summarize live ins.
 257 void RegPressureTracker::closeTop() {
 258   if (RequireIntervals)
 259     static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
 260   else
 261     static_cast<RegionPressure&>(P).TopPos = CurrPos;
 262
 263   assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
 264   P.LiveInRegs.reserve(LiveRegs.size());
 265   LiveRegs.appendTo(P.LiveInRegs);
 266 }
 267
 268 /// Set the boundary for the bottom of the region and summarize live outs.
 269 void RegPressureTracker::closeBottom() {
 270   if (RequireIntervals)
 271     static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
 272   else
 273     static_cast<RegionPressure&>(P).BottomPos = CurrPos;
 274
 275   assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
 276   P.LiveOutRegs.reserve(LiveRegs.size());
 277   LiveRegs.appendTo(P.LiveOutRegs);
 278 }
 279
 280 /// Finalize the region boundaries and record live ins and live outs.
 281 void RegPressureTracker::closeRegion() {
 282   if (!isTopClosed() && !isBottomClosed()) {
 283     assert(LiveRegs.size() == 0 && "no region boundary");
 284     return;
 285   }
 286   if (!isBottomClosed())
 287     closeBottom();
 288   else if (!isTopClosed())
 289     closeTop();
 290   // If both top and bottom are closed, do nothing.
 291 }
 292
 293 /// The register tracker is unaware of global liveness so ignores normal
 294 /// live-thru ranges. However, two-address or coalesced chains can also lead
 295 /// to live ranges with no holes. Count these to inform heuristics that we
 296 /// can never drop below this pressure.
 297 void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
 298   LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
 299   assert(isBottomClosed() && "need bottom-up tracking to intialize.");
 300   for (unsigned Reg : P.LiveOutRegs) {
 301     if (TargetRegisterInfo::isVirtualRegister(Reg)
 302         && !RPTracker.hasUntiedDef(Reg)) {
 303       increaseSetPressure(LiveThruPressure, MRI->getPressureSets(Reg));
 304     }
 305   }
 306 }
 307
 308 /// \brief Convenient wrapper for checking membership in RegisterOperands.
 309 /// (std::count() doesn't have an early exit).
 310 static bool containsReg(ArrayRef<unsigned> RegUnits, unsigned RegUnit) {
 311   return std::find(RegUnits.begin(), RegUnits.end(), RegUnit) != RegUnits.end();
 312 }
 313
 314 namespace {
 315
 316 /// List of register defined and used by a machine instruction.
 317 class RegisterOperands {
 318 public:
 319   SmallVector<unsigned, 8> Uses;
 320   SmallVector<unsigned, 8> Defs;
 321   SmallVector<unsigned, 8> DeadDefs;
 322
 323   void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI,
 324                const MachineRegisterInfo &MRI, bool IgnoreDead = false);
 325
 326   /// Use liveness information to find dead defs not marked with a dead flag
 327   /// and move them to the DeadDefs vector.
 328   void detectDeadDefs(const MachineInstr &MI, const LiveIntervals &LIS);
 329 };
 330
 331 /// Collect this instruction's unique uses and defs into SmallVectors for
 332 /// processing defs and uses in order.
 333 ///
 334 /// FIXME: always ignore tied opers
 335 class RegisterOperandsCollector {
 336   RegisterOperands &RegOpers;
 337   const TargetRegisterInfo &TRI;
 338   const MachineRegisterInfo &MRI;
 339   bool IgnoreDead;
 340
 341   RegisterOperandsCollector(RegisterOperands &RegOpers,
 342                             const TargetRegisterInfo &TRI,
 343                             const MachineRegisterInfo &MRI,
 344                             bool IgnoreDead)
 345     : RegOpers(RegOpers), TRI(TRI), MRI(MRI), IgnoreDead(IgnoreDead) {}
 346
 347   void collectInstr(const MachineInstr &MI) const {
 348     for (ConstMIBundleOperands OperI(&MI); OperI.isValid(); ++OperI)
 349       collectOperand(*OperI);
 350
 351     // Remove redundant physreg dead defs.
 352     SmallVectorImpl<unsigned>::iterator I =
 353       std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(),
 354                      std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs));
 355     RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end());
 356   }
 357
 358   /// Push this operand's register onto the correct vectors.
 359   void collectOperand(const MachineOperand &MO) const {
 360     if (!MO.isReg() || !MO.getReg())
 361       return;
 362     unsigned Reg = MO.getReg();
 363     if (MO.readsReg())
 364       pushRegUnits(Reg, RegOpers.Uses);
 365     if (MO.isDef()) {
 366       if (MO.isDead()) {
 367         if (!IgnoreDead)
 368           pushRegUnits(Reg, RegOpers.DeadDefs);
 369       } else
 370         pushRegUnits(Reg, RegOpers.Defs);
 371     }
 372   }
 373
 374   void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &RegUnits) const {
 375     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 376       if (containsReg(RegUnits, Reg))
 377         return;
 378       RegUnits.push_back(Reg);
 379     } else if (MRI.isAllocatable(Reg)) {
 380       for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) {
 381         if (containsReg(RegUnits, *Units))
 382           continue;
 383         RegUnits.push_back(*Units);
 384       }
 385     }
 386   }
 387
 388   friend class RegisterOperands;
 389 };
 390
 391 void RegisterOperands::collect(const MachineInstr &MI,
 392                                const TargetRegisterInfo &TRI,
 393                                const MachineRegisterInfo &MRI,
 394                                bool IgnoreDead) {
 395   RegisterOperandsCollector Collector(*this, TRI, MRI, IgnoreDead);
 396   Collector.collectInstr(MI);
 397 }
 398
 399 void RegisterOperands::detectDeadDefs(const MachineInstr &MI,
 400                                       const LiveIntervals &LIS) {
 401   SlotIndex SlotIdx = LIS.getInstructionIndex(&MI);
 402   for (SmallVectorImpl<unsigned>::iterator RI = Defs.begin();
 403        RI != Defs.end(); /*empty*/) {
 404     unsigned Reg = *RI;
 405     const LiveRange *LR = getLiveRange(LIS, Reg);
 406     if (LR != nullptr) {
 407       LiveQueryResult LRQ = LR->Query(SlotIdx);
 408       if (LRQ.isDeadDef()) {
 409         // LiveIntervals knows this is a dead even though it's MachineOperand is
 410         // not flagged as such.
 411         DeadDefs.push_back(Reg);
 412         RI = Defs.erase(RI);
 413         continue;
 414       }
 415     }
 416     ++RI;
 417   }
 418 }
 419
 420 } // namespace
 421
 422 /// Initialize an array of N PressureDiffs.
 423 void PressureDiffs::init(unsigned N) {
 424   Size = N;
 425   if (N <= Max) {
 426     memset(PDiffArray, 0, N * sizeof(PressureDiff));
 427     return;
 428   }
 429   Max = Size;
 430   free(PDiffArray);
 431   PDiffArray = reinterpret_cast<PressureDiff*>(calloc(N, sizeof(PressureDiff)));
 432 }
 433
 434 /// Add a change in pressure to the pressure diff of a given instruction.
 435 void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec,
 436                                      const MachineRegisterInfo *MRI) {
 437   PSetIterator PSetI = MRI->getPressureSets(RegUnit);
 438   int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight();
 439   for (; PSetI.isValid(); ++PSetI) {
 440     // Find an existing entry in the pressure diff for this PSet.
 441     PressureDiff::iterator I = nonconst_begin(), E = nonconst_end();
 442     for (; I != E && I->isValid(); ++I) {
 443       if (I->getPSet() >= *PSetI)
 444         break;
 445     }
 446     // If all pressure sets are more constrained, skip the remaining PSets.
 447     if (I == E)
 448       break;
 449     // Insert this PressureChange.
 450     if (!I->isValid() || I->getPSet() != *PSetI) {
 451       PressureChange PTmp = PressureChange(*PSetI);
 452       for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J)
 453         std::swap(*J, PTmp);
 454     }
 455     // Update the units for this pressure set.
 456     unsigned NewUnitInc = I->getUnitInc() + Weight;
 457     if (NewUnitInc != 0) {
 458       I->setUnitInc(NewUnitInc);
 459     } else {
 460       // Remove entry
 461       PressureDiff::iterator J;
 462       for (J = std::next(I); J != E && J->isValid(); ++J, ++I)
 463         *I = *J;
 464       if (J != E)
 465         *I = *J;
 466     }
 467   }
 468 }
 469
 470 /// Record the pressure difference induced by the given operand list.
 471 static void collectPDiff(PressureDiff &PDiff, RegisterOperands &RegOpers,
 472                          const MachineRegisterInfo *MRI) {
 473   assert(!PDiff.begin()->isValid() && "stale PDiff");
 474
 475   for (unsigned Reg : RegOpers.Defs)
 476     PDiff.addPressureChange(Reg, true, MRI);
 477
 478   for (unsigned Reg : RegOpers.Uses)
 479     PDiff.addPressureChange(Reg, false, MRI);
 480 }
 481
 482 /// Force liveness of registers.
 483 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
 484   for (unsigned Reg : Regs) {
 485     if (LiveRegs.insert(Reg))
 486       increaseRegPressure(Reg);
 487   }
 488 }
 489
 490 /// Add Reg to the live in set and increase max pressure.
 491 void RegPressureTracker::discoverLiveIn(unsigned Reg) {
 492   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
 493   if (containsReg(P.LiveInRegs, Reg))
 494     return;
 495
 496   // At live in discovery, unconditionally increase the high water mark.
 497   P.LiveInRegs.push_back(Reg);
 498   increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg));
 499 }
 500
 501 /// Add Reg to the live out set and increase max pressure.
 502 void RegPressureTracker::discoverLiveOut(unsigned Reg) {
 503   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
 504   if (containsReg(P.LiveOutRegs, Reg))
 505     return;
 506
 507   // At live out discovery, unconditionally increase the high water mark.
 508   P.LiveOutRegs.push_back(Reg);
 509   increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg));
 510 }
 511
 512 /// Recede across the previous instruction. If LiveUses is provided, record any
 513 /// RegUnits that are made live by the current instruction's uses. This includes
 514 /// registers that are both defined and used by the instruction.  If a pressure
 515 /// difference pointer is provided record the changes is pressure caused by this
 516 /// instruction independent of liveness.
 517 void RegPressureTracker::recede(SmallVectorImpl<unsigned> *LiveUses,
 518                                 PressureDiff *PDiff) {
 519   assert(CurrPos != MBB->begin());
 520   if (!isBottomClosed())
 521     closeBottom();
 522
 523   // Open the top of the region using block iterators.
 524   if (!RequireIntervals && isTopClosed())
 525     static_cast<RegionPressure&>(P).openTop(CurrPos);
 526
 527   // Find the previous instruction.
 528   do
 529     --CurrPos;
 530   while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
 531   assert(!CurrPos->isDebugValue());
 532
 533   SlotIndex SlotIdx;
 534   if (RequireIntervals)
 535     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
 536
 537   // Open the top of the region using slot indexes.
 538   if (RequireIntervals && isTopClosed())
 539     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
 540
 541   const MachineInstr &MI = *CurrPos;
 542   RegisterOperands RegOpers;
 543   RegOpers.collect(MI, *TRI, *MRI);
 544   if (RequireIntervals)
 545     RegOpers.detectDeadDefs(MI, *LIS);
 546
 547   if (PDiff)
 548     collectPDiff(*PDiff, RegOpers, MRI);
 549
 550   // Boost pressure for all dead defs together.
 551   increaseRegPressure(RegOpers.DeadDefs);
 552   decreaseRegPressure(RegOpers.DeadDefs);
 553
 554   // Kill liveness at live defs.
 555   // TODO: consider earlyclobbers?
 556   for (unsigned Reg : RegOpers.Defs) {
 557     if (LiveRegs.erase(Reg))
 558       decreaseRegPressure(Reg);
 559     else
 560       discoverLiveOut(Reg);
 561   }
 562
 563   // Generate liveness for uses.
 564   for (unsigned Reg : RegOpers.Uses) {
 565     if (!LiveRegs.contains(Reg)) {
 566       // Adjust liveouts if LiveIntervals are available.
 567       if (RequireIntervals) {
 568         const LiveRange *LR = getLiveRange(*LIS, Reg);
 569         if (LR) {
 570           LiveQueryResult LRQ = LR->Query(SlotIdx);
 571           if (!LRQ.isKill() && !LRQ.valueDefined())
 572             discoverLiveOut(Reg);
 573         }
 574       }
 575       increaseRegPressure(Reg);
 576       LiveRegs.insert(Reg);
 577       if (LiveUses && !containsReg(*LiveUses, Reg))
 578         LiveUses->push_back(Reg);
 579     }
 580   }
 581   if (TrackUntiedDefs) {
 582     for (unsigned Reg : RegOpers.Defs) {
 583       if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg))
 584         UntiedDefs.insert(Reg);
 585     }
 586   }
 587 }
 588
 589 /// Advance across the current instruction.
 590 void RegPressureTracker::advance() {
 591   assert(!TrackUntiedDefs && "unsupported mode");
 592
 593   assert(CurrPos != MBB->end());
 594   if (!isTopClosed())
 595     closeTop();
 596
 597   SlotIndex SlotIdx;
 598   if (RequireIntervals)
 599     SlotIdx = getCurrSlot();
 600
 601   // Open the bottom of the region using slot indexes.
 602   if (isBottomClosed()) {
 603     if (RequireIntervals)
 604       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
 605     else
 606       static_cast<RegionPressure&>(P).openBottom(CurrPos);
 607   }
 608
 609   RegisterOperands RegOpers;
 610   RegOpers.collect(*CurrPos, *TRI, *MRI);
 611
 612   for (unsigned Reg : RegOpers.Uses) {
 613     // Discover live-ins.
 614     bool isLive = LiveRegs.contains(Reg);
 615     if (!isLive)
 616       discoverLiveIn(Reg);
 617     // Kill liveness at last uses.
 618     bool lastUse = false;
 619     if (RequireIntervals) {
 620       const LiveRange *LR = getLiveRange(*LIS, Reg);
 621       lastUse = LR && LR->Query(SlotIdx).isKill();
 622     } else {
 623       // Allocatable physregs are always single-use before register rewriting.
 624       lastUse = !TargetRegisterInfo::isVirtualRegister(Reg);
 625     }
 626     if (lastUse && isLive) {
 627       LiveRegs.erase(Reg);
 628       decreaseRegPressure(Reg);
 629     } else if (!lastUse && !isLive)
 630       increaseRegPressure(Reg);
 631   }
 632
 633   // Generate liveness for defs.
 634   for (unsigned Reg : RegOpers.Defs) {
 635     if (LiveRegs.insert(Reg))
 636       increaseRegPressure(Reg);
 637   }
 638
 639   // Boost pressure for all dead defs together.
 640   increaseRegPressure(RegOpers.DeadDefs);
 641   decreaseRegPressure(RegOpers.DeadDefs);
 642
 643   // Find the next instruction.
 644   do
 645     ++CurrPos;
 646   while (CurrPos != MBB->end() && CurrPos->isDebugValue());
 647 }
 648
 649 /// Find the max change in excess pressure across all sets.
 650 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
 651                                        ArrayRef<unsigned> NewPressureVec,
 652                                        RegPressureDelta &Delta,
 653                                        const RegisterClassInfo *RCI,
 654                                        ArrayRef<unsigned> LiveThruPressureVec) {
 655   Delta.Excess = PressureChange();
 656   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 657     unsigned POld = OldPressureVec[i];
 658     unsigned PNew = NewPressureVec[i];
 659     int PDiff = (int)PNew - (int)POld;
 660     if (!PDiff) // No change in this set in the common case.
 661       continue;
 662     // Only consider change beyond the limit.
 663     unsigned Limit = RCI->getRegPressureSetLimit(i);
 664     if (!LiveThruPressureVec.empty())
 665       Limit += LiveThruPressureVec[i];
 666
 667     if (Limit > POld) {
 668       if (Limit > PNew)
 669         PDiff = 0;            // Under the limit
 670       else
 671         PDiff = PNew - Limit; // Just exceeded limit.
 672     } else if (Limit > PNew)
 673       PDiff = Limit - POld;   // Just obeyed limit.
 674
 675     if (PDiff) {
 676       Delta.Excess = PressureChange(i);
 677       Delta.Excess.setUnitInc(PDiff);
 678       break;
 679     }
 680   }
 681 }
 682
 683 /// Find the max change in max pressure that either surpasses a critical PSet
 684 /// limit or exceeds the current MaxPressureLimit.
 685 ///
 686 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
 687 /// silly. It's done now to demonstrate the concept but will go away with a
 688 /// RegPressureTracker API change to work with pressure differences.
 689 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
 690                                     ArrayRef<unsigned> NewMaxPressureVec,
 691                                     ArrayRef<PressureChange> CriticalPSets,
 692                                     ArrayRef<unsigned> MaxPressureLimit,
 693                                     RegPressureDelta &Delta) {
 694   Delta.CriticalMax = PressureChange();
 695   Delta.CurrentMax = PressureChange();
 696
 697   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 698   for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
 699     unsigned POld = OldMaxPressureVec[i];
 700     unsigned PNew = NewMaxPressureVec[i];
 701     if (PNew == POld) // No change in this set in the common case.
 702       continue;
 703
 704     if (!Delta.CriticalMax.isValid()) {
 705       while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
 706         ++CritIdx;
 707
 708       if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
 709         int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
 710         if (PDiff > 0) {
 711           Delta.CriticalMax = PressureChange(i);
 712           Delta.CriticalMax.setUnitInc(PDiff);
 713         }
 714       }
 715     }
 716     // Find the first increase above MaxPressureLimit.
 717     // (Ignores negative MDiff).
 718     if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
 719       Delta.CurrentMax = PressureChange(i);
 720       Delta.CurrentMax.setUnitInc(PNew - POld);
 721       if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
 722         break;
 723     }
 724   }
 725 }
 726
 727 /// Record the upward impact of a single instruction on current register
 728 /// pressure. Unlike the advance/recede pressure tracking interface, this does
 729 /// not discover live in/outs.
 730 ///
 731 /// This is intended for speculative queries. It leaves pressure inconsistent
 732 /// with the current position, so must be restored by the caller.
 733 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
 734   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
 735
 736   // Account for register pressure similar to RegPressureTracker::recede().
 737   RegisterOperands RegOpers;
 738   RegOpers.collect(*MI, *TRI, *MRI, /*IgnoreDead=*/true);
 739   assert(RegOpers.DeadDefs.size() == 0);
 740   if (RequireIntervals)
 741     RegOpers.detectDeadDefs(*MI, *LIS);
 742
 743   // Kill liveness at live defs.
 744   for (unsigned Reg : RegOpers.Defs) {
 745     if (!containsReg(RegOpers.Uses, Reg))
 746       decreaseRegPressure(Reg);
 747   }
 748   // Generate liveness for uses.
 749   for (unsigned Reg : RegOpers.Uses) {
 750     if (!LiveRegs.contains(Reg))
 751       increaseRegPressure(Reg);
 752   }
 753 }
 754
 755 /// Consider the pressure increase caused by traversing this instruction
 756 /// bottom-up. Find the pressure set with the most change beyond its pressure
 757 /// limit based on the tracker's current pressure, and return the change in
 758 /// number of register units of that pressure set introduced by this
 759 /// instruction.
 760 ///
 761 /// This assumes that the current LiveOut set is sufficient.
 762 ///
 763 /// This is expensive for an on-the-fly query because it calls
 764 /// bumpUpwardPressure to recompute the pressure sets based on current
 765 /// liveness. This mainly exists to verify correctness, e.g. with
 766 /// -verify-misched. getUpwardPressureDelta is the fast version of this query
 767 /// that uses the per-SUnit cache of the PressureDiff.
 768 void RegPressureTracker::
 769 getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
 770                           RegPressureDelta &Delta,
 771                           ArrayRef<PressureChange> CriticalPSets,
 772                           ArrayRef<unsigned> MaxPressureLimit) {
 773   // Snapshot Pressure.
 774   // FIXME: The snapshot heap space should persist. But I'm planning to
 775   // summarize the pressure effect so we don't need to snapshot at all.
 776   std::vector<unsigned> SavedPressure = CurrSetPressure;
 777   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 778
 779   bumpUpwardPressure(MI);
 780
 781   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
 782                              LiveThruPressure);
 783   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 784                           MaxPressureLimit, Delta);
 785   assert(Delta.CriticalMax.getUnitInc() >= 0 &&
 786          Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
 787
 788   // Restore the tracker's state.
 789   P.MaxSetPressure.swap(SavedMaxPressure);
 790   CurrSetPressure.swap(SavedPressure);
 791
 792 #ifndef NDEBUG
 793   if (!PDiff)
 794     return;
 795
 796   // Check if the alternate algorithm yields the same result.
 797   RegPressureDelta Delta2;
 798   getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
 799   if (Delta != Delta2) {
 800     dbgs() << "PDiff: ";
 801     PDiff->dump(*TRI);
 802     dbgs() << "DELTA: " << *MI;
 803     if (Delta.Excess.isValid())
 804       dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
 805              << " " << Delta.Excess.getUnitInc() << "\n";
 806     if (Delta.CriticalMax.isValid())
 807       dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
 808              << " " << Delta.CriticalMax.getUnitInc() << "\n";
 809     if (Delta.CurrentMax.isValid())
 810       dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
 811              << " " << Delta.CurrentMax.getUnitInc() << "\n";
 812     if (Delta2.Excess.isValid())
 813       dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
 814              << " " << Delta2.Excess.getUnitInc() << "\n";
 815     if (Delta2.CriticalMax.isValid())
 816       dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
 817              << " " << Delta2.CriticalMax.getUnitInc() << "\n";
 818     if (Delta2.CurrentMax.isValid())
 819       dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
 820              << " " << Delta2.CurrentMax.getUnitInc() << "\n";
 821     llvm_unreachable("RegP Delta Mismatch");
 822   }
 823 #endif
 824 }
 825
 826 /// This is the fast version of querying register pressure that does not
 827 /// directly depend on current liveness.
 828 ///
 829 /// @param Delta captures information needed for heuristics.
 830 ///
 831 /// @param CriticalPSets Are the pressure sets that are known to exceed some
 832 /// limit within the region, not necessarily at the current position.
 833 ///
 834 /// @param MaxPressureLimit Is the max pressure within the region, not
 835 /// necessarily at the current position.
 836 void RegPressureTracker::
 837 getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
 838                        RegPressureDelta &Delta,
 839                        ArrayRef<PressureChange> CriticalPSets,
 840                        ArrayRef<unsigned> MaxPressureLimit) const {
 841   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 842   for (PressureDiff::const_iterator
 843          PDiffI = PDiff.begin(), PDiffE = PDiff.end();
 844        PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
 845
 846     unsigned PSetID = PDiffI->getPSet();
 847     unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
 848     if (!LiveThruPressure.empty())
 849       Limit += LiveThruPressure[PSetID];
 850
 851     unsigned POld = CurrSetPressure[PSetID];
 852     unsigned MOld = P.MaxSetPressure[PSetID];
 853     unsigned MNew = MOld;
 854     // Ignore DeadDefs here because they aren't captured by PressureChange.
 855     unsigned PNew = POld + PDiffI->getUnitInc();
 856     assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
 857            && "PSet overflow/underflow");
 858     if (PNew > MOld)
 859       MNew = PNew;
 860     // Check if current pressure has exceeded the limit.
 861     if (!Delta.Excess.isValid()) {
 862       unsigned ExcessInc = 0;
 863       if (PNew > Limit)
 864         ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
 865       else if (POld > Limit)
 866         ExcessInc = Limit - POld;
 867       if (ExcessInc) {
 868         Delta.Excess = PressureChange(PSetID);
 869         Delta.Excess.setUnitInc(ExcessInc);
 870       }
 871     }
 872     // Check if max pressure has exceeded a critical pressure set max.
 873     if (MNew == MOld)
 874       continue;
 875     if (!Delta.CriticalMax.isValid()) {
 876       while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
 877         ++CritIdx;
 878
 879       if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
 880         int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
 881         if (CritInc > 0 && CritInc <= INT16_MAX) {
 882           Delta.CriticalMax = PressureChange(PSetID);
 883           Delta.CriticalMax.setUnitInc(CritInc);
 884         }
 885       }
 886     }
 887     // Check if max pressure has exceeded the current max.
 888     if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
 889       Delta.CurrentMax = PressureChange(PSetID);
 890       Delta.CurrentMax.setUnitInc(MNew - MOld);
 891     }
 892   }
 893 }
 894
 895 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
 896 static bool findUseBetween(unsigned Reg, SlotIndex PriorUseIdx,
 897                            SlotIndex NextUseIdx, const MachineRegisterInfo &MRI,
 898                            const LiveIntervals *LIS) {
 899   for (const MachineInstr &MI : MRI.use_nodbg_instructions(Reg)) {
 900     SlotIndex InstSlot = LIS->getInstructionIndex(&MI).getRegSlot();
 901     if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
 902       return true;
 903   }
 904   return false;
 905 }
 906
 907 /// Record the downward impact of a single instruction on current register
 908 /// pressure. Unlike the advance/recede pressure tracking interface, this does
 909 /// not discover live in/outs.
 910 ///
 911 /// This is intended for speculative queries. It leaves pressure inconsistent
 912 /// with the current position, so must be restored by the caller.
 913 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
 914   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
 915
 916   // Account for register pressure similar to RegPressureTracker::recede().
 917   RegisterOperands RegOpers;
 918   RegOpers.collect(*MI, *TRI, *MRI);
 919
 920   // Kill liveness at last uses. Assume allocatable physregs are single-use
 921   // rather than checking LiveIntervals.
 922   SlotIndex SlotIdx;
 923   if (RequireIntervals)
 924     SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
 925
 926   for (unsigned Reg : RegOpers.Uses) {
 927     if (RequireIntervals) {
 928       // FIXME: allow the caller to pass in the list of vreg uses that remain
 929       // to be bottom-scheduled to avoid searching uses at each query.
 930       SlotIndex CurrIdx = getCurrSlot();
 931       const LiveRange *LR = getLiveRange(*LIS, Reg);
 932       if (LR) {
 933         LiveQueryResult LRQ = LR->Query(SlotIdx);
 934         if (LRQ.isKill() && !findUseBetween(Reg, CurrIdx, SlotIdx, *MRI, LIS))
 935           decreaseRegPressure(Reg);
 936       }
 937     } else if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
 938       // Allocatable physregs are always single-use before register rewriting.
 939       decreaseRegPressure(Reg);
 940     }
 941   }
 942
 943   // Generate liveness for defs.
 944   increaseRegPressure(RegOpers.Defs);
 945
 946   // Boost pressure for all dead defs together.
 947   increaseRegPressure(RegOpers.DeadDefs);
 948   decreaseRegPressure(RegOpers.DeadDefs);
 949 }
 950
 951 /// Consider the pressure increase caused by traversing this instruction
 952 /// top-down. Find the register class with the most change in its pressure limit
 953 /// based on the tracker's current pressure, and return the number of excess
 954 /// register units of that pressure set introduced by this instruction.
 955 ///
 956 /// This assumes that the current LiveIn set is sufficient.
 957 ///
 958 /// This is expensive for an on-the-fly query because it calls
 959 /// bumpDownwardPressure to recompute the pressure sets based on current
 960 /// liveness. We don't yet have a fast version of downward pressure tracking
 961 /// analogous to getUpwardPressureDelta.
 962 void RegPressureTracker::
 963 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
 964                             ArrayRef<PressureChange> CriticalPSets,
 965                             ArrayRef<unsigned> MaxPressureLimit) {
 966   // Snapshot Pressure.
 967   std::vector<unsigned> SavedPressure = CurrSetPressure;
 968   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
 969
 970   bumpDownwardPressure(MI);
 971
 972   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
 973                              LiveThruPressure);
 974   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
 975                           MaxPressureLimit, Delta);
 976   assert(Delta.CriticalMax.getUnitInc() >= 0 &&
 977          Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
 978
 979   // Restore the tracker's state.
 980   P.MaxSetPressure.swap(SavedMaxPressure);
 981   CurrSetPressure.swap(SavedPressure);
 982 }
 983
 984 /// Get the pressure of each PSet after traversing this instruction bottom-up.
 985 void RegPressureTracker::
 986 getUpwardPressure(const MachineInstr *MI,
 987                   std::vector<unsigned> &PressureResult,
 988                   std::vector<unsigned> &MaxPressureResult) {
 989   // Snapshot pressure.
 990   PressureResult = CurrSetPressure;
 991   MaxPressureResult = P.MaxSetPressure;
 992
 993   bumpUpwardPressure(MI);
 994
 995   // Current pressure becomes the result. Restore current pressure.
 996   P.MaxSetPressure.swap(MaxPressureResult);
 997   CurrSetPressure.swap(PressureResult);
 998 }
 999
1000 /// Get the pressure of each PSet after traversing this instruction top-down.
1001 void RegPressureTracker::
1002 getDownwardPressure(const MachineInstr *MI,
1003                     std::vector<unsigned> &PressureResult,
1004                     std::vector<unsigned> &MaxPressureResult) {
1005   // Snapshot pressure.
1006   PressureResult = CurrSetPressure;
1007   MaxPressureResult = P.MaxSetPressure;
1008
1009   bumpDownwardPressure(MI);
1010
1011   // Current pressure becomes the result. Restore current pressure.
1012   P.MaxSetPressure.swap(MaxPressureResult);
1013   CurrSetPressure.swap(PressureResult);
1014 }