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/Config/llvm-config.h"
43 #include "llvm/IR/DebugLoc.h"
44 #include "llvm/MC/LaneBitmask.h"
45 #include "llvm/Support/Allocator.h"
47 #include "llvm/Support/Compiler.h"
48 #include "llvm/Support/Debug.h"
51 #include <algorithm>
52 #include <cassert>
53 #include <iterator>
54 #include <limits>
55 #include <tuple>
56 #include <utility>
57 
58 using namespace llvm;
59 
60 #define DEBUG_TYPE "regalloc"
61 
62 STATISTIC(NumFinished, "Number of splits finished");
63 STATISTIC(NumSimple, "Number of splits that were simple");
64 STATISTIC(NumCopies, "Number of copies inserted for splitting");
65 STATISTIC(NumRemats, "Number of rematerialized defs for splitting");
66 STATISTIC(NumRepairs, "Number of invalid live ranges repaired");
67 
68 //===----------------------------------------------------------------------===//
69 // Last Insert Point Analysis
70 //===----------------------------------------------------------------------===//
71 
73  unsigned BBNum)
74  : LIS(lis), LastInsertPoint(BBNum) {}
75 
77 InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
78  const MachineBasicBlock &MBB) {
79  unsigned Num = MBB.getNumber();
80  std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
81  SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);
82 
84  for (const MachineBasicBlock *SMBB : MBB.successors())
85  if (SMBB->isEHPad())
86  EHPadSuccessors.push_back(SMBB);
87 
88  // Compute insert points on the first call. The pair is independent of the
89  // current live interval.
90  if (!LIP.first.isValid()) {
92  if (FirstTerm == MBB.end())
93  LIP.first = MBBEnd;
94  else
95  LIP.first = LIS.getInstructionIndex(*FirstTerm);
96 
97  // If there is a landing pad successor, also find the call instruction.
98  if (EHPadSuccessors.empty())
99  return LIP.first;
100  // There may not be a call instruction (?) in which case we ignore LPad.
101  LIP.second = LIP.first;
102  for (MachineBasicBlock::const_iterator I = MBB.end(), E = MBB.begin();
103  I != E;) {
104  --I;
105  if (I->isCall()) {
106  LIP.second = LIS.getInstructionIndex(*I);
107  break;
108  }
109  }
110  }
111 
112  // If CurLI is live into a landing pad successor, move the last insert point
113  // back to the call that may throw.
114  if (!LIP.second)
115  return LIP.first;
116 
117  if (none_of(EHPadSuccessors, [&](const MachineBasicBlock *EHPad) {
118  return LIS.isLiveInToMBB(CurLI, EHPad);
119  }))
120  return LIP.first;
121 
122  // Find the value leaving MBB.
123  const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
124  if (!VNI)
125  return LIP.first;
126 
127  // If the value leaving MBB was defined after the call in MBB, it can't
128  // really be live-in to the landing pad. This can happen if the landing pad
129  // has a PHI, and this register is undef on the exceptional edge.
130  // <rdar://problem/10664933>
131  if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
132  return LIP.first;
133 
134  // Value is properly live-in to the landing pad.
135  // Only allow inserts before the call.
136  return LIP.second;
137 }
138 
141  MachineBasicBlock &MBB) {
142  SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
143  if (LIP == LIS.getMBBEndIdx(&MBB))
144  return MBB.end();
145  return LIS.getInstructionFromIndex(LIP);
146 }
147 
148 //===----------------------------------------------------------------------===//
149 // Split Analysis
150 //===----------------------------------------------------------------------===//
151 
153  const MachineLoopInfo &mli)
154  : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
155  TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
156 
158  UseSlots.clear();
159  UseBlocks.clear();
160  ThroughBlocks.clear();
161  CurLI = nullptr;
162  DidRepairRange = false;
163 }
164 
165 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
166 void SplitAnalysis::analyzeUses() {
167  assert(UseSlots.empty() && "Call clear first");
168 
169  // First get all the defs from the interval values. This provides the correct
170  // slots for early clobbers.
171  for (const VNInfo *VNI : CurLI->valnos)
172  if (!VNI->isPHIDef() && !VNI->isUnused())
173  UseSlots.push_back(VNI->def);
174 
175  // Get use slots form the use-def chain.
177  for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
178  if (!MO.isUndef())
179  UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());
180 
181  array_pod_sort(UseSlots.begin(), UseSlots.end());
182 
183  // Remove duplicates, keeping the smaller slot for each instruction.
184  // That is what we want for early clobbers.
185  UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
187  UseSlots.end());
188 
189  // Compute per-live block info.
190  if (!calcLiveBlockInfo()) {
191  // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
192  // I am looking at you, RegisterCoalescer!
193  DidRepairRange = true;
194  ++NumRepairs;
195  LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
196  const_cast<LiveIntervals&>(LIS)
197  .shrinkToUses(const_cast<LiveInterval*>(CurLI));
198  UseBlocks.clear();
199  ThroughBlocks.clear();
200  bool fixed = calcLiveBlockInfo();
201  (void)fixed;
202  assert(fixed && "Couldn't fix broken live interval");
203  }
204 
205  LLVM_DEBUG(dbgs() << "Analyze counted " << 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  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];
496  VNInfo *VNI = VFP.getPointer();
497 
498  // ParentVNI was either unmapped or already complex mapped. Either way, just
499  // set the force bit.
500  if (!VNI) {
501  VFP.setInt(true);
502  return;
503  }
504 
505  // This was previously a single mapping. Make sure the old def is represented
506  // by a trivial live range.
507  addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
508 
509  // Mark as complex mapped, forced.
510  VFP = ValueForcePair(nullptr, true);
511 }
512 
513 SlotIndex SplitEditor::buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg,
515  unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) {
516  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
517  bool FirstCopy = !Def.isValid();
518  MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)
519  .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)
520  | getInternalReadRegState(!FirstCopy), SubIdx)
521  .addReg(FromReg, 0, SubIdx);
522 
523  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
524  if (FirstCopy) {
525  SlotIndexes &Indexes = *LIS.getSlotIndexes();
526  Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
527  } else {
528  CopyMI->bundleWithPred();
529  }
530  LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx);
531  DestLI.refineSubRanges(Allocator, LaneMask,
532  [Def, &Allocator](LiveInterval::SubRange& SR) {
533  SR.createDeadDef(Def, Allocator);
534  });
535  return Def;
536 }
537 
538 SlotIndex SplitEditor::buildCopy(unsigned FromReg, unsigned ToReg,
539  LaneBitmask LaneMask, MachineBasicBlock &MBB,
540  MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {
541  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
542  if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {
543  // The full vreg is copied.
544  MachineInstr *CopyMI =
545  BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg);
546  SlotIndexes &Indexes = *LIS.getSlotIndexes();
547  return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
548  }
549 
550  // Only a subset of lanes needs to be copied. The following is a simple
551  // heuristic to construct a sequence of COPYs. We could add a target
552  // specific callback if this turns out to be suboptimal.
553  LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));
554 
555  // First pass: Try to find a perfectly matching subregister index. If none
556  // exists find the one covering the most lanemask bits.
557  SmallVector<unsigned, 8> PossibleIndexes;
558  unsigned BestIdx = 0;
559  unsigned BestCover = 0;
560  const TargetRegisterClass *RC = MRI.getRegClass(FromReg);
561  assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");
562  for (unsigned Idx = 1, E = TRI.getNumSubRegIndices(); Idx < E; ++Idx) {
563  // Is this index even compatible with the given class?
564  if (TRI.getSubClassWithSubReg(RC, Idx) != RC)
565  continue;
566  LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
567  // Early exit if we found a perfect match.
568  if (SubRegMask == LaneMask) {
569  BestIdx = Idx;
570  break;
571  }
572 
573  // The index must not cover any lanes outside \p LaneMask.
574  if ((SubRegMask & ~LaneMask).any())
575  continue;
576 
577  unsigned PopCount = SubRegMask.getNumLanes();
578  PossibleIndexes.push_back(Idx);
579  if (PopCount > BestCover) {
580  BestCover = PopCount;
581  BestIdx = Idx;
582  }
583  }
584 
585  // Abort if we cannot possibly implement the COPY with the given indexes.
586  if (BestIdx == 0)
587  report_fatal_error("Impossible to implement partial COPY");
588 
589  SlotIndex Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore,
590  BestIdx, DestLI, Late, SlotIndex());
591 
592  // Greedy heuristic: Keep iterating keeping the best covering subreg index
593  // each time.
594  LaneBitmask LanesLeft = LaneMask & ~(TRI.getSubRegIndexLaneMask(BestIdx));
595  while (LanesLeft.any()) {
596  unsigned BestIdx = 0;
597  int BestCover = std::numeric_limits<int>::min();
598  for (unsigned Idx : PossibleIndexes) {
599  LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
600  // Early exit if we found a perfect match.
601  if (SubRegMask == LanesLeft) {
602  BestIdx = Idx;
603  break;
604  }
605 
606  // Try to cover as much of the remaining lanes as possible but
607  // as few of the already covered lanes as possible.
608  int Cover = (SubRegMask & LanesLeft).getNumLanes()
609  - (SubRegMask & ~LanesLeft).getNumLanes();
610  if (Cover > BestCover) {
611  BestCover = Cover;
612  BestIdx = Idx;
613  }
614  }
615 
616  if (BestIdx == 0)
617  report_fatal_error("Impossible to implement partial COPY");
618 
619  buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,
620  DestLI, Late, Def);
621  LanesLeft &= ~TRI.getSubRegIndexLaneMask(BestIdx);
622  }
623 
624  return Def;
625 }
626 
627 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
628  VNInfo *ParentVNI,
629  SlotIndex UseIdx,
630  MachineBasicBlock &MBB,
632  SlotIndex Def;
633  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
634 
635  // We may be trying to avoid interference that ends at a deleted instruction,
636  // so always begin RegIdx 0 early and all others late.
637  bool Late = RegIdx != 0;
638 
639  // Attempt cheap-as-a-copy rematerialization.
640  unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
641  LiveInterval &OrigLI = LIS.getInterval(Original);
642  VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
643 
644  unsigned Reg = LI->reg;
645  bool DidRemat = false;
646  if (OrigVNI) {
647  LiveRangeEdit::Remat RM(ParentVNI);
648  RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
649  if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
650  Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);
651  ++NumRemats;
652  DidRemat = true;
653  }
654  }
655  if (!DidRemat) {
656  LaneBitmask LaneMask;
657  if (LI->hasSubRanges()) {
658  LaneMask = LaneBitmask::getNone();
659  for (LiveInterval::SubRange &S : LI->subranges())
660  LaneMask |= S.LaneMask;
661  } else {
662  LaneMask = LaneBitmask::getAll();
663  }
664 
665  ++NumCopies;
666  Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);
667  }
668 
669  // Define the value in Reg.
670  return defValue(RegIdx, ParentVNI, Def, false);
671 }
672 
673 /// Create a new virtual register and live interval.
675  // Create the complement as index 0.
676  if (Edit->empty())
677  Edit->createEmptyInterval();
678 
679  // Create the open interval.
680  OpenIdx = Edit->size();
681  Edit->createEmptyInterval();
682  return OpenIdx;
683 }
684 
685 void SplitEditor::selectIntv(unsigned Idx) {
686  assert(Idx != 0 && "Cannot select the complement interval");
687  assert(Idx < Edit->size() && "Can only select previously opened interval");
688  LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n');
689  OpenIdx = Idx;
690 }
691 
693  assert(OpenIdx && "openIntv not called before enterIntvBefore");
694  LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx);
695  Idx = Idx.getBaseIndex();
696  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
697  if (!ParentVNI) {
698  LLVM_DEBUG(dbgs() << ": not live\n");
699  return Idx;
700  }
701  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
703  assert(MI && "enterIntvBefore called with invalid index");
704 
705  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
706  return VNI->def;
707 }
708 
710  assert(OpenIdx && "openIntv not called before enterIntvAfter");
711  LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx);
712  Idx = Idx.getBoundaryIndex();
713  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
714  if (!ParentVNI) {
715  LLVM_DEBUG(dbgs() << ": not live\n");
716  return Idx;
717  }
718  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
720  assert(MI && "enterIntvAfter called with invalid index");
721 
722  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
723  std::next(MachineBasicBlock::iterator(MI)));
724  return VNI->def;
725 }
726 
728  assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
729  SlotIndex End = LIS.getMBBEndIdx(&MBB);
730  SlotIndex Last = End.getPrevSlot();
731  LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB) << ", "
732  << Last);
733  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
734  if (!ParentVNI) {
735  LLVM_DEBUG(dbgs() << ": not live\n");
736  return End;
737  }
738  LLVM_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  LLVM_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  LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
754  RegAssign.insert(Start, End, OpenIdx);
755  LLVM_DEBUG(dump());
756 }
757 
759  assert(OpenIdx && "openIntv not called before leaveIntvAfter");
760  LLVM_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  LLVM_DEBUG(dbgs() << ": not live\n");
767  return Boundary.getNextSlot();
768  }
769  LLVM_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  LLVM_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  LLVM_DEBUG(dbgs() << ": not live\n");
798  return Idx.getNextSlot();
799  }
800  LLVM_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  LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB) << ", "
812  << Start);
813 
814  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
815  if (!ParentVNI) {
816  LLVM_DEBUG(dbgs() << ": not live\n");
817  return Start;
818  }
819 
820  VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
821  MBB.SkipPHIsLabelsAndDebug(MBB.begin()));
822  RegAssign.insert(Start, VNI->def, OpenIdx);
823  LLVM_DEBUG(dump());
824  return VNI->def;
825 }
826 
828  assert(OpenIdx && "openIntv not called before overlapIntv");
829  const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
830  assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
831  "Parent changes value in extended range");
832  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
833  "Range cannot span basic blocks");
834 
835  // The complement interval will be extended as needed by LRCalc.extend().
836  if (ParentVNI)
837  forceRecompute(0, *ParentVNI);
838  LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
839  RegAssign.insert(Start, End, OpenIdx);
840  LLVM_DEBUG(dump());
841 }
842 
843 //===----------------------------------------------------------------------===//
844 // Spill modes
845 //===----------------------------------------------------------------------===//
846 
847 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
848  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
849  LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
850  RegAssignMap::iterator AssignI;
851  AssignI.setMap(RegAssign);
852 
853  for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
854  SlotIndex Def = Copies[i]->def;
856  assert(MI && "No instruction for back-copy");
857 
858  MachineBasicBlock *MBB = MI->getParent();
860  bool AtBegin;
861  do AtBegin = MBBI == MBB->begin();
862  while (!AtBegin && (--MBBI)->isDebugInstr());
863 
864  LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
865  LIS.removeVRegDefAt(*LI, Def);
867  MI->eraseFromParent();
868 
869  // Adjust RegAssign if a register assignment is killed at Def. We want to
870  // avoid calculating the live range of the source register if possible.
871  AssignI.find(Def.getPrevSlot());
872  if (!AssignI.valid() || AssignI.start() >= Def)
873  continue;
874  // If MI doesn't kill the assigned register, just leave it.
875  if (AssignI.stop() != Def)
876  continue;
877  unsigned RegIdx = AssignI.value();
878  if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
879  LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx
880  << '\n');
881  forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));
882  } else {
884  LLVM_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  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
912  << " dominates " << printMBBReference(*MBB)
913  << " at depth 0\n");
914  return MBB;
915  }
916 
917  // We'll never be able to exit the DefLoop.
918  if (Loop == DefLoop) {
919  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
920  << " dominates " << printMBBReference(*MBB)
921  << " in the same loop\n");
922  return MBB;
923  }
924 
925  // Least busy dominator seen so far.
926  unsigned Depth = Loop->getLoopDepth();
927  if (Depth < BestDepth) {
928  BestMBB = MBB;
929  BestDepth = Depth;
930  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
931  << " dominates " << printMBBReference(*MBB)
932  << " at depth " << Depth << '\n');
933  }
934 
935  // Leave loop by going to the immediate dominator of the loop header.
936  // This is a bigger stride than simply walking up the dominator tree.
937  MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
938 
939  // Too far up the dominator tree?
940  if (!IDom || !MDT.dominates(DefDomNode, IDom))
941  return BestMBB;
942 
943  MBB = IDom->getBlock();
944  }
945 }
946 
947 void SplitEditor::computeRedundantBackCopies(
948  DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
949  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
950  LiveInterval *Parent = &Edit->getParent();
951  SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
952  SmallPtrSet<VNInfo *, 8> DominatedVNIs;
953 
954  // Aggregate VNIs having the same value as ParentVNI.
955  for (VNInfo *VNI : LI->valnos) {
956  if (VNI->isUnused())
957  continue;
958  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
959  EqualVNs[ParentVNI->id].insert(VNI);
960  }
961 
962  // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
963  // redundant VNIs to BackCopies.
964  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
965  VNInfo *ParentVNI = Parent->getValNumInfo(i);
966  if (!NotToHoistSet.count(ParentVNI->id))
967  continue;
968  SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
970  for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
971  It2 = It1;
972  for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
973  if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
974  continue;
975 
976  MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
977  MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
978  if (MBB1 == MBB2) {
979  DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
980  } else if (MDT.dominates(MBB1, MBB2)) {
981  DominatedVNIs.insert(*It2);
982  } else if (MDT.dominates(MBB2, MBB1)) {
983  DominatedVNIs.insert(*It1);
984  }
985  }
986  }
987  if (!DominatedVNIs.empty()) {
988  forceRecompute(0, *ParentVNI);
989  for (auto VNI : DominatedVNIs) {
990  BackCopies.push_back(VNI);
991  }
992  DominatedVNIs.clear();
993  }
994  }
995 }
996 
997 /// For SM_Size mode, find a common dominator for all the back-copies for
998 /// the same ParentVNI and hoist the backcopies to the dominator BB.
999 /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
1000 /// to do the hoisting, simply remove the dominated backcopies for the same
1001 /// ParentVNI.
1002 void SplitEditor::hoistCopies() {
1003  // Get the complement interval, always RegIdx 0.
1004  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
1005  LiveInterval *Parent = &Edit->getParent();
1006 
1007  // Track the nearest common dominator for all back-copies for each ParentVNI,
1008  // indexed by ParentVNI->id.
1009  using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1010  SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
1011  // The total cost of all the back-copies for each ParentVNI.
1013  // The ParentVNI->id set for which hoisting back-copies are not beneficial
1014  // for Speed.
1015  DenseSet<unsigned> NotToHoistSet;
1016 
1017  // Find the nearest common dominator for parent values with multiple
1018  // back-copies. If a single back-copy dominates, put it in DomPair.second.
1019  for (VNInfo *VNI : LI->valnos) {
1020  if (VNI->isUnused())
1021  continue;
1022  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1023  assert(ParentVNI && "Parent not live at complement def");
1024 
1025  // Don't hoist remats. The complement is probably going to disappear
1026  // completely anyway.
1027  if (Edit->didRematerialize(ParentVNI))
1028  continue;
1029 
1030  MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
1031 
1032  DomPair &Dom = NearestDom[ParentVNI->id];
1033 
1034  // Keep directly defined parent values. This is either a PHI or an
1035  // instruction in the complement range. All other copies of ParentVNI
1036  // should be eliminated.
1037  if (VNI->def == ParentVNI->def) {
1038  LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
1039  Dom = DomPair(ValMBB, VNI->def);
1040  continue;
1041  }
1042  // Skip the singly mapped values. There is nothing to gain from hoisting a
1043  // single back-copy.
1044  if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
1045  LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
1046  continue;
1047  }
1048 
1049  if (!Dom.first) {
1050  // First time we see ParentVNI. VNI dominates itself.
1051  Dom = DomPair(ValMBB, VNI->def);
1052  } else if (Dom.first == ValMBB) {
1053  // Two defs in the same block. Pick the earlier def.
1054  if (!Dom.second.isValid() || VNI->def < Dom.second)
1055  Dom.second = VNI->def;
1056  } else {
1057  // Different basic blocks. Check if one dominates.
1058  MachineBasicBlock *Near =
1059  MDT.findNearestCommonDominator(Dom.first, ValMBB);
1060  if (Near == ValMBB)
1061  // Def ValMBB dominates.
1062  Dom = DomPair(ValMBB, VNI->def);
1063  else if (Near != Dom.first)
1064  // None dominate. Hoist to common dominator, need new def.
1065  Dom = DomPair(Near, SlotIndex());
1066  Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
1067  }
1068 
1069  LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'
1070  << VNI->def << " for parent " << ParentVNI->id << '@'
1071  << ParentVNI->def << " hoist to "
1072  << printMBBReference(*Dom.first) << ' ' << Dom.second
1073  << '\n');
1074  }
1075 
1076  // Insert the hoisted copies.
1077  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
1078  DomPair &Dom = NearestDom[i];
1079  if (!Dom.first || Dom.second.isValid())
1080  continue;
1081  // This value needs a hoisted copy inserted at the end of Dom.first.
1082  VNInfo *ParentVNI = Parent->getValNumInfo(i);
1083  MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
1084  // Get a less loopy dominator than Dom.first.
1085  Dom.first = findShallowDominator(Dom.first, DefMBB);
1086  if (SpillMode == SM_Speed &&
1087  MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
1088  NotToHoistSet.insert(ParentVNI->id);
1089  continue;
1090  }
1091  SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
1092  Dom.second =
1093  defFromParent(0, ParentVNI, Last, *Dom.first,
1094  SA.getLastSplitPointIter(Dom.first))->def;
1095  }
1096 
1097  // Remove redundant back-copies that are now known to be dominated by another
1098  // def with the same value.
1099  SmallVector<VNInfo*, 8> BackCopies;
1100  for (VNInfo *VNI : LI->valnos) {
1101  if (VNI->isUnused())
1102  continue;
1103  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1104  const DomPair &Dom = NearestDom[ParentVNI->id];
1105  if (!Dom.first || Dom.second == VNI->def ||
1106  NotToHoistSet.count(ParentVNI->id))
1107  continue;
1108  BackCopies.push_back(VNI);
1109  forceRecompute(0, *ParentVNI);
1110  }
1111 
1112  // If it is not beneficial to hoist all the BackCopies, simply remove
1113  // redundant BackCopies in speed mode.
1114  if (SpillMode == SM_Speed && !NotToHoistSet.empty())
1115  computeRedundantBackCopies(NotToHoistSet, BackCopies);
1116 
1117  removeBackCopies(BackCopies);
1118 }
1119 
1120 /// transferValues - Transfer all possible values to the new live ranges.
1121 /// Values that were rematerialized are left alone, they need LRCalc.extend().
1122 bool SplitEditor::transferValues() {
1123  bool Skipped = false;
1124  RegAssignMap::const_iterator AssignI = RegAssign.begin();
1125  for (const LiveRange::Segment &S : Edit->getParent()) {
1126  LLVM_DEBUG(dbgs() << " blit " << S << ':');
1127  VNInfo *ParentVNI = S.valno;
1128  // RegAssign has holes where RegIdx 0 should be used.
1129  SlotIndex Start = S.start;
1130  AssignI.advanceTo(Start);
1131  do {
1132  unsigned RegIdx;
1133  SlotIndex End = S.end;
1134  if (!AssignI.valid()) {
1135  RegIdx = 0;
1136  } else if (AssignI.start() <= Start) {
1137  RegIdx = AssignI.value();
1138  if (AssignI.stop() < End) {
1139  End = AssignI.stop();
1140  ++AssignI;
1141  }
1142  } else {
1143  RegIdx = 0;
1144  End = std::min(End, AssignI.start());
1145  }
1146 
1147  // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1148  LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('
1149  << printReg(Edit->get(RegIdx)) << ')');
1150  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1151 
1152  // Check for a simply defined value that can be blitted directly.
1153  ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
1154  if (VNInfo *VNI = VFP.getPointer()) {
1155  LLVM_DEBUG(dbgs() << ':' << VNI->id);
1156  LI.addSegment(LiveInterval::Segment(Start, End, VNI));
1157  Start = End;
1158  continue;
1159  }
1160 
1161  // Skip values with forced recomputation.
1162  if (VFP.getInt()) {
1163  LLVM_DEBUG(dbgs() << "(recalc)");
1164  Skipped = true;
1165  Start = End;
1166  continue;
1167  }
1168 
1169  LiveRangeCalc &LRC = getLRCalc(RegIdx);
1170 
1171  // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1172  // so the live range is accurate. Add live-in blocks in [Start;End) to the
1173  // LiveInBlocks.
1175  SlotIndex BlockStart, BlockEnd;
1176  std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
1177 
1178  // The first block may be live-in, or it may have its own def.
1179  if (Start != BlockStart) {
1180  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1181  assert(VNI && "Missing def for complex mapped value");
1182  LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB));
1183  // MBB has its own def. Is it also live-out?
1184  if (BlockEnd <= End)
1185  LRC.setLiveOutValue(&*MBB, VNI);
1186 
1187  // Skip to the next block for live-in.
1188  ++MBB;
1189  BlockStart = BlockEnd;
1190  }
1191 
1192  // Handle the live-in blocks covered by [Start;End).
1193  assert(Start <= BlockStart && "Expected live-in block");
1194  while (BlockStart < End) {
1195  LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB));
1196  BlockEnd = LIS.getMBBEndIdx(&*MBB);
1197  if (BlockStart == ParentVNI->def) {
1198  // This block has the def of a parent PHI, so it isn't live-in.
1199  assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
1200  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1201  assert(VNI && "Missing def for complex mapped parent PHI");
1202  if (End >= BlockEnd)
1203  LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
1204  } else {
1205  // This block needs a live-in value. The last block covered may not
1206  // be live-out.
1207  if (End < BlockEnd)
1208  LRC.addLiveInBlock(LI, MDT[&*MBB], End);
1209  else {
1210  // Live-through, and we don't know the value.
1211  LRC.addLiveInBlock(LI, MDT[&*MBB]);
1212  LRC.setLiveOutValue(&*MBB, nullptr);
1213  }
1214  }
1215  BlockStart = BlockEnd;
1216  ++MBB;
1217  }
1218  Start = End;
1219  } while (Start != S.end);
1220  LLVM_DEBUG(dbgs() << '\n');
1221  }
1222 
1223  LRCalc[0].calculateValues();
1224  if (SpillMode)
1225  LRCalc[1].calculateValues();
1226 
1227  return Skipped;
1228 }
1229 
1230 static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) {
1231  const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
1232  if (Seg == nullptr)
1233  return true;
1234  if (Seg->end != Def.getDeadSlot())
1235  return false;
1236  // This is a dead PHI. Remove it.
1237  LR.removeSegment(*Seg, true);
1238  return true;
1239 }
1240 
1241 void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC,
1242  LiveRange &LR, LaneBitmask LM,
1243  ArrayRef<SlotIndex> Undefs) {
1244  for (MachineBasicBlock *P : B.predecessors()) {
1245  SlotIndex End = LIS.getMBBEndIdx(P);
1246  SlotIndex LastUse = End.getPrevSlot();
1247  // The predecessor may not have a live-out value. That is OK, like an
1248  // undef PHI operand.
1249  LiveInterval &PLI = Edit->getParent();
1250  // Need the cast because the inputs to ?: would otherwise be deemed
1251  // "incompatible": SubRange vs LiveInterval.
1252  LiveRange &PSR = !LM.all() ? getSubRangeForMask(LM, PLI)
1253  : static_cast<LiveRange&>(PLI);
1254  if (PSR.liveAt(LastUse))
1255  LRC.extend(LR, End, /*PhysReg=*/0, Undefs);
1256  }
1257 }
1258 
1259 void SplitEditor::extendPHIKillRanges() {
1260  // Extend live ranges to be live-out for successor PHI values.
1261 
1262  // Visit each PHI def slot in the parent live interval. If the def is dead,
1263  // remove it. Otherwise, extend the live interval to reach the end indexes
1264  // of all predecessor blocks.
1265 
1266  LiveInterval &ParentLI = Edit->getParent();
1267  for (const VNInfo *V : ParentLI.valnos) {
1268  if (V->isUnused() || !V->isPHIDef())
1269  continue;
1270 
1271  unsigned RegIdx = RegAssign.lookup(V->def);
1272  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1273  LiveRangeCalc &LRC = getLRCalc(RegIdx);
1274  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1275  if (!removeDeadSegment(V->def, LI))
1276  extendPHIRange(B, LRC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
1277  }
1278 
1280  LiveRangeCalc SubLRC;
1281 
1282  for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
1283  for (const VNInfo *V : PS.valnos) {
1284  if (V->isUnused() || !V->isPHIDef())
1285  continue;
1286  unsigned RegIdx = RegAssign.lookup(V->def);
1287  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1288  LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI);
1289  if (removeDeadSegment(V->def, S))
1290  continue;
1291 
1292  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1293  SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1294  &LIS.getVNInfoAllocator());
1295  Undefs.clear();
1296  LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
1297  extendPHIRange(B, SubLRC, S, PS.LaneMask, Undefs);
1298  }
1299  }
1300 }
1301 
1302 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1303 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
1304  struct ExtPoint {
1305  ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
1306  : MO(O), RegIdx(R), Next(N) {}
1307 
1308  MachineOperand MO;
1309  unsigned RegIdx;
1310  SlotIndex Next;
1311  };
1312 
1313  SmallVector<ExtPoint,4> ExtPoints;
1314 
1315  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
1316  RE = MRI.reg_end(); RI != RE;) {
1317  MachineOperand &MO = *RI;
1318  MachineInstr *MI = MO.getParent();
1319  ++RI;
1320  // LiveDebugVariables should have handled all DBG_VALUE instructions.
1321  if (MI->isDebugValue()) {
1322  LLVM_DEBUG(dbgs() << "Zapping " << *MI);
1323  MO.setReg(0);
1324  continue;
1325  }
1326 
1327  // <undef> operands don't really read the register, so it doesn't matter
1328  // which register we choose. When the use operand is tied to a def, we must
1329  // use the same register as the def, so just do that always.
1330  SlotIndex Idx = LIS.getInstructionIndex(*MI);
1331  if (MO.isDef() || MO.isUndef())
1332  Idx = Idx.getRegSlot(MO.isEarlyClobber());
1333 
1334  // Rewrite to the mapped register at Idx.
1335  unsigned RegIdx = RegAssign.lookup(Idx);
1336  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1337  MO.setReg(LI.reg);
1338  LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent())
1339  << '\t' << Idx << ':' << RegIdx << '\t' << *MI);
1340 
1341  // Extend liveness to Idx if the instruction reads reg.
1342  if (!ExtendRanges || MO.isUndef())
1343  continue;
1344 
1345  // Skip instructions that don't read Reg.
1346  if (MO.isDef()) {
1347  if (!MO.getSubReg() && !MO.isEarlyClobber())
1348  continue;
1349  // We may want to extend a live range for a partial redef, or for a use
1350  // tied to an early clobber.
1351  Idx = Idx.getPrevSlot();
1352  if (!Edit->getParent().liveAt(Idx))
1353  continue;
1354  } else
1355  Idx = Idx.getRegSlot(true);
1356 
1357  SlotIndex Next = Idx.getNextSlot();
1358  if (LI.hasSubRanges()) {
1359  // We have to delay extending subranges until we have seen all operands
1360  // defining the register. This is because a <def,read-undef> operand
1361  // will create an "undef" point, and we cannot extend any subranges
1362  // until all of them have been accounted for.
1363  if (MO.isUse())
1364  ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1365  } else {
1366  LiveRangeCalc &LRC = getLRCalc(RegIdx);
1367  LRC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
1368  }
1369  }
1370 
1371  for (ExtPoint &EP : ExtPoints) {
1372  LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
1373  assert(LI.hasSubRanges());
1374 
1375  LiveRangeCalc SubLRC;
1376  unsigned Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1377  LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
1378  : MRI.getMaxLaneMaskForVReg(Reg);
1379  for (LiveInterval::SubRange &S : LI.subranges()) {
1380  if ((S.LaneMask & LM).none())
1381  continue;
1382  // The problem here can be that the new register may have been created
1383  // for a partially defined original register. For example:
1384  // %0:subreg_hireg<def,read-undef> = ...
1385  // ...
1386  // %1 = COPY %0
1387  if (S.empty())
1388  continue;
1389  SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1390  &LIS.getVNInfoAllocator());
1392  LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
1393  SubLRC.extend(S, EP.Next, 0, Undefs);
1394  }
1395  }
1396 
1397  for (unsigned R : *Edit) {
1398  LiveInterval &LI = LIS.getInterval(R);
1399  if (!LI.hasSubRanges())
1400  continue;
1401  LI.clear();
1402  LI.removeEmptySubRanges();
1403  LIS.constructMainRangeFromSubranges(LI);
1404  }
1405 }
1406 
1407 void SplitEditor::deleteRematVictims() {
1409  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
1410  LiveInterval *LI = &LIS.getInterval(*I);
1411  for (const LiveRange::Segment &S : LI->segments) {
1412  // Dead defs end at the dead slot.
1413  if (S.end != S.valno->def.getDeadSlot())
1414  continue;
1415  if (S.valno->isPHIDef())
1416  continue;
1417  MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1418  assert(MI && "Missing instruction for dead def");
1419  MI->addRegisterDead(LI->reg, &TRI);
1420 
1421  if (!MI->allDefsAreDead())
1422  continue;
1423 
1424  LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
1425  Dead.push_back(MI);
1426  }
1427  }
1428 
1429  if (Dead.empty())
1430  return;
1431 
1432  Edit->eliminateDeadDefs(Dead, None, &AA);
1433 }
1434 
1435 void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {
1436  // Fast-path for common case.
1437  if (!ParentVNI.isPHIDef()) {
1438  for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1439  forceRecompute(I, ParentVNI);
1440  return;
1441  }
1442 
1443  // Trace value through phis.
1444  SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist.
1446  Visited.insert(&ParentVNI);
1447  WorkList.push_back(&ParentVNI);
1448 
1449  const LiveInterval &ParentLI = Edit->getParent();
1450  const SlotIndexes &Indexes = *LIS.getSlotIndexes();
1451  do {
1452  const VNInfo &VNI = *WorkList.back();
1453  WorkList.pop_back();
1454  for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1455  forceRecompute(I, VNI);
1456  if (!VNI.isPHIDef())
1457  continue;
1458 
1459  MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);
1460  for (const MachineBasicBlock *Pred : MBB.predecessors()) {
1461  SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
1462  VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);
1463  assert(PredVNI && "Value available in PhiVNI predecessor");
1464  if (Visited.insert(PredVNI).second)
1465  WorkList.push_back(PredVNI);
1466  }
1467  } while(!WorkList.empty());
1468 }
1469 
1471  ++NumFinished;
1472 
1473  // At this point, the live intervals in Edit contain VNInfos corresponding to
1474  // the inserted copies.
1475 
1476  // Add the original defs from the parent interval.
1477  for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1478  if (ParentVNI->isUnused())
1479  continue;
1480  unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1481  defValue(RegIdx, ParentVNI, ParentVNI->def, true);
1482 
1483  // Force rematted values to be recomputed everywhere.
1484  // The new live ranges may be truncated.
1485  if (Edit->didRematerialize(ParentVNI))
1486  forceRecomputeVNI(*ParentVNI);
1487  }
1488 
1489  // Hoist back-copies to the complement interval when in spill mode.
1490  switch (SpillMode) {
1491  case SM_Partition:
1492  // Leave all back-copies as is.
1493  break;
1494  case SM_Size:
1495  case SM_Speed:
1496  // hoistCopies will behave differently between size and speed.
1497  hoistCopies();
1498  }
1499 
1500  // Transfer the simply mapped values, check if any are skipped.
1501  bool Skipped = transferValues();
1502 
1503  // Rewrite virtual registers, possibly extending ranges.
1504  rewriteAssigned(Skipped);
1505 
1506  if (Skipped)
1507  extendPHIKillRanges();
1508  else
1509  ++NumSimple;
1510 
1511  // Delete defs that were rematted everywhere.
1512  if (Skipped)
1513  deleteRematVictims();
1514 
1515  // Get rid of unused values and set phi-kill flags.
1516  for (unsigned Reg : *Edit) {
1517  LiveInterval &LI = LIS.getInterval(Reg);
1518  LI.removeEmptySubRanges();
1519  LI.RenumberValues();
1520  }
1521 
1522  // Provide a reverse mapping from original indices to Edit ranges.
1523  if (LRMap) {
1524  LRMap->clear();
1525  for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1526  LRMap->push_back(i);
1527  }
1528 
1529  // Now check if any registers were separated into multiple components.
1530  ConnectedVNInfoEqClasses ConEQ(LIS);
1531  for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1532  // Don't use iterators, they are invalidated by create() below.
1533  unsigned VReg = Edit->get(i);
1534  LiveInterval &LI = LIS.getInterval(VReg);
1536  LIS.splitSeparateComponents(LI, SplitLIs);
1537  unsigned Original = VRM.getOriginal(VReg);
1538  for (LiveInterval *SplitLI : SplitLIs)
1539  VRM.setIsSplitFromReg(SplitLI->reg, Original);
1540 
1541  // The new intervals all map back to i.
1542  if (LRMap)
1543  LRMap->resize(Edit->size(), i);
1544  }
1545 
1546  // Calculate spill weight and allocation hints for new intervals.
1547  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI);
1548 
1549  assert(!LRMap || LRMap->size() == Edit->size());
1550 }
1551 
1552 //===----------------------------------------------------------------------===//
1553 // Single Block Splitting
1554 //===----------------------------------------------------------------------===//
1555 
1557  bool SingleInstrs) const {
1558  // Always split for multiple instructions.
1559  if (!BI.isOneInstr())
1560  return true;
1561  // Don't split for single instructions unless explicitly requested.
1562  if (!SingleInstrs)
1563  return false;
1564  // Splitting a live-through range always makes progress.
1565  if (BI.LiveIn && BI.LiveOut)
1566  return true;
1567  // No point in isolating a copy. It has no register class constraints.
1568  if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
1569  return false;
1570  // Finally, don't isolate an end point that was created by earlier splits.
1571  return isOriginalEndpoint(BI.FirstInstr);
1572 }
1573 
1575  openIntv();
1576  SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
1577  SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
1578  LastSplitPoint));
1579  if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1580  useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1581  } else {
1582  // The last use is after the last valid split point.
1583  SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1584  useIntv(SegStart, SegStop);
1585  overlapIntv(SegStop, BI.LastInstr);
1586  }
1587 }
1588 
1589 //===----------------------------------------------------------------------===//
1590 // Global Live Range Splitting Support
1591 //===----------------------------------------------------------------------===//
1592 
1593 // These methods support a method of global live range splitting that uses a
1594 // global algorithm to decide intervals for CFG edges. They will insert split
1595 // points and color intervals in basic blocks while avoiding interference.
1596 //
1597 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1598 // are on the stack.
1599 
1601  unsigned IntvIn, SlotIndex LeaveBefore,
1602  unsigned IntvOut, SlotIndex EnterAfter){
1603  SlotIndex Start, Stop;
1604  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1605 
1606  LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop
1607  << ") intf " << LeaveBefore << '-' << EnterAfter
1608  << ", live-through " << IntvIn << " -> " << IntvOut);
1609 
1610  assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1611 
1612  assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1613  assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1614  assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1615 
1616  MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
1617 
1618  if (!IntvOut) {
1619  LLVM_DEBUG(dbgs() << ", spill on entry.\n");
1620  //
1621  // <<<<<<<<< Possible LeaveBefore interference.
1622  // |-----------| Live through.
1623  // -____________ Spill on entry.
1624  //
1625  selectIntv(IntvIn);
1626  SlotIndex Idx = leaveIntvAtTop(*MBB);
1627  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1628  (void)Idx;
1629  return;
1630  }
1631 
1632  if (!IntvIn) {
1633  LLVM_DEBUG(dbgs() << ", reload on exit.\n");
1634  //
1635  // >>>>>>> Possible EnterAfter interference.
1636  // |-----------| Live through.
1637  // ___________-- Reload on exit.
1638  //
1639  selectIntv(IntvOut);
1640  SlotIndex Idx = enterIntvAtEnd(*MBB);
1641  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1642  (void)Idx;
1643  return;
1644  }
1645 
1646  if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1647  LLVM_DEBUG(dbgs() << ", straight through.\n");
1648  //
1649  // |-----------| Live through.
1650  // ------------- Straight through, same intv, no interference.
1651  //
1652  selectIntv(IntvOut);
1653  useIntv(Start, Stop);
1654  return;
1655  }
1656 
1657  // We cannot legally insert splits after LSP.
1658  SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1659  assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1660 
1661  if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1662  LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1663  LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");
1664  //
1665  // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference.
1666  // |-----------| Live through.
1667  // ------======= Switch intervals between interference.
1668  //
1669  selectIntv(IntvOut);
1670  SlotIndex Idx;
1671  if (LeaveBefore && LeaveBefore < LSP) {
1672  Idx = enterIntvBefore(LeaveBefore);
1673  useIntv(Idx, Stop);
1674  } else {
1675  Idx = enterIntvAtEnd(*MBB);
1676  }
1677  selectIntv(IntvIn);
1678  useIntv(Start, Idx);
1679  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1680  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1681  return;
1682  }
1683 
1684  LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");
1685  //
1686  // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference.
1687  // |-----------| Live through.
1688  // ==---------== Switch intervals before/after interference.
1689  //
1690  assert(LeaveBefore <= EnterAfter && "Missed case");
1691 
1692  selectIntv(IntvOut);
1693  SlotIndex Idx = enterIntvAfter(EnterAfter);
1694  useIntv(Idx, Stop);
1695  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1696 
1697  selectIntv(IntvIn);
1698  Idx = leaveIntvBefore(LeaveBefore);
1699  useIntv(Start, Idx);
1700  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1701 }
1702 
1704  unsigned IntvIn, SlotIndex LeaveBefore) {
1705  SlotIndex Start, Stop;
1706  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1707 
1708  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1709  << Stop << "), uses " << BI.FirstInstr << '-'
1710  << BI.LastInstr << ", reg-in " << IntvIn
1711  << ", leave before " << LeaveBefore
1712  << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1713 
1714  assert(IntvIn && "Must have register in");
1715  assert(BI.LiveIn && "Must be live-in");
1716  assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1717 
1718  if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1719  LLVM_DEBUG(dbgs() << " before interference.\n");
1720  //
1721  // <<< Interference after kill.
1722  // |---o---x | Killed in block.
1723  // ========= Use IntvIn everywhere.
1724  //
1725  selectIntv(IntvIn);
1726  useIntv(Start, BI.LastInstr);
1727  return;
1728  }
1729 
1730  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1731 
1732  if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1733  //
1734  // <<< Possible interference after last use.
1735  // |---o---o---| Live-out on stack.
1736  // =========____ Leave IntvIn after last use.
1737  //
1738  // < Interference after last use.
1739  // |---o---o--o| Live-out on stack, late last use.
1740  // ============ Copy to stack after LSP, overlap IntvIn.
1741  // \_____ Stack interval is live-out.
1742  //
1743  if (BI.LastInstr < LSP) {
1744  LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");
1745  selectIntv(IntvIn);
1747  useIntv(Start, Idx);
1748  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1749  } else {
1750  LLVM_DEBUG(dbgs() << ", spill before last split point.\n");
1751  selectIntv(IntvIn);
1752  SlotIndex Idx = leaveIntvBefore(LSP);
1753  overlapIntv(Idx, BI.LastInstr);
1754  useIntv(Start, Idx);
1755  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1756  }
1757  return;
1758  }
1759 
1760  // The interference is overlapping somewhere we wanted to use IntvIn. That
1761  // means we need to create a local interval that can be allocated a
1762  // different register.
1763  unsigned LocalIntv = openIntv();
1764  (void)LocalIntv;
1765  LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1766 
1767  if (!BI.LiveOut || BI.LastInstr < LSP) {
1768  //
1769  // <<<<<<< Interference overlapping uses.
1770  // |---o---o---| Live-out on stack.
1771  // =====----____ Leave IntvIn before interference, then spill.
1772  //
1774  SlotIndex From = enterIntvBefore(LeaveBefore);
1775  useIntv(From, To);
1776  selectIntv(IntvIn);
1777  useIntv(Start, From);
1778  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1779  return;
1780  }
1781 
1782  // <<<<<<< Interference overlapping uses.
1783  // |---o---o--o| Live-out on stack, late last use.
1784  // =====------- Copy to stack before LSP, overlap LocalIntv.
1785  // \_____ Stack interval is live-out.
1786  //
1787  SlotIndex To = leaveIntvBefore(LSP);
1788  overlapIntv(To, BI.LastInstr);
1789  SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1790  useIntv(From, To);
1791  selectIntv(IntvIn);
1792  useIntv(Start, From);
1793  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1794 }
1795 
1797  unsigned IntvOut, SlotIndex EnterAfter) {
1798  SlotIndex Start, Stop;
1799  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1800 
1801  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1802  << Stop << "), uses " << BI.FirstInstr << '-'
1803  << BI.LastInstr << ", reg-out " << IntvOut
1804  << ", enter after " << EnterAfter
1805  << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1806 
1807  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1808 
1809  assert(IntvOut && "Must have register out");
1810  assert(BI.LiveOut && "Must be live-out");
1811  assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1812 
1813  if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1814  LLVM_DEBUG(dbgs() << " after interference.\n");
1815  //
1816  // >>>> Interference before def.
1817  // | o---o---| Defined in block.
1818  // ========= Use IntvOut everywhere.
1819  //
1820  selectIntv(IntvOut);
1821  useIntv(BI.FirstInstr, Stop);
1822  return;
1823  }
1824 
1825  if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1826  LLVM_DEBUG(dbgs() << ", reload after interference.\n");
1827  //
1828  // >>>> Interference before def.
1829  // |---o---o---| Live-through, stack-in.
1830  // ____========= Enter IntvOut before first use.
1831  //
1832  selectIntv(IntvOut);
1833  SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1834  useIntv(Idx, Stop);
1835  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1836  return;
1837  }
1838 
1839  // The interference is overlapping somewhere we wanted to use IntvOut. That
1840  // means we need to create a local interval that can be allocated a
1841  // different register.
1842  LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");
1843  //
1844  // >>>>>>> Interference overlapping uses.
1845  // |---o---o---| Live-through, stack-in.
1846  // ____---====== Create local interval for interference range.
1847  //
1848  selectIntv(IntvOut);
1849  SlotIndex Idx = enterIntvAfter(EnterAfter);
1850  useIntv(Idx, Stop);
1851  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1852 
1853  openIntv();
1854  SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
1855  useIntv(From, Idx);
1856 }
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:250
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:328
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:452
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:137
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:162
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 Reg
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:152
unsigned const TargetRegisterInfo * TRI
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:727
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:1703
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:1574
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:922
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:827
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:674
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
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:533
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:1470
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:140
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:826
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
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
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:140
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:973
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
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
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:383
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.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:497
void selectIntv(unsigned Idx)
selectIntv - Select a previously opened interval index.
Definition: SplitKit.cpp:685
#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:1796
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
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1032
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:849
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:861
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:133
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:1556
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:479
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:156
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:157
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:1600
InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum)
Definition: SplitKit.cpp:72
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:62
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:459
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:692
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:1230
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.
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:709
#define LLVM_DEBUG(X)
Definition: Debug.h:119
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:352