xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/SplitKit.cpp (revision 25ecdc7d52770caf1c9b44b5ec11f468f6b636f3)
1 //===- SplitKit.cpp - Toolkit for splitting live ranges -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains the SplitAnalysis class as well as mutator functions for
10 // live range splitting.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "SplitKit.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/None.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/CodeGen/LiveInterval.h"
24 #include "llvm/CodeGen/LiveIntervalCalc.h"
25 #include "llvm/CodeGen/LiveIntervals.h"
26 #include "llvm/CodeGen/LiveRangeEdit.h"
27 #include "llvm/CodeGen/MachineBasicBlock.h"
28 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
29 #include "llvm/CodeGen/MachineDominators.h"
30 #include "llvm/CodeGen/MachineFunction.h"
31 #include "llvm/CodeGen/MachineInstr.h"
32 #include "llvm/CodeGen/MachineInstrBuilder.h"
33 #include "llvm/CodeGen/MachineLoopInfo.h"
34 #include "llvm/CodeGen/MachineOperand.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/SlotIndexes.h"
37 #include "llvm/CodeGen/TargetInstrInfo.h"
38 #include "llvm/CodeGen/TargetOpcodes.h"
39 #include "llvm/CodeGen/TargetRegisterInfo.h"
40 #include "llvm/CodeGen/TargetSubtargetInfo.h"
41 #include "llvm/CodeGen/VirtRegMap.h"
42 #include "llvm/Config/llvm-config.h"
43 #include "llvm/IR/DebugLoc.h"
44 #include "llvm/MC/LaneBitmask.h"
45 #include "llvm/Support/Allocator.h"
46 #include "llvm/Support/BlockFrequency.h"
47 #include "llvm/Support/Compiler.h"
48 #include "llvm/Support/Debug.h"
49 #include "llvm/Support/ErrorHandling.h"
50 #include "llvm/Support/raw_ostream.h"
51 #include <algorithm>
52 #include <cassert>
53 #include <iterator>
54 #include <limits>
55 #include <tuple>
56 #include <utility>
57 
58 using namespace llvm;
59 
60 #define DEBUG_TYPE "regalloc"
61 
62 STATISTIC(NumFinished, "Number of splits finished");
63 STATISTIC(NumSimple,   "Number of splits that were simple");
64 STATISTIC(NumCopies,   "Number of copies inserted for splitting");
65 STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
66 STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
67 
68 //===----------------------------------------------------------------------===//
69 //                     Last Insert Point Analysis
70 //===----------------------------------------------------------------------===//
71 
72 InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
73                                          unsigned BBNum)
74     : LIS(lis), LastInsertPoint(BBNum) {}
75 
76 SlotIndex
77 InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
78                                             const MachineBasicBlock &MBB) {
79   unsigned Num = MBB.getNumber();
80   std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
81   SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);
82 
83   SmallVector<const MachineBasicBlock *, 1> ExceptionalSuccessors;
84   bool EHPadSuccessor = false;
85   for (const MachineBasicBlock *SMBB : MBB.successors()) {
86     if (SMBB->isEHPad()) {
87       ExceptionalSuccessors.push_back(SMBB);
88       EHPadSuccessor = true;
89     } else if (SMBB->isInlineAsmBrIndirectTarget())
90       ExceptionalSuccessors.push_back(SMBB);
91   }
92 
93   // Compute insert points on the first call. The pair is independent of the
94   // current live interval.
95   if (!LIP.first.isValid()) {
96     MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();
97     if (FirstTerm == MBB.end())
98       LIP.first = MBBEnd;
99     else
100       LIP.first = LIS.getInstructionIndex(*FirstTerm);
101 
102     // If there is a landing pad or inlineasm_br successor, also find the
103     // instruction. If there is no such instruction, we don't need to do
104     // anything special.  We assume there cannot be multiple instructions that
105     // are Calls with EHPad successors or INLINEASM_BR in a block. Further, we
106     // assume that if there are any, they will be after any other call
107     // instructions in the block.
108     if (ExceptionalSuccessors.empty())
109       return LIP.first;
110     for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
111       if ((EHPadSuccessor && I->isCall()) ||
112           I->getOpcode() == TargetOpcode::INLINEASM_BR) {
113         LIP.second = LIS.getInstructionIndex(*I);
114         break;
115       }
116     }
117   }
118 
119   // If CurLI is live into a landing pad successor, move the last insert point
120   // back to the call that may throw.
121   if (!LIP.second)
122     return LIP.first;
123 
124   if (none_of(ExceptionalSuccessors, [&](const MachineBasicBlock *EHPad) {
125         return LIS.isLiveInToMBB(CurLI, EHPad);
126       }))
127     return LIP.first;
128 
129   // Find the value leaving MBB.
130   const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
131   if (!VNI)
132     return LIP.first;
133 
134   // If the value leaving MBB was defined after the call in MBB, it can't
135   // really be live-in to the landing pad.  This can happen if the landing pad
136   // has a PHI, and this register is undef on the exceptional edge.
137   // <rdar://problem/10664933>
138   if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
139     return LIP.first;
140 
141   // Value is properly live-in to the landing pad.
142   // Only allow inserts before the call.
143   return LIP.second;
144 }
145 
146 MachineBasicBlock::iterator
147 InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,
148                                             MachineBasicBlock &MBB) {
149   SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
150   if (LIP == LIS.getMBBEndIdx(&MBB))
151     return MBB.end();
152   return LIS.getInstructionFromIndex(LIP);
153 }
154 
155 //===----------------------------------------------------------------------===//
156 //                                 Split Analysis
157 //===----------------------------------------------------------------------===//
158 
159 SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
160                              const MachineLoopInfo &mli)
161     : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
162       TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
163 
164 void SplitAnalysis::clear() {
165   UseSlots.clear();
166   UseBlocks.clear();
167   ThroughBlocks.clear();
168   CurLI = nullptr;
169   DidRepairRange = false;
170 }
171 
172 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
173 void SplitAnalysis::analyzeUses() {
174   assert(UseSlots.empty() && "Call clear first");
175 
176   // First get all the defs from the interval values. This provides the correct
177   // slots for early clobbers.
178   for (const VNInfo *VNI : CurLI->valnos)
179     if (!VNI->isPHIDef() && !VNI->isUnused())
180       UseSlots.push_back(VNI->def);
181 
182   // Get use slots form the use-def chain.
183   const MachineRegisterInfo &MRI = MF.getRegInfo();
184   for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
185     if (!MO.isUndef())
186       UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());
187 
188   array_pod_sort(UseSlots.begin(), UseSlots.end());
189 
190   // Remove duplicates, keeping the smaller slot for each instruction.
191   // That is what we want for early clobbers.
192   UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
193                              SlotIndex::isSameInstr),
194                  UseSlots.end());
195 
196   // Compute per-live block info.
197   if (!calcLiveBlockInfo()) {
198     // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
199     // I am looking at you, RegisterCoalescer!
200     DidRepairRange = true;
201     ++NumRepairs;
202     LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
203     const_cast<LiveIntervals&>(LIS)
204       .shrinkToUses(const_cast<LiveInterval*>(CurLI));
205     UseBlocks.clear();
206     ThroughBlocks.clear();
207     bool fixed = calcLiveBlockInfo();
208     (void)fixed;
209     assert(fixed && "Couldn't fix broken live interval");
210   }
211 
212   LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "
213                     << UseBlocks.size() << " blocks, through "
214                     << NumThroughBlocks << " blocks.\n");
215 }
216 
217 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
218 /// where CurLI is live.
219 bool SplitAnalysis::calcLiveBlockInfo() {
220   ThroughBlocks.resize(MF.getNumBlockIDs());
221   NumThroughBlocks = NumGapBlocks = 0;
222   if (CurLI->empty())
223     return true;
224 
225   LiveInterval::const_iterator LVI = CurLI->begin();
226   LiveInterval::const_iterator LVE = CurLI->end();
227 
228   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
229   UseI = UseSlots.begin();
230   UseE = UseSlots.end();
231 
232   // Loop over basic blocks where CurLI is live.
233   MachineFunction::iterator MFI =
234       LIS.getMBBFromIndex(LVI->start)->getIterator();
235   while (true) {
236     BlockInfo BI;
237     BI.MBB = &*MFI;
238     SlotIndex Start, Stop;
239     std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
240 
241     // If the block contains no uses, the range must be live through. At one
242     // point, RegisterCoalescer could create dangling ranges that ended
243     // mid-block.
244     if (UseI == UseE || *UseI >= Stop) {
245       ++NumThroughBlocks;
246       ThroughBlocks.set(BI.MBB->getNumber());
247       // The range shouldn't end mid-block if there are no uses. This shouldn't
248       // happen.
249       if (LVI->end < Stop)
250         return false;
251     } else {
252       // This block has uses. Find the first and last uses in the block.
253       BI.FirstInstr = *UseI;
254       assert(BI.FirstInstr >= Start);
255       do ++UseI;
256       while (UseI != UseE && *UseI < Stop);
257       BI.LastInstr = UseI[-1];
258       assert(BI.LastInstr < Stop);
259 
260       // LVI is the first live segment overlapping MBB.
261       BI.LiveIn = LVI->start <= Start;
262 
263       // When not live in, the first use should be a def.
264       if (!BI.LiveIn) {
265         assert(LVI->start == LVI->valno->def && "Dangling Segment start");
266         assert(LVI->start == BI.FirstInstr && "First instr should be a def");
267         BI.FirstDef = BI.FirstInstr;
268       }
269 
270       // Look for gaps in the live range.
271       BI.LiveOut = true;
272       while (LVI->end < Stop) {
273         SlotIndex LastStop = LVI->end;
274         if (++LVI == LVE || LVI->start >= Stop) {
275           BI.LiveOut = false;
276           BI.LastInstr = LastStop;
277           break;
278         }
279 
280         if (LastStop < LVI->start) {
281           // There is a gap in the live range. Create duplicate entries for the
282           // live-in snippet and the live-out snippet.
283           ++NumGapBlocks;
284 
285           // Push the Live-in part.
286           BI.LiveOut = false;
287           UseBlocks.push_back(BI);
288           UseBlocks.back().LastInstr = LastStop;
289 
290           // Set up BI for the live-out part.
291           BI.LiveIn = false;
292           BI.LiveOut = true;
293           BI.FirstInstr = BI.FirstDef = LVI->start;
294         }
295 
296         // A Segment that starts in the middle of the block must be a def.
297         assert(LVI->start == LVI->valno->def && "Dangling Segment start");
298         if (!BI.FirstDef)
299           BI.FirstDef = LVI->start;
300       }
301 
302       UseBlocks.push_back(BI);
303 
304       // LVI is now at LVE or LVI->end >= Stop.
305       if (LVI == LVE)
306         break;
307     }
308 
309     // Live segment ends exactly at Stop. Move to the next segment.
310     if (LVI->end == Stop && ++LVI == LVE)
311       break;
312 
313     // Pick the next basic block.
314     if (LVI->start < Stop)
315       ++MFI;
316     else
317       MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
318   }
319 
320   assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
321   return true;
322 }
323 
324 unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
325   if (cli->empty())
326     return 0;
327   LiveInterval *li = const_cast<LiveInterval*>(cli);
328   LiveInterval::iterator LVI = li->begin();
329   LiveInterval::iterator LVE = li->end();
330   unsigned Count = 0;
331 
332   // Loop over basic blocks where li is live.
333   MachineFunction::const_iterator MFI =
334       LIS.getMBBFromIndex(LVI->start)->getIterator();
335   SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);
336   while (true) {
337     ++Count;
338     LVI = li->advanceTo(LVI, Stop);
339     if (LVI == LVE)
340       return Count;
341     do {
342       ++MFI;
343       Stop = LIS.getMBBEndIdx(&*MFI);
344     } while (Stop <= LVI->start);
345   }
346 }
347 
348 bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
349   unsigned OrigReg = VRM.getOriginal(CurLI->reg);
350   const LiveInterval &Orig = LIS.getInterval(OrigReg);
351   assert(!Orig.empty() && "Splitting empty interval?");
352   LiveInterval::const_iterator I = Orig.find(Idx);
353 
354   // Range containing Idx should begin at Idx.
355   if (I != Orig.end() && I->start <= Idx)
356     return I->start == Idx;
357 
358   // Range does not contain Idx, previous must end at Idx.
359   return I != Orig.begin() && (--I)->end == Idx;
360 }
361 
362 void SplitAnalysis::analyze(const LiveInterval *li) {
363   clear();
364   CurLI = li;
365   analyzeUses();
366 }
367 
368 //===----------------------------------------------------------------------===//
369 //                               Split Editor
370 //===----------------------------------------------------------------------===//
371 
372 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
373 SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa,
374                          LiveIntervals &lis, VirtRegMap &vrm,
375                          MachineDominatorTree &mdt,
376                          MachineBlockFrequencyInfo &mbfi)
377     : SA(sa), AA(aa), LIS(lis), VRM(vrm),
378       MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt),
379       TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
380       TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
381       MBFI(mbfi), RegAssign(Allocator) {}
382 
383 void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
384   Edit = &LRE;
385   SpillMode = SM;
386   OpenIdx = 0;
387   RegAssign.clear();
388   Values.clear();
389 
390   // Reset the LiveIntervalCalc instances needed for this spill mode.
391   LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
392                   &LIS.getVNInfoAllocator());
393   if (SpillMode)
394     LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
395                     &LIS.getVNInfoAllocator());
396 
397   // We don't need an AliasAnalysis since we will only be performing
398   // cheap-as-a-copy remats anyway.
399   Edit->anyRematerializable(nullptr);
400 }
401 
402 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
403 LLVM_DUMP_METHOD void SplitEditor::dump() const {
404   if (RegAssign.empty()) {
405     dbgs() << " empty\n";
406     return;
407   }
408 
409   for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
410     dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
411   dbgs() << '\n';
412 }
413 #endif
414 
415 LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
416                                                         LiveInterval &LI) {
417   for (LiveInterval::SubRange &S : LI.subranges())
418     if (S.LaneMask == LM)
419       return S;
420   llvm_unreachable("SubRange for this mask not found");
421 }
422 
423 void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
424   if (!LI.hasSubRanges()) {
425     LI.createDeadDef(VNI);
426     return;
427   }
428 
429   SlotIndex Def = VNI->def;
430   if (Original) {
431     // If we are transferring a def from the original interval, make sure
432     // to only update the subranges for which the original subranges had
433     // a def at this location.
434     for (LiveInterval::SubRange &S : LI.subranges()) {
435       auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
436       VNInfo *PV = PS.getVNInfoAt(Def);
437       if (PV != nullptr && PV->def == Def)
438         S.createDeadDef(Def, LIS.getVNInfoAllocator());
439     }
440   } else {
441     // This is a new def: either from rematerialization, or from an inserted
442     // copy. Since rematerialization can regenerate a definition of a sub-
443     // register, we need to check which subranges need to be updated.
444     const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);
445     assert(DefMI != nullptr);
446     LaneBitmask LM;
447     for (const MachineOperand &DefOp : DefMI->defs()) {
448       Register R = DefOp.getReg();
449       if (R != LI.reg)
450         continue;
451       if (unsigned SR = DefOp.getSubReg())
452         LM |= TRI.getSubRegIndexLaneMask(SR);
453       else {
454         LM = MRI.getMaxLaneMaskForVReg(R);
455         break;
456       }
457     }
458     for (LiveInterval::SubRange &S : LI.subranges())
459       if ((S.LaneMask & LM).any())
460         S.createDeadDef(Def, LIS.getVNInfoAllocator());
461   }
462 }
463 
464 VNInfo *SplitEditor::defValue(unsigned RegIdx,
465                               const VNInfo *ParentVNI,
466                               SlotIndex Idx,
467                               bool Original) {
468   assert(ParentVNI && "Mapping  NULL value");
469   assert(Idx.isValid() && "Invalid SlotIndex");
470   assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
471   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
472 
473   // Create a new value.
474   VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
475 
476   bool Force = LI->hasSubRanges();
477   ValueForcePair FP(Force ? nullptr : VNI, Force);
478   // Use insert for lookup, so we can add missing values with a second lookup.
479   std::pair<ValueMap::iterator, bool> InsP =
480     Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));
481 
482   // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
483   // forced. Keep it as a simple def without any liveness.
484   if (!Force && InsP.second)
485     return VNI;
486 
487   // If the previous value was a simple mapping, add liveness for it now.
488   if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
489     addDeadDef(*LI, OldVNI, Original);
490 
491     // No longer a simple mapping.  Switch to a complex mapping. If the
492     // interval has subranges, make it a forced mapping.
493     InsP.first->second = ValueForcePair(nullptr, Force);
494   }
495 
496   // This is a complex mapping, add liveness for VNI
497   addDeadDef(*LI, VNI, Original);
498   return VNI;
499 }
500 
501 void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {
502   ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];
503   VNInfo *VNI = VFP.getPointer();
504 
505   // ParentVNI was either unmapped or already complex mapped. Either way, just
506   // set the force bit.
507   if (!VNI) {
508     VFP.setInt(true);
509     return;
510   }
511 
512   // This was previously a single mapping. Make sure the old def is represented
513   // by a trivial live range.
514   addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
515 
516   // Mark as complex mapped, forced.
517   VFP = ValueForcePair(nullptr, true);
518 }
519 
520 SlotIndex SplitEditor::buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg,
521     MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
522     unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) {
523   const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
524   bool FirstCopy = !Def.isValid();
525   MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)
526       .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)
527               | getInternalReadRegState(!FirstCopy), SubIdx)
528       .addReg(FromReg, 0, SubIdx);
529 
530   BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
531   SlotIndexes &Indexes = *LIS.getSlotIndexes();
532   if (FirstCopy) {
533     Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
534   } else {
535     CopyMI->bundleWithPred();
536   }
537   LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx);
538   DestLI.refineSubRanges(Allocator, LaneMask,
539                          [Def, &Allocator](LiveInterval::SubRange &SR) {
540                            SR.createDeadDef(Def, Allocator);
541                          },
542                          Indexes, TRI);
543   return Def;
544 }
545 
546 SlotIndex SplitEditor::buildCopy(unsigned FromReg, unsigned ToReg,
547     LaneBitmask LaneMask, MachineBasicBlock &MBB,
548     MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {
549   const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
550   if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {
551     // The full vreg is copied.
552     MachineInstr *CopyMI =
553         BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg);
554     SlotIndexes &Indexes = *LIS.getSlotIndexes();
555     return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
556   }
557 
558   // Only a subset of lanes needs to be copied. The following is a simple
559   // heuristic to construct a sequence of COPYs. We could add a target
560   // specific callback if this turns out to be suboptimal.
561   LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));
562 
563   // First pass: Try to find a perfectly matching subregister index. If none
564   // exists find the one covering the most lanemask bits.
565   SmallVector<unsigned, 8> PossibleIndexes;
566   unsigned BestIdx = 0;
567   unsigned BestCover = 0;
568   const TargetRegisterClass *RC = MRI.getRegClass(FromReg);
569   assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");
570   for (unsigned Idx = 1, E = TRI.getNumSubRegIndices(); Idx < E; ++Idx) {
571     // Is this index even compatible with the given class?
572     if (TRI.getSubClassWithSubReg(RC, Idx) != RC)
573       continue;
574     LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
575     // Early exit if we found a perfect match.
576     if (SubRegMask == LaneMask) {
577       BestIdx = Idx;
578       break;
579     }
580 
581     // The index must not cover any lanes outside \p LaneMask.
582     if ((SubRegMask & ~LaneMask).any())
583       continue;
584 
585     unsigned PopCount = SubRegMask.getNumLanes();
586     PossibleIndexes.push_back(Idx);
587     if (PopCount > BestCover) {
588       BestCover = PopCount;
589       BestIdx = Idx;
590     }
591   }
592 
593   // Abort if we cannot possibly implement the COPY with the given indexes.
594   if (BestIdx == 0)
595     report_fatal_error("Impossible to implement partial COPY");
596 
597   SlotIndex Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore,
598                                         BestIdx, DestLI, Late, SlotIndex());
599 
600   // Greedy heuristic: Keep iterating keeping the best covering subreg index
601   // each time.
602   LaneBitmask LanesLeft = LaneMask & ~(TRI.getSubRegIndexLaneMask(BestIdx));
603   while (LanesLeft.any()) {
604     unsigned BestIdx = 0;
605     int BestCover = std::numeric_limits<int>::min();
606     for (unsigned Idx : PossibleIndexes) {
607       LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
608       // Early exit if we found a perfect match.
609       if (SubRegMask == LanesLeft) {
610         BestIdx = Idx;
611         break;
612       }
613 
614       // Try to cover as much of the remaining lanes as possible but
615       // as few of the already covered lanes as possible.
616       int Cover = (SubRegMask & LanesLeft).getNumLanes()
617                 - (SubRegMask & ~LanesLeft).getNumLanes();
618       if (Cover > BestCover) {
619         BestCover = Cover;
620         BestIdx = Idx;
621       }
622     }
623 
624     if (BestIdx == 0)
625       report_fatal_error("Impossible to implement partial COPY");
626 
627     buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,
628                           DestLI, Late, Def);
629     LanesLeft &= ~TRI.getSubRegIndexLaneMask(BestIdx);
630   }
631 
632   return Def;
633 }
634 
635 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
636                                    VNInfo *ParentVNI,
637                                    SlotIndex UseIdx,
638                                    MachineBasicBlock &MBB,
639                                    MachineBasicBlock::iterator I) {
640   SlotIndex Def;
641   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
642 
643   // We may be trying to avoid interference that ends at a deleted instruction,
644   // so always begin RegIdx 0 early and all others late.
645   bool Late = RegIdx != 0;
646 
647   // Attempt cheap-as-a-copy rematerialization.
648   unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
649   LiveInterval &OrigLI = LIS.getInterval(Original);
650   VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
651 
652   unsigned Reg = LI->reg;
653   bool DidRemat = false;
654   if (OrigVNI) {
655     LiveRangeEdit::Remat RM(ParentVNI);
656     RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
657     if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
658       Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);
659       ++NumRemats;
660       DidRemat = true;
661     }
662   }
663   if (!DidRemat) {
664     LaneBitmask LaneMask;
665     if (LI->hasSubRanges()) {
666       LaneMask = LaneBitmask::getNone();
667       for (LiveInterval::SubRange &S : LI->subranges())
668         LaneMask |= S.LaneMask;
669     } else {
670       LaneMask = LaneBitmask::getAll();
671     }
672 
673     ++NumCopies;
674     Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);
675   }
676 
677   // Define the value in Reg.
678   return defValue(RegIdx, ParentVNI, Def, false);
679 }
680 
681 /// Create a new virtual register and live interval.
682 unsigned SplitEditor::openIntv() {
683   // Create the complement as index 0.
684   if (Edit->empty())
685     Edit->createEmptyInterval();
686 
687   // Create the open interval.
688   OpenIdx = Edit->size();
689   Edit->createEmptyInterval();
690   return OpenIdx;
691 }
692 
693 void SplitEditor::selectIntv(unsigned Idx) {
694   assert(Idx != 0 && "Cannot select the complement interval");
695   assert(Idx < Edit->size() && "Can only select previously opened interval");
696   LLVM_DEBUG(dbgs() << "    selectIntv " << OpenIdx << " -> " << Idx << '\n');
697   OpenIdx = Idx;
698 }
699 
700 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
701   assert(OpenIdx && "openIntv not called before enterIntvBefore");
702   LLVM_DEBUG(dbgs() << "    enterIntvBefore " << Idx);
703   Idx = Idx.getBaseIndex();
704   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
705   if (!ParentVNI) {
706     LLVM_DEBUG(dbgs() << ": not live\n");
707     return Idx;
708   }
709   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
710   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
711   assert(MI && "enterIntvBefore called with invalid index");
712 
713   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
714   return VNI->def;
715 }
716 
717 SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {
718   assert(OpenIdx && "openIntv not called before enterIntvAfter");
719   LLVM_DEBUG(dbgs() << "    enterIntvAfter " << Idx);
720   Idx = Idx.getBoundaryIndex();
721   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
722   if (!ParentVNI) {
723     LLVM_DEBUG(dbgs() << ": not live\n");
724     return Idx;
725   }
726   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
727   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
728   assert(MI && "enterIntvAfter called with invalid index");
729 
730   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
731                               std::next(MachineBasicBlock::iterator(MI)));
732   return VNI->def;
733 }
734 
735 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
736   assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
737   SlotIndex End = LIS.getMBBEndIdx(&MBB);
738   SlotIndex Last = End.getPrevSlot();
739   LLVM_DEBUG(dbgs() << "    enterIntvAtEnd " << printMBBReference(MBB) << ", "
740                     << Last);
741   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
742   if (!ParentVNI) {
743     LLVM_DEBUG(dbgs() << ": not live\n");
744     return End;
745   }
746   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id);
747   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
748                               SA.getLastSplitPointIter(&MBB));
749   RegAssign.insert(VNI->def, End, OpenIdx);
750   LLVM_DEBUG(dump());
751   return VNI->def;
752 }
753 
754 /// useIntv - indicate that all instructions in MBB should use OpenLI.
755 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
756   useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
757 }
758 
759 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
760   assert(OpenIdx && "openIntv not called before useIntv");
761   LLVM_DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
762   RegAssign.insert(Start, End, OpenIdx);
763   LLVM_DEBUG(dump());
764 }
765 
766 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
767   assert(OpenIdx && "openIntv not called before leaveIntvAfter");
768   LLVM_DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
769 
770   // The interval must be live beyond the instruction at Idx.
771   SlotIndex Boundary = Idx.getBoundaryIndex();
772   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
773   if (!ParentVNI) {
774     LLVM_DEBUG(dbgs() << ": not live\n");
775     return Boundary.getNextSlot();
776   }
777   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
778   MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
779   assert(MI && "No instruction at index");
780 
781   // In spill mode, make live ranges as short as possible by inserting the copy
782   // before MI.  This is only possible if that instruction doesn't redefine the
783   // value.  The inserted COPY is not a kill, and we don't need to recompute
784   // the source live range.  The spiller also won't try to hoist this copy.
785   if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
786       MI->readsVirtualRegister(Edit->getReg())) {
787     forceRecompute(0, *ParentVNI);
788     defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
789     return Idx;
790   }
791 
792   VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
793                               std::next(MachineBasicBlock::iterator(MI)));
794   return VNI->def;
795 }
796 
797 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
798   assert(OpenIdx && "openIntv not called before leaveIntvBefore");
799   LLVM_DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
800 
801   // The interval must be live into the instruction at Idx.
802   Idx = Idx.getBaseIndex();
803   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
804   if (!ParentVNI) {
805     LLVM_DEBUG(dbgs() << ": not live\n");
806     return Idx.getNextSlot();
807   }
808   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
809 
810   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
811   assert(MI && "No instruction at index");
812   VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
813   return VNI->def;
814 }
815 
816 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
817   assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
818   SlotIndex Start = LIS.getMBBStartIdx(&MBB);
819   LLVM_DEBUG(dbgs() << "    leaveIntvAtTop " << printMBBReference(MBB) << ", "
820                     << Start);
821 
822   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
823   if (!ParentVNI) {
824     LLVM_DEBUG(dbgs() << ": not live\n");
825     return Start;
826   }
827 
828   VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
829                               MBB.SkipPHIsLabelsAndDebug(MBB.begin()));
830   RegAssign.insert(Start, VNI->def, OpenIdx);
831   LLVM_DEBUG(dump());
832   return VNI->def;
833 }
834 
835 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
836   assert(OpenIdx && "openIntv not called before overlapIntv");
837   const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
838   assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
839          "Parent changes value in extended range");
840   assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
841          "Range cannot span basic blocks");
842 
843   // The complement interval will be extended as needed by LICalc.extend().
844   if (ParentVNI)
845     forceRecompute(0, *ParentVNI);
846   LLVM_DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
847   RegAssign.insert(Start, End, OpenIdx);
848   LLVM_DEBUG(dump());
849 }
850 
851 //===----------------------------------------------------------------------===//
852 //                                  Spill modes
853 //===----------------------------------------------------------------------===//
854 
855 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
856   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
857   LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
858   RegAssignMap::iterator AssignI;
859   AssignI.setMap(RegAssign);
860 
861   for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
862     SlotIndex Def = Copies[i]->def;
863     MachineInstr *MI = LIS.getInstructionFromIndex(Def);
864     assert(MI && "No instruction for back-copy");
865 
866     MachineBasicBlock *MBB = MI->getParent();
867     MachineBasicBlock::iterator MBBI(MI);
868     bool AtBegin;
869     do AtBegin = MBBI == MBB->begin();
870     while (!AtBegin && (--MBBI)->isDebugInstr());
871 
872     LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
873     LIS.removeVRegDefAt(*LI, Def);
874     LIS.RemoveMachineInstrFromMaps(*MI);
875     MI->eraseFromParent();
876 
877     // Adjust RegAssign if a register assignment is killed at Def. We want to
878     // avoid calculating the live range of the source register if possible.
879     AssignI.find(Def.getPrevSlot());
880     if (!AssignI.valid() || AssignI.start() >= Def)
881       continue;
882     // If MI doesn't kill the assigned register, just leave it.
883     if (AssignI.stop() != Def)
884       continue;
885     unsigned RegIdx = AssignI.value();
886     if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
887       LLVM_DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx
888                         << '\n');
889       forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));
890     } else {
891       SlotIndex Kill = LIS.getInstructionIndex(*MBBI).getRegSlot();
892       LLVM_DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
893       AssignI.setStop(Kill);
894     }
895   }
896 }
897 
898 MachineBasicBlock*
899 SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
900                                   MachineBasicBlock *DefMBB) {
901   if (MBB == DefMBB)
902     return MBB;
903   assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
904 
905   const MachineLoopInfo &Loops = SA.Loops;
906   const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
907   MachineDomTreeNode *DefDomNode = MDT[DefMBB];
908 
909   // Best candidate so far.
910   MachineBasicBlock *BestMBB = MBB;
911   unsigned BestDepth = std::numeric_limits<unsigned>::max();
912 
913   while (true) {
914     const MachineLoop *Loop = Loops.getLoopFor(MBB);
915 
916     // MBB isn't in a loop, it doesn't get any better.  All dominators have a
917     // higher frequency by definition.
918     if (!Loop) {
919       LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
920                         << " dominates " << printMBBReference(*MBB)
921                         << " at depth 0\n");
922       return MBB;
923     }
924 
925     // We'll never be able to exit the DefLoop.
926     if (Loop == DefLoop) {
927       LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
928                         << " dominates " << printMBBReference(*MBB)
929                         << " in the same loop\n");
930       return MBB;
931     }
932 
933     // Least busy dominator seen so far.
934     unsigned Depth = Loop->getLoopDepth();
935     if (Depth < BestDepth) {
936       BestMBB = MBB;
937       BestDepth = Depth;
938       LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
939                         << " dominates " << printMBBReference(*MBB)
940                         << " at depth " << Depth << '\n');
941     }
942 
943     // Leave loop by going to the immediate dominator of the loop header.
944     // This is a bigger stride than simply walking up the dominator tree.
945     MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
946 
947     // Too far up the dominator tree?
948     if (!IDom || !MDT.dominates(DefDomNode, IDom))
949       return BestMBB;
950 
951     MBB = IDom->getBlock();
952   }
953 }
954 
955 void SplitEditor::computeRedundantBackCopies(
956     DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
957   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
958   LiveInterval *Parent = &Edit->getParent();
959   SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
960   SmallPtrSet<VNInfo *, 8> DominatedVNIs;
961 
962   // Aggregate VNIs having the same value as ParentVNI.
963   for (VNInfo *VNI : LI->valnos) {
964     if (VNI->isUnused())
965       continue;
966     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
967     EqualVNs[ParentVNI->id].insert(VNI);
968   }
969 
970   // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
971   // redundant VNIs to BackCopies.
972   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
973     VNInfo *ParentVNI = Parent->getValNumInfo(i);
974     if (!NotToHoistSet.count(ParentVNI->id))
975       continue;
976     SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
977     SmallPtrSetIterator<VNInfo *> It2 = It1;
978     for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
979       It2 = It1;
980       for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
981         if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
982           continue;
983 
984         MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
985         MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
986         if (MBB1 == MBB2) {
987           DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
988         } else if (MDT.dominates(MBB1, MBB2)) {
989           DominatedVNIs.insert(*It2);
990         } else if (MDT.dominates(MBB2, MBB1)) {
991           DominatedVNIs.insert(*It1);
992         }
993       }
994     }
995     if (!DominatedVNIs.empty()) {
996       forceRecompute(0, *ParentVNI);
997       for (auto VNI : DominatedVNIs) {
998         BackCopies.push_back(VNI);
999       }
1000       DominatedVNIs.clear();
1001     }
1002   }
1003 }
1004 
1005 /// For SM_Size mode, find a common dominator for all the back-copies for
1006 /// the same ParentVNI and hoist the backcopies to the dominator BB.
1007 /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
1008 /// to do the hoisting, simply remove the dominated backcopies for the same
1009 /// ParentVNI.
1010 void SplitEditor::hoistCopies() {
1011   // Get the complement interval, always RegIdx 0.
1012   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
1013   LiveInterval *Parent = &Edit->getParent();
1014 
1015   // Track the nearest common dominator for all back-copies for each ParentVNI,
1016   // indexed by ParentVNI->id.
1017   using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1018   SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
1019   // The total cost of all the back-copies for each ParentVNI.
1020   SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums());
1021   // The ParentVNI->id set for which hoisting back-copies are not beneficial
1022   // for Speed.
1023   DenseSet<unsigned> NotToHoistSet;
1024 
1025   // Find the nearest common dominator for parent values with multiple
1026   // back-copies.  If a single back-copy dominates, put it in DomPair.second.
1027   for (VNInfo *VNI : LI->valnos) {
1028     if (VNI->isUnused())
1029       continue;
1030     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1031     assert(ParentVNI && "Parent not live at complement def");
1032 
1033     // Don't hoist remats.  The complement is probably going to disappear
1034     // completely anyway.
1035     if (Edit->didRematerialize(ParentVNI))
1036       continue;
1037 
1038     MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
1039 
1040     DomPair &Dom = NearestDom[ParentVNI->id];
1041 
1042     // Keep directly defined parent values.  This is either a PHI or an
1043     // instruction in the complement range.  All other copies of ParentVNI
1044     // should be eliminated.
1045     if (VNI->def == ParentVNI->def) {
1046       LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
1047       Dom = DomPair(ValMBB, VNI->def);
1048       continue;
1049     }
1050     // Skip the singly mapped values.  There is nothing to gain from hoisting a
1051     // single back-copy.
1052     if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
1053       LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
1054       continue;
1055     }
1056 
1057     if (!Dom.first) {
1058       // First time we see ParentVNI.  VNI dominates itself.
1059       Dom = DomPair(ValMBB, VNI->def);
1060     } else if (Dom.first == ValMBB) {
1061       // Two defs in the same block.  Pick the earlier def.
1062       if (!Dom.second.isValid() || VNI->def < Dom.second)
1063         Dom.second = VNI->def;
1064     } else {
1065       // Different basic blocks. Check if one dominates.
1066       MachineBasicBlock *Near =
1067         MDT.findNearestCommonDominator(Dom.first, ValMBB);
1068       if (Near == ValMBB)
1069         // Def ValMBB dominates.
1070         Dom = DomPair(ValMBB, VNI->def);
1071       else if (Near != Dom.first)
1072         // None dominate. Hoist to common dominator, need new def.
1073         Dom = DomPair(Near, SlotIndex());
1074       Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
1075     }
1076 
1077     LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'
1078                       << VNI->def << " for parent " << ParentVNI->id << '@'
1079                       << ParentVNI->def << " hoist to "
1080                       << printMBBReference(*Dom.first) << ' ' << Dom.second
1081                       << '\n');
1082   }
1083 
1084   // Insert the hoisted copies.
1085   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
1086     DomPair &Dom = NearestDom[i];
1087     if (!Dom.first || Dom.second.isValid())
1088       continue;
1089     // This value needs a hoisted copy inserted at the end of Dom.first.
1090     VNInfo *ParentVNI = Parent->getValNumInfo(i);
1091     MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
1092     // Get a less loopy dominator than Dom.first.
1093     Dom.first = findShallowDominator(Dom.first, DefMBB);
1094     if (SpillMode == SM_Speed &&
1095         MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
1096       NotToHoistSet.insert(ParentVNI->id);
1097       continue;
1098     }
1099     SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
1100     Dom.second =
1101       defFromParent(0, ParentVNI, Last, *Dom.first,
1102                     SA.getLastSplitPointIter(Dom.first))->def;
1103   }
1104 
1105   // Remove redundant back-copies that are now known to be dominated by another
1106   // def with the same value.
1107   SmallVector<VNInfo*, 8> BackCopies;
1108   for (VNInfo *VNI : LI->valnos) {
1109     if (VNI->isUnused())
1110       continue;
1111     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1112     const DomPair &Dom = NearestDom[ParentVNI->id];
1113     if (!Dom.first || Dom.second == VNI->def ||
1114         NotToHoistSet.count(ParentVNI->id))
1115       continue;
1116     BackCopies.push_back(VNI);
1117     forceRecompute(0, *ParentVNI);
1118   }
1119 
1120   // If it is not beneficial to hoist all the BackCopies, simply remove
1121   // redundant BackCopies in speed mode.
1122   if (SpillMode == SM_Speed && !NotToHoistSet.empty())
1123     computeRedundantBackCopies(NotToHoistSet, BackCopies);
1124 
1125   removeBackCopies(BackCopies);
1126 }
1127 
1128 /// transferValues - Transfer all possible values to the new live ranges.
1129 /// Values that were rematerialized are left alone, they need LICalc.extend().
1130 bool SplitEditor::transferValues() {
1131   bool Skipped = false;
1132   RegAssignMap::const_iterator AssignI = RegAssign.begin();
1133   for (const LiveRange::Segment &S : Edit->getParent()) {
1134     LLVM_DEBUG(dbgs() << "  blit " << S << ':');
1135     VNInfo *ParentVNI = S.valno;
1136     // RegAssign has holes where RegIdx 0 should be used.
1137     SlotIndex Start = S.start;
1138     AssignI.advanceTo(Start);
1139     do {
1140       unsigned RegIdx;
1141       SlotIndex End = S.end;
1142       if (!AssignI.valid()) {
1143         RegIdx = 0;
1144       } else if (AssignI.start() <= Start) {
1145         RegIdx = AssignI.value();
1146         if (AssignI.stop() < End) {
1147           End = AssignI.stop();
1148           ++AssignI;
1149         }
1150       } else {
1151         RegIdx = 0;
1152         End = std::min(End, AssignI.start());
1153       }
1154 
1155       // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1156       LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('
1157                         << printReg(Edit->get(RegIdx)) << ')');
1158       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1159 
1160       // Check for a simply defined value that can be blitted directly.
1161       ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
1162       if (VNInfo *VNI = VFP.getPointer()) {
1163         LLVM_DEBUG(dbgs() << ':' << VNI->id);
1164         LI.addSegment(LiveInterval::Segment(Start, End, VNI));
1165         Start = End;
1166         continue;
1167       }
1168 
1169       // Skip values with forced recomputation.
1170       if (VFP.getInt()) {
1171         LLVM_DEBUG(dbgs() << "(recalc)");
1172         Skipped = true;
1173         Start = End;
1174         continue;
1175       }
1176 
1177       LiveIntervalCalc &LIC = getLICalc(RegIdx);
1178 
1179       // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1180       // so the live range is accurate. Add live-in blocks in [Start;End) to the
1181       // LiveInBlocks.
1182       MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
1183       SlotIndex BlockStart, BlockEnd;
1184       std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
1185 
1186       // The first block may be live-in, or it may have its own def.
1187       if (Start != BlockStart) {
1188         VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1189         assert(VNI && "Missing def for complex mapped value");
1190         LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB));
1191         // MBB has its own def. Is it also live-out?
1192         if (BlockEnd <= End)
1193           LIC.setLiveOutValue(&*MBB, VNI);
1194 
1195         // Skip to the next block for live-in.
1196         ++MBB;
1197         BlockStart = BlockEnd;
1198       }
1199 
1200       // Handle the live-in blocks covered by [Start;End).
1201       assert(Start <= BlockStart && "Expected live-in block");
1202       while (BlockStart < End) {
1203         LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB));
1204         BlockEnd = LIS.getMBBEndIdx(&*MBB);
1205         if (BlockStart == ParentVNI->def) {
1206           // This block has the def of a parent PHI, so it isn't live-in.
1207           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
1208           VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1209           assert(VNI && "Missing def for complex mapped parent PHI");
1210           if (End >= BlockEnd)
1211             LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
1212         } else {
1213           // This block needs a live-in value.  The last block covered may not
1214           // be live-out.
1215           if (End < BlockEnd)
1216             LIC.addLiveInBlock(LI, MDT[&*MBB], End);
1217           else {
1218             // Live-through, and we don't know the value.
1219             LIC.addLiveInBlock(LI, MDT[&*MBB]);
1220             LIC.setLiveOutValue(&*MBB, nullptr);
1221           }
1222         }
1223         BlockStart = BlockEnd;
1224         ++MBB;
1225       }
1226       Start = End;
1227     } while (Start != S.end);
1228     LLVM_DEBUG(dbgs() << '\n');
1229   }
1230 
1231   LICalc[0].calculateValues();
1232   if (SpillMode)
1233     LICalc[1].calculateValues();
1234 
1235   return Skipped;
1236 }
1237 
1238 static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) {
1239   const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
1240   if (Seg == nullptr)
1241     return true;
1242   if (Seg->end != Def.getDeadSlot())
1243     return false;
1244   // This is a dead PHI. Remove it.
1245   LR.removeSegment(*Seg, true);
1246   return true;
1247 }
1248 
1249 void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
1250                                  LiveRange &LR, LaneBitmask LM,
1251                                  ArrayRef<SlotIndex> Undefs) {
1252   for (MachineBasicBlock *P : B.predecessors()) {
1253     SlotIndex End = LIS.getMBBEndIdx(P);
1254     SlotIndex LastUse = End.getPrevSlot();
1255     // The predecessor may not have a live-out value. That is OK, like an
1256     // undef PHI operand.
1257     LiveInterval &PLI = Edit->getParent();
1258     // Need the cast because the inputs to ?: would otherwise be deemed
1259     // "incompatible": SubRange vs LiveInterval.
1260     LiveRange &PSR = !LM.all() ? getSubRangeForMask(LM, PLI)
1261                                : static_cast<LiveRange&>(PLI);
1262     if (PSR.liveAt(LastUse))
1263       LIC.extend(LR, End, /*PhysReg=*/0, Undefs);
1264   }
1265 }
1266 
1267 void SplitEditor::extendPHIKillRanges() {
1268   // Extend live ranges to be live-out for successor PHI values.
1269 
1270   // Visit each PHI def slot in the parent live interval. If the def is dead,
1271   // remove it. Otherwise, extend the live interval to reach the end indexes
1272   // of all predecessor blocks.
1273 
1274   LiveInterval &ParentLI = Edit->getParent();
1275   for (const VNInfo *V : ParentLI.valnos) {
1276     if (V->isUnused() || !V->isPHIDef())
1277       continue;
1278 
1279     unsigned RegIdx = RegAssign.lookup(V->def);
1280     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1281     LiveIntervalCalc &LIC = getLICalc(RegIdx);
1282     MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1283     if (!removeDeadSegment(V->def, LI))
1284       extendPHIRange(B, LIC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
1285   }
1286 
1287   SmallVector<SlotIndex, 4> Undefs;
1288   LiveIntervalCalc SubLIC;
1289 
1290   for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
1291     for (const VNInfo *V : PS.valnos) {
1292       if (V->isUnused() || !V->isPHIDef())
1293         continue;
1294       unsigned RegIdx = RegAssign.lookup(V->def);
1295       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1296       LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI);
1297       if (removeDeadSegment(V->def, S))
1298         continue;
1299 
1300       MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1301       SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1302                    &LIS.getVNInfoAllocator());
1303       Undefs.clear();
1304       LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
1305       extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs);
1306     }
1307   }
1308 }
1309 
1310 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1311 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
1312   struct ExtPoint {
1313     ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
1314       : MO(O), RegIdx(R), Next(N) {}
1315 
1316     MachineOperand MO;
1317     unsigned RegIdx;
1318     SlotIndex Next;
1319   };
1320 
1321   SmallVector<ExtPoint,4> ExtPoints;
1322 
1323   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
1324        RE = MRI.reg_end(); RI != RE;) {
1325     MachineOperand &MO = *RI;
1326     MachineInstr *MI = MO.getParent();
1327     ++RI;
1328     // LiveDebugVariables should have handled all DBG_VALUE instructions.
1329     if (MI->isDebugValue()) {
1330       LLVM_DEBUG(dbgs() << "Zapping " << *MI);
1331       MO.setReg(0);
1332       continue;
1333     }
1334 
1335     // <undef> operands don't really read the register, so it doesn't matter
1336     // which register we choose.  When the use operand is tied to a def, we must
1337     // use the same register as the def, so just do that always.
1338     SlotIndex Idx = LIS.getInstructionIndex(*MI);
1339     if (MO.isDef() || MO.isUndef())
1340       Idx = Idx.getRegSlot(MO.isEarlyClobber());
1341 
1342     // Rewrite to the mapped register at Idx.
1343     unsigned RegIdx = RegAssign.lookup(Idx);
1344     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1345     MO.setReg(LI.reg);
1346     LLVM_DEBUG(dbgs() << "  rewr " << printMBBReference(*MI->getParent())
1347                       << '\t' << Idx << ':' << RegIdx << '\t' << *MI);
1348 
1349     // Extend liveness to Idx if the instruction reads reg.
1350     if (!ExtendRanges || MO.isUndef())
1351       continue;
1352 
1353     // Skip instructions that don't read Reg.
1354     if (MO.isDef()) {
1355       if (!MO.getSubReg() && !MO.isEarlyClobber())
1356         continue;
1357       // We may want to extend a live range for a partial redef, or for a use
1358       // tied to an early clobber.
1359       Idx = Idx.getPrevSlot();
1360       if (!Edit->getParent().liveAt(Idx))
1361         continue;
1362     } else
1363       Idx = Idx.getRegSlot(true);
1364 
1365     SlotIndex Next = Idx.getNextSlot();
1366     if (LI.hasSubRanges()) {
1367       // We have to delay extending subranges until we have seen all operands
1368       // defining the register. This is because a <def,read-undef> operand
1369       // will create an "undef" point, and we cannot extend any subranges
1370       // until all of them have been accounted for.
1371       if (MO.isUse())
1372         ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1373     } else {
1374       LiveIntervalCalc &LIC = getLICalc(RegIdx);
1375       LIC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
1376     }
1377   }
1378 
1379   for (ExtPoint &EP : ExtPoints) {
1380     LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
1381     assert(LI.hasSubRanges());
1382 
1383     LiveIntervalCalc SubLIC;
1384     Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1385     LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
1386                               : MRI.getMaxLaneMaskForVReg(Reg);
1387     for (LiveInterval::SubRange &S : LI.subranges()) {
1388       if ((S.LaneMask & LM).none())
1389         continue;
1390       // The problem here can be that the new register may have been created
1391       // for a partially defined original register. For example:
1392       //   %0:subreg_hireg<def,read-undef> = ...
1393       //   ...
1394       //   %1 = COPY %0
1395       if (S.empty())
1396         continue;
1397       SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1398                    &LIS.getVNInfoAllocator());
1399       SmallVector<SlotIndex, 4> Undefs;
1400       LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
1401       SubLIC.extend(S, EP.Next, 0, Undefs);
1402     }
1403   }
1404 
1405   for (unsigned R : *Edit) {
1406     LiveInterval &LI = LIS.getInterval(R);
1407     if (!LI.hasSubRanges())
1408       continue;
1409     LI.clear();
1410     LI.removeEmptySubRanges();
1411     LIS.constructMainRangeFromSubranges(LI);
1412   }
1413 }
1414 
1415 void SplitEditor::deleteRematVictims() {
1416   SmallVector<MachineInstr*, 8> Dead;
1417   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
1418     LiveInterval *LI = &LIS.getInterval(*I);
1419     for (const LiveRange::Segment &S : LI->segments) {
1420       // Dead defs end at the dead slot.
1421       if (S.end != S.valno->def.getDeadSlot())
1422         continue;
1423       if (S.valno->isPHIDef())
1424         continue;
1425       MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1426       assert(MI && "Missing instruction for dead def");
1427       MI->addRegisterDead(LI->reg, &TRI);
1428 
1429       if (!MI->allDefsAreDead())
1430         continue;
1431 
1432       LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
1433       Dead.push_back(MI);
1434     }
1435   }
1436 
1437   if (Dead.empty())
1438     return;
1439 
1440   Edit->eliminateDeadDefs(Dead, None, &AA);
1441 }
1442 
1443 void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {
1444   // Fast-path for common case.
1445   if (!ParentVNI.isPHIDef()) {
1446     for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1447       forceRecompute(I, ParentVNI);
1448     return;
1449   }
1450 
1451   // Trace value through phis.
1452   SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist.
1453   SmallVector<const VNInfo *, 4> WorkList;
1454   Visited.insert(&ParentVNI);
1455   WorkList.push_back(&ParentVNI);
1456 
1457   const LiveInterval &ParentLI = Edit->getParent();
1458   const SlotIndexes &Indexes = *LIS.getSlotIndexes();
1459   do {
1460     const VNInfo &VNI = *WorkList.back();
1461     WorkList.pop_back();
1462     for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1463       forceRecompute(I, VNI);
1464     if (!VNI.isPHIDef())
1465       continue;
1466 
1467     MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);
1468     for (const MachineBasicBlock *Pred : MBB.predecessors()) {
1469       SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
1470       VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);
1471       assert(PredVNI && "Value available in PhiVNI predecessor");
1472       if (Visited.insert(PredVNI).second)
1473         WorkList.push_back(PredVNI);
1474     }
1475   } while(!WorkList.empty());
1476 }
1477 
1478 void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
1479   ++NumFinished;
1480 
1481   // At this point, the live intervals in Edit contain VNInfos corresponding to
1482   // the inserted copies.
1483 
1484   // Add the original defs from the parent interval.
1485   for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1486     if (ParentVNI->isUnused())
1487       continue;
1488     unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1489     defValue(RegIdx, ParentVNI, ParentVNI->def, true);
1490 
1491     // Force rematted values to be recomputed everywhere.
1492     // The new live ranges may be truncated.
1493     if (Edit->didRematerialize(ParentVNI))
1494       forceRecomputeVNI(*ParentVNI);
1495   }
1496 
1497   // Hoist back-copies to the complement interval when in spill mode.
1498   switch (SpillMode) {
1499   case SM_Partition:
1500     // Leave all back-copies as is.
1501     break;
1502   case SM_Size:
1503   case SM_Speed:
1504     // hoistCopies will behave differently between size and speed.
1505     hoistCopies();
1506   }
1507 
1508   // Transfer the simply mapped values, check if any are skipped.
1509   bool Skipped = transferValues();
1510 
1511   // Rewrite virtual registers, possibly extending ranges.
1512   rewriteAssigned(Skipped);
1513 
1514   if (Skipped)
1515     extendPHIKillRanges();
1516   else
1517     ++NumSimple;
1518 
1519   // Delete defs that were rematted everywhere.
1520   if (Skipped)
1521     deleteRematVictims();
1522 
1523   // Get rid of unused values and set phi-kill flags.
1524   for (unsigned Reg : *Edit) {
1525     LiveInterval &LI = LIS.getInterval(Reg);
1526     LI.removeEmptySubRanges();
1527     LI.RenumberValues();
1528   }
1529 
1530   // Provide a reverse mapping from original indices to Edit ranges.
1531   if (LRMap) {
1532     LRMap->clear();
1533     for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1534       LRMap->push_back(i);
1535   }
1536 
1537   // Now check if any registers were separated into multiple components.
1538   ConnectedVNInfoEqClasses ConEQ(LIS);
1539   for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1540     // Don't use iterators, they are invalidated by create() below.
1541     unsigned VReg = Edit->get(i);
1542     LiveInterval &LI = LIS.getInterval(VReg);
1543     SmallVector<LiveInterval*, 8> SplitLIs;
1544     LIS.splitSeparateComponents(LI, SplitLIs);
1545     unsigned Original = VRM.getOriginal(VReg);
1546     for (LiveInterval *SplitLI : SplitLIs)
1547       VRM.setIsSplitFromReg(SplitLI->reg, Original);
1548 
1549     // The new intervals all map back to i.
1550     if (LRMap)
1551       LRMap->resize(Edit->size(), i);
1552   }
1553 
1554   // Calculate spill weight and allocation hints for new intervals.
1555   Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI);
1556 
1557   assert(!LRMap || LRMap->size() == Edit->size());
1558 }
1559 
1560 //===----------------------------------------------------------------------===//
1561 //                            Single Block Splitting
1562 //===----------------------------------------------------------------------===//
1563 
1564 bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,
1565                                            bool SingleInstrs) const {
1566   // Always split for multiple instructions.
1567   if (!BI.isOneInstr())
1568     return true;
1569   // Don't split for single instructions unless explicitly requested.
1570   if (!SingleInstrs)
1571     return false;
1572   // Splitting a live-through range always makes progress.
1573   if (BI.LiveIn && BI.LiveOut)
1574     return true;
1575   // No point in isolating a copy. It has no register class constraints.
1576   if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
1577     return false;
1578   // Finally, don't isolate an end point that was created by earlier splits.
1579   return isOriginalEndpoint(BI.FirstInstr);
1580 }
1581 
1582 void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) {
1583   openIntv();
1584   SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
1585   SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
1586     LastSplitPoint));
1587   if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1588     useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1589   } else {
1590       // The last use is after the last valid split point.
1591     SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1592     useIntv(SegStart, SegStop);
1593     overlapIntv(SegStop, BI.LastInstr);
1594   }
1595 }
1596 
1597 //===----------------------------------------------------------------------===//
1598 //                    Global Live Range Splitting Support
1599 //===----------------------------------------------------------------------===//
1600 
1601 // These methods support a method of global live range splitting that uses a
1602 // global algorithm to decide intervals for CFG edges. They will insert split
1603 // points and color intervals in basic blocks while avoiding interference.
1604 //
1605 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1606 // are on the stack.
1607 
1608 void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
1609                                         unsigned IntvIn, SlotIndex LeaveBefore,
1610                                         unsigned IntvOut, SlotIndex EnterAfter){
1611   SlotIndex Start, Stop;
1612   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1613 
1614   LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop
1615                     << ") intf " << LeaveBefore << '-' << EnterAfter
1616                     << ", live-through " << IntvIn << " -> " << IntvOut);
1617 
1618   assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1619 
1620   assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1621   assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1622   assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1623 
1624   MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
1625 
1626   if (!IntvOut) {
1627     LLVM_DEBUG(dbgs() << ", spill on entry.\n");
1628     //
1629     //        <<<<<<<<<    Possible LeaveBefore interference.
1630     //    |-----------|    Live through.
1631     //    -____________    Spill on entry.
1632     //
1633     selectIntv(IntvIn);
1634     SlotIndex Idx = leaveIntvAtTop(*MBB);
1635     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1636     (void)Idx;
1637     return;
1638   }
1639 
1640   if (!IntvIn) {
1641     LLVM_DEBUG(dbgs() << ", reload on exit.\n");
1642     //
1643     //    >>>>>>>          Possible EnterAfter interference.
1644     //    |-----------|    Live through.
1645     //    ___________--    Reload on exit.
1646     //
1647     selectIntv(IntvOut);
1648     SlotIndex Idx = enterIntvAtEnd(*MBB);
1649     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1650     (void)Idx;
1651     return;
1652   }
1653 
1654   if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1655     LLVM_DEBUG(dbgs() << ", straight through.\n");
1656     //
1657     //    |-----------|    Live through.
1658     //    -------------    Straight through, same intv, no interference.
1659     //
1660     selectIntv(IntvOut);
1661     useIntv(Start, Stop);
1662     return;
1663   }
1664 
1665   // We cannot legally insert splits after LSP.
1666   SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1667   assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1668 
1669   if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1670                   LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1671     LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");
1672     //
1673     //    >>>>     <<<<    Non-overlapping EnterAfter/LeaveBefore interference.
1674     //    |-----------|    Live through.
1675     //    ------=======    Switch intervals between interference.
1676     //
1677     selectIntv(IntvOut);
1678     SlotIndex Idx;
1679     if (LeaveBefore && LeaveBefore < LSP) {
1680       Idx = enterIntvBefore(LeaveBefore);
1681       useIntv(Idx, Stop);
1682     } else {
1683       Idx = enterIntvAtEnd(*MBB);
1684     }
1685     selectIntv(IntvIn);
1686     useIntv(Start, Idx);
1687     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1688     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1689     return;
1690   }
1691 
1692   LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");
1693   //
1694   //    >>><><><><<<<    Overlapping EnterAfter/LeaveBefore interference.
1695   //    |-----------|    Live through.
1696   //    ==---------==    Switch intervals before/after interference.
1697   //
1698   assert(LeaveBefore <= EnterAfter && "Missed case");
1699 
1700   selectIntv(IntvOut);
1701   SlotIndex Idx = enterIntvAfter(EnterAfter);
1702   useIntv(Idx, Stop);
1703   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1704 
1705   selectIntv(IntvIn);
1706   Idx = leaveIntvBefore(LeaveBefore);
1707   useIntv(Start, Idx);
1708   assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1709 }
1710 
1711 void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
1712                                   unsigned IntvIn, SlotIndex LeaveBefore) {
1713   SlotIndex Start, Stop;
1714   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1715 
1716   LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1717                     << Stop << "), uses " << BI.FirstInstr << '-'
1718                     << BI.LastInstr << ", reg-in " << IntvIn
1719                     << ", leave before " << LeaveBefore
1720                     << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1721 
1722   assert(IntvIn && "Must have register in");
1723   assert(BI.LiveIn && "Must be live-in");
1724   assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1725 
1726   if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1727     LLVM_DEBUG(dbgs() << " before interference.\n");
1728     //
1729     //               <<<    Interference after kill.
1730     //     |---o---x   |    Killed in block.
1731     //     =========        Use IntvIn everywhere.
1732     //
1733     selectIntv(IntvIn);
1734     useIntv(Start, BI.LastInstr);
1735     return;
1736   }
1737 
1738   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1739 
1740   if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1741     //
1742     //               <<<    Possible interference after last use.
1743     //     |---o---o---|    Live-out on stack.
1744     //     =========____    Leave IntvIn after last use.
1745     //
1746     //                 <    Interference after last use.
1747     //     |---o---o--o|    Live-out on stack, late last use.
1748     //     ============     Copy to stack after LSP, overlap IntvIn.
1749     //            \_____    Stack interval is live-out.
1750     //
1751     if (BI.LastInstr < LSP) {
1752       LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");
1753       selectIntv(IntvIn);
1754       SlotIndex Idx = leaveIntvAfter(BI.LastInstr);
1755       useIntv(Start, Idx);
1756       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1757     } else {
1758       LLVM_DEBUG(dbgs() << ", spill before last split point.\n");
1759       selectIntv(IntvIn);
1760       SlotIndex Idx = leaveIntvBefore(LSP);
1761       overlapIntv(Idx, BI.LastInstr);
1762       useIntv(Start, Idx);
1763       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1764     }
1765     return;
1766   }
1767 
1768   // The interference is overlapping somewhere we wanted to use IntvIn. That
1769   // means we need to create a local interval that can be allocated a
1770   // different register.
1771   unsigned LocalIntv = openIntv();
1772   (void)LocalIntv;
1773   LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1774 
1775   if (!BI.LiveOut || BI.LastInstr < LSP) {
1776     //
1777     //           <<<<<<<    Interference overlapping uses.
1778     //     |---o---o---|    Live-out on stack.
1779     //     =====----____    Leave IntvIn before interference, then spill.
1780     //
1781     SlotIndex To = leaveIntvAfter(BI.LastInstr);
1782     SlotIndex From = enterIntvBefore(LeaveBefore);
1783     useIntv(From, To);
1784     selectIntv(IntvIn);
1785     useIntv(Start, From);
1786     assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1787     return;
1788   }
1789 
1790   //           <<<<<<<    Interference overlapping uses.
1791   //     |---o---o--o|    Live-out on stack, late last use.
1792   //     =====-------     Copy to stack before LSP, overlap LocalIntv.
1793   //            \_____    Stack interval is live-out.
1794   //
1795   SlotIndex To = leaveIntvBefore(LSP);
1796   overlapIntv(To, BI.LastInstr);
1797   SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1798   useIntv(From, To);
1799   selectIntv(IntvIn);
1800   useIntv(Start, From);
1801   assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1802 }
1803 
1804 void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
1805                                    unsigned IntvOut, SlotIndex EnterAfter) {
1806   SlotIndex Start, Stop;
1807   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1808 
1809   LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1810                     << Stop << "), uses " << BI.FirstInstr << '-'
1811                     << BI.LastInstr << ", reg-out " << IntvOut
1812                     << ", enter after " << EnterAfter
1813                     << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1814 
1815   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1816 
1817   assert(IntvOut && "Must have register out");
1818   assert(BI.LiveOut && "Must be live-out");
1819   assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1820 
1821   if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1822     LLVM_DEBUG(dbgs() << " after interference.\n");
1823     //
1824     //    >>>>             Interference before def.
1825     //    |   o---o---|    Defined in block.
1826     //        =========    Use IntvOut everywhere.
1827     //
1828     selectIntv(IntvOut);
1829     useIntv(BI.FirstInstr, Stop);
1830     return;
1831   }
1832 
1833   if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1834     LLVM_DEBUG(dbgs() << ", reload after interference.\n");
1835     //
1836     //    >>>>             Interference before def.
1837     //    |---o---o---|    Live-through, stack-in.
1838     //    ____=========    Enter IntvOut before first use.
1839     //
1840     selectIntv(IntvOut);
1841     SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1842     useIntv(Idx, Stop);
1843     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1844     return;
1845   }
1846 
1847   // The interference is overlapping somewhere we wanted to use IntvOut. That
1848   // means we need to create a local interval that can be allocated a
1849   // different register.
1850   LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");
1851   //
1852   //    >>>>>>>          Interference overlapping uses.
1853   //    |---o---o---|    Live-through, stack-in.
1854   //    ____---======    Create local interval for interference range.
1855   //
1856   selectIntv(IntvOut);
1857   SlotIndex Idx = enterIntvAfter(EnterAfter);
1858   useIntv(Idx, Stop);
1859   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1860 
1861   openIntv();
1862   SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
1863   useIntv(From, Idx);
1864 }
1865