contrib/llvm/lib/CodeGen/RegisterPressure.cpp

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