LLVM  16.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.
353  : SA(SA), LIS(LIS), VRM(VRM), MRI(VRM.getMachineFunction().getRegInfo()),
354  MDT(MDT), TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),
355  TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),
356  MBFI(MBFI), VRAI(VRAI), RegAssign(Allocator) {}
357 
359  Edit = &LRE;
360  SpillMode = SM;
361  OpenIdx = 0;
362  RegAssign.clear();
363  Values.clear();
364 
365  // Reset the LiveIntervalCalc instances needed for this spill mode.
366  LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
367  &LIS.getVNInfoAllocator());
368  if (SpillMode)
369  LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
370  &LIS.getVNInfoAllocator());
371 
372  Edit->anyRematerializable();
373 }
374 
375 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
377  if (RegAssign.empty()) {
378  dbgs() << " empty\n";
379  return;
380  }
381 
382  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
383  dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
384  dbgs() << '\n';
385 }
386 #endif
387 
388 /// Find a subrange corresponding to the exact lane mask @p LM in the live
389 /// interval @p LI. The interval @p LI is assumed to contain such a subrange.
390 /// This function is used to find corresponding subranges between the
391 /// original interval and the new intervals.
392 template <typename T> auto &getSubrangeImpl(LaneBitmask LM, T &LI) {
393  for (auto &S : LI.subranges())
394  if (S.LaneMask == LM)
395  return S;
396  llvm_unreachable("SubRange for this mask not found");
397 }
398 
400  LiveInterval &LI) {
401  return getSubrangeImpl(LM, LI);
402 }
403 
405  const LiveInterval &LI) {
406  return getSubrangeImpl(LM, LI);
407 }
408 
409 /// Find a subrange corresponding to the lane mask @p LM, or a superset of it,
410 /// in the live interval @p LI. The interval @p LI is assumed to contain such
411 /// a subrange. This function is used to find corresponding subranges between
412 /// the original interval and the new intervals.
414  const LiveInterval &LI) {
415  for (const LiveInterval::SubRange &S : LI.subranges())
416  if ((S.LaneMask & LM) == LM)
417  return S;
418  llvm_unreachable("SubRange for this mask not found");
419 }
420 
421 void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
422  if (!LI.hasSubRanges()) {
423  LI.createDeadDef(VNI);
424  return;
425  }
426 
427  SlotIndex Def = VNI->def;
428  if (Original) {
429  // If we are transferring a def from the original interval, make sure
430  // to only update the subranges for which the original subranges had
431  // a def at this location.
432  for (LiveInterval::SubRange &S : LI.subranges()) {
433  auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
434  VNInfo *PV = PS.getVNInfoAt(Def);
435  if (PV != nullptr && PV->def == Def)
436  S.createDeadDef(Def, LIS.getVNInfoAllocator());
437  }
438  } else {
439  // This is a new def: either from rematerialization, or from an inserted
440  // copy. Since rematerialization can regenerate a definition of a sub-
441  // register, we need to check which subranges need to be updated.
443  assert(DefMI != nullptr);
444  LaneBitmask LM;
445  for (const MachineOperand &DefOp : DefMI->defs()) {
446  Register R = DefOp.getReg();
447  if (R != LI.reg())
448  continue;
449  if (unsigned SR = DefOp.getSubReg())
450  LM |= TRI.getSubRegIndexLaneMask(SR);
451  else {
452  LM = MRI.getMaxLaneMaskForVReg(R);
453  break;
454  }
455  }
456  for (LiveInterval::SubRange &S : LI.subranges())
457  if ((S.LaneMask & LM).any())
458  S.createDeadDef(Def, LIS.getVNInfoAllocator());
459  }
460 }
461 
462 VNInfo *SplitEditor::defValue(unsigned RegIdx,
463  const VNInfo *ParentVNI,
464  SlotIndex Idx,
465  bool Original) {
466  assert(ParentVNI && "Mapping NULL value");
467  assert(Idx.isValid() && "Invalid SlotIndex");
468  assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
469  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
470 
471  // Create a new value.
472  VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
473 
474  bool Force = LI->hasSubRanges();
475  ValueForcePair FP(Force ? nullptr : VNI, Force);
476  // Use insert for lookup, so we can add missing values with a second lookup.
477  std::pair<ValueMap::iterator, bool> InsP =
478  Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));
479 
480  // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
481  // forced. Keep it as a simple def without any liveness.
482  if (!Force && InsP.second)
483  return VNI;
484 
485  // If the previous value was a simple mapping, add liveness for it now.
486  if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
487  addDeadDef(*LI, OldVNI, Original);
488 
489  // No longer a simple mapping. Switch to a complex mapping. If the
490  // interval has subranges, make it a forced mapping.
491  InsP.first->second = ValueForcePair(nullptr, Force);
492  }
493 
494  // This is a complex mapping, add liveness for VNI
495  addDeadDef(*LI, VNI, Original);
496  return VNI;
497 }
498 
499 void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {
500  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];
501  VNInfo *VNI = VFP.getPointer();
502 
503  // ParentVNI was either unmapped or already complex mapped. Either way, just
504  // set the force bit.
505  if (!VNI) {
506  VFP.setInt(true);
507  return;
508  }
509 
510  // This was previously a single mapping. Make sure the old def is represented
511  // by a trivial live range.
512  addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
513 
514  // Mark as complex mapped, forced.
515  VFP = ValueForcePair(nullptr, true);
516 }
517 
518 SlotIndex SplitEditor::buildSingleSubRegCopy(Register FromReg, Register ToReg,
520  unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) {
521  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
522  bool FirstCopy = !Def.isValid();
523  MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)
524  .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)
525  | getInternalReadRegState(!FirstCopy), SubIdx)
526  .addReg(FromReg, 0, SubIdx);
527 
528  SlotIndexes &Indexes = *LIS.getSlotIndexes();
529  if (FirstCopy) {
530  Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
531  } else {
532  CopyMI->bundleWithPred();
533  }
534  return Def;
535 }
536 
537 SlotIndex SplitEditor::buildCopy(Register FromReg, Register ToReg,
538  LaneBitmask LaneMask, MachineBasicBlock &MBB,
539  MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {
540  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
541  SlotIndexes &Indexes = *LIS.getSlotIndexes();
542  if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {
543  // The full vreg is copied.
544  MachineInstr *CopyMI =
545  BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg);
546  return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
547  }
548 
549  // Only a subset of lanes needs to be copied. The following is a simple
550  // heuristic to construct a sequence of COPYs. We could add a target
551  // specific callback if this turns out to be suboptimal.
552  LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));
553 
554  // First pass: Try to find a perfectly matching subregister index. If none
555  // exists find the one covering the most lanemask bits.
556  const TargetRegisterClass *RC = MRI.getRegClass(FromReg);
557  assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");
558 
559  SmallVector<unsigned, 8> SubIndexes;
560 
561  // Abort if we cannot possibly implement the COPY with the given indexes.
562  if (!TRI.getCoveringSubRegIndexes(MRI, RC, LaneMask, SubIndexes))
563  report_fatal_error("Impossible to implement partial COPY");
564 
565  SlotIndex Def;
566  for (unsigned BestIdx : SubIndexes) {
567  Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,
568  DestLI, Late, Def);
569  }
570 
571  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
572  DestLI.refineSubRanges(
573  Allocator, LaneMask,
574  [Def, &Allocator](LiveInterval::SubRange &SR) {
575  SR.createDeadDef(Def, Allocator);
576  },
577  Indexes, TRI);
578 
579  return Def;
580 }
581 
582 VNInfo *SplitEditor::defFromParent(unsigned RegIdx, const VNInfo *ParentVNI,
585  SlotIndex Def;
586  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
587 
588  // We may be trying to avoid interference that ends at a deleted instruction,
589  // so always begin RegIdx 0 early and all others late.
590  bool Late = RegIdx != 0;
591 
592  // Attempt cheap-as-a-copy rematerialization.
593  unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
594  LiveInterval &OrigLI = LIS.getInterval(Original);
595  VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
596 
597  Register Reg = LI->reg();
598  bool DidRemat = false;
599  if (OrigVNI) {
600  LiveRangeEdit::Remat RM(ParentVNI);
601  RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
602  if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
603  Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);
604  ++NumRemats;
605  DidRemat = true;
606  }
607  }
608  if (!DidRemat) {
609  LaneBitmask LaneMask;
610  if (OrigLI.hasSubRanges()) {
611  LaneMask = LaneBitmask::getNone();
612  for (LiveInterval::SubRange &S : OrigLI.subranges()) {
613  if (S.liveAt(UseIdx))
614  LaneMask |= S.LaneMask;
615  }
616  } else {
617  LaneMask = LaneBitmask::getAll();
618  }
619 
620  if (LaneMask.none()) {
621  const MCInstrDesc &Desc = TII.get(TargetOpcode::IMPLICIT_DEF);
622  MachineInstr *ImplicitDef = BuildMI(MBB, I, DebugLoc(), Desc, Reg);
623  SlotIndexes &Indexes = *LIS.getSlotIndexes();
624  Def = Indexes.insertMachineInstrInMaps(*ImplicitDef, Late).getRegSlot();
625  } else {
626  ++NumCopies;
627  Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);
628  }
629  }
630 
631  // Define the value in Reg.
632  return defValue(RegIdx, ParentVNI, Def, false);
633 }
634 
635 /// Create a new virtual register and live interval.
637  // Create the complement as index 0.
638  if (Edit->empty())
639  Edit->createEmptyInterval();
640 
641  // Create the open interval.
642  OpenIdx = Edit->size();
643  Edit->createEmptyInterval();
644  return OpenIdx;
645 }
646 
647 void SplitEditor::selectIntv(unsigned Idx) {
648  assert(Idx != 0 && "Cannot select the complement interval");
649  assert(Idx < Edit->size() && "Can only select previously opened interval");
650  LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n');
651  OpenIdx = Idx;
652 }
653 
655  assert(OpenIdx && "openIntv not called before enterIntvBefore");
656  LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx);
657  Idx = Idx.getBaseIndex();
658  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
659  if (!ParentVNI) {
660  LLVM_DEBUG(dbgs() << ": not live\n");
661  return Idx;
662  }
663  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
665  assert(MI && "enterIntvBefore called with invalid index");
666 
667  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
668  return VNI->def;
669 }
670 
672  assert(OpenIdx && "openIntv not called before enterIntvAfter");
673  LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx);
674  Idx = Idx.getBoundaryIndex();
675  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
676  if (!ParentVNI) {
677  LLVM_DEBUG(dbgs() << ": not live\n");
678  return Idx;
679  }
680  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
682  assert(MI && "enterIntvAfter called with invalid index");
683 
684  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
685  std::next(MachineBasicBlock::iterator(MI)));
686  return VNI->def;
687 }
688 
690  assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
691  SlotIndex End = LIS.getMBBEndIdx(&MBB);
692  SlotIndex Last = End.getPrevSlot();
693  LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB) << ", "
694  << Last);
695  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
696  if (!ParentVNI) {
697  LLVM_DEBUG(dbgs() << ": not live\n");
698  return End;
699  }
700  SlotIndex LSP = SA.getLastSplitPoint(&MBB);
701  if (LSP < Last) {
702  // It could be that the use after LSP is a def, and thus the ParentVNI
703  // just selected starts at that def. For this case to exist, the def
704  // must be part of a tied def/use pair (as otherwise we'd have split
705  // distinct live ranges into individual live intervals), and thus we
706  // can insert the def into the VNI of the use and the tied def/use
707  // pair can live in the resulting interval.
708  Last = LSP;
709  ParentVNI = Edit->getParent().getVNInfoAt(Last);
710  if (!ParentVNI) {
711  // undef use --> undef tied def
712  LLVM_DEBUG(dbgs() << ": tied use not live\n");
713  return End;
714  }
715  }
716 
717  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id);
718  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
720  RegAssign.insert(VNI->def, End, OpenIdx);
721  LLVM_DEBUG(dump());
722  return VNI->def;
723 }
724 
725 /// useIntv - indicate that all instructions in MBB should use OpenLI.
727  useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
728 }
729 
731  assert(OpenIdx && "openIntv not called before useIntv");
732  LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
733  RegAssign.insert(Start, End, OpenIdx);
734  LLVM_DEBUG(dump());
735 }
736 
738  assert(OpenIdx && "openIntv not called before leaveIntvAfter");
739  LLVM_DEBUG(dbgs() << " leaveIntvAfter " << Idx);
740 
741  // The interval must be live beyond the instruction at Idx.
742  SlotIndex Boundary = Idx.getBoundaryIndex();
743  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
744  if (!ParentVNI) {
745  LLVM_DEBUG(dbgs() << ": not live\n");
746  return Boundary.getNextSlot();
747  }
748  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
749  MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
750  assert(MI && "No instruction at index");
751 
752  // In spill mode, make live ranges as short as possible by inserting the copy
753  // before MI. This is only possible if that instruction doesn't redefine the
754  // value. The inserted COPY is not a kill, and we don't need to recompute
755  // the source live range. The spiller also won't try to hoist this copy.
756  if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
757  MI->readsVirtualRegister(Edit->getReg())) {
758  forceRecompute(0, *ParentVNI);
759  defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
760  return Idx;
761  }
762 
763  VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
764  std::next(MachineBasicBlock::iterator(MI)));
765  return VNI->def;
766 }
767 
769  assert(OpenIdx && "openIntv not called before leaveIntvBefore");
770  LLVM_DEBUG(dbgs() << " leaveIntvBefore " << Idx);
771 
772  // The interval must be live into the instruction at Idx.
773  Idx = Idx.getBaseIndex();
774  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
775  if (!ParentVNI) {
776  LLVM_DEBUG(dbgs() << ": not live\n");
777  return Idx.getNextSlot();
778  }
779  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
780 
782  assert(MI && "No instruction at index");
783  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
784  return VNI->def;
785 }
786 
788  assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
789  SlotIndex Start = LIS.getMBBStartIdx(&MBB);
790  LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB) << ", "
791  << Start);
792 
793  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
794  if (!ParentVNI) {
795  LLVM_DEBUG(dbgs() << ": not live\n");
796  return Start;
797  }
798 
799  VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
801  RegAssign.insert(Start, VNI->def, OpenIdx);
802  LLVM_DEBUG(dump());
803  return VNI->def;
804 }
805 
806 static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg) {
807  return any_of(MI.defs(), [Reg](const MachineOperand &MO) {
808  return MO.isReg() && MO.isTied() && MO.getReg() == Reg;
809  });
810 }
811 
813  assert(OpenIdx && "openIntv not called before overlapIntv");
814  const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
815  assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
816  "Parent changes value in extended range");
817  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
818  "Range cannot span basic blocks");
819 
820  // The complement interval will be extended as needed by LICalc.extend().
821  if (ParentVNI)
822  forceRecompute(0, *ParentVNI);
823 
824  // If the last use is tied to a def, we can't mark it as live for the
825  // interval which includes only the use. That would cause the tied pair
826  // to end up in two different intervals.
827  if (auto *MI = LIS.getInstructionFromIndex(End))
828  if (hasTiedUseOf(*MI, Edit->getReg())) {
829  LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n");
830  return;
831  }
832 
833  LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
834  RegAssign.insert(Start, End, OpenIdx);
835  LLVM_DEBUG(dump());
836 }
837 
838 //===----------------------------------------------------------------------===//
839 // Spill modes
840 //===----------------------------------------------------------------------===//
841 
842 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
843  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
844  LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
845  RegAssignMap::iterator AssignI;
846  AssignI.setMap(RegAssign);
847 
848  for (const VNInfo *C : Copies) {
849  SlotIndex Def = C->def;
851  assert(MI && "No instruction for back-copy");
852 
853  MachineBasicBlock *MBB = MI->getParent();
855  bool AtBegin;
856  do AtBegin = MBBI == MBB->begin();
857  while (!AtBegin && (--MBBI)->isDebugOrPseudoInstr());
858 
859  LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
860  LIS.removeVRegDefAt(*LI, Def);
862  MI->eraseFromParent();
863 
864  // Adjust RegAssign if a register assignment is killed at Def. We want to
865  // avoid calculating the live range of the source register if possible.
866  AssignI.find(Def.getPrevSlot());
867  if (!AssignI.valid() || AssignI.start() >= Def)
868  continue;
869  // If MI doesn't kill the assigned register, just leave it.
870  if (AssignI.stop() != Def)
871  continue;
872  unsigned RegIdx = AssignI.value();
873  // We could hoist back-copy right after another back-copy. As a result
874  // MMBI points to copy instruction which is actually dead now.
875  // We cannot set its stop to MBBI which will be the same as start and
876  // interval does not support that.
877  SlotIndex Kill =
878  AtBegin ? SlotIndex() : LIS.getInstructionIndex(*MBBI).getRegSlot();
879  if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg()) ||
880  Kill <= AssignI.start()) {
881  LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx
882  << '\n');
883  forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));
884  } else {
885  LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI);
886  AssignI.setStop(Kill);
887  }
888  }
889 }
890 
892 SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
893  MachineBasicBlock *DefMBB) {
894  if (MBB == DefMBB)
895  return MBB;
896  assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
897 
898  const MachineLoopInfo &Loops = SA.Loops;
899  const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
900  MachineDomTreeNode *DefDomNode = MDT[DefMBB];
901 
902  // Best candidate so far.
903  MachineBasicBlock *BestMBB = MBB;
904  unsigned BestDepth = std::numeric_limits<unsigned>::max();
905 
906  while (true) {
907  const MachineLoop *Loop = Loops.getLoopFor(MBB);
908 
909  // MBB isn't in a loop, it doesn't get any better. All dominators have a
910  // higher frequency by definition.
911  if (!Loop) {
912  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
913  << " dominates " << printMBBReference(*MBB)
914  << " at depth 0\n");
915  return MBB;
916  }
917 
918  // We'll never be able to exit the DefLoop.
919  if (Loop == DefLoop) {
920  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
921  << " dominates " << printMBBReference(*MBB)
922  << " in the same loop\n");
923  return MBB;
924  }
925 
926  // Least busy dominator seen so far.
927  unsigned Depth = Loop->getLoopDepth();
928  if (Depth < BestDepth) {
929  BestMBB = MBB;
930  BestDepth = Depth;
931  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
932  << " dominates " << printMBBReference(*MBB)
933  << " at depth " << Depth << '\n');
934  }
935 
936  // Leave loop by going to the immediate dominator of the loop header.
937  // This is a bigger stride than simply walking up the dominator tree.
938  MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
939 
940  // Too far up the dominator tree?
941  if (!IDom || !MDT.dominates(DefDomNode, IDom))
942  return BestMBB;
943 
944  MBB = IDom->getBlock();
945  }
946 }
947 
948 void SplitEditor::computeRedundantBackCopies(
949  DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
950  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
951  const LiveInterval *Parent = &Edit->getParent();
952  SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
953  SmallPtrSet<VNInfo *, 8> DominatedVNIs;
954 
955  // Aggregate VNIs having the same value as ParentVNI.
956  for (VNInfo *VNI : LI->valnos) {
957  if (VNI->isUnused())
958  continue;
959  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
960  EqualVNs[ParentVNI->id].insert(VNI);
961  }
962 
963  // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
964  // redundant VNIs to BackCopies.
965  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
966  const VNInfo *ParentVNI = Parent->getValNumInfo(i);
967  if (!NotToHoistSet.count(ParentVNI->id))
968  continue;
969  SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
971  for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
972  It2 = It1;
973  for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
974  if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
975  continue;
976 
977  MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
978  MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
979  if (MBB1 == MBB2) {
980  DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
981  } else if (MDT.dominates(MBB1, MBB2)) {
982  DominatedVNIs.insert(*It2);
983  } else if (MDT.dominates(MBB2, MBB1)) {
984  DominatedVNIs.insert(*It1);
985  }
986  }
987  }
988  if (!DominatedVNIs.empty()) {
989  forceRecompute(0, *ParentVNI);
990  append_range(BackCopies, DominatedVNIs);
991  DominatedVNIs.clear();
992  }
993  }
994 }
995 
996 /// For SM_Size mode, find a common dominator for all the back-copies for
997 /// the same ParentVNI and hoist the backcopies to the dominator BB.
998 /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
999 /// to do the hoisting, simply remove the dominated backcopies for the same
1000 /// ParentVNI.
1001 void SplitEditor::hoistCopies() {
1002  // Get the complement interval, always RegIdx 0.
1003  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
1004  const LiveInterval *Parent = &Edit->getParent();
1005 
1006  // Track the nearest common dominator for all back-copies for each ParentVNI,
1007  // indexed by ParentVNI->id.
1008  using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1009  SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
1010  // The total cost of all the back-copies for each ParentVNI.
1012  // The ParentVNI->id set for which hoisting back-copies are not beneficial
1013  // for Speed.
1014  DenseSet<unsigned> NotToHoistSet;
1015 
1016  // Find the nearest common dominator for parent values with multiple
1017  // back-copies. If a single back-copy dominates, put it in DomPair.second.
1018  for (VNInfo *VNI : LI->valnos) {
1019  if (VNI->isUnused())
1020  continue;
1021  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1022  assert(ParentVNI && "Parent not live at complement def");
1023 
1024  // Don't hoist remats. The complement is probably going to disappear
1025  // completely anyway.
1026  if (Edit->didRematerialize(ParentVNI))
1027  continue;
1028 
1029  MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
1030 
1031  DomPair &Dom = NearestDom[ParentVNI->id];
1032 
1033  // Keep directly defined parent values. This is either a PHI or an
1034  // instruction in the complement range. All other copies of ParentVNI
1035  // should be eliminated.
1036  if (VNI->def == ParentVNI->def) {
1037  LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
1038  Dom = DomPair(ValMBB, VNI->def);
1039  continue;
1040  }
1041  // Skip the singly mapped values. There is nothing to gain from hoisting a
1042  // single back-copy.
1043  if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
1044  LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
1045  continue;
1046  }
1047 
1048  if (!Dom.first) {
1049  // First time we see ParentVNI. VNI dominates itself.
1050  Dom = DomPair(ValMBB, VNI->def);
1051  } else if (Dom.first == ValMBB) {
1052  // Two defs in the same block. Pick the earlier def.
1053  if (!Dom.second.isValid() || VNI->def < Dom.second)
1054  Dom.second = VNI->def;
1055  } else {
1056  // Different basic blocks. Check if one dominates.
1058  MDT.findNearestCommonDominator(Dom.first, ValMBB);
1059  if (Near == ValMBB)
1060  // Def ValMBB dominates.
1061  Dom = DomPair(ValMBB, VNI->def);
1062  else if (Near != Dom.first)
1063  // None dominate. Hoist to common dominator, need new def.
1064  Dom = DomPair(Near, SlotIndex());
1065  Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
1066  }
1067 
1068  LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'
1069  << VNI->def << " for parent " << ParentVNI->id << '@'
1070  << ParentVNI->def << " hoist to "
1071  << printMBBReference(*Dom.first) << ' ' << Dom.second
1072  << '\n');
1073  }
1074 
1075  // Insert the hoisted copies.
1076  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
1077  DomPair &Dom = NearestDom[i];
1078  if (!Dom.first || Dom.second.isValid())
1079  continue;
1080  // This value needs a hoisted copy inserted at the end of Dom.first.
1081  const VNInfo *ParentVNI = Parent->getValNumInfo(i);
1082  MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
1083  // Get a less loopy dominator than Dom.first.
1084  Dom.first = findShallowDominator(Dom.first, DefMBB);
1085  if (SpillMode == SM_Speed &&
1086  MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
1087  NotToHoistSet.insert(ParentVNI->id);
1088  continue;
1089  }
1090  SlotIndex LSP = SA.getLastSplitPoint(Dom.first);
1091  if (LSP <= ParentVNI->def) {
1092  NotToHoistSet.insert(ParentVNI->id);
1093  continue;
1094  }
1095  Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first,
1096  SA.getLastSplitPointIter(Dom.first))->def;
1097  }
1098 
1099  // Remove redundant back-copies that are now known to be dominated by another
1100  // def with the same value.
1101  SmallVector<VNInfo*, 8> BackCopies;
1102  for (VNInfo *VNI : LI->valnos) {
1103  if (VNI->isUnused())
1104  continue;
1105  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1106  const DomPair &Dom = NearestDom[ParentVNI->id];
1107  if (!Dom.first || Dom.second == VNI->def ||
1108  NotToHoistSet.count(ParentVNI->id))
1109  continue;
1110  BackCopies.push_back(VNI);
1111  forceRecompute(0, *ParentVNI);
1112  }
1113 
1114  // If it is not beneficial to hoist all the BackCopies, simply remove
1115  // redundant BackCopies in speed mode.
1116  if (SpillMode == SM_Speed && !NotToHoistSet.empty())
1117  computeRedundantBackCopies(NotToHoistSet, BackCopies);
1118 
1119  removeBackCopies(BackCopies);
1120 }
1121 
1122 /// transferValues - Transfer all possible values to the new live ranges.
1123 /// Values that were rematerialized are left alone, they need LICalc.extend().
1124 bool SplitEditor::transferValues() {
1125  bool Skipped = false;
1126  RegAssignMap::const_iterator AssignI = RegAssign.begin();
1127  for (const LiveRange::Segment &S : Edit->getParent()) {
1128  LLVM_DEBUG(dbgs() << " blit " << S << ':');
1129  VNInfo *ParentVNI = S.valno;
1130  // RegAssign has holes where RegIdx 0 should be used.
1131  SlotIndex Start = S.start;
1132  AssignI.advanceTo(Start);
1133  do {
1134  unsigned RegIdx;
1135  SlotIndex End = S.end;
1136  if (!AssignI.valid()) {
1137  RegIdx = 0;
1138  } else if (AssignI.start() <= Start) {
1139  RegIdx = AssignI.value();
1140  if (AssignI.stop() < End) {
1141  End = AssignI.stop();
1142  ++AssignI;
1143  }
1144  } else {
1145  RegIdx = 0;
1146  End = std::min(End, AssignI.start());
1147  }
1148 
1149  // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1150  LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('
1151  << printReg(Edit->get(RegIdx)) << ')');
1152  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1153 
1154  // Check for a simply defined value that can be blitted directly.
1155  ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
1156  if (VNInfo *VNI = VFP.getPointer()) {
1157  LLVM_DEBUG(dbgs() << ':' << VNI->id);
1158  LI.addSegment(LiveInterval::Segment(Start, End, VNI));
1159  Start = End;
1160  continue;
1161  }
1162 
1163  // Skip values with forced recomputation.
1164  if (VFP.getInt()) {
1165  LLVM_DEBUG(dbgs() << "(recalc)");
1166  Skipped = true;
1167  Start = End;
1168  continue;
1169  }
1170 
1171  LiveIntervalCalc &LIC = getLICalc(RegIdx);
1172 
1173  // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1174  // so the live range is accurate. Add live-in blocks in [Start;End) to the
1175  // LiveInBlocks.
1177  SlotIndex BlockStart, BlockEnd;
1178  std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
1179 
1180  // The first block may be live-in, or it may have its own def.
1181  if (Start != BlockStart) {
1182  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1183  assert(VNI && "Missing def for complex mapped value");
1184  LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB));
1185  // MBB has its own def. Is it also live-out?
1186  if (BlockEnd <= End)
1187  LIC.setLiveOutValue(&*MBB, VNI);
1188 
1189  // Skip to the next block for live-in.
1190  ++MBB;
1191  BlockStart = BlockEnd;
1192  }
1193 
1194  // Handle the live-in blocks covered by [Start;End).
1195  assert(Start <= BlockStart && "Expected live-in block");
1196  while (BlockStart < End) {
1197  LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB));
1198  BlockEnd = LIS.getMBBEndIdx(&*MBB);
1199  if (BlockStart == ParentVNI->def) {
1200  // This block has the def of a parent PHI, so it isn't live-in.
1201  assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
1202  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1203  assert(VNI && "Missing def for complex mapped parent PHI");
1204  if (End >= BlockEnd)
1205  LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
1206  } else {
1207  // This block needs a live-in value. The last block covered may not
1208  // be live-out.
1209  if (End < BlockEnd)
1210  LIC.addLiveInBlock(LI, MDT[&*MBB], End);
1211  else {
1212  // Live-through, and we don't know the value.
1213  LIC.addLiveInBlock(LI, MDT[&*MBB]);
1214  LIC.setLiveOutValue(&*MBB, nullptr);
1215  }
1216  }
1217  BlockStart = BlockEnd;
1218  ++MBB;
1219  }
1220  Start = End;
1221  } while (Start != S.end);
1222  LLVM_DEBUG(dbgs() << '\n');
1223  }
1224 
1225  LICalc[0].calculateValues();
1226  if (SpillMode)
1227  LICalc[1].calculateValues();
1228 
1229  return Skipped;
1230 }
1231 
1233  const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
1234  if (Seg == nullptr)
1235  return true;
1236  if (Seg->end != Def.getDeadSlot())
1237  return false;
1238  // This is a dead PHI. Remove it.
1239  LR.removeSegment(*Seg, true);
1240  return true;
1241 }
1242 
1243 void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
1244  LiveRange &LR, LaneBitmask LM,
1245  ArrayRef<SlotIndex> Undefs) {
1246  for (MachineBasicBlock *P : B.predecessors()) {
1247  SlotIndex End = LIS.getMBBEndIdx(P);
1248  SlotIndex LastUse = End.getPrevSlot();
1249  // The predecessor may not have a live-out value. That is OK, like an
1250  // undef PHI operand.
1251  const LiveInterval &PLI = Edit->getParent();
1252  // Need the cast because the inputs to ?: would otherwise be deemed
1253  // "incompatible": SubRange vs LiveInterval.
1254  const LiveRange &PSR = !LM.all() ? getSubRangeForMaskExact(LM, PLI)
1255  : static_cast<const LiveRange &>(PLI);
1256  if (PSR.liveAt(LastUse))
1257  LIC.extend(LR, End, /*PhysReg=*/0, Undefs);
1258  }
1259 }
1260 
1261 void SplitEditor::extendPHIKillRanges() {
1262  // Extend live ranges to be live-out for successor PHI values.
1263 
1264  // Visit each PHI def slot in the parent live interval. If the def is dead,
1265  // remove it. Otherwise, extend the live interval to reach the end indexes
1266  // of all predecessor blocks.
1267 
1268  const LiveInterval &ParentLI = Edit->getParent();
1269  for (const VNInfo *V : ParentLI.valnos) {
1270  if (V->isUnused() || !V->isPHIDef())
1271  continue;
1272 
1273  unsigned RegIdx = RegAssign.lookup(V->def);
1274  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1275  LiveIntervalCalc &LIC = getLICalc(RegIdx);
1276  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1277  if (!removeDeadSegment(V->def, LI))
1278  extendPHIRange(B, LIC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
1279  }
1280 
1282  LiveIntervalCalc SubLIC;
1283 
1284  for (const LiveInterval::SubRange &PS : ParentLI.subranges()) {
1285  for (const VNInfo *V : PS.valnos) {
1286  if (V->isUnused() || !V->isPHIDef())
1287  continue;
1288  unsigned RegIdx = RegAssign.lookup(V->def);
1289  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1290  LiveInterval::SubRange &S = getSubRangeForMaskExact(PS.LaneMask, LI);
1291  if (removeDeadSegment(V->def, S))
1292  continue;
1293 
1294  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1295  SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1296  &LIS.getVNInfoAllocator());
1297  Undefs.clear();
1298  LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
1299  extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs);
1300  }
1301  }
1302 }
1303 
1304 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1305 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
1306  struct ExtPoint {
1307  ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
1308  : MO(O), RegIdx(R), Next(N) {}
1309 
1310  MachineOperand MO;
1311  unsigned RegIdx;
1312  SlotIndex Next;
1313  };
1314 
1315  SmallVector<ExtPoint,4> ExtPoints;
1316 
1317  for (MachineOperand &MO :
1319  MachineInstr *MI = MO.getParent();
1320  // LiveDebugVariables should have handled all DBG_VALUE instructions.
1321  if (MI->isDebugValue()) {
1322  LLVM_DEBUG(dbgs() << "Zapping " << *MI);
1323  MO.setReg(0);
1324  continue;
1325  }
1326 
1327  // <undef> operands don't really read the register, so it doesn't matter
1328  // which register we choose. When the use operand is tied to a def, we must
1329  // use the same register as the def, so just do that always.
1330  SlotIndex Idx = LIS.getInstructionIndex(*MI);
1331  if (MO.isDef() || MO.isUndef())
1332  Idx = Idx.getRegSlot(MO.isEarlyClobber());
1333 
1334  // Rewrite to the mapped register at Idx.
1335  unsigned RegIdx = RegAssign.lookup(Idx);
1336  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1337  MO.setReg(LI.reg());
1338  LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent())
1339  << '\t' << Idx << ':' << RegIdx << '\t' << *MI);
1340 
1341  // Extend liveness to Idx if the instruction reads reg.
1342  if (!ExtendRanges || MO.isUndef())
1343  continue;
1344 
1345  // Skip instructions that don't read Reg.
1346  if (MO.isDef()) {
1347  if (!MO.getSubReg() && !MO.isEarlyClobber())
1348  continue;
1349  // We may want to extend a live range for a partial redef, or for a use
1350  // tied to an early clobber.
1351  if (!Edit->getParent().liveAt(Idx.getPrevSlot()))
1352  continue;
1353  } else {
1354  assert(MO.isUse());
1355  bool IsEarlyClobber = false;
1356  if (MO.isTied()) {
1357  // We want to extend a live range into `e` slot rather than `r` slot if
1358  // tied-def is early clobber, because the `e` slot already contained
1359  // in the live range of early-clobber tied-def operand, give an example
1360  // here:
1361  // 0 %0 = ...
1362  // 16 early-clobber %0 = Op %0 (tied-def 0), ...
1363  // 32 ... = Op %0
1364  // Before extend:
1365  // %0 = [0r, 0d) [16e, 32d)
1366  // The point we want to extend is 0d to 16e not 16r in this case, but if
1367  // we use 16r here we will extend nothing because that already contained
1368  // in [16e, 32d).
1369  unsigned OpIdx = MI->getOperandNo(&MO);
1370  unsigned DefOpIdx = MI->findTiedOperandIdx(OpIdx);
1371  const MachineOperand &DefOp = MI->getOperand(DefOpIdx);
1372  IsEarlyClobber = DefOp.isEarlyClobber();
1373  }
1374 
1375  Idx = Idx.getRegSlot(IsEarlyClobber);
1376  }
1377 
1378  SlotIndex Next = Idx;
1379  if (LI.hasSubRanges()) {
1380  // We have to delay extending subranges until we have seen all operands
1381  // defining the register. This is because a <def,read-undef> operand
1382  // will create an "undef" point, and we cannot extend any subranges
1383  // until all of them have been accounted for.
1384  if (MO.isUse())
1385  ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1386  } else {
1387  LiveIntervalCalc &LIC = getLICalc(RegIdx);
1388  LIC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
1389  }
1390  }
1391 
1392  for (ExtPoint &EP : ExtPoints) {
1393  LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
1394  assert(LI.hasSubRanges());
1395 
1396  LiveIntervalCalc SubLIC;
1397  Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1398  LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
1400  for (LiveInterval::SubRange &S : LI.subranges()) {
1401  if ((S.LaneMask & LM).none())
1402  continue;
1403  // The problem here can be that the new register may have been created
1404  // for a partially defined original register. For example:
1405  // %0:subreg_hireg<def,read-undef> = ...
1406  // ...
1407  // %1 = COPY %0
1408  if (S.empty())
1409  continue;
1410  SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1411  &LIS.getVNInfoAllocator());
1413  LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
1414  SubLIC.extend(S, EP.Next, 0, Undefs);
1415  }
1416  }
1417 
1418  for (Register R : *Edit) {
1419  LiveInterval &LI = LIS.getInterval(R);
1420  if (!LI.hasSubRanges())
1421  continue;
1422  LI.clear();
1423  LI.removeEmptySubRanges();
1425  }
1426 }
1427 
1428 void SplitEditor::deleteRematVictims() {
1430  for (const Register &R : *Edit) {
1431  LiveInterval *LI = &LIS.getInterval(R);
1432  for (const LiveRange::Segment &S : LI->segments) {
1433  // Dead defs end at the dead slot.
1434  if (S.end != S.valno->def.getDeadSlot())
1435  continue;
1436  if (S.valno->isPHIDef())
1437  continue;
1438  MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1439  assert(MI && "Missing instruction for dead def");
1440  MI->addRegisterDead(LI->reg(), &TRI);
1441 
1442  if (!MI->allDefsAreDead())
1443  continue;
1444 
1445  LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
1446  Dead.push_back(MI);
1447  }
1448  }
1449 
1450  if (Dead.empty())
1451  return;
1452 
1453  Edit->eliminateDeadDefs(Dead, None);
1454 }
1455 
1456 void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {
1457  // Fast-path for common case.
1458  if (!ParentVNI.isPHIDef()) {
1459  for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1460  forceRecompute(I, ParentVNI);
1461  return;
1462  }
1463 
1464  // Trace value through phis.
1465  SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist.
1467  Visited.insert(&ParentVNI);
1468  WorkList.push_back(&ParentVNI);
1469 
1470  const LiveInterval &ParentLI = Edit->getParent();
1471  const SlotIndexes &Indexes = *LIS.getSlotIndexes();
1472  do {
1473  const VNInfo &VNI = *WorkList.back();
1474  WorkList.pop_back();
1475  for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1476  forceRecompute(I, VNI);
1477  if (!VNI.isPHIDef())
1478  continue;
1479 
1480  MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);
1481  for (const MachineBasicBlock *Pred : MBB.predecessors()) {
1482  SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
1483  VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);
1484  assert(PredVNI && "Value available in PhiVNI predecessor");
1485  if (Visited.insert(PredVNI).second)
1486  WorkList.push_back(PredVNI);
1487  }
1488  } while(!WorkList.empty());
1489 }
1490 
1492  ++NumFinished;
1493 
1494  // At this point, the live intervals in Edit contain VNInfos corresponding to
1495  // the inserted copies.
1496 
1497  // Add the original defs from the parent interval.
1498  for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1499  if (ParentVNI->isUnused())
1500  continue;
1501  unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1502  defValue(RegIdx, ParentVNI, ParentVNI->def, true);
1503 
1504  // Force rematted values to be recomputed everywhere.
1505  // The new live ranges may be truncated.
1506  if (Edit->didRematerialize(ParentVNI))
1507  forceRecomputeVNI(*ParentVNI);
1508  }
1509 
1510  // Hoist back-copies to the complement interval when in spill mode.
1511  switch (SpillMode) {
1512  case SM_Partition:
1513  // Leave all back-copies as is.
1514  break;
1515  case SM_Size:
1516  case SM_Speed:
1517  // hoistCopies will behave differently between size and speed.
1518  hoistCopies();
1519  }
1520 
1521  // Transfer the simply mapped values, check if any are skipped.
1522  bool Skipped = transferValues();
1523 
1524  // Rewrite virtual registers, possibly extending ranges.
1525  rewriteAssigned(Skipped);
1526 
1527  if (Skipped)
1528  extendPHIKillRanges();
1529  else
1530  ++NumSimple;
1531 
1532  // Delete defs that were rematted everywhere.
1533  if (Skipped)
1534  deleteRematVictims();
1535 
1536  // Get rid of unused values and set phi-kill flags.
1537  for (Register Reg : *Edit) {
1538  LiveInterval &LI = LIS.getInterval(Reg);
1539  LI.removeEmptySubRanges();
1540  LI.RenumberValues();
1541  }
1542 
1543  // Provide a reverse mapping from original indices to Edit ranges.
1544  if (LRMap) {
1545  auto Seq = llvm::seq<unsigned>(0, Edit->size());
1546  LRMap->assign(Seq.begin(), Seq.end());
1547  }
1548 
1549  // Now check if any registers were separated into multiple components.
1550  ConnectedVNInfoEqClasses ConEQ(LIS);
1551  for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1552  // Don't use iterators, they are invalidated by create() below.
1553  Register VReg = Edit->get(i);
1554  LiveInterval &LI = LIS.getInterval(VReg);
1556  LIS.splitSeparateComponents(LI, SplitLIs);
1557  Register Original = VRM.getOriginal(VReg);
1558  for (LiveInterval *SplitLI : SplitLIs)
1559  VRM.setIsSplitFromReg(SplitLI->reg(), Original);
1560 
1561  // The new intervals all map back to i.
1562  if (LRMap)
1563  LRMap->resize(Edit->size(), i);
1564  }
1565 
1566  // Calculate spill weight and allocation hints for new intervals.
1567  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI);
1568 
1569  assert(!LRMap || LRMap->size() == Edit->size());
1570 }
1571 
1572 //===----------------------------------------------------------------------===//
1573 // Single Block Splitting
1574 //===----------------------------------------------------------------------===//
1575 
1577  bool SingleInstrs) const {
1578  // Always split for multiple instructions.
1579  if (!BI.isOneInstr())
1580  return true;
1581  // Don't split for single instructions unless explicitly requested.
1582  if (!SingleInstrs)
1583  return false;
1584  // Splitting a live-through range always makes progress.
1585  if (BI.LiveIn && BI.LiveOut)
1586  return true;
1587  // No point in isolating a copy. It has no register class constraints.
1589  return false;
1590  // Finally, don't isolate an end point that was created by earlier splits.
1591  return isOriginalEndpoint(BI.FirstInstr);
1592 }
1593 
1595  openIntv();
1596  SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB);
1598  LastSplitPoint));
1599  if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1600  useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1601  } else {
1602  // The last use is after the last valid split point.
1603  SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1604  useIntv(SegStart, SegStop);
1605  overlapIntv(SegStop, BI.LastInstr);
1606  }
1607 }
1608 
1609 //===----------------------------------------------------------------------===//
1610 // Global Live Range Splitting Support
1611 //===----------------------------------------------------------------------===//
1612 
1613 // These methods support a method of global live range splitting that uses a
1614 // global algorithm to decide intervals for CFG edges. They will insert split
1615 // points and color intervals in basic blocks while avoiding interference.
1616 //
1617 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1618 // are on the stack.
1619 
1621  unsigned IntvIn, SlotIndex LeaveBefore,
1622  unsigned IntvOut, SlotIndex EnterAfter){
1623  SlotIndex Start, Stop;
1624  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1625 
1626  LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop
1627  << ") intf " << LeaveBefore << '-' << EnterAfter
1628  << ", live-through " << IntvIn << " -> " << IntvOut);
1629 
1630  assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1631 
1632  assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1633  assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1634  assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1635 
1637 
1638  if (!IntvOut) {
1639  LLVM_DEBUG(dbgs() << ", spill on entry.\n");
1640  //
1641  // <<<<<<<<< Possible LeaveBefore interference.
1642  // |-----------| Live through.
1643  // -____________ Spill on entry.
1644  //
1645  selectIntv(IntvIn);
1646  SlotIndex Idx = leaveIntvAtTop(*MBB);
1647  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1648  (void)Idx;
1649  return;
1650  }
1651 
1652  if (!IntvIn) {
1653  LLVM_DEBUG(dbgs() << ", reload on exit.\n");
1654  //
1655  // >>>>>>> Possible EnterAfter interference.
1656  // |-----------| Live through.
1657  // ___________-- Reload on exit.
1658  //
1659  selectIntv(IntvOut);
1660  SlotIndex Idx = enterIntvAtEnd(*MBB);
1661  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1662  (void)Idx;
1663  return;
1664  }
1665 
1666  if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1667  LLVM_DEBUG(dbgs() << ", straight through.\n");
1668  //
1669  // |-----------| Live through.
1670  // ------------- Straight through, same intv, no interference.
1671  //
1672  selectIntv(IntvOut);
1673  useIntv(Start, Stop);
1674  return;
1675  }
1676 
1677  // We cannot legally insert splits after LSP.
1678  SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1679  assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1680 
1681  if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1682  LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1683  LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");
1684  //
1685  // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference.
1686  // |-----------| Live through.
1687  // ------======= Switch intervals between interference.
1688  //
1689  selectIntv(IntvOut);
1690  SlotIndex Idx;
1691  if (LeaveBefore && LeaveBefore < LSP) {
1692  Idx = enterIntvBefore(LeaveBefore);
1693  useIntv(Idx, Stop);
1694  } else {
1695  Idx = enterIntvAtEnd(*MBB);
1696  }
1697  selectIntv(IntvIn);
1698  useIntv(Start, Idx);
1699  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1700  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1701  return;
1702  }
1703 
1704  LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");
1705  //
1706  // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference.
1707  // |-----------| Live through.
1708  // ==---------== Switch intervals before/after interference.
1709  //
1710  assert(LeaveBefore <= EnterAfter && "Missed case");
1711 
1712  selectIntv(IntvOut);
1713  SlotIndex Idx = enterIntvAfter(EnterAfter);
1714  useIntv(Idx, Stop);
1715  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1716 
1717  selectIntv(IntvIn);
1718  Idx = leaveIntvBefore(LeaveBefore);
1719  useIntv(Start, Idx);
1720  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1721 }
1722 
1724  unsigned IntvIn, SlotIndex LeaveBefore) {
1725  SlotIndex Start, Stop;
1726  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1727 
1728  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1729  << Stop << "), uses " << BI.FirstInstr << '-'
1730  << BI.LastInstr << ", reg-in " << IntvIn
1731  << ", leave before " << LeaveBefore
1732  << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1733 
1734  assert(IntvIn && "Must have register in");
1735  assert(BI.LiveIn && "Must be live-in");
1736  assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1737 
1738  if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1739  LLVM_DEBUG(dbgs() << " before interference.\n");
1740  //
1741  // <<< Interference after kill.
1742  // |---o---x | Killed in block.
1743  // ========= Use IntvIn everywhere.
1744  //
1745  selectIntv(IntvIn);
1746  useIntv(Start, BI.LastInstr);
1747  return;
1748  }
1749 
1750  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);
1751 
1752  if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1753  //
1754  // <<< Possible interference after last use.
1755  // |---o---o---| Live-out on stack.
1756  // =========____ Leave IntvIn after last use.
1757  //
1758  // < Interference after last use.
1759  // |---o---o--o| Live-out on stack, late last use.
1760  // ============ Copy to stack after LSP, overlap IntvIn.
1761  // \_____ Stack interval is live-out.
1762  //
1763  if (BI.LastInstr < LSP) {
1764  LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");
1765  selectIntv(IntvIn);
1767  useIntv(Start, Idx);
1768  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1769  } else {
1770  LLVM_DEBUG(dbgs() << ", spill before last split point.\n");
1771  selectIntv(IntvIn);
1772  SlotIndex Idx = leaveIntvBefore(LSP);
1773  overlapIntv(Idx, BI.LastInstr);
1774  useIntv(Start, Idx);
1775  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1776  }
1777  return;
1778  }
1779 
1780  // The interference is overlapping somewhere we wanted to use IntvIn. That
1781  // means we need to create a local interval that can be allocated a
1782  // different register.
1783  unsigned LocalIntv = openIntv();
1784  (void)LocalIntv;
1785  LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1786 
1787  if (!BI.LiveOut || BI.LastInstr < LSP) {
1788  //
1789  // <<<<<<< Interference overlapping uses.
1790  // |---o---o---| Live-out on stack.
1791  // =====----____ Leave IntvIn before interference, then spill.
1792  //
1794  SlotIndex From = enterIntvBefore(LeaveBefore);
1795  useIntv(From, To);
1796  selectIntv(IntvIn);
1797  useIntv(Start, From);
1798  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1799  return;
1800  }
1801 
1802  // <<<<<<< Interference overlapping uses.
1803  // |---o---o--o| Live-out on stack, late last use.
1804  // =====------- Copy to stack before LSP, overlap LocalIntv.
1805  // \_____ Stack interval is live-out.
1806  //
1807  SlotIndex To = leaveIntvBefore(LSP);
1808  overlapIntv(To, BI.LastInstr);
1809  SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1810  useIntv(From, To);
1811  selectIntv(IntvIn);
1812  useIntv(Start, From);
1813  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1814 }
1815 
1817  unsigned IntvOut, SlotIndex EnterAfter) {
1818  SlotIndex Start, Stop;
1819  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1820 
1821  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1822  << Stop << "), uses " << BI.FirstInstr << '-'
1823  << BI.LastInstr << ", reg-out " << IntvOut
1824  << ", enter after " << EnterAfter
1825  << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1826 
1827  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);
1828 
1829  assert(IntvOut && "Must have register out");
1830  assert(BI.LiveOut && "Must be live-out");
1831  assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1832 
1833  if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1834  LLVM_DEBUG(dbgs() << " after interference.\n");
1835  //
1836  // >>>> Interference before def.
1837  // | o---o---| Defined in block.
1838  // ========= Use IntvOut everywhere.
1839  //
1840  selectIntv(IntvOut);
1841  useIntv(BI.FirstInstr, Stop);
1842  return;
1843  }
1844 
1845  if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1846  LLVM_DEBUG(dbgs() << ", reload after interference.\n");
1847  //
1848  // >>>> Interference before def.
1849  // |---o---o---| Live-through, stack-in.
1850  // ____========= Enter IntvOut before first use.
1851  //
1852  selectIntv(IntvOut);
1853  SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1854  useIntv(Idx, Stop);
1855  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1856  return;
1857  }
1858 
1859  // The interference is overlapping somewhere we wanted to use IntvOut. That
1860  // means we need to create a local interval that can be allocated a
1861  // different register.
1862  LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");
1863  //
1864  // >>>>>>> Interference overlapping uses.
1865  // |---o---o---| Live-through, stack-in.
1866  // ____---====== Create local interval for interference range.
1867  //
1868  selectIntv(IntvOut);
1869  SlotIndex Idx = enterIntvAfter(EnterAfter);
1870  useIntv(Idx, Stop);
1871  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1872 
1873  openIntv();
1875  useIntv(From, Idx);
1876 }
1877 
1879  OS << "{" << printMBBReference(*MBB) << ", "
1880  << "uses " << FirstInstr << " to " << LastInstr << ", "
1881  << "1st def " << FirstDef << ", "
1882  << (LiveIn ? "live in" : "dead in") << ", "
1883  << (LiveOut ? "live out" : "dead out") << "}";
1884 }
1885 
1887  print(dbgs());
1888  dbgs() << "\n";
1889 }
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:208
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:192
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:1617
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:962
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:1594
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:460
llvm::SplitEditor::enterIntvAtEnd
SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB)
enterIntvAtEnd - Enter the open interval at the end of MBB.
Definition: SplitKit.cpp:689
llvm::SplitAnalysis::BlockInfo::LiveIn
bool LiveIn
Current reg is live in.
Definition: SplitKit.h:126
llvm::IntervalMap::clear
void clear()
clear - Remove all entries.
Definition: IntervalMap.h:1330
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
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:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::SplitAnalysis::BlockInfo::FirstInstr
SlotIndex FirstInstr
First instr accessing current reg.
Definition: SplitKit.h:123
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:1129
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:1723
llvm::SplitEditor::openIntv
unsigned openIntv()
Create a new virtual register and live interval.
Definition: SplitKit.cpp:636
llvm::LiveIntervals::getSlotIndexes
SlotIndexes * getSlotIndexes() const
Definition: LiveIntervals.h:209
llvm::LiveIntervals::isLiveInToMBB
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
Definition: LiveIntervals.h:239
llvm::SlotIndex::isValid
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:152
llvm::SplitAnalysis::BlockInfo::isOneInstr
bool isOneInstr() const
isOneInstr - Returns true when this BlockInfo describes a single instruction.
Definition: SplitKit.h:131
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:547
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:197
llvm::PseudoProbeReservedId::Last
@ Last
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::LiveRangeEdit::anyRematerializable
bool anyRematerializable()
anyRematerializable - Return true if any parent values may be rematerializable.
Definition: LiveRangeEdit.cpp:98
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:253
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:374
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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:117
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:225
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::RegState::Define
@ Define
Register definition.
Definition: MachineInstrBuilder.h:44
llvm::MachineInstr::bundleWithPred
void bundleWithPred()
Bundle this instruction with its predecessor.
Definition: MachineInstr.cpp:754
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:678
llvm::SplitAnalysis::BlockInfo
Additional information about basic blocks where the current variable is live.
Definition: SplitKit.h:121
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:799
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
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:726
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:1101
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:481
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:1723
llvm::LiveRangeEdit::getReg
Register getReg() const
Definition: LiveRangeEdit.h:147
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:125
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:229
llvm::LiveIntervals::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Definition: LiveIntervals.h:249
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:220
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
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:1576
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
llvm::getUndefRegState
unsigned getUndefRegState(bool B)
Definition: MachineInstrBuilder.h:552
llvm::SplitEditor::reset
void reset(LiveRangeEdit &, ComplementSpillMode=SM_Partition)
reset - Prepare for a new split.
Definition: SplitKit.cpp:358
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:549
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:287
llvm::SplitEditor::SplitEditor
SplitEditor(SplitAnalysis &SA, 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
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::SplitAnalysis::LIS
const LiveIntervals & LIS
Definition: SplitKit.h:100
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:101
llvm::LiveRangeEdit::get
Register get(unsigned idx) const
Definition: LiveRangeEdit.h:155
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:381
llvm::LiveIntervals::getMBBStartIdx
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
Definition: LiveIntervals.h:230
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:204
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:280
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:533
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:46
llvm::SplitAnalysis::getLastSplitPointIter
MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB)
Definition: SplitKit.h:237
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:1620
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:768
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:43
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:392
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:145
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:53
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:642
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:319
DebugLoc.h
Copies
SI Lower i1 Copies
Definition: SILowerI1Copies.cpp:397
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:1144
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:1816
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
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:654
llvm::SlotIndexes::insertMachineInstrInMaps
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:540
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::SplitAnalysis::BlockInfo::dump
void dump() const
Definition: SplitKit.cpp:1886
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::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
llvm::DenseSet< unsigned >
llvm::SlotIndex::getBaseIndex
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:246
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:812
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::LiveRange::RenumberValues
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
Definition: LiveInterval.cpp:516
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:839
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:916
llvm::SplitAnalysis::BlockInfo::LastInstr
SlotIndex LastInstr
Last instr accessing current reg.
Definition: SplitKit.h:124
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:110
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:127
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:99
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:235
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:376
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::LiveRangeEdit::createEmptyInterval
LiveInterval & createEmptyInterval()
create - Create a new register with the same class and original slot as parent.
Definition: LiveRangeEdit.h:176
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:716
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:198
hasTiedUseOf
static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg)
Definition: SplitKit.cpp:806
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:1119
llvm::MachineRegisterInfo::reg_operands
iterator_range< reg_iterator > reg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:294
llvm::LiveRangeEdit::rematerializeAt
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false, unsigned SubIdx=0, MachineInstr *ReplaceIndexMI=nullptr)
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
Definition: LiveRangeEdit.cpp:182
llvm::SmallVectorImpl::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:582
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
llvm::SplitEditor::enterIntvAfter
SlotIndex enterIntvAfter(SlotIndex Idx)
enterIntvAfter - Enter the open interval after the instruction at Idx.
Definition: SplitKit.cpp:671
llvm::MachineOperand::isEarlyClobber
bool isEarlyClobber() const
Definition: MachineOperand.h:435
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:67
llvm::SlotIndexes::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:519
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:158
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:386
llvm::SplitAnalysis::MF
const MachineFunction & MF
Definition: SplitKit.h:98
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:259
llvm::LiveIntervals::getInterval
LiveInterval & getInterval(Register Reg)
Definition: LiveIntervals.h:112
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::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
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:1690
llvm::AArch64::RM
@ RM
Definition: AArch64ISelLowering.h:487
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:239
llvm::LiveRange::createDeadDef
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
Definition: LiveInterval.cpp:355
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:1115
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:1716
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
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:292
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1988
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:274
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:122
llvm::LiveRangeEdit::empty
bool empty() const
Definition: LiveRangeEdit.h:154
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:207
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:1491
getSubRangeForMaskExact
LiveInterval::SubRange & getSubRangeForMaskExact(LaneBitmask LM, LiveInterval &LI)
Definition: SplitKit.cpp:399
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:787
llvm::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:789
llvm::LiveRangeEdit::getParent
const LiveInterval & getParent() const
Definition: LiveRangeEdit.h:142
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:495
llvm::SplitEditor::ComplementSpillMode
ComplementSpillMode
ComplementSpillMode - Select how the complement live range should be created.
Definition: SplitKit.h:275
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::MachineInstr::isCopyLike
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Definition: MachineInstr.h:1350
llvm::codeview::LabelType::Near
@ Near
llvm::SmallVectorImpl::assign
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:708
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:294
llvm::ISD::INLINEASM_BR
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Definition: ISDOpcodes.h:1028
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
llvm::LaneBitmask::all
constexpr bool all() const
Definition: LaneBitmask.h:54
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
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:1940
llvm::LiveIntervals
Definition: LiveIntervals.h:53
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:614
removeDeadSegment
static bool removeDeadSegment(SlotIndex Def, LiveRange &LR)
Definition: SplitKit.cpp:1232
llvm::LiveRange::removeSegment
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
Definition: LiveInterval.cpp:568
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:1755
llvm::SplitEditor::leaveIntvAfter
SlotIndex leaveIntvAfter(SlotIndex Idx)
leaveIntvAfter - Leave the open interval after the instruction at Idx.
Definition: SplitKit.cpp:737
llvm::SplitAnalysis::BlockInfo::print
void print(raw_ostream &OS) const
Definition: SplitKit.cpp:1878
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:229
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:357
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
MachineInstrBuilder.h
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:143
llvm::LiveRangeEdit::size
unsigned size() const
Definition: LiveRangeEdit.h:153
N
#define N
llvm::LiveIntervals::RemoveMachineInstrFromMaps
void RemoveMachineInstrFromMaps(MachineInstr &MI)
Definition: LiveIntervals.h:270
llvm::LiveIntervals::splitSeparateComponents
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
Definition: LiveIntervals.cpp:1738
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:108
llvm::IntervalMap::begin
const_iterator begin() const
Definition: IntervalMap.h:1146
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:1142
llvm::SmallVectorImpl< VNInfo * >
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
MachineOperand.h
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:50
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:222
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:555
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:413
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:647
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:1720
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:96
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
llvm::LiveIntervals::getVNInfoAllocator
VNInfo::Allocator & getVNInfoAllocator()
Definition: LiveIntervals.h:278
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