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 24 using namespace llvm; 25 26 /// Increase pressure for each pressure set provided by TargetRegisterInfo. 27 static 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. 40 static 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. 49 void 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. 65 void 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) 79 static 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 87 void 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 100 void 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. 109 void 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. 126 void 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. 142 void 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. 150 void 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. 159 void 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. 167 void 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. 175 void 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. 183 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) { 184 if (BottomPos != PrevBottom) 185 return; 186 BottomPos = MachineBasicBlock::const_iterator(); 187 LiveInRegs.clear(); 188 } 189 190 const 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. 199 void 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. 232 bool 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. 240 bool 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 248 SlotIndex 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. 258 void 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. 276 void 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. 294 void 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. 308 static 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. 314 class RegisterOperands { 315 const TargetRegisterInfo *TRI; 316 const MachineRegisterInfo *MRI; 317 318 public: 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 340 protected: 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. 358 static 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. 371 void 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. 379 void 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. 390 void 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. 401 bool 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. 466 bool 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. 533 static 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. 571 static 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. 613 void 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. 650 void RegPressureTracker:: 651 getMaxUpwardPressureDelta(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). 674 static 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. 697 void 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. 742 void RegPressureTracker:: 743 getMaxDownwardPressureDelta(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. 764 void RegPressureTracker:: 765 getUpwardPressure(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. 780 void RegPressureTracker:: 781 getDownwardPressure(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