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/ADT/ArrayRef.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/CodeGen/LiveInterval.h"
  20 #include "llvm/CodeGen/LiveIntervals.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineFunction.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/MachineInstrBundle.h"
  25 #include "llvm/CodeGen/MachineOperand.h"
  26 #include "llvm/CodeGen/MachineRegisterInfo.h"
  27 #include "llvm/CodeGen/RegisterClassInfo.h"
  28 #include "llvm/CodeGen/SlotIndexes.h"
  29 #include "llvm/CodeGen/TargetRegisterInfo.h"
  30 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  31 #include "llvm/Config/llvm-config.h"
  32 #include "llvm/MC/LaneBitmask.h"
  33 #include "llvm/MC/MCRegisterInfo.h"
  34 #include "llvm/Support/Compiler.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/ErrorHandling.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include <algorithm>
  39 #include <cassert>
  40 #include <cstdint>
  41 #include <cstdlib>
  42 #include <cstring>
  43 #include <iterator>
  44 #include <limits>
  45 #include <utility>
  46 #include <vector>
  47
  48 using namespace llvm;
  49
  50 /// Increase pressure for each pressure set provided by TargetRegisterInfo.
  51 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
  52                                 const MachineRegisterInfo &MRI, unsigned Reg,
  53                                 LaneBitmask PrevMask, LaneBitmask NewMask) {
  54   assert((PrevMask & ~NewMask).none() && "Must not remove bits");
  55   if (PrevMask.any() || NewMask.none())
  56     return;
  57
  58   PSetIterator PSetI = MRI.getPressureSets(Reg);
  59   unsigned Weight = PSetI.getWeight();
  60   for (; PSetI.isValid(); ++PSetI)
  61     CurrSetPressure[*PSetI] += Weight;
  62 }
  63
  64 /// Decrease pressure for each pressure set provided by TargetRegisterInfo.
  65 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
  66                                 const MachineRegisterInfo &MRI, unsigned Reg,
  67                                 LaneBitmask PrevMask, LaneBitmask NewMask) {
  68   //assert((NewMask & !PrevMask) == 0 && "Must not add bits");
  69   if (NewMask.any() || PrevMask.none())
  70     return;
  71
  72   PSetIterator PSetI = MRI.getPressureSets(Reg);
  73   unsigned Weight = PSetI.getWeight();
  74   for (; PSetI.isValid(); ++PSetI) {
  75     assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow");
  76     CurrSetPressure[*PSetI] -= Weight;
  77   }
  78 }
  79
  80 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  81 LLVM_DUMP_METHOD
  82 void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
  83                               const TargetRegisterInfo *TRI) {
  84   bool Empty = true;
  85   for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
  86     if (SetPressure[i] != 0) {
  87       dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
  88       Empty = false;
  89     }
  90   }
  91   if (Empty)
  92     dbgs() << "\n";
  93 }
  94
  95 LLVM_DUMP_METHOD
  96 void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
  97   dbgs() << "Max Pressure: ";
  98   dumpRegSetPressure(MaxSetPressure, TRI);
  99   dbgs() << "Live In: ";
 100   for (const RegisterMaskPair &P : LiveInRegs) {
 101     dbgs() << printVRegOrUnit(P.RegUnit, TRI);
 102     if (!P.LaneMask.all())
 103       dbgs() << ':' << PrintLaneMask(P.LaneMask);
 104     dbgs() << ' ';
 105   }
 106   dbgs() << '\n';
 107   dbgs() << "Live Out: ";
 108   for (const RegisterMaskPair &P : LiveOutRegs) {
 109     dbgs() << printVRegOrUnit(P.RegUnit, TRI);
 110     if (!P.LaneMask.all())
 111       dbgs() << ':' << PrintLaneMask(P.LaneMask);
 112     dbgs() << ' ';
 113   }
 114   dbgs() << '\n';
 115 }
 116
 117 LLVM_DUMP_METHOD
 118 void RegPressureTracker::dump() const {
 119   if (!isTopClosed() || !isBottomClosed()) {
 120     dbgs() << "Curr Pressure: ";
 121     dumpRegSetPressure(CurrSetPressure, TRI);
 122   }
 123   P.dump(TRI);
 124 }
 125
 126 LLVM_DUMP_METHOD
 127 void PressureDiff::dump(const TargetRegisterInfo &TRI) const {
 128   const char *sep = "";
 129   for (const PressureChange &Change : *this) {
 130     if (!Change.isValid())
 131       break;
 132     dbgs() << sep << TRI.getRegPressureSetName(Change.getPSet())
 133            << " " << Change.getUnitInc();
 134     sep = "    ";
 135   }
 136   dbgs() << '\n';
 137 }
 138 #endif
 139
 140 void RegPressureTracker::increaseRegPressure(unsigned RegUnit,
 141                                              LaneBitmask PreviousMask,
 142                                              LaneBitmask NewMask) {
 143   if (PreviousMask.any() || NewMask.none())
 144     return;
 145
 146   PSetIterator PSetI = MRI->getPressureSets(RegUnit);
 147   unsigned Weight = PSetI.getWeight();
 148   for (; PSetI.isValid(); ++PSetI) {
 149     CurrSetPressure[*PSetI] += Weight;
 150     P.MaxSetPressure[*PSetI] =
 151         std::max(P.MaxSetPressure[*PSetI], CurrSetPressure[*PSetI]);
 152   }
 153 }
 154
 155 void RegPressureTracker::decreaseRegPressure(unsigned RegUnit,
 156                                              LaneBitmask PreviousMask,
 157                                              LaneBitmask NewMask) {
 158   decreaseSetPressure(CurrSetPressure, *MRI, RegUnit, PreviousMask, NewMask);
 159 }
 160
 161 /// Clear the result so it can be used for another round of pressure tracking.
 162 void IntervalPressure::reset() {
 163   TopIdx = BottomIdx = SlotIndex();
 164   MaxSetPressure.clear();
 165   LiveInRegs.clear();
 166   LiveOutRegs.clear();
 167 }
 168
 169 /// Clear the result so it can be used for another round of pressure tracking.
 170 void RegionPressure::reset() {
 171   TopPos = BottomPos = MachineBasicBlock::const_iterator();
 172   MaxSetPressure.clear();
 173   LiveInRegs.clear();
 174   LiveOutRegs.clear();
 175 }
 176
 177 /// If the current top is not less than or equal to the next index, open it.
 178 /// We happen to need the SlotIndex for the next top for pressure update.
 179 void IntervalPressure::openTop(SlotIndex NextTop) {
 180   if (TopIdx <= NextTop)
 181     return;
 182   TopIdx = SlotIndex();
 183   LiveInRegs.clear();
 184 }
 185
 186 /// If the current top is the previous instruction (before receding), open it.
 187 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
 188   if (TopPos != PrevTop)
 189     return;
 190   TopPos = MachineBasicBlock::const_iterator();
 191   LiveInRegs.clear();
 192 }
 193
 194 /// If the current bottom is not greater than the previous index, open it.
 195 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
 196   if (BottomIdx > PrevBottom)
 197     return;
 198   BottomIdx = SlotIndex();
 199   LiveInRegs.clear();
 200 }
 201
 202 /// If the current bottom is the previous instr (before advancing), open it.
 203 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
 204   if (BottomPos != PrevBottom)
 205     return;
 206   BottomPos = MachineBasicBlock::const_iterator();
 207   LiveInRegs.clear();
 208 }
 209
 210 void LiveRegSet::init(const MachineRegisterInfo &MRI) {
 211   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 212   unsigned NumRegUnits = TRI.getNumRegs();
 213   unsigned NumVirtRegs = MRI.getNumVirtRegs();
 214   Regs.setUniverse(NumRegUnits + NumVirtRegs);
 215   this->NumRegUnits = NumRegUnits;
 216 }
 217
 218 void LiveRegSet::clear() {
 219   Regs.clear();
 220 }
 221
 222 static const LiveRange *getLiveRange(const LiveIntervals &LIS, unsigned Reg) {
 223   if (TargetRegisterInfo::isVirtualRegister(Reg))
 224     return &LIS.getInterval(Reg);
 225   return LIS.getCachedRegUnit(Reg);
 226 }
 227
 228 void RegPressureTracker::reset() {
 229   MBB = nullptr;
 230   LIS = nullptr;
 231
 232   CurrSetPressure.clear();
 233   LiveThruPressure.clear();
 234   P.MaxSetPressure.clear();
 235
 236   if (RequireIntervals)
 237     static_cast<IntervalPressure&>(P).reset();
 238   else
 239     static_cast<RegionPressure&>(P).reset();
 240
 241   LiveRegs.clear();
 242   UntiedDefs.clear();
 243 }
 244
 245 /// Setup the RegPressureTracker.
 246 ///
 247 /// TODO: Add support for pressure without LiveIntervals.
 248 void RegPressureTracker::init(const MachineFunction *mf,
 249                               const RegisterClassInfo *rci,
 250                               const LiveIntervals *lis,
 251                               const MachineBasicBlock *mbb,
 252                               MachineBasicBlock::const_iterator pos,
 253                               bool TrackLaneMasks, bool TrackUntiedDefs) {
 254   reset();
 255
 256   MF = mf;
 257   TRI = MF->getSubtarget().getRegisterInfo();
 258   RCI = rci;
 259   MRI = &MF->getRegInfo();
 260   MBB = mbb;
 261   this->TrackUntiedDefs = TrackUntiedDefs;
 262   this->TrackLaneMasks = TrackLaneMasks;
 263
 264   if (RequireIntervals) {
 265     assert(lis && "IntervalPressure requires LiveIntervals");
 266     LIS = lis;
 267   }
 268
 269   CurrPos = pos;
 270   CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
 271
 272   P.MaxSetPressure = CurrSetPressure;
 273
 274   LiveRegs.init(*MRI);
 275   if (TrackUntiedDefs)
 276     UntiedDefs.setUniverse(MRI->getNumVirtRegs());
 277 }
 278
 279 /// Does this pressure result have a valid top position and live ins.
 280 bool RegPressureTracker::isTopClosed() const {
 281   if (RequireIntervals)
 282     return static_cast<IntervalPressure&>(P).TopIdx.isValid();
 283   return (static_cast<RegionPressure&>(P).TopPos ==
 284           MachineBasicBlock::const_iterator());
 285 }
 286
 287 /// Does this pressure result have a valid bottom position and live outs.
 288 bool RegPressureTracker::isBottomClosed() const {
 289   if (RequireIntervals)
 290     return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
 291   return (static_cast<RegionPressure&>(P).BottomPos ==
 292           MachineBasicBlock::const_iterator());
 293 }
 294
 295 SlotIndex RegPressureTracker::getCurrSlot() const {
 296   MachineBasicBlock::const_iterator IdxPos =
 297     skipDebugInstructionsForward(CurrPos, MBB->end());
 298   if (IdxPos == MBB->end())
 299     return LIS->getMBBEndIdx(MBB);
 300   return LIS->getInstructionIndex(*IdxPos).getRegSlot();
 301 }
 302
 303 /// Set the boundary for the top of the region and summarize live ins.
 304 void RegPressureTracker::closeTop() {
 305   if (RequireIntervals)
 306     static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
 307   else
 308     static_cast<RegionPressure&>(P).TopPos = CurrPos;
 309
 310   assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
 311   P.LiveInRegs.reserve(LiveRegs.size());
 312   LiveRegs.appendTo(P.LiveInRegs);
 313 }
 314
 315 /// Set the boundary for the bottom of the region and summarize live outs.
 316 void RegPressureTracker::closeBottom() {
 317   if (RequireIntervals)
 318     static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
 319   else
 320     static_cast<RegionPressure&>(P).BottomPos = CurrPos;
 321
 322   assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
 323   P.LiveOutRegs.reserve(LiveRegs.size());
 324   LiveRegs.appendTo(P.LiveOutRegs);
 325 }
 326
 327 /// Finalize the region boundaries and record live ins and live outs.
 328 void RegPressureTracker::closeRegion() {
 329   if (!isTopClosed() && !isBottomClosed()) {
 330     assert(LiveRegs.size() == 0 && "no region boundary");
 331     return;
 332   }
 333   if (!isBottomClosed())
 334     closeBottom();
 335   else if (!isTopClosed())
 336     closeTop();
 337   // If both top and bottom are closed, do nothing.
 338 }
 339
 340 /// The register tracker is unaware of global liveness so ignores normal
 341 /// live-thru ranges. However, two-address or coalesced chains can also lead
 342 /// to live ranges with no holes. Count these to inform heuristics that we
 343 /// can never drop below this pressure.
 344 void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
 345   LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
 346   assert(isBottomClosed() && "need bottom-up tracking to intialize.");
 347   for (const RegisterMaskPair &Pair : P.LiveOutRegs) {
 348     unsigned RegUnit = Pair.RegUnit;
 349     if (TargetRegisterInfo::isVirtualRegister(RegUnit)
 350         && !RPTracker.hasUntiedDef(RegUnit))
 351       increaseSetPressure(LiveThruPressure, *MRI, RegUnit,
 352                           LaneBitmask::getNone(), Pair.LaneMask);
 353   }
 354 }
 355
 356 static LaneBitmask getRegLanes(ArrayRef<RegisterMaskPair> RegUnits,
 357                                unsigned RegUnit) {
 358   auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
 359     return Other.RegUnit == RegUnit;
 360   });
 361   if (I == RegUnits.end())
 362     return LaneBitmask::getNone();
 363   return I->LaneMask;
 364 }
 365
 366 static void addRegLanes(SmallVectorImpl<RegisterMaskPair> &RegUnits,
 367                         RegisterMaskPair Pair) {
 368   unsigned RegUnit = Pair.RegUnit;
 369   assert(Pair.LaneMask.any());
 370   auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
 371     return Other.RegUnit == RegUnit;
 372   });
 373   if (I == RegUnits.end()) {
 374     RegUnits.push_back(Pair);
 375   } else {
 376     I->LaneMask |= Pair.LaneMask;
 377   }
 378 }
 379
 380 static void setRegZero(SmallVectorImpl<RegisterMaskPair> &RegUnits,
 381                        unsigned RegUnit) {
 382   auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
 383     return Other.RegUnit == RegUnit;
 384   });
 385   if (I == RegUnits.end()) {
 386     RegUnits.push_back(RegisterMaskPair(RegUnit, LaneBitmask::getNone()));
 387   } else {
 388     I->LaneMask = LaneBitmask::getNone();
 389   }
 390 }
 391
 392 static void removeRegLanes(SmallVectorImpl<RegisterMaskPair> &RegUnits,
 393                            RegisterMaskPair Pair) {
 394   unsigned RegUnit = Pair.RegUnit;
 395   assert(Pair.LaneMask.any());
 396   auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
 397     return Other.RegUnit == RegUnit;
 398   });
 399   if (I != RegUnits.end()) {
 400     I->LaneMask &= ~Pair.LaneMask;
 401     if (I->LaneMask.none())
 402       RegUnits.erase(I);
 403   }
 404 }
 405
 406 static LaneBitmask getLanesWithProperty(const LiveIntervals &LIS,
 407     const MachineRegisterInfo &MRI, bool TrackLaneMasks, unsigned RegUnit,
 408     SlotIndex Pos, LaneBitmask SafeDefault,
 409     bool(*Property)(const LiveRange &LR, SlotIndex Pos)) {
 410   if (TargetRegisterInfo::isVirtualRegister(RegUnit)) {
 411     const LiveInterval &LI = LIS.getInterval(RegUnit);
 412     LaneBitmask Result;
 413     if (TrackLaneMasks && LI.hasSubRanges()) {
 414         for (const LiveInterval::SubRange &SR : LI.subranges()) {
 415           if (Property(SR, Pos))
 416             Result |= SR.LaneMask;
 417         }
 418     } else if (Property(LI, Pos)) {
 419       Result = TrackLaneMasks ? MRI.getMaxLaneMaskForVReg(RegUnit)
 420                               : LaneBitmask::getAll();
 421     }
 422
 423     return Result;
 424   } else {
 425     const LiveRange *LR = LIS.getCachedRegUnit(RegUnit);
 426     // Be prepared for missing liveranges: We usually do not compute liveranges
 427     // for physical registers on targets with many registers (GPUs).
 428     if (LR == nullptr)
 429       return SafeDefault;
 430     return Property(*LR, Pos) ? LaneBitmask::getAll() : LaneBitmask::getNone();
 431   }
 432 }
 433
 434 static LaneBitmask getLiveLanesAt(const LiveIntervals &LIS,
 435                                   const MachineRegisterInfo &MRI,
 436                                   bool TrackLaneMasks, unsigned RegUnit,
 437                                   SlotIndex Pos) {
 438   return getLanesWithProperty(LIS, MRI, TrackLaneMasks, RegUnit, Pos,
 439                               LaneBitmask::getAll(),
 440                               [](const LiveRange &LR, SlotIndex Pos) {
 441                                 return LR.liveAt(Pos);
 442                               });
 443 }
 444
 445
 446 namespace {
 447
 448 /// Collect this instruction's unique uses and defs into SmallVectors for
 449 /// processing defs and uses in order.
 450 ///
 451 /// FIXME: always ignore tied opers
 452 class RegisterOperandsCollector {
 453   friend class llvm::RegisterOperands;
 454
 455   RegisterOperands &RegOpers;
 456   const TargetRegisterInfo &TRI;
 457   const MachineRegisterInfo &MRI;
 458   bool IgnoreDead;
 459
 460   RegisterOperandsCollector(RegisterOperands &RegOpers,
 461                             const TargetRegisterInfo &TRI,
 462                             const MachineRegisterInfo &MRI, bool IgnoreDead)
 463     : RegOpers(RegOpers), TRI(TRI), MRI(MRI), IgnoreDead(IgnoreDead) {}
 464
 465   void collectInstr(const MachineInstr &MI) const {
 466     for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
 467       collectOperand(*OperI);
 468
 469     // Remove redundant physreg dead defs.
 470     for (const RegisterMaskPair &P : RegOpers.Defs)
 471       removeRegLanes(RegOpers.DeadDefs, P);
 472   }
 473
 474   void collectInstrLanes(const MachineInstr &MI) const {
 475     for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
 476       collectOperandLanes(*OperI);
 477
 478     // Remove redundant physreg dead defs.
 479     for (const RegisterMaskPair &P : RegOpers.Defs)
 480       removeRegLanes(RegOpers.DeadDefs, P);
 481   }
 482
 483   /// Push this operand's register onto the correct vectors.
 484   void collectOperand(const MachineOperand &MO) const {
 485     if (!MO.isReg() || !MO.getReg())
 486       return;
 487     unsigned Reg = MO.getReg();
 488     if (MO.isUse()) {
 489       if (!MO.isUndef() && !MO.isInternalRead())
 490         pushReg(Reg, RegOpers.Uses);
 491     } else {
 492       assert(MO.isDef());
 493       // Subregister definitions may imply a register read.
 494       if (MO.readsReg())
 495         pushReg(Reg, RegOpers.Uses);
 496
 497       if (MO.isDead()) {
 498         if (!IgnoreDead)
 499           pushReg(Reg, RegOpers.DeadDefs);
 500       } else
 501         pushReg(Reg, RegOpers.Defs);
 502     }
 503   }
 504
 505   void pushReg(unsigned Reg,
 506                SmallVectorImpl<RegisterMaskPair> &RegUnits) const {
 507     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 508       addRegLanes(RegUnits, RegisterMaskPair(Reg, LaneBitmask::getAll()));
 509     } else if (MRI.isAllocatable(Reg)) {
 510       for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
 511         addRegLanes(RegUnits, RegisterMaskPair(*Units, LaneBitmask::getAll()));
 512     }
 513   }
 514
 515   void collectOperandLanes(const MachineOperand &MO) const {
 516     if (!MO.isReg() || !MO.getReg())
 517       return;
 518     unsigned Reg = MO.getReg();
 519     unsigned SubRegIdx = MO.getSubReg();
 520     if (MO.isUse()) {
 521       if (!MO.isUndef() && !MO.isInternalRead())
 522         pushRegLanes(Reg, SubRegIdx, RegOpers.Uses);
 523     } else {
 524       assert(MO.isDef());
 525       // Treat read-undef subreg defs as definitions of the whole register.
 526       if (MO.isUndef())
 527         SubRegIdx = 0;
 528
 529       if (MO.isDead()) {
 530         if (!IgnoreDead)
 531           pushRegLanes(Reg, SubRegIdx, RegOpers.DeadDefs);
 532       } else
 533         pushRegLanes(Reg, SubRegIdx, RegOpers.Defs);
 534     }
 535   }
 536
 537   void pushRegLanes(unsigned Reg, unsigned SubRegIdx,
 538                     SmallVectorImpl<RegisterMaskPair> &RegUnits) const {
 539     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 540       LaneBitmask LaneMask = SubRegIdx != 0
 541                              ? TRI.getSubRegIndexLaneMask(SubRegIdx)
 542                              : MRI.getMaxLaneMaskForVReg(Reg);
 543       addRegLanes(RegUnits, RegisterMaskPair(Reg, LaneMask));
 544     } else if (MRI.isAllocatable(Reg)) {
 545       for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
 546         addRegLanes(RegUnits, RegisterMaskPair(*Units, LaneBitmask::getAll()));
 547     }
 548   }
 549 };
 550
 551 } // end anonymous namespace
 552
 553 void RegisterOperands::collect(const MachineInstr &MI,
 554                                const TargetRegisterInfo &TRI,
 555                                const MachineRegisterInfo &MRI,
 556                                bool TrackLaneMasks, bool IgnoreDead) {
 557   RegisterOperandsCollector Collector(*this, TRI, MRI, IgnoreDead);
 558   if (TrackLaneMasks)
 559     Collector.collectInstrLanes(MI);
 560   else
 561     Collector.collectInstr(MI);
 562 }
 563
 564 void RegisterOperands::detectDeadDefs(const MachineInstr &MI,
 565                                       const LiveIntervals &LIS) {
 566   SlotIndex SlotIdx = LIS.getInstructionIndex(MI);
 567   for (auto RI = Defs.begin(); RI != Defs.end(); /*empty*/) {
 568     unsigned Reg = RI->RegUnit;
 569     const LiveRange *LR = getLiveRange(LIS, Reg);
 570     if (LR != nullptr) {
 571       LiveQueryResult LRQ = LR->Query(SlotIdx);
 572       if (LRQ.isDeadDef()) {
 573         // LiveIntervals knows this is a dead even though it's MachineOperand is
 574         // not flagged as such.
 575         DeadDefs.push_back(*RI);
 576         RI = Defs.erase(RI);
 577         continue;
 578       }
 579     }
 580     ++RI;
 581   }
 582 }
 583
 584 void RegisterOperands::adjustLaneLiveness(const LiveIntervals &LIS,
 585                                           const MachineRegisterInfo &MRI,
 586                                           SlotIndex Pos,
 587                                           MachineInstr *AddFlagsMI) {
 588   for (auto I = Defs.begin(); I != Defs.end(); ) {
 589     LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, true, I->RegUnit,
 590                                            Pos.getDeadSlot());
 591     // If the def is all that is live after the instruction, then in case
 592     // of a subregister def we need a read-undef flag.
 593     unsigned RegUnit = I->RegUnit;
 594     if (TargetRegisterInfo::isVirtualRegister(RegUnit) &&
 595         AddFlagsMI != nullptr && (LiveAfter & ~I->LaneMask).none())
 596       AddFlagsMI->setRegisterDefReadUndef(RegUnit);
 597
 598     LaneBitmask ActualDef = I->LaneMask & LiveAfter;
 599     if (ActualDef.none()) {
 600       I = Defs.erase(I);
 601     } else {
 602       I->LaneMask = ActualDef;
 603       ++I;
 604     }
 605   }
 606   for (auto I = Uses.begin(); I != Uses.end(); ) {
 607     LaneBitmask LiveBefore = getLiveLanesAt(LIS, MRI, true, I->RegUnit,
 608                                             Pos.getBaseIndex());
 609     LaneBitmask LaneMask = I->LaneMask & LiveBefore;
 610     if (LaneMask.none()) {
 611       I = Uses.erase(I);
 612     } else {
 613       I->LaneMask = LaneMask;
 614       ++I;
 615     }
 616   }
 617   if (AddFlagsMI != nullptr) {
 618     for (const RegisterMaskPair &P : DeadDefs) {
 619       unsigned RegUnit = P.RegUnit;
 620       if (!TargetRegisterInfo::isVirtualRegister(RegUnit))
 621         continue;
 622       LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, true, RegUnit,
 623                                              Pos.getDeadSlot());
 624       if (LiveAfter.none())
 625         AddFlagsMI->setRegisterDefReadUndef(RegUnit);
 626     }
 627   }
 628 }
 629
 630 /// Initialize an array of N PressureDiffs.
 631 void PressureDiffs::init(unsigned N) {
 632   Size = N;
 633   if (N <= Max) {
 634     memset(PDiffArray, 0, N * sizeof(PressureDiff));
 635     return;
 636   }
 637   Max = Size;
 638   free(PDiffArray);
 639   PDiffArray = static_cast<PressureDiff*>(safe_calloc(N, sizeof(PressureDiff)));
 640 }
 641
 642 void PressureDiffs::addInstruction(unsigned Idx,
 643                                    const RegisterOperands &RegOpers,
 644                                    const MachineRegisterInfo &MRI) {
 645   PressureDiff &PDiff = (*this)[Idx];
 646   assert(!PDiff.begin()->isValid() && "stale PDiff");
 647   for (const RegisterMaskPair &P : RegOpers.Defs)
 648     PDiff.addPressureChange(P.RegUnit, true, &MRI);
 649
 650   for (const RegisterMaskPair &P : RegOpers.Uses)
 651     PDiff.addPressureChange(P.RegUnit, false, &MRI);
 652 }
 653
 654 /// Add a change in pressure to the pressure diff of a given instruction.
 655 void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec,
 656                                      const MachineRegisterInfo *MRI) {
 657   PSetIterator PSetI = MRI->getPressureSets(RegUnit);
 658   int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight();
 659   for (; PSetI.isValid(); ++PSetI) {
 660     // Find an existing entry in the pressure diff for this PSet.
 661     PressureDiff::iterator I = nonconst_begin(), E = nonconst_end();
 662     for (; I != E && I->isValid(); ++I) {
 663       if (I->getPSet() >= *PSetI)
 664         break;
 665     }
 666     // If all pressure sets are more constrained, skip the remaining PSets.
 667     if (I == E)
 668       break;
 669     // Insert this PressureChange.
 670     if (!I->isValid() || I->getPSet() != *PSetI) {
 671       PressureChange PTmp = PressureChange(*PSetI);
 672       for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J)
 673         std::swap(*J, PTmp);
 674     }
 675     // Update the units for this pressure set.
 676     unsigned NewUnitInc = I->getUnitInc() + Weight;
 677     if (NewUnitInc != 0) {
 678       I->setUnitInc(NewUnitInc);
 679     } else {
 680       // Remove entry
 681       PressureDiff::iterator J;
 682       for (J = std::next(I); J != E && J->isValid(); ++J, ++I)
 683         *I = *J;
 684       *I = PressureChange();
 685     }
 686   }
 687 }
 688
 689 /// Force liveness of registers.
 690 void RegPressureTracker::addLiveRegs(ArrayRef<RegisterMaskPair> Regs) {
 691   for (const RegisterMaskPair &P : Regs) {
 692     LaneBitmask PrevMask = LiveRegs.insert(P);
 693     LaneBitmask NewMask = PrevMask | P.LaneMask;
 694     increaseRegPressure(P.RegUnit, PrevMask, NewMask);
 695   }
 696 }
 697
 698 void RegPressureTracker::discoverLiveInOrOut(RegisterMaskPair Pair,
 699     SmallVectorImpl<RegisterMaskPair> &LiveInOrOut) {
 700   assert(Pair.LaneMask.any());
 701
 702   unsigned RegUnit = Pair.RegUnit;
 703   auto I = llvm::find_if(LiveInOrOut, [RegUnit](const RegisterMaskPair &Other) {
 704     return Other.RegUnit == RegUnit;
 705   });
 706   LaneBitmask PrevMask;
 707   LaneBitmask NewMask;
 708   if (I == LiveInOrOut.end()) {
 709     PrevMask = LaneBitmask::getNone();
 710     NewMask = Pair.LaneMask;
 711     LiveInOrOut.push_back(Pair);
 712   } else {
 713     PrevMask = I->LaneMask;
 714     NewMask = PrevMask | Pair.LaneMask;
 715     I->LaneMask = NewMask;
 716   }
 717   increaseSetPressure(P.MaxSetPressure, *MRI, RegUnit, PrevMask, NewMask);
 718 }
 719
 720 void RegPressureTracker::discoverLiveIn(RegisterMaskPair Pair) {
 721   discoverLiveInOrOut(Pair, P.LiveInRegs);
 722 }
 723
 724 void RegPressureTracker::discoverLiveOut(RegisterMaskPair Pair) {
 725   discoverLiveInOrOut(Pair, P.LiveOutRegs);
 726 }
 727
 728 void RegPressureTracker::bumpDeadDefs(ArrayRef<RegisterMaskPair> DeadDefs) {
 729   for (const RegisterMaskPair &P : DeadDefs) {
 730     unsigned Reg = P.RegUnit;
 731     LaneBitmask LiveMask = LiveRegs.contains(Reg);
 732     LaneBitmask BumpedMask = LiveMask | P.LaneMask;
 733     increaseRegPressure(Reg, LiveMask, BumpedMask);
 734   }
 735   for (const RegisterMaskPair &P : DeadDefs) {
 736     unsigned Reg = P.RegUnit;
 737     LaneBitmask LiveMask = LiveRegs.contains(Reg);
 738     LaneBitmask BumpedMask = LiveMask | P.LaneMask;
 739     decreaseRegPressure(Reg, BumpedMask, LiveMask);
 740   }
 741 }
 742
 743 /// Recede across the previous instruction. If LiveUses is provided, record any
 744 /// RegUnits that are made live by the current instruction's uses. This includes
 745 /// registers that are both defined and used by the instruction.  If a pressure
 746 /// difference pointer is provided record the changes is pressure caused by this
 747 /// instruction independent of liveness.
 748 void RegPressureTracker::recede(const RegisterOperands &RegOpers,
 749                                 SmallVectorImpl<RegisterMaskPair> *LiveUses) {
 750   assert(!CurrPos->isDebugInstr());
 751
 752   // Boost pressure for all dead defs together.
 753   bumpDeadDefs(RegOpers.DeadDefs);
 754
 755   // Kill liveness at live defs.
 756   // TODO: consider earlyclobbers?
 757   for (const RegisterMaskPair &Def : RegOpers.Defs) {
 758     unsigned Reg = Def.RegUnit;
 759
 760     LaneBitmask PreviousMask = LiveRegs.erase(Def);
 761     LaneBitmask NewMask = PreviousMask & ~Def.LaneMask;
 762
 763     LaneBitmask LiveOut = Def.LaneMask & ~PreviousMask;
 764     if (LiveOut.any()) {
 765       discoverLiveOut(RegisterMaskPair(Reg, LiveOut));
 766       // Retroactively model effects on pressure of the live out lanes.
 767       increaseSetPressure(CurrSetPressure, *MRI, Reg, LaneBitmask::getNone(),
 768                           LiveOut);
 769       PreviousMask = LiveOut;
 770     }
 771
 772     if (NewMask.none()) {
 773       // Add a 0 entry to LiveUses as a marker that the complete vreg has become
 774       // dead.
 775       if (TrackLaneMasks && LiveUses != nullptr)
 776         setRegZero(*LiveUses, Reg);
 777     }
 778
 779     decreaseRegPressure(Reg, PreviousMask, NewMask);
 780   }
 781
 782   SlotIndex SlotIdx;
 783   if (RequireIntervals)
 784     SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
 785
 786   // Generate liveness for uses.
 787   for (const RegisterMaskPair &Use : RegOpers.Uses) {
 788     unsigned Reg = Use.RegUnit;
 789     assert(Use.LaneMask.any());
 790     LaneBitmask PreviousMask = LiveRegs.insert(Use);
 791     LaneBitmask NewMask = PreviousMask | Use.LaneMask;
 792     if (NewMask == PreviousMask)
 793       continue;
 794
 795     // Did the register just become live?
 796     if (PreviousMask.none()) {
 797       if (LiveUses != nullptr) {
 798         if (!TrackLaneMasks) {
 799           addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
 800         } else {
 801           auto I =
 802               llvm::find_if(*LiveUses, [Reg](const RegisterMaskPair Other) {
 803                 return Other.RegUnit == Reg;
 804               });
 805           bool IsRedef = I != LiveUses->end();
 806           if (IsRedef) {
 807             // ignore re-defs here...
 808             assert(I->LaneMask.none());
 809             removeRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
 810           } else {
 811             addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
 812           }
 813         }
 814       }
 815
 816       // Discover live outs if this may be the first occurance of this register.
 817       if (RequireIntervals) {
 818         LaneBitmask LiveOut = getLiveThroughAt(Reg, SlotIdx);
 819         if (LiveOut.any())
 820           discoverLiveOut(RegisterMaskPair(Reg, LiveOut));
 821       }
 822     }
 823
 824     increaseRegPressure(Reg, PreviousMask, NewMask);
 825   }
 826   if (TrackUntiedDefs) {
 827     for (const RegisterMaskPair &Def : RegOpers.Defs) {
 828       unsigned RegUnit = Def.RegUnit;
 829       if (TargetRegisterInfo::isVirtualRegister(RegUnit) &&
 830           (LiveRegs.contains(RegUnit) & Def.LaneMask).none())
 831         UntiedDefs.insert(RegUnit);
 832     }
 833   }
 834 }
 835
 836 void RegPressureTracker::recedeSkipDebugValues() {
 837   assert(CurrPos != MBB->begin());
 838   if (!isBottomClosed())
 839     closeBottom();
 840
 841   // Open the top of the region using block iterators.
 842   if (!RequireIntervals && isTopClosed())
 843     static_cast<RegionPressure&>(P).openTop(CurrPos);
 844
 845   // Find the previous instruction.
 846   CurrPos = skipDebugInstructionsBackward(std::prev(CurrPos), MBB->begin());
 847
 848   SlotIndex SlotIdx;
 849   if (RequireIntervals)
 850     SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
 851
 852   // Open the top of the region using slot indexes.
 853   if (RequireIntervals && isTopClosed())
 854     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
 855 }
 856
 857 void RegPressureTracker::recede(SmallVectorImpl<RegisterMaskPair> *LiveUses) {
 858   recedeSkipDebugValues();
 859
 860   const MachineInstr &MI = *CurrPos;
 861   RegisterOperands RegOpers;
 862   RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
 863   if (TrackLaneMasks) {
 864     SlotIndex SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
 865     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
 866   } else if (RequireIntervals) {
 867     RegOpers.detectDeadDefs(MI, *LIS);
 868   }
 869
 870   recede(RegOpers, LiveUses);
 871 }
 872
 873 /// Advance across the current instruction.
 874 void RegPressureTracker::advance(const RegisterOperands &RegOpers) {
 875   assert(!TrackUntiedDefs && "unsupported mode");
 876   assert(CurrPos != MBB->end());
 877   if (!isTopClosed())
 878     closeTop();
 879
 880   SlotIndex SlotIdx;
 881   if (RequireIntervals)
 882     SlotIdx = getCurrSlot();
 883
 884   // Open the bottom of the region using slot indexes.
 885   if (isBottomClosed()) {
 886     if (RequireIntervals)
 887       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
 888     else
 889       static_cast<RegionPressure&>(P).openBottom(CurrPos);
 890   }
 891
 892   for (const RegisterMaskPair &Use : RegOpers.Uses) {
 893     unsigned Reg = Use.RegUnit;
 894     LaneBitmask LiveMask = LiveRegs.contains(Reg);
 895     LaneBitmask LiveIn = Use.LaneMask & ~LiveMask;
 896     if (LiveIn.any()) {
 897       discoverLiveIn(RegisterMaskPair(Reg, LiveIn));
 898       increaseRegPressure(Reg, LiveMask, LiveMask | LiveIn);
 899       LiveRegs.insert(RegisterMaskPair(Reg, LiveIn));
 900     }
 901     // Kill liveness at last uses.
 902     if (RequireIntervals) {
 903       LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
 904       if (LastUseMask.any()) {
 905         LiveRegs.erase(RegisterMaskPair(Reg, LastUseMask));
 906         decreaseRegPressure(Reg, LiveMask, LiveMask & ~LastUseMask);
 907       }
 908     }
 909   }
 910
 911   // Generate liveness for defs.
 912   for (const RegisterMaskPair &Def : RegOpers.Defs) {
 913     LaneBitmask PreviousMask = LiveRegs.insert(Def);
 914     LaneBitmask NewMask = PreviousMask | Def.LaneMask;
 915     increaseRegPressure(Def.RegUnit, PreviousMask, NewMask);
 916   }
 917
 918   // Boost pressure for all dead defs together.
 919   bumpDeadDefs(RegOpers.DeadDefs);
 920
 921   // Find the next instruction.
 922   CurrPos = skipDebugInstructionsForward(std::next(CurrPos), MBB->end());
 923 }
 924
 925 void RegPressureTracker::advance() {
 926   const MachineInstr &MI = *CurrPos;
 927   RegisterOperands RegOpers;
 928   RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
 929   if (TrackLaneMasks) {
 930     SlotIndex SlotIdx = getCurrSlot();
 931     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
 932   }
 933   advance(RegOpers);
 934 }
 935
 936 /// Find the max change in excess pressure across all sets.
 937 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
 938                                        ArrayRef<unsigned> NewPressureVec,
 939                                        RegPressureDelta &Delta,
 940                                        const RegisterClassInfo *RCI,
 941                                        ArrayRef<unsigned> LiveThruPressureVec) {
 942   Delta.Excess = PressureChange();
 943   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 944     unsigned POld = OldPressureVec[i];
 945     unsigned PNew = NewPressureVec[i];
 946     int PDiff = (int)PNew - (int)POld;
 947     if (!PDiff) // No change in this set in the common case.
 948       continue;
 949     // Only consider change beyond the limit.
 950     unsigned Limit = RCI->getRegPressureSetLimit(i);
 951     if (!LiveThruPressureVec.empty())
 952       Limit += LiveThruPressureVec[i];
 953
 954     if (Limit > POld) {
 955       if (Limit > PNew)
 956         PDiff = 0;            // Under the limit
 957       else
 958         PDiff = PNew - Limit; // Just exceeded limit.
 959     } else if (Limit > PNew)
 960       PDiff = Limit - POld;   // Just obeyed limit.
 961
 962     if (PDiff) {
 963       Delta.Excess = PressureChange(i);
 964       Delta.Excess.setUnitInc(PDiff);
 965       break;
 966     }
 967   }
 968 }
 969
 970 /// Find the max change in max pressure that either surpasses a critical PSet
 971 /// limit or exceeds the current MaxPressureLimit.
 972 ///
 973 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
 974 /// silly. It's done now to demonstrate the concept but will go away with a
 975 /// RegPressureTracker API change to work with pressure differences.
 976 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
 977                                     ArrayRef<unsigned> NewMaxPressureVec,
 978                                     ArrayRef<PressureChange> CriticalPSets,
 979                                     ArrayRef<unsigned> MaxPressureLimit,
 980                                     RegPressureDelta &Delta) {
 981   Delta.CriticalMax = PressureChange();
 982   Delta.CurrentMax = PressureChange();
 983
 984   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 985   for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
 986     unsigned POld = OldMaxPressureVec[i];
 987     unsigned PNew = NewMaxPressureVec[i];
 988     if (PNew == POld) // No change in this set in the common case.
 989       continue;
 990
 991     if (!Delta.CriticalMax.isValid()) {
 992       while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
 993         ++CritIdx;
 994
 995       if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
 996         int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
 997         if (PDiff > 0) {
 998           Delta.CriticalMax = PressureChange(i);
 999           Delta.CriticalMax.setUnitInc(PDiff);
1000         }
1001       }
1002     }
1003     // Find the first increase above MaxPressureLimit.
1004     // (Ignores negative MDiff).
1005     if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
1006       Delta.CurrentMax = PressureChange(i);
1007       Delta.CurrentMax.setUnitInc(PNew - POld);
1008       if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
1009         break;
1010     }
1011   }
1012 }
1013
1014 /// Record the upward impact of a single instruction on current register
1015 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1016 /// not discover live in/outs.
1017 ///
1018 /// This is intended for speculative queries. It leaves pressure inconsistent
1019 /// with the current position, so must be restored by the caller.
1020 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
1021   assert(!MI->isDebugInstr() && "Expect a nondebug instruction.");
1022
1023   SlotIndex SlotIdx;
1024   if (RequireIntervals)
1025     SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1026
1027   // Account for register pressure similar to RegPressureTracker::recede().
1028   RegisterOperands RegOpers;
1029   RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, /*IgnoreDead=*/true);
1030   assert(RegOpers.DeadDefs.size() == 0);
1031   if (TrackLaneMasks)
1032     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1033   else if (RequireIntervals)
1034     RegOpers.detectDeadDefs(*MI, *LIS);
1035
1036   // Boost max pressure for all dead defs together.
1037   // Since CurrSetPressure and MaxSetPressure
1038   bumpDeadDefs(RegOpers.DeadDefs);
1039
1040   // Kill liveness at live defs.
1041   for (const RegisterMaskPair &P : RegOpers.Defs) {
1042     unsigned Reg = P.RegUnit;
1043     LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1044     LaneBitmask UseLanes = getRegLanes(RegOpers.Uses, Reg);
1045     LaneBitmask DefLanes = P.LaneMask;
1046     LaneBitmask LiveAfter = (LiveLanes & ~DefLanes) | UseLanes;
1047     decreaseRegPressure(Reg, LiveLanes, LiveAfter);
1048   }
1049   // Generate liveness for uses.
1050   for (const RegisterMaskPair &P : RegOpers.Uses) {
1051     unsigned Reg = P.RegUnit;
1052     LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1053     LaneBitmask LiveAfter = LiveLanes | P.LaneMask;
1054     increaseRegPressure(Reg, LiveLanes, LiveAfter);
1055   }
1056 }
1057
1058 /// Consider the pressure increase caused by traversing this instruction
1059 /// bottom-up. Find the pressure set with the most change beyond its pressure
1060 /// limit based on the tracker's current pressure, and return the change in
1061 /// number of register units of that pressure set introduced by this
1062 /// instruction.
1063 ///
1064 /// This assumes that the current LiveOut set is sufficient.
1065 ///
1066 /// This is expensive for an on-the-fly query because it calls
1067 /// bumpUpwardPressure to recompute the pressure sets based on current
1068 /// liveness. This mainly exists to verify correctness, e.g. with
1069 /// -verify-misched. getUpwardPressureDelta is the fast version of this query
1070 /// that uses the per-SUnit cache of the PressureDiff.
1071 void RegPressureTracker::
1072 getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
1073                           RegPressureDelta &Delta,
1074                           ArrayRef<PressureChange> CriticalPSets,
1075                           ArrayRef<unsigned> MaxPressureLimit) {
1076   // Snapshot Pressure.
1077   // FIXME: The snapshot heap space should persist. But I'm planning to
1078   // summarize the pressure effect so we don't need to snapshot at all.
1079   std::vector<unsigned> SavedPressure = CurrSetPressure;
1080   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1081
1082   bumpUpwardPressure(MI);
1083
1084   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1085                              LiveThruPressure);
1086   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1087                           MaxPressureLimit, Delta);
1088   assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1089          Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1090
1091   // Restore the tracker's state.
1092   P.MaxSetPressure.swap(SavedMaxPressure);
1093   CurrSetPressure.swap(SavedPressure);
1094
1095 #ifndef NDEBUG
1096   if (!PDiff)
1097     return;
1098
1099   // Check if the alternate algorithm yields the same result.
1100   RegPressureDelta Delta2;
1101   getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
1102   if (Delta != Delta2) {
1103     dbgs() << "PDiff: ";
1104     PDiff->dump(*TRI);
1105     dbgs() << "DELTA: " << *MI;
1106     if (Delta.Excess.isValid())
1107       dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
1108              << " " << Delta.Excess.getUnitInc() << "\n";
1109     if (Delta.CriticalMax.isValid())
1110       dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
1111              << " " << Delta.CriticalMax.getUnitInc() << "\n";
1112     if (Delta.CurrentMax.isValid())
1113       dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
1114              << " " << Delta.CurrentMax.getUnitInc() << "\n";
1115     if (Delta2.Excess.isValid())
1116       dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
1117              << " " << Delta2.Excess.getUnitInc() << "\n";
1118     if (Delta2.CriticalMax.isValid())
1119       dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
1120              << " " << Delta2.CriticalMax.getUnitInc() << "\n";
1121     if (Delta2.CurrentMax.isValid())
1122       dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
1123              << " " << Delta2.CurrentMax.getUnitInc() << "\n";
1124     llvm_unreachable("RegP Delta Mismatch");
1125   }
1126 #endif
1127 }
1128
1129 /// This is the fast version of querying register pressure that does not
1130 /// directly depend on current liveness.
1131 ///
1132 /// @param Delta captures information needed for heuristics.
1133 ///
1134 /// @param CriticalPSets Are the pressure sets that are known to exceed some
1135 /// limit within the region, not necessarily at the current position.
1136 ///
1137 /// @param MaxPressureLimit Is the max pressure within the region, not
1138 /// necessarily at the current position.
1139 void RegPressureTracker::
1140 getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
1141                        RegPressureDelta &Delta,
1142                        ArrayRef<PressureChange> CriticalPSets,
1143                        ArrayRef<unsigned> MaxPressureLimit) const {
1144   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1145   for (PressureDiff::const_iterator
1146          PDiffI = PDiff.begin(), PDiffE = PDiff.end();
1147        PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
1148
1149     unsigned PSetID = PDiffI->getPSet();
1150     unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
1151     if (!LiveThruPressure.empty())
1152       Limit += LiveThruPressure[PSetID];
1153
1154     unsigned POld = CurrSetPressure[PSetID];
1155     unsigned MOld = P.MaxSetPressure[PSetID];
1156     unsigned MNew = MOld;
1157     // Ignore DeadDefs here because they aren't captured by PressureChange.
1158     unsigned PNew = POld + PDiffI->getUnitInc();
1159     assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
1160            && "PSet overflow/underflow");
1161     if (PNew > MOld)
1162       MNew = PNew;
1163     // Check if current pressure has exceeded the limit.
1164     if (!Delta.Excess.isValid()) {
1165       unsigned ExcessInc = 0;
1166       if (PNew > Limit)
1167         ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
1168       else if (POld > Limit)
1169         ExcessInc = Limit - POld;
1170       if (ExcessInc) {
1171         Delta.Excess = PressureChange(PSetID);
1172         Delta.Excess.setUnitInc(ExcessInc);
1173       }
1174     }
1175     // Check if max pressure has exceeded a critical pressure set max.
1176     if (MNew == MOld)
1177       continue;
1178     if (!Delta.CriticalMax.isValid()) {
1179       while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
1180         ++CritIdx;
1181
1182       if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
1183         int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
1184         if (CritInc > 0 && CritInc <= std::numeric_limits<int16_t>::max()) {
1185           Delta.CriticalMax = PressureChange(PSetID);
1186           Delta.CriticalMax.setUnitInc(CritInc);
1187         }
1188       }
1189     }
1190     // Check if max pressure has exceeded the current max.
1191     if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
1192       Delta.CurrentMax = PressureChange(PSetID);
1193       Delta.CurrentMax.setUnitInc(MNew - MOld);
1194     }
1195   }
1196 }
1197
1198 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
1199 /// The query starts with a lane bitmask which gets lanes/bits removed for every
1200 /// use we find.
1201 static LaneBitmask findUseBetween(unsigned Reg, LaneBitmask LastUseMask,
1202                                   SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1203                                   const MachineRegisterInfo &MRI,
1204                                   const LiveIntervals *LIS) {
1205   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
1206   for (const MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1207     if (MO.isUndef())
1208       continue;
1209     const MachineInstr *MI = MO.getParent();
1210     SlotIndex InstSlot = LIS->getInstructionIndex(*MI).getRegSlot();
1211     if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) {
1212       unsigned SubRegIdx = MO.getSubReg();
1213       LaneBitmask UseMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
1214       LastUseMask &= ~UseMask;
1215       if (LastUseMask.none())
1216         return LaneBitmask::getNone();
1217     }
1218   }
1219   return LastUseMask;
1220 }
1221
1222 LaneBitmask RegPressureTracker::getLiveLanesAt(unsigned RegUnit,
1223                                                SlotIndex Pos) const {
1224   assert(RequireIntervals);
1225   return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1226                               LaneBitmask::getAll(),
1227       [](const LiveRange &LR, SlotIndex Pos) {
1228         return LR.liveAt(Pos);
1229       });
1230 }
1231
1232 LaneBitmask RegPressureTracker::getLastUsedLanes(unsigned RegUnit,
1233                                                  SlotIndex Pos) const {
1234   assert(RequireIntervals);
1235   return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit,
1236                               Pos.getBaseIndex(), LaneBitmask::getNone(),
1237       [](const LiveRange &LR, SlotIndex Pos) {
1238         const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1239         return S != nullptr && S->end == Pos.getRegSlot();
1240       });
1241 }
1242
1243 LaneBitmask RegPressureTracker::getLiveThroughAt(unsigned RegUnit,
1244                                                  SlotIndex Pos) const {
1245   assert(RequireIntervals);
1246   return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1247                               LaneBitmask::getNone(),
1248       [](const LiveRange &LR, SlotIndex Pos) {
1249         const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1250         return S != nullptr && S->start < Pos.getRegSlot(true) &&
1251                S->end != Pos.getDeadSlot();
1252       });
1253 }
1254
1255 /// Record the downward impact of a single instruction on current register
1256 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1257 /// not discover live in/outs.
1258 ///
1259 /// This is intended for speculative queries. It leaves pressure inconsistent
1260 /// with the current position, so must be restored by the caller.
1261 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
1262   assert(!MI->isDebugInstr() && "Expect a nondebug instruction.");
1263
1264   SlotIndex SlotIdx;
1265   if (RequireIntervals)
1266     SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1267
1268   // Account for register pressure similar to RegPressureTracker::recede().
1269   RegisterOperands RegOpers;
1270   RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, false);
1271   if (TrackLaneMasks)
1272     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1273
1274   if (RequireIntervals) {
1275     for (const RegisterMaskPair &Use : RegOpers.Uses) {
1276       unsigned Reg = Use.RegUnit;
1277       LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
1278       if (LastUseMask.none())
1279         continue;
1280       // The LastUseMask is queried from the liveness information of instruction
1281       // which may be further down the schedule. Some lanes may actually not be
1282       // last uses for the current position.
1283       // FIXME: allow the caller to pass in the list of vreg uses that remain
1284       // to be bottom-scheduled to avoid searching uses at each query.
1285       SlotIndex CurrIdx = getCurrSlot();
1286       LastUseMask
1287         = findUseBetween(Reg, LastUseMask, CurrIdx, SlotIdx, *MRI, LIS);
1288       if (LastUseMask.none())
1289         continue;
1290
1291       LaneBitmask LiveMask = LiveRegs.contains(Reg);
1292       LaneBitmask NewMask = LiveMask & ~LastUseMask;
1293       decreaseRegPressure(Reg, LiveMask, NewMask);
1294     }
1295   }
1296
1297   // Generate liveness for defs.
1298   for (const RegisterMaskPair &Def : RegOpers.Defs) {
1299     unsigned Reg = Def.RegUnit;
1300     LaneBitmask LiveMask = LiveRegs.contains(Reg);
1301     LaneBitmask NewMask = LiveMask | Def.LaneMask;
1302     increaseRegPressure(Reg, LiveMask, NewMask);
1303   }
1304
1305   // Boost pressure for all dead defs together.
1306   bumpDeadDefs(RegOpers.DeadDefs);
1307 }
1308
1309 /// Consider the pressure increase caused by traversing this instruction
1310 /// top-down. Find the register class with the most change in its pressure limit
1311 /// based on the tracker's current pressure, and return the number of excess
1312 /// register units of that pressure set introduced by this instruction.
1313 ///
1314 /// This assumes that the current LiveIn set is sufficient.
1315 ///
1316 /// This is expensive for an on-the-fly query because it calls
1317 /// bumpDownwardPressure to recompute the pressure sets based on current
1318 /// liveness. We don't yet have a fast version of downward pressure tracking
1319 /// analogous to getUpwardPressureDelta.
1320 void RegPressureTracker::
1321 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
1322                             ArrayRef<PressureChange> CriticalPSets,
1323                             ArrayRef<unsigned> MaxPressureLimit) {
1324   // Snapshot Pressure.
1325   std::vector<unsigned> SavedPressure = CurrSetPressure;
1326   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1327
1328   bumpDownwardPressure(MI);
1329
1330   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1331                              LiveThruPressure);
1332   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1333                           MaxPressureLimit, Delta);
1334   assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1335          Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1336
1337   // Restore the tracker's state.
1338   P.MaxSetPressure.swap(SavedMaxPressure);
1339   CurrSetPressure.swap(SavedPressure);
1340 }
1341
1342 /// Get the pressure of each PSet after traversing this instruction bottom-up.
1343 void RegPressureTracker::
1344 getUpwardPressure(const MachineInstr *MI,
1345                   std::vector<unsigned> &PressureResult,
1346                   std::vector<unsigned> &MaxPressureResult) {
1347   // Snapshot pressure.
1348   PressureResult = CurrSetPressure;
1349   MaxPressureResult = P.MaxSetPressure;
1350
1351   bumpUpwardPressure(MI);
1352
1353   // Current pressure becomes the result. Restore current pressure.
1354   P.MaxSetPressure.swap(MaxPressureResult);
1355   CurrSetPressure.swap(PressureResult);
1356 }
1357
1358 /// Get the pressure of each PSet after traversing this instruction top-down.
1359 void RegPressureTracker::
1360 getDownwardPressure(const MachineInstr *MI,
1361                     std::vector<unsigned> &PressureResult,
1362                     std::vector<unsigned> &MaxPressureResult) {
1363   // Snapshot pressure.
1364   PressureResult = CurrSetPressure;
1365   MaxPressureResult = P.MaxSetPressure;
1366
1367   bumpDownwardPressure(MI);
1368
1369   // Current pressure becomes the result. Restore current pressure.
1370   P.MaxSetPressure.swap(MaxPressureResult);
1371   CurrSetPressure.swap(PressureResult);
1372 }