contrib/llvm-project/llvm/lib/CodeGen/RegisterPressure.cpp

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