LLVM  16.0.0git
LiveIntervals.cpp
Go to the documentation of this file.
1 //===- LiveIntervals.cpp - Live Interval Analysis -------------------------===//
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 /// \file This file implements the LiveInterval analysis pass which is used
10 /// by the Linear Scan Register allocator. This pass linearizes the
11 /// basic blocks of the function in DFS order and computes live intervals for
12 /// each virtual and physical register.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/CodeGen/Passes.h"
35 #include "llvm/CodeGen/StackMaps.h"
39 #include "llvm/Config/llvm-config.h"
40 #include "llvm/IR/Statepoint.h"
41 #include "llvm/MC/LaneBitmask.h"
42 #include "llvm/MC/MCRegisterInfo.h"
43 #include "llvm/Pass.h"
45 #include "llvm/Support/Compiler.h"
46 #include "llvm/Support/Debug.h"
49 #include <algorithm>
50 #include <cassert>
51 #include <cstdint>
52 #include <iterator>
53 #include <tuple>
54 #include <utility>
55 
56 using namespace llvm;
57 
58 #define DEBUG_TYPE "regalloc"
59 
60 char LiveIntervals::ID = 0;
62 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", "Live Interval Analysis",
63  false, false)
67  "Live Interval Analysis", false, false)
68 
69 #ifndef NDEBUG
71  "precompute-phys-liveness", cl::Hidden,
72  cl::desc("Eagerly compute live intervals for all physreg units."));
73 #else
74 static bool EnablePrecomputePhysRegs = false;
75 #endif // NDEBUG
76 
77 namespace llvm {
78 
80  "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
81  cl::desc(
82  "Use segment set for the computation of the live ranges of physregs."));
83 
84 } // end namespace llvm
85 
87  AU.setPreservesCFG();
95 }
96 
99 }
100 
101 LiveIntervals::~LiveIntervals() { delete LICalc; }
102 
104  // Free the live intervals themselves.
105  for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
106  delete VirtRegIntervals[Register::index2VirtReg(i)];
107  VirtRegIntervals.clear();
108  RegMaskSlots.clear();
109  RegMaskBits.clear();
110  RegMaskBlocks.clear();
111 
112  for (LiveRange *LR : RegUnitRanges)
113  delete LR;
114  RegUnitRanges.clear();
115 
116  // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
117  VNInfoAllocator.Reset();
118 }
119 
121  MF = &fn;
122  MRI = &MF->getRegInfo();
123  TRI = MF->getSubtarget().getRegisterInfo();
124  TII = MF->getSubtarget().getInstrInfo();
125  Indexes = &getAnalysis<SlotIndexes>();
126  DomTree = &getAnalysis<MachineDominatorTree>();
127 
128  if (!LICalc)
129  LICalc = new LiveIntervalCalc();
130 
131  // Allocate space for all virtual registers.
132  VirtRegIntervals.resize(MRI->getNumVirtRegs());
133 
134  computeVirtRegs();
135  computeRegMasks();
136  computeLiveInRegUnits();
137 
139  // For stress testing, precompute live ranges of all physical register
140  // units, including reserved registers.
141  for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
142  getRegUnit(i);
143  }
144  LLVM_DEBUG(dump());
145  return false;
146 }
147 
148 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
149  OS << "********** INTERVALS **********\n";
150 
151  // Dump the regunits.
152  for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
153  if (LiveRange *LR = RegUnitRanges[Unit])
154  OS << printRegUnit(Unit, TRI) << ' ' << *LR << '\n';
155 
156  // Dump the virtregs.
157  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
159  if (hasInterval(Reg))
160  OS << getInterval(Reg) << '\n';
161  }
162 
163  OS << "RegMasks:";
164  for (SlotIndex Idx : RegMaskSlots)
165  OS << ' ' << Idx;
166  OS << '\n';
167 
168  printInstrs(OS);
169 }
170 
171 void LiveIntervals::printInstrs(raw_ostream &OS) const {
172  OS << "********** MACHINEINSTRS **********\n";
173  MF->print(OS, Indexes);
174 }
175 
176 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
177 LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
178  printInstrs(dbgs());
179 }
180 #endif
181 
182 LiveInterval *LiveIntervals::createInterval(Register reg) {
183  float Weight = Register::isPhysicalRegister(reg) ? huge_valf : 0.0F;
184  return new LiveInterval(reg, Weight);
185 }
186 
187 /// Compute the live interval of a virtual register, based on defs and uses.
188 bool LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
189  assert(LICalc && "LICalc not initialized.");
190  assert(LI.empty() && "Should only compute empty intervals.");
191  LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
192  LICalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg()));
193  return computeDeadValues(LI, nullptr);
194 }
195 
196 void LiveIntervals::computeVirtRegs() {
197  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
199  if (MRI->reg_nodbg_empty(Reg))
200  continue;
202  bool NeedSplit = computeVirtRegInterval(LI);
203  if (NeedSplit) {
205  splitSeparateComponents(LI, SplitLIs);
206  }
207  }
208 }
209 
210 void LiveIntervals::computeRegMasks() {
211  RegMaskBlocks.resize(MF->getNumBlockIDs());
212 
213  // Find all instructions with regmask operands.
214  for (const MachineBasicBlock &MBB : *MF) {
215  std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
216  RMB.first = RegMaskSlots.size();
217 
218  // Some block starts, such as EH funclets, create masks.
219  if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
220  RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
221  RegMaskBits.push_back(Mask);
222  }
223 
224  // Unwinders may clobber additional registers.
225  // FIXME: This functionality can possibly be merged into
226  // MachineBasicBlock::getBeginClobberMask().
227  if (MBB.isEHPad())
228  if (auto *Mask = TRI->getCustomEHPadPreservedMask(*MBB.getParent())) {
229  RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
230  RegMaskBits.push_back(Mask);
231  }
232 
233  for (const MachineInstr &MI : MBB) {
234  for (const MachineOperand &MO : MI.operands()) {
235  if (!MO.isRegMask())
236  continue;
237  RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
238  RegMaskBits.push_back(MO.getRegMask());
239  }
240  }
241 
242  // Some block ends, such as funclet returns, create masks. Put the mask on
243  // the last instruction of the block, because MBB slot index intervals are
244  // half-open.
245  if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
246  assert(!MBB.empty() && "empty return block?");
247  RegMaskSlots.push_back(
248  Indexes->getInstructionIndex(MBB.back()).getRegSlot());
249  RegMaskBits.push_back(Mask);
250  }
251 
252  // Compute the number of register mask instructions in this block.
253  RMB.second = RegMaskSlots.size() - RMB.first;
254  }
255 }
256 
257 //===----------------------------------------------------------------------===//
258 // Register Unit Liveness
259 //===----------------------------------------------------------------------===//
260 //
261 // Fixed interference typically comes from ABI boundaries: Function arguments
262 // and return values are passed in fixed registers, and so are exception
263 // pointers entering landing pads. Certain instructions require values to be
264 // present in specific registers. That is also represented through fixed
265 // interference.
266 //
267 
268 /// Compute the live range of a register unit, based on the uses and defs of
269 /// aliasing registers. The range should be empty, or contain only dead
270 /// phi-defs from ABI blocks.
271 void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
272  assert(LICalc && "LICalc not initialized.");
273  LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
274 
275  // The physregs aliasing Unit are the roots and their super-registers.
276  // Create all values as dead defs before extending to uses. Note that roots
277  // may share super-registers. That's OK because createDeadDefs() is
278  // idempotent. It is very rare for a register unit to have multiple roots, so
279  // uniquing super-registers is probably not worthwhile.
280  bool IsReserved = false;
281  for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
282  bool IsRootReserved = true;
283  for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
284  Super.isValid(); ++Super) {
285  MCRegister Reg = *Super;
286  if (!MRI->reg_empty(Reg))
287  LICalc->createDeadDefs(LR, Reg);
288  // A register unit is considered reserved if all its roots and all their
289  // super registers are reserved.
290  if (!MRI->isReserved(Reg))
291  IsRootReserved = false;
292  }
293  IsReserved |= IsRootReserved;
294  }
295  assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
296  "reserved computation mismatch");
297 
298  // Now extend LR to reach all uses.
299  // Ignore uses of reserved registers. We only track defs of those.
300  if (!IsReserved) {
301  for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
302  for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
303  Super.isValid(); ++Super) {
304  MCRegister Reg = *Super;
305  if (!MRI->reg_empty(Reg))
306  LICalc->extendToUses(LR, Reg);
307  }
308  }
309  }
310 
311  // Flush the segment set to the segment vector.
313  LR.flushSegmentSet();
314 }
315 
316 /// Precompute the live ranges of any register units that are live-in to an ABI
317 /// block somewhere. Register values can appear without a corresponding def when
318 /// entering the entry block or a landing pad.
319 void LiveIntervals::computeLiveInRegUnits() {
320  RegUnitRanges.resize(TRI->getNumRegUnits());
321  LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
322 
323  // Keep track of the live range sets allocated.
324  SmallVector<unsigned, 8> NewRanges;
325 
326  // Check all basic blocks for live-ins.
327  for (const MachineBasicBlock &MBB : *MF) {
328  // We only care about ABI blocks: Entry + landing pads.
329  if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
330  continue;
331 
332  // Create phi-defs at Begin for all live-in registers.
333  SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
334  LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
335  for (const auto &LI : MBB.liveins()) {
336  for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
337  unsigned Unit = *Units;
338  LiveRange *LR = RegUnitRanges[Unit];
339  if (!LR) {
340  // Use segment set to speed-up initial computation of the live range.
341  LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
342  NewRanges.push_back(Unit);
343  }
344  VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
345  (void)VNI;
346  LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
347  }
348  }
349  LLVM_DEBUG(dbgs() << '\n');
350  }
351  LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
352 
353  // Compute the 'normal' part of the ranges.
354  for (unsigned Unit : NewRanges)
355  computeRegUnitRange(*RegUnitRanges[Unit], Unit);
356 }
357 
360  for (VNInfo *VNI : VNIs) {
361  if (VNI->isUnused())
362  continue;
363  SlotIndex Def = VNI->def;
364  LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
365  }
366 }
367 
368 void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
369  ShrinkToUsesWorkList &WorkList,
370  Register Reg, LaneBitmask LaneMask) {
371  // Keep track of the PHIs that are in use.
372  SmallPtrSet<VNInfo*, 8> UsedPHIs;
373  // Blocks that have already been added to WorkList as live-out.
375 
376  auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
377  -> const LiveRange& {
378  if (M.none())
379  return I;
380  for (const LiveInterval::SubRange &SR : I.subranges()) {
381  if ((SR.LaneMask & M).any()) {
382  assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
383  return SR;
384  }
385  }
386  llvm_unreachable("Subrange for mask not found");
387  };
388 
389  const LiveInterval &LI = getInterval(Reg);
390  const LiveRange &OldRange = getSubRange(LI, LaneMask);
391 
392  // Extend intervals to reach all uses in WorkList.
393  while (!WorkList.empty()) {
394  SlotIndex Idx = WorkList.back().first;
395  VNInfo *VNI = WorkList.back().second;
396  WorkList.pop_back();
397  const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());
398  SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);
399 
400  // Extend the live range for VNI to be live at Idx.
401  if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {
402  assert(ExtVNI == VNI && "Unexpected existing value number");
403  (void)ExtVNI;
404  // Is this a PHIDef we haven't seen before?
405  if (!VNI->isPHIDef() || VNI->def != BlockStart ||
406  !UsedPHIs.insert(VNI).second)
407  continue;
408  // The PHI is live, make sure the predecessors are live-out.
409  for (const MachineBasicBlock *Pred : MBB->predecessors()) {
410  if (!LiveOut.insert(Pred).second)
411  continue;
412  SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
413  // A predecessor is not required to have a live-out value for a PHI.
414  if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
415  WorkList.push_back(std::make_pair(Stop, PVNI));
416  }
417  continue;
418  }
419 
420  // VNI is live-in to MBB.
421  LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
422  Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
423 
424  // Make sure VNI is live-out from the predecessors.
425  for (const MachineBasicBlock *Pred : MBB->predecessors()) {
426  if (!LiveOut.insert(Pred).second)
427  continue;
428  SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
429  if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {
430  assert(OldVNI == VNI && "Wrong value out of predecessor");
431  (void)OldVNI;
432  WorkList.push_back(std::make_pair(Stop, VNI));
433  } else {
434 #ifndef NDEBUG
435  // There was no old VNI. Verify that Stop is jointly dominated
436  // by <undef>s for this live range.
437  assert(LaneMask.any() &&
438  "Missing value out of predecessor for main range");
440  LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
441  assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
442  "Missing value out of predecessor for subrange");
443 #endif
444  }
445  }
446  }
447 }
448 
451  LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');
453  "Can only shrink virtual registers");
454 
455  // Shrink subregister live ranges.
456  bool NeedsCleanup = false;
457  for (LiveInterval::SubRange &S : li->subranges()) {
458  shrinkToUses(S, li->reg());
459  if (S.empty())
460  NeedsCleanup = true;
461  }
462  if (NeedsCleanup)
463  li->removeEmptySubRanges();
464 
465  // Find all the values used, including PHI kills.
466  ShrinkToUsesWorkList WorkList;
467 
468  // Visit all instructions reading li->reg().
469  Register Reg = li->reg();
470  for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
471  if (UseMI.isDebugInstr() || !UseMI.readsVirtualRegister(Reg))
472  continue;
474  LiveQueryResult LRQ = li->Query(Idx);
475  VNInfo *VNI = LRQ.valueIn();
476  if (!VNI) {
477  // This shouldn't happen: readsVirtualRegister returns true, but there is
478  // no live value. It is likely caused by a target getting <undef> flags
479  // wrong.
480  LLVM_DEBUG(
481  dbgs() << Idx << '\t' << UseMI
482  << "Warning: Instr claims to read non-existent value in "
483  << *li << '\n');
484  continue;
485  }
486  // Special case: An early-clobber tied operand reads and writes the
487  // register one slot early.
488  if (VNInfo *DefVNI = LRQ.valueDefined())
489  Idx = DefVNI->def;
490 
491  WorkList.push_back(std::make_pair(Idx, VNI));
492  }
493 
494  // Create new live ranges with only minimal live segments per def.
495  LiveRange NewLR;
496  createSegmentsForValues(NewLR, li->vnis());
497  extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
498 
499  // Move the trimmed segments back.
500  li->segments.swap(NewLR.segments);
501 
502  // Handle dead values.
503  bool CanSeparate = computeDeadValues(*li, dead);
504  LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');
505  return CanSeparate;
506 }
507 
508 bool LiveIntervals::computeDeadValues(LiveInterval &LI,
510  bool MayHaveSplitComponents = false;
511 
512  for (VNInfo *VNI : LI.valnos) {
513  if (VNI->isUnused())
514  continue;
515  SlotIndex Def = VNI->def;
517  assert(I != LI.end() && "Missing segment for VNI");
518 
519  // Is the register live before? Otherwise we may have to add a read-undef
520  // flag for subregister defs.
521  Register VReg = LI.reg();
522  if (MRI->shouldTrackSubRegLiveness(VReg)) {
523  if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
525  MI->setRegisterDefReadUndef(VReg);
526  }
527  }
528 
529  if (I->end != Def.getDeadSlot())
530  continue;
531  if (VNI->isPHIDef()) {
532  // This is a dead PHI. Remove it.
533  VNI->markUnused();
534  LI.removeSegment(I);
535  LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
536  } else {
537  // This is a dead def. Make sure the instruction knows.
539  assert(MI && "No instruction defining live value");
540  MI->addRegisterDead(LI.reg(), TRI);
541 
542  if (dead && MI->allDefsAreDead()) {
543  LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
544  dead->push_back(MI);
545  }
546  }
547  MayHaveSplitComponents = true;
548  }
549  return MayHaveSplitComponents;
550 }
551 
553  LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');
555  "Can only shrink virtual registers");
556  // Find all the values used, including PHI kills.
557  ShrinkToUsesWorkList WorkList;
558 
559  // Visit all instructions reading Reg.
560  SlotIndex LastIdx;
561  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
562  // Skip "undef" uses.
563  if (!MO.readsReg())
564  continue;
565  // Maybe the operand is for a subregister we don't care about.
566  unsigned SubReg = MO.getSubReg();
567  if (SubReg != 0) {
568  LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
569  if ((LaneMask & SR.LaneMask).none())
570  continue;
571  }
572  // We only need to visit each instruction once.
573  MachineInstr *UseMI = MO.getParent();
574  SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
575  if (Idx == LastIdx)
576  continue;
577  LastIdx = Idx;
578 
579  LiveQueryResult LRQ = SR.Query(Idx);
580  VNInfo *VNI = LRQ.valueIn();
581  // For Subranges it is possible that only undef values are left in that
582  // part of the subregister, so there is no real liverange at the use
583  if (!VNI)
584  continue;
585 
586  // Special case: An early-clobber tied operand reads and writes the
587  // register one slot early.
588  if (VNInfo *DefVNI = LRQ.valueDefined())
589  Idx = DefVNI->def;
590 
591  WorkList.push_back(std::make_pair(Idx, VNI));
592  }
593 
594  // Create a new live ranges with only minimal live segments per def.
595  LiveRange NewLR;
596  createSegmentsForValues(NewLR, SR.vnis());
597  extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
598 
599  // Move the trimmed ranges back.
600  SR.segments.swap(NewLR.segments);
601 
602  // Remove dead PHI value numbers
603  for (VNInfo *VNI : SR.valnos) {
604  if (VNI->isUnused())
605  continue;
606  const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
607  assert(Segment != nullptr && "Missing segment for VNI");
608  if (Segment->end != VNI->def.getDeadSlot())
609  continue;
610  if (VNI->isPHIDef()) {
611  // This is a dead PHI. Remove it.
612  LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def
613  << " may separate interval\n");
614  VNI->markUnused();
615  SR.removeSegment(*Segment);
616  }
617  }
618 
619  LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');
620 }
621 
623  ArrayRef<SlotIndex> Indices,
624  ArrayRef<SlotIndex> Undefs) {
625  assert(LICalc && "LICalc not initialized.");
626  LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
627  for (SlotIndex Idx : Indices)
628  LICalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
629 }
630 
632  SmallVectorImpl<SlotIndex> *EndPoints) {
633  LiveQueryResult LRQ = LR.Query(Kill);
634  VNInfo *VNI = LRQ.valueOutOrDead();
635  if (!VNI)
636  return;
637 
638  MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
639  SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
640 
641  // If VNI isn't live out from KillMBB, the value is trivially pruned.
642  if (LRQ.endPoint() < MBBEnd) {
643  LR.removeSegment(Kill, LRQ.endPoint());
644  if (EndPoints) EndPoints->push_back(LRQ.endPoint());
645  return;
646  }
647 
648  // VNI is live out of KillMBB.
649  LR.removeSegment(Kill, MBBEnd);
650  if (EndPoints) EndPoints->push_back(MBBEnd);
651 
652  // Find all blocks that are reachable from KillMBB without leaving VNI's live
653  // range. It is possible that KillMBB itself is reachable, so start a DFS
654  // from each successor.
656  VisitedTy Visited;
657  for (MachineBasicBlock *Succ : KillMBB->successors()) {
659  I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
660  I != E;) {
661  MachineBasicBlock *MBB = *I;
662 
663  // Check if VNI is live in to MBB.
664  SlotIndex MBBStart, MBBEnd;
665  std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
666  LiveQueryResult LRQ = LR.Query(MBBStart);
667  if (LRQ.valueIn() != VNI) {
668  // This block isn't part of the VNI segment. Prune the search.
669  I.skipChildren();
670  continue;
671  }
672 
673  // Prune the search if VNI is killed in MBB.
674  if (LRQ.endPoint() < MBBEnd) {
675  LR.removeSegment(MBBStart, LRQ.endPoint());
676  if (EndPoints) EndPoints->push_back(LRQ.endPoint());
677  I.skipChildren();
678  continue;
679  }
680 
681  // VNI is live through MBB.
682  LR.removeSegment(MBBStart, MBBEnd);
683  if (EndPoints) EndPoints->push_back(MBBEnd);
684  ++I;
685  }
686  }
687 }
688 
689 //===----------------------------------------------------------------------===//
690 // Register allocator hooks.
691 //
692 
694  // Keep track of regunit ranges.
696 
697  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
699  if (MRI->reg_nodbg_empty(Reg))
700  continue;
701  const LiveInterval &LI = getInterval(Reg);
702  if (LI.empty())
703  continue;
704 
705  // Target may have not allocated this yet.
706  Register PhysReg = VRM->getPhys(Reg);
707  if (!PhysReg)
708  continue;
709 
710  // Find the regunit intervals for the assigned register. They may overlap
711  // the virtual register live range, cancelling any kills.
712  RU.clear();
713  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid();
714  ++Unit) {
715  const LiveRange &RURange = getRegUnit(*Unit);
716  if (RURange.empty())
717  continue;
718  RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
719  }
720  // Every instruction that kills Reg corresponds to a segment range end
721  // point.
722  for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
723  ++RI) {
724  // A block index indicates an MBB edge.
725  if (RI->end.isBlock())
726  continue;
728  if (!MI)
729  continue;
730 
731  // Check if any of the regunits are live beyond the end of RI. That could
732  // happen when a physreg is defined as a copy of a virtreg:
733  //
734  // %eax = COPY %5
735  // FOO %5 <--- MI, cancel kill because %eax is live.
736  // BAR killed %eax
737  //
738  // There should be no kill flag on FOO when %5 is rewritten as %eax.
739  for (auto &RUP : RU) {
740  const LiveRange &RURange = *RUP.first;
741  LiveRange::const_iterator &I = RUP.second;
742  if (I == RURange.end())
743  continue;
744  I = RURange.advanceTo(I, RI->end);
745  if (I == RURange.end() || I->start >= RI->end)
746  continue;
747  // I is overlapping RI.
748  goto CancelKill;
749  }
750 
751  if (MRI->subRegLivenessEnabled()) {
752  // When reading a partial undefined value we must not add a kill flag.
753  // The regalloc might have used the undef lane for something else.
754  // Example:
755  // %1 = ... ; R32: %1
756  // %2:high16 = ... ; R64: %2
757  // = read killed %2 ; R64: %2
758  // = read %1 ; R32: %1
759  // The <kill> flag is correct for %2, but the register allocator may
760  // assign R0L to %1, and R0 to %2 because the low 32bits of R0
761  // are actually never written by %2. After assignment the <kill>
762  // flag at the read instruction is invalid.
763  LaneBitmask DefinedLanesMask;
764  if (LI.hasSubRanges()) {
765  // Compute a mask of lanes that are defined.
766  DefinedLanesMask = LaneBitmask::getNone();
767  for (const LiveInterval::SubRange &SR : LI.subranges())
768  for (const LiveRange::Segment &Segment : SR.segments) {
769  if (Segment.start >= RI->end)
770  break;
771  if (Segment.end == RI->end) {
772  DefinedLanesMask |= SR.LaneMask;
773  break;
774  }
775  }
776  } else
777  DefinedLanesMask = LaneBitmask::getAll();
778 
779  bool IsFullWrite = false;
780  for (const MachineOperand &MO : MI->operands()) {
781  if (!MO.isReg() || MO.getReg() != Reg)
782  continue;
783  if (MO.isUse()) {
784  // Reading any undefined lanes?
785  unsigned SubReg = MO.getSubReg();
787  : MRI->getMaxLaneMaskForVReg(Reg);
788  if ((UseMask & ~DefinedLanesMask).any())
789  goto CancelKill;
790  } else if (MO.getSubReg() == 0) {
791  // Writing to the full register?
792  assert(MO.isDef());
793  IsFullWrite = true;
794  }
795  }
796 
797  // If an instruction writes to a subregister, a new segment starts in
798  // the LiveInterval. But as this is only overriding part of the register
799  // adding kill-flags is not correct here after registers have been
800  // assigned.
801  if (!IsFullWrite) {
802  // Next segment has to be adjacent in the subregister write case.
803  LiveRange::const_iterator N = std::next(RI);
804  if (N != LI.end() && N->start == RI->end)
805  goto CancelKill;
806  }
807  }
808 
809  MI->addRegisterKilled(Reg, nullptr);
810  continue;
811 CancelKill:
812  MI->clearRegisterKills(Reg, nullptr);
813  }
814  }
815 }
816 
819  assert(!LI.empty() && "LiveInterval is empty.");
820 
821  // A local live range must be fully contained inside the block, meaning it is
822  // defined and killed at instructions, not at block boundaries. It is not
823  // live in or out of any block.
824  //
825  // It is technically possible to have a PHI-defined live range identical to a
826  // single block, but we are going to return false in that case.
827 
828  SlotIndex Start = LI.beginIndex();
829  if (Start.isBlock())
830  return nullptr;
831 
832  SlotIndex Stop = LI.endIndex();
833  if (Stop.isBlock())
834  return nullptr;
835 
836  // getMBBFromIndex doesn't need to search the MBB table when both indexes
837  // belong to proper instructions.
838  MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
839  MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
840  return MBB1 == MBB2 ? MBB1 : nullptr;
841 }
842 
843 bool
844 LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
845  for (const VNInfo *PHI : LI.valnos) {
846  if (PHI->isUnused() || !PHI->isPHIDef())
847  continue;
848  const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
849  // Conservatively return true instead of scanning huge predecessor lists.
850  if (PHIMBB->pred_size() > 100)
851  return true;
852  for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
853  if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
854  return true;
855  }
856  return false;
857 }
858 
859 float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
860  const MachineBlockFrequencyInfo *MBFI,
861  const MachineInstr &MI) {
862  return getSpillWeight(isDef, isUse, MBFI, MI.getParent());
863 }
864 
865 float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
866  const MachineBlockFrequencyInfo *MBFI,
867  const MachineBasicBlock *MBB) {
868  return (isDef + isUse) * MBFI->getBlockFreqRelativeToEntryBlock(MBB);
869 }
870 
874  VNInfo *VN = Interval.getNextValue(
875  SlotIndex(getInstructionIndex(startInst).getRegSlot()),
877  LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
878  getMBBEndIdx(startInst.getParent()), VN);
879  Interval.addSegment(S);
880 
881  return S;
882 }
883 
884 //===----------------------------------------------------------------------===//
885 // Register mask functions
886 //===----------------------------------------------------------------------===//
887 /// Check whether use of reg in MI is live-through. Live-through means that
888 /// the value is alive on exit from Machine instruction. The example of such
889 /// use is a deopt value in statepoint instruction.
891  if (MI->getOpcode() != TargetOpcode::STATEPOINT)
892  return false;
893  StatepointOpers SO(MI);
895  return false;
896  for (unsigned Idx = SO.getNumDeoptArgsIdx(), E = SO.getNumGCPtrIdx(); Idx < E;
897  ++Idx) {
898  const MachineOperand &MO = MI->getOperand(Idx);
899  if (MO.isReg() && MO.getReg() == Reg)
900  return true;
901  }
902  return false;
903 }
904 
906  BitVector &UsableRegs) {
907  if (LI.empty())
908  return false;
909  LiveInterval::const_iterator LiveI = LI.begin(), LiveE = LI.end();
910 
911  // Use a smaller arrays for local live ranges.
912  ArrayRef<SlotIndex> Slots;
917  } else {
918  Slots = getRegMaskSlots();
919  Bits = getRegMaskBits();
920  }
921 
922  // We are going to enumerate all the register mask slots contained in LI.
923  // Start with a binary search of RegMaskSlots to find a starting point.
924  ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);
925  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
926 
927  // No slots in range, LI begins after the last call.
928  if (SlotI == SlotE)
929  return false;
930 
931  bool Found = false;
932  // Utility to union regmasks.
933  auto unionBitMask = [&](unsigned Idx) {
934  if (!Found) {
935  // This is the first overlap. Initialize UsableRegs to all ones.
936  UsableRegs.clear();
937  UsableRegs.resize(TRI->getNumRegs(), true);
938  Found = true;
939  }
940  // Remove usable registers clobbered by this mask.
941  UsableRegs.clearBitsNotInMask(Bits[Idx]);
942  };
943  while (true) {
944  assert(*SlotI >= LiveI->start);
945  // Loop over all slots overlapping this segment.
946  while (*SlotI < LiveI->end) {
947  // *SlotI overlaps LI. Collect mask bits.
948  unionBitMask(SlotI - Slots.begin());
949  if (++SlotI == SlotE)
950  return Found;
951  }
952  // If segment ends with live-through use we need to collect its regmask.
953  if (*SlotI == LiveI->end)
954  if (MachineInstr *MI = getInstructionFromIndex(*SlotI))
955  if (hasLiveThroughUse(MI, LI.reg()))
956  unionBitMask(SlotI++ - Slots.begin());
957  // *SlotI is beyond the current LI segment.
958  // Special advance implementation to not miss next LiveI->end.
959  if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.endIndex())
960  return Found;
961  while (LiveI->end < *SlotI)
962  ++LiveI;
963  // Advance SlotI until it overlaps.
964  while (*SlotI < LiveI->start)
965  if (++SlotI == SlotE)
966  return Found;
967  }
968 }
969 
970 //===----------------------------------------------------------------------===//
971 // IntervalUpdate class.
972 //===----------------------------------------------------------------------===//
973 
974 /// Toolkit used by handleMove to trim or extend live intervals.
976 private:
977  LiveIntervals& LIS;
978  const MachineRegisterInfo& MRI;
979  const TargetRegisterInfo& TRI;
980  SlotIndex OldIdx;
981  SlotIndex NewIdx;
983  bool UpdateFlags;
984 
985 public:
987  const TargetRegisterInfo& TRI,
988  SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
989  : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
990  UpdateFlags(UpdateFlags) {}
991 
992  // FIXME: UpdateFlags is a workaround that creates live intervals for all
993  // physregs, even those that aren't needed for regalloc, in order to update
994  // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
995  // flags, and postRA passes will use a live register utility instead.
996  LiveRange *getRegUnitLI(unsigned Unit) {
997  if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
998  return &LIS.getRegUnit(Unit);
999  return LIS.getCachedRegUnit(Unit);
1000  }
1001 
1002  /// Update all live ranges touched by MI, assuming a move from OldIdx to
1003  /// NewIdx.
1005  LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "
1006  << *MI);
1007  bool hasRegMask = false;
1008  for (MachineOperand &MO : MI->operands()) {
1009  if (MO.isRegMask())
1010  hasRegMask = true;
1011  if (!MO.isReg())
1012  continue;
1013  if (MO.isUse()) {
1014  if (!MO.readsReg())
1015  continue;
1016  // Aggressively clear all kill flags.
1017  // They are reinserted by VirtRegRewriter.
1018  MO.setIsKill(false);
1019  }
1020 
1021  Register Reg = MO.getReg();
1022  if (!Reg)
1023  continue;
1025  LiveInterval &LI = LIS.getInterval(Reg);
1026  if (LI.hasSubRanges()) {
1027  unsigned SubReg = MO.getSubReg();
1030  for (LiveInterval::SubRange &S : LI.subranges()) {
1031  if ((S.LaneMask & LaneMask).none())
1032  continue;
1033  updateRange(S, Reg, S.LaneMask);
1034  }
1035  }
1036  updateRange(LI, Reg, LaneBitmask::getNone());
1037  // If main range has a hole and we are moving a subrange use across
1038  // the hole updateRange() cannot properly handle it since it only
1039  // gets the LiveRange and not the whole LiveInterval. As a result
1040  // we may end up with a main range not covering all subranges.
1041  // This is extremely rare case, so let's check and reconstruct the
1042  // main range.
1043  if (LI.hasSubRanges()) {
1044  unsigned SubReg = MO.getSubReg();
1047  for (LiveInterval::SubRange &S : LI.subranges()) {
1048  if ((S.LaneMask & LaneMask).none() || LI.covers(S))
1049  continue;
1050  LI.clear();
1052  break;
1053  }
1054  }
1055 
1056  continue;
1057  }
1058 
1059  // For physregs, only update the regunits that actually have a
1060  // precomputed live range.
1061  for (MCRegUnitIterator Units(Reg.asMCReg(), &TRI); Units.isValid();
1062  ++Units)
1063  if (LiveRange *LR = getRegUnitLI(*Units))
1064  updateRange(*LR, *Units, LaneBitmask::getNone());
1065  }
1066  if (hasRegMask)
1067  updateRegMaskSlots();
1068  }
1069 
1070 private:
1071  /// Update a single live range, assuming an instruction has been moved from
1072  /// OldIdx to NewIdx.
1073  void updateRange(LiveRange &LR, Register Reg, LaneBitmask LaneMask) {
1074  if (!Updated.insert(&LR).second)
1075  return;
1076  LLVM_DEBUG({
1077  dbgs() << " ";
1079  dbgs() << printReg(Reg);
1080  if (LaneMask.any())
1081  dbgs() << " L" << PrintLaneMask(LaneMask);
1082  } else {
1083  dbgs() << printRegUnit(Reg, &TRI);
1084  }
1085  dbgs() << ":\t" << LR << '\n';
1086  });
1087  if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
1088  handleMoveDown(LR);
1089  else
1090  handleMoveUp(LR, Reg, LaneMask);
1091  LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n');
1092  LR.verify();
1093  }
1094 
1095  /// Update LR to reflect an instruction has been moved downwards from OldIdx
1096  /// to NewIdx (OldIdx < NewIdx).
1097  void handleMoveDown(LiveRange &LR) {
1098  LiveRange::iterator E = LR.end();
1099  // Segment going into OldIdx.
1100  LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1101 
1102  // No value live before or after OldIdx? Nothing to do.
1103  if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1104  return;
1105 
1106  LiveRange::iterator OldIdxOut;
1107  // Do we have a value live-in to OldIdx?
1108  if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1109  // If the live-in value already extends to NewIdx, there is nothing to do.
1110  if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
1111  return;
1112  // Aggressively remove all kill flags from the old kill point.
1113  // Kill flags shouldn't be used while live intervals exist, they will be
1114  // reinserted by VirtRegRewriter.
1115  if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
1116  for (MachineOperand &MOP : mi_bundle_ops(*KillMI))
1117  if (MOP.isReg() && MOP.isUse())
1118  MOP.setIsKill(false);
1119 
1120  // Is there a def before NewIdx which is not OldIdx?
1121  LiveRange::iterator Next = std::next(OldIdxIn);
1122  if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
1123  SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1124  // If we are here then OldIdx was just a use but not a def. We only have
1125  // to ensure liveness extends to NewIdx.
1126  LiveRange::iterator NewIdxIn =
1127  LR.advanceTo(Next, NewIdx.getBaseIndex());
1128  // Extend the segment before NewIdx if necessary.
1129  if (NewIdxIn == E ||
1130  !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
1131  LiveRange::iterator Prev = std::prev(NewIdxIn);
1132  Prev->end = NewIdx.getRegSlot();
1133  }
1134  // Extend OldIdxIn.
1135  OldIdxIn->end = Next->start;
1136  return;
1137  }
1138 
1139  // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1140  // invalid by overlapping ranges.
1141  bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1142  OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
1143  // If this was not a kill, then there was no def and we're done.
1144  if (!isKill)
1145  return;
1146 
1147  // Did we have a Def at OldIdx?
1148  OldIdxOut = Next;
1149  if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1150  return;
1151  } else {
1152  OldIdxOut = OldIdxIn;
1153  }
1154 
1155  // If we are here then there is a Definition at OldIdx. OldIdxOut points
1156  // to the segment starting there.
1157  assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1158  "No def?");
1159  VNInfo *OldIdxVNI = OldIdxOut->valno;
1160  assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1161 
1162  // If the defined value extends beyond NewIdx, just move the beginning
1163  // of the segment to NewIdx.
1164  SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1165  if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
1166  OldIdxVNI->def = NewIdxDef;
1167  OldIdxOut->start = OldIdxVNI->def;
1168  return;
1169  }
1170 
1171  // If we are here then we have a Definition at OldIdx which ends before
1172  // NewIdx.
1173 
1174  // Is there an existing Def at NewIdx?
1175  LiveRange::iterator AfterNewIdx
1176  = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
1177  bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1178  if (!OldIdxDefIsDead &&
1179  SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
1180  // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1181  VNInfo *DefVNI;
1182  if (OldIdxOut != LR.begin() &&
1183  !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
1184  OldIdxOut->start)) {
1185  // There is no gap between OldIdxOut and its predecessor anymore,
1186  // merge them.
1187  LiveRange::iterator IPrev = std::prev(OldIdxOut);
1188  DefVNI = OldIdxVNI;
1189  IPrev->end = OldIdxOut->end;
1190  } else {
1191  // The value is live in to OldIdx
1192  LiveRange::iterator INext = std::next(OldIdxOut);
1193  assert(INext != E && "Must have following segment");
1194  // We merge OldIdxOut and its successor. As we're dealing with subreg
1195  // reordering, there is always a successor to OldIdxOut in the same BB
1196  // We don't need INext->valno anymore and will reuse for the new segment
1197  // we create later.
1198  DefVNI = OldIdxVNI;
1199  INext->start = OldIdxOut->end;
1200  INext->valno->def = INext->start;
1201  }
1202  // If NewIdx is behind the last segment, extend that and append a new one.
1203  if (AfterNewIdx == E) {
1204  // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1205  // one position.
1206  // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1207  // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1208  std::copy(std::next(OldIdxOut), E, OldIdxOut);
1209  // The last segment is undefined now, reuse it for a dead def.
1210  LiveRange::iterator NewSegment = std::prev(E);
1211  *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1212  DefVNI);
1213  DefVNI->def = NewIdxDef;
1214 
1215  LiveRange::iterator Prev = std::prev(NewSegment);
1216  Prev->end = NewIdxDef;
1217  } else {
1218  // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1219  // one position.
1220  // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1221  // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1222  std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1223  LiveRange::iterator Prev = std::prev(AfterNewIdx);
1224  // We have two cases:
1225  if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
1226  // Case 1: NewIdx is inside a liverange. Split this liverange at
1227  // NewIdxDef into the segment "Prev" followed by "NewSegment".
1228  LiveRange::iterator NewSegment = AfterNewIdx;
1229  *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
1230  Prev->valno->def = NewIdxDef;
1231 
1232  *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
1233  DefVNI->def = Prev->start;
1234  } else {
1235  // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1236  // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1237  *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
1238  DefVNI->def = NewIdxDef;
1239  assert(DefVNI != AfterNewIdx->valno);
1240  }
1241  }
1242  return;
1243  }
1244 
1245  if (AfterNewIdx != E &&
1246  SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
1247  // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1248  // that value.
1249  assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
1250  LR.removeValNo(OldIdxVNI);
1251  } else {
1252  // There was no existing def at NewIdx. We need to create a dead def
1253  // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1254  // a new segment at the place where we want to construct the dead def.
1255  // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1256  // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1257  assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
1258  std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1259  // We can reuse OldIdxVNI now.
1260  LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
1261  VNInfo *NewSegmentVNI = OldIdxVNI;
1262  NewSegmentVNI->def = NewIdxDef;
1263  *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1264  NewSegmentVNI);
1265  }
1266  }
1267 
1268  /// Update LR to reflect an instruction has been moved upwards from OldIdx
1269  /// to NewIdx (NewIdx < OldIdx).
1270  void handleMoveUp(LiveRange &LR, Register Reg, LaneBitmask LaneMask) {
1271  LiveRange::iterator E = LR.end();
1272  // Segment going into OldIdx.
1273  LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1274 
1275  // No value live before or after OldIdx? Nothing to do.
1276  if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1277  return;
1278 
1279  LiveRange::iterator OldIdxOut;
1280  // Do we have a value live-in to OldIdx?
1281  if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1282  // If the live-in value isn't killed here, then we have no Def at
1283  // OldIdx, moreover the value must be live at NewIdx so there is nothing
1284  // to do.
1285  bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1286  if (!isKill)
1287  return;
1288 
1289  // At this point we have to move OldIdxIn->end back to the nearest
1290  // previous use or (dead-)def but no further than NewIdx.
1291  SlotIndex DefBeforeOldIdx
1292  = std::max(OldIdxIn->start.getDeadSlot(),
1293  NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
1294  OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1295 
1296  // Did we have a Def at OldIdx? If not we are done now.
1297  OldIdxOut = std::next(OldIdxIn);
1298  if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1299  return;
1300  } else {
1301  OldIdxOut = OldIdxIn;
1302  OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
1303  }
1304 
1305  // If we are here then there is a Definition at OldIdx. OldIdxOut points
1306  // to the segment starting there.
1307  assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1308  "No def?");
1309  VNInfo *OldIdxVNI = OldIdxOut->valno;
1310  assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1311  bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1312 
1313  // Is there an existing def at NewIdx?
1314  SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1315  LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
1316  if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
1317  assert(NewIdxOut->valno != OldIdxVNI &&
1318  "Same value defined more than once?");
1319  // If OldIdx was a dead def remove it.
1320  if (!OldIdxDefIsDead) {
1321  // Remove segment starting at NewIdx and move begin of OldIdxOut to
1322  // NewIdx so it can take its place.
1323  OldIdxVNI->def = NewIdxDef;
1324  OldIdxOut->start = NewIdxDef;
1325  LR.removeValNo(NewIdxOut->valno);
1326  } else {
1327  // Simply remove the dead def at OldIdx.
1328  LR.removeValNo(OldIdxVNI);
1329  }
1330  } else {
1331  // Previously nothing was live after NewIdx, so all we have to do now is
1332  // move the begin of OldIdxOut to NewIdx.
1333  if (!OldIdxDefIsDead) {
1334  // Do we have any intermediate Defs between OldIdx and NewIdx?
1335  if (OldIdxIn != E &&
1336  SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
1337  // OldIdx is not a dead def and NewIdx is before predecessor start.
1338  LiveRange::iterator NewIdxIn = NewIdxOut;
1339  assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1340  const SlotIndex SplitPos = NewIdxDef;
1341  OldIdxVNI = OldIdxIn->valno;
1342 
1343  SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;
1344  LiveRange::iterator Prev = std::prev(OldIdxIn);
1345  if (OldIdxIn != LR.begin() &&
1346  SlotIndex::isEarlierInstr(NewIdx, Prev->end)) {
1347  // If the segment before OldIdx read a value defined earlier than
1348  // NewIdx, the moved instruction also reads and forwards that
1349  // value. Extend the lifetime of the new def point.
1350 
1351  // Extend to where the previous range started, unless there is
1352  // another redef first.
1353  NewDefEndPoint = std::min(OldIdxIn->start,
1354  std::next(NewIdxOut)->start);
1355  }
1356 
1357  // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1358  OldIdxOut->valno->def = OldIdxIn->start;
1359  *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1360  OldIdxOut->valno);
1361  // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1362  // We Slide [NewIdxIn, OldIdxIn) down one position.
1363  // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1364  // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1365  std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1366  // NewIdxIn is now considered undef so we can reuse it for the moved
1367  // value.
1368  LiveRange::iterator NewSegment = NewIdxIn;
1369  LiveRange::iterator Next = std::next(NewSegment);
1370  if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1371  // There is no gap between NewSegment and its predecessor.
1372  *NewSegment = LiveRange::Segment(Next->start, SplitPos,
1373  Next->valno);
1374 
1375  *Next = LiveRange::Segment(SplitPos, NewDefEndPoint, OldIdxVNI);
1376  Next->valno->def = SplitPos;
1377  } else {
1378  // There is a gap between NewSegment and its predecessor
1379  // Value becomes live in.
1380  *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
1381  NewSegment->valno->def = SplitPos;
1382  }
1383  } else {
1384  // Leave the end point of a live def.
1385  OldIdxOut->start = NewIdxDef;
1386  OldIdxVNI->def = NewIdxDef;
1387  if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
1388  OldIdxIn->end = NewIdxDef;
1389  }
1390  } else if (OldIdxIn != E
1391  && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)
1392  && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) {
1393  // OldIdxVNI is a dead def that has been moved into the middle of
1394  // another value in LR. That can happen when LR is a whole register,
1395  // but the dead def is a write to a subreg that is dead at NewIdx.
1396  // The dead def may have been moved across other values
1397  // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1398  // down one position.
1399  // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1400  // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1401  std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1402  // Modify the segment at NewIdxOut and the following segment to meet at
1403  // the point of the dead def, with the following segment getting
1404  // OldIdxVNI as its value number.
1405  *NewIdxOut = LiveRange::Segment(
1406  NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);
1407  *(NewIdxOut + 1) = LiveRange::Segment(
1408  NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1409  OldIdxVNI->def = NewIdxDef;
1410  // Modify subsequent segments to be defined by the moved def OldIdxVNI.
1411  for (auto *Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx)
1412  Idx->valno = OldIdxVNI;
1413  // Aggressively remove all dead flags from the former dead definition.
1414  // Kill/dead flags shouldn't be used while live intervals exist; they
1415  // will be reinserted by VirtRegRewriter.
1416  if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))
1417  for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
1418  if (MO->isReg() && !MO->isUse())
1419  MO->setIsDead(false);
1420  } else {
1421  // OldIdxVNI is a dead def. It may have been moved across other values
1422  // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1423  // down one position.
1424  // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1425  // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1426  std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1427  // OldIdxVNI can be reused now to build a new dead def segment.
1428  LiveRange::iterator NewSegment = NewIdxOut;
1429  VNInfo *NewSegmentVNI = OldIdxVNI;
1430  *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1431  NewSegmentVNI);
1432  NewSegmentVNI->def = NewIdxDef;
1433  }
1434  }
1435  }
1436 
1437  void updateRegMaskSlots() {
1439  llvm::lower_bound(LIS.RegMaskSlots, OldIdx);
1440  assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1441  "No RegMask at OldIdx.");
1442  *RI = NewIdx.getRegSlot();
1443  assert((RI == LIS.RegMaskSlots.begin() ||
1444  SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1445  "Cannot move regmask instruction above another call");
1446  assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1447  SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1448  "Cannot move regmask instruction below another call");
1449  }
1450 
1451  // Return the last use of reg between NewIdx and OldIdx.
1452  SlotIndex findLastUseBefore(SlotIndex Before, Register Reg,
1453  LaneBitmask LaneMask) {
1455  SlotIndex LastUse = Before;
1456  for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1457  if (MO.isUndef())
1458  continue;
1459  unsigned SubReg = MO.getSubReg();
1460  if (SubReg != 0 && LaneMask.any()
1461  && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
1462  continue;
1463 
1464  const MachineInstr &MI = *MO.getParent();
1465  SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1466  if (InstSlot > LastUse && InstSlot < OldIdx)
1467  LastUse = InstSlot.getRegSlot();
1468  }
1469  return LastUse;
1470  }
1471 
1472  // This is a regunit interval, so scanning the use list could be very
1473  // expensive. Scan upwards from OldIdx instead.
1474  assert(Before < OldIdx && "Expected upwards move");
1475  SlotIndexes *Indexes = LIS.getSlotIndexes();
1476  MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
1477 
1478  // OldIdx may not correspond to an instruction any longer, so set MII to
1479  // point to the next instruction after OldIdx, or MBB->end().
1481  if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1482  Indexes->getNextNonNullIndex(OldIdx)))
1483  if (MI->getParent() == MBB)
1484  MII = MI;
1485 
1487  while (MII != Begin) {
1488  if ((--MII)->isDebugOrPseudoInstr())
1489  continue;
1490  SlotIndex Idx = Indexes->getInstructionIndex(*MII);
1491 
1492  // Stop searching when Before is reached.
1493  if (!SlotIndex::isEarlierInstr(Before, Idx))
1494  return Before;
1495 
1496  // Check if MII uses Reg.
1497  for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
1498  if (MO->isReg() && !MO->isUndef() &&
1499  Register::isPhysicalRegister(MO->getReg()) &&
1500  TRI.hasRegUnit(MO->getReg(), Reg))
1501  return Idx.getRegSlot();
1502  }
1503  // Didn't reach Before. It must be the first instruction in the block.
1504  return Before;
1505  }
1506 };
1507 
1508 void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {
1509  // It is fine to move a bundle as a whole, but not an individual instruction
1510  // inside it.
1511  assert((!MI.isBundled() || MI.getOpcode() == TargetOpcode::BUNDLE) &&
1512  "Cannot move instruction in bundle");
1513  SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1514  Indexes->removeMachineInstrFromMaps(MI);
1515  SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1516  assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
1517  OldIndex < getMBBEndIdx(MI.getParent()) &&
1518  "Cannot handle moves across basic block boundaries.");
1519 
1520  HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1521  HME.updateAllRanges(&MI);
1522 }
1523 
1525  bool UpdateFlags) {
1526  assert((BundleStart.getOpcode() == TargetOpcode::BUNDLE) &&
1527  "Bundle start is not a bundle");
1528  SmallVector<SlotIndex, 16> ToProcess;
1529  const SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(BundleStart);
1530  auto BundleEnd = getBundleEnd(BundleStart.getIterator());
1531 
1532  auto I = BundleStart.getIterator();
1533  I++;
1534  while (I != BundleEnd) {
1535  if (!Indexes->hasIndex(*I))
1536  continue;
1537  SlotIndex OldIndex = Indexes->getInstructionIndex(*I, true);
1538  ToProcess.push_back(OldIndex);
1539  Indexes->removeMachineInstrFromMaps(*I, true);
1540  I++;
1541  }
1542  for (SlotIndex OldIndex : ToProcess) {
1543  HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1544  HME.updateAllRanges(&BundleStart);
1545  }
1546 
1547  // Fix up dead defs
1548  const SlotIndex Index = getInstructionIndex(BundleStart);
1549  for (unsigned Idx = 0, E = BundleStart.getNumOperands(); Idx != E; ++Idx) {
1550  MachineOperand &MO = BundleStart.getOperand(Idx);
1551  if (!MO.isReg())
1552  continue;
1553  Register Reg = MO.getReg();
1554  if (Reg.isVirtual() && hasInterval(Reg) && !MO.isUndef()) {
1555  LiveInterval &LI = getInterval(Reg);
1556  LiveQueryResult LRQ = LI.Query(Index);
1557  if (LRQ.isDeadDef())
1558  MO.setIsDead();
1559  }
1560  }
1561 }
1562 
1563 void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1564  const MachineBasicBlock::iterator End,
1565  const SlotIndex EndIdx, LiveRange &LR,
1566  const Register Reg,
1567  LaneBitmask LaneMask) {
1568  LiveInterval::iterator LII = LR.find(EndIdx);
1569  SlotIndex lastUseIdx;
1570  if (LII != LR.end() && LII->start < EndIdx) {
1571  lastUseIdx = LII->end;
1572  } else if (LII == LR.begin()) {
1573  // We may not have a liverange at all if this is a subregister untouched
1574  // between \p Begin and \p End.
1575  } else {
1576  --LII;
1577  }
1578 
1579  for (MachineBasicBlock::iterator I = End; I != Begin;) {
1580  --I;
1581  MachineInstr &MI = *I;
1582  if (MI.isDebugOrPseudoInstr())
1583  continue;
1584 
1585  SlotIndex instrIdx = getInstructionIndex(MI);
1586  bool isStartValid = getInstructionFromIndex(LII->start);
1587  bool isEndValid = getInstructionFromIndex(LII->end);
1588 
1589  // FIXME: This doesn't currently handle early-clobber or multiple removed
1590  // defs inside of the region to repair.
1591  for (const MachineOperand &MO : MI.operands()) {
1592  if (!MO.isReg() || MO.getReg() != Reg)
1593  continue;
1594 
1595  unsigned SubReg = MO.getSubReg();
1597  if ((Mask & LaneMask).none())
1598  continue;
1599 
1600  if (MO.isDef()) {
1601  if (!isStartValid) {
1602  if (LII->end.isDead()) {
1603  LII = LR.removeSegment(LII, true);
1604  if (LII != LR.begin())
1605  --LII;
1606  } else {
1607  LII->start = instrIdx.getRegSlot();
1608  LII->valno->def = instrIdx.getRegSlot();
1609  if (MO.getSubReg() && !MO.isUndef())
1610  lastUseIdx = instrIdx.getRegSlot();
1611  else
1612  lastUseIdx = SlotIndex();
1613  continue;
1614  }
1615  }
1616 
1617  if (!lastUseIdx.isValid()) {
1618  VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1619  LiveRange::Segment S(instrIdx.getRegSlot(),
1620  instrIdx.getDeadSlot(), VNI);
1621  LII = LR.addSegment(S);
1622  } else if (LII->start != instrIdx.getRegSlot()) {
1623  VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1624  LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1625  LII = LR.addSegment(S);
1626  }
1627 
1628  if (MO.getSubReg() && !MO.isUndef())
1629  lastUseIdx = instrIdx.getRegSlot();
1630  else
1631  lastUseIdx = SlotIndex();
1632  } else if (MO.isUse()) {
1633  // FIXME: This should probably be handled outside of this branch,
1634  // either as part of the def case (for defs inside of the region) or
1635  // after the loop over the region.
1636  if (!isEndValid && !LII->end.isBlock())
1637  LII->end = instrIdx.getRegSlot();
1638  if (!lastUseIdx.isValid())
1639  lastUseIdx = instrIdx.getRegSlot();
1640  }
1641  }
1642  }
1643 
1644  bool isStartValid = getInstructionFromIndex(LII->start);
1645  if (!isStartValid && LII->end.isDead())
1646  LR.removeSegment(*LII, true);
1647 }
1648 
1649 void
1653  ArrayRef<Register> OrigRegs) {
1654  // Find anchor points, which are at the beginning/end of blocks or at
1655  // instructions that already have indexes.
1656  while (Begin != MBB->begin() && !Indexes->hasIndex(*std::prev(Begin)))
1657  --Begin;
1658  while (End != MBB->end() && !Indexes->hasIndex(*End))
1659  ++End;
1660 
1661  SlotIndex EndIdx;
1662  if (End == MBB->end())
1663  EndIdx = getMBBEndIdx(MBB).getPrevSlot();
1664  else
1665  EndIdx = getInstructionIndex(*End);
1666 
1667  Indexes->repairIndexesInRange(MBB, Begin, End);
1668 
1669  // Make sure a live interval exists for all register operands in the range.
1670  SmallVector<Register> RegsToRepair(OrigRegs.begin(), OrigRegs.end());
1671  for (MachineBasicBlock::iterator I = End; I != Begin;) {
1672  --I;
1673  MachineInstr &MI = *I;
1674  if (MI.isDebugOrPseudoInstr())
1675  continue;
1676  for (const MachineOperand &MO : MI.operands()) {
1677  if (MO.isReg() && MO.getReg().isVirtual()) {
1678  Register Reg = MO.getReg();
1679  // If the new instructions refer to subregs but the old instructions did
1680  // not, throw away any old live interval so it will be recomputed with
1681  // subranges.
1682  if (MO.getSubReg() && hasInterval(Reg) &&
1683  !getInterval(Reg).hasSubRanges() &&
1686  if (!hasInterval(Reg)) {
1688  // Don't bother to repair a freshly calculated live interval.
1689  erase_value(RegsToRepair, Reg);
1690  }
1691  }
1692  }
1693  }
1694 
1695  for (Register Reg : RegsToRepair) {
1696  if (!Reg.isVirtual())
1697  continue;
1698 
1699  LiveInterval &LI = getInterval(Reg);
1700  // FIXME: Should we support undefs that gain defs?
1701  if (!LI.hasAtLeastOneValue())
1702  continue;
1703 
1704  for (LiveInterval::SubRange &S : LI.subranges())
1705  repairOldRegInRange(Begin, End, EndIdx, S, Reg, S.LaneMask);
1706  LI.removeEmptySubRanges();
1707 
1708  repairOldRegInRange(Begin, End, EndIdx, LI, Reg);
1709  }
1710 }
1711 
1713  for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
1714  if (LiveRange *LR = getCachedRegUnit(*Unit))
1715  if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1716  LR->removeValNo(VNI);
1717  }
1718 }
1719 
1721  // LI may not have the main range computed yet, but its subranges may
1722  // be present.
1723  VNInfo *VNI = LI.getVNInfoAt(Pos);
1724  if (VNI != nullptr) {
1725  assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
1726  LI.removeValNo(VNI);
1727  }
1728 
1729  // Also remove the value defined in subranges.
1730  for (LiveInterval::SubRange &S : LI.subranges()) {
1731  if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1732  if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
1733  S.removeValNo(SVNI);
1734  }
1735  LI.removeEmptySubRanges();
1736 }
1737 
1739  SmallVectorImpl<LiveInterval*> &SplitLIs) {
1740  ConnectedVNInfoEqClasses ConEQ(*this);
1741  unsigned NumComp = ConEQ.Classify(LI);
1742  if (NumComp <= 1)
1743  return;
1744  LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
1745  Register Reg = LI.reg();
1746  const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
1747  for (unsigned I = 1; I < NumComp; ++I) {
1748  Register NewVReg = MRI->createVirtualRegister(RegClass);
1749  LiveInterval &NewLI = createEmptyInterval(NewVReg);
1750  SplitLIs.push_back(&NewLI);
1751  }
1752  ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
1753 }
1754 
1756  assert(LICalc && "LICalc not initialized.");
1757  LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
1758  LICalc->constructMainRangeFromSubranges(LI);
1759 }
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
i
i
Definition: README.txt:29
llvm::LiveQueryResult::valueDefined
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
Definition: LiveInterval.h:135
llvm::LiveIntervals::addSegmentToEndOfBlock
LiveInterval::Segment addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst)
Given a register and an instruction, adds a live segment from that instruction to the end of its MBB.
Definition: LiveIntervals.cpp:872
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::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
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
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::MachineRegisterInfo::subRegLivenessEnabled
bool subRegLivenessEnabled() const
Definition: MachineRegisterInfo.h:219
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:107
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:382
llvm::MachineRegisterInfo::shouldTrackSubRegLiveness
bool shouldTrackSubRegLiveness(const TargetRegisterClass &RC) const
Returns true if liveness for register class RC should be tracked at the subregister level.
Definition: MachineRegisterInfo.h:212
llvm::LiveRange::flushSegmentSet
void flushSegmentSet()
Flush segment set into the regular segment vector.
Definition: LiveInterval.cpp:790
llvm::LiveIntervals::getSlotIndexes
SlotIndexes * getSlotIndexes() const
Definition: LiveIntervals.h:209
llvm::LiveIntervals::HMEditor::getRegUnitLI
LiveRange * getRegUnitLI(unsigned Unit)
Definition: LiveIntervals.cpp:996
llvm::BumpPtrAllocatorImpl::Reset
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
llvm::ConnectedVNInfoEqClasses::Distribute
void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
Definition: LiveInterval.cpp:1346
llvm::MachineRegisterInfo::createVirtualRegister
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
Definition: MachineRegisterInfo.cpp:156
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
llvm::SlotIndex::isEarlierEqualInstr
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
Definition: SlotIndexes.h:210
llvm::SlotIndex::isValid
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:152
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1922
Pass.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:95
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:328
llvm::ArrayRef::iterator
const_pointer iterator
Definition: ArrayRef.h:49
llvm::LiveQueryResult::valueOutOrDead
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
Definition: LiveInterval.h:129
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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::LiveIntervals::getRegMaskSlotsInBlock
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
Definition: LiveIntervals.h:349
llvm::LiveIntervals::getInstructionFromIndex
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
Definition: LiveIntervals.h:225
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::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::LiveQueryResult::isDeadDef
bool isDeadDef() const
Return true if this instruction has a dead def.
Definition: LiveInterval.h:117
llvm::MachineBlockFrequencyInfo::getBlockFreqRelativeToEntryBlock
float getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
Definition: MachineBlockFrequencyInfo.h:68
llvm::LiveRange::Segment
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
llvm::LiveIntervals::intervalIsInOneMBB
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
Definition: LiveIntervals.cpp:818
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::huge_valf
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
Definition: MathExtras.cpp:28
llvm::LiveIntervals::addKillFlags
void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
Definition: LiveIntervals.cpp:693
MachineBasicBlock.h
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:127
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::VNInfo::def
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
llvm::LiveIntervals::HMEditor::HMEditor
HMEditor(LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
Definition: LiveIntervals.cpp:986
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:799
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::LiveIntervals::removeInterval
void removeInterval(Register Reg)
Interval removal.
Definition: LiveIntervals.h:143
llvm::MachineBasicBlock::liveins
iterator_range< livein_iterator > liveins() const
Definition: MachineBasicBlock.h:449
llvm::LiveIntervals::getRegMaskSlots
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
Definition: LiveIntervals.h:345
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:334
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::LiveRange::Segment::start
SlotIndex start
Definition: LiveInterval.h:163
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:770
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::SlotIndexes::repairIndexesInRange
void repairIndexesInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End)
Repair indexes after adding and removing instructions.
Definition: SlotIndexes.cpp:179
llvm::SlotIndexes::getMBBEndIdx
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:481
llvm::Register::index2VirtReg
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:285
llvm::MCRegisterInfo::getNumRegUnits
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
Definition: MCRegisterInfo.h:505
llvm::LiveQueryResult
Result of a LiveRange query.
Definition: LiveInterval.h:90
llvm::mi_bundle_ops
iterator_range< MIBundleOperands > mi_bundle_ops(MachineInstr &MI)
Definition: MachineInstrBundle.h:210
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::LegalityPredicates::any
Predicate any(Predicate P0, Predicate P1)
True iff P0 or P1 are true.
Definition: LegalizerInfo.h:241
llvm::LiveIntervals::createAndComputeVirtRegInterval
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
Definition: LiveIntervals.h:136
llvm::LiveIntervals::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Definition: LiveIntervals.h:249
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
llvm::LiveIntervalCalc::constructMainRangeFromSubranges
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
Definition: LiveIntervalCalc.cpp:107
llvm::LiveIntervals::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
Definition: LiveIntervals.h:220
MachineRegisterInfo.h
llvm::LiveIntervals::handleMove
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
Definition: LiveIntervals.cpp:1508
llvm::LiveRange::beginIndex
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
Definition: LiveInterval.h:385
llvm::LiveInterval::SubRange::LaneMask
LaneBitmask LaneMask
Definition: LiveInterval.h:696
llvm::LiveIntervals::print
void print(raw_ostream &O, const Module *=nullptr) const override
Implement the dump method.
Definition: LiveIntervals.cpp:148
llvm::getBundleEnd
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
Definition: MachineInstrBundle.h:60
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::df_ext_begin
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:242
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
CommandLine.h
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:365
llvm::StatepointOpers::getNumDeoptArgsIdx
unsigned getNumDeoptArgsIdx() const
Get index of Number Deopt Arguments operand.
Definition: StackMaps.h:199
llvm::AnalysisUsage::addRequiredTransitiveID
AnalysisUsage & addRequiredTransitiveID(char &ID)
Definition: Pass.cpp:289
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::SlotIndexes::hasIndex
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:385
llvm::MachineRegisterInfo::use_nodbg_operands
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:534
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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
llvm::LiveIntervals::getCachedRegUnit
LiveRange * getCachedRegUnit(unsigned Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
Definition: LiveIntervals.h:400
llvm::LiveRange::covers
bool covers(const LiveRange &Other) const
Returns true if all segments of the Other live range are completely covered by this live range.
Definition: LiveInterval.cpp:479
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LiveIntervals::ID
static char ID
Definition: LiveIntervals.h:97
llvm::LiveIntervals::hasPHIKill
bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
Definition: LiveIntervals.cpp:844
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:930
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::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::LiveIntervals::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
Definition: LiveIntervals.cpp:120
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::LaneBitmask::getNone
static constexpr LaneBitmask getNone()
Definition: LaneBitmask.h:83
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::TargetRegisterInfo::hasRegUnit
bool hasRegUnit(MCRegister Reg, Register RegUnit) const
Returns true if Reg contains RegUnit.
Definition: TargetRegisterInfo.h:431
llvm::LiveIntervalCalc::createDeadDefs
void createDeadDefs(LiveRange &LR, Register Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
Definition: LiveIntervalCalc.cpp:124
LiveVariables.h
false
Definition: StackSlotColoring.cpp:141
llvm::LiveIntervals::pruneValue
void pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl< SlotIndex > *EndPoints)
If LR has a live value at Kill, prune its live range by removing any liveness reachable from Kill.
Definition: LiveIntervals.cpp:631
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineRegisterInfo::reg_instructions
iterator_range< reg_instr_iterator > reg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:310
llvm::LiveRange::valnos
VNInfoList valnos
Definition: LiveInterval.h:204
MachineInstrBundle.h
llvm::SlotIndexes::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:390
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::PrintLaneMask
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:94
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:642
llvm::SlotIndex::getDeadSlot
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:264
llvm::MIBundleOperands
MIBundleOperands - Iterate over all operands in a bundle of machine instructions.
Definition: MachineInstrBundle.h:166
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:319
SmallPtrSet.h
llvm::BitVector::clearBitsNotInMask
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
Definition: BitVector.h:718
llvm::BitVector
Definition: BitVector.h:75
llvm::LiveIntervals::LiveIntervals
LiveIntervals()
Definition: LiveIntervals.cpp:97
none
@ none
Definition: HWAddressSanitizer.cpp:188
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
createSegmentsForValues
static void createSegmentsForValues(LiveRange &LR, iterator_range< LiveInterval::vni_iterator > VNIs)
Definition: LiveIntervals.cpp:358
llvm::LiveQueryResult::valueIn
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
Definition: LiveInterval.h:105
llvm::SlotIndexes::getInstructionFromIndex
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
Definition: SlotIndexes.h:408
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::LiveQueryResult::endPoint
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
Definition: LiveInterval.h:147
Statepoint.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2005
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MCRegUnitRootIterator::isValid
bool isValid() const
Check if the iterator is at the end of the list.
Definition: MCRegisterInfo.h:773
llvm::LiveIntervals::handleMoveIntoNewBundle
void handleMoveIntoNewBundle(MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals of operands of all instructions in the newly created bundle specified by BundleStart...
Definition: LiveIntervals.cpp:1524
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::printRegUnit
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
Definition: TargetRegisterInfo.cpp:142
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
Passes.h
LiveIntervalCalc.h
llvm::LiveIntervals::HMEditor
Toolkit used by handleMove to trim or extend live intervals.
Definition: LiveIntervals.cpp:975
llvm::LiveIntervals::removePhysRegDefAt
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
Definition: LiveIntervals.cpp:1712
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::MachineLoopInfoID
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
Definition: MachineLoopInfo.cpp:43
llvm::cl::opt< bool >
llvm::SlotIndex::getBaseIndex
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:246
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:394
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::SlotIndexes::getMBBStartIdx
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:471
llvm::MachineOperand::setIsDead
void setIsDead(bool Val=true)
Definition: MachineOperand.h:515
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::LiveRange::hasAtLeastOneValue
bool hasAtLeastOneValue() const
Definition: LiveInterval.h:309
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
uint64_t
liveintervals
liveintervals
Definition: LiveIntervals.cpp:66
LiveIntervals.h
llvm::LiveIntervalCalc::calculate
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
Definition: LiveIntervalCalc.cpp:43
llvm::LiveIntervals::getRegMaskBitsInBlock
ArrayRef< const uint32_t * > getRegMaskBitsInBlock(unsigned MBBNum) const
Returns an array of mask pointers corresponding to getRegMaskSlotsInBlock(MBBNum).
Definition: LiveIntervals.h:360
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
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::Interval
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::VirtRegMap::getPhys
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
Definition: VirtRegMap.h:105
llvm::LaneBitmask::any
constexpr bool any() const
Definition: LaneBitmask.h:53
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::LiveIntervals::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: LiveIntervals.cpp:103
MCRegisterInfo.h
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
llvm::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
ArrayRef.h
llvm::LiveRange::Query
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:541
llvm::RISCVFPRndMode::RUP
@ RUP
Definition: RISCVBaseInfo.h:276
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::MIBundleOperandIteratorBase::isValid
bool isValid() const
isValid - Returns true until all the operands have been visited.
Definition: MachineInstrBundle.h:136
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ConnectedVNInfoEqClasses::Classify
unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
Definition: LiveInterval.cpp:1304
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:261
llvm::pdb::PDB_TableType::Segments
@ Segments
llvm::MCSuperRegIterator
MCSuperRegIterator enumerates all super-registers of Reg.
Definition: MCRegisterInfo.h:644
llvm::SlotIndexes::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:519
iterator_range.h
llvm::LiveIntervals::shrinkToUses
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
Definition: LiveIntervals.cpp:449
llvm::LiveIntervals::checkRegMaskInterference
bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
Definition: LiveIntervals.cpp:905
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:386
LiveRange
SI Optimize VGPR LiveRange
Definition: SIOptimizeVGPRLiveRange.cpp:616
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::MachineFunction
Definition: MachineFunction.h:257
llvm::LiveRange::FindSegmentContaining
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
Definition: LiveInterval.h:436
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:70
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::MachineBasicBlock::getBeginClobberMask
const uint32_t * getBeginClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the start of this basic block.
Definition: MachineBasicBlock.cpp:1598
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
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::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:576
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:516
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::StatepointOpers::getFlags
uint64_t getFlags() const
Return the statepoint flags.
Definition: StackMaps.h:222
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::LiveRange::vnis
iterator_range< vni_iterator > vnis()
Definition: LiveInterval.h:230
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", "Live Interval Analysis", false, false) INITIALIZE_PASS_END(LiveIntervals
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
uint32_t
Compiler.h
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
TargetSubtargetInfo.h
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::LiveIntervals::createEmptyInterval
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
Definition: LiveIntervals.h:129
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
llvm::Pass::dump
void dump() const
Definition: Pass.cpp:136
hasLiveThroughUse
static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg)
Check whether use of reg in MI is live-through.
Definition: LiveIntervals.cpp:890
llvm::LiveRange::Segment::end
SlotIndex end
Definition: LiveInterval.h:164
llvm::df_ext_end
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:247
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
llvm::LiveRange::endIndex
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:392
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::LiveRangeCalc::isJointlyDominated
static LLVM_ATTRIBUTE_UNUSED bool isJointlyDominated(const MachineBasicBlock *MBB, ArrayRef< SlotIndex > Defs, const SlotIndexes &Indexes)
A diagnostic function to check if the end of the block MBB is jointly dominated by the blocks corresp...
Definition: LiveRangeCalc.cpp:432
llvm::StatepointOpers
MI-level Statepoint operands.
Definition: StackMaps.h:158
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::SmallVectorImpl::swap
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:972
llvm::LiveIntervals::getSpillWeight
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
Definition: LiveIntervals.cpp:859
llvm::initializeLiveIntervalsPass
void initializeLiveIntervalsPass(PassRegistry &)
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
llvm::LiveIntervals::extendToIndices
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
Definition: LiveIntervals.cpp:622
llvm::SlotIndex::getPrevSlot
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:294
llvm::LiveIntervals::~LiveIntervals
~LiveIntervals() override
Definition: LiveIntervals.cpp:101
llvm::TargetRegisterInfo::getCustomEHPadPreservedMask
virtual const uint32_t * getCustomEHPadPreservedMask(const MachineFunction &MF) const
Return a register mask for the registers preserved by the unwinder, or nullptr if no custom mask is n...
Definition: TargetRegisterInfo.h:492
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
llvm::MachineFunction::print
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
Definition: MachineFunction.cpp:571
llvm::MachineRegisterInfo::reg_empty
bool reg_empty(Register RegNo) const
reg_empty - Return true if there are no instructions using or defining the specified register (it may...
Definition: MachineRegisterInfo.h:331
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:284
StackMaps.h
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
llvm::LiveRange::verify
void verify() const
Walk the range and assert if any invariants fail to hold.
Definition: LiveInterval.cpp:1055
EnablePrecomputePhysRegs
Live Interval static false cl::opt< bool > EnablePrecomputePhysRegs("precompute-phys-liveness", cl::Hidden, cl::desc("Eagerly compute live intervals for all physreg units."))
llvm::MachineBasicBlock::livein_empty
bool livein_empty() const
Definition: MachineBasicBlock.h:448
llvm::LiveIntervals::getRegMaskBits
ArrayRef< const uint32_t * > getRegMaskBits() const
Returns an array of register mask pointers corresponding to getRegMaskSlots().
Definition: LiveIntervals.h:356
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::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LiveIntervals.cpp:86
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::SlotIndexes::getNextNonNullIndex
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
Definition: SlotIndexes.h:414
LiveInterval.h
llvm::MachineBasicBlock::getEndClobberMask
const uint32_t * getEndClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the end of the basic block.
Definition: MachineBasicBlock.cpp:1604
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:680
llvm::MCRegUnitRootIterator
MCRegUnitRootIterator enumerates the root registers of a register unit.
Definition: MCRegisterInfo.h:754
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
llvm::UseSegmentSetForPhysRegs
cl::opt< bool > UseSegmentSetForPhysRegs
llvm::LiveIntervals::HMEditor::updateAllRanges
void updateAllRanges(MachineInstr *MI)
Update all live ranges touched by MI, assuming a move from OldIdx to NewIdx.
Definition: LiveIntervals.cpp:1004
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
N
#define N
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::LiveIntervals::splitSeparateComponents
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
Definition: LiveIntervals.cpp:1738
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:519
llvm::MachineDominatorsID
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
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::df_ext_iterator
Definition: DepthFirstIterator.h:236
LaneBitmask.h
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::LiveRange::clear
void clear()
Definition: LiveInterval.h:300
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:277
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::SmallVectorImpl< MachineInstr * >
MachineOperand.h
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::LiveIntervals::repairIntervalsInRange
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< Register > OrigRegs)
Update live intervals for instructions in a range of iterators.
Definition: LiveIntervals.cpp:1650
llvm::StatepointFlags::DeoptLiveIn
@ DeoptLiveIn
Mark the deopt arguments associated with the statepoint as only being "live-in".
llvm::LiveVariables
Definition: LiveVariables.h:47
llvm::VNInfo::isUnused
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
llvm::LiveIntervals::hasInterval
bool hasInterval(Register Reg) const
Definition: LiveIntervals.h:123
llvm::LiveRange::removeValNo
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
Definition: LiveInterval.cpp:619
llvm::MachineRegisterInfo::isReservedRegUnit
bool isReservedRegUnit(unsigned Unit) const
Returns true when the given register unit is considered reserved.
Definition: MachineRegisterInfo.cpp:642
SlotIndexes.h
llvm::cl::desc
Definition: CommandLine.h:413
llvm::MachineRegisterInfo::reg_nodbg_empty
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
Definition: MachineRegisterInfo.h:385
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
MachineFunction.h
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
llvm::MachineInstrBundleIterator< MachineInstr >
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
llvm::ConnectedVNInfoEqClasses
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
Definition: LiveInterval.h:998
llvm::SlotIndexes::removeMachineInstrFromMaps
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
Definition: SlotIndexes.cpp:115
llvm::LiveIntervalsID
char & LiveIntervalsID
LiveIntervals - This analysis keeps track of the live ranges of virtual and physical registers.
Definition: LiveIntervals.cpp:61
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
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
SubReg
unsigned SubReg
Definition: AArch64AdvSIMDScalarPass.cpp:104
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::LiveIntervals::getVNInfoAllocator
VNInfo::Allocator & getVNInfoAllocator()
Definition: LiveIntervals.h:278
llvm::LiveRange::end
iterator end()
Definition: LiveInterval.h:216
llvm::VNInfo::markUnused
void markUnused()
Mark this value as unused.
Definition: LiveInterval.h:84
llvm::LiveIntervals::getRegUnit
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
Definition: LiveIntervals.h:387
MachineDominators.h
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
llvm::StatepointOpers::getNumGCPtrIdx
unsigned getNumGCPtrIdx()
Get index of number of GC pointers.
Definition: StackMaps.cpp:114
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