dab1dfe4f1f856bcafe05deb5db7097b16a954ee
[oota-llvm.git] / lib / CodeGen / SplitKit.cpp
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 #include "SplitKit.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
18 #include "llvm/CodeGen/LiveRangeEdit.h"
19 #include "llvm/CodeGen/MachineDominators.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineLoopInfo.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/VirtRegMap.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetMachine.h"
28
29 using namespace llvm;
30
31 #define DEBUG_TYPE "regalloc"
32
33 STATISTIC(NumFinished, "Number of splits finished");
34 STATISTIC(NumSimple,   "Number of splits that were simple");
35 STATISTIC(NumCopies,   "Number of copies inserted for splitting");
36 STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
37 STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
38
39 //===----------------------------------------------------------------------===//
40 //                                 Split Analysis
41 //===----------------------------------------------------------------------===//
42
43 SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
44                              const MachineLoopInfo &mli)
45     : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
46       TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr),
47       LastSplitPoint(MF.getNumBlockIDs()) {}
48
49 void SplitAnalysis::clear() {
50   UseSlots.clear();
51   UseBlocks.clear();
52   ThroughBlocks.clear();
53   CurLI = nullptr;
54   DidRepairRange = false;
55 }
56
57 SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
58   const MachineBasicBlock *MBB = MF.getBlockNumbered(Num);
59   const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor();
60   std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num];
61   SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB);
62
63   // Compute split points on the first call. The pair is independent of the
64   // current live interval.
65   if (!LSP.first.isValid()) {
66     MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator();
67     if (FirstTerm == MBB->end())
68       LSP.first = MBBEnd;
69     else
70       LSP.first = LIS.getInstructionIndex(FirstTerm);
71
72     // If there is a landing pad successor, also find the call instruction.
73     if (!LPad)
74       return LSP.first;
75     // There may not be a call instruction (?) in which case we ignore LPad.
76     LSP.second = LSP.first;
77     for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin();
78          I != E;) {
79       --I;
80       if (I->isCall()) {
81         LSP.second = LIS.getInstructionIndex(I);
82         break;
83       }
84     }
85   }
86
87   // If CurLI is live into a landing pad successor, move the last split point
88   // back to the call that may throw.
89   if (!LPad || !LSP.second || !LIS.isLiveInToMBB(*CurLI, LPad))
90     return LSP.first;
91
92   // Find the value leaving MBB.
93   const VNInfo *VNI = CurLI->getVNInfoBefore(MBBEnd);
94   if (!VNI)
95     return LSP.first;
96
97   // If the value leaving MBB was defined after the call in MBB, it can't
98   // really be live-in to the landing pad.  This can happen if the landing pad
99   // has a PHI, and this register is undef on the exceptional edge.
100   // <rdar://problem/10664933>
101   if (!SlotIndex::isEarlierInstr(VNI->def, LSP.second) && VNI->def < MBBEnd)
102     return LSP.first;
103
104   // Value is properly live-in to the landing pad.
105   // Only allow splits before the call.
106   return LSP.second;
107 }
108
109 MachineBasicBlock::iterator
110 SplitAnalysis::getLastSplitPointIter(MachineBasicBlock *MBB) {
111   SlotIndex LSP = getLastSplitPoint(MBB->getNumber());
112   if (LSP == LIS.getMBBEndIdx(MBB))
113     return MBB->end();
114   return LIS.getInstructionFromIndex(LSP);
115 }
116
117 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
118 void SplitAnalysis::analyzeUses() {
119   assert(UseSlots.empty() && "Call clear first");
120
121   // First get all the defs from the interval values. This provides the correct
122   // slots for early clobbers.
123   for (const VNInfo *VNI : CurLI->valnos)
124     if (!VNI->isPHIDef() && !VNI->isUnused())
125       UseSlots.push_back(VNI->def);
126
127   // Get use slots form the use-def chain.
128   const MachineRegisterInfo &MRI = MF.getRegInfo();
129   for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
130     if (!MO.isUndef())
131       UseSlots.push_back(LIS.getInstructionIndex(MO.getParent()).getRegSlot());
132
133   array_pod_sort(UseSlots.begin(), UseSlots.end());
134
135   // Remove duplicates, keeping the smaller slot for each instruction.
136   // That is what we want for early clobbers.
137   UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
138                              SlotIndex::isSameInstr),
139                  UseSlots.end());
140
141   // Compute per-live block info.
142   if (!calcLiveBlockInfo()) {
143     // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
144     // I am looking at you, RegisterCoalescer!
145     DidRepairRange = true;
146     ++NumRepairs;
147     DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
148     const_cast<LiveIntervals&>(LIS)
149       .shrinkToUses(const_cast<LiveInterval*>(CurLI));
150     UseBlocks.clear();
151     ThroughBlocks.clear();
152     bool fixed = calcLiveBlockInfo();
153     (void)fixed;
154     assert(fixed && "Couldn't fix broken live interval");
155   }
156
157   DEBUG(dbgs() << "Analyze counted "
158                << UseSlots.size() << " instrs in "
159                << UseBlocks.size() << " blocks, through "
160                << NumThroughBlocks << " blocks.\n");
161 }
162
163 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
164 /// where CurLI is live.
165 bool SplitAnalysis::calcLiveBlockInfo() {
166   ThroughBlocks.resize(MF.getNumBlockIDs());
167   NumThroughBlocks = NumGapBlocks = 0;
168   if (CurLI->empty())
169     return true;
170
171   LiveInterval::const_iterator LVI = CurLI->begin();
172   LiveInterval::const_iterator LVE = CurLI->end();
173
174   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
175   UseI = UseSlots.begin();
176   UseE = UseSlots.end();
177
178   // Loop over basic blocks where CurLI is live.
179   MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
180   for (;;) {
181     BlockInfo BI;
182     BI.MBB = MFI;
183     SlotIndex Start, Stop;
184     std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
185
186     // If the block contains no uses, the range must be live through. At one
187     // point, RegisterCoalescer could create dangling ranges that ended
188     // mid-block.
189     if (UseI == UseE || *UseI >= Stop) {
190       ++NumThroughBlocks;
191       ThroughBlocks.set(BI.MBB->getNumber());
192       // The range shouldn't end mid-block if there are no uses. This shouldn't
193       // happen.
194       if (LVI->end < Stop)
195         return false;
196     } else {
197       // This block has uses. Find the first and last uses in the block.
198       BI.FirstInstr = *UseI;
199       assert(BI.FirstInstr >= Start);
200       do ++UseI;
201       while (UseI != UseE && *UseI < Stop);
202       BI.LastInstr = UseI[-1];
203       assert(BI.LastInstr < Stop);
204
205       // LVI is the first live segment overlapping MBB.
206       BI.LiveIn = LVI->start <= Start;
207
208       // When not live in, the first use should be a def.
209       if (!BI.LiveIn) {
210         assert(LVI->start == LVI->valno->def && "Dangling Segment start");
211         assert(LVI->start == BI.FirstInstr && "First instr should be a def");
212         BI.FirstDef = BI.FirstInstr;
213       }
214
215       // Look for gaps in the live range.
216       BI.LiveOut = true;
217       while (LVI->end < Stop) {
218         SlotIndex LastStop = LVI->end;
219         if (++LVI == LVE || LVI->start >= Stop) {
220           BI.LiveOut = false;
221           BI.LastInstr = LastStop;
222           break;
223         }
224
225         if (LastStop < LVI->start) {
226           // There is a gap in the live range. Create duplicate entries for the
227           // live-in snippet and the live-out snippet.
228           ++NumGapBlocks;
229
230           // Push the Live-in part.
231           BI.LiveOut = false;
232           UseBlocks.push_back(BI);
233           UseBlocks.back().LastInstr = LastStop;
234
235           // Set up BI for the live-out part.
236           BI.LiveIn = false;
237           BI.LiveOut = true;
238           BI.FirstInstr = BI.FirstDef = LVI->start;
239         }
240
241         // A Segment that starts in the middle of the block must be a def.
242         assert(LVI->start == LVI->valno->def && "Dangling Segment start");
243         if (!BI.FirstDef)
244           BI.FirstDef = LVI->start;
245       }
246
247       UseBlocks.push_back(BI);
248
249       // LVI is now at LVE or LVI->end >= Stop.
250       if (LVI == LVE)
251         break;
252     }
253
254     // Live segment ends exactly at Stop. Move to the next segment.
255     if (LVI->end == Stop && ++LVI == LVE)
256       break;
257
258     // Pick the next basic block.
259     if (LVI->start < Stop)
260       ++MFI;
261     else
262       MFI = LIS.getMBBFromIndex(LVI->start);
263   }
264
265   assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
266   return true;
267 }
268
269 unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
270   if (cli->empty())
271     return 0;
272   LiveInterval *li = const_cast<LiveInterval*>(cli);
273   LiveInterval::iterator LVI = li->begin();
274   LiveInterval::iterator LVE = li->end();
275   unsigned Count = 0;
276
277   // Loop over basic blocks where li is live.
278   MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start);
279   SlotIndex Stop = LIS.getMBBEndIdx(MFI);
280   for (;;) {
281     ++Count;
282     LVI = li->advanceTo(LVI, Stop);
283     if (LVI == LVE)
284       return Count;
285     do {
286       ++MFI;
287       Stop = LIS.getMBBEndIdx(MFI);
288     } while (Stop <= LVI->start);
289   }
290 }
291
292 bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
293   unsigned OrigReg = VRM.getOriginal(CurLI->reg);
294   const LiveInterval &Orig = LIS.getInterval(OrigReg);
295   assert(!Orig.empty() && "Splitting empty interval?");
296   LiveInterval::const_iterator I = Orig.find(Idx);
297
298   // Range containing Idx should begin at Idx.
299   if (I != Orig.end() && I->start <= Idx)
300     return I->start == Idx;
301
302   // Range does not contain Idx, previous must end at Idx.
303   return I != Orig.begin() && (--I)->end == Idx;
304 }
305
306 void SplitAnalysis::analyze(const LiveInterval *li) {
307   clear();
308   CurLI = li;
309   analyzeUses();
310 }
311
312
313 //===----------------------------------------------------------------------===//
314 //                               Split Editor
315 //===----------------------------------------------------------------------===//
316
317 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
318 SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
319                          MachineDominatorTree &mdt,
320                          MachineBlockFrequencyInfo &mbfi)
321     : SA(sa), LIS(lis), VRM(vrm), MRI(vrm.getMachineFunction().getRegInfo()),
322       MDT(mdt), TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
323       TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
324       MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition),
325       RegAssign(Allocator) {}
326
327 void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
328   Edit = &LRE;
329   SpillMode = SM;
330   OpenIdx = 0;
331   RegAssign.clear();
332   Values.clear();
333
334   // Reset the LiveRangeCalc instances needed for this spill mode.
335   LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
336                   &LIS.getVNInfoAllocator());
337   if (SpillMode)
338     LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
339                     &LIS.getVNInfoAllocator());
340
341   // We don't need an AliasAnalysis since we will only be performing
342   // cheap-as-a-copy remats anyway.
343   Edit->anyRematerializable(nullptr);
344 }
345
346 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
347 void SplitEditor::dump() const {
348   if (RegAssign.empty()) {
349     dbgs() << " empty\n";
350     return;
351   }
352
353   for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
354     dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
355   dbgs() << '\n';
356 }
357 #endif
358
359 VNInfo *SplitEditor::defValue(unsigned RegIdx,
360                               const VNInfo *ParentVNI,
361                               SlotIndex Idx) {
362   assert(ParentVNI && "Mapping  NULL value");
363   assert(Idx.isValid() && "Invalid SlotIndex");
364   assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
365   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
366
367   // Create a new value.
368   VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
369
370   // Use insert for lookup, so we can add missing values with a second lookup.
371   std::pair<ValueMap::iterator, bool> InsP =
372     Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id),
373                                  ValueForcePair(VNI, false)));
374
375   // This was the first time (RegIdx, ParentVNI) was mapped.
376   // Keep it as a simple def without any liveness.
377   if (InsP.second)
378     return VNI;
379
380   // If the previous value was a simple mapping, add liveness for it now.
381   if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
382     SlotIndex Def = OldVNI->def;
383     LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI));
384     // No longer a simple mapping.  Switch to a complex, non-forced mapping.
385     InsP.first->second = ValueForcePair();
386   }
387
388   // This is a complex mapping, add liveness for VNI
389   SlotIndex Def = VNI->def;
390   LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
391
392   return VNI;
393 }
394
395 void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
396   assert(ParentVNI && "Mapping  NULL value");
397   ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
398   VNInfo *VNI = VFP.getPointer();
399
400   // ParentVNI was either unmapped or already complex mapped. Either way, just
401   // set the force bit.
402   if (!VNI) {
403     VFP.setInt(true);
404     return;
405   }
406
407   // This was previously a single mapping. Make sure the old def is represented
408   // by a trivial live range.
409   SlotIndex Def = VNI->def;
410   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
411   LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
412   // Mark as complex mapped, forced.
413   VFP = ValueForcePair(nullptr, true);
414 }
415
416 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
417                                    VNInfo *ParentVNI,
418                                    SlotIndex UseIdx,
419                                    MachineBasicBlock &MBB,
420                                    MachineBasicBlock::iterator I) {
421   MachineInstr *CopyMI = nullptr;
422   SlotIndex Def;
423   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
424
425   // We may be trying to avoid interference that ends at a deleted instruction,
426   // so always begin RegIdx 0 early and all others late.
427   bool Late = RegIdx != 0;
428
429   // Attempt cheap-as-a-copy rematerialization.
430   LiveRangeEdit::Remat RM(ParentVNI);
431   if (Edit->canRematerializeAt(RM, UseIdx, true)) {
432     Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late);
433     ++NumRemats;
434   } else {
435     // Can't remat, just insert a copy from parent.
436     CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
437                .addReg(Edit->getReg());
438     Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late)
439             .getRegSlot();
440     ++NumCopies;
441   }
442
443   // Define the value in Reg.
444   return defValue(RegIdx, ParentVNI, Def);
445 }
446
447 /// Create a new virtual register and live interval.
448 unsigned SplitEditor::openIntv() {
449   // Create the complement as index 0.
450   if (Edit->empty())
451     Edit->createEmptyInterval();
452
453   // Create the open interval.
454   OpenIdx = Edit->size();
455   Edit->createEmptyInterval();
456   return OpenIdx;
457 }
458
459 void SplitEditor::selectIntv(unsigned Idx) {
460   assert(Idx != 0 && "Cannot select the complement interval");
461   assert(Idx < Edit->size() && "Can only select previously opened interval");
462   DEBUG(dbgs() << "    selectIntv " << OpenIdx << " -> " << Idx << '\n');
463   OpenIdx = Idx;
464 }
465
466 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
467   assert(OpenIdx && "openIntv not called before enterIntvBefore");
468   DEBUG(dbgs() << "    enterIntvBefore " << Idx);
469   Idx = Idx.getBaseIndex();
470   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
471   if (!ParentVNI) {
472     DEBUG(dbgs() << ": not live\n");
473     return Idx;
474   }
475   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
476   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
477   assert(MI && "enterIntvBefore called with invalid index");
478
479   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
480   return VNI->def;
481 }
482
483 SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {
484   assert(OpenIdx && "openIntv not called before enterIntvAfter");
485   DEBUG(dbgs() << "    enterIntvAfter " << Idx);
486   Idx = Idx.getBoundaryIndex();
487   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
488   if (!ParentVNI) {
489     DEBUG(dbgs() << ": not live\n");
490     return Idx;
491   }
492   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
493   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
494   assert(MI && "enterIntvAfter called with invalid index");
495
496   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
497                               std::next(MachineBasicBlock::iterator(MI)));
498   return VNI->def;
499 }
500
501 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
502   assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
503   SlotIndex End = LIS.getMBBEndIdx(&MBB);
504   SlotIndex Last = End.getPrevSlot();
505   DEBUG(dbgs() << "    enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
506   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
507   if (!ParentVNI) {
508     DEBUG(dbgs() << ": not live\n");
509     return End;
510   }
511   DEBUG(dbgs() << ": valno " << ParentVNI->id);
512   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
513                               SA.getLastSplitPointIter(&MBB));
514   RegAssign.insert(VNI->def, End, OpenIdx);
515   DEBUG(dump());
516   return VNI->def;
517 }
518
519 /// useIntv - indicate that all instructions in MBB should use OpenLI.
520 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
521   useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
522 }
523
524 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
525   assert(OpenIdx && "openIntv not called before useIntv");
526   DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
527   RegAssign.insert(Start, End, OpenIdx);
528   DEBUG(dump());
529 }
530
531 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
532   assert(OpenIdx && "openIntv not called before leaveIntvAfter");
533   DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
534
535   // The interval must be live beyond the instruction at Idx.
536   SlotIndex Boundary = Idx.getBoundaryIndex();
537   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
538   if (!ParentVNI) {
539     DEBUG(dbgs() << ": not live\n");
540     return Boundary.getNextSlot();
541   }
542   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
543   MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
544   assert(MI && "No instruction at index");
545
546   // In spill mode, make live ranges as short as possible by inserting the copy
547   // before MI.  This is only possible if that instruction doesn't redefine the
548   // value.  The inserted COPY is not a kill, and we don't need to recompute
549   // the source live range.  The spiller also won't try to hoist this copy.
550   if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
551       MI->readsVirtualRegister(Edit->getReg())) {
552     forceRecompute(0, ParentVNI);
553     defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
554     return Idx;
555   }
556
557   VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
558                               std::next(MachineBasicBlock::iterator(MI)));
559   return VNI->def;
560 }
561
562 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
563   assert(OpenIdx && "openIntv not called before leaveIntvBefore");
564   DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
565
566   // The interval must be live into the instruction at Idx.
567   Idx = Idx.getBaseIndex();
568   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
569   if (!ParentVNI) {
570     DEBUG(dbgs() << ": not live\n");
571     return Idx.getNextSlot();
572   }
573   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
574
575   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
576   assert(MI && "No instruction at index");
577   VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
578   return VNI->def;
579 }
580
581 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
582   assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
583   SlotIndex Start = LIS.getMBBStartIdx(&MBB);
584   DEBUG(dbgs() << "    leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
585
586   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
587   if (!ParentVNI) {
588     DEBUG(dbgs() << ": not live\n");
589     return Start;
590   }
591
592   VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
593                               MBB.SkipPHIsAndLabels(MBB.begin()));
594   RegAssign.insert(Start, VNI->def, OpenIdx);
595   DEBUG(dump());
596   return VNI->def;
597 }
598
599 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
600   assert(OpenIdx && "openIntv not called before overlapIntv");
601   const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
602   assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
603          "Parent changes value in extended range");
604   assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
605          "Range cannot span basic blocks");
606
607   // The complement interval will be extended as needed by LRCalc.extend().
608   if (ParentVNI)
609     forceRecompute(0, ParentVNI);
610   DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
611   RegAssign.insert(Start, End, OpenIdx);
612   DEBUG(dump());
613 }
614
615 //===----------------------------------------------------------------------===//
616 //                                  Spill modes
617 //===----------------------------------------------------------------------===//
618
619 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
620   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
621   DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
622   RegAssignMap::iterator AssignI;
623   AssignI.setMap(RegAssign);
624
625   for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
626     SlotIndex Def = Copies[i]->def;
627     MachineInstr *MI = LIS.getInstructionFromIndex(Def);
628     assert(MI && "No instruction for back-copy");
629
630     MachineBasicBlock *MBB = MI->getParent();
631     MachineBasicBlock::iterator MBBI(MI);
632     bool AtBegin;
633     do AtBegin = MBBI == MBB->begin();
634     while (!AtBegin && (--MBBI)->isDebugValue());
635
636     DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
637     LIS.removeVRegDefAt(*LI, Def);
638     LIS.RemoveMachineInstrFromMaps(MI);
639     MI->eraseFromParent();
640
641     // Adjust RegAssign if a register assignment is killed at Def. We want to
642     // avoid calculating the live range of the source register if possible.
643     AssignI.find(Def.getPrevSlot());
644     if (!AssignI.valid() || AssignI.start() >= Def)
645       continue;
646     // If MI doesn't kill the assigned register, just leave it.
647     if (AssignI.stop() != Def)
648       continue;
649     unsigned RegIdx = AssignI.value();
650     if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
651       DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx << '\n');
652       forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
653     } else {
654       SlotIndex Kill = LIS.getInstructionIndex(MBBI).getRegSlot();
655       DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
656       AssignI.setStop(Kill);
657     }
658   }
659 }
660
661 MachineBasicBlock*
662 SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
663                                   MachineBasicBlock *DefMBB) {
664   if (MBB == DefMBB)
665     return MBB;
666   assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
667
668   const MachineLoopInfo &Loops = SA.Loops;
669   const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
670   MachineDomTreeNode *DefDomNode = MDT[DefMBB];
671
672   // Best candidate so far.
673   MachineBasicBlock *BestMBB = MBB;
674   unsigned BestDepth = UINT_MAX;
675
676   for (;;) {
677     const MachineLoop *Loop = Loops.getLoopFor(MBB);
678
679     // MBB isn't in a loop, it doesn't get any better.  All dominators have a
680     // higher frequency by definition.
681     if (!Loop) {
682       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
683                    << MBB->getNumber() << " at depth 0\n");
684       return MBB;
685     }
686
687     // We'll never be able to exit the DefLoop.
688     if (Loop == DefLoop) {
689       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
690                    << MBB->getNumber() << " in the same loop\n");
691       return MBB;
692     }
693
694     // Least busy dominator seen so far.
695     unsigned Depth = Loop->getLoopDepth();
696     if (Depth < BestDepth) {
697       BestMBB = MBB;
698       BestDepth = Depth;
699       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
700                    << MBB->getNumber() << " at depth " << Depth << '\n');
701     }
702
703     // Leave loop by going to the immediate dominator of the loop header.
704     // This is a bigger stride than simply walking up the dominator tree.
705     MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
706
707     // Too far up the dominator tree?
708     if (!IDom || !MDT.dominates(DefDomNode, IDom))
709       return BestMBB;
710
711     MBB = IDom->getBlock();
712   }
713 }
714
715 void SplitEditor::hoistCopiesForSize() {
716   // Get the complement interval, always RegIdx 0.
717   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
718   LiveInterval *Parent = &Edit->getParent();
719
720   // Track the nearest common dominator for all back-copies for each ParentVNI,
721   // indexed by ParentVNI->id.
722   typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair;
723   SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
724
725   // Find the nearest common dominator for parent values with multiple
726   // back-copies.  If a single back-copy dominates, put it in DomPair.second.
727   for (VNInfo *VNI : LI->valnos) {
728     if (VNI->isUnused())
729       continue;
730     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
731     assert(ParentVNI && "Parent not live at complement def");
732
733     // Don't hoist remats.  The complement is probably going to disappear
734     // completely anyway.
735     if (Edit->didRematerialize(ParentVNI))
736       continue;
737
738     MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
739     DomPair &Dom = NearestDom[ParentVNI->id];
740
741     // Keep directly defined parent values.  This is either a PHI or an
742     // instruction in the complement range.  All other copies of ParentVNI
743     // should be eliminated.
744     if (VNI->def == ParentVNI->def) {
745       DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
746       Dom = DomPair(ValMBB, VNI->def);
747       continue;
748     }
749     // Skip the singly mapped values.  There is nothing to gain from hoisting a
750     // single back-copy.
751     if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
752       DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
753       continue;
754     }
755
756     if (!Dom.first) {
757       // First time we see ParentVNI.  VNI dominates itself.
758       Dom = DomPair(ValMBB, VNI->def);
759     } else if (Dom.first == ValMBB) {
760       // Two defs in the same block.  Pick the earlier def.
761       if (!Dom.second.isValid() || VNI->def < Dom.second)
762         Dom.second = VNI->def;
763     } else {
764       // Different basic blocks. Check if one dominates.
765       MachineBasicBlock *Near =
766         MDT.findNearestCommonDominator(Dom.first, ValMBB);
767       if (Near == ValMBB)
768         // Def ValMBB dominates.
769         Dom = DomPair(ValMBB, VNI->def);
770       else if (Near != Dom.first)
771         // None dominate. Hoist to common dominator, need new def.
772         Dom = DomPair(Near, SlotIndex());
773     }
774
775     DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def
776                  << " for parent " << ParentVNI->id << '@' << ParentVNI->def
777                  << " hoist to BB#" << Dom.first->getNumber() << ' '
778                  << Dom.second << '\n');
779   }
780
781   // Insert the hoisted copies.
782   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
783     DomPair &Dom = NearestDom[i];
784     if (!Dom.first || Dom.second.isValid())
785       continue;
786     // This value needs a hoisted copy inserted at the end of Dom.first.
787     VNInfo *ParentVNI = Parent->getValNumInfo(i);
788     MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
789     // Get a less loopy dominator than Dom.first.
790     Dom.first = findShallowDominator(Dom.first, DefMBB);
791     SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
792     Dom.second =
793       defFromParent(0, ParentVNI, Last, *Dom.first,
794                     SA.getLastSplitPointIter(Dom.first))->def;
795   }
796
797   // Remove redundant back-copies that are now known to be dominated by another
798   // def with the same value.
799   SmallVector<VNInfo*, 8> BackCopies;
800   for (VNInfo *VNI : LI->valnos) {
801     if (VNI->isUnused())
802       continue;
803     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
804     const DomPair &Dom = NearestDom[ParentVNI->id];
805     if (!Dom.first || Dom.second == VNI->def)
806       continue;
807     BackCopies.push_back(VNI);
808     forceRecompute(0, ParentVNI);
809   }
810   removeBackCopies(BackCopies);
811 }
812
813
814 /// transferValues - Transfer all possible values to the new live ranges.
815 /// Values that were rematerialized are left alone, they need LRCalc.extend().
816 bool SplitEditor::transferValues() {
817   bool Skipped = false;
818   RegAssignMap::const_iterator AssignI = RegAssign.begin();
819   for (const LiveRange::Segment &S : Edit->getParent()) {
820     DEBUG(dbgs() << "  blit " << S << ':');
821     VNInfo *ParentVNI = S.valno;
822     // RegAssign has holes where RegIdx 0 should be used.
823     SlotIndex Start = S.start;
824     AssignI.advanceTo(Start);
825     do {
826       unsigned RegIdx;
827       SlotIndex End = S.end;
828       if (!AssignI.valid()) {
829         RegIdx = 0;
830       } else if (AssignI.start() <= Start) {
831         RegIdx = AssignI.value();
832         if (AssignI.stop() < End) {
833           End = AssignI.stop();
834           ++AssignI;
835         }
836       } else {
837         RegIdx = 0;
838         End = std::min(End, AssignI.start());
839       }
840
841       // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
842       DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx);
843       LiveRange &LR = LIS.getInterval(Edit->get(RegIdx));
844
845       // Check for a simply defined value that can be blitted directly.
846       ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
847       if (VNInfo *VNI = VFP.getPointer()) {
848         DEBUG(dbgs() << ':' << VNI->id);
849         LR.addSegment(LiveInterval::Segment(Start, End, VNI));
850         Start = End;
851         continue;
852       }
853
854       // Skip values with forced recomputation.
855       if (VFP.getInt()) {
856         DEBUG(dbgs() << "(recalc)");
857         Skipped = true;
858         Start = End;
859         continue;
860       }
861
862       LiveRangeCalc &LRC = getLRCalc(RegIdx);
863
864       // This value has multiple defs in RegIdx, but it wasn't rematerialized,
865       // so the live range is accurate. Add live-in blocks in [Start;End) to the
866       // LiveInBlocks.
867       MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
868       SlotIndex BlockStart, BlockEnd;
869       std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB);
870
871       // The first block may be live-in, or it may have its own def.
872       if (Start != BlockStart) {
873         VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
874         assert(VNI && "Missing def for complex mapped value");
875         DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
876         // MBB has its own def. Is it also live-out?
877         if (BlockEnd <= End)
878           LRC.setLiveOutValue(MBB, VNI);
879
880         // Skip to the next block for live-in.
881         ++MBB;
882         BlockStart = BlockEnd;
883       }
884
885       // Handle the live-in blocks covered by [Start;End).
886       assert(Start <= BlockStart && "Expected live-in block");
887       while (BlockStart < End) {
888         DEBUG(dbgs() << ">BB#" << MBB->getNumber());
889         BlockEnd = LIS.getMBBEndIdx(MBB);
890         if (BlockStart == ParentVNI->def) {
891           // This block has the def of a parent PHI, so it isn't live-in.
892           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
893           VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
894           assert(VNI && "Missing def for complex mapped parent PHI");
895           if (End >= BlockEnd)
896             LRC.setLiveOutValue(MBB, VNI); // Live-out as well.
897         } else {
898           // This block needs a live-in value.  The last block covered may not
899           // be live-out.
900           if (End < BlockEnd)
901             LRC.addLiveInBlock(LR, MDT[MBB], End);
902           else {
903             // Live-through, and we don't know the value.
904             LRC.addLiveInBlock(LR, MDT[MBB]);
905             LRC.setLiveOutValue(MBB, nullptr);
906           }
907         }
908         BlockStart = BlockEnd;
909         ++MBB;
910       }
911       Start = End;
912     } while (Start != S.end);
913     DEBUG(dbgs() << '\n');
914   }
915
916   LRCalc[0].calculateValues();
917   if (SpillMode)
918     LRCalc[1].calculateValues();
919
920   return Skipped;
921 }
922
923 void SplitEditor::extendPHIKillRanges() {
924     // Extend live ranges to be live-out for successor PHI values.
925   for (const VNInfo *PHIVNI : Edit->getParent().valnos) {
926     if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
927       continue;
928     unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
929     LiveRange &LR = LIS.getInterval(Edit->get(RegIdx));
930     LiveRangeCalc &LRC = getLRCalc(RegIdx);
931     MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
932     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
933          PE = MBB->pred_end(); PI != PE; ++PI) {
934       SlotIndex End = LIS.getMBBEndIdx(*PI);
935       SlotIndex LastUse = End.getPrevSlot();
936       // The predecessor may not have a live-out value. That is OK, like an
937       // undef PHI operand.
938       if (Edit->getParent().liveAt(LastUse)) {
939         assert(RegAssign.lookup(LastUse) == RegIdx &&
940                "Different register assignment in phi predecessor");
941         LRC.extend(LR, End);
942       }
943     }
944   }
945 }
946
947 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
948 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
949   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
950        RE = MRI.reg_end(); RI != RE;) {
951     MachineOperand &MO = *RI;
952     MachineInstr *MI = MO.getParent();
953     ++RI;
954     // LiveDebugVariables should have handled all DBG_VALUE instructions.
955     if (MI->isDebugValue()) {
956       DEBUG(dbgs() << "Zapping " << *MI);
957       MO.setReg(0);
958       continue;
959     }
960
961     // <undef> operands don't really read the register, so it doesn't matter
962     // which register we choose.  When the use operand is tied to a def, we must
963     // use the same register as the def, so just do that always.
964     SlotIndex Idx = LIS.getInstructionIndex(MI);
965     if (MO.isDef() || MO.isUndef())
966       Idx = Idx.getRegSlot(MO.isEarlyClobber());
967
968     // Rewrite to the mapped register at Idx.
969     unsigned RegIdx = RegAssign.lookup(Idx);
970     LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
971     MO.setReg(LI->reg);
972     DEBUG(dbgs() << "  rewr BB#" << MI->getParent()->getNumber() << '\t'
973                  << Idx << ':' << RegIdx << '\t' << *MI);
974
975     // Extend liveness to Idx if the instruction reads reg.
976     if (!ExtendRanges || MO.isUndef())
977       continue;
978
979     // Skip instructions that don't read Reg.
980     if (MO.isDef()) {
981       if (!MO.getSubReg() && !MO.isEarlyClobber())
982         continue;
983       // We may wan't to extend a live range for a partial redef, or for a use
984       // tied to an early clobber.
985       Idx = Idx.getPrevSlot();
986       if (!Edit->getParent().liveAt(Idx))
987         continue;
988     } else
989       Idx = Idx.getRegSlot(true);
990
991     getLRCalc(RegIdx).extend(*LI, Idx.getNextSlot());
992   }
993 }
994
995 void SplitEditor::deleteRematVictims() {
996   SmallVector<MachineInstr*, 8> Dead;
997   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
998     LiveInterval *LI = &LIS.getInterval(*I);
999     for (const LiveRange::Segment &S : LI->segments) {
1000       // Dead defs end at the dead slot.
1001       if (S.end != S.valno->def.getDeadSlot())
1002         continue;
1003       MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1004       assert(MI && "Missing instruction for dead def");
1005       MI->addRegisterDead(LI->reg, &TRI);
1006
1007       if (!MI->allDefsAreDead())
1008         continue;
1009
1010       DEBUG(dbgs() << "All defs dead: " << *MI);
1011       Dead.push_back(MI);
1012     }
1013   }
1014
1015   if (Dead.empty())
1016     return;
1017
1018   Edit->eliminateDeadDefs(Dead);
1019 }
1020
1021 void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
1022   ++NumFinished;
1023
1024   // At this point, the live intervals in Edit contain VNInfos corresponding to
1025   // the inserted copies.
1026
1027   // Add the original defs from the parent interval.
1028   for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1029     if (ParentVNI->isUnused())
1030       continue;
1031     unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1032     defValue(RegIdx, ParentVNI, ParentVNI->def);
1033
1034     // Force rematted values to be recomputed everywhere.
1035     // The new live ranges may be truncated.
1036     if (Edit->didRematerialize(ParentVNI))
1037       for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1038         forceRecompute(i, ParentVNI);
1039   }
1040
1041   // Hoist back-copies to the complement interval when in spill mode.
1042   switch (SpillMode) {
1043   case SM_Partition:
1044     // Leave all back-copies as is.
1045     break;
1046   case SM_Size:
1047     hoistCopiesForSize();
1048     break;
1049   case SM_Speed:
1050     llvm_unreachable("Spill mode 'speed' not implemented yet");
1051   }
1052
1053   // Transfer the simply mapped values, check if any are skipped.
1054   bool Skipped = transferValues();
1055   if (Skipped)
1056     extendPHIKillRanges();
1057   else
1058     ++NumSimple;
1059
1060   // Rewrite virtual registers, possibly extending ranges.
1061   rewriteAssigned(Skipped);
1062
1063   // Delete defs that were rematted everywhere.
1064   if (Skipped)
1065     deleteRematVictims();
1066
1067   // Get rid of unused values and set phi-kill flags.
1068   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) {
1069     LiveInterval &LI = LIS.getInterval(*I);
1070     LI.RenumberValues();
1071   }
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 = &LIS.getInterval(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->createEmptyInterval());
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(), SA.Loops, MBFI);
1101
1102   assert(!LRMap || LRMap->size() == Edit->size());
1103 }
1104
1105
1106 //===----------------------------------------------------------------------===//
1107 //                            Single Block Splitting
1108 //===----------------------------------------------------------------------===//
1109
1110 bool 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
1128 void 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
1155 void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
1156                                         unsigned IntvIn, SlotIndex LeaveBefore,
1157                                         unsigned IntvOut, SlotIndex EnterAfter){
1158   SlotIndex Start, Stop;
1159   std::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
1259 void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
1260                                   unsigned IntvIn, SlotIndex LeaveBefore) {
1261   SlotIndex Start, Stop;
1262   std::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
1351 void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
1352                                    unsigned IntvOut, SlotIndex EnterAfter) {
1353   SlotIndex Start, Stop;
1354   std::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 }