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