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