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