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