RegisterPressure.cpp revision 846b31d74aa673a178f57f9d47f366d8ddb756d3
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 PDiff.addPressureChange(RegOpers.Defs[i], true, MRI); 404 405 for (unsigned i = 0, e = RegOpers.Uses.size(); i != e; ++i) 406 PDiff.addPressureChange(RegOpers.Uses[i], false, MRI); 407} 408 409/// Force liveness of registers. 410void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) { 411 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 412 if (LiveRegs.insert(Regs[i])) 413 increaseRegPressure(Regs[i]); 414 } 415} 416 417/// Add Reg to the live in set and increase max pressure. 418void RegPressureTracker::discoverLiveIn(unsigned Reg) { 419 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 420 if (containsReg(P.LiveInRegs, Reg)) 421 return; 422 423 // At live in discovery, unconditionally increase the high water mark. 424 P.LiveInRegs.push_back(Reg); 425 increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); 426} 427 428/// Add Reg to the live out set and increase max pressure. 429void RegPressureTracker::discoverLiveOut(unsigned Reg) { 430 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 431 if (containsReg(P.LiveOutRegs, Reg)) 432 return; 433 434 // At live out discovery, unconditionally increase the high water mark. 435 P.LiveOutRegs.push_back(Reg); 436 increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); 437} 438 439/// Recede across the previous instruction. If LiveUses is provided, record any 440/// RegUnits that are made live by the current instruction's uses. This includes 441/// registers that are both defined and used by the instruction. If a pressure 442/// difference pointer is provided record the changes is pressure caused by this 443/// instruction independent of liveness. 444bool RegPressureTracker::recede(SmallVectorImpl<unsigned> *LiveUses, 445 PressureDiff *PDiff) { 446 // Check for the top of the analyzable region. 447 if (CurrPos == MBB->begin()) { 448 closeRegion(); 449 return false; 450 } 451 if (!isBottomClosed()) 452 closeBottom(); 453 454 // Open the top of the region using block iterators. 455 if (!RequireIntervals && isTopClosed()) 456 static_cast<RegionPressure&>(P).openTop(CurrPos); 457 458 // Find the previous instruction. 459 do 460 --CurrPos; 461 while (CurrPos != MBB->begin() && CurrPos->isDebugValue()); 462 463 if (CurrPos->isDebugValue()) { 464 closeRegion(); 465 return false; 466 } 467 SlotIndex SlotIdx; 468 if (RequireIntervals) 469 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); 470 471 // Open the top of the region using slot indexes. 472 if (RequireIntervals && isTopClosed()) 473 static_cast<IntervalPressure&>(P).openTop(SlotIdx); 474 475 RegisterOperands RegOpers(TRI, MRI); 476 collectOperands(CurrPos, RegOpers); 477 478 if (PDiff) 479 collectPDiff(*PDiff, RegOpers, MRI); 480 481 // Boost pressure for all dead defs together. 482 increaseRegPressure(RegOpers.DeadDefs); 483 decreaseRegPressure(RegOpers.DeadDefs); 484 485 // Kill liveness at live defs. 486 // TODO: consider earlyclobbers? 487 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 488 unsigned Reg = RegOpers.Defs[i]; 489 if (LiveRegs.erase(Reg)) 490 decreaseRegPressure(Reg); 491 else 492 discoverLiveOut(Reg); 493 } 494 495 // Generate liveness for uses. 496 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 497 unsigned Reg = RegOpers.Uses[i]; 498 if (!LiveRegs.contains(Reg)) { 499 // Adjust liveouts if LiveIntervals are available. 500 if (RequireIntervals) { 501 const LiveInterval *LI = getInterval(Reg); 502 // Check if this LR is killed and not redefined here. 503 if (LI) { 504 LiveRangeQuery LRQ(*LI, SlotIdx); 505 if (!LRQ.isKill() && !LRQ.valueDefined()) 506 discoverLiveOut(Reg); 507 } 508 } 509 increaseRegPressure(Reg); 510 LiveRegs.insert(Reg); 511 if (LiveUses && !containsReg(*LiveUses, Reg)) 512 LiveUses->push_back(Reg); 513 } 514 } 515 if (TrackUntiedDefs) { 516 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 517 unsigned Reg = RegOpers.Defs[i]; 518 if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg)) 519 UntiedDefs.insert(Reg); 520 } 521 } 522 return true; 523} 524 525/// Advance across the current instruction. 526bool RegPressureTracker::advance() { 527 assert(!TrackUntiedDefs && "unsupported mode"); 528 529 // Check for the bottom of the analyzable region. 530 if (CurrPos == MBB->end()) { 531 closeRegion(); 532 return false; 533 } 534 if (!isTopClosed()) 535 closeTop(); 536 537 SlotIndex SlotIdx; 538 if (RequireIntervals) 539 SlotIdx = getCurrSlot(); 540 541 // Open the bottom of the region using slot indexes. 542 if (isBottomClosed()) { 543 if (RequireIntervals) 544 static_cast<IntervalPressure&>(P).openBottom(SlotIdx); 545 else 546 static_cast<RegionPressure&>(P).openBottom(CurrPos); 547 } 548 549 RegisterOperands RegOpers(TRI, MRI); 550 collectOperands(CurrPos, RegOpers); 551 552 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 553 unsigned Reg = RegOpers.Uses[i]; 554 // Discover live-ins. 555 bool isLive = LiveRegs.contains(Reg); 556 if (!isLive) 557 discoverLiveIn(Reg); 558 // Kill liveness at last uses. 559 bool lastUse = false; 560 if (RequireIntervals) { 561 const LiveInterval *LI = getInterval(Reg); 562 lastUse = LI && LiveRangeQuery(*LI, SlotIdx).isKill(); 563 } 564 else { 565 // Allocatable physregs are always single-use before register rewriting. 566 lastUse = !TargetRegisterInfo::isVirtualRegister(Reg); 567 } 568 if (lastUse && isLive) { 569 LiveRegs.erase(Reg); 570 decreaseRegPressure(Reg); 571 } 572 else if (!lastUse && !isLive) 573 increaseRegPressure(Reg); 574 } 575 576 // Generate liveness for defs. 577 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 578 unsigned Reg = RegOpers.Defs[i]; 579 if (LiveRegs.insert(Reg)) 580 increaseRegPressure(Reg); 581 } 582 583 // Boost pressure for all dead defs together. 584 increaseRegPressure(RegOpers.DeadDefs); 585 decreaseRegPressure(RegOpers.DeadDefs); 586 587 // Find the next instruction. 588 do 589 ++CurrPos; 590 while (CurrPos != MBB->end() && CurrPos->isDebugValue()); 591 return true; 592} 593 594/// Find the max change in excess pressure across all sets. 595static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec, 596 ArrayRef<unsigned> NewPressureVec, 597 RegPressureDelta &Delta, 598 const RegisterClassInfo *RCI, 599 ArrayRef<unsigned> LiveThruPressureVec) { 600 Delta.Excess = PressureChange(); 601 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) { 602 unsigned POld = OldPressureVec[i]; 603 unsigned PNew = NewPressureVec[i]; 604 int PDiff = (int)PNew - (int)POld; 605 if (!PDiff) // No change in this set in the common case. 606 continue; 607 // Only consider change beyond the limit. 608 unsigned Limit = RCI->getRegPressureSetLimit(i); 609 if (!LiveThruPressureVec.empty()) 610 Limit += LiveThruPressureVec[i]; 611 612 if (Limit > POld) { 613 if (Limit > PNew) 614 PDiff = 0; // Under the limit 615 else 616 PDiff = PNew - Limit; // Just exceeded limit. 617 } 618 else if (Limit > PNew) 619 PDiff = Limit - POld; // Just obeyed limit. 620 621 if (PDiff) { 622 Delta.Excess = PressureChange(i); 623 Delta.Excess.setUnitInc(PDiff); 624 break; 625 } 626 } 627} 628 629/// Find the max change in max pressure that either surpasses a critical PSet 630/// limit or exceeds the current MaxPressureLimit. 631/// 632/// FIXME: comparing each element of the old and new MaxPressure vectors here is 633/// silly. It's done now to demonstrate the concept but will go away with a 634/// RegPressureTracker API change to work with pressure differences. 635static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec, 636 ArrayRef<unsigned> NewMaxPressureVec, 637 ArrayRef<PressureChange> CriticalPSets, 638 ArrayRef<unsigned> MaxPressureLimit, 639 RegPressureDelta &Delta) { 640 Delta.CriticalMax = PressureChange(); 641 Delta.CurrentMax = PressureChange(); 642 643 unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); 644 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) { 645 unsigned POld = OldMaxPressureVec[i]; 646 unsigned PNew = NewMaxPressureVec[i]; 647 if (PNew == POld) // No change in this set in the common case. 648 continue; 649 650 if (!Delta.CriticalMax.isValid()) { 651 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i) 652 ++CritIdx; 653 654 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) { 655 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc(); 656 if (PDiff > 0) { 657 Delta.CriticalMax = PressureChange(i); 658 Delta.CriticalMax.setUnitInc(PDiff); 659 } 660 } 661 } 662 // Find the first increase above MaxPressureLimit. 663 // (Ignores negative MDiff). 664 if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) { 665 Delta.CurrentMax = PressureChange(i); 666 Delta.CurrentMax.setUnitInc(PNew - POld); 667 if (CritIdx == CritEnd || Delta.CriticalMax.isValid()) 668 break; 669 } 670 } 671} 672 673/// Record the upward impact of a single instruction on current register 674/// pressure. Unlike the advance/recede pressure tracking interface, this does 675/// not discover live in/outs. 676/// 677/// This is intended for speculative queries. It leaves pressure inconsistent 678/// with the current position, so must be restored by the caller. 679void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) { 680 assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 681 682 // Account for register pressure similar to RegPressureTracker::recede(). 683 RegisterOperands RegOpers(TRI, MRI, /*IgnoreDead=*/true); 684 collectOperands(MI, RegOpers); 685 686 // Boost max pressure for all dead defs together. 687 // Since CurrSetPressure and MaxSetPressure 688 increaseRegPressure(RegOpers.DeadDefs); 689 decreaseRegPressure(RegOpers.DeadDefs); 690 691 // Kill liveness at live defs. 692 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 693 unsigned Reg = RegOpers.Defs[i]; 694 if (!containsReg(RegOpers.Uses, Reg)) 695 decreaseRegPressure(Reg); 696 } 697 // Generate liveness for uses. 698 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 699 unsigned Reg = RegOpers.Uses[i]; 700 if (!LiveRegs.contains(Reg)) 701 increaseRegPressure(Reg); 702 } 703} 704 705/// Consider the pressure increase caused by traversing this instruction 706/// bottom-up. Find the pressure set with the most change beyond its pressure 707/// limit based on the tracker's current pressure, and return the change in 708/// number of register units of that pressure set introduced by this 709/// instruction. 710/// 711/// This assumes that the current LiveOut set is sufficient. 712/// 713/// FIXME: This is expensive for an on-the-fly query. We need to cache the 714/// result per-SUnit with enough information to adjust for the current 715/// scheduling position. But this works as a proof of concept. 716void RegPressureTracker:: 717getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, 718 RegPressureDelta &Delta, 719 ArrayRef<PressureChange> CriticalPSets, 720 ArrayRef<unsigned> MaxPressureLimit) { 721 // Snapshot Pressure. 722 // FIXME: The snapshot heap space should persist. But I'm planning to 723 // summarize the pressure effect so we don't need to snapshot at all. 724 std::vector<unsigned> SavedPressure = CurrSetPressure; 725 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 726 727 bumpUpwardPressure(MI); 728 729 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, 730 LiveThruPressure); 731 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 732 MaxPressureLimit, Delta); 733 assert(Delta.CriticalMax.getUnitInc() >= 0 && 734 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure"); 735 736 // Restore the tracker's state. 737 P.MaxSetPressure.swap(SavedMaxPressure); 738 CurrSetPressure.swap(SavedPressure); 739 740#ifndef NDEBUG 741 if (!PDiff) 742 return; 743 744 // Check if the alternate algorithm yields the same result. 745 RegPressureDelta Delta2; 746 getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit); 747 if (Delta != Delta2) { 748 dbgs() << "DELTA: " << *MI; 749 if (Delta.Excess.isValid()) 750 dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet()) 751 << " " << Delta.Excess.getUnitInc() << "\n"; 752 if (Delta.CriticalMax.isValid()) 753 dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet()) 754 << " " << Delta.CriticalMax.getUnitInc() << "\n"; 755 if (Delta.CurrentMax.isValid()) 756 dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet()) 757 << " " << Delta.CurrentMax.getUnitInc() << "\n"; 758 if (Delta2.Excess.isValid()) 759 dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet()) 760 << " " << Delta2.Excess.getUnitInc() << "\n"; 761 if (Delta2.CriticalMax.isValid()) 762 dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet()) 763 << " " << Delta2.CriticalMax.getUnitInc() << "\n"; 764 if (Delta2.CurrentMax.isValid()) 765 dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet()) 766 << " " << Delta2.CurrentMax.getUnitInc() << "\n"; 767 llvm_unreachable("RegP Delta Mismatch"); 768 } 769#endif 770} 771 772/// This is a prototype of the fast version of querying register pressure that 773/// does not directly depend on current liveness. It's still slow because we 774/// recompute pressure change on-the-fly. This implementation only exists to 775/// prove correctness. 776/// 777/// @param Delta captures information needed for heuristics. 778/// 779/// @param CriticalPSets Are the pressure sets that are known to exceed some 780/// limit within the region, not necessarily at the current position. 781/// 782/// @param MaxPressureLimit Is the max pressure within the region, not 783/// necessarily at the current position. 784void RegPressureTracker:: 785getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff, 786 RegPressureDelta &Delta, 787 ArrayRef<PressureChange> CriticalPSets, 788 ArrayRef<unsigned> MaxPressureLimit) const { 789 unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); 790 for (PressureDiff::const_iterator 791 PDiffI = PDiff.begin(), PDiffE = PDiff.end(); 792 PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) { 793 794 unsigned PSetID = PDiffI->getPSet(); 795 unsigned Limit = RCI->getRegPressureSetLimit(PSetID); 796 if (!LiveThruPressure.empty()) 797 Limit += LiveThruPressure[PSetID]; 798 799 unsigned POld = CurrSetPressure[PSetID]; 800 unsigned MOld = P.MaxSetPressure[PSetID]; 801 unsigned MNew = MOld; 802 // Ignore DeadDefs here because they aren't captured by PressureChange. 803 unsigned PNew = POld + PDiffI->getUnitInc(); 804 assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld) && "PSet overflow"); 805 if (PNew > MOld) 806 MNew = PNew; 807 // Check if current pressure has exceeded the limit. 808 if (!Delta.Excess.isValid()) { 809 unsigned ExcessInc = 0; 810 if (PNew > Limit) 811 ExcessInc = POld > Limit ? PNew - POld : PNew - Limit; 812 else if (POld > Limit) 813 ExcessInc = Limit - POld; 814 if (ExcessInc) { 815 Delta.Excess = PressureChange(PSetID); 816 Delta.Excess.setUnitInc(ExcessInc); 817 } 818 } 819 // Check if max pressure has exceeded a critical pressure set max. 820 if (MNew == MOld) 821 continue; 822 if (!Delta.CriticalMax.isValid()) { 823 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID) 824 ++CritIdx; 825 826 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) { 827 int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc(); 828 if (CritInc > 0 && CritInc <= INT16_MAX) { 829 Delta.CriticalMax = PressureChange(PSetID); 830 Delta.CriticalMax.setUnitInc(CritInc); 831 } 832 } 833 } 834 // Check if max pressure has exceeded the current max. 835 if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) { 836 Delta.CurrentMax = PressureChange(PSetID); 837 Delta.CurrentMax.setUnitInc(MNew - MOld); 838 } 839 } 840} 841 842/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx). 843static bool findUseBetween(unsigned Reg, 844 SlotIndex PriorUseIdx, SlotIndex NextUseIdx, 845 const MachineRegisterInfo *MRI, 846 const LiveIntervals *LIS) { 847 for (MachineRegisterInfo::use_nodbg_iterator 848 UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end(); 849 UI != UE; UI.skipInstruction()) { 850 const MachineInstr* MI = &*UI; 851 if (MI->isDebugValue()) 852 continue; 853 SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot(); 854 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) 855 return true; 856 } 857 return false; 858} 859 860/// Record the downward impact of a single instruction on current register 861/// pressure. Unlike the advance/recede pressure tracking interface, this does 862/// not discover live in/outs. 863/// 864/// This is intended for speculative queries. It leaves pressure inconsistent 865/// with the current position, so must be restored by the caller. 866void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) { 867 assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 868 869 // Account for register pressure similar to RegPressureTracker::recede(). 870 RegisterOperands RegOpers(TRI, MRI); 871 collectOperands(MI, RegOpers); 872 873 // Kill liveness at last uses. Assume allocatable physregs are single-use 874 // rather than checking LiveIntervals. 875 SlotIndex SlotIdx; 876 if (RequireIntervals) 877 SlotIdx = LIS->getInstructionIndex(MI).getRegSlot(); 878 879 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 880 unsigned Reg = RegOpers.Uses[i]; 881 if (RequireIntervals) { 882 // FIXME: allow the caller to pass in the list of vreg uses that remain 883 // to be bottom-scheduled to avoid searching uses at each query. 884 SlotIndex CurrIdx = getCurrSlot(); 885 const LiveInterval *LI = getInterval(Reg); 886 if (LI) { 887 LiveRangeQuery LRQ(*LI, SlotIdx); 888 if (LRQ.isKill() && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) 889 decreaseRegPressure(Reg); 890 } 891 } 892 else if (!TargetRegisterInfo::isVirtualRegister(Reg)) { 893 // Allocatable physregs are always single-use before register rewriting. 894 decreaseRegPressure(Reg); 895 } 896 } 897 898 // Generate liveness for defs. 899 increaseRegPressure(RegOpers.Defs); 900 901 // Boost pressure for all dead defs together. 902 increaseRegPressure(RegOpers.DeadDefs); 903 decreaseRegPressure(RegOpers.DeadDefs); 904} 905 906/// Consider the pressure increase caused by traversing this instruction 907/// top-down. Find the register class with the most change in its pressure limit 908/// based on the tracker's current pressure, and return the number of excess 909/// register units of that pressure set introduced by this instruction. 910/// 911/// This assumes that the current LiveIn set is sufficient. 912void RegPressureTracker:: 913getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 914 ArrayRef<PressureChange> CriticalPSets, 915 ArrayRef<unsigned> MaxPressureLimit) { 916 // Snapshot Pressure. 917 std::vector<unsigned> SavedPressure = CurrSetPressure; 918 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 919 920 bumpDownwardPressure(MI); 921 922 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, 923 LiveThruPressure); 924 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 925 MaxPressureLimit, Delta); 926 assert(Delta.CriticalMax.getUnitInc() >= 0 && 927 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure"); 928 929 // Restore the tracker's state. 930 P.MaxSetPressure.swap(SavedMaxPressure); 931 CurrSetPressure.swap(SavedPressure); 932} 933 934/// Get the pressure of each PSet after traversing this instruction bottom-up. 935void RegPressureTracker:: 936getUpwardPressure(const MachineInstr *MI, 937 std::vector<unsigned> &PressureResult, 938 std::vector<unsigned> &MaxPressureResult) { 939 // Snapshot pressure. 940 PressureResult = CurrSetPressure; 941 MaxPressureResult = P.MaxSetPressure; 942 943 bumpUpwardPressure(MI); 944 945 // Current pressure becomes the result. Restore current pressure. 946 P.MaxSetPressure.swap(MaxPressureResult); 947 CurrSetPressure.swap(PressureResult); 948} 949 950/// Get the pressure of each PSet after traversing this instruction top-down. 951void RegPressureTracker:: 952getDownwardPressure(const MachineInstr *MI, 953 std::vector<unsigned> &PressureResult, 954 std::vector<unsigned> &MaxPressureResult) { 955 // Snapshot pressure. 956 PressureResult = CurrSetPressure; 957 MaxPressureResult = P.MaxSetPressure; 958 959 bumpDownwardPressure(MI); 960 961 // Current pressure becomes the result. Restore current pressure. 962 P.MaxSetPressure.swap(MaxPressureResult); 963 CurrSetPressure.swap(PressureResult); 964} 965