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