contrib/llvm/lib/CodeGen/SplitKit.cpp

   1 //===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
   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 contains the SplitAnalysis class as well as mutator functions for
  11 // live range splitting.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "SplitKit.h"
  16 #include "llvm/ADT/Statistic.h"
  17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  18 #include "llvm/CodeGen/LiveRangeEdit.h"
  19 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  20 #include "llvm/CodeGen/MachineDominators.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/MachineLoopInfo.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/CodeGen/VirtRegMap.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include "llvm/Target/TargetInstrInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "regalloc"
  33
  34 STATISTIC(NumFinished, "Number of splits finished");
  35 STATISTIC(NumSimple,   "Number of splits that were simple");
  36 STATISTIC(NumCopies,   "Number of copies inserted for splitting");
  37 STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
  38 STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
  39
  40 //===----------------------------------------------------------------------===//
  41 //                     Last Insert Point Analysis
  42 //===----------------------------------------------------------------------===//
  43
  44 InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
  45                                          unsigned BBNum)
  46     : LIS(lis), LastInsertPoint(BBNum) {}
  47
  48 SlotIndex
  49 InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
  50                                             const MachineBasicBlock &MBB) {
  51   unsigned Num = MBB.getNumber();
  52   std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
  53   SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);
  54
  55   SmallVector<const MachineBasicBlock *, 1> EHPadSucessors;
  56   for (const MachineBasicBlock *SMBB : MBB.successors())
  57     if (SMBB->isEHPad())
  58       EHPadSucessors.push_back(SMBB);
  59
  60   // Compute insert points on the first call. The pair is independent of the
  61   // current live interval.
  62   if (!LIP.first.isValid()) {
  63     MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();
  64     if (FirstTerm == MBB.end())
  65       LIP.first = MBBEnd;
  66     else
  67       LIP.first = LIS.getInstructionIndex(*FirstTerm);
  68
  69     // If there is a landing pad successor, also find the call instruction.
  70     if (EHPadSucessors.empty())
  71       return LIP.first;
  72     // There may not be a call instruction (?) in which case we ignore LPad.
  73     LIP.second = LIP.first;
  74     for (MachineBasicBlock::const_iterator I = MBB.end(), E = MBB.begin();
  75          I != E;) {
  76       --I;
  77       if (I->isCall()) {
  78         LIP.second = LIS.getInstructionIndex(*I);
  79         break;
  80       }
  81     }
  82   }
  83
  84   // If CurLI is live into a landing pad successor, move the last insert point
  85   // back to the call that may throw.
  86   if (!LIP.second)
  87     return LIP.first;
  88
  89   if (none_of(EHPadSucessors, [&](const MachineBasicBlock *EHPad) {
  90         return LIS.isLiveInToMBB(CurLI, EHPad);
  91       }))
  92     return LIP.first;
  93
  94   // Find the value leaving MBB.
  95   const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
  96   if (!VNI)
  97     return LIP.first;
  98
  99   // If the value leaving MBB was defined after the call in MBB, it can't
 100   // really be live-in to the landing pad.  This can happen if the landing pad
 101   // has a PHI, and this register is undef on the exceptional edge.
 102   // <rdar://problem/10664933>
 103   if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
 104     return LIP.first;
 105
 106   // Value is properly live-in to the landing pad.
 107   // Only allow inserts before the call.
 108   return LIP.second;
 109 }
 110
 111 MachineBasicBlock::iterator
 112 InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,
 113                                             MachineBasicBlock &MBB) {
 114   SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
 115   if (LIP == LIS.getMBBEndIdx(&MBB))
 116     return MBB.end();
 117   return LIS.getInstructionFromIndex(LIP);
 118 }
 119
 120 //===----------------------------------------------------------------------===//
 121 //                                 Split Analysis
 122 //===----------------------------------------------------------------------===//
 123
 124 SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
 125                              const MachineLoopInfo &mli)
 126     : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
 127       TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr),
 128       IPA(lis, MF.getNumBlockIDs()) {}
 129
 130 void SplitAnalysis::clear() {
 131   UseSlots.clear();
 132   UseBlocks.clear();
 133   ThroughBlocks.clear();
 134   CurLI = nullptr;
 135   DidRepairRange = false;
 136 }
 137
 138 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
 139 void SplitAnalysis::analyzeUses() {
 140   assert(UseSlots.empty() && "Call clear first");
 141
 142   // First get all the defs from the interval values. This provides the correct
 143   // slots for early clobbers.
 144   for (const VNInfo *VNI : CurLI->valnos)
 145     if (!VNI->isPHIDef() && !VNI->isUnused())
 146       UseSlots.push_back(VNI->def);
 147
 148   // Get use slots form the use-def chain.
 149   const MachineRegisterInfo &MRI = MF.getRegInfo();
 150   for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
 151     if (!MO.isUndef())
 152       UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());
 153
 154   array_pod_sort(UseSlots.begin(), UseSlots.end());
 155
 156   // Remove duplicates, keeping the smaller slot for each instruction.
 157   // That is what we want for early clobbers.
 158   UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
 159                              SlotIndex::isSameInstr),
 160                  UseSlots.end());
 161
 162   // Compute per-live block info.
 163   if (!calcLiveBlockInfo()) {
 164     // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
 165     // I am looking at you, RegisterCoalescer!
 166     DidRepairRange = true;
 167     ++NumRepairs;
 168     DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
 169     const_cast<LiveIntervals&>(LIS)
 170       .shrinkToUses(const_cast<LiveInterval*>(CurLI));
 171     UseBlocks.clear();
 172     ThroughBlocks.clear();
 173     bool fixed = calcLiveBlockInfo();
 174     (void)fixed;
 175     assert(fixed && "Couldn't fix broken live interval");
 176   }
 177
 178   DEBUG(dbgs() << "Analyze counted "
 179                << UseSlots.size() << " instrs in "
 180                << UseBlocks.size() << " blocks, through "
 181                << NumThroughBlocks << " blocks.\n");
 182 }
 183
 184 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
 185 /// where CurLI is live.
 186 bool SplitAnalysis::calcLiveBlockInfo() {
 187   ThroughBlocks.resize(MF.getNumBlockIDs());
 188   NumThroughBlocks = NumGapBlocks = 0;
 189   if (CurLI->empty())
 190     return true;
 191
 192   LiveInterval::const_iterator LVI = CurLI->begin();
 193   LiveInterval::const_iterator LVE = CurLI->end();
 194
 195   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
 196   UseI = UseSlots.begin();
 197   UseE = UseSlots.end();
 198
 199   // Loop over basic blocks where CurLI is live.
 200   MachineFunction::iterator MFI =
 201       LIS.getMBBFromIndex(LVI->start)->getIterator();
 202   for (;;) {
 203     BlockInfo BI;
 204     BI.MBB = &*MFI;
 205     SlotIndex Start, Stop;
 206     std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
 207
 208     // If the block contains no uses, the range must be live through. At one
 209     // point, RegisterCoalescer could create dangling ranges that ended
 210     // mid-block.
 211     if (UseI == UseE || *UseI >= Stop) {
 212       ++NumThroughBlocks;
 213       ThroughBlocks.set(BI.MBB->getNumber());
 214       // The range shouldn't end mid-block if there are no uses. This shouldn't
 215       // happen.
 216       if (LVI->end < Stop)
 217         return false;
 218     } else {
 219       // This block has uses. Find the first and last uses in the block.
 220       BI.FirstInstr = *UseI;
 221       assert(BI.FirstInstr >= Start);
 222       do ++UseI;
 223       while (UseI != UseE && *UseI < Stop);
 224       BI.LastInstr = UseI[-1];
 225       assert(BI.LastInstr < Stop);
 226
 227       // LVI is the first live segment overlapping MBB.
 228       BI.LiveIn = LVI->start <= Start;
 229
 230       // When not live in, the first use should be a def.
 231       if (!BI.LiveIn) {
 232         assert(LVI->start == LVI->valno->def && "Dangling Segment start");
 233         assert(LVI->start == BI.FirstInstr && "First instr should be a def");
 234         BI.FirstDef = BI.FirstInstr;
 235       }
 236
 237       // Look for gaps in the live range.
 238       BI.LiveOut = true;
 239       while (LVI->end < Stop) {
 240         SlotIndex LastStop = LVI->end;
 241         if (++LVI == LVE || LVI->start >= Stop) {
 242           BI.LiveOut = false;
 243           BI.LastInstr = LastStop;
 244           break;
 245         }
 246
 247         if (LastStop < LVI->start) {
 248           // There is a gap in the live range. Create duplicate entries for the
 249           // live-in snippet and the live-out snippet.
 250           ++NumGapBlocks;
 251
 252           // Push the Live-in part.
 253           BI.LiveOut = false;
 254           UseBlocks.push_back(BI);
 255           UseBlocks.back().LastInstr = LastStop;
 256
 257           // Set up BI for the live-out part.
 258           BI.LiveIn = false;
 259           BI.LiveOut = true;
 260           BI.FirstInstr = BI.FirstDef = LVI->start;
 261         }
 262
 263         // A Segment that starts in the middle of the block must be a def.
 264         assert(LVI->start == LVI->valno->def && "Dangling Segment start");
 265         if (!BI.FirstDef)
 266           BI.FirstDef = LVI->start;
 267       }
 268
 269       UseBlocks.push_back(BI);
 270
 271       // LVI is now at LVE or LVI->end >= Stop.
 272       if (LVI == LVE)
 273         break;
 274     }
 275
 276     // Live segment ends exactly at Stop. Move to the next segment.
 277     if (LVI->end == Stop && ++LVI == LVE)
 278       break;
 279
 280     // Pick the next basic block.
 281     if (LVI->start < Stop)
 282       ++MFI;
 283     else
 284       MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
 285   }
 286
 287   assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
 288   return true;
 289 }
 290
 291 unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
 292   if (cli->empty())
 293     return 0;
 294   LiveInterval *li = const_cast<LiveInterval*>(cli);
 295   LiveInterval::iterator LVI = li->begin();
 296   LiveInterval::iterator LVE = li->end();
 297   unsigned Count = 0;
 298
 299   // Loop over basic blocks where li is live.
 300   MachineFunction::const_iterator MFI =
 301       LIS.getMBBFromIndex(LVI->start)->getIterator();
 302   SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);
 303   for (;;) {
 304     ++Count;
 305     LVI = li->advanceTo(LVI, Stop);
 306     if (LVI == LVE)
 307       return Count;
 308     do {
 309       ++MFI;
 310       Stop = LIS.getMBBEndIdx(&*MFI);
 311     } while (Stop <= LVI->start);
 312   }
 313 }
 314
 315 bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
 316   unsigned OrigReg = VRM.getOriginal(CurLI->reg);
 317   const LiveInterval &Orig = LIS.getInterval(OrigReg);
 318   assert(!Orig.empty() && "Splitting empty interval?");
 319   LiveInterval::const_iterator I = Orig.find(Idx);
 320
 321   // Range containing Idx should begin at Idx.
 322   if (I != Orig.end() && I->start <= Idx)
 323     return I->start == Idx;
 324
 325   // Range does not contain Idx, previous must end at Idx.
 326   return I != Orig.begin() && (--I)->end == Idx;
 327 }
 328
 329 void SplitAnalysis::analyze(const LiveInterval *li) {
 330   clear();
 331   CurLI = li;
 332   analyzeUses();
 333 }
 334
 335
 336 //===----------------------------------------------------------------------===//
 337 //                               Split Editor
 338 //===----------------------------------------------------------------------===//
 339
 340 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
 341 SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa,
 342                          LiveIntervals &lis, VirtRegMap &vrm,
 343                          MachineDominatorTree &mdt,
 344                          MachineBlockFrequencyInfo &mbfi)
 345     : SA(sa), AA(aa), LIS(lis), VRM(vrm),
 346       MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt),
 347       TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
 348       TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
 349       MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition),
 350       RegAssign(Allocator) {}
 351
 352 void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
 353   Edit = &LRE;
 354   SpillMode = SM;
 355   OpenIdx = 0;
 356   RegAssign.clear();
 357   Values.clear();
 358
 359   // Reset the LiveRangeCalc instances needed for this spill mode.
 360   LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
 361                   &LIS.getVNInfoAllocator());
 362   if (SpillMode)
 363     LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
 364                     &LIS.getVNInfoAllocator());
 365
 366   // We don't need an AliasAnalysis since we will only be performing
 367   // cheap-as-a-copy remats anyway.
 368   Edit->anyRematerializable(nullptr);
 369 }
 370
 371 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 372 LLVM_DUMP_METHOD void SplitEditor::dump() const {
 373   if (RegAssign.empty()) {
 374     dbgs() << " empty\n";
 375     return;
 376   }
 377
 378   for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
 379     dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
 380   dbgs() << '\n';
 381 }
 382 #endif
 383
 384 LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
 385                                                         LiveInterval &LI) {
 386   for (LiveInterval::SubRange &S : LI.subranges())
 387     if (S.LaneMask == LM)
 388       return S;
 389   llvm_unreachable("SubRange for this mask not found");
 390 }
 391
 392 void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
 393   if (!LI.hasSubRanges()) {
 394     LI.createDeadDef(VNI);
 395     return;
 396   }
 397
 398   SlotIndex Def = VNI->def;
 399   if (Original) {
 400     // If we are transferring a def from the original interval, make sure
 401     // to only update the subranges for which the original subranges had
 402     // a def at this location.
 403     for (LiveInterval::SubRange &S : LI.subranges()) {
 404       auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
 405       VNInfo *PV = PS.getVNInfoAt(Def);
 406       if (PV != nullptr && PV->def == Def)
 407         S.createDeadDef(Def, LIS.getVNInfoAllocator());
 408     }
 409   } else {
 410     // This is a new def: either from rematerialization, or from an inserted
 411     // copy. Since rematerialization can regenerate a definition of a sub-
 412     // register, we need to check which subranges need to be updated.
 413     const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);
 414     assert(DefMI != nullptr);
 415     LaneBitmask LM;
 416     for (const MachineOperand &DefOp : DefMI->defs()) {
 417       unsigned R = DefOp.getReg();
 418       if (R != LI.reg)
 419         continue;
 420       if (unsigned SR = DefOp.getSubReg())
 421         LM |= TRI.getSubRegIndexLaneMask(SR);
 422       else {
 423         LM = MRI.getMaxLaneMaskForVReg(R);
 424         break;
 425       }
 426     }
 427     for (LiveInterval::SubRange &S : LI.subranges())
 428       if ((S.LaneMask & LM).any())
 429         S.createDeadDef(Def, LIS.getVNInfoAllocator());
 430   }
 431 }
 432
 433 VNInfo *SplitEditor::defValue(unsigned RegIdx,
 434                               const VNInfo *ParentVNI,
 435                               SlotIndex Idx,
 436                               bool Original) {
 437   assert(ParentVNI && "Mapping  NULL value");
 438   assert(Idx.isValid() && "Invalid SlotIndex");
 439   assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
 440   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
 441
 442   // Create a new value.
 443   VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
 444
 445   bool Force = LI->hasSubRanges();
 446   ValueForcePair FP(Force ? nullptr : VNI, Force);
 447   // Use insert for lookup, so we can add missing values with a second lookup.
 448   std::pair<ValueMap::iterator, bool> InsP =
 449     Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));
 450
 451   // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
 452   // forced. Keep it as a simple def without any liveness.
 453   if (!Force && InsP.second)
 454     return VNI;
 455
 456   // If the previous value was a simple mapping, add liveness for it now.
 457   if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
 458     addDeadDef(*LI, OldVNI, Original);
 459
 460     // No longer a simple mapping.  Switch to a complex mapping. If the
 461     // interval has subranges, make it a forced mapping.
 462     InsP.first->second = ValueForcePair(nullptr, Force);
 463   }
 464
 465   // This is a complex mapping, add liveness for VNI
 466   addDeadDef(*LI, VNI, Original);
 467   return VNI;
 468 }
 469
 470 void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
 471   assert(ParentVNI && "Mapping  NULL value");
 472   ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
 473   VNInfo *VNI = VFP.getPointer();
 474
 475   // ParentVNI was either unmapped or already complex mapped. Either way, just
 476   // set the force bit.
 477   if (!VNI) {
 478     VFP.setInt(true);
 479     return;
 480   }
 481
 482   // This was previously a single mapping. Make sure the old def is represented
 483   // by a trivial live range.
 484   addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
 485
 486   // Mark as complex mapped, forced.
 487   VFP = ValueForcePair(nullptr, true);
 488 }
 489
 490 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
 491                                    VNInfo *ParentVNI,
 492                                    SlotIndex UseIdx,
 493                                    MachineBasicBlock &MBB,
 494                                    MachineBasicBlock::iterator I) {
 495   MachineInstr *CopyMI = nullptr;
 496   SlotIndex Def;
 497   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
 498
 499   // We may be trying to avoid interference that ends at a deleted instruction,
 500   // so always begin RegIdx 0 early and all others late.
 501   bool Late = RegIdx != 0;
 502
 503   // Attempt cheap-as-a-copy rematerialization.
 504   unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
 505   LiveInterval &OrigLI = LIS.getInterval(Original);
 506   VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
 507
 508   bool DidRemat = false;
 509   if (OrigVNI) {
 510     LiveRangeEdit::Remat RM(ParentVNI);
 511     RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
 512     if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
 513       Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late);
 514       ++NumRemats;
 515       DidRemat = true;
 516     }
 517   }
 518   if (!DidRemat) {
 519     // Can't remat, just insert a copy from parent.
 520     CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
 521                .addReg(Edit->getReg());
 522     Def = LIS.getSlotIndexes()
 523               ->insertMachineInstrInMaps(*CopyMI, Late)
 524               .getRegSlot();
 525     ++NumCopies;
 526   }
 527
 528   // Define the value in Reg.
 529   return defValue(RegIdx, ParentVNI, Def, false);
 530 }
 531
 532 /// Create a new virtual register and live interval.
 533 unsigned SplitEditor::openIntv() {
 534   // Create the complement as index 0.
 535   if (Edit->empty())
 536     Edit->createEmptyInterval();
 537
 538   // Create the open interval.
 539   OpenIdx = Edit->size();
 540   Edit->createEmptyInterval();
 541   return OpenIdx;
 542 }
 543
 544 void SplitEditor::selectIntv(unsigned Idx) {
 545   assert(Idx != 0 && "Cannot select the complement interval");
 546   assert(Idx < Edit->size() && "Can only select previously opened interval");
 547   DEBUG(dbgs() << "    selectIntv " << OpenIdx << " -> " << Idx << '\n');
 548   OpenIdx = Idx;
 549 }
 550
 551 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
 552   assert(OpenIdx && "openIntv not called before enterIntvBefore");
 553   DEBUG(dbgs() << "    enterIntvBefore " << Idx);
 554   Idx = Idx.getBaseIndex();
 555   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
 556   if (!ParentVNI) {
 557     DEBUG(dbgs() << ": not live\n");
 558     return Idx;
 559   }
 560   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 561   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
 562   assert(MI && "enterIntvBefore called with invalid index");
 563
 564   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
 565   return VNI->def;
 566 }
 567
 568 SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {
 569   assert(OpenIdx && "openIntv not called before enterIntvAfter");
 570   DEBUG(dbgs() << "    enterIntvAfter " << Idx);
 571   Idx = Idx.getBoundaryIndex();
 572   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
 573   if (!ParentVNI) {
 574     DEBUG(dbgs() << ": not live\n");
 575     return Idx;
 576   }
 577   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 578   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
 579   assert(MI && "enterIntvAfter called with invalid index");
 580
 581   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
 582                               std::next(MachineBasicBlock::iterator(MI)));
 583   return VNI->def;
 584 }
 585
 586 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
 587   assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
 588   SlotIndex End = LIS.getMBBEndIdx(&MBB);
 589   SlotIndex Last = End.getPrevSlot();
 590   DEBUG(dbgs() << "    enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
 591   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
 592   if (!ParentVNI) {
 593     DEBUG(dbgs() << ": not live\n");
 594     return End;
 595   }
 596   DEBUG(dbgs() << ": valno " << ParentVNI->id);
 597   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
 598                               SA.getLastSplitPointIter(&MBB));
 599   RegAssign.insert(VNI->def, End, OpenIdx);
 600   DEBUG(dump());
 601   return VNI->def;
 602 }
 603
 604 /// useIntv - indicate that all instructions in MBB should use OpenLI.
 605 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
 606   useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
 607 }
 608
 609 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
 610   assert(OpenIdx && "openIntv not called before useIntv");
 611   DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
 612   RegAssign.insert(Start, End, OpenIdx);
 613   DEBUG(dump());
 614 }
 615
 616 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
 617   assert(OpenIdx && "openIntv not called before leaveIntvAfter");
 618   DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
 619
 620   // The interval must be live beyond the instruction at Idx.
 621   SlotIndex Boundary = Idx.getBoundaryIndex();
 622   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
 623   if (!ParentVNI) {
 624     DEBUG(dbgs() << ": not live\n");
 625     return Boundary.getNextSlot();
 626   }
 627   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 628   MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
 629   assert(MI && "No instruction at index");
 630
 631   // In spill mode, make live ranges as short as possible by inserting the copy
 632   // before MI.  This is only possible if that instruction doesn't redefine the
 633   // value.  The inserted COPY is not a kill, and we don't need to recompute
 634   // the source live range.  The spiller also won't try to hoist this copy.
 635   if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
 636       MI->readsVirtualRegister(Edit->getReg())) {
 637     forceRecompute(0, ParentVNI);
 638     defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
 639     return Idx;
 640   }
 641
 642   VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
 643                               std::next(MachineBasicBlock::iterator(MI)));
 644   return VNI->def;
 645 }
 646
 647 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
 648   assert(OpenIdx && "openIntv not called before leaveIntvBefore");
 649   DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
 650
 651   // The interval must be live into the instruction at Idx.
 652   Idx = Idx.getBaseIndex();
 653   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
 654   if (!ParentVNI) {
 655     DEBUG(dbgs() << ": not live\n");
 656     return Idx.getNextSlot();
 657   }
 658   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 659
 660   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
 661   assert(MI && "No instruction at index");
 662   VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
 663   return VNI->def;
 664 }
 665
 666 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
 667   assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
 668   SlotIndex Start = LIS.getMBBStartIdx(&MBB);
 669   DEBUG(dbgs() << "    leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
 670
 671   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
 672   if (!ParentVNI) {
 673     DEBUG(dbgs() << ": not live\n");
 674     return Start;
 675   }
 676
 677   VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
 678                               MBB.SkipPHIsLabelsAndDebug(MBB.begin()));
 679   RegAssign.insert(Start, VNI->def, OpenIdx);
 680   DEBUG(dump());
 681   return VNI->def;
 682 }
 683
 684 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
 685   assert(OpenIdx && "openIntv not called before overlapIntv");
 686   const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
 687   assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
 688          "Parent changes value in extended range");
 689   assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
 690          "Range cannot span basic blocks");
 691
 692   // The complement interval will be extended as needed by LRCalc.extend().
 693   if (ParentVNI)
 694     forceRecompute(0, ParentVNI);
 695   DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
 696   RegAssign.insert(Start, End, OpenIdx);
 697   DEBUG(dump());
 698 }
 699
 700 //===----------------------------------------------------------------------===//
 701 //                                  Spill modes
 702 //===----------------------------------------------------------------------===//
 703
 704 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
 705   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
 706   DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
 707   RegAssignMap::iterator AssignI;
 708   AssignI.setMap(RegAssign);
 709
 710   for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
 711     SlotIndex Def = Copies[i]->def;
 712     MachineInstr *MI = LIS.getInstructionFromIndex(Def);
 713     assert(MI && "No instruction for back-copy");
 714
 715     MachineBasicBlock *MBB = MI->getParent();
 716     MachineBasicBlock::iterator MBBI(MI);
 717     bool AtBegin;
 718     do AtBegin = MBBI == MBB->begin();
 719     while (!AtBegin && (--MBBI)->isDebugValue());
 720
 721     DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
 722     LIS.removeVRegDefAt(*LI, Def);
 723     LIS.RemoveMachineInstrFromMaps(*MI);
 724     MI->eraseFromParent();
 725
 726     // Adjust RegAssign if a register assignment is killed at Def. We want to
 727     // avoid calculating the live range of the source register if possible.
 728     AssignI.find(Def.getPrevSlot());
 729     if (!AssignI.valid() || AssignI.start() >= Def)
 730       continue;
 731     // If MI doesn't kill the assigned register, just leave it.
 732     if (AssignI.stop() != Def)
 733       continue;
 734     unsigned RegIdx = AssignI.value();
 735     if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
 736       DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx << '\n');
 737       forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
 738     } else {
 739       SlotIndex Kill = LIS.getInstructionIndex(*MBBI).getRegSlot();
 740       DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
 741       AssignI.setStop(Kill);
 742     }
 743   }
 744 }
 745
 746 MachineBasicBlock*
 747 SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
 748                                   MachineBasicBlock *DefMBB) {
 749   if (MBB == DefMBB)
 750     return MBB;
 751   assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
 752
 753   const MachineLoopInfo &Loops = SA.Loops;
 754   const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
 755   MachineDomTreeNode *DefDomNode = MDT[DefMBB];
 756
 757   // Best candidate so far.
 758   MachineBasicBlock *BestMBB = MBB;
 759   unsigned BestDepth = UINT_MAX;
 760
 761   for (;;) {
 762     const MachineLoop *Loop = Loops.getLoopFor(MBB);
 763
 764     // MBB isn't in a loop, it doesn't get any better.  All dominators have a
 765     // higher frequency by definition.
 766     if (!Loop) {
 767       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
 768                    << MBB->getNumber() << " at depth 0\n");
 769       return MBB;
 770     }
 771
 772     // We'll never be able to exit the DefLoop.
 773     if (Loop == DefLoop) {
 774       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
 775                    << MBB->getNumber() << " in the same loop\n");
 776       return MBB;
 777     }
 778
 779     // Least busy dominator seen so far.
 780     unsigned Depth = Loop->getLoopDepth();
 781     if (Depth < BestDepth) {
 782       BestMBB = MBB;
 783       BestDepth = Depth;
 784       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
 785                    << MBB->getNumber() << " at depth " << Depth << '\n');
 786     }
 787
 788     // Leave loop by going to the immediate dominator of the loop header.
 789     // This is a bigger stride than simply walking up the dominator tree.
 790     MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
 791
 792     // Too far up the dominator tree?
 793     if (!IDom || !MDT.dominates(DefDomNode, IDom))
 794       return BestMBB;
 795
 796     MBB = IDom->getBlock();
 797   }
 798 }
 799
 800 void SplitEditor::computeRedundantBackCopies(
 801     DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
 802   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
 803   LiveInterval *Parent = &Edit->getParent();
 804   SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
 805   SmallPtrSet<VNInfo *, 8> DominatedVNIs;
 806
 807   // Aggregate VNIs having the same value as ParentVNI.
 808   for (VNInfo *VNI : LI->valnos) {
 809     if (VNI->isUnused())
 810       continue;
 811     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
 812     EqualVNs[ParentVNI->id].insert(VNI);
 813   }
 814
 815   // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
 816   // redundant VNIs to BackCopies.
 817   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
 818     VNInfo *ParentVNI = Parent->getValNumInfo(i);
 819     if (!NotToHoistSet.count(ParentVNI->id))
 820       continue;
 821     SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
 822     SmallPtrSetIterator<VNInfo *> It2 = It1;
 823     for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
 824       It2 = It1;
 825       for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
 826         if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
 827           continue;
 828
 829         MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
 830         MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
 831         if (MBB1 == MBB2) {
 832           DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
 833         } else if (MDT.dominates(MBB1, MBB2)) {
 834           DominatedVNIs.insert(*It2);
 835         } else if (MDT.dominates(MBB2, MBB1)) {
 836           DominatedVNIs.insert(*It1);
 837         }
 838       }
 839     }
 840     if (!DominatedVNIs.empty()) {
 841       forceRecompute(0, ParentVNI);
 842       for (auto VNI : DominatedVNIs) {
 843         BackCopies.push_back(VNI);
 844       }
 845       DominatedVNIs.clear();
 846     }
 847   }
 848 }
 849
 850 /// For SM_Size mode, find a common dominator for all the back-copies for
 851 /// the same ParentVNI and hoist the backcopies to the dominator BB.
 852 /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
 853 /// to do the hoisting, simply remove the dominated backcopies for the same
 854 /// ParentVNI.
 855 void SplitEditor::hoistCopies() {
 856   // Get the complement interval, always RegIdx 0.
 857   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
 858   LiveInterval *Parent = &Edit->getParent();
 859
 860   // Track the nearest common dominator for all back-copies for each ParentVNI,
 861   // indexed by ParentVNI->id.
 862   typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair;
 863   SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
 864   // The total cost of all the back-copies for each ParentVNI.
 865   SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums());
 866   // The ParentVNI->id set for which hoisting back-copies are not beneficial
 867   // for Speed.
 868   DenseSet<unsigned> NotToHoistSet;
 869
 870   // Find the nearest common dominator for parent values with multiple
 871   // back-copies.  If a single back-copy dominates, put it in DomPair.second.
 872   for (VNInfo *VNI : LI->valnos) {
 873     if (VNI->isUnused())
 874       continue;
 875     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
 876     assert(ParentVNI && "Parent not live at complement def");
 877
 878     // Don't hoist remats.  The complement is probably going to disappear
 879     // completely anyway.
 880     if (Edit->didRematerialize(ParentVNI))
 881       continue;
 882
 883     MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
 884
 885     DomPair &Dom = NearestDom[ParentVNI->id];
 886
 887     // Keep directly defined parent values.  This is either a PHI or an
 888     // instruction in the complement range.  All other copies of ParentVNI
 889     // should be eliminated.
 890     if (VNI->def == ParentVNI->def) {
 891       DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
 892       Dom = DomPair(ValMBB, VNI->def);
 893       continue;
 894     }
 895     // Skip the singly mapped values.  There is nothing to gain from hoisting a
 896     // single back-copy.
 897     if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
 898       DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
 899       continue;
 900     }
 901
 902     if (!Dom.first) {
 903       // First time we see ParentVNI.  VNI dominates itself.
 904       Dom = DomPair(ValMBB, VNI->def);
 905     } else if (Dom.first == ValMBB) {
 906       // Two defs in the same block.  Pick the earlier def.
 907       if (!Dom.second.isValid() || VNI->def < Dom.second)
 908         Dom.second = VNI->def;
 909     } else {
 910       // Different basic blocks. Check if one dominates.
 911       MachineBasicBlock *Near =
 912         MDT.findNearestCommonDominator(Dom.first, ValMBB);
 913       if (Near == ValMBB)
 914         // Def ValMBB dominates.
 915         Dom = DomPair(ValMBB, VNI->def);
 916       else if (Near != Dom.first)
 917         // None dominate. Hoist to common dominator, need new def.
 918         Dom = DomPair(Near, SlotIndex());
 919       Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
 920     }
 921
 922     DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def
 923                  << " for parent " << ParentVNI->id << '@' << ParentVNI->def
 924                  << " hoist to BB#" << Dom.first->getNumber() << ' '
 925                  << Dom.second << '\n');
 926   }
 927
 928   // Insert the hoisted copies.
 929   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
 930     DomPair &Dom = NearestDom[i];
 931     if (!Dom.first || Dom.second.isValid())
 932       continue;
 933     // This value needs a hoisted copy inserted at the end of Dom.first.
 934     VNInfo *ParentVNI = Parent->getValNumInfo(i);
 935     MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
 936     // Get a less loopy dominator than Dom.first.
 937     Dom.first = findShallowDominator(Dom.first, DefMBB);
 938     if (SpillMode == SM_Speed &&
 939         MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
 940       NotToHoistSet.insert(ParentVNI->id);
 941       continue;
 942     }
 943     SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
 944     Dom.second =
 945       defFromParent(0, ParentVNI, Last, *Dom.first,
 946                     SA.getLastSplitPointIter(Dom.first))->def;
 947   }
 948
 949   // Remove redundant back-copies that are now known to be dominated by another
 950   // def with the same value.
 951   SmallVector<VNInfo*, 8> BackCopies;
 952   for (VNInfo *VNI : LI->valnos) {
 953     if (VNI->isUnused())
 954       continue;
 955     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
 956     const DomPair &Dom = NearestDom[ParentVNI->id];
 957     if (!Dom.first || Dom.second == VNI->def ||
 958         NotToHoistSet.count(ParentVNI->id))
 959       continue;
 960     BackCopies.push_back(VNI);
 961     forceRecompute(0, ParentVNI);
 962   }
 963
 964   // If it is not beneficial to hoist all the BackCopies, simply remove
 965   // redundant BackCopies in speed mode.
 966   if (SpillMode == SM_Speed && !NotToHoistSet.empty())
 967     computeRedundantBackCopies(NotToHoistSet, BackCopies);
 968
 969   removeBackCopies(BackCopies);
 970 }
 971
 972
 973 /// transferValues - Transfer all possible values to the new live ranges.
 974 /// Values that were rematerialized are left alone, they need LRCalc.extend().
 975 bool SplitEditor::transferValues() {
 976   bool Skipped = false;
 977   RegAssignMap::const_iterator AssignI = RegAssign.begin();
 978   for (const LiveRange::Segment &S : Edit->getParent()) {
 979     DEBUG(dbgs() << "  blit " << S << ':');
 980     VNInfo *ParentVNI = S.valno;
 981     // RegAssign has holes where RegIdx 0 should be used.
 982     SlotIndex Start = S.start;
 983     AssignI.advanceTo(Start);
 984     do {
 985       unsigned RegIdx;
 986       SlotIndex End = S.end;
 987       if (!AssignI.valid()) {
 988         RegIdx = 0;
 989       } else if (AssignI.start() <= Start) {
 990         RegIdx = AssignI.value();
 991         if (AssignI.stop() < End) {
 992           End = AssignI.stop();
 993           ++AssignI;
 994         }
 995       } else {
 996         RegIdx = 0;
 997         End = std::min(End, AssignI.start());
 998       }
 999
1000       // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1001       DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx
1002                    << '(' << PrintReg(Edit->get(RegIdx)) << ')');
1003       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1004
1005       // Check for a simply defined value that can be blitted directly.
1006       ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
1007       if (VNInfo *VNI = VFP.getPointer()) {
1008         DEBUG(dbgs() << ':' << VNI->id);
1009         LI.addSegment(LiveInterval::Segment(Start, End, VNI));
1010         Start = End;
1011         continue;
1012       }
1013
1014       // Skip values with forced recomputation.
1015       if (VFP.getInt()) {
1016         DEBUG(dbgs() << "(recalc)");
1017         Skipped = true;
1018         Start = End;
1019         continue;
1020       }
1021
1022       LiveRangeCalc &LRC = getLRCalc(RegIdx);
1023
1024       // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1025       // so the live range is accurate. Add live-in blocks in [Start;End) to the
1026       // LiveInBlocks.
1027       MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
1028       SlotIndex BlockStart, BlockEnd;
1029       std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
1030
1031       // The first block may be live-in, or it may have its own def.
1032       if (Start != BlockStart) {
1033         VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1034         assert(VNI && "Missing def for complex mapped value");
1035         DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
1036         // MBB has its own def. Is it also live-out?
1037         if (BlockEnd <= End)
1038           LRC.setLiveOutValue(&*MBB, VNI);
1039
1040         // Skip to the next block for live-in.
1041         ++MBB;
1042         BlockStart = BlockEnd;
1043       }
1044
1045       // Handle the live-in blocks covered by [Start;End).
1046       assert(Start <= BlockStart && "Expected live-in block");
1047       while (BlockStart < End) {
1048         DEBUG(dbgs() << ">BB#" << MBB->getNumber());
1049         BlockEnd = LIS.getMBBEndIdx(&*MBB);
1050         if (BlockStart == ParentVNI->def) {
1051           // This block has the def of a parent PHI, so it isn't live-in.
1052           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
1053           VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1054           assert(VNI && "Missing def for complex mapped parent PHI");
1055           if (End >= BlockEnd)
1056             LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
1057         } else {
1058           // This block needs a live-in value.  The last block covered may not
1059           // be live-out.
1060           if (End < BlockEnd)
1061             LRC.addLiveInBlock(LI, MDT[&*MBB], End);
1062           else {
1063             // Live-through, and we don't know the value.
1064             LRC.addLiveInBlock(LI, MDT[&*MBB]);
1065             LRC.setLiveOutValue(&*MBB, nullptr);
1066           }
1067         }
1068         BlockStart = BlockEnd;
1069         ++MBB;
1070       }
1071       Start = End;
1072     } while (Start != S.end);
1073     DEBUG(dbgs() << '\n');
1074   }
1075
1076   LRCalc[0].calculateValues();
1077   if (SpillMode)
1078     LRCalc[1].calculateValues();
1079
1080   return Skipped;
1081 }
1082
1083 static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) {
1084   const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
1085   if (Seg == nullptr)
1086     return true;
1087   if (Seg->end != Def.getDeadSlot())
1088     return false;
1089   // This is a dead PHI. Remove it.
1090   LR.removeSegment(*Seg, true);
1091   return true;
1092 }
1093
1094 void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC,
1095                                  LiveRange &LR, LaneBitmask LM,
1096                                  ArrayRef<SlotIndex> Undefs) {
1097   for (MachineBasicBlock *P : B.predecessors()) {
1098     SlotIndex End = LIS.getMBBEndIdx(P);
1099     SlotIndex LastUse = End.getPrevSlot();
1100     // The predecessor may not have a live-out value. That is OK, like an
1101     // undef PHI operand.
1102     LiveInterval &PLI = Edit->getParent();
1103     // Need the cast because the inputs to ?: would otherwise be deemed
1104     // "incompatible": SubRange vs LiveInterval.
1105     LiveRange &PSR = !LM.all() ? getSubRangeForMask(LM, PLI)
1106                                : static_cast<LiveRange&>(PLI);
1107     if (PSR.liveAt(LastUse))
1108       LRC.extend(LR, End, /*PhysReg=*/0, Undefs);
1109   }
1110 }
1111
1112 void SplitEditor::extendPHIKillRanges() {
1113   // Extend live ranges to be live-out for successor PHI values.
1114
1115   // Visit each PHI def slot in the parent live interval. If the def is dead,
1116   // remove it. Otherwise, extend the live interval to reach the end indexes
1117   // of all predecessor blocks.
1118
1119   LiveInterval &ParentLI = Edit->getParent();
1120   for (const VNInfo *V : ParentLI.valnos) {
1121     if (V->isUnused() || !V->isPHIDef())
1122       continue;
1123
1124     unsigned RegIdx = RegAssign.lookup(V->def);
1125     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1126     LiveRangeCalc &LRC = getLRCalc(RegIdx);
1127     MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1128     if (!removeDeadSegment(V->def, LI))
1129       extendPHIRange(B, LRC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
1130   }
1131
1132   SmallVector<SlotIndex, 4> Undefs;
1133   LiveRangeCalc SubLRC;
1134
1135   for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
1136     for (const VNInfo *V : PS.valnos) {
1137       if (V->isUnused() || !V->isPHIDef())
1138         continue;
1139       unsigned RegIdx = RegAssign.lookup(V->def);
1140       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1141       LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI);
1142       if (removeDeadSegment(V->def, S))
1143         continue;
1144
1145       MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1146       SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1147                    &LIS.getVNInfoAllocator());
1148       Undefs.clear();
1149       LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
1150       extendPHIRange(B, SubLRC, S, PS.LaneMask, Undefs);
1151     }
1152   }
1153 }
1154
1155 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1156 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
1157   struct ExtPoint {
1158     ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
1159       : MO(O), RegIdx(R), Next(N) {}
1160     MachineOperand MO;
1161     unsigned RegIdx;
1162     SlotIndex Next;
1163   };
1164
1165   SmallVector<ExtPoint,4> ExtPoints;
1166
1167   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
1168        RE = MRI.reg_end(); RI != RE;) {
1169     MachineOperand &MO = *RI;
1170     MachineInstr *MI = MO.getParent();
1171     ++RI;
1172     // LiveDebugVariables should have handled all DBG_VALUE instructions.
1173     if (MI->isDebugValue()) {
1174       DEBUG(dbgs() << "Zapping " << *MI);
1175       MO.setReg(0);
1176       continue;
1177     }
1178
1179     // <undef> operands don't really read the register, so it doesn't matter
1180     // which register we choose.  When the use operand is tied to a def, we must
1181     // use the same register as the def, so just do that always.
1182     SlotIndex Idx = LIS.getInstructionIndex(*MI);
1183     if (MO.isDef() || MO.isUndef())
1184       Idx = Idx.getRegSlot(MO.isEarlyClobber());
1185
1186     // Rewrite to the mapped register at Idx.
1187     unsigned RegIdx = RegAssign.lookup(Idx);
1188     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1189     MO.setReg(LI.reg);
1190     DEBUG(dbgs() << "  rewr BB#" << MI->getParent()->getNumber() << '\t'
1191                  << Idx << ':' << RegIdx << '\t' << *MI);
1192
1193     // Extend liveness to Idx if the instruction reads reg.
1194     if (!ExtendRanges || MO.isUndef())
1195       continue;
1196
1197     // Skip instructions that don't read Reg.
1198     if (MO.isDef()) {
1199       if (!MO.getSubReg() && !MO.isEarlyClobber())
1200         continue;
1201       // We may want to extend a live range for a partial redef, or for a use
1202       // tied to an early clobber.
1203       Idx = Idx.getPrevSlot();
1204       if (!Edit->getParent().liveAt(Idx))
1205         continue;
1206     } else
1207       Idx = Idx.getRegSlot(true);
1208
1209     SlotIndex Next = Idx.getNextSlot();
1210     if (LI.hasSubRanges()) {
1211       // We have to delay extending subranges until we have seen all operands
1212       // defining the register. This is because a <def,read-undef> operand
1213       // will create an "undef" point, and we cannot extend any subranges
1214       // until all of them have been accounted for.
1215       if (MO.isUse())
1216         ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1217     } else {
1218       LiveRangeCalc &LRC = getLRCalc(RegIdx);
1219       LRC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
1220     }
1221   }
1222
1223   for (ExtPoint &EP : ExtPoints) {
1224     LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
1225     assert(LI.hasSubRanges());
1226
1227     LiveRangeCalc SubLRC;
1228     unsigned Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1229     LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
1230                               : MRI.getMaxLaneMaskForVReg(Reg);
1231     for (LiveInterval::SubRange &S : LI.subranges()) {
1232       if ((S.LaneMask & LM).none())
1233         continue;
1234       // The problem here can be that the new register may have been created
1235       // for a partially defined original register. For example:
1236       //   %vreg827:subreg_hireg<def,read-undef> = ...
1237       //   ...
1238       //   %vreg828<def> = COPY %vreg827
1239       if (S.empty())
1240         continue;
1241       SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1242                    &LIS.getVNInfoAllocator());
1243       SmallVector<SlotIndex, 4> Undefs;
1244       LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
1245       SubLRC.extend(S, EP.Next, 0, Undefs);
1246     }
1247   }
1248
1249   for (unsigned R : *Edit) {
1250     LiveInterval &LI = LIS.getInterval(R);
1251     if (!LI.hasSubRanges())
1252       continue;
1253     LI.clear();
1254     LI.removeEmptySubRanges();
1255     LIS.constructMainRangeFromSubranges(LI);
1256   }
1257 }
1258
1259 void SplitEditor::deleteRematVictims() {
1260   SmallVector<MachineInstr*, 8> Dead;
1261   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
1262     LiveInterval *LI = &LIS.getInterval(*I);
1263     for (const LiveRange::Segment &S : LI->segments) {
1264       // Dead defs end at the dead slot.
1265       if (S.end != S.valno->def.getDeadSlot())
1266         continue;
1267       if (S.valno->isPHIDef())
1268         continue;
1269       MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1270       assert(MI && "Missing instruction for dead def");
1271       MI->addRegisterDead(LI->reg, &TRI);
1272
1273       if (!MI->allDefsAreDead())
1274         continue;
1275
1276       DEBUG(dbgs() << "All defs dead: " << *MI);
1277       Dead.push_back(MI);
1278     }
1279   }
1280
1281   if (Dead.empty())
1282     return;
1283
1284   Edit->eliminateDeadDefs(Dead, None, &AA);
1285 }
1286
1287 void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
1288   ++NumFinished;
1289
1290   // At this point, the live intervals in Edit contain VNInfos corresponding to
1291   // the inserted copies.
1292
1293   // Add the original defs from the parent interval.
1294   for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1295     if (ParentVNI->isUnused())
1296       continue;
1297     unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1298     defValue(RegIdx, ParentVNI, ParentVNI->def, true);
1299
1300     // Force rematted values to be recomputed everywhere.
1301     // The new live ranges may be truncated.
1302     if (Edit->didRematerialize(ParentVNI))
1303       for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1304         forceRecompute(i, ParentVNI);
1305   }
1306
1307   // Hoist back-copies to the complement interval when in spill mode.
1308   switch (SpillMode) {
1309   case SM_Partition:
1310     // Leave all back-copies as is.
1311     break;
1312   case SM_Size:
1313   case SM_Speed:
1314     // hoistCopies will behave differently between size and speed.
1315     hoistCopies();
1316   }
1317
1318   // Transfer the simply mapped values, check if any are skipped.
1319   bool Skipped = transferValues();
1320
1321   // Rewrite virtual registers, possibly extending ranges.
1322   rewriteAssigned(Skipped);
1323
1324   if (Skipped)
1325     extendPHIKillRanges();
1326   else
1327     ++NumSimple;
1328
1329   // Delete defs that were rematted everywhere.
1330   if (Skipped)
1331     deleteRematVictims();
1332
1333   // Get rid of unused values and set phi-kill flags.
1334   for (unsigned Reg : *Edit) {
1335     LiveInterval &LI = LIS.getInterval(Reg);
1336     LI.removeEmptySubRanges();
1337     LI.RenumberValues();
1338   }
1339
1340   // Provide a reverse mapping from original indices to Edit ranges.
1341   if (LRMap) {
1342     LRMap->clear();
1343     for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1344       LRMap->push_back(i);
1345   }
1346
1347   // Now check if any registers were separated into multiple components.
1348   ConnectedVNInfoEqClasses ConEQ(LIS);
1349   for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1350     // Don't use iterators, they are invalidated by create() below.
1351     unsigned VReg = Edit->get(i);
1352     LiveInterval &LI = LIS.getInterval(VReg);
1353     SmallVector<LiveInterval*, 8> SplitLIs;
1354     LIS.splitSeparateComponents(LI, SplitLIs);
1355     unsigned Original = VRM.getOriginal(VReg);
1356     for (LiveInterval *SplitLI : SplitLIs)
1357       VRM.setIsSplitFromReg(SplitLI->reg, Original);
1358
1359     // The new intervals all map back to i.
1360     if (LRMap)
1361       LRMap->resize(Edit->size(), i);
1362   }
1363
1364   // Calculate spill weight and allocation hints for new intervals.
1365   Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI);
1366
1367   assert(!LRMap || LRMap->size() == Edit->size());
1368 }
1369
1370
1371 //===----------------------------------------------------------------------===//
1372 //                            Single Block Splitting
1373 //===----------------------------------------------------------------------===//
1374
1375 bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,
1376                                            bool SingleInstrs) const {
1377   // Always split for multiple instructions.
1378   if (!BI.isOneInstr())
1379     return true;
1380   // Don't split for single instructions unless explicitly requested.
1381   if (!SingleInstrs)
1382     return false;
1383   // Splitting a live-through range always makes progress.
1384   if (BI.LiveIn && BI.LiveOut)
1385     return true;
1386   // No point in isolating a copy. It has no register class constraints.
1387   if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
1388     return false;
1389   // Finally, don't isolate an end point that was created by earlier splits.
1390   return isOriginalEndpoint(BI.FirstInstr);
1391 }
1392
1393 void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) {
1394   openIntv();
1395   SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
1396   SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
1397     LastSplitPoint));
1398   if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1399     useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1400   } else {
1401       // The last use is after the last valid split point.
1402     SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1403     useIntv(SegStart, SegStop);
1404     overlapIntv(SegStop, BI.LastInstr);
1405   }
1406 }
1407
1408
1409 //===----------------------------------------------------------------------===//
1410 //                    Global Live Range Splitting Support
1411 //===----------------------------------------------------------------------===//
1412
1413 // These methods support a method of global live range splitting that uses a
1414 // global algorithm to decide intervals for CFG edges. They will insert split
1415 // points and color intervals in basic blocks while avoiding interference.
1416 //
1417 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1418 // are on the stack.
1419
1420 void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
1421                                         unsigned IntvIn, SlotIndex LeaveBefore,
1422                                         unsigned IntvOut, SlotIndex EnterAfter){
1423   SlotIndex Start, Stop;
1424   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1425
1426   DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop
1427                << ") intf " << LeaveBefore << '-' << EnterAfter
1428                << ", live-through " << IntvIn << " -> " << IntvOut);
1429
1430   assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1431
1432   assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1433   assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1434   assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1435
1436   MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
1437
1438   if (!IntvOut) {
1439     DEBUG(dbgs() << ", spill on entry.\n");
1440     //
1441     //        <<<<<<<<<    Possible LeaveBefore interference.
1442     //    |-----------|    Live through.
1443     //    -____________    Spill on entry.
1444     //
1445     selectIntv(IntvIn);
1446     SlotIndex Idx = leaveIntvAtTop(*MBB);
1447     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1448     (void)Idx;
1449     return;
1450   }
1451
1452   if (!IntvIn) {
1453     DEBUG(dbgs() << ", reload on exit.\n");
1454     //
1455     //    >>>>>>>          Possible EnterAfter interference.
1456     //    |-----------|    Live through.
1457     //    ___________--    Reload on exit.
1458     //
1459     selectIntv(IntvOut);
1460     SlotIndex Idx = enterIntvAtEnd(*MBB);
1461     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1462     (void)Idx;
1463     return;
1464   }
1465
1466   if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1467     DEBUG(dbgs() << ", straight through.\n");
1468     //
1469     //    |-----------|    Live through.
1470     //    -------------    Straight through, same intv, no interference.
1471     //
1472     selectIntv(IntvOut);
1473     useIntv(Start, Stop);
1474     return;
1475   }
1476
1477   // We cannot legally insert splits after LSP.
1478   SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1479   assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1480
1481   if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1482                   LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1483     DEBUG(dbgs() << ", switch avoiding interference.\n");
1484     //
1485     //    >>>>     <<<<    Non-overlapping EnterAfter/LeaveBefore interference.
1486     //    |-----------|    Live through.
1487     //    ------=======    Switch intervals between interference.
1488     //
1489     selectIntv(IntvOut);
1490     SlotIndex Idx;
1491     if (LeaveBefore && LeaveBefore < LSP) {
1492       Idx = enterIntvBefore(LeaveBefore);
1493       useIntv(Idx, Stop);
1494     } else {
1495       Idx = enterIntvAtEnd(*MBB);
1496     }
1497     selectIntv(IntvIn);
1498     useIntv(Start, Idx);
1499     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1500     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1501     return;
1502   }
1503
1504   DEBUG(dbgs() << ", create local intv for interference.\n");
1505   //
1506   //    >>><><><><<<<    Overlapping EnterAfter/LeaveBefore interference.
1507   //    |-----------|    Live through.
1508   //    ==---------==    Switch intervals before/after interference.
1509   //
1510   assert(LeaveBefore <= EnterAfter && "Missed case");
1511
1512   selectIntv(IntvOut);
1513   SlotIndex Idx = enterIntvAfter(EnterAfter);
1514   useIntv(Idx, Stop);
1515   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1516
1517   selectIntv(IntvIn);
1518   Idx = leaveIntvBefore(LeaveBefore);
1519   useIntv(Start, Idx);
1520   assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1521 }
1522
1523
1524 void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
1525                                   unsigned IntvIn, SlotIndex LeaveBefore) {
1526   SlotIndex Start, Stop;
1527   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1528
1529   DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1530                << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1531                << ", reg-in " << IntvIn << ", leave before " << LeaveBefore
1532                << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1533
1534   assert(IntvIn && "Must have register in");
1535   assert(BI.LiveIn && "Must be live-in");
1536   assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1537
1538   if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1539     DEBUG(dbgs() << " before interference.\n");
1540     //
1541     //               <<<    Interference after kill.
1542     //     |---o---x   |    Killed in block.
1543     //     =========        Use IntvIn everywhere.
1544     //
1545     selectIntv(IntvIn);
1546     useIntv(Start, BI.LastInstr);
1547     return;
1548   }
1549
1550   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1551
1552   if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1553     //
1554     //               <<<    Possible interference after last use.
1555     //     |---o---o---|    Live-out on stack.
1556     //     =========____    Leave IntvIn after last use.
1557     //
1558     //                 <    Interference after last use.
1559     //     |---o---o--o|    Live-out on stack, late last use.
1560     //     ============     Copy to stack after LSP, overlap IntvIn.
1561     //            \_____    Stack interval is live-out.
1562     //
1563     if (BI.LastInstr < LSP) {
1564       DEBUG(dbgs() << ", spill after last use before interference.\n");
1565       selectIntv(IntvIn);
1566       SlotIndex Idx = leaveIntvAfter(BI.LastInstr);
1567       useIntv(Start, Idx);
1568       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1569     } else {
1570       DEBUG(dbgs() << ", spill before last split point.\n");
1571       selectIntv(IntvIn);
1572       SlotIndex Idx = leaveIntvBefore(LSP);
1573       overlapIntv(Idx, BI.LastInstr);
1574       useIntv(Start, Idx);
1575       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1576     }
1577     return;
1578   }
1579
1580   // The interference is overlapping somewhere we wanted to use IntvIn. That
1581   // means we need to create a local interval that can be allocated a
1582   // different register.
1583   unsigned LocalIntv = openIntv();
1584   (void)LocalIntv;
1585   DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1586
1587   if (!BI.LiveOut || BI.LastInstr < LSP) {
1588     //
1589     //           <<<<<<<    Interference overlapping uses.
1590     //     |---o---o---|    Live-out on stack.
1591     //     =====----____    Leave IntvIn before interference, then spill.
1592     //
1593     SlotIndex To = leaveIntvAfter(BI.LastInstr);
1594     SlotIndex From = enterIntvBefore(LeaveBefore);
1595     useIntv(From, To);
1596     selectIntv(IntvIn);
1597     useIntv(Start, From);
1598     assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1599     return;
1600   }
1601
1602   //           <<<<<<<    Interference overlapping uses.
1603   //     |---o---o--o|    Live-out on stack, late last use.
1604   //     =====-------     Copy to stack before LSP, overlap LocalIntv.
1605   //            \_____    Stack interval is live-out.
1606   //
1607   SlotIndex To = leaveIntvBefore(LSP);
1608   overlapIntv(To, BI.LastInstr);
1609   SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1610   useIntv(From, To);
1611   selectIntv(IntvIn);
1612   useIntv(Start, From);
1613   assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1614 }
1615
1616 void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
1617                                    unsigned IntvOut, SlotIndex EnterAfter) {
1618   SlotIndex Start, Stop;
1619   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1620
1621   DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1622                << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1623                << ", reg-out " << IntvOut << ", enter after " << EnterAfter
1624                << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1625
1626   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1627
1628   assert(IntvOut && "Must have register out");
1629   assert(BI.LiveOut && "Must be live-out");
1630   assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1631
1632   if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1633     DEBUG(dbgs() << " after interference.\n");
1634     //
1635     //    >>>>             Interference before def.
1636     //    |   o---o---|    Defined in block.
1637     //        =========    Use IntvOut everywhere.
1638     //
1639     selectIntv(IntvOut);
1640     useIntv(BI.FirstInstr, Stop);
1641     return;
1642   }
1643
1644   if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1645     DEBUG(dbgs() << ", reload after interference.\n");
1646     //
1647     //    >>>>             Interference before def.
1648     //    |---o---o---|    Live-through, stack-in.
1649     //    ____=========    Enter IntvOut before first use.
1650     //
1651     selectIntv(IntvOut);
1652     SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1653     useIntv(Idx, Stop);
1654     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1655     return;
1656   }
1657
1658   // The interference is overlapping somewhere we wanted to use IntvOut. That
1659   // means we need to create a local interval that can be allocated a
1660   // different register.
1661   DEBUG(dbgs() << ", interference overlaps uses.\n");
1662   //
1663   //    >>>>>>>          Interference overlapping uses.
1664   //    |---o---o---|    Live-through, stack-in.
1665   //    ____---======    Create local interval for interference range.
1666   //
1667   selectIntv(IntvOut);
1668   SlotIndex Idx = enterIntvAfter(EnterAfter);
1669   useIntv(Idx, Stop);
1670   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1671
1672   openIntv();
1673   SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
1674   useIntv(From, Idx);
1675 }