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