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