LCOV - code coverage report
Current view: top level - lib/CodeGen - SplitKit.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 764 811 94.2 %
Date: 2017-09-14 15:23:50 Functions: 43 47 91.5 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13