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