LLVM  6.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 BB#" << MBB.getNumber() << ", " << Last);
733  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
734  if (!ParentVNI) {
735  DEBUG(dbgs() << ": not live\n");
736  return End;
737  }
738  DEBUG(dbgs() << ": valno " << ParentVNI->id);
739  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
740  SA.getLastSplitPointIter(&MBB));
741  RegAssign.insert(VNI->def, End, OpenIdx);
742  DEBUG(dump());
743  return VNI->def;
744 }
745 
746 /// useIntv - indicate that all instructions in MBB should use OpenLI.
748  useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
749 }
750 
752  assert(OpenIdx && "openIntv not called before useIntv");
753  DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
754  RegAssign.insert(Start, End, OpenIdx);
755  DEBUG(dump());
756 }
757 
759  assert(OpenIdx && "openIntv not called before leaveIntvAfter");
760  DEBUG(dbgs() << " leaveIntvAfter " << Idx);
761 
762  // The interval must be live beyond the instruction at Idx.
763  SlotIndex Boundary = Idx.getBoundaryIndex();
764  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
765  if (!ParentVNI) {
766  DEBUG(dbgs() << ": not live\n");
767  return Boundary.getNextSlot();
768  }
769  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
770  MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
771  assert(MI && "No instruction at index");
772 
773  // In spill mode, make live ranges as short as possible by inserting the copy
774  // before MI. This is only possible if that instruction doesn't redefine the
775  // value. The inserted COPY is not a kill, and we don't need to recompute
776  // the source live range. The spiller also won't try to hoist this copy.
777  if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
778  MI->readsVirtualRegister(Edit->getReg())) {
779  forceRecompute(0, ParentVNI);
780  defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
781  return Idx;
782  }
783 
784  VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
785  std::next(MachineBasicBlock::iterator(MI)));
786  return VNI->def;
787 }
788 
790  assert(OpenIdx && "openIntv not called before leaveIntvBefore");
791  DEBUG(dbgs() << " leaveIntvBefore " << Idx);
792 
793  // The interval must be live into the instruction at Idx.
794  Idx = Idx.getBaseIndex();
795  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
796  if (!ParentVNI) {
797  DEBUG(dbgs() << ": not live\n");
798  return Idx.getNextSlot();
799  }
800  DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
801 
803  assert(MI && "No instruction at index");
804  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
805  return VNI->def;
806 }
807 
809  assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
810  SlotIndex Start = LIS.getMBBStartIdx(&MBB);
811  DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
812 
813  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
814  if (!ParentVNI) {
815  DEBUG(dbgs() << ": not live\n");
816  return Start;
817  }
818 
819  VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
820  MBB.SkipPHIsLabelsAndDebug(MBB.begin()));
821  RegAssign.insert(Start, VNI->def, OpenIdx);
822  DEBUG(dump());
823  return VNI->def;
824 }
825 
827  assert(OpenIdx && "openIntv not called before overlapIntv");
828  const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
829  assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
830  "Parent changes value in extended range");
831  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
832  "Range cannot span basic blocks");
833 
834  // The complement interval will be extended as needed by LRCalc.extend().
835  if (ParentVNI)
836  forceRecompute(0, ParentVNI);
837  DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
838  RegAssign.insert(Start, End, OpenIdx);
839  DEBUG(dump());
840 }
841 
842 //===----------------------------------------------------------------------===//
843 // Spill modes
844 //===----------------------------------------------------------------------===//
845 
846 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
847  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
848  DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
849  RegAssignMap::iterator AssignI;
850  AssignI.setMap(RegAssign);
851 
852  for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
853  SlotIndex Def = Copies[i]->def;
855  assert(MI && "No instruction for back-copy");
856 
857  MachineBasicBlock *MBB = MI->getParent();
859  bool AtBegin;
860  do AtBegin = MBBI == MBB->begin();
861  while (!AtBegin && (--MBBI)->isDebugValue());
862 
863  DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
864  LIS.removeVRegDefAt(*LI, Def);
866  MI->eraseFromParent();
867 
868  // Adjust RegAssign if a register assignment is killed at Def. We want to
869  // avoid calculating the live range of the source register if possible.
870  AssignI.find(Def.getPrevSlot());
871  if (!AssignI.valid() || AssignI.start() >= Def)
872  continue;
873  // If MI doesn't kill the assigned register, just leave it.
874  if (AssignI.stop() != Def)
875  continue;
876  unsigned RegIdx = AssignI.value();
877  if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
878  DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n');
879  forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
880  } else {
882  DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI);
883  AssignI.setStop(Kill);
884  }
885  }
886 }
887 
889 SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
890  MachineBasicBlock *DefMBB) {
891  if (MBB == DefMBB)
892  return MBB;
893  assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
894 
895  const MachineLoopInfo &Loops = SA.Loops;
896  const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
897  MachineDomTreeNode *DefDomNode = MDT[DefMBB];
898 
899  // Best candidate so far.
900  MachineBasicBlock *BestMBB = MBB;
901  unsigned BestDepth = std::numeric_limits<unsigned>::max();
902 
903  while (true) {
904  const MachineLoop *Loop = Loops.getLoopFor(MBB);
905 
906  // MBB isn't in a loop, it doesn't get any better. All dominators have a
907  // higher frequency by definition.
908  if (!Loop) {
909  DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
910  << MBB->getNumber() << " at depth 0\n");
911  return MBB;
912  }
913 
914  // We'll never be able to exit the DefLoop.
915  if (Loop == DefLoop) {
916  DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
917  << MBB->getNumber() << " in the same loop\n");
918  return MBB;
919  }
920 
921  // Least busy dominator seen so far.
922  unsigned Depth = Loop->getLoopDepth();
923  if (Depth < BestDepth) {
924  BestMBB = MBB;
925  BestDepth = Depth;
926  DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
927  << MBB->getNumber() << " at depth " << Depth << '\n');
928  }
929 
930  // Leave loop by going to the immediate dominator of the loop header.
931  // This is a bigger stride than simply walking up the dominator tree.
932  MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
933 
934  // Too far up the dominator tree?
935  if (!IDom || !MDT.dominates(DefDomNode, IDom))
936  return BestMBB;
937 
938  MBB = IDom->getBlock();
939  }
940 }
941 
942 void SplitEditor::computeRedundantBackCopies(
943  DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
944  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
945  LiveInterval *Parent = &Edit->getParent();
946  SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
947  SmallPtrSet<VNInfo *, 8> DominatedVNIs;
948 
949  // Aggregate VNIs having the same value as ParentVNI.
950  for (VNInfo *VNI : LI->valnos) {
951  if (VNI->isUnused())
952  continue;
953  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
954  EqualVNs[ParentVNI->id].insert(VNI);
955  }
956 
957  // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
958  // redundant VNIs to BackCopies.
959  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
960  VNInfo *ParentVNI = Parent->getValNumInfo(i);
961  if (!NotToHoistSet.count(ParentVNI->id))
962  continue;
963  SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
965  for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
966  It2 = It1;
967  for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
968  if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
969  continue;
970 
971  MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
972  MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
973  if (MBB1 == MBB2) {
974  DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
975  } else if (MDT.dominates(MBB1, MBB2)) {
976  DominatedVNIs.insert(*It2);
977  } else if (MDT.dominates(MBB2, MBB1)) {
978  DominatedVNIs.insert(*It1);
979  }
980  }
981  }
982  if (!DominatedVNIs.empty()) {
983  forceRecompute(0, ParentVNI);
984  for (auto VNI : DominatedVNIs) {
985  BackCopies.push_back(VNI);
986  }
987  DominatedVNIs.clear();
988  }
989  }
990 }
991 
992 /// For SM_Size mode, find a common dominator for all the back-copies for
993 /// the same ParentVNI and hoist the backcopies to the dominator BB.
994 /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
995 /// to do the hoisting, simply remove the dominated backcopies for the same
996 /// ParentVNI.
997 void SplitEditor::hoistCopies() {
998  // Get the complement interval, always RegIdx 0.
999  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
1000  LiveInterval *Parent = &Edit->getParent();
1001 
1002  // Track the nearest common dominator for all back-copies for each ParentVNI,
1003  // indexed by ParentVNI->id.
1004  using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1005  SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
1006  // The total cost of all the back-copies for each ParentVNI.
1008  // The ParentVNI->id set for which hoisting back-copies are not beneficial
1009  // for Speed.
1010  DenseSet<unsigned> NotToHoistSet;
1011 
1012  // Find the nearest common dominator for parent values with multiple
1013  // back-copies. If a single back-copy dominates, put it in DomPair.second.
1014  for (VNInfo *VNI : LI->valnos) {
1015  if (VNI->isUnused())
1016  continue;
1017  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1018  assert(ParentVNI && "Parent not live at complement def");
1019 
1020  // Don't hoist remats. The complement is probably going to disappear
1021  // completely anyway.
1022  if (Edit->didRematerialize(ParentVNI))
1023  continue;
1024 
1025  MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
1026 
1027  DomPair &Dom = NearestDom[ParentVNI->id];
1028 
1029  // Keep directly defined parent values. This is either a PHI or an
1030  // instruction in the complement range. All other copies of ParentVNI
1031  // should be eliminated.
1032  if (VNI->def == ParentVNI->def) {
1033  DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
1034  Dom = DomPair(ValMBB, VNI->def);
1035  continue;
1036  }
1037  // Skip the singly mapped values. There is nothing to gain from hoisting a
1038  // single back-copy.
1039  if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
1040  DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
1041  continue;
1042  }
1043 
1044  if (!Dom.first) {
1045  // First time we see ParentVNI. VNI dominates itself.
1046  Dom = DomPair(ValMBB, VNI->def);
1047  } else if (Dom.first == ValMBB) {
1048  // Two defs in the same block. Pick the earlier def.
1049  if (!Dom.second.isValid() || VNI->def < Dom.second)
1050  Dom.second = VNI->def;
1051  } else {
1052  // Different basic blocks. Check if one dominates.
1053  MachineBasicBlock *Near =
1054  MDT.findNearestCommonDominator(Dom.first, ValMBB);
1055  if (Near == ValMBB)
1056  // Def ValMBB dominates.
1057  Dom = DomPair(ValMBB, VNI->def);
1058  else if (Near != Dom.first)
1059  // None dominate. Hoist to common dominator, need new def.
1060  Dom = DomPair(Near, SlotIndex());
1061  Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
1062  }
1063 
1064  DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def
1065  << " for parent " << ParentVNI->id << '@' << ParentVNI->def
1066  << " hoist to BB#" << Dom.first->getNumber() << ' '
1067  << Dom.second << '\n');
1068  }
1069 
1070  // Insert the hoisted copies.
1071  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
1072  DomPair &Dom = NearestDom[i];
1073  if (!Dom.first || Dom.second.isValid())
1074  continue;
1075  // This value needs a hoisted copy inserted at the end of Dom.first.
1076  VNInfo *ParentVNI = Parent->getValNumInfo(i);
1077  MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
1078  // Get a less loopy dominator than Dom.first.
1079  Dom.first = findShallowDominator(Dom.first, DefMBB);
1080  if (SpillMode == SM_Speed &&
1081  MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
1082  NotToHoistSet.insert(ParentVNI->id);
1083  continue;
1084  }
1085  SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
1086  Dom.second =
1087  defFromParent(0, ParentVNI, Last, *Dom.first,
1088  SA.getLastSplitPointIter(Dom.first))->def;
1089  }
1090 
1091  // Remove redundant back-copies that are now known to be dominated by another
1092  // def with the same value.
1093  SmallVector<VNInfo*, 8> BackCopies;
1094  for (VNInfo *VNI : LI->valnos) {
1095  if (VNI->isUnused())
1096  continue;
1097  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1098  const DomPair &Dom = NearestDom[ParentVNI->id];
1099  if (!Dom.first || Dom.second == VNI->def ||
1100  NotToHoistSet.count(ParentVNI->id))
1101  continue;
1102  BackCopies.push_back(VNI);
1103  forceRecompute(0, ParentVNI);
1104  }
1105 
1106  // If it is not beneficial to hoist all the BackCopies, simply remove
1107  // redundant BackCopies in speed mode.
1108  if (SpillMode == SM_Speed && !NotToHoistSet.empty())
1109  computeRedundantBackCopies(NotToHoistSet, BackCopies);
1110 
1111  removeBackCopies(BackCopies);
1112 }
1113 
1114 /// transferValues - Transfer all possible values to the new live ranges.
1115 /// Values that were rematerialized are left alone, they need LRCalc.extend().
1116 bool SplitEditor::transferValues() {
1117  bool Skipped = false;
1118  RegAssignMap::const_iterator AssignI = RegAssign.begin();
1119  for (const LiveRange::Segment &S : Edit->getParent()) {
1120  DEBUG(dbgs() << " blit " << S << ':');
1121  VNInfo *ParentVNI = S.valno;
1122  // RegAssign has holes where RegIdx 0 should be used.
1123  SlotIndex Start = S.start;
1124  AssignI.advanceTo(Start);
1125  do {
1126  unsigned RegIdx;
1127  SlotIndex End = S.end;
1128  if (!AssignI.valid()) {
1129  RegIdx = 0;
1130  } else if (AssignI.start() <= Start) {
1131  RegIdx = AssignI.value();
1132  if (AssignI.stop() < End) {
1133  End = AssignI.stop();
1134  ++AssignI;
1135  }
1136  } else {
1137  RegIdx = 0;
1138  End = std::min(End, AssignI.start());
1139  }
1140 
1141  // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1142  DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx
1143  << '(' << PrintReg(Edit->get(RegIdx)) << ')');
1144  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1145 
1146  // Check for a simply defined value that can be blitted directly.
1147  ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
1148  if (VNInfo *VNI = VFP.getPointer()) {
1149  DEBUG(dbgs() << ':' << VNI->id);
1150  LI.addSegment(LiveInterval::Segment(Start, End, VNI));
1151  Start = End;
1152  continue;
1153  }
1154 
1155  // Skip values with forced recomputation.
1156  if (VFP.getInt()) {
1157  DEBUG(dbgs() << "(recalc)");
1158  Skipped = true;
1159  Start = End;
1160  continue;
1161  }
1162 
1163  LiveRangeCalc &LRC = getLRCalc(RegIdx);
1164 
1165  // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1166  // so the live range is accurate. Add live-in blocks in [Start;End) to the
1167  // LiveInBlocks.
1169  SlotIndex BlockStart, BlockEnd;
1170  std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
1171 
1172  // The first block may be live-in, or it may have its own def.
1173  if (Start != BlockStart) {
1174  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1175  assert(VNI && "Missing def for complex mapped value");
1176  DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
1177  // MBB has its own def. Is it also live-out?
1178  if (BlockEnd <= End)
1179  LRC.setLiveOutValue(&*MBB, VNI);
1180 
1181  // Skip to the next block for live-in.
1182  ++MBB;
1183  BlockStart = BlockEnd;
1184  }
1185 
1186  // Handle the live-in blocks covered by [Start;End).
1187  assert(Start <= BlockStart && "Expected live-in block");
1188  while (BlockStart < End) {
1189  DEBUG(dbgs() << ">BB#" << MBB->getNumber());
1190  BlockEnd = LIS.getMBBEndIdx(&*MBB);
1191  if (BlockStart == ParentVNI->def) {
1192  // This block has the def of a parent PHI, so it isn't live-in.
1193  assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
1194  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1195  assert(VNI && "Missing def for complex mapped parent PHI");
1196  if (End >= BlockEnd)
1197  LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
1198  } else {
1199  // This block needs a live-in value. The last block covered may not
1200  // be live-out.
1201  if (End < BlockEnd)
1202  LRC.addLiveInBlock(LI, MDT[&*MBB], End);
1203  else {
1204  // Live-through, and we don't know the value.
1205  LRC.addLiveInBlock(LI, MDT[&*MBB]);
1206  LRC.setLiveOutValue(&*MBB, nullptr);
1207  }
1208  }
1209  BlockStart = BlockEnd;
1210  ++MBB;
1211  }
1212  Start = End;
1213  } while (Start != S.end);
1214  DEBUG(dbgs() << '\n');
1215  }
1216 
1217  LRCalc[0].calculateValues();
1218  if (SpillMode)
1219  LRCalc[1].calculateValues();
1220 
1221  return Skipped;
1222 }
1223 
1224 static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) {
1225  const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
1226  if (Seg == nullptr)
1227  return true;
1228  if (Seg->end != Def.getDeadSlot())
1229  return false;
1230  // This is a dead PHI. Remove it.
1231  LR.removeSegment(*Seg, true);
1232  return true;
1233 }
1234 
1235 void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC,
1236  LiveRange &LR, LaneBitmask LM,
1237  ArrayRef<SlotIndex> Undefs) {
1238  for (MachineBasicBlock *P : B.predecessors()) {
1239  SlotIndex End = LIS.getMBBEndIdx(P);
1240  SlotIndex LastUse = End.getPrevSlot();
1241  // The predecessor may not have a live-out value. That is OK, like an
1242  // undef PHI operand.
1243  LiveInterval &PLI = Edit->getParent();
1244  // Need the cast because the inputs to ?: would otherwise be deemed
1245  // "incompatible": SubRange vs LiveInterval.
1246  LiveRange &PSR = !LM.all() ? getSubRangeForMask(LM, PLI)
1247  : static_cast<LiveRange&>(PLI);
1248  if (PSR.liveAt(LastUse))
1249  LRC.extend(LR, End, /*PhysReg=*/0, Undefs);
1250  }
1251 }
1252 
1253 void SplitEditor::extendPHIKillRanges() {
1254  // Extend live ranges to be live-out for successor PHI values.
1255 
1256  // Visit each PHI def slot in the parent live interval. If the def is dead,
1257  // remove it. Otherwise, extend the live interval to reach the end indexes
1258  // of all predecessor blocks.
1259 
1260  LiveInterval &ParentLI = Edit->getParent();
1261  for (const VNInfo *V : ParentLI.valnos) {
1262  if (V->isUnused() || !V->isPHIDef())
1263  continue;
1264 
1265  unsigned RegIdx = RegAssign.lookup(V->def);
1266  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1267  LiveRangeCalc &LRC = getLRCalc(RegIdx);
1268  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1269  if (!removeDeadSegment(V->def, LI))
1270  extendPHIRange(B, LRC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
1271  }
1272 
1274  LiveRangeCalc SubLRC;
1275 
1276  for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
1277  for (const VNInfo *V : PS.valnos) {
1278  if (V->isUnused() || !V->isPHIDef())
1279  continue;
1280  unsigned RegIdx = RegAssign.lookup(V->def);
1281  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1282  LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI);
1283  if (removeDeadSegment(V->def, S))
1284  continue;
1285 
1286  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1287  SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1288  &LIS.getVNInfoAllocator());
1289  Undefs.clear();
1290  LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
1291  extendPHIRange(B, SubLRC, S, PS.LaneMask, Undefs);
1292  }
1293  }
1294 }
1295 
1296 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1297 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
1298  struct ExtPoint {
1299  ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
1300  : MO(O), RegIdx(R), Next(N) {}
1301 
1302  MachineOperand MO;
1303  unsigned RegIdx;
1304  SlotIndex Next;
1305  };
1306 
1307  SmallVector<ExtPoint,4> ExtPoints;
1308 
1309  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
1310  RE = MRI.reg_end(); RI != RE;) {
1311  MachineOperand &MO = *RI;
1312  MachineInstr *MI = MO.getParent();
1313  ++RI;
1314  // LiveDebugVariables should have handled all DBG_VALUE instructions.
1315  if (MI->isDebugValue()) {
1316  DEBUG(dbgs() << "Zapping " << *MI);
1317  MO.setReg(0);
1318  continue;
1319  }
1320 
1321  // <undef> operands don't really read the register, so it doesn't matter
1322  // which register we choose. When the use operand is tied to a def, we must
1323  // use the same register as the def, so just do that always.
1324  SlotIndex Idx = LIS.getInstructionIndex(*MI);
1325  if (MO.isDef() || MO.isUndef())
1326  Idx = Idx.getRegSlot(MO.isEarlyClobber());
1327 
1328  // Rewrite to the mapped register at Idx.
1329  unsigned RegIdx = RegAssign.lookup(Idx);
1330  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1331  MO.setReg(LI.reg);
1332  DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
1333  << Idx << ':' << RegIdx << '\t' << *MI);
1334 
1335  // Extend liveness to Idx if the instruction reads reg.
1336  if (!ExtendRanges || MO.isUndef())
1337  continue;
1338 
1339  // Skip instructions that don't read Reg.
1340  if (MO.isDef()) {
1341  if (!MO.getSubReg() && !MO.isEarlyClobber())
1342  continue;
1343  // We may want to extend a live range for a partial redef, or for a use
1344  // tied to an early clobber.
1345  Idx = Idx.getPrevSlot();
1346  if (!Edit->getParent().liveAt(Idx))
1347  continue;
1348  } else
1349  Idx = Idx.getRegSlot(true);
1350 
1351  SlotIndex Next = Idx.getNextSlot();
1352  if (LI.hasSubRanges()) {
1353  // We have to delay extending subranges until we have seen all operands
1354  // defining the register. This is because a <def,read-undef> operand
1355  // will create an "undef" point, and we cannot extend any subranges
1356  // until all of them have been accounted for.
1357  if (MO.isUse())
1358  ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1359  } else {
1360  LiveRangeCalc &LRC = getLRCalc(RegIdx);
1361  LRC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
1362  }
1363  }
1364 
1365  for (ExtPoint &EP : ExtPoints) {
1366  LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
1367  assert(LI.hasSubRanges());
1368 
1369  LiveRangeCalc SubLRC;
1370  unsigned Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1371  LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
1372  : MRI.getMaxLaneMaskForVReg(Reg);
1373  for (LiveInterval::SubRange &S : LI.subranges()) {
1374  if ((S.LaneMask & LM).none())
1375  continue;
1376  // The problem here can be that the new register may have been created
1377  // for a partially defined original register. For example:
1378  // %vreg827:subreg_hireg<def,read-undef> = ...
1379  // ...
1380  // %vreg828<def> = COPY %vreg827
1381  if (S.empty())
1382  continue;
1383  SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1384  &LIS.getVNInfoAllocator());
1386  LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
1387  SubLRC.extend(S, EP.Next, 0, Undefs);
1388  }
1389  }
1390 
1391  for (unsigned R : *Edit) {
1392  LiveInterval &LI = LIS.getInterval(R);
1393  if (!LI.hasSubRanges())
1394  continue;
1395  LI.clear();
1396  LI.removeEmptySubRanges();
1397  LIS.constructMainRangeFromSubranges(LI);
1398  }
1399 }
1400 
1401 void SplitEditor::deleteRematVictims() {
1403  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
1404  LiveInterval *LI = &LIS.getInterval(*I);
1405  for (const LiveRange::Segment &S : LI->segments) {
1406  // Dead defs end at the dead slot.
1407  if (S.end != S.valno->def.getDeadSlot())
1408  continue;
1409  if (S.valno->isPHIDef())
1410  continue;
1411  MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1412  assert(MI && "Missing instruction for dead def");
1413  MI->addRegisterDead(LI->reg, &TRI);
1414 
1415  if (!MI->allDefsAreDead())
1416  continue;
1417 
1418  DEBUG(dbgs() << "All defs dead: " << *MI);
1419  Dead.push_back(MI);
1420  }
1421  }
1422 
1423  if (Dead.empty())
1424  return;
1425 
1426  Edit->eliminateDeadDefs(Dead, None, &AA);
1427 }
1428 
1430  ++NumFinished;
1431 
1432  // At this point, the live intervals in Edit contain VNInfos corresponding to
1433  // the inserted copies.
1434 
1435  // Add the original defs from the parent interval.
1436  for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1437  if (ParentVNI->isUnused())
1438  continue;
1439  unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1440  defValue(RegIdx, ParentVNI, ParentVNI->def, true);
1441 
1442  // Force rematted values to be recomputed everywhere.
1443  // The new live ranges may be truncated.
1444  if (Edit->didRematerialize(ParentVNI))
1445  for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1446  forceRecompute(i, ParentVNI);
1447  }
1448 
1449  // Hoist back-copies to the complement interval when in spill mode.
1450  switch (SpillMode) {
1451  case SM_Partition:
1452  // Leave all back-copies as is.
1453  break;
1454  case SM_Size:
1455  case SM_Speed:
1456  // hoistCopies will behave differently between size and speed.
1457  hoistCopies();
1458  }
1459 
1460  // Transfer the simply mapped values, check if any are skipped.
1461  bool Skipped = transferValues();
1462 
1463  // Rewrite virtual registers, possibly extending ranges.
1464  rewriteAssigned(Skipped);
1465 
1466  if (Skipped)
1467  extendPHIKillRanges();
1468  else
1469  ++NumSimple;
1470 
1471  // Delete defs that were rematted everywhere.
1472  if (Skipped)
1473  deleteRematVictims();
1474 
1475  // Get rid of unused values and set phi-kill flags.
1476  for (unsigned Reg : *Edit) {
1477  LiveInterval &LI = LIS.getInterval(Reg);
1478  LI.removeEmptySubRanges();
1479  LI.RenumberValues();
1480  }
1481 
1482  // Provide a reverse mapping from original indices to Edit ranges.
1483  if (LRMap) {
1484  LRMap->clear();
1485  for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1486  LRMap->push_back(i);
1487  }
1488 
1489  // Now check if any registers were separated into multiple components.
1490  ConnectedVNInfoEqClasses ConEQ(LIS);
1491  for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1492  // Don't use iterators, they are invalidated by create() below.
1493  unsigned VReg = Edit->get(i);
1494  LiveInterval &LI = LIS.getInterval(VReg);
1496  LIS.splitSeparateComponents(LI, SplitLIs);
1497  unsigned Original = VRM.getOriginal(VReg);
1498  for (LiveInterval *SplitLI : SplitLIs)
1499  VRM.setIsSplitFromReg(SplitLI->reg, Original);
1500 
1501  // The new intervals all map back to i.
1502  if (LRMap)
1503  LRMap->resize(Edit->size(), i);
1504  }
1505 
1506  // Calculate spill weight and allocation hints for new intervals.
1507  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI);
1508 
1509  assert(!LRMap || LRMap->size() == Edit->size());
1510 }
1511 
1512 //===----------------------------------------------------------------------===//
1513 // Single Block Splitting
1514 //===----------------------------------------------------------------------===//
1515 
1517  bool SingleInstrs) const {
1518  // Always split for multiple instructions.
1519  if (!BI.isOneInstr())
1520  return true;
1521  // Don't split for single instructions unless explicitly requested.
1522  if (!SingleInstrs)
1523  return false;
1524  // Splitting a live-through range always makes progress.
1525  if (BI.LiveIn && BI.LiveOut)
1526  return true;
1527  // No point in isolating a copy. It has no register class constraints.
1528  if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
1529  return false;
1530  // Finally, don't isolate an end point that was created by earlier splits.
1531  return isOriginalEndpoint(BI.FirstInstr);
1532 }
1533 
1535  openIntv();
1536  SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
1537  SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
1538  LastSplitPoint));
1539  if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1540  useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1541  } else {
1542  // The last use is after the last valid split point.
1543  SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1544  useIntv(SegStart, SegStop);
1545  overlapIntv(SegStop, BI.LastInstr);
1546  }
1547 }
1548 
1549 //===----------------------------------------------------------------------===//
1550 // Global Live Range Splitting Support
1551 //===----------------------------------------------------------------------===//
1552 
1553 // These methods support a method of global live range splitting that uses a
1554 // global algorithm to decide intervals for CFG edges. They will insert split
1555 // points and color intervals in basic blocks while avoiding interference.
1556 //
1557 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1558 // are on the stack.
1559 
1561  unsigned IntvIn, SlotIndex LeaveBefore,
1562  unsigned IntvOut, SlotIndex EnterAfter){
1563  SlotIndex Start, Stop;
1564  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1565 
1566  DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop
1567  << ") intf " << LeaveBefore << '-' << EnterAfter
1568  << ", live-through " << IntvIn << " -> " << IntvOut);
1569 
1570  assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1571 
1572  assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1573  assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1574  assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1575 
1576  MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
1577 
1578  if (!IntvOut) {
1579  DEBUG(dbgs() << ", spill on entry.\n");
1580  //
1581  // <<<<<<<<< Possible LeaveBefore interference.
1582  // |-----------| Live through.
1583  // -____________ Spill on entry.
1584  //
1585  selectIntv(IntvIn);
1586  SlotIndex Idx = leaveIntvAtTop(*MBB);
1587  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1588  (void)Idx;
1589  return;
1590  }
1591 
1592  if (!IntvIn) {
1593  DEBUG(dbgs() << ", reload on exit.\n");
1594  //
1595  // >>>>>>> Possible EnterAfter interference.
1596  // |-----------| Live through.
1597  // ___________-- Reload on exit.
1598  //
1599  selectIntv(IntvOut);
1600  SlotIndex Idx = enterIntvAtEnd(*MBB);
1601  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1602  (void)Idx;
1603  return;
1604  }
1605 
1606  if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1607  DEBUG(dbgs() << ", straight through.\n");
1608  //
1609  // |-----------| Live through.
1610  // ------------- Straight through, same intv, no interference.
1611  //
1612  selectIntv(IntvOut);
1613  useIntv(Start, Stop);
1614  return;
1615  }
1616 
1617  // We cannot legally insert splits after LSP.
1618  SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1619  assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1620 
1621  if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1622  LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1623  DEBUG(dbgs() << ", switch avoiding interference.\n");
1624  //
1625  // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference.
1626  // |-----------| Live through.
1627  // ------======= Switch intervals between interference.
1628  //
1629  selectIntv(IntvOut);
1630  SlotIndex Idx;
1631  if (LeaveBefore && LeaveBefore < LSP) {
1632  Idx = enterIntvBefore(LeaveBefore);
1633  useIntv(Idx, Stop);
1634  } else {
1635  Idx = enterIntvAtEnd(*MBB);
1636  }
1637  selectIntv(IntvIn);
1638  useIntv(Start, Idx);
1639  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1640  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1641  return;
1642  }
1643 
1644  DEBUG(dbgs() << ", create local intv for interference.\n");
1645  //
1646  // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference.
1647  // |-----------| Live through.
1648  // ==---------== Switch intervals before/after interference.
1649  //
1650  assert(LeaveBefore <= EnterAfter && "Missed case");
1651 
1652  selectIntv(IntvOut);
1653  SlotIndex Idx = enterIntvAfter(EnterAfter);
1654  useIntv(Idx, Stop);
1655  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1656 
1657  selectIntv(IntvIn);
1658  Idx = leaveIntvBefore(LeaveBefore);
1659  useIntv(Start, Idx);
1660  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1661 }
1662 
1664  unsigned IntvIn, SlotIndex LeaveBefore) {
1665  SlotIndex Start, Stop;
1666  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1667 
1668  DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1669  << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1670  << ", reg-in " << IntvIn << ", leave before " << LeaveBefore
1671  << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1672 
1673  assert(IntvIn && "Must have register in");
1674  assert(BI.LiveIn && "Must be live-in");
1675  assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1676 
1677  if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1678  DEBUG(dbgs() << " before interference.\n");
1679  //
1680  // <<< Interference after kill.
1681  // |---o---x | Killed in block.
1682  // ========= Use IntvIn everywhere.
1683  //
1684  selectIntv(IntvIn);
1685  useIntv(Start, BI.LastInstr);
1686  return;
1687  }
1688 
1689  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1690 
1691  if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1692  //
1693  // <<< Possible interference after last use.
1694  // |---o---o---| Live-out on stack.
1695  // =========____ Leave IntvIn after last use.
1696  //
1697  // < Interference after last use.
1698  // |---o---o--o| Live-out on stack, late last use.
1699  // ============ Copy to stack after LSP, overlap IntvIn.
1700  // \_____ Stack interval is live-out.
1701  //
1702  if (BI.LastInstr < LSP) {
1703  DEBUG(dbgs() << ", spill after last use before interference.\n");
1704  selectIntv(IntvIn);
1706  useIntv(Start, Idx);
1707  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1708  } else {
1709  DEBUG(dbgs() << ", spill before last split point.\n");
1710  selectIntv(IntvIn);
1711  SlotIndex Idx = leaveIntvBefore(LSP);
1712  overlapIntv(Idx, BI.LastInstr);
1713  useIntv(Start, Idx);
1714  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1715  }
1716  return;
1717  }
1718 
1719  // The interference is overlapping somewhere we wanted to use IntvIn. That
1720  // means we need to create a local interval that can be allocated a
1721  // different register.
1722  unsigned LocalIntv = openIntv();
1723  (void)LocalIntv;
1724  DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1725 
1726  if (!BI.LiveOut || BI.LastInstr < LSP) {
1727  //
1728  // <<<<<<< Interference overlapping uses.
1729  // |---o---o---| Live-out on stack.
1730  // =====----____ Leave IntvIn before interference, then spill.
1731  //
1733  SlotIndex From = enterIntvBefore(LeaveBefore);
1734  useIntv(From, To);
1735  selectIntv(IntvIn);
1736  useIntv(Start, From);
1737  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1738  return;
1739  }
1740 
1741  // <<<<<<< Interference overlapping uses.
1742  // |---o---o--o| Live-out on stack, late last use.
1743  // =====------- Copy to stack before LSP, overlap LocalIntv.
1744  // \_____ Stack interval is live-out.
1745  //
1746  SlotIndex To = leaveIntvBefore(LSP);
1747  overlapIntv(To, BI.LastInstr);
1748  SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1749  useIntv(From, To);
1750  selectIntv(IntvIn);
1751  useIntv(Start, From);
1752  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1753 }
1754 
1756  unsigned IntvOut, SlotIndex EnterAfter) {
1757  SlotIndex Start, Stop;
1758  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1759 
1760  DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1761  << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1762  << ", reg-out " << IntvOut << ", enter after " << EnterAfter
1763  << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1764 
1765  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1766 
1767  assert(IntvOut && "Must have register out");
1768  assert(BI.LiveOut && "Must be live-out");
1769  assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1770 
1771  if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1772  DEBUG(dbgs() << " after interference.\n");
1773  //
1774  // >>>> Interference before def.
1775  // | o---o---| Defined in block.
1776  // ========= Use IntvOut everywhere.
1777  //
1778  selectIntv(IntvOut);
1779  useIntv(BI.FirstInstr, Stop);
1780  return;
1781  }
1782 
1783  if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1784  DEBUG(dbgs() << ", reload after interference.\n");
1785  //
1786  // >>>> Interference before def.
1787  // |---o---o---| Live-through, stack-in.
1788  // ____========= Enter IntvOut before first use.
1789  //
1790  selectIntv(IntvOut);
1791  SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1792  useIntv(Idx, Stop);
1793  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1794  return;
1795  }
1796 
1797  // The interference is overlapping somewhere we wanted to use IntvOut. That
1798  // means we need to create a local interval that can be allocated a
1799  // different register.
1800  DEBUG(dbgs() << ", interference overlaps uses.\n");
1801  //
1802  // >>>>>>> Interference overlapping uses.
1803  // |---o---o---| Live-through, stack-in.
1804  // ____---====== Create local interval for interference range.
1805  //
1806  selectIntv(IntvOut);
1807  SlotIndex Idx = enterIntvAfter(EnterAfter);
1808  useIntv(Idx, Stop);
1809  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1810 
1811  openIntv();
1812  SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
1813  useIntv(From, Idx);
1814 }
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:244
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
static LaneBitmask getAll()
Definition: LaneBitmask.h:84
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:1663
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:1534
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
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.
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:781
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:826
ValT lookup(KeyT x, ValT NotFound=ValT()) const
lookup - Return the mapped value at x or NotFound.
Definition: IntervalMap.h:1076
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
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:758
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:1429
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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.
#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:713
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:747
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:138
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:935
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:354
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:808
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:1755
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:789
bool isDebugValue() const
Definition: MachineInstr.h:816
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:864
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineInstrBuilder MachineInstrBuilder & DefMI
static LaneBitmask getNone()
Definition: LaneBitmask.h:83
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:1516
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:482
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:139
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:59
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:1560
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:420
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:1224
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:355