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