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)
 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
 859   const MachineInstr &MI = *CurrPos;
 860   RegisterOperands RegOpers;
 861   RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
 862   if (TrackLaneMasks) {
 863     SlotIndex SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
 864     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
 865   } else if (RequireIntervals) {
 866     RegOpers.detectDeadDefs(MI, *LIS);
 867   }
 868
 869   recede(RegOpers, LiveUses);
 870 }
 871
 872 /// Advance across the current instruction.
 873 void RegPressureTracker::advance(const RegisterOperands &RegOpers) {
 874   assert(!TrackUntiedDefs && "unsupported mode");
 875   assert(CurrPos != MBB->end());
 876   if (!isTopClosed())
 877     closeTop();
 878
 879   SlotIndex SlotIdx;
 880   if (RequireIntervals)
 881     SlotIdx = getCurrSlot();
 882
 883   // Open the bottom of the region using slot indexes.
 884   if (isBottomClosed()) {
 885     if (RequireIntervals)
 886       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
 887     else
 888       static_cast<RegionPressure&>(P).openBottom(CurrPos);
 889   }
 890
 891   for (const RegisterMaskPair &Use : RegOpers.Uses) {
 892     unsigned Reg = Use.RegUnit;
 893     LaneBitmask LiveMask = LiveRegs.contains(Reg);
 894     LaneBitmask LiveIn = Use.LaneMask & ~LiveMask;
 895     if (LiveIn.any()) {
 896       discoverLiveIn(RegisterMaskPair(Reg, LiveIn));
 897       increaseRegPressure(Reg, LiveMask, LiveMask | LiveIn);
 898       LiveRegs.insert(RegisterMaskPair(Reg, LiveIn));
 899     }
 900     // Kill liveness at last uses.
 901     if (RequireIntervals) {
 902       LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
 903       if (LastUseMask.any()) {
 904         LiveRegs.erase(RegisterMaskPair(Reg, LastUseMask));
 905         decreaseRegPressure(Reg, LiveMask, LiveMask & ~LastUseMask);
 906       }
 907     }
 908   }
 909
 910   // Generate liveness for defs.
 911   for (const RegisterMaskPair &Def : RegOpers.Defs) {
 912     LaneBitmask PreviousMask = LiveRegs.insert(Def);
 913     LaneBitmask NewMask = PreviousMask | Def.LaneMask;
 914     increaseRegPressure(Def.RegUnit, PreviousMask, NewMask);
 915   }
 916
 917   // Boost pressure for all dead defs together.
 918   bumpDeadDefs(RegOpers.DeadDefs);
 919
 920   // Find the next instruction.
 921   CurrPos = skipDebugInstructionsForward(std::next(CurrPos), MBB->end());
 922 }
 923
 924 void RegPressureTracker::advance() {
 925   const MachineInstr &MI = *CurrPos;
 926   RegisterOperands RegOpers;
 927   RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
 928   if (TrackLaneMasks) {
 929     SlotIndex SlotIdx = getCurrSlot();
 930     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
 931   }
 932   advance(RegOpers);
 933 }
 934
 935 /// Find the max change in excess pressure across all sets.
 936 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
 937                                        ArrayRef<unsigned> NewPressureVec,
 938                                        RegPressureDelta &Delta,
 939                                        const RegisterClassInfo *RCI,
 940                                        ArrayRef<unsigned> LiveThruPressureVec) {
 941   Delta.Excess = PressureChange();
 942   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
 943     unsigned POld = OldPressureVec[i];
 944     unsigned PNew = NewPressureVec[i];
 945     int PDiff = (int)PNew - (int)POld;
 946     if (!PDiff) // No change in this set in the common case.
 947       continue;
 948     // Only consider change beyond the limit.
 949     unsigned Limit = RCI->getRegPressureSetLimit(i);
 950     if (!LiveThruPressureVec.empty())
 951       Limit += LiveThruPressureVec[i];
 952
 953     if (Limit > POld) {
 954       if (Limit > PNew)
 955         PDiff = 0;            // Under the limit
 956       else
 957         PDiff = PNew - Limit; // Just exceeded limit.
 958     } else if (Limit > PNew)
 959       PDiff = Limit - POld;   // Just obeyed limit.
 960
 961     if (PDiff) {
 962       Delta.Excess = PressureChange(i);
 963       Delta.Excess.setUnitInc(PDiff);
 964       break;
 965     }
 966   }
 967 }
 968
 969 /// Find the max change in max pressure that either surpasses a critical PSet
 970 /// limit or exceeds the current MaxPressureLimit.
 971 ///
 972 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
 973 /// silly. It's done now to demonstrate the concept but will go away with a
 974 /// RegPressureTracker API change to work with pressure differences.
 975 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
 976                                     ArrayRef<unsigned> NewMaxPressureVec,
 977                                     ArrayRef<PressureChange> CriticalPSets,
 978                                     ArrayRef<unsigned> MaxPressureLimit,
 979                                     RegPressureDelta &Delta) {
 980   Delta.CriticalMax = PressureChange();
 981   Delta.CurrentMax = PressureChange();
 982
 983   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
 984   for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
 985     unsigned POld = OldMaxPressureVec[i];
 986     unsigned PNew = NewMaxPressureVec[i];
 987     if (PNew == POld) // No change in this set in the common case.
 988       continue;
 989
 990     if (!Delta.CriticalMax.isValid()) {
 991       while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
 992         ++CritIdx;
 993
 994       if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
 995         int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
 996         if (PDiff > 0) {
 997           Delta.CriticalMax = PressureChange(i);
 998           Delta.CriticalMax.setUnitInc(PDiff);
 999         }
1000       }
1001     }
1002     // Find the first increase above MaxPressureLimit.
1003     // (Ignores negative MDiff).
1004     if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
1005       Delta.CurrentMax = PressureChange(i);
1006       Delta.CurrentMax.setUnitInc(PNew - POld);
1007       if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
1008         break;
1009     }
1010   }
1011 }
1012
1013 /// Record the upward impact of a single instruction on current register
1014 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1015 /// not discover live in/outs.
1016 ///
1017 /// This is intended for speculative queries. It leaves pressure inconsistent
1018 /// with the current position, so must be restored by the caller.
1019 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
1020   assert(!MI->isDebugInstr() && "Expect a nondebug instruction.");
1021
1022   SlotIndex SlotIdx;
1023   if (RequireIntervals)
1024     SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1025
1026   // Account for register pressure similar to RegPressureTracker::recede().
1027   RegisterOperands RegOpers;
1028   RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, /*IgnoreDead=*/true);
1029   assert(RegOpers.DeadDefs.size() == 0);
1030   if (TrackLaneMasks)
1031     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1032   else if (RequireIntervals)
1033     RegOpers.detectDeadDefs(*MI, *LIS);
1034
1035   // Boost max pressure for all dead defs together.
1036   // Since CurrSetPressure and MaxSetPressure
1037   bumpDeadDefs(RegOpers.DeadDefs);
1038
1039   // Kill liveness at live defs.
1040   for (const RegisterMaskPair &P : RegOpers.Defs) {
1041     unsigned Reg = P.RegUnit;
1042     LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1043     LaneBitmask UseLanes = getRegLanes(RegOpers.Uses, Reg);
1044     LaneBitmask DefLanes = P.LaneMask;
1045     LaneBitmask LiveAfter = (LiveLanes & ~DefLanes) | UseLanes;
1046     decreaseRegPressure(Reg, LiveLanes, LiveAfter);
1047   }
1048   // Generate liveness for uses.
1049   for (const RegisterMaskPair &P : RegOpers.Uses) {
1050     unsigned Reg = P.RegUnit;
1051     LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1052     LaneBitmask LiveAfter = LiveLanes | P.LaneMask;
1053     increaseRegPressure(Reg, LiveLanes, LiveAfter);
1054   }
1055 }
1056
1057 /// Consider the pressure increase caused by traversing this instruction
1058 /// bottom-up. Find the pressure set with the most change beyond its pressure
1059 /// limit based on the tracker's current pressure, and return the change in
1060 /// number of register units of that pressure set introduced by this
1061 /// instruction.
1062 ///
1063 /// This assumes that the current LiveOut set is sufficient.
1064 ///
1065 /// This is expensive for an on-the-fly query because it calls
1066 /// bumpUpwardPressure to recompute the pressure sets based on current
1067 /// liveness. This mainly exists to verify correctness, e.g. with
1068 /// -verify-misched. getUpwardPressureDelta is the fast version of this query
1069 /// that uses the per-SUnit cache of the PressureDiff.
1070 void RegPressureTracker::
1071 getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
1072                           RegPressureDelta &Delta,
1073                           ArrayRef<PressureChange> CriticalPSets,
1074                           ArrayRef<unsigned> MaxPressureLimit) {
1075   // Snapshot Pressure.
1076   // FIXME: The snapshot heap space should persist. But I'm planning to
1077   // summarize the pressure effect so we don't need to snapshot at all.
1078   std::vector<unsigned> SavedPressure = CurrSetPressure;
1079   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1080
1081   bumpUpwardPressure(MI);
1082
1083   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1084                              LiveThruPressure);
1085   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1086                           MaxPressureLimit, Delta);
1087   assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1088          Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1089
1090   // Restore the tracker's state.
1091   P.MaxSetPressure.swap(SavedMaxPressure);
1092   CurrSetPressure.swap(SavedPressure);
1093
1094 #ifndef NDEBUG
1095   if (!PDiff)
1096     return;
1097
1098   // Check if the alternate algorithm yields the same result.
1099   RegPressureDelta Delta2;
1100   getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
1101   if (Delta != Delta2) {
1102     dbgs() << "PDiff: ";
1103     PDiff->dump(*TRI);
1104     dbgs() << "DELTA: " << *MI;
1105     if (Delta.Excess.isValid())
1106       dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
1107              << " " << Delta.Excess.getUnitInc() << "\n";
1108     if (Delta.CriticalMax.isValid())
1109       dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
1110              << " " << Delta.CriticalMax.getUnitInc() << "\n";
1111     if (Delta.CurrentMax.isValid())
1112       dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
1113              << " " << Delta.CurrentMax.getUnitInc() << "\n";
1114     if (Delta2.Excess.isValid())
1115       dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
1116              << " " << Delta2.Excess.getUnitInc() << "\n";
1117     if (Delta2.CriticalMax.isValid())
1118       dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
1119              << " " << Delta2.CriticalMax.getUnitInc() << "\n";
1120     if (Delta2.CurrentMax.isValid())
1121       dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
1122              << " " << Delta2.CurrentMax.getUnitInc() << "\n";
1123     llvm_unreachable("RegP Delta Mismatch");
1124   }
1125 #endif
1126 }
1127
1128 /// This is the fast version of querying register pressure that does not
1129 /// directly depend on current liveness.
1130 ///
1131 /// @param Delta captures information needed for heuristics.
1132 ///
1133 /// @param CriticalPSets Are the pressure sets that are known to exceed some
1134 /// limit within the region, not necessarily at the current position.
1135 ///
1136 /// @param MaxPressureLimit Is the max pressure within the region, not
1137 /// necessarily at the current position.
1138 void RegPressureTracker::
1139 getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
1140                        RegPressureDelta &Delta,
1141                        ArrayRef<PressureChange> CriticalPSets,
1142                        ArrayRef<unsigned> MaxPressureLimit) const {
1143   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1144   for (PressureDiff::const_iterator
1145          PDiffI = PDiff.begin(), PDiffE = PDiff.end();
1146        PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
1147
1148     unsigned PSetID = PDiffI->getPSet();
1149     unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
1150     if (!LiveThruPressure.empty())
1151       Limit += LiveThruPressure[PSetID];
1152
1153     unsigned POld = CurrSetPressure[PSetID];
1154     unsigned MOld = P.MaxSetPressure[PSetID];
1155     unsigned MNew = MOld;
1156     // Ignore DeadDefs here because they aren't captured by PressureChange.
1157     unsigned PNew = POld + PDiffI->getUnitInc();
1158     assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
1159            && "PSet overflow/underflow");
1160     if (PNew > MOld)
1161       MNew = PNew;
1162     // Check if current pressure has exceeded the limit.
1163     if (!Delta.Excess.isValid()) {
1164       unsigned ExcessInc = 0;
1165       if (PNew > Limit)
1166         ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
1167       else if (POld > Limit)
1168         ExcessInc = Limit - POld;
1169       if (ExcessInc) {
1170         Delta.Excess = PressureChange(PSetID);
1171         Delta.Excess.setUnitInc(ExcessInc);
1172       }
1173     }
1174     // Check if max pressure has exceeded a critical pressure set max.
1175     if (MNew == MOld)
1176       continue;
1177     if (!Delta.CriticalMax.isValid()) {
1178       while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
1179         ++CritIdx;
1180
1181       if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
1182         int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
1183         if (CritInc > 0 && CritInc <= std::numeric_limits<int16_t>::max()) {
1184           Delta.CriticalMax = PressureChange(PSetID);
1185           Delta.CriticalMax.setUnitInc(CritInc);
1186         }
1187       }
1188     }
1189     // Check if max pressure has exceeded the current max.
1190     if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
1191       Delta.CurrentMax = PressureChange(PSetID);
1192       Delta.CurrentMax.setUnitInc(MNew - MOld);
1193     }
1194   }
1195 }
1196
1197 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
1198 /// The query starts with a lane bitmask which gets lanes/bits removed for every
1199 /// use we find.
1200 static LaneBitmask findUseBetween(unsigned Reg, LaneBitmask LastUseMask,
1201                                   SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1202                                   const MachineRegisterInfo &MRI,
1203                                   const LiveIntervals *LIS) {
1204   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
1205   for (const MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1206     if (MO.isUndef())
1207       continue;
1208     const MachineInstr *MI = MO.getParent();
1209     SlotIndex InstSlot = LIS->getInstructionIndex(*MI).getRegSlot();
1210     if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) {
1211       unsigned SubRegIdx = MO.getSubReg();
1212       LaneBitmask UseMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
1213       LastUseMask &= ~UseMask;
1214       if (LastUseMask.none())
1215         return LaneBitmask::getNone();
1216     }
1217   }
1218   return LastUseMask;
1219 }
1220
1221 LaneBitmask RegPressureTracker::getLiveLanesAt(unsigned RegUnit,
1222                                                SlotIndex Pos) const {
1223   assert(RequireIntervals);
1224   return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1225                               LaneBitmask::getAll(),
1226       [](const LiveRange &LR, SlotIndex Pos) {
1227         return LR.liveAt(Pos);
1228       });
1229 }
1230
1231 LaneBitmask RegPressureTracker::getLastUsedLanes(unsigned RegUnit,
1232                                                  SlotIndex Pos) const {
1233   assert(RequireIntervals);
1234   return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit,
1235                               Pos.getBaseIndex(), LaneBitmask::getNone(),
1236       [](const LiveRange &LR, SlotIndex Pos) {
1237         const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1238         return S != nullptr && S->end == Pos.getRegSlot();
1239       });
1240 }
1241
1242 LaneBitmask RegPressureTracker::getLiveThroughAt(unsigned RegUnit,
1243                                                  SlotIndex Pos) const {
1244   assert(RequireIntervals);
1245   return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1246                               LaneBitmask::getNone(),
1247       [](const LiveRange &LR, SlotIndex Pos) {
1248         const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1249         return S != nullptr && S->start < Pos.getRegSlot(true) &&
1250                S->end != Pos.getDeadSlot();
1251       });
1252 }
1253
1254 /// Record the downward impact of a single instruction on current register
1255 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1256 /// not discover live in/outs.
1257 ///
1258 /// This is intended for speculative queries. It leaves pressure inconsistent
1259 /// with the current position, so must be restored by the caller.
1260 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
1261   assert(!MI->isDebugInstr() && "Expect a nondebug instruction.");
1262
1263   SlotIndex SlotIdx;
1264   if (RequireIntervals)
1265     SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1266
1267   // Account for register pressure similar to RegPressureTracker::recede().
1268   RegisterOperands RegOpers;
1269   RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, false);
1270   if (TrackLaneMasks)
1271     RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1272
1273   if (RequireIntervals) {
1274     for (const RegisterMaskPair &Use : RegOpers.Uses) {
1275       unsigned Reg = Use.RegUnit;
1276       LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
1277       if (LastUseMask.none())
1278         continue;
1279       // The LastUseMask is queried from the liveness information of instruction
1280       // which may be further down the schedule. Some lanes may actually not be
1281       // last uses for the current position.
1282       // FIXME: allow the caller to pass in the list of vreg uses that remain
1283       // to be bottom-scheduled to avoid searching uses at each query.
1284       SlotIndex CurrIdx = getCurrSlot();
1285       LastUseMask
1286         = findUseBetween(Reg, LastUseMask, CurrIdx, SlotIdx, *MRI, LIS);
1287       if (LastUseMask.none())
1288         continue;
1289
1290       LaneBitmask LiveMask = LiveRegs.contains(Reg);
1291       LaneBitmask NewMask = LiveMask & ~LastUseMask;
1292       decreaseRegPressure(Reg, LiveMask, NewMask);
1293     }
1294   }
1295
1296   // Generate liveness for defs.
1297   for (const RegisterMaskPair &Def : RegOpers.Defs) {
1298     unsigned Reg = Def.RegUnit;
1299     LaneBitmask LiveMask = LiveRegs.contains(Reg);
1300     LaneBitmask NewMask = LiveMask | Def.LaneMask;
1301     increaseRegPressure(Reg, LiveMask, NewMask);
1302   }
1303
1304   // Boost pressure for all dead defs together.
1305   bumpDeadDefs(RegOpers.DeadDefs);
1306 }
1307
1308 /// Consider the pressure increase caused by traversing this instruction
1309 /// top-down. Find the register class with the most change in its pressure limit
1310 /// based on the tracker's current pressure, and return the number of excess
1311 /// register units of that pressure set introduced by this instruction.
1312 ///
1313 /// This assumes that the current LiveIn set is sufficient.
1314 ///
1315 /// This is expensive for an on-the-fly query because it calls
1316 /// bumpDownwardPressure to recompute the pressure sets based on current
1317 /// liveness. We don't yet have a fast version of downward pressure tracking
1318 /// analogous to getUpwardPressureDelta.
1319 void RegPressureTracker::
1320 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
1321                             ArrayRef<PressureChange> CriticalPSets,
1322                             ArrayRef<unsigned> MaxPressureLimit) {
1323   // Snapshot Pressure.
1324   std::vector<unsigned> SavedPressure = CurrSetPressure;
1325   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1326
1327   bumpDownwardPressure(MI);
1328
1329   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1330                              LiveThruPressure);
1331   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1332                           MaxPressureLimit, Delta);
1333   assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1334          Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1335
1336   // Restore the tracker's state.
1337   P.MaxSetPressure.swap(SavedMaxPressure);
1338   CurrSetPressure.swap(SavedPressure);
1339 }
1340
1341 /// Get the pressure of each PSet after traversing this instruction bottom-up.
1342 void RegPressureTracker::
1343 getUpwardPressure(const MachineInstr *MI,
1344                   std::vector<unsigned> &PressureResult,
1345                   std::vector<unsigned> &MaxPressureResult) {
1346   // Snapshot pressure.
1347   PressureResult = CurrSetPressure;
1348   MaxPressureResult = P.MaxSetPressure;
1349
1350   bumpUpwardPressure(MI);
1351
1352   // Current pressure becomes the result. Restore current pressure.
1353   P.MaxSetPressure.swap(MaxPressureResult);
1354   CurrSetPressure.swap(PressureResult);
1355 }
1356
1357 /// Get the pressure of each PSet after traversing this instruction top-down.
1358 void RegPressureTracker::
1359 getDownwardPressure(const MachineInstr *MI,
1360                     std::vector<unsigned> &PressureResult,
1361                     std::vector<unsigned> &MaxPressureResult) {
1362   // Snapshot pressure.
1363   PressureResult = CurrSetPressure;
1364   MaxPressureResult = P.MaxSetPressure;
1365
1366   bumpDownwardPressure(MI);
1367
1368   // Current pressure becomes the result. Restore current pressure.
1369   P.MaxSetPressure.swap(MaxPressureResult);
1370   CurrSetPressure.swap(PressureResult);
1371 }