1//===-- LiveIntervalAnalysis.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// 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 uses the
13// LiveVariables pass to conservatively compute live intervals for
14// each virtual and physical register.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/LiveIntervalAnalysis.h"
19#include "LiveRangeCalc.h"
20#include "llvm/ADT/DenseSet.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/Analysis/AliasAnalysis.h"
23#include "llvm/CodeGen/LiveVariables.h"
24#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
25#include "llvm/CodeGen/MachineDominators.h"
26#include "llvm/CodeGen/MachineInstr.h"
27#include "llvm/CodeGen/MachineRegisterInfo.h"
28#include "llvm/CodeGen/Passes.h"
29#include "llvm/CodeGen/VirtRegMap.h"
30#include "llvm/IR/Value.h"
31#include "llvm/Support/BlockFrequency.h"
32#include "llvm/Support/CommandLine.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/ErrorHandling.h"
35#include "llvm/Support/Format.h"
36#include "llvm/Support/raw_ostream.h"
37#include "llvm/Target/TargetInstrInfo.h"
38#include "llvm/Target/TargetRegisterInfo.h"
39#include "llvm/Target/TargetSubtargetInfo.h"
40#include <algorithm>
41#include <cmath>
42#include <limits>
43using namespace llvm;
44
45#define DEBUG_TYPE "regalloc"
46
47char LiveIntervals::ID = 0;
48char &llvm::LiveIntervalsID = LiveIntervals::ID;
49INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
50                "Live Interval Analysis", false, false)
51INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
52INITIALIZE_PASS_DEPENDENCY(LiveVariables)
53INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
54INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
55INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
56                "Live Interval Analysis", false, false)
57
58#ifndef NDEBUG
59static cl::opt<bool> EnablePrecomputePhysRegs(
60  "precompute-phys-liveness", cl::Hidden,
61  cl::desc("Eagerly compute live intervals for all physreg units."));
62#else
63static bool EnablePrecomputePhysRegs = false;
64#endif // NDEBUG
65
66static cl::opt<bool> EnableSubRegLiveness(
67  "enable-subreg-liveness", cl::Hidden, cl::init(true),
68  cl::desc("Enable subregister liveness tracking."));
69
70namespace llvm {
71cl::opt<bool> UseSegmentSetForPhysRegs(
72    "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
73    cl::desc(
74        "Use segment set for the computation of the live ranges of physregs."));
75}
76
77void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
78  AU.setPreservesCFG();
79  AU.addRequired<AliasAnalysis>();
80  AU.addPreserved<AliasAnalysis>();
81  // LiveVariables isn't really required by this analysis, it is only required
82  // here to make sure it is live during TwoAddressInstructionPass and
83  // PHIElimination. This is temporary.
84  AU.addRequired<LiveVariables>();
85  AU.addPreserved<LiveVariables>();
86  AU.addPreservedID(MachineLoopInfoID);
87  AU.addRequiredTransitiveID(MachineDominatorsID);
88  AU.addPreservedID(MachineDominatorsID);
89  AU.addPreserved<SlotIndexes>();
90  AU.addRequiredTransitive<SlotIndexes>();
91  MachineFunctionPass::getAnalysisUsage(AU);
92}
93
94LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
95  DomTree(nullptr), LRCalc(nullptr) {
96  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
97}
98
99LiveIntervals::~LiveIntervals() {
100  delete LRCalc;
101}
102
103void LiveIntervals::releaseMemory() {
104  // Free the live intervals themselves.
105  for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
106    delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
107  VirtRegIntervals.clear();
108  RegMaskSlots.clear();
109  RegMaskBits.clear();
110  RegMaskBlocks.clear();
111
112  for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
113    delete RegUnitRanges[i];
114  RegUnitRanges.clear();
115
116  // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
117  VNInfoAllocator.Reset();
118}
119
120/// runOnMachineFunction - calculates LiveIntervals
121///
122bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
123  MF = &fn;
124  MRI = &MF->getRegInfo();
125  TRI = MF->getSubtarget().getRegisterInfo();
126  TII = MF->getSubtarget().getInstrInfo();
127  AA = &getAnalysis<AliasAnalysis>();
128  Indexes = &getAnalysis<SlotIndexes>();
129  DomTree = &getAnalysis<MachineDominatorTree>();
130
131  if (EnableSubRegLiveness && MF->getSubtarget().enableSubRegLiveness())
132    MRI->enableSubRegLiveness(true);
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  DEBUG(dump());
151  return true;
152}
153
154/// print - Implement the dump method.
155void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
156  OS << "********** INTERVALS **********\n";
157
158  // Dump the regunits.
159  for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
160    if (LiveRange *LR = RegUnitRanges[i])
161      OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n';
162
163  // Dump the virtregs.
164  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
165    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
166    if (hasInterval(Reg))
167      OS << getInterval(Reg) << '\n';
168  }
169
170  OS << "RegMasks:";
171  for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i)
172    OS << ' ' << RegMaskSlots[i];
173  OS << '\n';
174
175  printInstrs(OS);
176}
177
178void 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)
184void LiveIntervals::dumpInstrs() const {
185  printInstrs(dbgs());
186}
187#endif
188
189LiveInterval* LiveIntervals::createInterval(unsigned reg) {
190  float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
191                  llvm::huge_valf : 0.0F;
192  return new LiveInterval(reg, Weight);
193}
194
195
196/// computeVirtRegInterval - Compute the live interval of a virtual register,
197/// based on defs and uses.
198void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
199  assert(LRCalc && "LRCalc not initialized.");
200  assert(LI.empty() && "Should only compute empty intervals.");
201  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
202  LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
203  computeDeadValues(LI, nullptr);
204}
205
206void LiveIntervals::computeVirtRegs() {
207  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
208    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
209    if (MRI->reg_nodbg_empty(Reg))
210      continue;
211    createAndComputeVirtRegInterval(Reg);
212  }
213}
214
215void LiveIntervals::computeRegMasks() {
216  RegMaskBlocks.resize(MF->getNumBlockIDs());
217
218  // Find all instructions with regmask operands.
219  for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
220       MBBI != E; ++MBBI) {
221    MachineBasicBlock *MBB = MBBI;
222    std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
223    RMB.first = RegMaskSlots.size();
224    for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end();
225         MI != ME; ++MI)
226      for (MIOperands MO(MI); MO.isValid(); ++MO) {
227        if (!MO->isRegMask())
228          continue;
229          RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
230          RegMaskBits.push_back(MO->getRegMask());
231      }
232    // Compute the number of register mask instructions in this block.
233    RMB.second = RegMaskSlots.size() - RMB.first;
234  }
235}
236
237//===----------------------------------------------------------------------===//
238//                           Register Unit Liveness
239//===----------------------------------------------------------------------===//
240//
241// Fixed interference typically comes from ABI boundaries: Function arguments
242// and return values are passed in fixed registers, and so are exception
243// pointers entering landing pads. Certain instructions require values to be
244// present in specific registers. That is also represented through fixed
245// interference.
246//
247
248/// computeRegUnitInterval - Compute the live range of a register unit, based
249/// on the uses and defs of aliasing registers.  The range should be empty,
250/// or contain only dead phi-defs from ABI blocks.
251void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
252  assert(LRCalc && "LRCalc not initialized.");
253  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
254
255  // The physregs aliasing Unit are the roots and their super-registers.
256  // Create all values as dead defs before extending to uses. Note that roots
257  // may share super-registers. That's OK because createDeadDefs() is
258  // idempotent. It is very rare for a register unit to have multiple roots, so
259  // uniquing super-registers is probably not worthwhile.
260  for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
261    for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
262         Supers.isValid(); ++Supers) {
263      if (!MRI->reg_empty(*Supers))
264        LRCalc->createDeadDefs(LR, *Supers);
265    }
266  }
267
268  // Now extend LR to reach all uses.
269  // Ignore uses of reserved registers. We only track defs of those.
270  for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
271    for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
272         Supers.isValid(); ++Supers) {
273      unsigned Reg = *Supers;
274      if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg))
275        LRCalc->extendToUses(LR, Reg);
276    }
277  }
278
279  // Flush the segment set to the segment vector.
280  if (UseSegmentSetForPhysRegs)
281    LR.flushSegmentSet();
282}
283
284
285/// computeLiveInRegUnits - Precompute the live ranges of any register units
286/// that are live-in to an ABI block somewhere. Register values can appear
287/// without a corresponding def when entering the entry block or a landing pad.
288///
289void LiveIntervals::computeLiveInRegUnits() {
290  RegUnitRanges.resize(TRI->getNumRegUnits());
291  DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
292
293  // Keep track of the live range sets allocated.
294  SmallVector<unsigned, 8> NewRanges;
295
296  // Check all basic blocks for live-ins.
297  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
298       MFI != MFE; ++MFI) {
299    const MachineBasicBlock *MBB = MFI;
300
301    // We only care about ABI blocks: Entry + landing pads.
302    if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
303      continue;
304
305    // Create phi-defs at Begin for all live-in registers.
306    SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
307    DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
308    for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
309         LIE = MBB->livein_end(); LII != LIE; ++LII) {
310      for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
311        unsigned Unit = *Units;
312        LiveRange *LR = RegUnitRanges[Unit];
313        if (!LR) {
314          // Use segment set to speed-up initial computation of the live range.
315          LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
316          NewRanges.push_back(Unit);
317        }
318        VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
319        (void)VNI;
320        DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
321      }
322    }
323    DEBUG(dbgs() << '\n');
324  }
325  DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
326
327  // Compute the 'normal' part of the ranges.
328  for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) {
329    unsigned Unit = NewRanges[i];
330    computeRegUnitRange(*RegUnitRanges[Unit], Unit);
331  }
332}
333
334
335static void createSegmentsForValues(LiveRange &LR,
336      iterator_range<LiveInterval::vni_iterator> VNIs) {
337  for (auto VNI : VNIs) {
338    if (VNI->isUnused())
339      continue;
340    SlotIndex Def = VNI->def;
341    LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
342  }
343}
344
345typedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList;
346
347static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
348                                 ShrinkToUsesWorkList &WorkList,
349                                 const LiveRange &OldRange) {
350  // Keep track of the PHIs that are in use.
351  SmallPtrSet<VNInfo*, 8> UsedPHIs;
352  // Blocks that have already been added to WorkList as live-out.
353  SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
354
355  // Extend intervals to reach all uses in WorkList.
356  while (!WorkList.empty()) {
357    SlotIndex Idx = WorkList.back().first;
358    VNInfo *VNI = WorkList.back().second;
359    WorkList.pop_back();
360    const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
361    SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
362
363    // Extend the live range for VNI to be live at Idx.
364    if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
365      assert(ExtVNI == VNI && "Unexpected existing value number");
366      (void)ExtVNI;
367      // Is this a PHIDef we haven't seen before?
368      if (!VNI->isPHIDef() || VNI->def != BlockStart ||
369          !UsedPHIs.insert(VNI).second)
370        continue;
371      // The PHI is live, make sure the predecessors are live-out.
372      for (auto &Pred : MBB->predecessors()) {
373        if (!LiveOut.insert(Pred).second)
374          continue;
375        SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
376        // A predecessor is not required to have a live-out value for a PHI.
377        if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
378          WorkList.push_back(std::make_pair(Stop, PVNI));
379      }
380      continue;
381    }
382
383    // VNI is live-in to MBB.
384    DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
385    LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
386
387    // Make sure VNI is live-out from the predecessors.
388    for (auto &Pred : MBB->predecessors()) {
389      if (!LiveOut.insert(Pred).second)
390        continue;
391      SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
392      assert(OldRange.getVNInfoBefore(Stop) == VNI &&
393             "Wrong value out of predecessor");
394      WorkList.push_back(std::make_pair(Stop, VNI));
395    }
396  }
397}
398
399/// shrinkToUses - After removing some uses of a register, shrink its live
400/// range to just the remaining uses. This method does not compute reaching
401/// defs for new uses, and it doesn't remove dead defs.
402bool LiveIntervals::shrinkToUses(LiveInterval *li,
403                                 SmallVectorImpl<MachineInstr*> *dead) {
404  DEBUG(dbgs() << "Shrink: " << *li << '\n');
405  assert(TargetRegisterInfo::isVirtualRegister(li->reg)
406         && "Can only shrink virtual registers");
407
408  // Shrink subregister live ranges.
409  for (LiveInterval::SubRange &S : li->subranges()) {
410    shrinkToUses(S, li->reg);
411  }
412
413  // Find all the values used, including PHI kills.
414  ShrinkToUsesWorkList WorkList;
415
416  // Visit all instructions reading li->reg.
417  for (MachineRegisterInfo::reg_instr_iterator
418       I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end();
419       I != E; ) {
420    MachineInstr *UseMI = &*(I++);
421    if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
422      continue;
423    SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
424    LiveQueryResult LRQ = li->Query(Idx);
425    VNInfo *VNI = LRQ.valueIn();
426    if (!VNI) {
427      // This shouldn't happen: readsVirtualRegister returns true, but there is
428      // no live value. It is likely caused by a target getting <undef> flags
429      // wrong.
430      DEBUG(dbgs() << Idx << '\t' << *UseMI
431                   << "Warning: Instr claims to read non-existent value in "
432                    << *li << '\n');
433      continue;
434    }
435    // Special case: An early-clobber tied operand reads and writes the
436    // register one slot early.
437    if (VNInfo *DefVNI = LRQ.valueDefined())
438      Idx = DefVNI->def;
439
440    WorkList.push_back(std::make_pair(Idx, VNI));
441  }
442
443  // Create new live ranges with only minimal live segments per def.
444  LiveRange NewLR;
445  createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
446  extendSegmentsToUses(NewLR, *Indexes, WorkList, *li);
447
448  // Move the trimmed segments back.
449  li->segments.swap(NewLR.segments);
450
451  // Handle dead values.
452  bool CanSeparate = computeDeadValues(*li, dead);
453  DEBUG(dbgs() << "Shrunk: " << *li << '\n');
454  return CanSeparate;
455}
456
457bool LiveIntervals::computeDeadValues(LiveInterval &LI,
458                                      SmallVectorImpl<MachineInstr*> *dead) {
459  bool PHIRemoved = false;
460  for (auto VNI : LI.valnos) {
461    if (VNI->isUnused())
462      continue;
463    SlotIndex Def = VNI->def;
464    LiveRange::iterator I = LI.FindSegmentContaining(Def);
465    assert(I != LI.end() && "Missing segment for VNI");
466
467    // Is the register live before? Otherwise we may have to add a read-undef
468    // flag for subregister defs.
469    if (MRI->shouldTrackSubRegLiveness(LI.reg)) {
470      if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
471        MachineInstr *MI = getInstructionFromIndex(Def);
472        MI->addRegisterDefReadUndef(LI.reg);
473      }
474    }
475
476    if (I->end != Def.getDeadSlot())
477      continue;
478    if (VNI->isPHIDef()) {
479      // This is a dead PHI. Remove it.
480      VNI->markUnused();
481      LI.removeSegment(I);
482      DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
483      PHIRemoved = true;
484    } else {
485      // This is a dead def. Make sure the instruction knows.
486      MachineInstr *MI = getInstructionFromIndex(Def);
487      assert(MI && "No instruction defining live value");
488      MI->addRegisterDead(LI.reg, TRI);
489      if (dead && MI->allDefsAreDead()) {
490        DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
491        dead->push_back(MI);
492      }
493    }
494  }
495  return PHIRemoved;
496}
497
498void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
499{
500  DEBUG(dbgs() << "Shrink: " << SR << '\n');
501  assert(TargetRegisterInfo::isVirtualRegister(Reg)
502         && "Can only shrink virtual registers");
503  // Find all the values used, including PHI kills.
504  ShrinkToUsesWorkList WorkList;
505
506  // Visit all instructions reading Reg.
507  SlotIndex LastIdx;
508  for (MachineOperand &MO : MRI->reg_operands(Reg)) {
509    MachineInstr *UseMI = MO.getParent();
510    if (UseMI->isDebugValue())
511      continue;
512    // Maybe the operand is for a subregister we don't care about.
513    unsigned SubReg = MO.getSubReg();
514    if (SubReg != 0) {
515      unsigned SubRegMask = TRI->getSubRegIndexLaneMask(SubReg);
516      if ((SubRegMask & SR.LaneMask) == 0)
517        continue;
518    }
519    // We only need to visit each instruction once.
520    SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
521    if (Idx == LastIdx)
522      continue;
523    LastIdx = Idx;
524
525    LiveQueryResult LRQ = SR.Query(Idx);
526    VNInfo *VNI = LRQ.valueIn();
527    // For Subranges it is possible that only undef values are left in that
528    // part of the subregister, so there is no real liverange at the use
529    if (!VNI)
530      continue;
531
532    // Special case: An early-clobber tied operand reads and writes the
533    // register one slot early.
534    if (VNInfo *DefVNI = LRQ.valueDefined())
535      Idx = DefVNI->def;
536
537    WorkList.push_back(std::make_pair(Idx, VNI));
538  }
539
540  // Create a new live ranges with only minimal live segments per def.
541  LiveRange NewLR;
542  createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
543  extendSegmentsToUses(NewLR, *Indexes, WorkList, SR);
544
545  // Move the trimmed ranges back.
546  SR.segments.swap(NewLR.segments);
547
548  // Remove dead PHI value numbers
549  for (auto VNI : SR.valnos) {
550    if (VNI->isUnused())
551      continue;
552    const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
553    assert(Segment != nullptr && "Missing segment for VNI");
554    if (Segment->end != VNI->def.getDeadSlot())
555      continue;
556    if (VNI->isPHIDef()) {
557      // This is a dead PHI. Remove it.
558      VNI->markUnused();
559      SR.removeSegment(*Segment);
560      DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
561    }
562  }
563
564  DEBUG(dbgs() << "Shrunk: " << SR << '\n');
565}
566
567void LiveIntervals::extendToIndices(LiveRange &LR,
568                                    ArrayRef<SlotIndex> Indices) {
569  assert(LRCalc && "LRCalc not initialized.");
570  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
571  for (unsigned i = 0, e = Indices.size(); i != e; ++i)
572    LRCalc->extend(LR, Indices[i]);
573}
574
575void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
576                               SmallVectorImpl<SlotIndex> *EndPoints) {
577  LiveQueryResult LRQ = LR.Query(Kill);
578  VNInfo *VNI = LRQ.valueOutOrDead();
579  if (!VNI)
580    return;
581
582  MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
583  SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
584
585  // If VNI isn't live out from KillMBB, the value is trivially pruned.
586  if (LRQ.endPoint() < MBBEnd) {
587    LR.removeSegment(Kill, LRQ.endPoint());
588    if (EndPoints) EndPoints->push_back(LRQ.endPoint());
589    return;
590  }
591
592  // VNI is live out of KillMBB.
593  LR.removeSegment(Kill, MBBEnd);
594  if (EndPoints) EndPoints->push_back(MBBEnd);
595
596  // Find all blocks that are reachable from KillMBB without leaving VNI's live
597  // range. It is possible that KillMBB itself is reachable, so start a DFS
598  // from each successor.
599  typedef SmallPtrSet<MachineBasicBlock*, 9> VisitedTy;
600  VisitedTy Visited;
601  for (MachineBasicBlock::succ_iterator
602       SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end();
603       SuccI != SuccE; ++SuccI) {
604    for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
605         I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited);
606         I != E;) {
607      MachineBasicBlock *MBB = *I;
608
609      // Check if VNI is live in to MBB.
610      SlotIndex MBBStart, MBBEnd;
611      std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
612      LiveQueryResult LRQ = LR.Query(MBBStart);
613      if (LRQ.valueIn() != VNI) {
614        // This block isn't part of the VNI segment. Prune the search.
615        I.skipChildren();
616        continue;
617      }
618
619      // Prune the search if VNI is killed in MBB.
620      if (LRQ.endPoint() < MBBEnd) {
621        LR.removeSegment(MBBStart, LRQ.endPoint());
622        if (EndPoints) EndPoints->push_back(LRQ.endPoint());
623        I.skipChildren();
624        continue;
625      }
626
627      // VNI is live through MBB.
628      LR.removeSegment(MBBStart, MBBEnd);
629      if (EndPoints) EndPoints->push_back(MBBEnd);
630      ++I;
631    }
632  }
633}
634
635//===----------------------------------------------------------------------===//
636// Register allocator hooks.
637//
638
639void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
640  // Keep track of regunit ranges.
641  SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;
642  // Keep track of subregister ranges.
643  SmallVector<std::pair<const LiveInterval::SubRange*,
644                        LiveRange::const_iterator>, 4> SRs;
645
646  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
647    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
648    if (MRI->reg_nodbg_empty(Reg))
649      continue;
650    const LiveInterval &LI = getInterval(Reg);
651    if (LI.empty())
652      continue;
653
654    // Find the regunit intervals for the assigned register. They may overlap
655    // the virtual register live range, cancelling any kills.
656    RU.clear();
657    for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid();
658         ++Units) {
659      const LiveRange &RURange = getRegUnit(*Units);
660      if (RURange.empty())
661        continue;
662      RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
663    }
664
665    if (MRI->subRegLivenessEnabled()) {
666      SRs.clear();
667      for (const LiveInterval::SubRange &SR : LI.subranges()) {
668        SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end)));
669      }
670    }
671
672    // Every instruction that kills Reg corresponds to a segment range end
673    // point.
674    for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
675         ++RI) {
676      // A block index indicates an MBB edge.
677      if (RI->end.isBlock())
678        continue;
679      MachineInstr *MI = getInstructionFromIndex(RI->end);
680      if (!MI)
681        continue;
682
683      // Check if any of the regunits are live beyond the end of RI. That could
684      // happen when a physreg is defined as a copy of a virtreg:
685      //
686      //   %EAX = COPY %vreg5
687      //   FOO %vreg5         <--- MI, cancel kill because %EAX is live.
688      //   BAR %EAX<kill>
689      //
690      // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
691      for (auto &RUP : RU) {
692        const LiveRange &RURange = *RUP.first;
693        LiveRange::const_iterator &I = RUP.second;
694        if (I == RURange.end())
695          continue;
696        I = RURange.advanceTo(I, RI->end);
697        if (I == RURange.end() || I->start >= RI->end)
698          continue;
699        // I is overlapping RI.
700        goto CancelKill;
701      }
702
703      if (MRI->subRegLivenessEnabled()) {
704        // When reading a partial undefined value we must not add a kill flag.
705        // The regalloc might have used the undef lane for something else.
706        // Example:
707        //     %vreg1 = ...              ; R32: %vreg1
708        //     %vreg2:high16 = ...       ; R64: %vreg2
709        //        = read %vreg2<kill>    ; R64: %vreg2
710        //        = read %vreg1          ; R32: %vreg1
711        // The <kill> flag is correct for %vreg2, but the register allocator may
712        // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0
713        // are actually never written by %vreg2. After assignment the <kill>
714        // flag at the read instruction is invalid.
715        unsigned DefinedLanesMask;
716        if (!SRs.empty()) {
717          // Compute a mask of lanes that are defined.
718          DefinedLanesMask = 0;
719          for (auto &SRP : SRs) {
720            const LiveInterval::SubRange &SR = *SRP.first;
721            LiveRange::const_iterator &I = SRP.second;
722            if (I == SR.end())
723              continue;
724            I = SR.advanceTo(I, RI->end);
725            if (I == SR.end() || I->start >= RI->end)
726              continue;
727            // I is overlapping RI
728            DefinedLanesMask |= SR.LaneMask;
729          }
730        } else
731          DefinedLanesMask = ~0u;
732
733        bool IsFullWrite = false;
734        for (const MachineOperand &MO : MI->operands()) {
735          if (!MO.isReg() || MO.getReg() != Reg)
736            continue;
737          if (MO.isUse()) {
738            // Reading any undefined lanes?
739            unsigned UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
740            if ((UseMask & ~DefinedLanesMask) != 0)
741              goto CancelKill;
742          } else if (MO.getSubReg() == 0) {
743            // Writing to the full register?
744            assert(MO.isDef());
745            IsFullWrite = true;
746          }
747        }
748
749        // If an instruction writes to a subregister, a new segment starts in
750        // the LiveInterval. But as this is only overriding part of the register
751        // adding kill-flags is not correct here after registers have been
752        // assigned.
753        if (!IsFullWrite) {
754          // Next segment has to be adjacent in the subregister write case.
755          LiveRange::const_iterator N = std::next(RI);
756          if (N != LI.end() && N->start == RI->end)
757            goto CancelKill;
758        }
759      }
760
761      MI->addRegisterKilled(Reg, nullptr);
762      continue;
763CancelKill:
764      MI->clearRegisterKills(Reg, nullptr);
765    }
766  }
767}
768
769MachineBasicBlock*
770LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
771  // A local live range must be fully contained inside the block, meaning it is
772  // defined and killed at instructions, not at block boundaries. It is not
773  // live in or or out of any block.
774  //
775  // It is technically possible to have a PHI-defined live range identical to a
776  // single block, but we are going to return false in that case.
777
778  SlotIndex Start = LI.beginIndex();
779  if (Start.isBlock())
780    return nullptr;
781
782  SlotIndex Stop = LI.endIndex();
783  if (Stop.isBlock())
784    return nullptr;
785
786  // getMBBFromIndex doesn't need to search the MBB table when both indexes
787  // belong to proper instructions.
788  MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
789  MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
790  return MBB1 == MBB2 ? MBB1 : nullptr;
791}
792
793bool
794LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
795  for (const VNInfo *PHI : LI.valnos) {
796    if (PHI->isUnused() || !PHI->isPHIDef())
797      continue;
798    const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
799    // Conservatively return true instead of scanning huge predecessor lists.
800    if (PHIMBB->pred_size() > 100)
801      return true;
802    for (MachineBasicBlock::const_pred_iterator
803         PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI)
804      if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI)))
805        return true;
806  }
807  return false;
808}
809
810float
811LiveIntervals::getSpillWeight(bool isDef, bool isUse,
812                              const MachineBlockFrequencyInfo *MBFI,
813                              const MachineInstr *MI) {
814  BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent());
815  const float Scale = 1.0f / MBFI->getEntryFreq();
816  return (isDef + isUse) * (Freq.getFrequency() * Scale);
817}
818
819LiveRange::Segment
820LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) {
821  LiveInterval& Interval = createEmptyInterval(reg);
822  VNInfo* VN = Interval.getNextValue(
823    SlotIndex(getInstructionIndex(startInst).getRegSlot()),
824    getVNInfoAllocator());
825  LiveRange::Segment S(
826     SlotIndex(getInstructionIndex(startInst).getRegSlot()),
827     getMBBEndIdx(startInst->getParent()), VN);
828  Interval.addSegment(S);
829
830  return S;
831}
832
833
834//===----------------------------------------------------------------------===//
835//                          Register mask functions
836//===----------------------------------------------------------------------===//
837
838bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
839                                             BitVector &UsableRegs) {
840  if (LI.empty())
841    return false;
842  LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
843
844  // Use a smaller arrays for local live ranges.
845  ArrayRef<SlotIndex> Slots;
846  ArrayRef<const uint32_t*> Bits;
847  if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
848    Slots = getRegMaskSlotsInBlock(MBB->getNumber());
849    Bits = getRegMaskBitsInBlock(MBB->getNumber());
850  } else {
851    Slots = getRegMaskSlots();
852    Bits = getRegMaskBits();
853  }
854
855  // We are going to enumerate all the register mask slots contained in LI.
856  // Start with a binary search of RegMaskSlots to find a starting point.
857  ArrayRef<SlotIndex>::iterator SlotI =
858    std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
859  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
860
861  // No slots in range, LI begins after the last call.
862  if (SlotI == SlotE)
863    return false;
864
865  bool Found = false;
866  for (;;) {
867    assert(*SlotI >= LiveI->start);
868    // Loop over all slots overlapping this segment.
869    while (*SlotI < LiveI->end) {
870      // *SlotI overlaps LI. Collect mask bits.
871      if (!Found) {
872        // This is the first overlap. Initialize UsableRegs to all ones.
873        UsableRegs.clear();
874        UsableRegs.resize(TRI->getNumRegs(), true);
875        Found = true;
876      }
877      // Remove usable registers clobbered by this mask.
878      UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
879      if (++SlotI == SlotE)
880        return Found;
881    }
882    // *SlotI is beyond the current LI segment.
883    LiveI = LI.advanceTo(LiveI, *SlotI);
884    if (LiveI == LiveE)
885      return Found;
886    // Advance SlotI until it overlaps.
887    while (*SlotI < LiveI->start)
888      if (++SlotI == SlotE)
889        return Found;
890  }
891}
892
893//===----------------------------------------------------------------------===//
894//                         IntervalUpdate class.
895//===----------------------------------------------------------------------===//
896
897// HMEditor is a toolkit used by handleMove to trim or extend live intervals.
898class LiveIntervals::HMEditor {
899private:
900  LiveIntervals& LIS;
901  const MachineRegisterInfo& MRI;
902  const TargetRegisterInfo& TRI;
903  SlotIndex OldIdx;
904  SlotIndex NewIdx;
905  SmallPtrSet<LiveRange*, 8> Updated;
906  bool UpdateFlags;
907
908public:
909  HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
910           const TargetRegisterInfo& TRI,
911           SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
912    : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
913      UpdateFlags(UpdateFlags) {}
914
915  // FIXME: UpdateFlags is a workaround that creates live intervals for all
916  // physregs, even those that aren't needed for regalloc, in order to update
917  // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
918  // flags, and postRA passes will use a live register utility instead.
919  LiveRange *getRegUnitLI(unsigned Unit) {
920    if (UpdateFlags)
921      return &LIS.getRegUnit(Unit);
922    return LIS.getCachedRegUnit(Unit);
923  }
924
925  /// Update all live ranges touched by MI, assuming a move from OldIdx to
926  /// NewIdx.
927  void updateAllRanges(MachineInstr *MI) {
928    DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
929    bool hasRegMask = false;
930    for (MIOperands MO(MI); MO.isValid(); ++MO) {
931      if (MO->isRegMask())
932        hasRegMask = true;
933      if (!MO->isReg())
934        continue;
935      // Aggressively clear all kill flags.
936      // They are reinserted by VirtRegRewriter.
937      if (MO->isUse())
938        MO->setIsKill(false);
939
940      unsigned Reg = MO->getReg();
941      if (!Reg)
942        continue;
943      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
944        LiveInterval &LI = LIS.getInterval(Reg);
945        if (LI.hasSubRanges()) {
946          unsigned SubReg = MO->getSubReg();
947          unsigned LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
948          for (LiveInterval::SubRange &S : LI.subranges()) {
949            if ((S.LaneMask & LaneMask) == 0)
950              continue;
951            updateRange(S, Reg, S.LaneMask);
952          }
953        }
954        updateRange(LI, Reg, 0);
955        continue;
956      }
957
958      // For physregs, only update the regunits that actually have a
959      // precomputed live range.
960      for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
961        if (LiveRange *LR = getRegUnitLI(*Units))
962          updateRange(*LR, *Units, 0);
963    }
964    if (hasRegMask)
965      updateRegMaskSlots();
966  }
967
968private:
969  /// Update a single live range, assuming an instruction has been moved from
970  /// OldIdx to NewIdx.
971  void updateRange(LiveRange &LR, unsigned Reg, unsigned LaneMask) {
972    if (!Updated.insert(&LR).second)
973      return;
974    DEBUG({
975      dbgs() << "     ";
976      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
977        dbgs() << PrintReg(Reg);
978        if (LaneMask != 0)
979          dbgs() << format(" L%04X", LaneMask);
980      } else {
981        dbgs() << PrintRegUnit(Reg, &TRI);
982      }
983      dbgs() << ":\t" << LR << '\n';
984    });
985    if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
986      handleMoveDown(LR);
987    else
988      handleMoveUp(LR, Reg, LaneMask);
989    DEBUG(dbgs() << "        -->\t" << LR << '\n');
990    LR.verify();
991  }
992
993  /// Update LR to reflect an instruction has been moved downwards from OldIdx
994  /// to NewIdx.
995  ///
996  /// 1. Live def at OldIdx:
997  ///    Move def to NewIdx, assert endpoint after NewIdx.
998  ///
999  /// 2. Live def at OldIdx, killed at NewIdx:
1000  ///    Change to dead def at NewIdx.
1001  ///    (Happens when bundling def+kill together).
1002  ///
1003  /// 3. Dead def at OldIdx:
1004  ///    Move def to NewIdx, possibly across another live value.
1005  ///
1006  /// 4. Def at OldIdx AND at NewIdx:
1007  ///    Remove segment [OldIdx;NewIdx) and value defined at OldIdx.
1008  ///    (Happens when bundling multiple defs together).
1009  ///
1010  /// 5. Value read at OldIdx, killed before NewIdx:
1011  ///    Extend kill to NewIdx.
1012  ///
1013  void handleMoveDown(LiveRange &LR) {
1014    // First look for a kill at OldIdx.
1015    LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
1016    LiveRange::iterator E = LR.end();
1017    // Is LR even live at OldIdx?
1018    if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
1019      return;
1020
1021    // Handle a live-in value.
1022    if (!SlotIndex::isSameInstr(I->start, OldIdx)) {
1023      bool isKill = SlotIndex::isSameInstr(OldIdx, I->end);
1024      // If the live-in value already extends to NewIdx, there is nothing to do.
1025      if (!SlotIndex::isEarlierInstr(I->end, NewIdx))
1026        return;
1027      // Aggressively remove all kill flags from the old kill point.
1028      // Kill flags shouldn't be used while live intervals exist, they will be
1029      // reinserted by VirtRegRewriter.
1030      if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end))
1031        for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO)
1032          if (MO->isReg() && MO->isUse())
1033            MO->setIsKill(false);
1034      // Adjust I->end to reach NewIdx. This may temporarily make LR invalid by
1035      // overlapping ranges. Case 5 above.
1036      I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
1037      // If this was a kill, there may also be a def. Otherwise we're done.
1038      if (!isKill)
1039        return;
1040      ++I;
1041    }
1042
1043    // Check for a def at OldIdx.
1044    if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start))
1045      return;
1046    // We have a def at OldIdx.
1047    VNInfo *DefVNI = I->valno;
1048    assert(DefVNI->def == I->start && "Inconsistent def");
1049    DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber());
1050    // If the defined value extends beyond NewIdx, just move the def down.
1051    // This is case 1 above.
1052    if (SlotIndex::isEarlierInstr(NewIdx, I->end)) {
1053      I->start = DefVNI->def;
1054      return;
1055    }
1056    // The remaining possibilities are now:
1057    // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx).
1058    // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot().
1059    // In either case, it is possible that there is an existing def at NewIdx.
1060    assert((I->end == OldIdx.getDeadSlot() ||
1061            SlotIndex::isSameInstr(I->end, NewIdx)) &&
1062            "Cannot move def below kill");
1063    LiveRange::iterator NewI = LR.advanceTo(I, NewIdx.getRegSlot());
1064    if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) {
1065      // There is an existing def at NewIdx, case 4 above. The def at OldIdx is
1066      // coalesced into that value.
1067      assert(NewI->valno != DefVNI && "Multiple defs of value?");
1068      LR.removeValNo(DefVNI);
1069      return;
1070    }
1071    // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx.
1072    // If the def at OldIdx was dead, we allow it to be moved across other LR
1073    // values. The new range should be placed immediately before NewI, move any
1074    // intermediate ranges up.
1075    assert(NewI != I && "Inconsistent iterators");
1076    std::copy(std::next(I), NewI, I);
1077    *std::prev(NewI)
1078      = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
1079  }
1080
1081  /// Update LR to reflect an instruction has been moved upwards from OldIdx
1082  /// to NewIdx.
1083  ///
1084  /// 1. Live def at OldIdx:
1085  ///    Hoist def to NewIdx.
1086  ///
1087  /// 2. Dead def at OldIdx:
1088  ///    Hoist def+end to NewIdx, possibly move across other values.
1089  ///
1090  /// 3. Dead def at OldIdx AND existing def at NewIdx:
1091  ///    Remove value defined at OldIdx, coalescing it with existing value.
1092  ///
1093  /// 4. Live def at OldIdx AND existing def at NewIdx:
1094  ///    Remove value defined at NewIdx, hoist OldIdx def to NewIdx.
1095  ///    (Happens when bundling multiple defs together).
1096  ///
1097  /// 5. Value killed at OldIdx:
1098  ///    Hoist kill to NewIdx, then scan for last kill between NewIdx and
1099  ///    OldIdx.
1100  ///
1101  void handleMoveUp(LiveRange &LR, unsigned Reg, unsigned LaneMask) {
1102    // First look for a kill at OldIdx.
1103    LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
1104    LiveRange::iterator E = LR.end();
1105    // Is LR even live at OldIdx?
1106    if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
1107      return;
1108
1109    // Handle a live-in value.
1110    if (!SlotIndex::isSameInstr(I->start, OldIdx)) {
1111      // If the live-in value isn't killed here, there is nothing to do.
1112      if (!SlotIndex::isSameInstr(OldIdx, I->end))
1113        return;
1114      // Adjust I->end to end at NewIdx. If we are hoisting a kill above
1115      // another use, we need to search for that use. Case 5 above.
1116      I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
1117      ++I;
1118      // If OldIdx also defines a value, there couldn't have been another use.
1119      if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) {
1120        // No def, search for the new kill.
1121        // This can never be an early clobber kill since there is no def.
1122        std::prev(I)->end = findLastUseBefore(Reg, LaneMask).getRegSlot();
1123        return;
1124      }
1125    }
1126
1127    // Now deal with the def at OldIdx.
1128    assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?");
1129    VNInfo *DefVNI = I->valno;
1130    assert(DefVNI->def == I->start && "Inconsistent def");
1131    DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber());
1132
1133    // Check for an existing def at NewIdx.
1134    LiveRange::iterator NewI = LR.find(NewIdx.getRegSlot());
1135    if (SlotIndex::isSameInstr(NewI->start, NewIdx)) {
1136      assert(NewI->valno != DefVNI && "Same value defined more than once?");
1137      // There is an existing def at NewIdx.
1138      if (I->end.isDead()) {
1139        // Case 3: Remove the dead def at OldIdx.
1140        LR.removeValNo(DefVNI);
1141        return;
1142      }
1143      // Case 4: Replace def at NewIdx with live def at OldIdx.
1144      I->start = DefVNI->def;
1145      LR.removeValNo(NewI->valno);
1146      return;
1147    }
1148
1149    // There is no existing def at NewIdx. Hoist DefVNI.
1150    if (!I->end.isDead()) {
1151      // Leave the end point of a live def.
1152      I->start = DefVNI->def;
1153      return;
1154    }
1155
1156    // DefVNI is a dead def. It may have been moved across other values in LR,
1157    // so move I up to NewI. Slide [NewI;I) down one position.
1158    std::copy_backward(NewI, I, std::next(I));
1159    *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
1160  }
1161
1162  void updateRegMaskSlots() {
1163    SmallVectorImpl<SlotIndex>::iterator RI =
1164      std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
1165                       OldIdx);
1166    assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1167           "No RegMask at OldIdx.");
1168    *RI = NewIdx.getRegSlot();
1169    assert((RI == LIS.RegMaskSlots.begin() ||
1170            SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1171           "Cannot move regmask instruction above another call");
1172    assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1173            SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1174           "Cannot move regmask instruction below another call");
1175  }
1176
1177  // Return the last use of reg between NewIdx and OldIdx.
1178  SlotIndex findLastUseBefore(unsigned Reg, unsigned LaneMask) {
1179
1180    if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1181      SlotIndex LastUse = NewIdx;
1182      for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1183        unsigned SubReg = MO.getSubReg();
1184        if (SubReg != 0 && LaneMask != 0
1185            && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask) == 0)
1186          continue;
1187
1188        const MachineInstr *MI = MO.getParent();
1189        SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1190        if (InstSlot > LastUse && InstSlot < OldIdx)
1191          LastUse = InstSlot;
1192      }
1193      return LastUse;
1194    }
1195
1196    // This is a regunit interval, so scanning the use list could be very
1197    // expensive. Scan upwards from OldIdx instead.
1198    assert(NewIdx < OldIdx && "Expected upwards move");
1199    SlotIndexes *Indexes = LIS.getSlotIndexes();
1200    MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx);
1201
1202    // OldIdx may not correspond to an instruction any longer, so set MII to
1203    // point to the next instruction after OldIdx, or MBB->end().
1204    MachineBasicBlock::iterator MII = MBB->end();
1205    if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1206                           Indexes->getNextNonNullIndex(OldIdx)))
1207      if (MI->getParent() == MBB)
1208        MII = MI;
1209
1210    MachineBasicBlock::iterator Begin = MBB->begin();
1211    while (MII != Begin) {
1212      if ((--MII)->isDebugValue())
1213        continue;
1214      SlotIndex Idx = Indexes->getInstructionIndex(MII);
1215
1216      // Stop searching when NewIdx is reached.
1217      if (!SlotIndex::isEarlierInstr(NewIdx, Idx))
1218        return NewIdx;
1219
1220      // Check if MII uses Reg.
1221      for (MIBundleOperands MO(MII); MO.isValid(); ++MO)
1222        if (MO->isReg() &&
1223            TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
1224            TRI.hasRegUnit(MO->getReg(), Reg))
1225          return Idx;
1226    }
1227    // Didn't reach NewIdx. It must be the first instruction in the block.
1228    return NewIdx;
1229  }
1230};
1231
1232void LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) {
1233  assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
1234  SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1235  Indexes->removeMachineInstrFromMaps(MI);
1236  SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1237  assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
1238         OldIndex < getMBBEndIdx(MI->getParent()) &&
1239         "Cannot handle moves across basic block boundaries.");
1240
1241  HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1242  HME.updateAllRanges(MI);
1243}
1244
1245void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI,
1246                                         MachineInstr* BundleStart,
1247                                         bool UpdateFlags) {
1248  SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1249  SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1250  HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1251  HME.updateAllRanges(MI);
1252}
1253
1254void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1255                                        const MachineBasicBlock::iterator End,
1256                                        const SlotIndex endIdx,
1257                                        LiveRange &LR, const unsigned Reg,
1258                                        const unsigned LaneMask) {
1259  LiveInterval::iterator LII = LR.find(endIdx);
1260  SlotIndex lastUseIdx;
1261  if (LII != LR.end() && LII->start < endIdx)
1262    lastUseIdx = LII->end;
1263  else
1264    --LII;
1265
1266  for (MachineBasicBlock::iterator I = End; I != Begin;) {
1267    --I;
1268    MachineInstr *MI = I;
1269    if (MI->isDebugValue())
1270      continue;
1271
1272    SlotIndex instrIdx = getInstructionIndex(MI);
1273    bool isStartValid = getInstructionFromIndex(LII->start);
1274    bool isEndValid = getInstructionFromIndex(LII->end);
1275
1276    // FIXME: This doesn't currently handle early-clobber or multiple removed
1277    // defs inside of the region to repair.
1278    for (MachineInstr::mop_iterator OI = MI->operands_begin(),
1279         OE = MI->operands_end(); OI != OE; ++OI) {
1280      const MachineOperand &MO = *OI;
1281      if (!MO.isReg() || MO.getReg() != Reg)
1282        continue;
1283
1284      unsigned SubReg = MO.getSubReg();
1285      unsigned Mask = TRI->getSubRegIndexLaneMask(SubReg);
1286      if ((Mask & LaneMask) == 0)
1287        continue;
1288
1289      if (MO.isDef()) {
1290        if (!isStartValid) {
1291          if (LII->end.isDead()) {
1292            SlotIndex prevStart;
1293            if (LII != LR.begin())
1294              prevStart = std::prev(LII)->start;
1295
1296            // FIXME: This could be more efficient if there was a
1297            // removeSegment method that returned an iterator.
1298            LR.removeSegment(*LII, true);
1299            if (prevStart.isValid())
1300              LII = LR.find(prevStart);
1301            else
1302              LII = LR.begin();
1303          } else {
1304            LII->start = instrIdx.getRegSlot();
1305            LII->valno->def = instrIdx.getRegSlot();
1306            if (MO.getSubReg() && !MO.isUndef())
1307              lastUseIdx = instrIdx.getRegSlot();
1308            else
1309              lastUseIdx = SlotIndex();
1310            continue;
1311          }
1312        }
1313
1314        if (!lastUseIdx.isValid()) {
1315          VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1316          LiveRange::Segment S(instrIdx.getRegSlot(),
1317                               instrIdx.getDeadSlot(), VNI);
1318          LII = LR.addSegment(S);
1319        } else if (LII->start != instrIdx.getRegSlot()) {
1320          VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1321          LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1322          LII = LR.addSegment(S);
1323        }
1324
1325        if (MO.getSubReg() && !MO.isUndef())
1326          lastUseIdx = instrIdx.getRegSlot();
1327        else
1328          lastUseIdx = SlotIndex();
1329      } else if (MO.isUse()) {
1330        // FIXME: This should probably be handled outside of this branch,
1331        // either as part of the def case (for defs inside of the region) or
1332        // after the loop over the region.
1333        if (!isEndValid && !LII->end.isBlock())
1334          LII->end = instrIdx.getRegSlot();
1335        if (!lastUseIdx.isValid())
1336          lastUseIdx = instrIdx.getRegSlot();
1337      }
1338    }
1339  }
1340}
1341
1342void
1343LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
1344                                      MachineBasicBlock::iterator Begin,
1345                                      MachineBasicBlock::iterator End,
1346                                      ArrayRef<unsigned> OrigRegs) {
1347  // Find anchor points, which are at the beginning/end of blocks or at
1348  // instructions that already have indexes.
1349  while (Begin != MBB->begin() && !Indexes->hasIndex(Begin))
1350    --Begin;
1351  while (End != MBB->end() && !Indexes->hasIndex(End))
1352    ++End;
1353
1354  SlotIndex endIdx;
1355  if (End == MBB->end())
1356    endIdx = getMBBEndIdx(MBB).getPrevSlot();
1357  else
1358    endIdx = getInstructionIndex(End);
1359
1360  Indexes->repairIndexesInRange(MBB, Begin, End);
1361
1362  for (MachineBasicBlock::iterator I = End; I != Begin;) {
1363    --I;
1364    MachineInstr *MI = I;
1365    if (MI->isDebugValue())
1366      continue;
1367    for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
1368         MOE = MI->operands_end(); MOI != MOE; ++MOI) {
1369      if (MOI->isReg() &&
1370          TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
1371          !hasInterval(MOI->getReg())) {
1372        createAndComputeVirtRegInterval(MOI->getReg());
1373      }
1374    }
1375  }
1376
1377  for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) {
1378    unsigned Reg = OrigRegs[i];
1379    if (!TargetRegisterInfo::isVirtualRegister(Reg))
1380      continue;
1381
1382    LiveInterval &LI = getInterval(Reg);
1383    // FIXME: Should we support undefs that gain defs?
1384    if (!LI.hasAtLeastOneValue())
1385      continue;
1386
1387    for (LiveInterval::SubRange &S : LI.subranges()) {
1388      repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask);
1389    }
1390    repairOldRegInRange(Begin, End, endIdx, LI, Reg);
1391  }
1392}
1393
1394void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
1395  for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
1396    if (LiveRange *LR = getCachedRegUnit(*Units))
1397      if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1398        LR->removeValNo(VNI);
1399  }
1400}
1401
1402void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
1403  VNInfo *VNI = LI.getVNInfoAt(Pos);
1404  if (VNI == nullptr)
1405    return;
1406  LI.removeValNo(VNI);
1407
1408  // Also remove the value in subranges.
1409  for (LiveInterval::SubRange &S : LI.subranges()) {
1410    if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1411      S.removeValNo(SVNI);
1412  }
1413  LI.removeEmptySubRanges();
1414}
1415