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