SplitKit.cpp revision 263508
1//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 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 contains the SplitAnalysis class as well as mutator functions for 11// live range splitting. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "SplitKit.h" 17#include "llvm/ADT/Statistic.h" 18#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19#include "llvm/CodeGen/LiveRangeEdit.h" 20#include "llvm/CodeGen/MachineDominators.h" 21#include "llvm/CodeGen/MachineInstrBuilder.h" 22#include "llvm/CodeGen/MachineLoopInfo.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/CodeGen/VirtRegMap.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/Target/TargetInstrInfo.h" 28#include "llvm/Target/TargetMachine.h" 29 30using namespace llvm; 31 32STATISTIC(NumFinished, "Number of splits finished"); 33STATISTIC(NumSimple, "Number of splits that were simple"); 34STATISTIC(NumCopies, "Number of copies inserted for splitting"); 35STATISTIC(NumRemats, "Number of rematerialized defs for splitting"); 36STATISTIC(NumRepairs, "Number of invalid live ranges repaired"); 37 38//===----------------------------------------------------------------------===// 39// Split Analysis 40//===----------------------------------------------------------------------===// 41 42SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 43 const LiveIntervals &lis, 44 const MachineLoopInfo &mli) 45 : MF(vrm.getMachineFunction()), 46 VRM(vrm), 47 LIS(lis), 48 Loops(mli), 49 TII(*MF.getTarget().getInstrInfo()), 50 CurLI(0), 51 LastSplitPoint(MF.getNumBlockIDs()) {} 52 53void SplitAnalysis::clear() { 54 UseSlots.clear(); 55 UseBlocks.clear(); 56 ThroughBlocks.clear(); 57 CurLI = 0; 58 DidRepairRange = false; 59} 60 61SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 62 const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 63 const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); 64 std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num]; 65 SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB); 66 67 // Compute split points on the first call. The pair is independent of the 68 // current live interval. 69 if (!LSP.first.isValid()) { 70 MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator(); 71 if (FirstTerm == MBB->end()) 72 LSP.first = MBBEnd; 73 else 74 LSP.first = LIS.getInstructionIndex(FirstTerm); 75 76 // If there is a landing pad successor, also find the call instruction. 77 if (!LPad) 78 return LSP.first; 79 // There may not be a call instruction (?) in which case we ignore LPad. 80 LSP.second = LSP.first; 81 for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin(); 82 I != E;) { 83 --I; 84 if (I->isCall()) { 85 LSP.second = LIS.getInstructionIndex(I); 86 break; 87 } 88 } 89 } 90 91 // If CurLI is live into a landing pad successor, move the last split point 92 // back to the call that may throw. 93 if (!LPad || !LSP.second || !LIS.isLiveInToMBB(*CurLI, LPad)) 94 return LSP.first; 95 96 // Find the value leaving MBB. 97 const VNInfo *VNI = CurLI->getVNInfoBefore(MBBEnd); 98 if (!VNI) 99 return LSP.first; 100 101 // If the value leaving MBB was defined after the call in MBB, it can't 102 // really be live-in to the landing pad. This can happen if the landing pad 103 // has a PHI, and this register is undef on the exceptional edge. 104 // <rdar://problem/10664933> 105 if (!SlotIndex::isEarlierInstr(VNI->def, LSP.second) && VNI->def < MBBEnd) 106 return LSP.first; 107 108 // Value is properly live-in to the landing pad. 109 // Only allow splits before the call. 110 return LSP.second; 111} 112 113MachineBasicBlock::iterator 114SplitAnalysis::getLastSplitPointIter(MachineBasicBlock *MBB) { 115 SlotIndex LSP = getLastSplitPoint(MBB->getNumber()); 116 if (LSP == LIS.getMBBEndIdx(MBB)) 117 return MBB->end(); 118 return LIS.getInstructionFromIndex(LSP); 119} 120 121/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 122void SplitAnalysis::analyzeUses() { 123 assert(UseSlots.empty() && "Call clear first"); 124 125 // First get all the defs from the interval values. This provides the correct 126 // slots for early clobbers. 127 for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), 128 E = CurLI->vni_end(); I != E; ++I) 129 if (!(*I)->isPHIDef() && !(*I)->isUnused()) 130 UseSlots.push_back((*I)->def); 131 132 // Get use slots form the use-def chain. 133 const MachineRegisterInfo &MRI = MF.getRegInfo(); 134 for (MachineRegisterInfo::use_nodbg_iterator 135 I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 136 ++I) 137 if (!I.getOperand().isUndef()) 138 UseSlots.push_back(LIS.getInstructionIndex(&*I).getRegSlot()); 139 140 array_pod_sort(UseSlots.begin(), UseSlots.end()); 141 142 // Remove duplicates, keeping the smaller slot for each instruction. 143 // That is what we want for early clobbers. 144 UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 145 SlotIndex::isSameInstr), 146 UseSlots.end()); 147 148 // Compute per-live block info. 149 if (!calcLiveBlockInfo()) { 150 // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 151 // I am looking at you, RegisterCoalescer! 152 DidRepairRange = true; 153 ++NumRepairs; 154 DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 155 const_cast<LiveIntervals&>(LIS) 156 .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 157 UseBlocks.clear(); 158 ThroughBlocks.clear(); 159 bool fixed = calcLiveBlockInfo(); 160 (void)fixed; 161 assert(fixed && "Couldn't fix broken live interval"); 162 } 163 164 DEBUG(dbgs() << "Analyze counted " 165 << UseSlots.size() << " instrs in " 166 << UseBlocks.size() << " blocks, through " 167 << NumThroughBlocks << " blocks.\n"); 168} 169 170/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 171/// where CurLI is live. 172bool SplitAnalysis::calcLiveBlockInfo() { 173 ThroughBlocks.resize(MF.getNumBlockIDs()); 174 NumThroughBlocks = NumGapBlocks = 0; 175 if (CurLI->empty()) 176 return true; 177 178 LiveInterval::const_iterator LVI = CurLI->begin(); 179 LiveInterval::const_iterator LVE = CurLI->end(); 180 181 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 182 UseI = UseSlots.begin(); 183 UseE = UseSlots.end(); 184 185 // Loop over basic blocks where CurLI is live. 186 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 187 for (;;) { 188 BlockInfo BI; 189 BI.MBB = MFI; 190 SlotIndex Start, Stop; 191 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 192 193 // If the block contains no uses, the range must be live through. At one 194 // point, RegisterCoalescer could create dangling ranges that ended 195 // mid-block. 196 if (UseI == UseE || *UseI >= Stop) { 197 ++NumThroughBlocks; 198 ThroughBlocks.set(BI.MBB->getNumber()); 199 // The range shouldn't end mid-block if there are no uses. This shouldn't 200 // happen. 201 if (LVI->end < Stop) 202 return false; 203 } else { 204 // This block has uses. Find the first and last uses in the block. 205 BI.FirstInstr = *UseI; 206 assert(BI.FirstInstr >= Start); 207 do ++UseI; 208 while (UseI != UseE && *UseI < Stop); 209 BI.LastInstr = UseI[-1]; 210 assert(BI.LastInstr < Stop); 211 212 // LVI is the first live segment overlapping MBB. 213 BI.LiveIn = LVI->start <= Start; 214 215 // When not live in, the first use should be a def. 216 if (!BI.LiveIn) { 217 assert(LVI->start == LVI->valno->def && "Dangling Segment start"); 218 assert(LVI->start == BI.FirstInstr && "First instr should be a def"); 219 BI.FirstDef = BI.FirstInstr; 220 } 221 222 // Look for gaps in the live range. 223 BI.LiveOut = true; 224 while (LVI->end < Stop) { 225 SlotIndex LastStop = LVI->end; 226 if (++LVI == LVE || LVI->start >= Stop) { 227 BI.LiveOut = false; 228 BI.LastInstr = LastStop; 229 break; 230 } 231 232 if (LastStop < LVI->start) { 233 // There is a gap in the live range. Create duplicate entries for the 234 // live-in snippet and the live-out snippet. 235 ++NumGapBlocks; 236 237 // Push the Live-in part. 238 BI.LiveOut = false; 239 UseBlocks.push_back(BI); 240 UseBlocks.back().LastInstr = LastStop; 241 242 // Set up BI for the live-out part. 243 BI.LiveIn = false; 244 BI.LiveOut = true; 245 BI.FirstInstr = BI.FirstDef = LVI->start; 246 } 247 248 // A Segment that starts in the middle of the block must be a def. 249 assert(LVI->start == LVI->valno->def && "Dangling Segment start"); 250 if (!BI.FirstDef) 251 BI.FirstDef = LVI->start; 252 } 253 254 UseBlocks.push_back(BI); 255 256 // LVI is now at LVE or LVI->end >= Stop. 257 if (LVI == LVE) 258 break; 259 } 260 261 // Live segment ends exactly at Stop. Move to the next segment. 262 if (LVI->end == Stop && ++LVI == LVE) 263 break; 264 265 // Pick the next basic block. 266 if (LVI->start < Stop) 267 ++MFI; 268 else 269 MFI = LIS.getMBBFromIndex(LVI->start); 270 } 271 272 assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); 273 return true; 274} 275 276unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 277 if (cli->empty()) 278 return 0; 279 LiveInterval *li = const_cast<LiveInterval*>(cli); 280 LiveInterval::iterator LVI = li->begin(); 281 LiveInterval::iterator LVE = li->end(); 282 unsigned Count = 0; 283 284 // Loop over basic blocks where li is live. 285 MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); 286 SlotIndex Stop = LIS.getMBBEndIdx(MFI); 287 for (;;) { 288 ++Count; 289 LVI = li->advanceTo(LVI, Stop); 290 if (LVI == LVE) 291 return Count; 292 do { 293 ++MFI; 294 Stop = LIS.getMBBEndIdx(MFI); 295 } while (Stop <= LVI->start); 296 } 297} 298 299bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 300 unsigned OrigReg = VRM.getOriginal(CurLI->reg); 301 const LiveInterval &Orig = LIS.getInterval(OrigReg); 302 assert(!Orig.empty() && "Splitting empty interval?"); 303 LiveInterval::const_iterator I = Orig.find(Idx); 304 305 // Range containing Idx should begin at Idx. 306 if (I != Orig.end() && I->start <= Idx) 307 return I->start == Idx; 308 309 // Range does not contain Idx, previous must end at Idx. 310 return I != Orig.begin() && (--I)->end == Idx; 311} 312 313void SplitAnalysis::analyze(const LiveInterval *li) { 314 clear(); 315 CurLI = li; 316 analyzeUses(); 317} 318 319 320//===----------------------------------------------------------------------===// 321// Split Editor 322//===----------------------------------------------------------------------===// 323 324/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 325SplitEditor::SplitEditor(SplitAnalysis &sa, 326 LiveIntervals &lis, 327 VirtRegMap &vrm, 328 MachineDominatorTree &mdt, 329 MachineBlockFrequencyInfo &mbfi) 330 : SA(sa), LIS(lis), VRM(vrm), 331 MRI(vrm.getMachineFunction().getRegInfo()), 332 MDT(mdt), 333 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 334 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 335 MBFI(mbfi), 336 Edit(0), 337 OpenIdx(0), 338 SpillMode(SM_Partition), 339 RegAssign(Allocator) 340{} 341 342void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { 343 Edit = &LRE; 344 SpillMode = SM; 345 OpenIdx = 0; 346 RegAssign.clear(); 347 Values.clear(); 348 349 // Reset the LiveRangeCalc instances needed for this spill mode. 350 LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, 351 &LIS.getVNInfoAllocator()); 352 if (SpillMode) 353 LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, 354 &LIS.getVNInfoAllocator()); 355 356 // We don't need an AliasAnalysis since we will only be performing 357 // cheap-as-a-copy remats anyway. 358 Edit->anyRematerializable(0); 359} 360 361#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 362void SplitEditor::dump() const { 363 if (RegAssign.empty()) { 364 dbgs() << " empty\n"; 365 return; 366 } 367 368 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 369 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 370 dbgs() << '\n'; 371} 372#endif 373 374VNInfo *SplitEditor::defValue(unsigned RegIdx, 375 const VNInfo *ParentVNI, 376 SlotIndex Idx) { 377 assert(ParentVNI && "Mapping NULL value"); 378 assert(Idx.isValid() && "Invalid SlotIndex"); 379 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 380 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 381 382 // Create a new value. 383 VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); 384 385 // Use insert for lookup, so we can add missing values with a second lookup. 386 std::pair<ValueMap::iterator, bool> InsP = 387 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), 388 ValueForcePair(VNI, false))); 389 390 // This was the first time (RegIdx, ParentVNI) was mapped. 391 // Keep it as a simple def without any liveness. 392 if (InsP.second) 393 return VNI; 394 395 // If the previous value was a simple mapping, add liveness for it now. 396 if (VNInfo *OldVNI = InsP.first->second.getPointer()) { 397 SlotIndex Def = OldVNI->def; 398 LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI)); 399 // No longer a simple mapping. Switch to a complex, non-forced mapping. 400 InsP.first->second = ValueForcePair(); 401 } 402 403 // This is a complex mapping, add liveness for VNI 404 SlotIndex Def = VNI->def; 405 LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); 406 407 return VNI; 408} 409 410void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) { 411 assert(ParentVNI && "Mapping NULL value"); 412 ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)]; 413 VNInfo *VNI = VFP.getPointer(); 414 415 // ParentVNI was either unmapped or already complex mapped. Either way, just 416 // set the force bit. 417 if (!VNI) { 418 VFP.setInt(true); 419 return; 420 } 421 422 // This was previously a single mapping. Make sure the old def is represented 423 // by a trivial live range. 424 SlotIndex Def = VNI->def; 425 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 426 LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); 427 // Mark as complex mapped, forced. 428 VFP = ValueForcePair(0, true); 429} 430 431VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 432 VNInfo *ParentVNI, 433 SlotIndex UseIdx, 434 MachineBasicBlock &MBB, 435 MachineBasicBlock::iterator I) { 436 MachineInstr *CopyMI = 0; 437 SlotIndex Def; 438 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 439 440 // We may be trying to avoid interference that ends at a deleted instruction, 441 // so always begin RegIdx 0 early and all others late. 442 bool Late = RegIdx != 0; 443 444 // Attempt cheap-as-a-copy rematerialization. 445 LiveRangeEdit::Remat RM(ParentVNI); 446 if (Edit->canRematerializeAt(RM, UseIdx, true)) { 447 Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late); 448 ++NumRemats; 449 } else { 450 // Can't remat, just insert a copy from parent. 451 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 452 .addReg(Edit->getReg()); 453 Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 454 .getRegSlot(); 455 ++NumCopies; 456 } 457 458 // Define the value in Reg. 459 return defValue(RegIdx, ParentVNI, Def); 460} 461 462/// Create a new virtual register and live interval. 463unsigned SplitEditor::openIntv() { 464 // Create the complement as index 0. 465 if (Edit->empty()) 466 Edit->createEmptyInterval(); 467 468 // Create the open interval. 469 OpenIdx = Edit->size(); 470 Edit->createEmptyInterval(); 471 return OpenIdx; 472} 473 474void SplitEditor::selectIntv(unsigned Idx) { 475 assert(Idx != 0 && "Cannot select the complement interval"); 476 assert(Idx < Edit->size() && "Can only select previously opened interval"); 477 DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 478 OpenIdx = Idx; 479} 480 481SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 482 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 483 DEBUG(dbgs() << " enterIntvBefore " << Idx); 484 Idx = Idx.getBaseIndex(); 485 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 486 if (!ParentVNI) { 487 DEBUG(dbgs() << ": not live\n"); 488 return Idx; 489 } 490 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 491 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 492 assert(MI && "enterIntvBefore called with invalid index"); 493 494 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 495 return VNI->def; 496} 497 498SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 499 assert(OpenIdx && "openIntv not called before enterIntvAfter"); 500 DEBUG(dbgs() << " enterIntvAfter " << Idx); 501 Idx = Idx.getBoundaryIndex(); 502 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 503 if (!ParentVNI) { 504 DEBUG(dbgs() << ": not live\n"); 505 return Idx; 506 } 507 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 508 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 509 assert(MI && "enterIntvAfter called with invalid index"); 510 511 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 512 llvm::next(MachineBasicBlock::iterator(MI))); 513 return VNI->def; 514} 515 516SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 517 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 518 SlotIndex End = LIS.getMBBEndIdx(&MBB); 519 SlotIndex Last = End.getPrevSlot(); 520 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 521 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 522 if (!ParentVNI) { 523 DEBUG(dbgs() << ": not live\n"); 524 return End; 525 } 526 DEBUG(dbgs() << ": valno " << ParentVNI->id); 527 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 528 SA.getLastSplitPointIter(&MBB)); 529 RegAssign.insert(VNI->def, End, OpenIdx); 530 DEBUG(dump()); 531 return VNI->def; 532} 533 534/// useIntv - indicate that all instructions in MBB should use OpenLI. 535void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 536 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 537} 538 539void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 540 assert(OpenIdx && "openIntv not called before useIntv"); 541 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 542 RegAssign.insert(Start, End, OpenIdx); 543 DEBUG(dump()); 544} 545 546SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 547 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 548 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 549 550 // The interval must be live beyond the instruction at Idx. 551 SlotIndex Boundary = Idx.getBoundaryIndex(); 552 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); 553 if (!ParentVNI) { 554 DEBUG(dbgs() << ": not live\n"); 555 return Boundary.getNextSlot(); 556 } 557 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 558 MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); 559 assert(MI && "No instruction at index"); 560 561 // In spill mode, make live ranges as short as possible by inserting the copy 562 // before MI. This is only possible if that instruction doesn't redefine the 563 // value. The inserted COPY is not a kill, and we don't need to recompute 564 // the source live range. The spiller also won't try to hoist this copy. 565 if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && 566 MI->readsVirtualRegister(Edit->getReg())) { 567 forceRecompute(0, ParentVNI); 568 defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 569 return Idx; 570 } 571 572 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), 573 llvm::next(MachineBasicBlock::iterator(MI))); 574 return VNI->def; 575} 576 577SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 578 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 579 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 580 581 // The interval must be live into the instruction at Idx. 582 Idx = Idx.getBaseIndex(); 583 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 584 if (!ParentVNI) { 585 DEBUG(dbgs() << ": not live\n"); 586 return Idx.getNextSlot(); 587 } 588 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 589 590 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 591 assert(MI && "No instruction at index"); 592 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 593 return VNI->def; 594} 595 596SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 597 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 598 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 599 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 600 601 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 602 if (!ParentVNI) { 603 DEBUG(dbgs() << ": not live\n"); 604 return Start; 605 } 606 607 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 608 MBB.SkipPHIsAndLabels(MBB.begin())); 609 RegAssign.insert(Start, VNI->def, OpenIdx); 610 DEBUG(dump()); 611 return VNI->def; 612} 613 614void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 615 assert(OpenIdx && "openIntv not called before overlapIntv"); 616 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 617 assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && 618 "Parent changes value in extended range"); 619 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 620 "Range cannot span basic blocks"); 621 622 // The complement interval will be extended as needed by LRCalc.extend(). 623 if (ParentVNI) 624 forceRecompute(0, ParentVNI); 625 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 626 RegAssign.insert(Start, End, OpenIdx); 627 DEBUG(dump()); 628} 629 630//===----------------------------------------------------------------------===// 631// Spill modes 632//===----------------------------------------------------------------------===// 633 634void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { 635 LiveInterval *LI = &LIS.getInterval(Edit->get(0)); 636 DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n"); 637 RegAssignMap::iterator AssignI; 638 AssignI.setMap(RegAssign); 639 640 for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 641 VNInfo *VNI = Copies[i]; 642 SlotIndex Def = VNI->def; 643 MachineInstr *MI = LIS.getInstructionFromIndex(Def); 644 assert(MI && "No instruction for back-copy"); 645 646 MachineBasicBlock *MBB = MI->getParent(); 647 MachineBasicBlock::iterator MBBI(MI); 648 bool AtBegin; 649 do AtBegin = MBBI == MBB->begin(); 650 while (!AtBegin && (--MBBI)->isDebugValue()); 651 652 DEBUG(dbgs() << "Removing " << Def << '\t' << *MI); 653 LI->removeValNo(VNI); 654 LIS.RemoveMachineInstrFromMaps(MI); 655 MI->eraseFromParent(); 656 657 // Adjust RegAssign if a register assignment is killed at VNI->def. We 658 // want to avoid calculating the live range of the source register if 659 // possible. 660 AssignI.find(Def.getPrevSlot()); 661 if (!AssignI.valid() || AssignI.start() >= Def) 662 continue; 663 // If MI doesn't kill the assigned register, just leave it. 664 if (AssignI.stop() != Def) 665 continue; 666 unsigned RegIdx = AssignI.value(); 667 if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) { 668 DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n'); 669 forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def)); 670 } else { 671 SlotIndex Kill = LIS.getInstructionIndex(MBBI).getRegSlot(); 672 DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); 673 AssignI.setStop(Kill); 674 } 675 } 676} 677 678MachineBasicBlock* 679SplitEditor::findShallowDominator(MachineBasicBlock *MBB, 680 MachineBasicBlock *DefMBB) { 681 if (MBB == DefMBB) 682 return MBB; 683 assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def."); 684 685 const MachineLoopInfo &Loops = SA.Loops; 686 const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); 687 MachineDomTreeNode *DefDomNode = MDT[DefMBB]; 688 689 // Best candidate so far. 690 MachineBasicBlock *BestMBB = MBB; 691 unsigned BestDepth = UINT_MAX; 692 693 for (;;) { 694 const MachineLoop *Loop = Loops.getLoopFor(MBB); 695 696 // MBB isn't in a loop, it doesn't get any better. All dominators have a 697 // higher frequency by definition. 698 if (!Loop) { 699 DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 700 << MBB->getNumber() << " at depth 0\n"); 701 return MBB; 702 } 703 704 // We'll never be able to exit the DefLoop. 705 if (Loop == DefLoop) { 706 DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 707 << MBB->getNumber() << " in the same loop\n"); 708 return MBB; 709 } 710 711 // Least busy dominator seen so far. 712 unsigned Depth = Loop->getLoopDepth(); 713 if (Depth < BestDepth) { 714 BestMBB = MBB; 715 BestDepth = Depth; 716 DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 717 << MBB->getNumber() << " at depth " << Depth << '\n'); 718 } 719 720 // Leave loop by going to the immediate dominator of the loop header. 721 // This is a bigger stride than simply walking up the dominator tree. 722 MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); 723 724 // Too far up the dominator tree? 725 if (!IDom || !MDT.dominates(DefDomNode, IDom)) 726 return BestMBB; 727 728 MBB = IDom->getBlock(); 729 } 730} 731 732void SplitEditor::hoistCopiesForSize() { 733 // Get the complement interval, always RegIdx 0. 734 LiveInterval *LI = &LIS.getInterval(Edit->get(0)); 735 LiveInterval *Parent = &Edit->getParent(); 736 737 // Track the nearest common dominator for all back-copies for each ParentVNI, 738 // indexed by ParentVNI->id. 739 typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair; 740 SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); 741 742 // Find the nearest common dominator for parent values with multiple 743 // back-copies. If a single back-copy dominates, put it in DomPair.second. 744 for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); 745 VI != VE; ++VI) { 746 VNInfo *VNI = *VI; 747 if (VNI->isUnused()) 748 continue; 749 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 750 assert(ParentVNI && "Parent not live at complement def"); 751 752 // Don't hoist remats. The complement is probably going to disappear 753 // completely anyway. 754 if (Edit->didRematerialize(ParentVNI)) 755 continue; 756 757 MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); 758 DomPair &Dom = NearestDom[ParentVNI->id]; 759 760 // Keep directly defined parent values. This is either a PHI or an 761 // instruction in the complement range. All other copies of ParentVNI 762 // should be eliminated. 763 if (VNI->def == ParentVNI->def) { 764 DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); 765 Dom = DomPair(ValMBB, VNI->def); 766 continue; 767 } 768 // Skip the singly mapped values. There is nothing to gain from hoisting a 769 // single back-copy. 770 if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { 771 DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); 772 continue; 773 } 774 775 if (!Dom.first) { 776 // First time we see ParentVNI. VNI dominates itself. 777 Dom = DomPair(ValMBB, VNI->def); 778 } else if (Dom.first == ValMBB) { 779 // Two defs in the same block. Pick the earlier def. 780 if (!Dom.second.isValid() || VNI->def < Dom.second) 781 Dom.second = VNI->def; 782 } else { 783 // Different basic blocks. Check if one dominates. 784 MachineBasicBlock *Near = 785 MDT.findNearestCommonDominator(Dom.first, ValMBB); 786 if (Near == ValMBB) 787 // Def ValMBB dominates. 788 Dom = DomPair(ValMBB, VNI->def); 789 else if (Near != Dom.first) 790 // None dominate. Hoist to common dominator, need new def. 791 Dom = DomPair(Near, SlotIndex()); 792 } 793 794 DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def 795 << " for parent " << ParentVNI->id << '@' << ParentVNI->def 796 << " hoist to BB#" << Dom.first->getNumber() << ' ' 797 << Dom.second << '\n'); 798 } 799 800 // Insert the hoisted copies. 801 for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { 802 DomPair &Dom = NearestDom[i]; 803 if (!Dom.first || Dom.second.isValid()) 804 continue; 805 // This value needs a hoisted copy inserted at the end of Dom.first. 806 VNInfo *ParentVNI = Parent->getValNumInfo(i); 807 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); 808 // Get a less loopy dominator than Dom.first. 809 Dom.first = findShallowDominator(Dom.first, DefMBB); 810 SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot(); 811 Dom.second = 812 defFromParent(0, ParentVNI, Last, *Dom.first, 813 SA.getLastSplitPointIter(Dom.first))->def; 814 } 815 816 // Remove redundant back-copies that are now known to be dominated by another 817 // def with the same value. 818 SmallVector<VNInfo*, 8> BackCopies; 819 for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); 820 VI != VE; ++VI) { 821 VNInfo *VNI = *VI; 822 if (VNI->isUnused()) 823 continue; 824 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 825 const DomPair &Dom = NearestDom[ParentVNI->id]; 826 if (!Dom.first || Dom.second == VNI->def) 827 continue; 828 BackCopies.push_back(VNI); 829 forceRecompute(0, ParentVNI); 830 } 831 removeBackCopies(BackCopies); 832} 833 834 835/// transferValues - Transfer all possible values to the new live ranges. 836/// Values that were rematerialized are left alone, they need LRCalc.extend(). 837bool SplitEditor::transferValues() { 838 bool Skipped = false; 839 RegAssignMap::const_iterator AssignI = RegAssign.begin(); 840 for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 841 ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 842 DEBUG(dbgs() << " blit " << *ParentI << ':'); 843 VNInfo *ParentVNI = ParentI->valno; 844 // RegAssign has holes where RegIdx 0 should be used. 845 SlotIndex Start = ParentI->start; 846 AssignI.advanceTo(Start); 847 do { 848 unsigned RegIdx; 849 SlotIndex End = ParentI->end; 850 if (!AssignI.valid()) { 851 RegIdx = 0; 852 } else if (AssignI.start() <= Start) { 853 RegIdx = AssignI.value(); 854 if (AssignI.stop() < End) { 855 End = AssignI.stop(); 856 ++AssignI; 857 } 858 } else { 859 RegIdx = 0; 860 End = std::min(End, AssignI.start()); 861 } 862 863 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 864 DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 865 LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); 866 867 // Check for a simply defined value that can be blitted directly. 868 ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); 869 if (VNInfo *VNI = VFP.getPointer()) { 870 DEBUG(dbgs() << ':' << VNI->id); 871 LR.addSegment(LiveInterval::Segment(Start, End, VNI)); 872 Start = End; 873 continue; 874 } 875 876 // Skip values with forced recomputation. 877 if (VFP.getInt()) { 878 DEBUG(dbgs() << "(recalc)"); 879 Skipped = true; 880 Start = End; 881 continue; 882 } 883 884 LiveRangeCalc &LRC = getLRCalc(RegIdx); 885 886 // This value has multiple defs in RegIdx, but it wasn't rematerialized, 887 // so the live range is accurate. Add live-in blocks in [Start;End) to the 888 // LiveInBlocks. 889 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 890 SlotIndex BlockStart, BlockEnd; 891 tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 892 893 // The first block may be live-in, or it may have its own def. 894 if (Start != BlockStart) { 895 VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); 896 assert(VNI && "Missing def for complex mapped value"); 897 DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 898 // MBB has its own def. Is it also live-out? 899 if (BlockEnd <= End) 900 LRC.setLiveOutValue(MBB, VNI); 901 902 // Skip to the next block for live-in. 903 ++MBB; 904 BlockStart = BlockEnd; 905 } 906 907 // Handle the live-in blocks covered by [Start;End). 908 assert(Start <= BlockStart && "Expected live-in block"); 909 while (BlockStart < End) { 910 DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 911 BlockEnd = LIS.getMBBEndIdx(MBB); 912 if (BlockStart == ParentVNI->def) { 913 // This block has the def of a parent PHI, so it isn't live-in. 914 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 915 VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); 916 assert(VNI && "Missing def for complex mapped parent PHI"); 917 if (End >= BlockEnd) 918 LRC.setLiveOutValue(MBB, VNI); // Live-out as well. 919 } else { 920 // This block needs a live-in value. The last block covered may not 921 // be live-out. 922 if (End < BlockEnd) 923 LRC.addLiveInBlock(LR, MDT[MBB], End); 924 else { 925 // Live-through, and we don't know the value. 926 LRC.addLiveInBlock(LR, MDT[MBB]); 927 LRC.setLiveOutValue(MBB, 0); 928 } 929 } 930 BlockStart = BlockEnd; 931 ++MBB; 932 } 933 Start = End; 934 } while (Start != ParentI->end); 935 DEBUG(dbgs() << '\n'); 936 } 937 938 LRCalc[0].calculateValues(); 939 if (SpillMode) 940 LRCalc[1].calculateValues(); 941 942 return Skipped; 943} 944 945void SplitEditor::extendPHIKillRanges() { 946 // Extend live ranges to be live-out for successor PHI values. 947 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 948 E = Edit->getParent().vni_end(); I != E; ++I) { 949 const VNInfo *PHIVNI = *I; 950 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 951 continue; 952 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 953 LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); 954 LiveRangeCalc &LRC = getLRCalc(RegIdx); 955 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 956 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 957 PE = MBB->pred_end(); PI != PE; ++PI) { 958 SlotIndex End = LIS.getMBBEndIdx(*PI); 959 SlotIndex LastUse = End.getPrevSlot(); 960 // The predecessor may not have a live-out value. That is OK, like an 961 // undef PHI operand. 962 if (Edit->getParent().liveAt(LastUse)) { 963 assert(RegAssign.lookup(LastUse) == RegIdx && 964 "Different register assignment in phi predecessor"); 965 LRC.extend(LR, End); 966 } 967 } 968 } 969} 970 971/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 972void SplitEditor::rewriteAssigned(bool ExtendRanges) { 973 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 974 RE = MRI.reg_end(); RI != RE;) { 975 MachineOperand &MO = RI.getOperand(); 976 MachineInstr *MI = MO.getParent(); 977 ++RI; 978 // LiveDebugVariables should have handled all DBG_VALUE instructions. 979 if (MI->isDebugValue()) { 980 DEBUG(dbgs() << "Zapping " << *MI); 981 MO.setReg(0); 982 continue; 983 } 984 985 // <undef> operands don't really read the register, so it doesn't matter 986 // which register we choose. When the use operand is tied to a def, we must 987 // use the same register as the def, so just do that always. 988 SlotIndex Idx = LIS.getInstructionIndex(MI); 989 if (MO.isDef() || MO.isUndef()) 990 Idx = Idx.getRegSlot(MO.isEarlyClobber()); 991 992 // Rewrite to the mapped register at Idx. 993 unsigned RegIdx = RegAssign.lookup(Idx); 994 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 995 MO.setReg(LI->reg); 996 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 997 << Idx << ':' << RegIdx << '\t' << *MI); 998 999 // Extend liveness to Idx if the instruction reads reg. 1000 if (!ExtendRanges || MO.isUndef()) 1001 continue; 1002 1003 // Skip instructions that don't read Reg. 1004 if (MO.isDef()) { 1005 if (!MO.getSubReg() && !MO.isEarlyClobber()) 1006 continue; 1007 // We may wan't to extend a live range for a partial redef, or for a use 1008 // tied to an early clobber. 1009 Idx = Idx.getPrevSlot(); 1010 if (!Edit->getParent().liveAt(Idx)) 1011 continue; 1012 } else 1013 Idx = Idx.getRegSlot(true); 1014 1015 getLRCalc(RegIdx).extend(*LI, Idx.getNextSlot()); 1016 } 1017} 1018 1019void SplitEditor::deleteRematVictims() { 1020 SmallVector<MachineInstr*, 8> Dead; 1021 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 1022 LiveInterval *LI = &LIS.getInterval(*I); 1023 for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 1024 LII != LIE; ++LII) { 1025 // Dead defs end at the dead slot. 1026 if (LII->end != LII->valno->def.getDeadSlot()) 1027 continue; 1028 MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 1029 assert(MI && "Missing instruction for dead def"); 1030 MI->addRegisterDead(LI->reg, &TRI); 1031 1032 if (!MI->allDefsAreDead()) 1033 continue; 1034 1035 DEBUG(dbgs() << "All defs dead: " << *MI); 1036 Dead.push_back(MI); 1037 } 1038 } 1039 1040 if (Dead.empty()) 1041 return; 1042 1043 Edit->eliminateDeadDefs(Dead); 1044} 1045 1046void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 1047 ++NumFinished; 1048 1049 // At this point, the live intervals in Edit contain VNInfos corresponding to 1050 // the inserted copies. 1051 1052 // Add the original defs from the parent interval. 1053 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 1054 E = Edit->getParent().vni_end(); I != E; ++I) { 1055 const VNInfo *ParentVNI = *I; 1056 if (ParentVNI->isUnused()) 1057 continue; 1058 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 1059 defValue(RegIdx, ParentVNI, ParentVNI->def); 1060 1061 // Force rematted values to be recomputed everywhere. 1062 // The new live ranges may be truncated. 1063 if (Edit->didRematerialize(ParentVNI)) 1064 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1065 forceRecompute(i, ParentVNI); 1066 } 1067 1068 // Hoist back-copies to the complement interval when in spill mode. 1069 switch (SpillMode) { 1070 case SM_Partition: 1071 // Leave all back-copies as is. 1072 break; 1073 case SM_Size: 1074 hoistCopiesForSize(); 1075 break; 1076 case SM_Speed: 1077 llvm_unreachable("Spill mode 'speed' not implemented yet"); 1078 } 1079 1080 // Transfer the simply mapped values, check if any are skipped. 1081 bool Skipped = transferValues(); 1082 if (Skipped) 1083 extendPHIKillRanges(); 1084 else 1085 ++NumSimple; 1086 1087 // Rewrite virtual registers, possibly extending ranges. 1088 rewriteAssigned(Skipped); 1089 1090 // Delete defs that were rematted everywhere. 1091 if (Skipped) 1092 deleteRematVictims(); 1093 1094 // Get rid of unused values and set phi-kill flags. 1095 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) { 1096 LiveInterval &LI = LIS.getInterval(*I); 1097 LI.RenumberValues(); 1098 } 1099 1100 // Provide a reverse mapping from original indices to Edit ranges. 1101 if (LRMap) { 1102 LRMap->clear(); 1103 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1104 LRMap->push_back(i); 1105 } 1106 1107 // Now check if any registers were separated into multiple components. 1108 ConnectedVNInfoEqClasses ConEQ(LIS); 1109 for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 1110 // Don't use iterators, they are invalidated by create() below. 1111 LiveInterval *li = &LIS.getInterval(Edit->get(i)); 1112 unsigned NumComp = ConEQ.Classify(li); 1113 if (NumComp <= 1) 1114 continue; 1115 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 1116 SmallVector<LiveInterval*, 8> dups; 1117 dups.push_back(li); 1118 for (unsigned j = 1; j != NumComp; ++j) 1119 dups.push_back(&Edit->createEmptyInterval()); 1120 ConEQ.Distribute(&dups[0], MRI); 1121 // The new intervals all map back to i. 1122 if (LRMap) 1123 LRMap->resize(Edit->size(), i); 1124 } 1125 1126 // Calculate spill weight and allocation hints for new intervals. 1127 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI); 1128 1129 assert(!LRMap || LRMap->size() == Edit->size()); 1130} 1131 1132 1133//===----------------------------------------------------------------------===// 1134// Single Block Splitting 1135//===----------------------------------------------------------------------===// 1136 1137bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, 1138 bool SingleInstrs) const { 1139 // Always split for multiple instructions. 1140 if (!BI.isOneInstr()) 1141 return true; 1142 // Don't split for single instructions unless explicitly requested. 1143 if (!SingleInstrs) 1144 return false; 1145 // Splitting a live-through range always makes progress. 1146 if (BI.LiveIn && BI.LiveOut) 1147 return true; 1148 // No point in isolating a copy. It has no register class constraints. 1149 if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) 1150 return false; 1151 // Finally, don't isolate an end point that was created by earlier splits. 1152 return isOriginalEndpoint(BI.FirstInstr); 1153} 1154 1155void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1156 openIntv(); 1157 SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1158 SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, 1159 LastSplitPoint)); 1160 if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { 1161 useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); 1162 } else { 1163 // The last use is after the last valid split point. 1164 SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1165 useIntv(SegStart, SegStop); 1166 overlapIntv(SegStop, BI.LastInstr); 1167 } 1168} 1169 1170 1171//===----------------------------------------------------------------------===// 1172// Global Live Range Splitting Support 1173//===----------------------------------------------------------------------===// 1174 1175// These methods support a method of global live range splitting that uses a 1176// global algorithm to decide intervals for CFG edges. They will insert split 1177// points and color intervals in basic blocks while avoiding interference. 1178// 1179// Note that splitSingleBlock is also useful for blocks where both CFG edges 1180// are on the stack. 1181 1182void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 1183 unsigned IntvIn, SlotIndex LeaveBefore, 1184 unsigned IntvOut, SlotIndex EnterAfter){ 1185 SlotIndex Start, Stop; 1186 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 1187 1188 DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 1189 << ") intf " << LeaveBefore << '-' << EnterAfter 1190 << ", live-through " << IntvIn << " -> " << IntvOut); 1191 1192 assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 1193 1194 assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 1195 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 1196 assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 1197 1198 MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 1199 1200 if (!IntvOut) { 1201 DEBUG(dbgs() << ", spill on entry.\n"); 1202 // 1203 // <<<<<<<<< Possible LeaveBefore interference. 1204 // |-----------| Live through. 1205 // -____________ Spill on entry. 1206 // 1207 selectIntv(IntvIn); 1208 SlotIndex Idx = leaveIntvAtTop(*MBB); 1209 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1210 (void)Idx; 1211 return; 1212 } 1213 1214 if (!IntvIn) { 1215 DEBUG(dbgs() << ", reload on exit.\n"); 1216 // 1217 // >>>>>>> Possible EnterAfter interference. 1218 // |-----------| Live through. 1219 // ___________-- Reload on exit. 1220 // 1221 selectIntv(IntvOut); 1222 SlotIndex Idx = enterIntvAtEnd(*MBB); 1223 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1224 (void)Idx; 1225 return; 1226 } 1227 1228 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 1229 DEBUG(dbgs() << ", straight through.\n"); 1230 // 1231 // |-----------| Live through. 1232 // ------------- Straight through, same intv, no interference. 1233 // 1234 selectIntv(IntvOut); 1235 useIntv(Start, Stop); 1236 return; 1237 } 1238 1239 // We cannot legally insert splits after LSP. 1240 SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 1241 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 1242 1243 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 1244 LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 1245 DEBUG(dbgs() << ", switch avoiding interference.\n"); 1246 // 1247 // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 1248 // |-----------| Live through. 1249 // ------======= Switch intervals between interference. 1250 // 1251 selectIntv(IntvOut); 1252 SlotIndex Idx; 1253 if (LeaveBefore && LeaveBefore < LSP) { 1254 Idx = enterIntvBefore(LeaveBefore); 1255 useIntv(Idx, Stop); 1256 } else { 1257 Idx = enterIntvAtEnd(*MBB); 1258 } 1259 selectIntv(IntvIn); 1260 useIntv(Start, Idx); 1261 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1262 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1263 return; 1264 } 1265 1266 DEBUG(dbgs() << ", create local intv for interference.\n"); 1267 // 1268 // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1269 // |-----------| Live through. 1270 // ==---------== Switch intervals before/after interference. 1271 // 1272 assert(LeaveBefore <= EnterAfter && "Missed case"); 1273 1274 selectIntv(IntvOut); 1275 SlotIndex Idx = enterIntvAfter(EnterAfter); 1276 useIntv(Idx, Stop); 1277 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1278 1279 selectIntv(IntvIn); 1280 Idx = leaveIntvBefore(LeaveBefore); 1281 useIntv(Start, Idx); 1282 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1283} 1284 1285 1286void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1287 unsigned IntvIn, SlotIndex LeaveBefore) { 1288 SlotIndex Start, Stop; 1289 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1290 1291 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1292 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1293 << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1294 << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1295 1296 assert(IntvIn && "Must have register in"); 1297 assert(BI.LiveIn && "Must be live-in"); 1298 assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1299 1300 if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { 1301 DEBUG(dbgs() << " before interference.\n"); 1302 // 1303 // <<< Interference after kill. 1304 // |---o---x | Killed in block. 1305 // ========= Use IntvIn everywhere. 1306 // 1307 selectIntv(IntvIn); 1308 useIntv(Start, BI.LastInstr); 1309 return; 1310 } 1311 1312 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1313 1314 if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { 1315 // 1316 // <<< Possible interference after last use. 1317 // |---o---o---| Live-out on stack. 1318 // =========____ Leave IntvIn after last use. 1319 // 1320 // < Interference after last use. 1321 // |---o---o--o| Live-out on stack, late last use. 1322 // ============ Copy to stack after LSP, overlap IntvIn. 1323 // \_____ Stack interval is live-out. 1324 // 1325 if (BI.LastInstr < LSP) { 1326 DEBUG(dbgs() << ", spill after last use before interference.\n"); 1327 selectIntv(IntvIn); 1328 SlotIndex Idx = leaveIntvAfter(BI.LastInstr); 1329 useIntv(Start, Idx); 1330 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1331 } else { 1332 DEBUG(dbgs() << ", spill before last split point.\n"); 1333 selectIntv(IntvIn); 1334 SlotIndex Idx = leaveIntvBefore(LSP); 1335 overlapIntv(Idx, BI.LastInstr); 1336 useIntv(Start, Idx); 1337 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1338 } 1339 return; 1340 } 1341 1342 // The interference is overlapping somewhere we wanted to use IntvIn. That 1343 // means we need to create a local interval that can be allocated a 1344 // different register. 1345 unsigned LocalIntv = openIntv(); 1346 (void)LocalIntv; 1347 DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1348 1349 if (!BI.LiveOut || BI.LastInstr < LSP) { 1350 // 1351 // <<<<<<< Interference overlapping uses. 1352 // |---o---o---| Live-out on stack. 1353 // =====----____ Leave IntvIn before interference, then spill. 1354 // 1355 SlotIndex To = leaveIntvAfter(BI.LastInstr); 1356 SlotIndex From = enterIntvBefore(LeaveBefore); 1357 useIntv(From, To); 1358 selectIntv(IntvIn); 1359 useIntv(Start, From); 1360 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1361 return; 1362 } 1363 1364 // <<<<<<< Interference overlapping uses. 1365 // |---o---o--o| Live-out on stack, late last use. 1366 // =====------- Copy to stack before LSP, overlap LocalIntv. 1367 // \_____ Stack interval is live-out. 1368 // 1369 SlotIndex To = leaveIntvBefore(LSP); 1370 overlapIntv(To, BI.LastInstr); 1371 SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1372 useIntv(From, To); 1373 selectIntv(IntvIn); 1374 useIntv(Start, From); 1375 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1376} 1377 1378void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1379 unsigned IntvOut, SlotIndex EnterAfter) { 1380 SlotIndex Start, Stop; 1381 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1382 1383 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1384 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1385 << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1386 << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1387 1388 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1389 1390 assert(IntvOut && "Must have register out"); 1391 assert(BI.LiveOut && "Must be live-out"); 1392 assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1393 1394 if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { 1395 DEBUG(dbgs() << " after interference.\n"); 1396 // 1397 // >>>> Interference before def. 1398 // | o---o---| Defined in block. 1399 // ========= Use IntvOut everywhere. 1400 // 1401 selectIntv(IntvOut); 1402 useIntv(BI.FirstInstr, Stop); 1403 return; 1404 } 1405 1406 if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { 1407 DEBUG(dbgs() << ", reload after interference.\n"); 1408 // 1409 // >>>> Interference before def. 1410 // |---o---o---| Live-through, stack-in. 1411 // ____========= Enter IntvOut before first use. 1412 // 1413 selectIntv(IntvOut); 1414 SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); 1415 useIntv(Idx, Stop); 1416 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1417 return; 1418 } 1419 1420 // The interference is overlapping somewhere we wanted to use IntvOut. That 1421 // means we need to create a local interval that can be allocated a 1422 // different register. 1423 DEBUG(dbgs() << ", interference overlaps uses.\n"); 1424 // 1425 // >>>>>>> Interference overlapping uses. 1426 // |---o---o---| Live-through, stack-in. 1427 // ____---====== Create local interval for interference range. 1428 // 1429 selectIntv(IntvOut); 1430 SlotIndex Idx = enterIntvAfter(EnterAfter); 1431 useIntv(Idx, Stop); 1432 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1433 1434 openIntv(); 1435 SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); 1436 useIntv(From, Idx); 1437} 1438