SplitKit.cpp revision 2debd48ca790ac01be6e12e094fdf4fdcadc8364 
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 "regalloc"
16#include "SplitKit.h"
17#include "LiveRangeEdit.h"
18#include "VirtRegMap.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/CodeGen/LiveIntervalAnalysis.h"
21#include "llvm/CodeGen/MachineDominators.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/MachineLoopInfo.h"
24#include "llvm/CodeGen/MachineRegisterInfo.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
32STATISTIC(NumFinished, "Number of splits finished");
33STATISTIC(NumSimple,   "Number of splits that were simple");
34STATISTIC(NumCopies,   "Number of copies inserted for splitting");
35STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
36STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
37
38//===----------------------------------------------------------------------===//
39//                                 Split Analysis
40//===----------------------------------------------------------------------===//
41
42SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
43                             const LiveIntervals &lis,
44                             const MachineLoopInfo &mli)
45  : MF(vrm.getMachineFunction()),
46    VRM(vrm),
47    LIS(lis),
48    Loops(mli),
49    TII(*MF.getTarget().getInstrInfo()),
50    CurLI(0),
51    LastSplitPoint(MF.getNumBlockIDs()) {}
52
53void SplitAnalysis::clear() {
54  UseSlots.clear();
55  UseBlocks.clear();
56  ThroughBlocks.clear();
57  CurLI = 0;
58  DidRepairRange = false;
59}
60
61SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
62  const MachineBasicBlock *MBB = MF.getBlockNumbered(Num);
63  const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor();
64  std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num];
65
66  // Compute split points on the first call. The pair is independent of the
67  // current live interval.
68  if (!LSP.first.isValid()) {
69    MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator();
70    if (FirstTerm == MBB->end())
71      LSP.first = LIS.getMBBEndIdx(MBB);
72    else
73      LSP.first = LIS.getInstructionIndex(FirstTerm);
74
75    // If there is a landing pad successor, also find the call instruction.
76    if (!LPad)
77      return LSP.first;
78    // There may not be a call instruction (?) in which case we ignore LPad.
79    LSP.second = LSP.first;
80    for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin();
81         I != E;) {
82      --I;
83      if (I->getDesc().isCall()) {
84        LSP.second = LIS.getInstructionIndex(I);
85        break;
86      }
87    }
88  }
89
90  // If CurLI is live into a landing pad successor, move the last split point
91  // back to the call that may throw.
92  if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad))
93    return LSP.second;
94  else
95    return LSP.first;
96}
97
98/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
99void SplitAnalysis::analyzeUses() {
100  assert(UseSlots.empty() && "Call clear first");
101
102  // First get all the defs from the interval values. This provides the correct
103  // slots for early clobbers.
104  for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(),
105       E = CurLI->vni_end(); I != E; ++I)
106    if (!(*I)->isPHIDef() && !(*I)->isUnused())
107      UseSlots.push_back((*I)->def);
108
109  // Get use slots form the use-def chain.
110  const MachineRegisterInfo &MRI = MF.getRegInfo();
111  for (MachineRegisterInfo::use_nodbg_iterator
112       I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E;
113       ++I)
114    if (!I.getOperand().isUndef())
115      UseSlots.push_back(LIS.getInstructionIndex(&*I).getRegSlot());
116
117  array_pod_sort(UseSlots.begin(), UseSlots.end());
118
119  // Remove duplicates, keeping the smaller slot for each instruction.
120  // That is what we want for early clobbers.
121  UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
122                             SlotIndex::isSameInstr),
123                 UseSlots.end());
124
125  // Compute per-live block info.
126  if (!calcLiveBlockInfo()) {
127    // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
128    // I am looking at you, RegisterCoalescer!
129    DidRepairRange = true;
130    ++NumRepairs;
131    DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
132    const_cast<LiveIntervals&>(LIS)
133      .shrinkToUses(const_cast<LiveInterval*>(CurLI));
134    UseBlocks.clear();
135    ThroughBlocks.clear();
136    bool fixed = calcLiveBlockInfo();
137    (void)fixed;
138    assert(fixed && "Couldn't fix broken live interval");
139  }
140
141  DEBUG(dbgs() << "Analyze counted "
142               << UseSlots.size() << " instrs in "
143               << UseBlocks.size() << " blocks, through "
144               << NumThroughBlocks << " blocks.\n");
145}
146
147/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
148/// where CurLI is live.
149bool SplitAnalysis::calcLiveBlockInfo() {
150  ThroughBlocks.resize(MF.getNumBlockIDs());
151  NumThroughBlocks = NumGapBlocks = 0;
152  if (CurLI->empty())
153    return true;
154
155  LiveInterval::const_iterator LVI = CurLI->begin();
156  LiveInterval::const_iterator LVE = CurLI->end();
157
158  SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
159  UseI = UseSlots.begin();
160  UseE = UseSlots.end();
161
162  // Loop over basic blocks where CurLI is live.
163  MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
164  for (;;) {
165    BlockInfo BI;
166    BI.MBB = MFI;
167    SlotIndex Start, Stop;
168    tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
169
170    // If the block contains no uses, the range must be live through. At one
171    // point, RegisterCoalescer could create dangling ranges that ended
172    // mid-block.
173    if (UseI == UseE || *UseI >= Stop) {
174      ++NumThroughBlocks;
175      ThroughBlocks.set(BI.MBB->getNumber());
176      // The range shouldn't end mid-block if there are no uses. This shouldn't
177      // happen.
178      if (LVI->end < Stop)
179        return false;
180    } else {
181      // This block has uses. Find the first and last uses in the block.
182      BI.FirstInstr = *UseI;
183      assert(BI.FirstInstr >= Start);
184      do ++UseI;
185      while (UseI != UseE && *UseI < Stop);
186      BI.LastInstr = UseI[-1];
187      assert(BI.LastInstr < Stop);
188
189      // LVI is the first live segment overlapping MBB.
190      BI.LiveIn = LVI->start <= Start;
191
192      // When not live in, the first use should be a def.
193      if (!BI.LiveIn) {
194        assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
195        assert(LVI->start == BI.FirstInstr && "First instr should be a def");
196        BI.FirstDef = BI.FirstInstr;
197      }
198
199      // Look for gaps in the live range.
200      BI.LiveOut = true;
201      while (LVI->end < Stop) {
202        SlotIndex LastStop = LVI->end;
203        if (++LVI == LVE || LVI->start >= Stop) {
204          BI.LiveOut = false;
205          BI.LastInstr = LastStop;
206          break;
207        }
208
209        if (LastStop < LVI->start) {
210          // There is a gap in the live range. Create duplicate entries for the
211          // live-in snippet and the live-out snippet.
212          ++NumGapBlocks;
213
214          // Push the Live-in part.
215          BI.LiveOut = false;
216          UseBlocks.push_back(BI);
217          UseBlocks.back().LastInstr = LastStop;
218
219          // Set up BI for the live-out part.
220          BI.LiveIn = false;
221          BI.LiveOut = true;
222          BI.FirstInstr = BI.FirstDef = LVI->start;
223        }
224
225        // A LiveRange that starts in the middle of the block must be a def.
226        assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
227        if (!BI.FirstDef)
228          BI.FirstDef = LVI->start;
229      }
230
231      UseBlocks.push_back(BI);
232
233      // LVI is now at LVE or LVI->end >= Stop.
234      if (LVI == LVE)
235        break;
236    }
237
238    // Live segment ends exactly at Stop. Move to the next segment.
239    if (LVI->end == Stop && ++LVI == LVE)
240      break;
241
242    // Pick the next basic block.
243    if (LVI->start < Stop)
244      ++MFI;
245    else
246      MFI = LIS.getMBBFromIndex(LVI->start);
247  }
248
249  assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
250  return true;
251}
252
253unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
254  if (cli->empty())
255    return 0;
256  LiveInterval *li = const_cast<LiveInterval*>(cli);
257  LiveInterval::iterator LVI = li->begin();
258  LiveInterval::iterator LVE = li->end();
259  unsigned Count = 0;
260
261  // Loop over basic blocks where li is live.
262  MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start);
263  SlotIndex Stop = LIS.getMBBEndIdx(MFI);
264  for (;;) {
265    ++Count;
266    LVI = li->advanceTo(LVI, Stop);
267    if (LVI == LVE)
268      return Count;
269    do {
270      ++MFI;
271      Stop = LIS.getMBBEndIdx(MFI);
272    } while (Stop <= LVI->start);
273  }
274}
275
276bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
277  unsigned OrigReg = VRM.getOriginal(CurLI->reg);
278  const LiveInterval &Orig = LIS.getInterval(OrigReg);
279  assert(!Orig.empty() && "Splitting empty interval?");
280  LiveInterval::const_iterator I = Orig.find(Idx);
281
282  // Range containing Idx should begin at Idx.
283  if (I != Orig.end() && I->start <= Idx)
284    return I->start == Idx;
285
286  // Range does not contain Idx, previous must end at Idx.
287  return I != Orig.begin() && (--I)->end == Idx;
288}
289
290void SplitAnalysis::analyze(const LiveInterval *li) {
291  clear();
292  CurLI = li;
293  analyzeUses();
294}
295
296
297//===----------------------------------------------------------------------===//
298//                               Split Editor
299//===----------------------------------------------------------------------===//
300
301/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
302SplitEditor::SplitEditor(SplitAnalysis &sa,
303                         LiveIntervals &lis,
304                         VirtRegMap &vrm,
305                         MachineDominatorTree &mdt)
306  : SA(sa), LIS(lis), VRM(vrm),
307    MRI(vrm.getMachineFunction().getRegInfo()),
308    MDT(mdt),
309    TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
310    TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
311    Edit(0),
312    OpenIdx(0),
313    SpillMode(SM_Partition),
314    RegAssign(Allocator)
315{}
316
317void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
318  Edit = &LRE;
319  SpillMode = SM;
320  OpenIdx = 0;
321  RegAssign.clear();
322  Values.clear();
323
324  // Reset the LiveRangeCalc instances needed for this spill mode.
325  LRCalc[0].reset(&VRM.getMachineFunction());
326  if (SpillMode)
327    LRCalc[1].reset(&VRM.getMachineFunction());
328
329  // We don't need an AliasAnalysis since we will only be performing
330  // cheap-as-a-copy remats anyway.
331  Edit->anyRematerializable(LIS, TII, 0);
332}
333
334void SplitEditor::dump() const {
335  if (RegAssign.empty()) {
336    dbgs() << " empty\n";
337    return;
338  }
339
340  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
341    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
342  dbgs() << '\n';
343}
344
345VNInfo *SplitEditor::defValue(unsigned RegIdx,
346                              const VNInfo *ParentVNI,
347                              SlotIndex Idx) {
348  assert(ParentVNI && "Mapping  NULL value");
349  assert(Idx.isValid() && "Invalid SlotIndex");
350  assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
351  LiveInterval *LI = Edit->get(RegIdx);
352
353  // Create a new value.
354  VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
355
356  // Use insert for lookup, so we can add missing values with a second lookup.
357  std::pair<ValueMap::iterator, bool> InsP =
358    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id),
359                                 ValueForcePair(VNI, false)));
360
361  // This was the first time (RegIdx, ParentVNI) was mapped.
362  // Keep it as a simple def without any liveness.
363  if (InsP.second)
364    return VNI;
365
366  // If the previous value was a simple mapping, add liveness for it now.
367  if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
368    SlotIndex Def = OldVNI->def;
369    LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
370    // No longer a simple mapping.  Switch to a complex, non-forced mapping.
371    InsP.first->second = ValueForcePair();
372  }
373
374  // This is a complex mapping, add liveness for VNI
375  SlotIndex Def = VNI->def;
376  LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
377
378  return VNI;
379}
380
381void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
382  assert(ParentVNI && "Mapping  NULL value");
383  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
384  VNInfo *VNI = VFP.getPointer();
385
386  // ParentVNI was either unmapped or already complex mapped. Either way, just
387  // set the force bit.
388  if (!VNI) {
389    VFP.setInt(true);
390    return;
391  }
392
393  // This was previously a single mapping. Make sure the old def is represented
394  // by a trivial live range.
395  SlotIndex Def = VNI->def;
396  Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
397  // Mark as complex mapped, forced.
398  VFP = ValueForcePair(0, true);
399}
400
401VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
402                                   VNInfo *ParentVNI,
403                                   SlotIndex UseIdx,
404                                   MachineBasicBlock &MBB,
405                                   MachineBasicBlock::iterator I) {
406  MachineInstr *CopyMI = 0;
407  SlotIndex Def;
408  LiveInterval *LI = Edit->get(RegIdx);
409
410  // We may be trying to avoid interference that ends at a deleted instruction,
411  // so always begin RegIdx 0 early and all others late.
412  bool Late = RegIdx != 0;
413
414  // Attempt cheap-as-a-copy rematerialization.
415  LiveRangeEdit::Remat RM(ParentVNI);
416  if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) {
417    Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late);
418    ++NumRemats;
419  } else {
420    // Can't remat, just insert a copy from parent.
421    CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
422               .addReg(Edit->getReg());
423    Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late)
424            .getRegSlot();
425    ++NumCopies;
426  }
427
428  // Define the value in Reg.
429  VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
430  VNI->setCopy(CopyMI);
431  return VNI;
432}
433
434/// Create a new virtual register and live interval.
435unsigned SplitEditor::openIntv() {
436  // Create the complement as index 0.
437  if (Edit->empty())
438    Edit->create(LIS, VRM);
439
440  // Create the open interval.
441  OpenIdx = Edit->size();
442  Edit->create(LIS, VRM);
443  return OpenIdx;
444}
445
446void SplitEditor::selectIntv(unsigned Idx) {
447  assert(Idx != 0 && "Cannot select the complement interval");
448  assert(Idx < Edit->size() && "Can only select previously opened interval");
449  DEBUG(dbgs() << "    selectIntv " << OpenIdx << " -> " << Idx << '\n');
450  OpenIdx = Idx;
451}
452
453SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
454  assert(OpenIdx && "openIntv not called before enterIntvBefore");
455  DEBUG(dbgs() << "    enterIntvBefore " << Idx);
456  Idx = Idx.getBaseIndex();
457  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
458  if (!ParentVNI) {
459    DEBUG(dbgs() << ": not live\n");
460    return Idx;
461  }
462  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
463  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
464  assert(MI && "enterIntvBefore called with invalid index");
465
466  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
467  return VNI->def;
468}
469
470SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {
471  assert(OpenIdx && "openIntv not called before enterIntvAfter");
472  DEBUG(dbgs() << "    enterIntvAfter " << Idx);
473  Idx = Idx.getBoundaryIndex();
474  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
475  if (!ParentVNI) {
476    DEBUG(dbgs() << ": not live\n");
477    return Idx;
478  }
479  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
480  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
481  assert(MI && "enterIntvAfter called with invalid index");
482
483  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
484                              llvm::next(MachineBasicBlock::iterator(MI)));
485  return VNI->def;
486}
487
488SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
489  assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
490  SlotIndex End = LIS.getMBBEndIdx(&MBB);
491  SlotIndex Last = End.getPrevSlot();
492  DEBUG(dbgs() << "    enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
493  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
494  if (!ParentVNI) {
495    DEBUG(dbgs() << ": not live\n");
496    return End;
497  }
498  DEBUG(dbgs() << ": valno " << ParentVNI->id);
499  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
500                              LIS.getLastSplitPoint(Edit->getParent(), &MBB));
501  RegAssign.insert(VNI->def, End, OpenIdx);
502  DEBUG(dump());
503  return VNI->def;
504}
505
506/// useIntv - indicate that all instructions in MBB should use OpenLI.
507void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
508  useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
509}
510
511void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
512  assert(OpenIdx && "openIntv not called before useIntv");
513  DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
514  RegAssign.insert(Start, End, OpenIdx);
515  DEBUG(dump());
516}
517
518SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
519  assert(OpenIdx && "openIntv not called before leaveIntvAfter");
520  DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
521
522  // The interval must be live beyond the instruction at Idx.
523  SlotIndex Boundary = Idx.getBoundaryIndex();
524  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
525  if (!ParentVNI) {
526    DEBUG(dbgs() << ": not live\n");
527    return Boundary.getNextSlot();
528  }
529  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
530  MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
531  assert(MI && "No instruction at index");
532
533  // In spill mode, make live ranges as short as possible by inserting the copy
534  // before MI.  This is only possible if that instruction doesn't redefine the
535  // value.  The inserted COPY is not a kill, and we don't need to recompute
536  // the source live range.  The spiller also won't try to hoist this copy.
537  if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
538      MI->readsVirtualRegister(Edit->getReg())) {
539    forceRecompute(0, ParentVNI);
540    defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
541    return Idx;
542  }
543
544  VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
545                              llvm::next(MachineBasicBlock::iterator(MI)));
546  return VNI->def;
547}
548
549SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
550  assert(OpenIdx && "openIntv not called before leaveIntvBefore");
551  DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
552
553  // The interval must be live into the instruction at Idx.
554  Idx = Idx.getBaseIndex();
555  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
556  if (!ParentVNI) {
557    DEBUG(dbgs() << ": not live\n");
558    return Idx.getNextSlot();
559  }
560  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
561
562  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
563  assert(MI && "No instruction at index");
564  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
565  return VNI->def;
566}
567
568SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
569  assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
570  SlotIndex Start = LIS.getMBBStartIdx(&MBB);
571  DEBUG(dbgs() << "    leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
572
573  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
574  if (!ParentVNI) {
575    DEBUG(dbgs() << ": not live\n");
576    return Start;
577  }
578
579  VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
580                              MBB.SkipPHIsAndLabels(MBB.begin()));
581  RegAssign.insert(Start, VNI->def, OpenIdx);
582  DEBUG(dump());
583  return VNI->def;
584}
585
586void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
587  assert(OpenIdx && "openIntv not called before overlapIntv");
588  const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
589  assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) &&
590         "Parent changes value in extended range");
591  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
592         "Range cannot span basic blocks");
593
594  // The complement interval will be extended as needed by LRCalc.extend().
595  if (ParentVNI)
596    forceRecompute(0, ParentVNI);
597  DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
598  RegAssign.insert(Start, End, OpenIdx);
599  DEBUG(dump());
600}
601
602//===----------------------------------------------------------------------===//
603//                                  Spill modes
604//===----------------------------------------------------------------------===//
605
606void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
607  LiveInterval *LI = Edit->get(0);
608  DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
609  RegAssignMap::iterator AssignI;
610  AssignI.setMap(RegAssign);
611
612  for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
613    VNInfo *VNI = Copies[i];
614    SlotIndex Def = VNI->def;
615    MachineInstr *MI = LIS.getInstructionFromIndex(Def);
616    assert(MI && "No instruction for back-copy");
617
618    MachineBasicBlock *MBB = MI->getParent();
619    MachineBasicBlock::iterator MBBI(MI);
620    bool AtBegin;
621    do AtBegin = MBBI == MBB->begin();
622    while (!AtBegin && (--MBBI)->isDebugValue());
623
624    DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
625    LI->removeValNo(VNI);
626    LIS.RemoveMachineInstrFromMaps(MI);
627    MI->eraseFromParent();
628
629    // Adjust RegAssign if a register assignment is killed at VNI->def.  We
630    // want to avoid calculating the live range of the source register if
631    // possible.
632    AssignI.find(VNI->def.getPrevSlot());
633    if (!AssignI.valid() || AssignI.start() >= Def)
634      continue;
635    // If MI doesn't kill the assigned register, just leave it.
636    if (AssignI.stop() != Def)
637      continue;
638    unsigned RegIdx = AssignI.value();
639    if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
640      DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx << '\n');
641      forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
642    } else {
643      SlotIndex Kill = LIS.getInstructionIndex(MBBI).getRegSlot();
644      DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
645      AssignI.setStop(Kill);
646    }
647  }
648}
649
650MachineBasicBlock*
651SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
652                                  MachineBasicBlock *DefMBB) {
653  if (MBB == DefMBB)
654    return MBB;
655  assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
656
657  const MachineLoopInfo &Loops = SA.Loops;
658  const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
659  MachineDomTreeNode *DefDomNode = MDT[DefMBB];
660
661  // Best candidate so far.
662  MachineBasicBlock *BestMBB = MBB;
663  unsigned BestDepth = UINT_MAX;
664
665  for (;;) {
666    const MachineLoop *Loop = Loops.getLoopFor(MBB);
667
668    // MBB isn't in a loop, it doesn't get any better.  All dominators have a
669    // higher frequency by definition.
670    if (!Loop) {
671      DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
672                   << MBB->getNumber() << " at depth 0\n");
673      return MBB;
674    }
675
676    // We'll never be able to exit the DefLoop.
677    if (Loop == DefLoop) {
678      DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
679                   << MBB->getNumber() << " in the same loop\n");
680      return MBB;
681    }
682
683    // Least busy dominator seen so far.
684    unsigned Depth = Loop->getLoopDepth();
685    if (Depth < BestDepth) {
686      BestMBB = MBB;
687      BestDepth = Depth;
688      DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
689                   << MBB->getNumber() << " at depth " << Depth << '\n');
690    }
691
692    // Leave loop by going to the immediate dominator of the loop header.
693    // This is a bigger stride than simply walking up the dominator tree.
694    MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
695
696    // Too far up the dominator tree?
697    if (!IDom || !MDT.dominates(DefDomNode, IDom))
698      return BestMBB;
699
700    MBB = IDom->getBlock();
701  }
702}
703
704void SplitEditor::hoistCopiesForSize() {
705  // Get the complement interval, always RegIdx 0.
706  LiveInterval *LI = Edit->get(0);
707  LiveInterval *Parent = &Edit->getParent();
708
709  // Track the nearest common dominator for all back-copies for each ParentVNI,
710  // indexed by ParentVNI->id.
711  typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair;
712  SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
713
714  // Find the nearest common dominator for parent values with multiple
715  // back-copies.  If a single back-copy dominates, put it in DomPair.second.
716  for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
717       VI != VE; ++VI) {
718    VNInfo *VNI = *VI;
719    VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
720    assert(ParentVNI && "Parent not live at complement def");
721
722    // Don't hoist remats.  The complement is probably going to disappear
723    // completely anyway.
724    if (Edit->didRematerialize(ParentVNI))
725      continue;
726
727    MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
728    DomPair &Dom = NearestDom[ParentVNI->id];
729
730    // Keep directly defined parent values.  This is either a PHI or an
731    // instruction in the complement range.  All other copies of ParentVNI
732    // should be eliminated.
733    if (VNI->def == ParentVNI->def) {
734      DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
735      Dom = DomPair(ValMBB, VNI->def);
736      continue;
737    }
738    // Skip the singly mapped values.  There is nothing to gain from hoisting a
739    // single back-copy.
740    if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
741      DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
742      continue;
743    }
744
745    if (!Dom.first) {
746      // First time we see ParentVNI.  VNI dominates itself.
747      Dom = DomPair(ValMBB, VNI->def);
748    } else if (Dom.first == ValMBB) {
749      // Two defs in the same block.  Pick the earlier def.
750      if (!Dom.second.isValid() || VNI->def < Dom.second)
751        Dom.second = VNI->def;
752    } else {
753      // Different basic blocks. Check if one dominates.
754      MachineBasicBlock *Near =
755        MDT.findNearestCommonDominator(Dom.first, ValMBB);
756      if (Near == ValMBB)
757        // Def ValMBB dominates.
758        Dom = DomPair(ValMBB, VNI->def);
759      else if (Near != Dom.first)
760        // None dominate. Hoist to common dominator, need new def.
761        Dom = DomPair(Near, SlotIndex());
762    }
763
764    DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def
765                 << " for parent " << ParentVNI->id << '@' << ParentVNI->def
766                 << " hoist to BB#" << Dom.first->getNumber() << ' '
767                 << Dom.second << '\n');
768  }
769
770  // Insert the hoisted copies.
771  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
772    DomPair &Dom = NearestDom[i];
773    if (!Dom.first || Dom.second.isValid())
774      continue;
775    // This value needs a hoisted copy inserted at the end of Dom.first.
776    VNInfo *ParentVNI = Parent->getValNumInfo(i);
777    MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
778    // Get a less loopy dominator than Dom.first.
779    Dom.first = findShallowDominator(Dom.first, DefMBB);
780    SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
781    Dom.second =
782      defFromParent(0, ParentVNI, Last, *Dom.first,
783                    LIS.getLastSplitPoint(Edit->getParent(), Dom.first))->def;
784  }
785
786  // Remove redundant back-copies that are now known to be dominated by another
787  // def with the same value.
788  SmallVector<VNInfo*, 8> BackCopies;
789  for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
790       VI != VE; ++VI) {
791    VNInfo *VNI = *VI;
792    VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
793    const DomPair &Dom = NearestDom[ParentVNI->id];
794    if (!Dom.first || Dom.second == VNI->def)
795      continue;
796    BackCopies.push_back(VNI);
797    forceRecompute(0, ParentVNI);
798  }
799  removeBackCopies(BackCopies);
800}
801
802
803/// transferValues - Transfer all possible values to the new live ranges.
804/// Values that were rematerialized are left alone, they need LRCalc.extend().
805bool SplitEditor::transferValues() {
806  bool Skipped = false;
807  RegAssignMap::const_iterator AssignI = RegAssign.begin();
808  for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(),
809         ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) {
810    DEBUG(dbgs() << "  blit " << *ParentI << ':');
811    VNInfo *ParentVNI = ParentI->valno;
812    // RegAssign has holes where RegIdx 0 should be used.
813    SlotIndex Start = ParentI->start;
814    AssignI.advanceTo(Start);
815    do {
816      unsigned RegIdx;
817      SlotIndex End = ParentI->end;
818      if (!AssignI.valid()) {
819        RegIdx = 0;
820      } else if (AssignI.start() <= Start) {
821        RegIdx = AssignI.value();
822        if (AssignI.stop() < End) {
823          End = AssignI.stop();
824          ++AssignI;
825        }
826      } else {
827        RegIdx = 0;
828        End = std::min(End, AssignI.start());
829      }
830
831      // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
832      DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx);
833      LiveInterval *LI = Edit->get(RegIdx);
834
835      // Check for a simply defined value that can be blitted directly.
836      ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
837      if (VNInfo *VNI = VFP.getPointer()) {
838        DEBUG(dbgs() << ':' << VNI->id);
839        LI->addRange(LiveRange(Start, End, VNI));
840        Start = End;
841        continue;
842      }
843
844      // Skip values with forced recomputation.
845      if (VFP.getInt()) {
846        DEBUG(dbgs() << "(recalc)");
847        Skipped = true;
848        Start = End;
849        continue;
850      }
851
852      LiveRangeCalc &LRC = getLRCalc(RegIdx);
853
854      // This value has multiple defs in RegIdx, but it wasn't rematerialized,
855      // so the live range is accurate. Add live-in blocks in [Start;End) to the
856      // LiveInBlocks.
857      MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
858      SlotIndex BlockStart, BlockEnd;
859      tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB);
860
861      // The first block may be live-in, or it may have its own def.
862      if (Start != BlockStart) {
863        VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
864        assert(VNI && "Missing def for complex mapped value");
865        DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
866        // MBB has its own def. Is it also live-out?
867        if (BlockEnd <= End)
868          LRC.setLiveOutValue(MBB, VNI);
869
870        // Skip to the next block for live-in.
871        ++MBB;
872        BlockStart = BlockEnd;
873      }
874
875      // Handle the live-in blocks covered by [Start;End).
876      assert(Start <= BlockStart && "Expected live-in block");
877      while (BlockStart < End) {
878        DEBUG(dbgs() << ">BB#" << MBB->getNumber());
879        BlockEnd = LIS.getMBBEndIdx(MBB);
880        if (BlockStart == ParentVNI->def) {
881          // This block has the def of a parent PHI, so it isn't live-in.
882          assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
883          VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
884          assert(VNI && "Missing def for complex mapped parent PHI");
885          if (End >= BlockEnd)
886            LRC.setLiveOutValue(MBB, VNI); // Live-out as well.
887        } else {
888          // This block needs a live-in value.  The last block covered may not
889          // be live-out.
890          if (End < BlockEnd)
891            LRC.addLiveInBlock(LI, MDT[MBB], End);
892          else {
893            // Live-through, and we don't know the value.
894            LRC.addLiveInBlock(LI, MDT[MBB]);
895            LRC.setLiveOutValue(MBB, 0);
896          }
897        }
898        BlockStart = BlockEnd;
899        ++MBB;
900      }
901      Start = End;
902    } while (Start != ParentI->end);
903    DEBUG(dbgs() << '\n');
904  }
905
906  LRCalc[0].calculateValues(LIS.getSlotIndexes(), &MDT,
907                            &LIS.getVNInfoAllocator());
908  if (SpillMode)
909    LRCalc[1].calculateValues(LIS.getSlotIndexes(), &MDT,
910                              &LIS.getVNInfoAllocator());
911
912  return Skipped;
913}
914
915void SplitEditor::extendPHIKillRanges() {
916    // Extend live ranges to be live-out for successor PHI values.
917  for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
918       E = Edit->getParent().vni_end(); I != E; ++I) {
919    const VNInfo *PHIVNI = *I;
920    if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
921      continue;
922    unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
923    LiveInterval *LI = Edit->get(RegIdx);
924    LiveRangeCalc &LRC = getLRCalc(RegIdx);
925    MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
926    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
927         PE = MBB->pred_end(); PI != PE; ++PI) {
928      SlotIndex End = LIS.getMBBEndIdx(*PI);
929      SlotIndex LastUse = End.getPrevSlot();
930      // The predecessor may not have a live-out value. That is OK, like an
931      // undef PHI operand.
932      if (Edit->getParent().liveAt(LastUse)) {
933        assert(RegAssign.lookup(LastUse) == RegIdx &&
934               "Different register assignment in phi predecessor");
935        LRC.extend(LI, End,
936                   LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator());
937      }
938    }
939  }
940}
941
942/// rewriteAssigned - Rewrite all uses of Edit->getReg().
943void SplitEditor::rewriteAssigned(bool ExtendRanges) {
944  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
945       RE = MRI.reg_end(); RI != RE;) {
946    MachineOperand &MO = RI.getOperand();
947    MachineInstr *MI = MO.getParent();
948    ++RI;
949    // LiveDebugVariables should have handled all DBG_VALUE instructions.
950    if (MI->isDebugValue()) {
951      DEBUG(dbgs() << "Zapping " << *MI);
952      MO.setReg(0);
953      continue;
954    }
955
956    // <undef> operands don't really read the register, so it doesn't matter
957    // which register we choose.  When the use operand is tied to a def, we must
958    // use the same register as the def, so just do that always.
959    SlotIndex Idx = LIS.getInstructionIndex(MI);
960    if (MO.isDef() || MO.isUndef())
961      Idx = Idx.getRegSlot(MO.isEarlyClobber());
962
963    // Rewrite to the mapped register at Idx.
964    unsigned RegIdx = RegAssign.lookup(Idx);
965    LiveInterval *LI = Edit->get(RegIdx);
966    MO.setReg(LI->reg);
967    DEBUG(dbgs() << "  rewr BB#" << MI->getParent()->getNumber() << '\t'
968                 << Idx << ':' << RegIdx << '\t' << *MI);
969
970    // Extend liveness to Idx if the instruction reads reg.
971    if (!ExtendRanges || MO.isUndef())
972      continue;
973
974    // Skip instructions that don't read Reg.
975    if (MO.isDef()) {
976      if (!MO.getSubReg() && !MO.isEarlyClobber())
977        continue;
978      // We may wan't to extend a live range for a partial redef, or for a use
979      // tied to an early clobber.
980      Idx = Idx.getPrevSlot();
981      if (!Edit->getParent().liveAt(Idx))
982        continue;
983    } else
984      Idx = Idx.getRegSlot(true);
985
986    getLRCalc(RegIdx).extend(LI, Idx.getNextSlot(), LIS.getSlotIndexes(),
987                             &MDT, &LIS.getVNInfoAllocator());
988  }
989}
990
991void SplitEditor::deleteRematVictims() {
992  SmallVector<MachineInstr*, 8> Dead;
993  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
994    LiveInterval *LI = *I;
995    for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end();
996           LII != LIE; ++LII) {
997      // Dead defs end at the store slot.
998      if (LII->end != LII->valno->def.getNextSlot())
999        continue;
1000      MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def);
1001      assert(MI && "Missing instruction for dead def");
1002      MI->addRegisterDead(LI->reg, &TRI);
1003
1004      if (!MI->allDefsAreDead())
1005        continue;
1006
1007      DEBUG(dbgs() << "All defs dead: " << *MI);
1008      Dead.push_back(MI);
1009    }
1010  }
1011
1012  if (Dead.empty())
1013    return;
1014
1015  Edit->eliminateDeadDefs(Dead, LIS, VRM, TII);
1016}
1017
1018void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
1019  ++NumFinished;
1020
1021  // At this point, the live intervals in Edit contain VNInfos corresponding to
1022  // the inserted copies.
1023
1024  // Add the original defs from the parent interval.
1025  for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
1026         E = Edit->getParent().vni_end(); I != E; ++I) {
1027    const VNInfo *ParentVNI = *I;
1028    if (ParentVNI->isUnused())
1029      continue;
1030    unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1031    VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def);
1032    VNI->setIsPHIDef(ParentVNI->isPHIDef());
1033    VNI->setCopy(ParentVNI->getCopy());
1034
1035    // Force rematted values to be recomputed everywhere.
1036    // The new live ranges may be truncated.
1037    if (Edit->didRematerialize(ParentVNI))
1038      for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1039        forceRecompute(i, ParentVNI);
1040  }
1041
1042  // Hoist back-copies to the complement interval when in spill mode.
1043  switch (SpillMode) {
1044  case SM_Partition:
1045    // Leave all back-copies as is.
1046    break;
1047  case SM_Size:
1048    hoistCopiesForSize();
1049    break;
1050  case SM_Speed:
1051    llvm_unreachable("Spill mode 'speed' not implemented yet");
1052    break;
1053  }
1054
1055  // Transfer the simply mapped values, check if any are skipped.
1056  bool Skipped = transferValues();
1057  if (Skipped)
1058    extendPHIKillRanges();
1059  else
1060    ++NumSimple;
1061
1062  // Rewrite virtual registers, possibly extending ranges.
1063  rewriteAssigned(Skipped);
1064
1065  // Delete defs that were rematted everywhere.
1066  if (Skipped)
1067    deleteRematVictims();
1068
1069  // Get rid of unused values and set phi-kill flags.
1070  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I)
1071    (*I)->RenumberValues(LIS);
1072
1073  // Provide a reverse mapping from original indices to Edit ranges.
1074  if (LRMap) {
1075    LRMap->clear();
1076    for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1077      LRMap->push_back(i);
1078  }
1079
1080  // Now check if any registers were separated into multiple components.
1081  ConnectedVNInfoEqClasses ConEQ(LIS);
1082  for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1083    // Don't use iterators, they are invalidated by create() below.
1084    LiveInterval *li = Edit->get(i);
1085    unsigned NumComp = ConEQ.Classify(li);
1086    if (NumComp <= 1)
1087      continue;
1088    DEBUG(dbgs() << "  " << NumComp << " components: " << *li << '\n');
1089    SmallVector<LiveInterval*, 8> dups;
1090    dups.push_back(li);
1091    for (unsigned j = 1; j != NumComp; ++j)
1092      dups.push_back(&Edit->create(LIS, VRM));
1093    ConEQ.Distribute(&dups[0], MRI);
1094    // The new intervals all map back to i.
1095    if (LRMap)
1096      LRMap->resize(Edit->size(), i);
1097  }
1098
1099  // Calculate spill weight and allocation hints for new intervals.
1100  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops);
1101
1102  assert(!LRMap || LRMap->size() == Edit->size());
1103}
1104
1105
1106//===----------------------------------------------------------------------===//
1107//                            Single Block Splitting
1108//===----------------------------------------------------------------------===//
1109
1110bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,
1111                                           bool SingleInstrs) const {
1112  // Always split for multiple instructions.
1113  if (!BI.isOneInstr())
1114    return true;
1115  // Don't split for single instructions unless explicitly requested.
1116  if (!SingleInstrs)
1117    return false;
1118  // Splitting a live-through range always makes progress.
1119  if (BI.LiveIn && BI.LiveOut)
1120    return true;
1121  // No point in isolating a copy. It has no register class constraints.
1122  if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
1123    return false;
1124  // Finally, don't isolate an end point that was created by earlier splits.
1125  return isOriginalEndpoint(BI.FirstInstr);
1126}
1127
1128void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) {
1129  openIntv();
1130  SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
1131  SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
1132    LastSplitPoint));
1133  if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1134    useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1135  } else {
1136      // The last use is after the last valid split point.
1137    SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1138    useIntv(SegStart, SegStop);
1139    overlapIntv(SegStop, BI.LastInstr);
1140  }
1141}
1142
1143
1144//===----------------------------------------------------------------------===//
1145//                    Global Live Range Splitting Support
1146//===----------------------------------------------------------------------===//
1147
1148// These methods support a method of global live range splitting that uses a
1149// global algorithm to decide intervals for CFG edges. They will insert split
1150// points and color intervals in basic blocks while avoiding interference.
1151//
1152// Note that splitSingleBlock is also useful for blocks where both CFG edges
1153// are on the stack.
1154
1155void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
1156                                        unsigned IntvIn, SlotIndex LeaveBefore,
1157                                        unsigned IntvOut, SlotIndex EnterAfter){
1158  SlotIndex Start, Stop;
1159  tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1160
1161  DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop
1162               << ") intf " << LeaveBefore << '-' << EnterAfter
1163               << ", live-through " << IntvIn << " -> " << IntvOut);
1164
1165  assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1166
1167  assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1168  assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1169  assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1170
1171  MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
1172
1173  if (!IntvOut) {
1174    DEBUG(dbgs() << ", spill on entry.\n");
1175    //
1176    //        <<<<<<<<<    Possible LeaveBefore interference.
1177    //    |-----------|    Live through.
1178    //    -____________    Spill on entry.
1179    //
1180    selectIntv(IntvIn);
1181    SlotIndex Idx = leaveIntvAtTop(*MBB);
1182    assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1183    (void)Idx;
1184    return;
1185  }
1186
1187  if (!IntvIn) {
1188    DEBUG(dbgs() << ", reload on exit.\n");
1189    //
1190    //    >>>>>>>          Possible EnterAfter interference.
1191    //    |-----------|    Live through.
1192    //    ___________--    Reload on exit.
1193    //
1194    selectIntv(IntvOut);
1195    SlotIndex Idx = enterIntvAtEnd(*MBB);
1196    assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1197    (void)Idx;
1198    return;
1199  }
1200
1201  if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1202    DEBUG(dbgs() << ", straight through.\n");
1203    //
1204    //    |-----------|    Live through.
1205    //    -------------    Straight through, same intv, no interference.
1206    //
1207    selectIntv(IntvOut);
1208    useIntv(Start, Stop);
1209    return;
1210  }
1211
1212  // We cannot legally insert splits after LSP.
1213  SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1214  assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1215
1216  if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1217                  LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1218    DEBUG(dbgs() << ", switch avoiding interference.\n");
1219    //
1220    //    >>>>     <<<<    Non-overlapping EnterAfter/LeaveBefore interference.
1221    //    |-----------|    Live through.
1222    //    ------=======    Switch intervals between interference.
1223    //
1224    selectIntv(IntvOut);
1225    SlotIndex Idx;
1226    if (LeaveBefore && LeaveBefore < LSP) {
1227      Idx = enterIntvBefore(LeaveBefore);
1228      useIntv(Idx, Stop);
1229    } else {
1230      Idx = enterIntvAtEnd(*MBB);
1231    }
1232    selectIntv(IntvIn);
1233    useIntv(Start, Idx);
1234    assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1235    assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1236    return;
1237  }
1238
1239  DEBUG(dbgs() << ", create local intv for interference.\n");
1240  //
1241  //    >>><><><><<<<    Overlapping EnterAfter/LeaveBefore interference.
1242  //    |-----------|    Live through.
1243  //    ==---------==    Switch intervals before/after interference.
1244  //
1245  assert(LeaveBefore <= EnterAfter && "Missed case");
1246
1247  selectIntv(IntvOut);
1248  SlotIndex Idx = enterIntvAfter(EnterAfter);
1249  useIntv(Idx, Stop);
1250  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1251
1252  selectIntv(IntvIn);
1253  Idx = leaveIntvBefore(LeaveBefore);
1254  useIntv(Start, Idx);
1255  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1256}
1257
1258
1259void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
1260                                  unsigned IntvIn, SlotIndex LeaveBefore) {
1261  SlotIndex Start, Stop;
1262  tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1263
1264  DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1265               << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1266               << ", reg-in " << IntvIn << ", leave before " << LeaveBefore
1267               << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1268
1269  assert(IntvIn && "Must have register in");
1270  assert(BI.LiveIn && "Must be live-in");
1271  assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1272
1273  if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1274    DEBUG(dbgs() << " before interference.\n");
1275    //
1276    //               <<<    Interference after kill.
1277    //     |---o---x   |    Killed in block.
1278    //     =========        Use IntvIn everywhere.
1279    //
1280    selectIntv(IntvIn);
1281    useIntv(Start, BI.LastInstr);
1282    return;
1283  }
1284
1285  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1286
1287  if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1288    //
1289    //               <<<    Possible interference after last use.
1290    //     |---o---o---|    Live-out on stack.
1291    //     =========____    Leave IntvIn after last use.
1292    //
1293    //                 <    Interference after last use.
1294    //     |---o---o--o|    Live-out on stack, late last use.
1295    //     ============     Copy to stack after LSP, overlap IntvIn.
1296    //            \_____    Stack interval is live-out.
1297    //
1298    if (BI.LastInstr < LSP) {
1299      DEBUG(dbgs() << ", spill after last use before interference.\n");
1300      selectIntv(IntvIn);
1301      SlotIndex Idx = leaveIntvAfter(BI.LastInstr);
1302      useIntv(Start, Idx);
1303      assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1304    } else {
1305      DEBUG(dbgs() << ", spill before last split point.\n");
1306      selectIntv(IntvIn);
1307      SlotIndex Idx = leaveIntvBefore(LSP);
1308      overlapIntv(Idx, BI.LastInstr);
1309      useIntv(Start, Idx);
1310      assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1311    }
1312    return;
1313  }
1314
1315  // The interference is overlapping somewhere we wanted to use IntvIn. That
1316  // means we need to create a local interval that can be allocated a
1317  // different register.
1318  unsigned LocalIntv = openIntv();
1319  (void)LocalIntv;
1320  DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1321
1322  if (!BI.LiveOut || BI.LastInstr < LSP) {
1323    //
1324    //           <<<<<<<    Interference overlapping uses.
1325    //     |---o---o---|    Live-out on stack.
1326    //     =====----____    Leave IntvIn before interference, then spill.
1327    //
1328    SlotIndex To = leaveIntvAfter(BI.LastInstr);
1329    SlotIndex From = enterIntvBefore(LeaveBefore);
1330    useIntv(From, To);
1331    selectIntv(IntvIn);
1332    useIntv(Start, From);
1333    assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1334    return;
1335  }
1336
1337  //           <<<<<<<    Interference overlapping uses.
1338  //     |---o---o--o|    Live-out on stack, late last use.
1339  //     =====-------     Copy to stack before LSP, overlap LocalIntv.
1340  //            \_____    Stack interval is live-out.
1341  //
1342  SlotIndex To = leaveIntvBefore(LSP);
1343  overlapIntv(To, BI.LastInstr);
1344  SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1345  useIntv(From, To);
1346  selectIntv(IntvIn);
1347  useIntv(Start, From);
1348  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1349}
1350
1351void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
1352                                   unsigned IntvOut, SlotIndex EnterAfter) {
1353  SlotIndex Start, Stop;
1354  tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1355
1356  DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1357               << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1358               << ", reg-out " << IntvOut << ", enter after " << EnterAfter
1359               << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1360
1361  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1362
1363  assert(IntvOut && "Must have register out");
1364  assert(BI.LiveOut && "Must be live-out");
1365  assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1366
1367  if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1368    DEBUG(dbgs() << " after interference.\n");
1369    //
1370    //    >>>>             Interference before def.
1371    //    |   o---o---|    Defined in block.
1372    //        =========    Use IntvOut everywhere.
1373    //
1374    selectIntv(IntvOut);
1375    useIntv(BI.FirstInstr, Stop);
1376    return;
1377  }
1378
1379  if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1380    DEBUG(dbgs() << ", reload after interference.\n");
1381    //
1382    //    >>>>             Interference before def.
1383    //    |---o---o---|    Live-through, stack-in.
1384    //    ____=========    Enter IntvOut before first use.
1385    //
1386    selectIntv(IntvOut);
1387    SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1388    useIntv(Idx, Stop);
1389    assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1390    return;
1391  }
1392
1393  // The interference is overlapping somewhere we wanted to use IntvOut. That
1394  // means we need to create a local interval that can be allocated a
1395  // different register.
1396  DEBUG(dbgs() << ", interference overlaps uses.\n");
1397  //
1398  //    >>>>>>>          Interference overlapping uses.
1399  //    |---o---o---|    Live-through, stack-in.
1400  //    ____---======    Create local interval for interference range.
1401  //
1402  selectIntv(IntvOut);
1403  SlotIndex Idx = enterIntvAfter(EnterAfter);
1404  useIntv(Idx, Stop);
1405  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1406
1407  openIntv();
1408  SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
1409  useIntv(From, Idx);
1410}
1411