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