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