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