SplitKit.cpp revision f1b05f2b0ef48cb80b064e2f792b38c626822fc0 
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/// getMultiUseBlocks - if curli has more than one use in a basic block, it
283/// may be an advantage to split curli for the duration of the block.
284bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
285  // If curli is local to one block, there is no point to splitting it.
286  if (usingBlocks_.size() <= 1)
287    return false;
288  // Add blocks with multiple uses.
289  for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
290       I != E; ++I)
291    switch (I->second) {
292    case 0:
293    case 1:
294      continue;
295    case 2: {
296      // It doesn't pay to split a 2-instr block if it redefines curli.
297      VNInfo *VN1 = curli_->getVNInfoAt(lis_.getMBBStartIdx(I->first));
298      VNInfo *VN2 =
299        curli_->getVNInfoAt(lis_.getMBBEndIdx(I->first).getPrevIndex());
300      // live-in and live-out with a different value.
301      if (VN1 && VN2 && VN1 != VN2)
302        continue;
303    } // Fall through.
304    default:
305      Blocks.insert(I->first);
306    }
307  return !Blocks.empty();
308}
309
310//===----------------------------------------------------------------------===//
311//                               Split Editor
312//===----------------------------------------------------------------------===//
313
314/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
315SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
316                         std::vector<LiveInterval*> &intervals)
317  : sa_(sa), lis_(lis), vrm_(vrm),
318    mri_(vrm.getMachineFunction().getRegInfo()),
319    tii_(*vrm.getMachineFunction().getTarget().getInstrInfo()),
320    curli_(sa_.getCurLI()),
321    dupli_(0), openli_(0),
322    intervals_(intervals),
323    firstInterval(intervals_.size())
324{
325  assert(curli_ && "SplitEditor created from empty SplitAnalysis");
326
327  // Make sure curli_ is assigned a stack slot, so all our intervals get the
328  // same slot as curli_.
329  if (vrm_.getStackSlot(curli_->reg) == VirtRegMap::NO_STACK_SLOT)
330    vrm_.assignVirt2StackSlot(curli_->reg);
331
332}
333
334LiveInterval *SplitEditor::createInterval() {
335  unsigned curli = sa_.getCurLI()->reg;
336  unsigned Reg = mri_.createVirtualRegister(mri_.getRegClass(curli));
337  LiveInterval &Intv = lis_.getOrCreateInterval(Reg);
338  vrm_.grow();
339  vrm_.assignVirt2StackSlot(Reg, vrm_.getStackSlot(curli));
340  return &Intv;
341}
342
343LiveInterval *SplitEditor::getDupLI() {
344  if (!dupli_) {
345    // Create an interval for dupli that is a copy of curli.
346    dupli_ = createInterval();
347    dupli_->Copy(*curli_, &mri_, lis_.getVNInfoAllocator());
348    DEBUG(dbgs() << "SplitEditor DupLI: " << *dupli_ << '\n');
349  }
350  return dupli_;
351}
352
353VNInfo *SplitEditor::mapValue(const VNInfo *curliVNI) {
354  VNInfo *&VNI = valueMap_[curliVNI];
355  if (!VNI)
356    VNI = openli_->createValueCopy(curliVNI, lis_.getVNInfoAllocator());
357  return VNI;
358}
359
360/// Insert a COPY instruction curli -> li. Allocate a new value from li
361/// defined by the COPY. Note that rewrite() will deal with the curli
362/// register, so this function can be used to copy from any interval - openli,
363/// curli, or dupli.
364VNInfo *SplitEditor::insertCopy(LiveInterval &LI,
365                                MachineBasicBlock &MBB,
366                                MachineBasicBlock::iterator I) {
367  MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY),
368                             LI.reg).addReg(curli_->reg);
369  SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
370  return LI.getNextValue(DefIdx, MI, true, lis_.getVNInfoAllocator());
371}
372
373/// Create a new virtual register and live interval.
374void SplitEditor::openIntv() {
375  assert(!openli_ && "Previous LI not closed before openIntv");
376  openli_ = createInterval();
377  intervals_.push_back(openli_);
378  liveThrough_ = false;
379}
380
381/// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
382/// not live before Idx, a COPY is not inserted.
383void SplitEditor::enterIntvBefore(SlotIndex Idx) {
384  assert(openli_ && "openIntv not called before enterIntvBefore");
385
386  // Copy from curli_ if it is live.
387  if (VNInfo *CurVNI = curli_->getVNInfoAt(Idx.getUseIndex())) {
388    MachineInstr *MI = lis_.getInstructionFromIndex(Idx);
389    assert(MI && "enterIntvBefore called with invalid index");
390    VNInfo *VNI = insertCopy(*openli_, *MI->getParent(), MI);
391    openli_->addRange(LiveRange(VNI->def, Idx.getDefIndex(), VNI));
392
393    // Make sure CurVNI is properly mapped.
394    VNInfo *&mapVNI = valueMap_[CurVNI];
395    // We dont have SSA update yet, so only one entry per value is allowed.
396    assert(!mapVNI && "enterIntvBefore called more than once for the same value");
397    mapVNI = VNI;
398  }
399  DEBUG(dbgs() << "  enterIntvBefore " << Idx << ": " << *openli_ << '\n');
400}
401
402/// enterIntvAtEnd - Enter openli at the end of MBB.
403/// PhiMBB is a successor inside openli where a PHI value is created.
404/// Currently, all entries must share the same PhiMBB.
405void SplitEditor::enterIntvAtEnd(MachineBasicBlock &A, MachineBasicBlock &B) {
406  assert(openli_ && "openIntv not called before enterIntvAtEnd");
407
408  SlotIndex EndA = lis_.getMBBEndIdx(&A);
409  VNInfo *CurVNIA = curli_->getVNInfoAt(EndA.getPrevIndex());
410  if (!CurVNIA) {
411    DEBUG(dbgs() << "  ignoring enterIntvAtEnd, curli not live out of BB#"
412                 << A.getNumber() << ".\n");
413    return;
414  }
415
416  // Add a phi kill value and live range out of A.
417  VNInfo *VNIA = insertCopy(*openli_, A, A.getFirstTerminator());
418  openli_->addRange(LiveRange(VNIA->def, EndA, VNIA));
419
420  // FIXME: If this is the only entry edge, we don't need the extra PHI value.
421  // FIXME: If there are multiple entry blocks (so not a loop), we need proper
422  // SSA update.
423
424  // Now look at the start of B.
425  SlotIndex StartB = lis_.getMBBStartIdx(&B);
426  SlotIndex EndB = lis_.getMBBEndIdx(&B);
427  const LiveRange *CurB = curli_->getLiveRangeContaining(StartB);
428  if (!CurB) {
429    DEBUG(dbgs() << "  enterIntvAtEnd: curli not live in to BB#"
430                 << B.getNumber() << ".\n");
431    return;
432  }
433
434  VNInfo *VNIB = openli_->getVNInfoAt(StartB);
435  if (!VNIB) {
436    // Create a phi value.
437    VNIB = openli_->getNextValue(SlotIndex(StartB, true), 0, false,
438                                 lis_.getVNInfoAllocator());
439    VNIB->setIsPHIDef(true);
440    // Add a minimal range for the new value.
441    openli_->addRange(LiveRange(VNIB->def, std::min(EndB, CurB->end), VNIB));
442
443    VNInfo *&mapVNI = valueMap_[CurB->valno];
444    if (mapVNI) {
445      // Multiple copies - must create PHI value.
446      abort();
447    } else {
448      // This is the first copy of dupLR. Mark the mapping.
449      mapVNI = VNIB;
450    }
451
452  }
453
454  DEBUG(dbgs() << "  enterIntvAtEnd: " << *openli_ << '\n');
455}
456
457/// useIntv - indicate that all instructions in MBB should use openli.
458void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
459  useIntv(lis_.getMBBStartIdx(&MBB), lis_.getMBBEndIdx(&MBB));
460}
461
462void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
463  assert(openli_ && "openIntv not called before useIntv");
464
465  // Map the curli values from the interval into openli_
466  LiveInterval::const_iterator B = curli_->begin(), E = curli_->end();
467  LiveInterval::const_iterator I = std::lower_bound(B, E, Start);
468
469  if (I != B) {
470    --I;
471    // I begins before Start, but overlaps. openli may already have a value.
472    if (I->end > Start && !openli_->liveAt(Start))
473      openli_->addRange(LiveRange(Start, std::min(End, I->end),
474                        mapValue(I->valno)));
475    ++I;
476  }
477
478  // The remaining ranges begin after Start.
479  for (;I != E && I->start < End; ++I)
480    openli_->addRange(LiveRange(I->start, std::min(End, I->end),
481                                mapValue(I->valno)));
482  DEBUG(dbgs() << "  added range [" << Start << ';' << End << "): " << *openli_
483               << '\n');
484}
485
486/// leaveIntvAfter - Leave openli after the instruction at Idx.
487void SplitEditor::leaveIntvAfter(SlotIndex Idx) {
488  assert(openli_ && "openIntv not called before leaveIntvAfter");
489
490  const LiveRange *CurLR = curli_->getLiveRangeContaining(Idx.getDefIndex());
491  if (!CurLR || CurLR->end <= Idx.getBoundaryIndex()) {
492    DEBUG(dbgs() << "  leaveIntvAfter at " << Idx << ": not live\n");
493    return;
494  }
495
496  // Was this value of curli live through openli?
497  if (!openli_->liveAt(CurLR->valno->def)) {
498    DEBUG(dbgs() << "  leaveIntvAfter " << Idx << ": using external value\n");
499    liveThrough_ = true;
500    return;
501  }
502
503  // We are going to insert a back copy, so we must have a dupli_.
504  LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Idx.getDefIndex());
505  assert(DupLR && "dupli not live into black, but curli is?");
506
507  // Insert the COPY instruction.
508  MachineBasicBlock::iterator I = lis_.getInstructionFromIndex(Idx);
509  MachineInstr *MI = BuildMI(*I->getParent(), llvm::next(I), I->getDebugLoc(),
510                             tii_.get(TargetOpcode::COPY), dupli_->reg)
511                       .addReg(openli_->reg);
512  SlotIndex CopyIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
513  openli_->addRange(LiveRange(Idx.getDefIndex(), CopyIdx,
514                    mapValue(CurLR->valno)));
515  DupLR->valno->def = CopyIdx;
516  DEBUG(dbgs() << "  leaveIntvAfter " << Idx << ": " << *openli_ << '\n');
517}
518
519/// leaveIntvAtTop - Leave the interval at the top of MBB.
520/// Currently, only one value can leave the interval.
521void SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
522  assert(openli_ && "openIntv not called before leaveIntvAtTop");
523
524  SlotIndex Start = lis_.getMBBStartIdx(&MBB);
525  const LiveRange *CurLR = curli_->getLiveRangeContaining(Start);
526
527  // Is curli even live-in to MBB?
528  if (!CurLR) {
529    DEBUG(dbgs() << "  leaveIntvAtTop at " << Start << ": not live\n");
530    return;
531  }
532
533  // Is curli defined by PHI at the beginning of MBB?
534  bool isPHIDef = CurLR->valno->isPHIDef() &&
535                  CurLR->valno->def.getBaseIndex() == Start;
536
537  // If MBB is using a value of curli that was defined outside the openli range,
538  // we don't want to copy it back here.
539  if (!isPHIDef && !openli_->liveAt(CurLR->valno->def)) {
540    DEBUG(dbgs() << "  leaveIntvAtTop at " << Start
541                 << ": using external value\n");
542    liveThrough_ = true;
543    return;
544  }
545
546  // We are going to insert a back copy, so we must have a dupli_.
547  LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Start);
548  assert(DupLR && "dupli not live into black, but curli is?");
549
550  // Insert the COPY instruction.
551  MachineInstr *MI = BuildMI(MBB, MBB.begin(), DebugLoc(),
552                             tii_.get(TargetOpcode::COPY), dupli_->reg)
553                       .addReg(openli_->reg);
554  SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
555
556  // Adjust dupli and openli values.
557  if (isPHIDef) {
558    // dupli was already a PHI on entry to MBB. Simply insert an openli PHI,
559    // and shift the dupli def down to the COPY.
560    VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false,
561                                        lis_.getVNInfoAllocator());
562    VNI->setIsPHIDef(true);
563    openli_->addRange(LiveRange(VNI->def, Idx, VNI));
564
565    dupli_->removeRange(Start, Idx);
566    DupLR->valno->def = Idx;
567    DupLR->valno->setIsPHIDef(false);
568  } else {
569    // The dupli value was defined somewhere inside the openli range.
570    DEBUG(dbgs() << "  leaveIntvAtTop source value defined at "
571                 << DupLR->valno->def << "\n");
572    // FIXME: We may not need a PHI here if all predecessors have the same
573    // value.
574    VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false,
575                                        lis_.getVNInfoAllocator());
576    VNI->setIsPHIDef(true);
577    openli_->addRange(LiveRange(VNI->def, Idx, VNI));
578
579    // FIXME: What if DupLR->valno is used by multiple exits? SSA Update.
580
581    // closeIntv is going to remove the superfluous live ranges.
582    DupLR->valno->def = Idx;
583    DupLR->valno->setIsPHIDef(false);
584  }
585
586  DEBUG(dbgs() << "  leaveIntvAtTop at " << Idx << ": " << *openli_ << '\n');
587}
588
589/// closeIntv - Indicate that we are done editing the currently open
590/// LiveInterval, and ranges can be trimmed.
591void SplitEditor::closeIntv() {
592  assert(openli_ && "openIntv not called before closeIntv");
593
594  DEBUG(dbgs() << "  closeIntv cleaning up\n");
595  DEBUG(dbgs() << "    open " << *openli_ << '\n');
596
597  if (liveThrough_) {
598    DEBUG(dbgs() << "  value live through region, leaving dupli as is.\n");
599  } else {
600    // live out with copies inserted, or killed by region. Either way we need to
601    // remove the overlapping region from dupli.
602    getDupLI();
603    for (LiveInterval::iterator I = openli_->begin(), E = openli_->end();
604         I != E; ++I) {
605      dupli_->removeRange(I->start, I->end);
606    }
607    // FIXME: A block branching to the entry block may also branch elsewhere
608    // curli is live. We need both openli and curli to be live in that case.
609    DEBUG(dbgs() << "    dup2 " << *dupli_ << '\n');
610  }
611  openli_ = 0;
612  valueMap_.clear();
613}
614
615/// rewrite - after all the new live ranges have been created, rewrite
616/// instructions using curli to use the new intervals.
617void SplitEditor::rewrite() {
618  assert(!openli_ && "Previous LI not closed before rewrite");
619  const LiveInterval *curli = sa_.getCurLI();
620  for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(curli->reg),
621       RE = mri_.reg_end(); RI != RE;) {
622    MachineOperand &MO = RI.getOperand();
623    MachineInstr *MI = MO.getParent();
624    ++RI;
625    if (MI->isDebugValue()) {
626      DEBUG(dbgs() << "Zapping " << *MI);
627      // FIXME: We can do much better with debug values.
628      MO.setReg(0);
629      continue;
630    }
631    SlotIndex Idx = lis_.getInstructionIndex(MI);
632    Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
633    LiveInterval *LI = dupli_;
634    for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) {
635      LiveInterval *testli = intervals_[i];
636      if (testli->liveAt(Idx)) {
637        LI = testli;
638        break;
639      }
640    }
641    if (LI)
642      MO.setReg(LI->reg);
643    DEBUG(dbgs() << "rewrite " << Idx << '\t' << *MI);
644  }
645
646  // dupli_ goes in last, after rewriting.
647  if (dupli_) {
648    dupli_->RenumberValues();
649    intervals_.push_back(dupli_);
650  }
651
652  // Calculate spill weight and allocation hints for new intervals.
653  VirtRegAuxInfo vrai(vrm_.getMachineFunction(), lis_, sa_.loops_);
654  for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) {
655    LiveInterval &li = *intervals_[i];
656    vrai.CalculateRegClass(li.reg);
657    vrai.CalculateWeightAndHint(li);
658    DEBUG(dbgs() << "new intv " << mri_.getRegClass(li.reg)->getName() << ":"
659                 << li << '\n');
660  }
661}
662
663
664//===----------------------------------------------------------------------===//
665//                               Loop Splitting
666//===----------------------------------------------------------------------===//
667
668bool SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
669  SplitAnalysis::LoopBlocks Blocks;
670  sa_.getLoopBlocks(Loop, Blocks);
671
672  // Break critical edges as needed.
673  SplitAnalysis::BlockPtrSet CriticalExits;
674  sa_.getCriticalExits(Blocks, CriticalExits);
675  assert(CriticalExits.empty() && "Cannot break critical exits yet");
676
677  // Create new live interval for the loop.
678  openIntv();
679
680  // Insert copies in the predecessors.
681  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
682       E = Blocks.Preds.end(); I != E; ++I) {
683    MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
684    enterIntvAtEnd(MBB, *Loop->getHeader());
685  }
686
687  // Switch all loop blocks.
688  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Loop.begin(),
689       E = Blocks.Loop.end(); I != E; ++I)
690     useIntv(**I);
691
692  // Insert back copies in the exit blocks.
693  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Exits.begin(),
694       E = Blocks.Exits.end(); I != E; ++I) {
695    MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
696    leaveIntvAtTop(MBB);
697  }
698
699  // Done.
700  closeIntv();
701  rewrite();
702  return dupli_;
703}
704
705
706//===----------------------------------------------------------------------===//
707//                            Single Block Splitting
708//===----------------------------------------------------------------------===//
709
710/// splitSingleBlocks - Split curli into a separate live interval inside each
711/// basic block in Blocks. Return true if curli has been completely replaced,
712/// false if curli is still intact, and needs to be spilled or split further.
713bool SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
714  DEBUG(dbgs() << "splitSingleBlocks for " << Blocks.size() << " blocks.\n");
715  // Determine the first and last instruction using curli in each block.
716  typedef std::pair<SlotIndex,SlotIndex> IndexPair;
717  typedef DenseMap<const MachineBasicBlock*,IndexPair> IndexPairMap;
718  IndexPairMap MBBRange;
719  for (SplitAnalysis::InstrPtrSet::const_iterator I = sa_.usingInstrs_.begin(),
720       E = sa_.usingInstrs_.end(); I != E; ++I) {
721    const MachineBasicBlock *MBB = (*I)->getParent();
722    if (!Blocks.count(MBB))
723      continue;
724    SlotIndex Idx = lis_.getInstructionIndex(*I);
725    DEBUG(dbgs() << "BB#" << MBB->getNumber() << '\t' << Idx << '\t' << **I);
726    IndexPair &IP = MBBRange[MBB];
727    if (!IP.first.isValid() || Idx < IP.first)
728      IP.first = Idx;
729    if (!IP.second.isValid() || Idx > IP.second)
730      IP.second = Idx;
731  }
732
733  // Create a new interval for each block.
734  for (SplitAnalysis::BlockPtrSet::const_iterator I = Blocks.begin(),
735       E = Blocks.end(); I != E; ++I) {
736    IndexPair &IP = MBBRange[*I];
737    DEBUG(dbgs() << "Splitting for BB#" << (*I)->getNumber() << ": ["
738                 << IP.first << ';' << IP.second << ")\n");
739    assert(IP.first.isValid() && IP.second.isValid());
740
741    openIntv();
742    enterIntvBefore(IP.first);
743    useIntv(IP.first.getBaseIndex(), IP.second.getBoundaryIndex());
744    leaveIntvAfter(IP.second);
745    closeIntv();
746  }
747  rewrite();
748  return dupli_;
749}
750
751