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