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