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