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