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