lib/CodeGen/RegisterPressure.cpp

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