RegisterPressure.cpp revision 1362dcb5899bc88f0e567dd10e2e9003a79ace21
1//===-- RegisterPressure.cpp - Dynamic Register Pressure ------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the RegisterPressure class which can be used to track 11// MachineInstr level register pressure. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/CodeGen/RegisterPressure.h" 16#include "llvm/CodeGen/LiveInterval.h" 17#include "llvm/CodeGen/LiveIntervalAnalysis.h" 18#include "llvm/CodeGen/MachineRegisterInfo.h" 19#include "llvm/CodeGen/RegisterClassInfo.h" 20#include "llvm/Support/Debug.h" 21#include "llvm/Support/raw_ostream.h" 22#include "llvm/Target/TargetMachine.h" 23 24using namespace llvm; 25 26/// Increase pressure for each pressure set provided by TargetRegisterInfo. 27static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure, 28 PSetIterator PSetI) { 29 unsigned Weight = PSetI.getWeight(); 30 for (; PSetI.isValid(); ++PSetI) 31 CurrSetPressure[*PSetI] += Weight; 32} 33 34/// Decrease pressure for each pressure set provided by TargetRegisterInfo. 35static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure, 36 PSetIterator PSetI) { 37 unsigned Weight = PSetI.getWeight(); 38 for (; PSetI.isValid(); ++PSetI) { 39 assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"); 40 CurrSetPressure[*PSetI] -= Weight; 41 } 42} 43 44#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 45void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure, 46 const TargetRegisterInfo *TRI) { 47 bool Empty = true; 48 for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) { 49 if (SetPressure[i] != 0) { 50 dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n'; 51 Empty = false; 52 } 53 } 54 if (Empty) 55 dbgs() << "\n"; 56} 57 58void RegisterPressure::dump(const TargetRegisterInfo *TRI) const { 59 dbgs() << "Max Pressure: "; 60 dumpRegSetPressure(MaxSetPressure, TRI); 61 dbgs() << "Live In: "; 62 for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i) 63 dbgs() << PrintReg(LiveInRegs[i], TRI) << " "; 64 dbgs() << '\n'; 65 dbgs() << "Live Out: "; 66 for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i) 67 dbgs() << PrintReg(LiveOutRegs[i], TRI) << " "; 68 dbgs() << '\n'; 69} 70 71void RegPressureTracker::dump() const { 72 if (!isTopClosed() || !isBottomClosed()) { 73 dbgs() << "Curr Pressure: "; 74 dumpRegSetPressure(CurrSetPressure, TRI); 75 } 76 P.dump(TRI); 77} 78#endif 79 80/// Increase the current pressure as impacted by these registers and bump 81/// the high water mark if needed. 82void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> RegUnits) { 83 for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) { 84 PSetIterator PSetI = MRI->getPressureSets(RegUnits[i]); 85 unsigned Weight = PSetI.getWeight(); 86 for (; PSetI.isValid(); ++PSetI) { 87 CurrSetPressure[*PSetI] += Weight; 88 if (CurrSetPressure[*PSetI] > P.MaxSetPressure[*PSetI]) { 89 P.MaxSetPressure[*PSetI] = CurrSetPressure[*PSetI]; 90 } 91 } 92 } 93} 94 95/// Simply decrease the current pressure as impacted by these registers. 96void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> RegUnits) { 97 for (unsigned I = 0, E = RegUnits.size(); I != E; ++I) 98 decreaseSetPressure(CurrSetPressure, MRI->getPressureSets(RegUnits[I])); 99} 100 101/// Clear the result so it can be used for another round of pressure tracking. 102void IntervalPressure::reset() { 103 TopIdx = BottomIdx = SlotIndex(); 104 MaxSetPressure.clear(); 105 LiveInRegs.clear(); 106 LiveOutRegs.clear(); 107} 108 109/// Clear the result so it can be used for another round of pressure tracking. 110void RegionPressure::reset() { 111 TopPos = BottomPos = MachineBasicBlock::const_iterator(); 112 MaxSetPressure.clear(); 113 LiveInRegs.clear(); 114 LiveOutRegs.clear(); 115} 116 117/// If the current top is not less than or equal to the next index, open it. 118/// We happen to need the SlotIndex for the next top for pressure update. 119void IntervalPressure::openTop(SlotIndex NextTop) { 120 if (TopIdx <= NextTop) 121 return; 122 TopIdx = SlotIndex(); 123 LiveInRegs.clear(); 124} 125 126/// If the current top is the previous instruction (before receding), open it. 127void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) { 128 if (TopPos != PrevTop) 129 return; 130 TopPos = MachineBasicBlock::const_iterator(); 131 LiveInRegs.clear(); 132} 133 134/// If the current bottom is not greater than the previous index, open it. 135void IntervalPressure::openBottom(SlotIndex PrevBottom) { 136 if (BottomIdx > PrevBottom) 137 return; 138 BottomIdx = SlotIndex(); 139 LiveInRegs.clear(); 140} 141 142/// If the current bottom is the previous instr (before advancing), open it. 143void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) { 144 if (BottomPos != PrevBottom) 145 return; 146 BottomPos = MachineBasicBlock::const_iterator(); 147 LiveInRegs.clear(); 148} 149 150const LiveInterval *RegPressureTracker::getInterval(unsigned Reg) const { 151 if (TargetRegisterInfo::isVirtualRegister(Reg)) 152 return &LIS->getInterval(Reg); 153 return LIS->getCachedRegUnit(Reg); 154} 155 156/// Setup the RegPressureTracker. 157/// 158/// TODO: Add support for pressure without LiveIntervals. 159void RegPressureTracker::init(const MachineFunction *mf, 160 const RegisterClassInfo *rci, 161 const LiveIntervals *lis, 162 const MachineBasicBlock *mbb, 163 MachineBasicBlock::const_iterator pos, 164 bool ShouldTrackUntiedDefs) 165{ 166 MF = mf; 167 TRI = MF->getTarget().getRegisterInfo(); 168 RCI = rci; 169 MRI = &MF->getRegInfo(); 170 MBB = mbb; 171 TrackUntiedDefs = ShouldTrackUntiedDefs; 172 173 if (RequireIntervals) { 174 assert(lis && "IntervalPressure requires LiveIntervals"); 175 LIS = lis; 176 } 177 178 CurrPos = pos; 179 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0); 180 LiveThruPressure.clear(); 181 182 if (RequireIntervals) 183 static_cast<IntervalPressure&>(P).reset(); 184 else 185 static_cast<RegionPressure&>(P).reset(); 186 P.MaxSetPressure = CurrSetPressure; 187 188 LiveRegs.PhysRegs.clear(); 189 LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs()); 190 LiveRegs.VirtRegs.clear(); 191 LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs()); 192 UntiedDefs.clear(); 193 if (TrackUntiedDefs) 194 UntiedDefs.setUniverse(MRI->getNumVirtRegs()); 195} 196 197/// Does this pressure result have a valid top position and live ins. 198bool RegPressureTracker::isTopClosed() const { 199 if (RequireIntervals) 200 return static_cast<IntervalPressure&>(P).TopIdx.isValid(); 201 return (static_cast<RegionPressure&>(P).TopPos == 202 MachineBasicBlock::const_iterator()); 203} 204 205/// Does this pressure result have a valid bottom position and live outs. 206bool RegPressureTracker::isBottomClosed() const { 207 if (RequireIntervals) 208 return static_cast<IntervalPressure&>(P).BottomIdx.isValid(); 209 return (static_cast<RegionPressure&>(P).BottomPos == 210 MachineBasicBlock::const_iterator()); 211} 212 213 214SlotIndex RegPressureTracker::getCurrSlot() const { 215 MachineBasicBlock::const_iterator IdxPos = CurrPos; 216 while (IdxPos != MBB->end() && IdxPos->isDebugValue()) 217 ++IdxPos; 218 if (IdxPos == MBB->end()) 219 return LIS->getMBBEndIdx(MBB); 220 return LIS->getInstructionIndex(IdxPos).getRegSlot(); 221} 222 223/// Set the boundary for the top of the region and summarize live ins. 224void RegPressureTracker::closeTop() { 225 if (RequireIntervals) 226 static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot(); 227 else 228 static_cast<RegionPressure&>(P).TopPos = CurrPos; 229 230 assert(P.LiveInRegs.empty() && "inconsistent max pressure result"); 231 P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); 232 P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); 233 for (SparseSet<unsigned>::const_iterator I = 234 LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) 235 P.LiveInRegs.push_back(*I); 236 std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end()); 237 P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()), 238 P.LiveInRegs.end()); 239} 240 241/// Set the boundary for the bottom of the region and summarize live outs. 242void RegPressureTracker::closeBottom() { 243 if (RequireIntervals) 244 static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot(); 245 else 246 static_cast<RegionPressure&>(P).BottomPos = CurrPos; 247 248 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result"); 249 P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); 250 P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); 251 for (SparseSet<unsigned>::const_iterator I = 252 LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) 253 P.LiveOutRegs.push_back(*I); 254 std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end()); 255 P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()), 256 P.LiveOutRegs.end()); 257} 258 259/// Finalize the region boundaries and record live ins and live outs. 260void RegPressureTracker::closeRegion() { 261 if (!isTopClosed() && !isBottomClosed()) { 262 assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() && 263 "no region boundary"); 264 return; 265 } 266 if (!isBottomClosed()) 267 closeBottom(); 268 else if (!isTopClosed()) 269 closeTop(); 270 // If both top and bottom are closed, do nothing. 271} 272 273/// The register tracker is unaware of global liveness so ignores normal 274/// live-thru ranges. However, two-address or coalesced chains can also lead 275/// to live ranges with no holes. Count these to inform heuristics that we 276/// can never drop below this pressure. 277void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) { 278 LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0); 279 assert(isBottomClosed() && "need bottom-up tracking to intialize."); 280 for (unsigned i = 0, e = P.LiveOutRegs.size(); i < e; ++i) { 281 unsigned Reg = P.LiveOutRegs[i]; 282 if (TargetRegisterInfo::isVirtualRegister(Reg) 283 && !RPTracker.hasUntiedDef(Reg)) { 284 increaseSetPressure(LiveThruPressure, MRI->getPressureSets(Reg)); 285 } 286 } 287} 288 289/// \brief Convenient wrapper for checking membership in RegisterOperands. 290/// (std::count() doesn't have an early exit). 291static bool containsReg(ArrayRef<unsigned> RegUnits, unsigned RegUnit) { 292 return std::find(RegUnits.begin(), RegUnits.end(), RegUnit) != RegUnits.end(); 293} 294 295/// Collect this instruction's unique uses and defs into SmallVectors for 296/// processing defs and uses in order. 297/// 298/// FIXME: always ignore tied opers 299class RegisterOperands { 300 const TargetRegisterInfo *TRI; 301 const MachineRegisterInfo *MRI; 302 bool IgnoreDead; 303 304public: 305 SmallVector<unsigned, 8> Uses; 306 SmallVector<unsigned, 8> Defs; 307 SmallVector<unsigned, 8> DeadDefs; 308 309 RegisterOperands(const TargetRegisterInfo *tri, 310 const MachineRegisterInfo *mri, bool ID = false): 311 TRI(tri), MRI(mri), IgnoreDead(ID) {} 312 313 /// Push this operand's register onto the correct vector. 314 void collect(const MachineOperand &MO) { 315 if (!MO.isReg() || !MO.getReg()) 316 return; 317 if (MO.readsReg()) 318 pushRegUnits(MO.getReg(), Uses); 319 if (MO.isDef()) { 320 if (MO.isDead()) { 321 if (!IgnoreDead) 322 pushRegUnits(MO.getReg(), DeadDefs); 323 } 324 else 325 pushRegUnits(MO.getReg(), Defs); 326 } 327 } 328 329protected: 330 void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &RegUnits) { 331 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 332 if (containsReg(RegUnits, Reg)) 333 return; 334 RegUnits.push_back(Reg); 335 } 336 else if (MRI->isAllocatable(Reg)) { 337 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 338 if (containsReg(RegUnits, *Units)) 339 continue; 340 RegUnits.push_back(*Units); 341 } 342 } 343 } 344}; 345 346/// Collect physical and virtual register operands. 347static void collectOperands(const MachineInstr *MI, 348 RegisterOperands &RegOpers) { 349 for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) 350 RegOpers.collect(*OperI); 351 352 // Remove redundant physreg dead defs. 353 SmallVectorImpl<unsigned>::iterator I = 354 std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(), 355 std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs)); 356 RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end()); 357} 358 359/// Initialize an array of N PressureDiffs. 360void PressureDiffs::init(unsigned N) { 361 Size = N; 362 if (N <= Max) { 363 memset(PDiffArray, 0, N * sizeof(PressureDiff)); 364 return; 365 } 366 Max = Size; 367 free(PDiffArray); 368 PDiffArray = reinterpret_cast<PressureDiff*>(calloc(N, sizeof(PressureDiff))); 369} 370 371/// Add a change in pressure to the pressure diff of a given instruction. 372void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec, 373 const MachineRegisterInfo *MRI) { 374 PSetIterator PSetI = MRI->getPressureSets(RegUnit); 375 int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight(); 376 for (; PSetI.isValid(); ++PSetI) { 377 // Find an existing entry in the pressure diff for this PSet. 378 PressureDiff::iterator I = begin(), E = end(); 379 for (; I != E && I->isValid(); ++I) { 380 if (I->getPSet() >= *PSetI) 381 break; 382 } 383 // If all pressure sets are more constrained, skip the remaining PSets. 384 if (I == E) 385 break; 386 // Insert this PressureChange. 387 if (!I->isValid() || I->getPSet() != *PSetI) { 388 PressureChange PTmp = PressureChange(*PSetI); 389 for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J) 390 std::swap(*J,PTmp); 391 } 392 // Update the units for this pressure set. 393 I->setUnitInc(I->getUnitInc() + Weight); 394 } 395} 396 397/// Record the pressure difference induced by the given operand list. 398static void collectPDiff(PressureDiff &PDiff, RegisterOperands &RegOpers, 399 const MachineRegisterInfo *MRI) { 400 assert(!PDiff.begin()->isValid() && "stale PDiff"); 401 402 for (unsigned i = 0, e = RegOpers.Defs.size(); i != e; ++i) { 403 if (!containsReg(RegOpers.Uses, RegOpers.Defs[i])) 404 PDiff.addPressureChange(RegOpers.Defs[i], true, MRI); 405 } 406 for (unsigned i = 0, e = RegOpers.Uses.size(); i != e; ++i) 407 PDiff.addPressureChange(RegOpers.Uses[i], false, MRI); 408} 409 410/// Force liveness of registers. 411void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) { 412 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 413 if (LiveRegs.insert(Regs[i])) 414 increaseRegPressure(Regs[i]); 415 } 416} 417 418/// Add Reg to the live in set and increase max pressure. 419void RegPressureTracker::discoverLiveIn(unsigned Reg) { 420 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 421 if (containsReg(P.LiveInRegs, Reg)) 422 return; 423 424 // At live in discovery, unconditionally increase the high water mark. 425 P.LiveInRegs.push_back(Reg); 426 increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); 427} 428 429/// Add Reg to the live out set and increase max pressure. 430void RegPressureTracker::discoverLiveOut(unsigned Reg) { 431 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 432 if (containsReg(P.LiveOutRegs, Reg)) 433 return; 434 435 // At live out discovery, unconditionally increase the high water mark. 436 P.LiveOutRegs.push_back(Reg); 437 increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); 438} 439 440/// Recede across the previous instruction. 441/// Record the pressure difference if it is provided. 442bool RegPressureTracker::recede(PressureDiff *PDiff) { 443 // Check for the top of the analyzable region. 444 if (CurrPos == MBB->begin()) { 445 closeRegion(); 446 return false; 447 } 448 if (!isBottomClosed()) 449 closeBottom(); 450 451 // Open the top of the region using block iterators. 452 if (!RequireIntervals && isTopClosed()) 453 static_cast<RegionPressure&>(P).openTop(CurrPos); 454 455 // Find the previous instruction. 456 do 457 --CurrPos; 458 while (CurrPos != MBB->begin() && CurrPos->isDebugValue()); 459 460 if (CurrPos->isDebugValue()) { 461 closeRegion(); 462 return false; 463 } 464 SlotIndex SlotIdx; 465 if (RequireIntervals) 466 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); 467 468 // Open the top of the region using slot indexes. 469 if (RequireIntervals && isTopClosed()) 470 static_cast<IntervalPressure&>(P).openTop(SlotIdx); 471 472 RegisterOperands RegOpers(TRI, MRI); 473 collectOperands(CurrPos, RegOpers); 474 475 if (PDiff) 476 collectPDiff(*PDiff, RegOpers, MRI); 477 478 // Boost pressure for all dead defs together. 479 increaseRegPressure(RegOpers.DeadDefs); 480 decreaseRegPressure(RegOpers.DeadDefs); 481 482 // Kill liveness at live defs. 483 // TODO: consider earlyclobbers? 484 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 485 unsigned Reg = RegOpers.Defs[i]; 486 if (LiveRegs.erase(Reg)) 487 decreaseRegPressure(Reg); 488 else 489 discoverLiveOut(Reg); 490 } 491 492 // Generate liveness for uses. 493 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 494 unsigned Reg = RegOpers.Uses[i]; 495 if (!LiveRegs.contains(Reg)) { 496 // Adjust liveouts if LiveIntervals are available. 497 if (RequireIntervals) { 498 const LiveInterval *LI = getInterval(Reg); 499 if (LI && !LI->isKilledAtInstr(SlotIdx)) 500 discoverLiveOut(Reg); 501 } 502 increaseRegPressure(Reg); 503 LiveRegs.insert(Reg); 504 } 505 } 506 if (TrackUntiedDefs) { 507 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 508 unsigned Reg = RegOpers.Defs[i]; 509 if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg)) 510 UntiedDefs.insert(Reg); 511 } 512 } 513 return true; 514} 515 516/// Advance across the current instruction. 517bool RegPressureTracker::advance() { 518 assert(!TrackUntiedDefs && "unsupported mode"); 519 520 // Check for the bottom of the analyzable region. 521 if (CurrPos == MBB->end()) { 522 closeRegion(); 523 return false; 524 } 525 if (!isTopClosed()) 526 closeTop(); 527 528 SlotIndex SlotIdx; 529 if (RequireIntervals) 530 SlotIdx = getCurrSlot(); 531 532 // Open the bottom of the region using slot indexes. 533 if (isBottomClosed()) { 534 if (RequireIntervals) 535 static_cast<IntervalPressure&>(P).openBottom(SlotIdx); 536 else 537 static_cast<RegionPressure&>(P).openBottom(CurrPos); 538 } 539 540 RegisterOperands RegOpers(TRI, MRI); 541 collectOperands(CurrPos, RegOpers); 542 543 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 544 unsigned Reg = RegOpers.Uses[i]; 545 // Discover live-ins. 546 bool isLive = LiveRegs.contains(Reg); 547 if (!isLive) 548 discoverLiveIn(Reg); 549 // Kill liveness at last uses. 550 bool lastUse = false; 551 if (RequireIntervals) { 552 const LiveInterval *LI = getInterval(Reg); 553 lastUse = LI && LI->isKilledAtInstr(SlotIdx); 554 } 555 else { 556 // Allocatable physregs are always single-use before register rewriting. 557 lastUse = !TargetRegisterInfo::isVirtualRegister(Reg); 558 } 559 if (lastUse && isLive) { 560 LiveRegs.erase(Reg); 561 decreaseRegPressure(Reg); 562 } 563 else if (!lastUse && !isLive) 564 increaseRegPressure(Reg); 565 } 566 567 // Generate liveness for defs. 568 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 569 unsigned Reg = RegOpers.Defs[i]; 570 if (LiveRegs.insert(Reg)) 571 increaseRegPressure(Reg); 572 } 573 574 // Boost pressure for all dead defs together. 575 increaseRegPressure(RegOpers.DeadDefs); 576 decreaseRegPressure(RegOpers.DeadDefs); 577 578 // Find the next instruction. 579 do 580 ++CurrPos; 581 while (CurrPos != MBB->end() && CurrPos->isDebugValue()); 582 return true; 583} 584 585/// Find the max change in excess pressure across all sets. 586static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec, 587 ArrayRef<unsigned> NewPressureVec, 588 RegPressureDelta &Delta, 589 const RegisterClassInfo *RCI, 590 ArrayRef<unsigned> LiveThruPressureVec) { 591 Delta.Excess = PressureChange(); 592 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) { 593 unsigned POld = OldPressureVec[i]; 594 unsigned PNew = NewPressureVec[i]; 595 int PDiff = (int)PNew - (int)POld; 596 if (!PDiff) // No change in this set in the common case. 597 continue; 598 // Only consider change beyond the limit. 599 unsigned Limit = RCI->getRegPressureSetLimit(i); 600 if (!LiveThruPressureVec.empty()) 601 Limit += LiveThruPressureVec[i]; 602 603 if (Limit > POld) { 604 if (Limit > PNew) 605 PDiff = 0; // Under the limit 606 else 607 PDiff = PNew - Limit; // Just exceeded limit. 608 } 609 else if (Limit > PNew) 610 PDiff = Limit - POld; // Just obeyed limit. 611 612 if (PDiff) { 613 Delta.Excess = PressureChange(i); 614 Delta.Excess.setUnitInc(PDiff); 615 break; 616 } 617 } 618} 619 620/// Find the max change in max pressure that either surpasses a critical PSet 621/// limit or exceeds the current MaxPressureLimit. 622/// 623/// FIXME: comparing each element of the old and new MaxPressure vectors here is 624/// silly. It's done now to demonstrate the concept but will go away with a 625/// RegPressureTracker API change to work with pressure differences. 626static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec, 627 ArrayRef<unsigned> NewMaxPressureVec, 628 ArrayRef<PressureChange> CriticalPSets, 629 ArrayRef<unsigned> MaxPressureLimit, 630 RegPressureDelta &Delta) { 631 Delta.CriticalMax = PressureChange(); 632 Delta.CurrentMax = PressureChange(); 633 634 unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); 635 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) { 636 unsigned POld = OldMaxPressureVec[i]; 637 unsigned PNew = NewMaxPressureVec[i]; 638 if (PNew == POld) // No change in this set in the common case. 639 continue; 640 641 if (!Delta.CriticalMax.isValid()) { 642 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i) 643 ++CritIdx; 644 645 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) { 646 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc(); 647 if (PDiff > 0) { 648 Delta.CriticalMax = PressureChange(i); 649 Delta.CriticalMax.setUnitInc(PDiff); 650 } 651 } 652 } 653 // Find the first increase above MaxPressureLimit. 654 // (Ignores negative MDiff). 655 if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) { 656 Delta.CurrentMax = PressureChange(i); 657 Delta.CurrentMax.setUnitInc(PNew - POld); 658 if (CritIdx == CritEnd || Delta.CriticalMax.isValid()) 659 break; 660 } 661 } 662} 663 664/// Record the upward impact of a single instruction on current register 665/// pressure. Unlike the advance/recede pressure tracking interface, this does 666/// not discover live in/outs. 667/// 668/// This is intended for speculative queries. It leaves pressure inconsistent 669/// with the current position, so must be restored by the caller. 670void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) { 671 assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 672 673 // Account for register pressure similar to RegPressureTracker::recede(). 674 RegisterOperands RegOpers(TRI, MRI, /*IgnoreDead=*/true); 675 collectOperands(MI, RegOpers); 676 677 // Boost max pressure for all dead defs together. 678 // Since CurrSetPressure and MaxSetPressure 679 increaseRegPressure(RegOpers.DeadDefs); 680 decreaseRegPressure(RegOpers.DeadDefs); 681 682 // Kill liveness at live defs. 683 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 684 unsigned Reg = RegOpers.Defs[i]; 685 if (!containsReg(RegOpers.Uses, Reg)) 686 decreaseRegPressure(Reg); 687 } 688 // Generate liveness for uses. 689 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 690 unsigned Reg = RegOpers.Uses[i]; 691 if (!LiveRegs.contains(Reg)) 692 increaseRegPressure(Reg); 693 } 694} 695 696/// Consider the pressure increase caused by traversing this instruction 697/// bottom-up. Find the pressure set with the most change beyond its pressure 698/// limit based on the tracker's current pressure, and return the change in 699/// number of register units of that pressure set introduced by this 700/// instruction. 701/// 702/// This assumes that the current LiveOut set is sufficient. 703/// 704/// FIXME: This is expensive for an on-the-fly query. We need to cache the 705/// result per-SUnit with enough information to adjust for the current 706/// scheduling position. But this works as a proof of concept. 707void RegPressureTracker:: 708getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, 709 RegPressureDelta &Delta, 710 ArrayRef<PressureChange> CriticalPSets, 711 ArrayRef<unsigned> MaxPressureLimit) { 712 // Snapshot Pressure. 713 // FIXME: The snapshot heap space should persist. But I'm planning to 714 // summarize the pressure effect so we don't need to snapshot at all. 715 std::vector<unsigned> SavedPressure = CurrSetPressure; 716 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 717 718 bumpUpwardPressure(MI); 719 720 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, 721 LiveThruPressure); 722 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 723 MaxPressureLimit, Delta); 724 assert(Delta.CriticalMax.getUnitInc() >= 0 && 725 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure"); 726 727 // Restore the tracker's state. 728 P.MaxSetPressure.swap(SavedMaxPressure); 729 CurrSetPressure.swap(SavedPressure); 730 731#ifndef NDEBUG 732 if (!PDiff) 733 return; 734 735 // Check if the alternate algorithm yields the same result. 736 RegPressureDelta Delta2; 737 getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit); 738 if (Delta != Delta2) { 739 dbgs() << "DELTA: " << *MI; 740 if (Delta.Excess.isValid()) 741 dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet()) 742 << " " << Delta.Excess.getUnitInc() << "\n"; 743 if (Delta.CriticalMax.isValid()) 744 dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet()) 745 << " " << Delta.CriticalMax.getUnitInc() << "\n"; 746 if (Delta.CurrentMax.isValid()) 747 dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet()) 748 << " " << Delta.CurrentMax.getUnitInc() << "\n"; 749 if (Delta2.Excess.isValid()) 750 dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet()) 751 << " " << Delta2.Excess.getUnitInc() << "\n"; 752 if (Delta2.CriticalMax.isValid()) 753 dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet()) 754 << " " << Delta2.CriticalMax.getUnitInc() << "\n"; 755 if (Delta2.CurrentMax.isValid()) 756 dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet()) 757 << " " << Delta2.CurrentMax.getUnitInc() << "\n"; 758 llvm_unreachable("RegP Delta Mismatch"); 759 } 760#endif 761} 762 763/// This is a prototype of the fast version of querying register pressure that 764/// does not directly depend on current liveness. It's still slow because we 765/// recompute pressure change on-the-fly. This implementation only exists to 766/// prove correctness. 767/// 768/// @param Delta captures information needed for heuristics. 769/// 770/// @param CriticalPSets Are the pressure sets that are known to exceed some 771/// limit within the region, not necessarily at the current position. 772/// 773/// @param MaxPressureLimit Is the max pressure within the region, not 774/// necessarily at the current position. 775void RegPressureTracker:: 776getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff1, 777 RegPressureDelta &Delta, 778 ArrayRef<PressureChange> CriticalPSets, 779 ArrayRef<unsigned> MaxPressureLimit) const { 780 RegisterOperands RegOpers(TRI, MRI, /*IgnoreDead=*/true); 781 collectOperands(MI, RegOpers); 782 783 // Decrease the pressure change for live uses. 784 PressureDiff PDiff = PDiff1; 785 for (unsigned i = 0, e = RegOpers.Uses.size(); i != e; ++i) { 786 if (LiveRegs.contains(RegOpers.Uses[i])) 787 PDiff.addPressureChange(RegOpers.Uses[i], true, MRI); 788 } 789 790 // Now directly query pressure from PDiff. Everything above this can be 791 // cached and updated independent of the query. 792 unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); 793 for (PressureDiff::const_iterator 794 PDiffI = PDiff.begin(), PDiffE = PDiff.end(); 795 PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) { 796 797 unsigned PSetID = PDiffI->getPSet(); 798 unsigned Limit = RCI->getRegPressureSetLimit(PSetID); 799 if (!LiveThruPressure.empty()) 800 Limit += LiveThruPressure[PSetID]; 801 802 unsigned POld = CurrSetPressure[PSetID]; 803 unsigned MOld = P.MaxSetPressure[PSetID]; 804 unsigned MNew = MOld; 805 // Ignore DeadDefs here because they aren't captured by PressureChange. 806 unsigned PNew = POld + PDiffI->getUnitInc(); 807 assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld) && "PSet overflow"); 808 if (PNew > MOld) 809 MNew = PNew; 810 // Check if current pressure has exceeded the limit. 811 if (!Delta.Excess.isValid()) { 812 unsigned ExcessInc = 0; 813 if (PNew > Limit) 814 ExcessInc = POld > Limit ? PNew - POld : PNew - Limit; 815 else if (POld > Limit) 816 ExcessInc = Limit - POld; 817 if (ExcessInc) { 818 Delta.Excess = PressureChange(PSetID); 819 Delta.Excess.setUnitInc(ExcessInc); 820 } 821 } 822 // Check if max pressure has exceeded a critical pressure set max. 823 if (MNew == MOld) 824 continue; 825 if (!Delta.CriticalMax.isValid()) { 826 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID) 827 ++CritIdx; 828 829 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) { 830 int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc(); 831 if (CritInc > 0 && CritInc <= INT16_MAX) { 832 Delta.CriticalMax = PressureChange(PSetID); 833 Delta.CriticalMax.setUnitInc(CritInc); 834 } 835 } 836 } 837 // Check if max pressure has exceeded the current max. 838 if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) { 839 Delta.CurrentMax = PressureChange(PSetID); 840 Delta.CurrentMax.setUnitInc(MNew - MOld); 841 } 842 } 843} 844 845/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx). 846static bool findUseBetween(unsigned Reg, 847 SlotIndex PriorUseIdx, SlotIndex NextUseIdx, 848 const MachineRegisterInfo *MRI, 849 const LiveIntervals *LIS) { 850 for (MachineRegisterInfo::use_nodbg_iterator 851 UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end(); 852 UI != UE; UI.skipInstruction()) { 853 const MachineInstr* MI = &*UI; 854 if (MI->isDebugValue()) 855 continue; 856 SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot(); 857 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) 858 return true; 859 } 860 return false; 861} 862 863/// Record the downward impact of a single instruction on current register 864/// pressure. Unlike the advance/recede pressure tracking interface, this does 865/// not discover live in/outs. 866/// 867/// This is intended for speculative queries. It leaves pressure inconsistent 868/// with the current position, so must be restored by the caller. 869void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) { 870 assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 871 872 // Account for register pressure similar to RegPressureTracker::recede(). 873 RegisterOperands RegOpers(TRI, MRI); 874 collectOperands(MI, RegOpers); 875 876 // Kill liveness at last uses. Assume allocatable physregs are single-use 877 // rather than checking LiveIntervals. 878 SlotIndex SlotIdx; 879 if (RequireIntervals) 880 SlotIdx = LIS->getInstructionIndex(MI).getRegSlot(); 881 882 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 883 unsigned Reg = RegOpers.Uses[i]; 884 if (RequireIntervals) { 885 // FIXME: allow the caller to pass in the list of vreg uses that remain 886 // to be bottom-scheduled to avoid searching uses at each query. 887 SlotIndex CurrIdx = getCurrSlot(); 888 const LiveInterval *LI = getInterval(Reg); 889 if (LI && LI->isKilledAtInstr(SlotIdx) 890 && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) { 891 decreaseRegPressure(Reg); 892 } 893 } 894 else if (!TargetRegisterInfo::isVirtualRegister(Reg)) { 895 // Allocatable physregs are always single-use before register rewriting. 896 decreaseRegPressure(Reg); 897 } 898 } 899 900 // Generate liveness for defs. 901 increaseRegPressure(RegOpers.Defs); 902 903 // Boost pressure for all dead defs together. 904 increaseRegPressure(RegOpers.DeadDefs); 905 decreaseRegPressure(RegOpers.DeadDefs); 906} 907 908/// Consider the pressure increase caused by traversing this instruction 909/// top-down. Find the register class with the most change in its pressure limit 910/// based on the tracker's current pressure, and return the number of excess 911/// register units of that pressure set introduced by this instruction. 912/// 913/// This assumes that the current LiveIn set is sufficient. 914void RegPressureTracker:: 915getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 916 ArrayRef<PressureChange> CriticalPSets, 917 ArrayRef<unsigned> MaxPressureLimit) { 918 // Snapshot Pressure. 919 std::vector<unsigned> SavedPressure = CurrSetPressure; 920 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 921 922 bumpDownwardPressure(MI); 923 924 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, 925 LiveThruPressure); 926 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 927 MaxPressureLimit, Delta); 928 assert(Delta.CriticalMax.getUnitInc() >= 0 && 929 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure"); 930 931 // Restore the tracker's state. 932 P.MaxSetPressure.swap(SavedMaxPressure); 933 CurrSetPressure.swap(SavedPressure); 934} 935 936/// Get the pressure of each PSet after traversing this instruction bottom-up. 937void RegPressureTracker:: 938getUpwardPressure(const MachineInstr *MI, 939 std::vector<unsigned> &PressureResult, 940 std::vector<unsigned> &MaxPressureResult) { 941 // Snapshot pressure. 942 PressureResult = CurrSetPressure; 943 MaxPressureResult = P.MaxSetPressure; 944 945 bumpUpwardPressure(MI); 946 947 // Current pressure becomes the result. Restore current pressure. 948 P.MaxSetPressure.swap(MaxPressureResult); 949 CurrSetPressure.swap(PressureResult); 950} 951 952/// Get the pressure of each PSet after traversing this instruction top-down. 953void RegPressureTracker:: 954getDownwardPressure(const MachineInstr *MI, 955 std::vector<unsigned> &PressureResult, 956 std::vector<unsigned> &MaxPressureResult) { 957 // Snapshot pressure. 958 PressureResult = CurrSetPressure; 959 MaxPressureResult = P.MaxSetPressure; 960 961 bumpDownwardPressure(MI); 962 963 // Current pressure becomes the result. Restore current pressure. 964 P.MaxSetPressure.swap(MaxPressureResult); 965 CurrSetPressure.swap(PressureResult); 966} 967