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 std::vector<unsigned> &MaxSetPressure, 29 const int *PSet, unsigned Weight) { 30 for (; *PSet != -1; ++PSet) { 31 CurrSetPressure[*PSet] += Weight; 32 if (&CurrSetPressure != &MaxSetPressure 33 && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) { 34 MaxSetPressure[*PSet] = CurrSetPressure[*PSet]; 35 } 36 } 37} 38 39/// Decrease pressure for each pressure set provided by TargetRegisterInfo. 40static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure, 41 const int *PSet, unsigned Weight) { 42 for (; *PSet != -1; ++PSet) { 43 assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow"); 44 CurrSetPressure[*PSet] -= Weight; 45 } 46} 47 48/// Directly increase pressure only within this RegisterPressure result. 49void RegisterPressure::increase(unsigned Reg, const TargetRegisterInfo *TRI, 50 const MachineRegisterInfo *MRI) { 51 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 52 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 53 increaseSetPressure(MaxSetPressure, MaxSetPressure, 54 TRI->getRegClassPressureSets(RC), 55 TRI->getRegClassWeight(RC).RegWeight); 56 } 57 else { 58 increaseSetPressure(MaxSetPressure, MaxSetPressure, 59 TRI->getRegUnitPressureSets(Reg), 60 TRI->getRegUnitWeight(Reg)); 61 } 62} 63 64/// Directly decrease pressure only within this RegisterPressure result. 65void RegisterPressure::decrease(unsigned Reg, const TargetRegisterInfo *TRI, 66 const MachineRegisterInfo *MRI) { 67 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 68 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 69 decreaseSetPressure(MaxSetPressure, TRI->getRegClassPressureSets(RC), 70 TRI->getRegClassWeight(RC).RegWeight); 71 } 72 else { 73 decreaseSetPressure(MaxSetPressure, TRI->getRegUnitPressureSets(Reg), 74 TRI->getRegUnitWeight(Reg)); 75 } 76} 77 78#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 79static void dumpSetPressure(const std::vector<unsigned> &SetPressure, 80 const TargetRegisterInfo *TRI) { 81 for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) { 82 if (SetPressure[i] != 0) 83 dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n'; 84 } 85} 86 87void RegisterPressure::dump(const TargetRegisterInfo *TRI) const { 88 dbgs() << "Max Pressure: "; 89 dumpSetPressure(MaxSetPressure, TRI); 90 dbgs() << "Live In: "; 91 for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i) 92 dbgs() << PrintReg(LiveInRegs[i], TRI) << " "; 93 dbgs() << '\n'; 94 dbgs() << "Live Out: "; 95 for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i) 96 dbgs() << PrintReg(LiveOutRegs[i], TRI) << " "; 97 dbgs() << '\n'; 98} 99 100void RegPressureTracker::dump() const { 101 dbgs() << "Curr Pressure: "; 102 dumpSetPressure(CurrSetPressure, TRI); 103 P.dump(TRI); 104} 105#endif 106 107/// Increase the current pressure as impacted by these registers and bump 108/// the high water mark if needed. 109void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> Regs) { 110 for (unsigned I = 0, E = Regs.size(); I != E; ++I) { 111 if (TargetRegisterInfo::isVirtualRegister(Regs[I])) { 112 const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]); 113 increaseSetPressure(CurrSetPressure, P.MaxSetPressure, 114 TRI->getRegClassPressureSets(RC), 115 TRI->getRegClassWeight(RC).RegWeight); 116 } 117 else { 118 increaseSetPressure(CurrSetPressure, P.MaxSetPressure, 119 TRI->getRegUnitPressureSets(Regs[I]), 120 TRI->getRegUnitWeight(Regs[I])); 121 } 122 } 123} 124 125/// Simply decrease the current pressure as impacted by these registers. 126void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> Regs) { 127 for (unsigned I = 0, E = Regs.size(); I != E; ++I) { 128 if (TargetRegisterInfo::isVirtualRegister(Regs[I])) { 129 const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]); 130 decreaseSetPressure(CurrSetPressure, 131 TRI->getRegClassPressureSets(RC), 132 TRI->getRegClassWeight(RC).RegWeight); 133 } 134 else { 135 decreaseSetPressure(CurrSetPressure, TRI->getRegUnitPressureSets(Regs[I]), 136 TRI->getRegUnitWeight(Regs[I])); 137 } 138 } 139} 140 141/// Clear the result so it can be used for another round of pressure tracking. 142void IntervalPressure::reset() { 143 TopIdx = BottomIdx = SlotIndex(); 144 MaxSetPressure.clear(); 145 LiveInRegs.clear(); 146 LiveOutRegs.clear(); 147} 148 149/// Clear the result so it can be used for another round of pressure tracking. 150void RegionPressure::reset() { 151 TopPos = BottomPos = MachineBasicBlock::const_iterator(); 152 MaxSetPressure.clear(); 153 LiveInRegs.clear(); 154 LiveOutRegs.clear(); 155} 156 157/// If the current top is not less than or equal to the next index, open it. 158/// We happen to need the SlotIndex for the next top for pressure update. 159void IntervalPressure::openTop(SlotIndex NextTop) { 160 if (TopIdx <= NextTop) 161 return; 162 TopIdx = SlotIndex(); 163 LiveInRegs.clear(); 164} 165 166/// If the current top is the previous instruction (before receding), open it. 167void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) { 168 if (TopPos != PrevTop) 169 return; 170 TopPos = MachineBasicBlock::const_iterator(); 171 LiveInRegs.clear(); 172} 173 174/// If the current bottom is not greater than the previous index, open it. 175void IntervalPressure::openBottom(SlotIndex PrevBottom) { 176 if (BottomIdx > PrevBottom) 177 return; 178 BottomIdx = SlotIndex(); 179 LiveInRegs.clear(); 180} 181 182/// If the current bottom is the previous instr (before advancing), open it. 183void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) { 184 if (BottomPos != PrevBottom) 185 return; 186 BottomPos = MachineBasicBlock::const_iterator(); 187 LiveInRegs.clear(); 188} 189 190const LiveInterval *RegPressureTracker::getInterval(unsigned Reg) const { 191 if (TargetRegisterInfo::isVirtualRegister(Reg)) 192 return &LIS->getInterval(Reg); 193 return LIS->getCachedRegUnit(Reg); 194} 195 196/// Setup the RegPressureTracker. 197/// 198/// TODO: Add support for pressure without LiveIntervals. 199void RegPressureTracker::init(const MachineFunction *mf, 200 const RegisterClassInfo *rci, 201 const LiveIntervals *lis, 202 const MachineBasicBlock *mbb, 203 MachineBasicBlock::const_iterator pos) 204{ 205 MF = mf; 206 TRI = MF->getTarget().getRegisterInfo(); 207 RCI = rci; 208 MRI = &MF->getRegInfo(); 209 MBB = mbb; 210 211 if (RequireIntervals) { 212 assert(lis && "IntervalPressure requires LiveIntervals"); 213 LIS = lis; 214 } 215 216 CurrPos = pos; 217 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0); 218 219 if (RequireIntervals) 220 static_cast<IntervalPressure&>(P).reset(); 221 else 222 static_cast<RegionPressure&>(P).reset(); 223 P.MaxSetPressure = CurrSetPressure; 224 225 LiveRegs.PhysRegs.clear(); 226 LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs()); 227 LiveRegs.VirtRegs.clear(); 228 LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs()); 229} 230 231/// Does this pressure result have a valid top position and live ins. 232bool RegPressureTracker::isTopClosed() const { 233 if (RequireIntervals) 234 return static_cast<IntervalPressure&>(P).TopIdx.isValid(); 235 return (static_cast<RegionPressure&>(P).TopPos == 236 MachineBasicBlock::const_iterator()); 237} 238 239/// Does this pressure result have a valid bottom position and live outs. 240bool RegPressureTracker::isBottomClosed() const { 241 if (RequireIntervals) 242 return static_cast<IntervalPressure&>(P).BottomIdx.isValid(); 243 return (static_cast<RegionPressure&>(P).BottomPos == 244 MachineBasicBlock::const_iterator()); 245} 246 247 248SlotIndex RegPressureTracker::getCurrSlot() const { 249 MachineBasicBlock::const_iterator IdxPos = CurrPos; 250 while (IdxPos != MBB->end() && IdxPos->isDebugValue()) 251 ++IdxPos; 252 if (IdxPos == MBB->end()) 253 return LIS->getMBBEndIdx(MBB); 254 return LIS->getInstructionIndex(IdxPos).getRegSlot(); 255} 256 257/// Set the boundary for the top of the region and summarize live ins. 258void RegPressureTracker::closeTop() { 259 if (RequireIntervals) 260 static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot(); 261 else 262 static_cast<RegionPressure&>(P).TopPos = CurrPos; 263 264 assert(P.LiveInRegs.empty() && "inconsistent max pressure result"); 265 P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); 266 P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); 267 for (SparseSet<unsigned>::const_iterator I = 268 LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) 269 P.LiveInRegs.push_back(*I); 270 std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end()); 271 P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()), 272 P.LiveInRegs.end()); 273} 274 275/// Set the boundary for the bottom of the region and summarize live outs. 276void RegPressureTracker::closeBottom() { 277 if (RequireIntervals) 278 static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot(); 279 else 280 static_cast<RegionPressure&>(P).BottomPos = CurrPos; 281 282 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result"); 283 P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); 284 P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); 285 for (SparseSet<unsigned>::const_iterator I = 286 LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) 287 P.LiveOutRegs.push_back(*I); 288 std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end()); 289 P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()), 290 P.LiveOutRegs.end()); 291} 292 293/// Finalize the region boundaries and record live ins and live outs. 294void RegPressureTracker::closeRegion() { 295 if (!isTopClosed() && !isBottomClosed()) { 296 assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() && 297 "no region boundary"); 298 return; 299 } 300 if (!isBottomClosed()) 301 closeBottom(); 302 else if (!isTopClosed()) 303 closeTop(); 304 // If both top and bottom are closed, do nothing. 305} 306 307/// \brief Convenient wrapper for checking membership in RegisterOperands. 308static bool containsReg(ArrayRef<unsigned> Regs, unsigned Reg) { 309 return std::find(Regs.begin(), Regs.end(), Reg) != Regs.end(); 310} 311 312/// Collect this instruction's unique uses and defs into SmallVectors for 313/// processing defs and uses in order. 314class RegisterOperands { 315 const TargetRegisterInfo *TRI; 316 const MachineRegisterInfo *MRI; 317 318public: 319 SmallVector<unsigned, 8> Uses; 320 SmallVector<unsigned, 8> Defs; 321 SmallVector<unsigned, 8> DeadDefs; 322 323 RegisterOperands(const TargetRegisterInfo *tri, 324 const MachineRegisterInfo *mri): TRI(tri), MRI(mri) {} 325 326 /// Push this operand's register onto the correct vector. 327 void collect(const MachineOperand &MO) { 328 if (!MO.isReg() || !MO.getReg()) 329 return; 330 if (MO.readsReg()) 331 pushRegUnits(MO.getReg(), Uses); 332 if (MO.isDef()) { 333 if (MO.isDead()) 334 pushRegUnits(MO.getReg(), DeadDefs); 335 else 336 pushRegUnits(MO.getReg(), Defs); 337 } 338 } 339 340protected: 341 void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &Regs) { 342 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 343 if (containsReg(Regs, Reg)) 344 return; 345 Regs.push_back(Reg); 346 } 347 else if (MRI->isAllocatable(Reg)) { 348 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 349 if (containsReg(Regs, *Units)) 350 continue; 351 Regs.push_back(*Units); 352 } 353 } 354 } 355}; 356 357/// Collect physical and virtual register operands. 358static void collectOperands(const MachineInstr *MI, 359 RegisterOperands &RegOpers) { 360 for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) 361 RegOpers.collect(*OperI); 362 363 // Remove redundant physreg dead defs. 364 SmallVectorImpl<unsigned>::iterator I = 365 std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(), 366 std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs)); 367 RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end()); 368} 369 370/// Force liveness of registers. 371void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) { 372 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 373 if (LiveRegs.insert(Regs[i])) 374 increaseRegPressure(Regs[i]); 375 } 376} 377 378/// Add Reg to the live in set and increase max pressure. 379void RegPressureTracker::discoverLiveIn(unsigned Reg) { 380 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 381 if (containsReg(P.LiveInRegs, Reg)) 382 return; 383 384 // At live in discovery, unconditionally increase the high water mark. 385 P.LiveInRegs.push_back(Reg); 386 P.increase(Reg, TRI, MRI); 387} 388 389/// Add Reg to the live out set and increase max pressure. 390void RegPressureTracker::discoverLiveOut(unsigned Reg) { 391 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 392 if (containsReg(P.LiveOutRegs, Reg)) 393 return; 394 395 // At live out discovery, unconditionally increase the high water mark. 396 P.LiveOutRegs.push_back(Reg); 397 P.increase(Reg, TRI, MRI); 398} 399 400/// Recede across the previous instruction. 401bool RegPressureTracker::recede() { 402 // Check for the top of the analyzable region. 403 if (CurrPos == MBB->begin()) { 404 closeRegion(); 405 return false; 406 } 407 if (!isBottomClosed()) 408 closeBottom(); 409 410 // Open the top of the region using block iterators. 411 if (!RequireIntervals && isTopClosed()) 412 static_cast<RegionPressure&>(P).openTop(CurrPos); 413 414 // Find the previous instruction. 415 do 416 --CurrPos; 417 while (CurrPos != MBB->begin() && CurrPos->isDebugValue()); 418 419 if (CurrPos->isDebugValue()) { 420 closeRegion(); 421 return false; 422 } 423 SlotIndex SlotIdx; 424 if (RequireIntervals) 425 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); 426 427 // Open the top of the region using slot indexes. 428 if (RequireIntervals && isTopClosed()) 429 static_cast<IntervalPressure&>(P).openTop(SlotIdx); 430 431 RegisterOperands RegOpers(TRI, MRI); 432 collectOperands(CurrPos, RegOpers); 433 434 // Boost pressure for all dead defs together. 435 increaseRegPressure(RegOpers.DeadDefs); 436 decreaseRegPressure(RegOpers.DeadDefs); 437 438 // Kill liveness at live defs. 439 // TODO: consider earlyclobbers? 440 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 441 unsigned Reg = RegOpers.Defs[i]; 442 if (LiveRegs.erase(Reg)) 443 decreaseRegPressure(Reg); 444 else 445 discoverLiveOut(Reg); 446 } 447 448 // Generate liveness for uses. 449 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 450 unsigned Reg = RegOpers.Uses[i]; 451 if (!LiveRegs.contains(Reg)) { 452 // Adjust liveouts if LiveIntervals are available. 453 if (RequireIntervals) { 454 const LiveInterval *LI = getInterval(Reg); 455 if (LI && !LI->killedAt(SlotIdx)) 456 discoverLiveOut(Reg); 457 } 458 increaseRegPressure(Reg); 459 LiveRegs.insert(Reg); 460 } 461 } 462 return true; 463} 464 465/// Advance across the current instruction. 466bool RegPressureTracker::advance() { 467 // Check for the bottom of the analyzable region. 468 if (CurrPos == MBB->end()) { 469 closeRegion(); 470 return false; 471 } 472 if (!isTopClosed()) 473 closeTop(); 474 475 SlotIndex SlotIdx; 476 if (RequireIntervals) 477 SlotIdx = getCurrSlot(); 478 479 // Open the bottom of the region using slot indexes. 480 if (isBottomClosed()) { 481 if (RequireIntervals) 482 static_cast<IntervalPressure&>(P).openBottom(SlotIdx); 483 else 484 static_cast<RegionPressure&>(P).openBottom(CurrPos); 485 } 486 487 RegisterOperands RegOpers(TRI, MRI); 488 collectOperands(CurrPos, RegOpers); 489 490 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 491 unsigned Reg = RegOpers.Uses[i]; 492 // Discover live-ins. 493 bool isLive = LiveRegs.contains(Reg); 494 if (!isLive) 495 discoverLiveIn(Reg); 496 // Kill liveness at last uses. 497 bool lastUse = false; 498 if (RequireIntervals) { 499 const LiveInterval *LI = getInterval(Reg); 500 lastUse = LI && LI->killedAt(SlotIdx); 501 } 502 else { 503 // Allocatable physregs are always single-use before register rewriting. 504 lastUse = !TargetRegisterInfo::isVirtualRegister(Reg); 505 } 506 if (lastUse && isLive) { 507 LiveRegs.erase(Reg); 508 decreaseRegPressure(Reg); 509 } 510 else if (!lastUse && !isLive) 511 increaseRegPressure(Reg); 512 } 513 514 // Generate liveness for defs. 515 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 516 unsigned Reg = RegOpers.Defs[i]; 517 if (LiveRegs.insert(Reg)) 518 increaseRegPressure(Reg); 519 } 520 521 // Boost pressure for all dead defs together. 522 increaseRegPressure(RegOpers.DeadDefs); 523 decreaseRegPressure(RegOpers.DeadDefs); 524 525 // Find the next instruction. 526 do 527 ++CurrPos; 528 while (CurrPos != MBB->end() && CurrPos->isDebugValue()); 529 return true; 530} 531 532/// Find the max change in excess pressure across all sets. 533static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec, 534 ArrayRef<unsigned> NewPressureVec, 535 RegPressureDelta &Delta, 536 const TargetRegisterInfo *TRI) { 537 int ExcessUnits = 0; 538 unsigned PSetID = ~0U; 539 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) { 540 unsigned POld = OldPressureVec[i]; 541 unsigned PNew = NewPressureVec[i]; 542 int PDiff = (int)PNew - (int)POld; 543 if (!PDiff) // No change in this set in the common case. 544 continue; 545 // Only consider change beyond the limit. 546 unsigned Limit = TRI->getRegPressureSetLimit(i); 547 if (Limit > POld) { 548 if (Limit > PNew) 549 PDiff = 0; // Under the limit 550 else 551 PDiff = PNew - Limit; // Just exceeded limit. 552 } 553 else if (Limit > PNew) 554 PDiff = Limit - POld; // Just obeyed limit. 555 556 if (std::abs(PDiff) > std::abs(ExcessUnits)) { 557 ExcessUnits = PDiff; 558 PSetID = i; 559 } 560 } 561 Delta.Excess.PSetID = PSetID; 562 Delta.Excess.UnitIncrease = ExcessUnits; 563} 564 565/// Find the max change in max pressure that either surpasses a critical PSet 566/// limit or exceeds the current MaxPressureLimit. 567/// 568/// FIXME: comparing each element of the old and new MaxPressure vectors here is 569/// silly. It's done now to demonstrate the concept but will go away with a 570/// RegPressureTracker API change to work with pressure differences. 571static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec, 572 ArrayRef<unsigned> NewMaxPressureVec, 573 ArrayRef<PressureElement> CriticalPSets, 574 ArrayRef<unsigned> MaxPressureLimit, 575 RegPressureDelta &Delta) { 576 Delta.CriticalMax = PressureElement(); 577 Delta.CurrentMax = PressureElement(); 578 579 unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); 580 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) { 581 unsigned POld = OldMaxPressureVec[i]; 582 unsigned PNew = NewMaxPressureVec[i]; 583 if (PNew == POld) // No change in this set in the common case. 584 continue; 585 586 while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i) 587 ++CritIdx; 588 589 if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) { 590 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease; 591 if (PDiff > Delta.CriticalMax.UnitIncrease) { 592 Delta.CriticalMax.PSetID = i; 593 Delta.CriticalMax.UnitIncrease = PDiff; 594 } 595 } 596 597 // Find the greatest increase above MaxPressureLimit. 598 // (Ignores negative MDiff). 599 int MDiff = (int)PNew - (int)MaxPressureLimit[i]; 600 if (MDiff > Delta.CurrentMax.UnitIncrease) { 601 Delta.CurrentMax.PSetID = i; 602 Delta.CurrentMax.UnitIncrease = PNew; 603 } 604 } 605} 606 607/// Record the upward impact of a single instruction on current register 608/// pressure. Unlike the advance/recede pressure tracking interface, this does 609/// not discover live in/outs. 610/// 611/// This is intended for speculative queries. It leaves pressure inconsistent 612/// with the current position, so must be restored by the caller. 613void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) { 614 assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 615 616 // Account for register pressure similar to RegPressureTracker::recede(). 617 RegisterOperands RegOpers(TRI, MRI); 618 collectOperands(MI, RegOpers); 619 620 // Boost max pressure for all dead defs together. 621 // Since CurrSetPressure and MaxSetPressure 622 increaseRegPressure(RegOpers.DeadDefs); 623 decreaseRegPressure(RegOpers.DeadDefs); 624 625 // Kill liveness at live defs. 626 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 627 unsigned Reg = RegOpers.Defs[i]; 628 if (!containsReg(RegOpers.Uses, Reg)) 629 decreaseRegPressure(Reg); 630 } 631 // Generate liveness for uses. 632 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 633 unsigned Reg = RegOpers.Uses[i]; 634 if (!LiveRegs.contains(Reg)) 635 increaseRegPressure(Reg); 636 } 637} 638 639/// Consider the pressure increase caused by traversing this instruction 640/// bottom-up. Find the pressure set with the most change beyond its pressure 641/// limit based on the tracker's current pressure, and return the change in 642/// number of register units of that pressure set introduced by this 643/// instruction. 644/// 645/// This assumes that the current LiveOut set is sufficient. 646/// 647/// FIXME: This is expensive for an on-the-fly query. We need to cache the 648/// result per-SUnit with enough information to adjust for the current 649/// scheduling position. But this works as a proof of concept. 650void RegPressureTracker:: 651getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 652 ArrayRef<PressureElement> CriticalPSets, 653 ArrayRef<unsigned> MaxPressureLimit) { 654 // Snapshot Pressure. 655 // FIXME: The snapshot heap space should persist. But I'm planning to 656 // summarize the pressure effect so we don't need to snapshot at all. 657 std::vector<unsigned> SavedPressure = CurrSetPressure; 658 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 659 660 bumpUpwardPressure(MI); 661 662 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI); 663 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 664 MaxPressureLimit, Delta); 665 assert(Delta.CriticalMax.UnitIncrease >= 0 && 666 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure"); 667 668 // Restore the tracker's state. 669 P.MaxSetPressure.swap(SavedMaxPressure); 670 CurrSetPressure.swap(SavedPressure); 671} 672 673/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx). 674static bool findUseBetween(unsigned Reg, 675 SlotIndex PriorUseIdx, SlotIndex NextUseIdx, 676 const MachineRegisterInfo *MRI, 677 const LiveIntervals *LIS) { 678 for (MachineRegisterInfo::use_nodbg_iterator 679 UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end(); 680 UI != UE; UI.skipInstruction()) { 681 const MachineInstr* MI = &*UI; 682 if (MI->isDebugValue()) 683 continue; 684 SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot(); 685 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) 686 return true; 687 } 688 return false; 689} 690 691/// Record the downward impact of a single instruction on current register 692/// pressure. Unlike the advance/recede pressure tracking interface, this does 693/// not discover live in/outs. 694/// 695/// This is intended for speculative queries. It leaves pressure inconsistent 696/// with the current position, so must be restored by the caller. 697void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) { 698 assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 699 700 // Account for register pressure similar to RegPressureTracker::recede(). 701 RegisterOperands RegOpers(TRI, MRI); 702 collectOperands(MI, RegOpers); 703 704 // Kill liveness at last uses. Assume allocatable physregs are single-use 705 // rather than checking LiveIntervals. 706 SlotIndex SlotIdx; 707 if (RequireIntervals) 708 SlotIdx = LIS->getInstructionIndex(MI).getRegSlot(); 709 710 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 711 unsigned Reg = RegOpers.Uses[i]; 712 if (RequireIntervals) { 713 // FIXME: allow the caller to pass in the list of vreg uses that remain 714 // to be bottom-scheduled to avoid searching uses at each query. 715 SlotIndex CurrIdx = getCurrSlot(); 716 const LiveInterval *LI = getInterval(Reg); 717 if (LI && LI->killedAt(SlotIdx) 718 && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) { 719 decreaseRegPressure(Reg); 720 } 721 } 722 else if (!TargetRegisterInfo::isVirtualRegister(Reg)) { 723 // Allocatable physregs are always single-use before register rewriting. 724 decreaseRegPressure(Reg); 725 } 726 } 727 728 // Generate liveness for defs. 729 increaseRegPressure(RegOpers.Defs); 730 731 // Boost pressure for all dead defs together. 732 increaseRegPressure(RegOpers.DeadDefs); 733 decreaseRegPressure(RegOpers.DeadDefs); 734} 735 736/// Consider the pressure increase caused by traversing this instruction 737/// top-down. Find the register class with the most change in its pressure limit 738/// based on the tracker's current pressure, and return the number of excess 739/// register units of that pressure set introduced by this instruction. 740/// 741/// This assumes that the current LiveIn set is sufficient. 742void RegPressureTracker:: 743getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 744 ArrayRef<PressureElement> CriticalPSets, 745 ArrayRef<unsigned> MaxPressureLimit) { 746 // Snapshot Pressure. 747 std::vector<unsigned> SavedPressure = CurrSetPressure; 748 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 749 750 bumpDownwardPressure(MI); 751 752 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI); 753 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 754 MaxPressureLimit, Delta); 755 assert(Delta.CriticalMax.UnitIncrease >= 0 && 756 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure"); 757 758 // Restore the tracker's state. 759 P.MaxSetPressure.swap(SavedMaxPressure); 760 CurrSetPressure.swap(SavedPressure); 761} 762 763/// Get the pressure of each PSet after traversing this instruction bottom-up. 764void RegPressureTracker:: 765getUpwardPressure(const MachineInstr *MI, 766 std::vector<unsigned> &PressureResult, 767 std::vector<unsigned> &MaxPressureResult) { 768 // Snapshot pressure. 769 PressureResult = CurrSetPressure; 770 MaxPressureResult = P.MaxSetPressure; 771 772 bumpUpwardPressure(MI); 773 774 // Current pressure becomes the result. Restore current pressure. 775 P.MaxSetPressure.swap(MaxPressureResult); 776 CurrSetPressure.swap(PressureResult); 777} 778 779/// Get the pressure of each PSet after traversing this instruction top-down. 780void RegPressureTracker:: 781getDownwardPressure(const MachineInstr *MI, 782 std::vector<unsigned> &PressureResult, 783 std::vector<unsigned> &MaxPressureResult) { 784 // Snapshot pressure. 785 PressureResult = CurrSetPressure; 786 MaxPressureResult = P.MaxSetPressure; 787 788 bumpDownwardPressure(MI); 789 790 // Current pressure becomes the result. Restore current pressure. 791 P.MaxSetPressure.swap(MaxPressureResult); 792 CurrSetPressure.swap(PressureResult); 793} 794