SplitKit.cpp revision 23436597a8efad427059f2a6db5264e6a40d2dc7
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 "splitter" 16#include "SplitKit.h" 17#include "VirtRegMap.h" 18#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19#include "llvm/CodeGen/MachineFunctionPass.h" 20#include "llvm/CodeGen/MachineInstrBuilder.h" 21#include "llvm/CodeGen/MachineLoopInfo.h" 22#include "llvm/CodeGen/MachineRegisterInfo.h" 23#include "llvm/Support/CommandLine.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/Support/raw_ostream.h" 26#include "llvm/Target/TargetInstrInfo.h" 27#include "llvm/Target/TargetMachine.h" 28 29using namespace llvm; 30 31static cl::opt<bool> 32AllowSplit("spiller-splits-edges", 33 cl::desc("Allow critical edge splitting during spilling")); 34 35//===----------------------------------------------------------------------===// 36// Split Analysis 37//===----------------------------------------------------------------------===// 38 39SplitAnalysis::SplitAnalysis(const MachineFunction &mf, 40 const LiveIntervals &lis, 41 const MachineLoopInfo &mli) 42 : mf_(mf), 43 lis_(lis), 44 loops_(mli), 45 tii_(*mf.getTarget().getInstrInfo()), 46 curli_(0) {} 47 48void SplitAnalysis::clear() { 49 usingInstrs_.clear(); 50 usingBlocks_.clear(); 51 usingLoops_.clear(); 52 curli_ = 0; 53} 54 55bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) { 56 MachineBasicBlock *T, *F; 57 SmallVector<MachineOperand, 4> Cond; 58 return !tii_.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond); 59} 60 61/// analyzeUses - Count instructions, basic blocks, and loops using curli. 62void SplitAnalysis::analyzeUses() { 63 const MachineRegisterInfo &MRI = mf_.getRegInfo(); 64 for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg); 65 MachineInstr *MI = I.skipInstruction();) { 66 if (MI->isDebugValue() || !usingInstrs_.insert(MI)) 67 continue; 68 MachineBasicBlock *MBB = MI->getParent(); 69 if (usingBlocks_[MBB]++) 70 continue; 71 if (MachineLoop *Loop = loops_.getLoopFor(MBB)) 72 usingLoops_.insert(Loop); 73 } 74 DEBUG(dbgs() << "Counted " 75 << usingInstrs_.size() << " instrs, " 76 << usingBlocks_.size() << " blocks, " 77 << usingLoops_.size() << " loops in " 78 << *curli_ << "\n"); 79} 80 81// Get three sets of basic blocks surrounding a loop: Blocks inside the loop, 82// predecessor blocks, and exit blocks. 83void SplitAnalysis::getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks) { 84 Blocks.clear(); 85 86 // Blocks in the loop. 87 Blocks.Loop.insert(Loop->block_begin(), Loop->block_end()); 88 89 // Predecessor blocks. 90 const MachineBasicBlock *Header = Loop->getHeader(); 91 for (MachineBasicBlock::const_pred_iterator I = Header->pred_begin(), 92 E = Header->pred_end(); I != E; ++I) 93 if (!Blocks.Loop.count(*I)) 94 Blocks.Preds.insert(*I); 95 96 // Exit blocks. 97 for (MachineLoop::block_iterator I = Loop->block_begin(), 98 E = Loop->block_end(); I != E; ++I) { 99 const MachineBasicBlock *MBB = *I; 100 for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 101 SE = MBB->succ_end(); SI != SE; ++SI) 102 if (!Blocks.Loop.count(*SI)) 103 Blocks.Exits.insert(*SI); 104 } 105} 106 107/// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 108/// and around the Loop. 109SplitAnalysis::LoopPeripheralUse SplitAnalysis:: 110analyzeLoopPeripheralUse(const SplitAnalysis::LoopBlocks &Blocks) { 111 LoopPeripheralUse use = ContainedInLoop; 112 for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end(); 113 I != E; ++I) { 114 const MachineBasicBlock *MBB = I->first; 115 // Is this a peripheral block? 116 if (use < MultiPeripheral && 117 (Blocks.Preds.count(MBB) || Blocks.Exits.count(MBB))) { 118 if (I->second > 1) use = MultiPeripheral; 119 else use = SinglePeripheral; 120 continue; 121 } 122 // Is it a loop block? 123 if (Blocks.Loop.count(MBB)) 124 continue; 125 // It must be an unrelated block. 126 return OutsideLoop; 127 } 128 return use; 129} 130 131/// getCriticalExits - It may be necessary to partially break critical edges 132/// leaving the loop if an exit block has phi uses of curli. Collect the exit 133/// blocks that need special treatment into CriticalExits. 134void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks, 135 BlockPtrSet &CriticalExits) { 136 CriticalExits.clear(); 137 138 // A critical exit block contains a phi def of curli, and has a predecessor 139 // that is not in the loop nor a loop predecessor. 140 // For such an exit block, the edges carrying the new variable must be moved 141 // to a new pre-exit block. 142 for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end(); 143 I != E; ++I) { 144 const MachineBasicBlock *Succ = *I; 145 SlotIndex SuccIdx = lis_.getMBBStartIdx(Succ); 146 VNInfo *SuccVNI = curli_->getVNInfoAt(SuccIdx); 147 // This exit may not have curli live in at all. No need to split. 148 if (!SuccVNI) 149 continue; 150 // If this is not a PHI def, it is either using a value from before the 151 // loop, or a value defined inside the loop. Both are safe. 152 if (!SuccVNI->isPHIDef() || SuccVNI->def.getBaseIndex() != SuccIdx) 153 continue; 154 // This exit block does have a PHI. Does it also have a predecessor that is 155 // not a loop block or loop predecessor? 156 for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(), 157 PE = Succ->pred_end(); PI != PE; ++PI) { 158 const MachineBasicBlock *Pred = *PI; 159 if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred)) 160 continue; 161 // This is a critical exit block, and we need to split the exit edge. 162 CriticalExits.insert(Succ); 163 break; 164 } 165 } 166} 167 168/// canSplitCriticalExits - Return true if it is possible to insert new exit 169/// blocks before the blocks in CriticalExits. 170bool 171SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks, 172 BlockPtrSet &CriticalExits) { 173 // If we don't allow critical edge splitting, require no critical exits. 174 if (!AllowSplit) 175 return CriticalExits.empty(); 176 177 for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end(); 178 I != E; ++I) { 179 const MachineBasicBlock *Succ = *I; 180 // We want to insert a new pre-exit MBB before Succ, and change all the 181 // in-loop blocks to branch to the pre-exit instead of Succ. 182 // Check that all the in-loop predecessors can be changed. 183 for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(), 184 PE = Succ->pred_end(); PI != PE; ++PI) { 185 const MachineBasicBlock *Pred = *PI; 186 // The external predecessors won't be altered. 187 if (!Blocks.Loop.count(Pred) && !Blocks.Preds.count(Pred)) 188 continue; 189 if (!canAnalyzeBranch(Pred)) 190 return false; 191 } 192 193 // If Succ's layout predecessor falls through, that too must be analyzable. 194 // We need to insert the pre-exit block in the gap. 195 MachineFunction::const_iterator MFI = Succ; 196 if (MFI == mf_.begin()) 197 continue; 198 if (!canAnalyzeBranch(--MFI)) 199 return false; 200 } 201 // No problems found. 202 return true; 203} 204 205void SplitAnalysis::analyze(const LiveInterval *li) { 206 clear(); 207 curli_ = li; 208 analyzeUses(); 209} 210 211const MachineLoop *SplitAnalysis::getBestSplitLoop() { 212 assert(curli_ && "Call analyze() before getBestSplitLoop"); 213 if (usingLoops_.empty()) 214 return 0; 215 216 LoopPtrSet Loops, SecondLoops; 217 LoopBlocks Blocks; 218 BlockPtrSet CriticalExits; 219 220 // Find first-class and second class candidate loops. 221 // We prefer to split around loops where curli is used outside the periphery. 222 for (LoopPtrSet::const_iterator I = usingLoops_.begin(), 223 E = usingLoops_.end(); I != E; ++I) { 224 getLoopBlocks(*I, Blocks); 225 226 // FIXME: We need an SSA updater to properly handle multiple exit blocks. 227 if (Blocks.Exits.size() > 1) { 228 DEBUG(dbgs() << "MultipleExits: " << **I); 229 continue; 230 } 231 232 LoopPtrSet *LPS = 0; 233 switch(analyzeLoopPeripheralUse(Blocks)) { 234 case OutsideLoop: 235 LPS = &Loops; 236 break; 237 case MultiPeripheral: 238 LPS = &SecondLoops; 239 break; 240 case ContainedInLoop: 241 DEBUG(dbgs() << "ContainedInLoop: " << **I); 242 continue; 243 case SinglePeripheral: 244 DEBUG(dbgs() << "SinglePeripheral: " << **I); 245 continue; 246 } 247 // Will it be possible to split around this loop? 248 getCriticalExits(Blocks, CriticalExits); 249 DEBUG(dbgs() << CriticalExits.size() << " critical exits: " << **I); 250 if (!canSplitCriticalExits(Blocks, CriticalExits)) 251 continue; 252 // This is a possible split. 253 assert(LPS); 254 LPS->insert(*I); 255 } 256 257 DEBUG(dbgs() << "Got " << Loops.size() << " + " << SecondLoops.size() 258 << " candidate loops\n"); 259 260 // If there are no first class loops available, look at second class loops. 261 if (Loops.empty()) 262 Loops = SecondLoops; 263 264 if (Loops.empty()) 265 return 0; 266 267 // Pick the earliest loop. 268 // FIXME: Are there other heuristics to consider? 269 const MachineLoop *Best = 0; 270 SlotIndex BestIdx; 271 for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E; 272 ++I) { 273 SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader()); 274 if (!Best || Idx < BestIdx) 275 Best = *I, BestIdx = Idx; 276 } 277 DEBUG(dbgs() << "Best: " << *Best); 278 return Best; 279} 280 281 282//===----------------------------------------------------------------------===// 283// Split Editor 284//===----------------------------------------------------------------------===// 285 286/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 287SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm, 288 std::vector<LiveInterval*> &intervals) 289 : sa_(sa), lis_(lis), vrm_(vrm), 290 mri_(vrm.getMachineFunction().getRegInfo()), 291 tii_(*vrm.getMachineFunction().getTarget().getInstrInfo()), 292 dupli_(0), openli_(0), 293 intervals_(intervals), 294 firstInterval(intervals_.size()) 295{ 296 const LiveInterval *curli = sa_.getCurLI(); 297 assert(curli && "SplitEditor created from empty SplitAnalysis"); 298 299 // Make sure curli is assigned a stack slot, so all our intervals get the 300 // same slot as curli. 301 if (vrm_.getStackSlot(curli->reg) == VirtRegMap::NO_STACK_SLOT) 302 vrm_.assignVirt2StackSlot(curli->reg); 303 304 // Create an interval for dupli that is a copy of curli. 305 dupli_ = createInterval(); 306 dupli_->Copy(*curli, &mri_, lis_.getVNInfoAllocator()); 307 DEBUG(dbgs() << "SplitEditor DupLI: " << *dupli_ << '\n'); 308} 309 310LiveInterval *SplitEditor::createInterval() { 311 unsigned curli = sa_.getCurLI()->reg; 312 unsigned Reg = mri_.createVirtualRegister(mri_.getRegClass(curli)); 313 LiveInterval &Intv = lis_.getOrCreateInterval(Reg); 314 vrm_.grow(); 315 vrm_.assignVirt2StackSlot(Reg, vrm_.getStackSlot(curli)); 316 return &Intv; 317} 318 319VNInfo *SplitEditor::mapValue(VNInfo *dupliVNI) { 320 VNInfo *&VNI = valueMap_[dupliVNI]; 321 if (!VNI) 322 VNI = openli_->createValueCopy(dupliVNI, lis_.getVNInfoAllocator()); 323 return VNI; 324} 325 326/// Insert a COPY instruction curli -> li. Allocate a new value from li 327/// defined by the COPY. Note that rewrite() will deal with the curli 328/// register, so this function can be used to copy from any interval - openli, 329/// curli, or dupli. 330VNInfo *SplitEditor::insertCopy(LiveInterval &LI, 331 MachineBasicBlock &MBB, 332 MachineBasicBlock::iterator I) { 333 unsigned curli = sa_.getCurLI()->reg; 334 MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY), 335 LI.reg).addReg(curli); 336 SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 337 return LI.getNextValue(DefIdx, MI, true, lis_.getVNInfoAllocator()); 338} 339 340/// Create a new virtual register and live interval. 341void SplitEditor::openIntv() { 342 assert(!openli_ && "Previous LI not closed before openIntv"); 343 openli_ = createInterval(); 344 intervals_.push_back(openli_); 345 liveThrough_ = false; 346} 347 348/// enterIntvAtEnd - Enter openli at the end of MBB. 349/// PhiMBB is a successor inside openli where a PHI value is created. 350/// Currently, all entries must share the same PhiMBB. 351void SplitEditor::enterIntvAtEnd(MachineBasicBlock &A, MachineBasicBlock &B) { 352 assert(openli_ && "openIntv not called before enterIntvAtEnd"); 353 354 SlotIndex EndA = lis_.getMBBEndIdx(&A); 355 VNInfo *DupVNIA = dupli_->getVNInfoAt(EndA.getPrevIndex()); 356 if (!DupVNIA) { 357 DEBUG(dbgs() << " ignoring enterIntvAtEnd, dupli not live out of BB#" 358 << A.getNumber() << ".\n"); 359 return; 360 } 361 362 // Add a phi kill value and live range out of A. 363 VNInfo *VNIA = insertCopy(*openli_, A, A.getFirstTerminator()); 364 openli_->addRange(LiveRange(VNIA->def, EndA, VNIA)); 365 366 // FIXME: If this is the only entry edge, we don't need the extra PHI value. 367 // FIXME: If there are multiple entry blocks (so not a loop), we need proper 368 // SSA update. 369 370 // Now look at the start of B. 371 SlotIndex StartB = lis_.getMBBStartIdx(&B); 372 SlotIndex EndB = lis_.getMBBEndIdx(&B); 373 LiveRange *DupB = dupli_->getLiveRangeContaining(StartB); 374 if (!DupB) { 375 DEBUG(dbgs() << " enterIntvAtEnd: dupli not live in to BB#" 376 << B.getNumber() << ".\n"); 377 return; 378 } 379 380 VNInfo *VNIB = openli_->getVNInfoAt(StartB); 381 if (!VNIB) { 382 // Create a phi value. 383 VNIB = openli_->getNextValue(SlotIndex(StartB, true), 0, false, 384 lis_.getVNInfoAllocator()); 385 VNIB->setIsPHIDef(true); 386 // Add a minimal range for the new value. 387 openli_->addRange(LiveRange(VNIB->def, std::min(EndB, DupB->end), VNIB)); 388 389 VNInfo *&mapVNI = valueMap_[DupB->valno]; 390 if (mapVNI) { 391 // Multiple copies - must create PHI value. 392 abort(); 393 } else { 394 // This is the first copy of dupLR. Mark the mapping. 395 mapVNI = VNIB; 396 } 397 398 } 399 400 DEBUG(dbgs() << " enterIntvAtEnd: " << *openli_ << '\n'); 401} 402 403/// useIntv - indicate that all instructions in MBB should use openli. 404void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 405 useIntv(lis_.getMBBStartIdx(&MBB), lis_.getMBBEndIdx(&MBB)); 406} 407 408void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 409 assert(openli_ && "openIntv not called before useIntv"); 410 411 // Map the dupli values from the interval into openli_ 412 LiveInterval::const_iterator B = dupli_->begin(), E = dupli_->end(); 413 LiveInterval::const_iterator I = std::lower_bound(B, E, Start); 414 415 if (I != B) { 416 --I; 417 // I begins before Start, but overlaps. openli may already have a value. 418 if (I->end > Start && !openli_->liveAt(Start)) 419 openli_->addRange(LiveRange(Start, std::min(End, I->end), 420 mapValue(I->valno))); 421 ++I; 422 } 423 424 // The remaining ranges begin after Start. 425 for (;I != E && I->start < End; ++I) 426 openli_->addRange(LiveRange(I->start, std::min(End, I->end), 427 mapValue(I->valno))); 428 DEBUG(dbgs() << " added range [" << Start << ';' << End << "): " << *openli_ 429 << '\n'); 430} 431 432/// leaveIntvAtTop - Leave the interval at the top of MBB. 433/// Currently, only one value can leave the interval. 434void SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 435 assert(openli_ && "openIntv not called before leaveIntvAtTop"); 436 437 SlotIndex Start = lis_.getMBBStartIdx(&MBB); 438 LiveRange *DupLR = dupli_->getLiveRangeContaining(Start); 439 440 // Is dupli even live-in to MBB? 441 if (!DupLR) { 442 DEBUG(dbgs() << " leaveIntvAtTop at " << Start << ": not live\n"); 443 return; 444 } 445 446 // Is dupli defined by PHI at the beginning of MBB? 447 bool isPHIDef = DupLR->valno->isPHIDef() && 448 DupLR->valno->def.getBaseIndex() == Start; 449 450 // If MBB is using a value of dupli that was defined outside the openli range, 451 // we don't want to copy it back here. 452 if (!isPHIDef && !openli_->liveAt(DupLR->valno->def)) { 453 DEBUG(dbgs() << " leaveIntvAtTop at " << Start 454 << ": using external value\n"); 455 liveThrough_ = true; 456 return; 457 } 458 459 // Insert the COPY instruction. 460 MachineInstr *MI = BuildMI(MBB, MBB.begin(), DebugLoc(), 461 tii_.get(TargetOpcode::COPY), dupli_->reg) 462 .addReg(openli_->reg); 463 SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 464 465 // Adjust dupli and openli values. 466 if (isPHIDef) { 467 // dupli was already a PHI on entry to MBB. Simply insert an openli PHI, 468 // and shift the dupli def down to the COPY. 469 VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false, 470 lis_.getVNInfoAllocator()); 471 VNI->setIsPHIDef(true); 472 openli_->addRange(LiveRange(VNI->def, Idx, VNI)); 473 474 dupli_->removeRange(Start, Idx); 475 DupLR->valno->def = Idx; 476 DupLR->valno->setIsPHIDef(false); 477 } else { 478 // The dupli value was defined somewhere inside the openli range. 479 DEBUG(dbgs() << " leaveIntvAtTop source value defined at " 480 << DupLR->valno->def << "\n"); 481 // FIXME: We may not need a PHI here if all predecessors have the same 482 // value. 483 VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false, 484 lis_.getVNInfoAllocator()); 485 VNI->setIsPHIDef(true); 486 openli_->addRange(LiveRange(VNI->def, Idx, VNI)); 487 488 // FIXME: What if DupLR->valno is used by multiple exits? SSA Update. 489 490 // closeIntv is going to remove the superfluous live ranges. 491 DupLR->valno->def = Idx; 492 DupLR->valno->setIsPHIDef(false); 493 } 494 495 DEBUG(dbgs() << " leaveIntvAtTop at " << Idx << ": " << *openli_ << '\n'); 496} 497 498/// closeIntv - Indicate that we are done editing the currently open 499/// LiveInterval, and ranges can be trimmed. 500void SplitEditor::closeIntv() { 501 assert(openli_ && "openIntv not called before closeIntv"); 502 503 DEBUG(dbgs() << " closeIntv cleaning up\n"); 504 505 DEBUG(dbgs() << " dup " << *dupli_ << '\n'); 506 DEBUG(dbgs() << " open " << *openli_ << '\n'); 507 508 if (liveThrough_) { 509 DEBUG(dbgs() << " value live through region, leaving dupli as is.\n"); 510 } else { 511 // live out with copies inserted, or killed by region. Either way we need to 512 // remove the overlapping region from dupli. 513 for (LiveInterval::iterator I = openli_->begin(), E = openli_->end(); 514 I != E; ++I) { 515 dupli_->removeRange(I->start, I->end); 516 } 517 // FIXME: A block branching to the entry block may also branch elsewhere 518 // curli is live. We need both openli and curli to be live in that case. 519 DEBUG(dbgs() << " dup2 " << *dupli_ << '\n'); 520 } 521 openli_ = 0; 522} 523 524/// rewrite - after all the new live ranges have been created, rewrite 525/// instructions using curli to use the new intervals. 526void SplitEditor::rewrite() { 527 assert(!openli_ && "Previous LI not closed before rewrite"); 528 const LiveInterval *curli = sa_.getCurLI(); 529 for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(curli->reg), 530 RE = mri_.reg_end(); RI != RE;) { 531 MachineOperand &MO = RI.getOperand(); 532 MachineInstr *MI = MO.getParent(); 533 ++RI; 534 if (MI->isDebugValue()) { 535 DEBUG(dbgs() << "Zapping " << *MI); 536 // FIXME: We can do much better with debug values. 537 MO.setReg(0); 538 continue; 539 } 540 SlotIndex Idx = lis_.getInstructionIndex(MI); 541 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 542 LiveInterval *LI = dupli_; 543 for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) { 544 LiveInterval *testli = intervals_[i]; 545 if (testli->liveAt(Idx)) { 546 LI = testli; 547 break; 548 } 549 } 550 if (LI) 551 MO.setReg(LI->reg); 552 DEBUG(dbgs() << "rewrite " << Idx << '\t' << *MI); 553 } 554 555 // dupli_ goes in last, after rewriting. 556 if (dupli_) { 557 dupli_->RenumberValues(); 558 intervals_.push_back(dupli_); 559 } 560 561 // FIXME: *Calculate spill weights, allocation hints, and register classes for 562 // firstInterval.. 563} 564 565 566//===----------------------------------------------------------------------===// 567// Loop Splitting 568//===----------------------------------------------------------------------===// 569 570void SplitEditor::splitAroundLoop(const MachineLoop *Loop) { 571 SplitAnalysis::LoopBlocks Blocks; 572 sa_.getLoopBlocks(Loop, Blocks); 573 574 // Break critical edges as needed. 575 SplitAnalysis::BlockPtrSet CriticalExits; 576 sa_.getCriticalExits(Blocks, CriticalExits); 577 assert(CriticalExits.empty() && "Cannot break critical exits yet"); 578 579 // Create new live interval for the loop. 580 openIntv(); 581 582 // Insert copies in the predecessors. 583 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(), 584 E = Blocks.Preds.end(); I != E; ++I) { 585 MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I); 586 enterIntvAtEnd(MBB, *Loop->getHeader()); 587 } 588 589 // Switch all loop blocks. 590 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Loop.begin(), 591 E = Blocks.Loop.end(); I != E; ++I) 592 useIntv(**I); 593 594 // Insert back copies in the exit blocks. 595 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Exits.begin(), 596 E = Blocks.Exits.end(); I != E; ++I) { 597 MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I); 598 leaveIntvAtTop(MBB); 599 } 600 601 // Done. 602 closeIntv(); 603 rewrite(); 604} 605 606