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