contrib/llvm/lib/CodeGen/LiveIntervals.cpp

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