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