SplitKit.cpp revision 9820ef1382ece54ec8143a62226db4f4a2872181 
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.\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() << "  multiple exits from " << **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() << "  contained in " << **I);
242      continue;
243    case SinglePeripheral:
244      DEBUG(dbgs() << "  single peripheral use in " << **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 from "
250                 << **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() << "  getBestSplitLoop found " << Loops.size() << " + "
259               << SecondLoops.size() << " 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() << "  getBestSplitLoop found " << *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  }
349  return dupli_;
350}
351
352VNInfo *SplitEditor::mapValue(const VNInfo *curliVNI) {
353  VNInfo *&VNI = valueMap_[curliVNI];
354  if (!VNI)
355    VNI = openli_->createValueCopy(curliVNI, lis_.getVNInfoAllocator());
356  return VNI;
357}
358
359/// Insert a COPY instruction curli -> li. Allocate a new value from li
360/// defined by the COPY. Note that rewrite() will deal with the curli
361/// register, so this function can be used to copy from any interval - openli,
362/// curli, or dupli.
363VNInfo *SplitEditor::insertCopy(LiveInterval &LI,
364                                MachineBasicBlock &MBB,
365                                MachineBasicBlock::iterator I) {
366  MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY),
367                             LI.reg).addReg(curli_->reg);
368  SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
369  return LI.getNextValue(DefIdx, MI, true, lis_.getVNInfoAllocator());
370}
371
372/// Create a new virtual register and live interval.
373void SplitEditor::openIntv() {
374  assert(!openli_ && "Previous LI not closed before openIntv");
375  openli_ = createInterval();
376  intervals_.push_back(openli_);
377  liveThrough_ = false;
378}
379
380/// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
381/// not live before Idx, a COPY is not inserted.
382void SplitEditor::enterIntvBefore(SlotIndex Idx) {
383  assert(openli_ && "openIntv not called before enterIntvBefore");
384
385  // Copy from curli_ if it is live.
386  if (VNInfo *CurVNI = curli_->getVNInfoAt(Idx.getUseIndex())) {
387    MachineInstr *MI = lis_.getInstructionFromIndex(Idx);
388    assert(MI && "enterIntvBefore called with invalid index");
389    VNInfo *VNI = insertCopy(*openli_, *MI->getParent(), MI);
390    openli_->addRange(LiveRange(VNI->def, Idx.getDefIndex(), VNI));
391
392    // Make sure CurVNI is properly mapped.
393    VNInfo *&mapVNI = valueMap_[CurVNI];
394    // We dont have SSA update yet, so only one entry per value is allowed.
395    assert(!mapVNI && "enterIntvBefore called more than once for the same value");
396    mapVNI = VNI;
397  }
398  DEBUG(dbgs() << "    enterIntvBefore " << Idx << ": " << *openli_ << '\n');
399}
400
401/// enterIntvAtEnd - Enter openli at the end of MBB.
402/// PhiMBB is a successor inside openli where a PHI value is created.
403/// Currently, all entries must share the same PhiMBB.
404void SplitEditor::enterIntvAtEnd(MachineBasicBlock &A, MachineBasicBlock &B) {
405  assert(openli_ && "openIntv not called before enterIntvAtEnd");
406
407  SlotIndex EndA = lis_.getMBBEndIdx(&A);
408  VNInfo *CurVNIA = curli_->getVNInfoAt(EndA.getPrevIndex());
409  if (!CurVNIA) {
410    DEBUG(dbgs() << "    enterIntvAtEnd, curli not live out of BB#"
411                 << A.getNumber() << ".\n");
412    return;
413  }
414
415  // Add a phi kill value and live range out of A.
416  VNInfo *VNIA = insertCopy(*openli_, A, A.getFirstTerminator());
417  openli_->addRange(LiveRange(VNIA->def, EndA, VNIA));
418
419  // FIXME: If this is the only entry edge, we don't need the extra PHI value.
420  // FIXME: If there are multiple entry blocks (so not a loop), we need proper
421  // SSA update.
422
423  // Now look at the start of B.
424  SlotIndex StartB = lis_.getMBBStartIdx(&B);
425  SlotIndex EndB = lis_.getMBBEndIdx(&B);
426  const LiveRange *CurB = curli_->getLiveRangeContaining(StartB);
427  if (!CurB) {
428    DEBUG(dbgs() << "    enterIntvAtEnd: curli not live in to BB#"
429                 << B.getNumber() << ".\n");
430    return;
431  }
432
433  VNInfo *VNIB = openli_->getVNInfoAt(StartB);
434  if (!VNIB) {
435    // Create a phi value.
436    VNIB = openli_->getNextValue(SlotIndex(StartB, true), 0, false,
437                                 lis_.getVNInfoAllocator());
438    VNIB->setIsPHIDef(true);
439    // Add a minimal range for the new value.
440    openli_->addRange(LiveRange(VNIB->def, std::min(EndB, CurB->end), VNIB));
441
442    VNInfo *&mapVNI = valueMap_[CurB->valno];
443    if (mapVNI) {
444      // Multiple copies - must create PHI value.
445      abort();
446    } else {
447      // This is the first copy of dupLR. Mark the mapping.
448      mapVNI = VNIB;
449    }
450
451  }
452
453  DEBUG(dbgs() << "    enterIntvAtEnd: " << *openli_ << '\n');
454}
455
456/// useIntv - indicate that all instructions in MBB should use openli.
457void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
458  useIntv(lis_.getMBBStartIdx(&MBB), lis_.getMBBEndIdx(&MBB));
459}
460
461void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
462  assert(openli_ && "openIntv not called before useIntv");
463
464  // Map the curli values from the interval into openli_
465  LiveInterval::const_iterator B = curli_->begin(), E = curli_->end();
466  LiveInterval::const_iterator I = std::lower_bound(B, E, Start);
467
468  if (I != B) {
469    --I;
470    // I begins before Start, but overlaps. openli may already have a value.
471    if (I->end > Start && !openli_->liveAt(Start))
472      openli_->addRange(LiveRange(Start, std::min(End, I->end),
473                        mapValue(I->valno)));
474    ++I;
475  }
476
477  // The remaining ranges begin after Start.
478  for (;I != E && I->start < End; ++I)
479    openli_->addRange(LiveRange(I->start, std::min(End, I->end),
480                                mapValue(I->valno)));
481  DEBUG(dbgs() << "    use [" << Start << ';' << End << "): " << *openli_
482               << '\n');
483}
484
485/// leaveIntvAfter - Leave openli after the instruction at Idx.
486void SplitEditor::leaveIntvAfter(SlotIndex Idx) {
487  assert(openli_ && "openIntv not called before leaveIntvAfter");
488
489  const LiveRange *CurLR = curli_->getLiveRangeContaining(Idx.getDefIndex());
490  if (!CurLR || CurLR->end <= Idx.getBoundaryIndex()) {
491    DEBUG(dbgs() << "    leaveIntvAfter " << Idx << ": not live\n");
492    return;
493  }
494
495  // Was this value of curli live through openli?
496  if (!openli_->liveAt(CurLR->valno->def)) {
497    DEBUG(dbgs() << "    leaveIntvAfter " << Idx << ": using external value\n");
498    liveThrough_ = true;
499    return;
500  }
501
502  // We are going to insert a back copy, so we must have a dupli_.
503  LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Idx.getDefIndex());
504  assert(DupLR && "dupli not live into black, but curli is?");
505
506  // Insert the COPY instruction.
507  MachineBasicBlock::iterator I = lis_.getInstructionFromIndex(Idx);
508  MachineInstr *MI = BuildMI(*I->getParent(), llvm::next(I), I->getDebugLoc(),
509                             tii_.get(TargetOpcode::COPY), dupli_->reg)
510                       .addReg(openli_->reg);
511  SlotIndex CopyIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
512  openli_->addRange(LiveRange(Idx.getDefIndex(), CopyIdx,
513                    mapValue(CurLR->valno)));
514  DupLR->valno->def = CopyIdx;
515  DEBUG(dbgs() << "    leaveIntvAfter " << Idx << ": " << *openli_ << '\n');
516}
517
518/// leaveIntvAtTop - Leave the interval at the top of MBB.
519/// Currently, only one value can leave the interval.
520void SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
521  assert(openli_ && "openIntv not called before leaveIntvAtTop");
522
523  SlotIndex Start = lis_.getMBBStartIdx(&MBB);
524  const LiveRange *CurLR = curli_->getLiveRangeContaining(Start);
525
526  // Is curli even live-in to MBB?
527  if (!CurLR) {
528    DEBUG(dbgs() << "    leaveIntvAtTop at " << Start << ": not live\n");
529    return;
530  }
531
532  // Is curli defined by PHI at the beginning of MBB?
533  bool isPHIDef = CurLR->valno->isPHIDef() &&
534                  CurLR->valno->def.getBaseIndex() == Start;
535
536  // If MBB is using a value of curli that was defined outside the openli range,
537  // we don't want to copy it back here.
538  if (!isPHIDef && !openli_->liveAt(CurLR->valno->def)) {
539    DEBUG(dbgs() << "    leaveIntvAtTop at " << Start
540                 << ": using external value\n");
541    liveThrough_ = true;
542    return;
543  }
544
545  // We are going to insert a back copy, so we must have a dupli_.
546  LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Start);
547  assert(DupLR && "dupli not live into black, but curli is?");
548
549  // Insert the COPY instruction.
550  MachineInstr *MI = BuildMI(MBB, MBB.begin(), DebugLoc(),
551                             tii_.get(TargetOpcode::COPY), dupli_->reg)
552                       .addReg(openli_->reg);
553  SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
554
555  // Adjust dupli and openli values.
556  if (isPHIDef) {
557    // dupli was already a PHI on entry to MBB. Simply insert an openli PHI,
558    // and shift the dupli def down to the COPY.
559    VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false,
560                                        lis_.getVNInfoAllocator());
561    VNI->setIsPHIDef(true);
562    openli_->addRange(LiveRange(VNI->def, Idx, VNI));
563
564    dupli_->removeRange(Start, Idx);
565    DupLR->valno->def = Idx;
566    DupLR->valno->setIsPHIDef(false);
567  } else {
568    // The dupli value was defined somewhere inside the openli range.
569    DEBUG(dbgs() << "    leaveIntvAtTop source value defined at "
570                 << DupLR->valno->def << "\n");
571    // FIXME: We may not need a PHI here if all predecessors have the same
572    // value.
573    VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false,
574                                        lis_.getVNInfoAllocator());
575    VNI->setIsPHIDef(true);
576    openli_->addRange(LiveRange(VNI->def, Idx, VNI));
577
578    // FIXME: What if DupLR->valno is used by multiple exits? SSA Update.
579
580    // closeIntv is going to remove the superfluous live ranges.
581    DupLR->valno->def = Idx;
582    DupLR->valno->setIsPHIDef(false);
583  }
584
585  DEBUG(dbgs() << "    leaveIntvAtTop at " << Idx << ": " << *openli_ << '\n');
586}
587
588/// closeIntv - Indicate that we are done editing the currently open
589/// LiveInterval, and ranges can be trimmed.
590void SplitEditor::closeIntv() {
591  assert(openli_ && "openIntv not called before closeIntv");
592
593  DEBUG(dbgs() << "    closeIntv cleaning up\n");
594  DEBUG(dbgs() << "    open " << *openli_ << '\n');
595
596  if (liveThrough_) {
597    DEBUG(dbgs() << "    value live through region, leaving dupli as is.\n");
598  } else {
599    // live out with copies inserted, or killed by region. Either way we need to
600    // remove the overlapping region from dupli.
601    getDupLI();
602    for (LiveInterval::iterator I = openli_->begin(), E = openli_->end();
603         I != E; ++I) {
604      dupli_->removeRange(I->start, I->end);
605    }
606    // FIXME: A block branching to the entry block may also branch elsewhere
607    // curli is live. We need both openli and curli to be live in that case.
608    DEBUG(dbgs() << "    dup2 " << *dupli_ << '\n');
609  }
610  openli_ = 0;
611  valueMap_.clear();
612}
613
614/// rewrite - after all the new live ranges have been created, rewrite
615/// instructions using curli to use the new intervals.
616void SplitEditor::rewrite() {
617  assert(!openli_ && "Previous LI not closed before rewrite");
618  const LiveInterval *curli = sa_.getCurLI();
619  for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(curli->reg),
620       RE = mri_.reg_end(); RI != RE;) {
621    MachineOperand &MO = RI.getOperand();
622    MachineInstr *MI = MO.getParent();
623    ++RI;
624    if (MI->isDebugValue()) {
625      DEBUG(dbgs() << "Zapping " << *MI);
626      // FIXME: We can do much better with debug values.
627      MO.setReg(0);
628      continue;
629    }
630    SlotIndex Idx = lis_.getInstructionIndex(MI);
631    Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
632    LiveInterval *LI = dupli_;
633    for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) {
634      LiveInterval *testli = intervals_[i];
635      if (testli->liveAt(Idx)) {
636        LI = testli;
637        break;
638      }
639    }
640    if (LI) {
641      MO.setReg(LI->reg);
642      DEBUG(dbgs() << "  rewrite " << Idx << '\t' << *MI);
643    }
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 interval " << 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