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