contrib/llvm/lib/CodeGen/RegisterPressure.cpp

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