LCOV - code coverage report
Current view: top level - lib/CodeGen - SplitKit.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 642 681 94.3 %
Date: 2018-06-17 00:07:59 Functions: 44 48 91.7 %
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/LiveIntervals.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/TargetInstrInfo.h"
      38             : #include "llvm/CodeGen/TargetOpcodes.h"
      39             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      40             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      41             : #include "llvm/CodeGen/VirtRegMap.h"
      42             : #include "llvm/Config/llvm-config.h"
      43             : #include "llvm/IR/DebugLoc.h"
      44             : #include "llvm/MC/LaneBitmask.h"
      45             : #include "llvm/Support/Allocator.h"
      46             : #include "llvm/Support/BlockFrequency.h"
      47             : #include "llvm/Support/Compiler.h"
      48             : #include "llvm/Support/Debug.h"
      49             : #include "llvm/Support/ErrorHandling.h"
      50             : #include "llvm/Support/raw_ostream.h"
      51             : #include <algorithm>
      52             : #include <cassert>
      53             : #include <iterator>
      54             : #include <limits>
      55             : #include <tuple>
      56             : #include <utility>
      57             : 
      58             : using namespace llvm;
      59             : 
      60             : #define DEBUG_TYPE "regalloc"
      61             : 
      62             : STATISTIC(NumFinished, "Number of splits finished");
      63             : STATISTIC(NumSimple,   "Number of splits that were simple");
      64             : STATISTIC(NumCopies,   "Number of copies inserted for splitting");
      65             : STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
      66             : STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
      67             : 
      68             : //===----------------------------------------------------------------------===//
      69             : //                     Last Insert Point Analysis
      70             : //===----------------------------------------------------------------------===//
      71             : 
      72      179260 : InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
      73      358295 :                                          unsigned BBNum)
      74     1074885 :     : LIS(lis), LastInsertPoint(BBNum) {}
      75             : 
      76             : SlotIndex
      77      543571 : InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
      78             :                                             const MachineBasicBlock &MBB) {
      79      543571 :   unsigned Num = MBB.getNumber();
      80      543571 :   std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
      81      543571 :   SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);
      82             : 
      83             :   SmallVector<const MachineBasicBlock *, 1> EHPadSuccessors;
      84     1608091 :   for (const MachineBasicBlock *SMBB : MBB.successors())
      85     1064520 :     if (SMBB->isEHPad())
      86      502002 :       EHPadSuccessors.push_back(SMBB);
      87             : 
      88             :   // Compute insert points on the first call. The pair is independent of the
      89             :   // current live interval.
      90      543571 :   if (!LIP.first.isValid()) {
      91             :     MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();
      92       59095 :     if (FirstTerm == MBB.end())
      93        8752 :       LIP.first = MBBEnd;
      94             :     else
      95      100686 :       LIP.first = LIS.getInstructionIndex(*FirstTerm);
      96             : 
      97             :     // If there is a landing pad successor, also find the call instruction.
      98       59095 :     if (EHPadSuccessors.empty())
      99       41660 :       return LIP.first;
     100             :     // There may not be a call instruction (?) in which case we ignore LPad.
     101       17435 :     LIP.second = LIP.first;
     102       17435 :     for (MachineBasicBlock::const_iterator I = MBB.end(), E = MBB.begin();
     103       73943 :          I != E;) {
     104             :       --I;
     105       73942 :       if (I->isCall()) {
     106       52302 :         LIP.second = LIS.getInstructionIndex(*I);
     107       17434 :         break;
     108             :       }
     109             :     }
     110             :   }
     111             : 
     112             :   // If CurLI is live into a landing pad successor, move the last insert point
     113             :   // back to the call that may throw.
     114      501911 :   if (!LIP.second)
     115           0 :     return LIP.first;
     116             : 
     117     1003870 :   if (none_of(EHPadSuccessors, [&](const MachineBasicBlock *EHPad) {
     118      501959 :         return LIS.isLiveInToMBB(CurLI, EHPad);
     119      501959 :       }))
     120      429286 :     return LIP.first;
     121             : 
     122             :   // Find the value leaving MBB.
     123       72625 :   const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
     124       72625 :   if (!VNI)
     125           0 :     return LIP.first;
     126             : 
     127             :   // If the value leaving MBB was defined after the call in MBB, it can't
     128             :   // really be live-in to the landing pad.  This can happen if the landing pad
     129             :   // has a PHI, and this register is undef on the exceptional edge.
     130             :   // <rdar://problem/10664933>
     131       72644 :   if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
     132           5 :     return LIP.first;
     133             : 
     134             :   // Value is properly live-in to the landing pad.
     135             :   // Only allow inserts before the call.
     136       72620 :   return LIP.second;
     137             : }
     138             : 
     139             : MachineBasicBlock::iterator
     140       17904 : InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,
     141             :                                             MachineBasicBlock &MBB) {
     142       17904 :   SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
     143       35808 :   if (LIP == LIS.getMBBEndIdx(&MBB))
     144             :     return MBB.end();
     145       16721 :   return LIS.getInstructionFromIndex(LIP);
     146             : }
     147             : 
     148             : //===----------------------------------------------------------------------===//
     149             : //                                 Split Analysis
     150             : //===----------------------------------------------------------------------===//
     151             : 
     152      179035 : SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
     153      179035 :                              const MachineLoopInfo &mli)
     154      179035 :     : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
     155      358070 :       TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
     156             : 
     157           0 : void SplitAnalysis::clear() {
     158             :   UseSlots.clear();
     159             :   UseBlocks.clear();
     160             :   ThroughBlocks.clear();
     161           0 :   CurLI = nullptr;
     162       57527 :   DidRepairRange = false;
     163           0 : }
     164             : 
     165             : /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
     166       57527 : void SplitAnalysis::analyzeUses() {
     167             :   assert(UseSlots.empty() && "Call clear first");
     168             : 
     169             :   // First get all the defs from the interval values. This provides the correct
     170             :   // slots for early clobbers.
     171      288368 :   for (const VNInfo *VNI : CurLI->valnos)
     172      163497 :     if (!VNI->isPHIDef() && !VNI->isUnused())
     173       76840 :       UseSlots.push_back(VNI->def);
     174             : 
     175             :   // Get use slots form the use-def chain.
     176       57527 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     177      439469 :   for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
     178      324415 :     if (!MO.isUndef())
     179      648818 :       UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());
     180             : 
     181             :   array_pod_sort(UseSlots.begin(), UseSlots.end());
     182             : 
     183             :   // Remove duplicates, keeping the smaller slot for each instruction.
     184             :   // That is what we want for early clobbers.
     185             :   UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
     186             :                              SlotIndex::isSameInstr),
     187             :                  UseSlots.end());
     188             : 
     189             :   // Compute per-live block info.
     190       57527 :   if (!calcLiveBlockInfo()) {
     191             :     // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
     192             :     // I am looking at you, RegisterCoalescer!
     193           0 :     DidRepairRange = true;
     194             :     ++NumRepairs;
     195             :     LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
     196           0 :     const_cast<LiveIntervals&>(LIS)
     197           0 :       .shrinkToUses(const_cast<LiveInterval*>(CurLI));
     198             :     UseBlocks.clear();
     199             :     ThroughBlocks.clear();
     200           0 :     bool fixed = calcLiveBlockInfo();
     201             :     (void)fixed;
     202             :     assert(fixed && "Couldn't fix broken live interval");
     203             :   }
     204             : 
     205             :   LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "
     206             :                     << UseBlocks.size() << " blocks, through "
     207             :                     << NumThroughBlocks << " blocks.\n");
     208       57527 : }
     209             : 
     210             : /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
     211             : /// where CurLI is live.
     212       57527 : bool SplitAnalysis::calcLiveBlockInfo() {
     213      115054 :   ThroughBlocks.resize(MF.getNumBlockIDs());
     214       57527 :   NumThroughBlocks = NumGapBlocks = 0;
     215      115054 :   if (CurLI->empty())
     216             :     return true;
     217             : 
     218             :   LiveInterval::const_iterator LVI = CurLI->begin();
     219             :   LiveInterval::const_iterator LVE = CurLI->end();
     220             : 
     221             :   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
     222             :   UseI = UseSlots.begin();
     223             :   UseE = UseSlots.end();
     224             : 
     225             :   // Loop over basic blocks where CurLI is live.
     226             :   MachineFunction::iterator MFI =
     227      115054 :       LIS.getMBBFromIndex(LVI->start)->getIterator();
     228             :   while (true) {
     229             :     BlockInfo BI;
     230      809618 :     BI.MBB = &*MFI;
     231             :     SlotIndex Start, Stop;
     232      809618 :     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     1453178 :     if (UseI == UseE || *UseI >= Stop) {
     238      661909 :       ++NumThroughBlocks;
     239      661909 :       ThroughBlocks.set(BI.MBB->getNumber());
     240             :       // The range shouldn't end mid-block if there are no uses. This shouldn't
     241             :       // happen.
     242      661909 :       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      147709 :       BI.FirstInstr = *UseI;
     247             :       assert(BI.FirstInstr >= Start);
     248      389958 :       do ++UseI;
     249      722389 :       while (UseI != UseE && *UseI < Stop);
     250      147709 :       BI.LastInstr = UseI[-1];
     251             :       assert(BI.LastInstr < Stop);
     252             : 
     253             :       // LVI is the first live segment overlapping MBB.
     254      147709 :       BI.LiveIn = LVI->start <= Start;
     255             : 
     256             :       // When not live in, the first use should be a def.
     257      147709 :       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       66398 :         BI.FirstDef = BI.FirstInstr;
     261             :       }
     262             : 
     263             :       // Look for gaps in the live range.
     264      147709 :       BI.LiveOut = true;
     265      158151 :       while (LVI->end < Stop) {
     266             :         SlotIndex LastStop = LVI->end;
     267       96671 :         if (++LVI == LVE || LVI->start >= Stop) {
     268       60588 :           BI.LiveOut = false;
     269       60588 :           BI.LastInstr = LastStop;
     270             :           break;
     271             :         }
     272             : 
     273       10442 :         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         156 :           ++NumGapBlocks;
     277             : 
     278             :           // Push the Live-in part.
     279         156 :           BI.LiveOut = false;
     280         156 :           UseBlocks.push_back(BI);
     281         156 :           UseBlocks.back().LastInstr = LastStop;
     282             : 
     283             :           // Set up BI for the live-out part.
     284         156 :           BI.LiveIn = false;
     285         156 :           BI.LiveOut = true;
     286         156 :           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       10442 :         if (!BI.FirstDef)
     292        2198 :           BI.FirstDef = LVI->start;
     293             :       }
     294             : 
     295      147709 :       UseBlocks.push_back(BI);
     296             : 
     297             :       // LVI is now at LVE or LVI->end >= Stop.
     298      147709 :       if (LVI == LVE)
     299             :         break;
     300             :     }
     301             : 
     302             :     // Live segment ends exactly at Stop. Move to the next segment.
     303      764229 :     if (LVI->end == Stop && ++LVI == LVE)
     304             :       break;
     305             : 
     306             :     // Pick the next basic block.
     307      752091 :     if (LVI->start < Stop)
     308             :       ++MFI;
     309             :     else
     310      329168 :       MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
     311      752091 :   }
     312             : 
     313             :   assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
     314       57527 :   return true;
     315             : }
     316             : 
     317       16534 : unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
     318       16534 :   if (cli->empty())
     319             :     return 0;
     320             :   LiveInterval *li = const_cast<LiveInterval*>(cli);
     321             :   LiveInterval::iterator LVI = li->begin();
     322             :   LiveInterval::iterator LVE = li->end();
     323             :   unsigned Count = 0;
     324             : 
     325             :   // Loop over basic blocks where li is live.
     326             :   MachineFunction::const_iterator MFI =
     327       33040 :       LIS.getMBBFromIndex(LVI->start)->getIterator();
     328       16520 :   SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);
     329             :   while (true) {
     330      151513 :     ++Count;
     331      151513 :     LVI = li->advanceTo(LVI, Stop);
     332      151513 :     if (LVI == LVE)
     333             :       return Count;
     334             :     do {
     335             :       ++MFI;
     336             :       Stop = LIS.getMBBEndIdx(&*MFI);
     337      412049 :     } while (Stop <= LVI->start);
     338             :   }
     339             : }
     340             : 
     341         390 : bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
     342         390 :   unsigned OrigReg = VRM.getOriginal(CurLI->reg);
     343         390 :   const LiveInterval &Orig = LIS.getInterval(OrigReg);
     344             :   assert(!Orig.empty() && "Splitting empty interval?");
     345         390 :   LiveInterval::const_iterator I = Orig.find(Idx);
     346             : 
     347             :   // Range containing Idx should begin at Idx.
     348         730 :   if (I != Orig.end() && I->start <= Idx)
     349         294 :     return I->start == Idx;
     350             : 
     351             :   // Range does not contain Idx, previous must end at Idx.
     352         192 :   return I != Orig.begin() && (--I)->end == Idx;
     353             : }
     354             : 
     355       57527 : void SplitAnalysis::analyze(const LiveInterval *li) {
     356             :   clear();
     357       57527 :   CurLI = li;
     358       57527 :   analyzeUses();
     359       57527 : }
     360             : 
     361             : //===----------------------------------------------------------------------===//
     362             : //                               Split Editor
     363             : //===----------------------------------------------------------------------===//
     364             : 
     365             : /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
     366      179035 : SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa,
     367             :                          LiveIntervals &lis, VirtRegMap &vrm,
     368             :                          MachineDominatorTree &mdt,
     369      179035 :                          MachineBlockFrequencyInfo &mbfi)
     370             :     : SA(sa), AA(aa), LIS(lis), VRM(vrm),
     371      179035 :       MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt),
     372      179035 :       TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
     373      179035 :       TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
     374     1074210 :       MBFI(mbfi), RegAssign(Allocator) {}
     375             : 
     376       46483 : void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
     377       46483 :   Edit = &LRE;
     378       46483 :   SpillMode = SM;
     379       46483 :   OpenIdx = 0;
     380       46483 :   RegAssign.clear();
     381       46483 :   Values.clear();
     382             : 
     383             :   // Reset the LiveRangeCalc instances needed for this spill mode.
     384       92966 :   LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
     385       46483 :                   &LIS.getVNInfoAllocator());
     386       46483 :   if (SpillMode)
     387       70052 :     LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
     388       35026 :                     &LIS.getVNInfoAllocator());
     389             : 
     390             :   // We don't need an AliasAnalysis since we will only be performing
     391             :   // cheap-as-a-copy remats anyway.
     392       46483 :   Edit->anyRematerializable(nullptr);
     393       46483 : }
     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         303 :   for (LiveInterval::SubRange &S : LI.subranges())
     411         303 :     if (S.LaneMask == LM)
     412           0 :       return S;
     413           0 :   llvm_unreachable("SubRange for this mask not found");
     414             : }
     415             : 
     416       71566 : void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
     417       71566 :   if (!LI.hasSubRanges()) {
     418       71462 :     LI.createDeadDef(VNI);
     419       71462 :     return;
     420             :   }
     421             : 
     422         104 :   SlotIndex Def = VNI->def;
     423         104 :   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         194 :     for (LiveInterval::SubRange &S : LI.subranges()) {
     428         143 :       auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
     429         143 :       VNInfo *PV = PS.getVNInfoAt(Def);
     430         254 :       if (PV != nullptr && PV->def == Def)
     431         216 :         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             :     const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);
     438             :     assert(DefMI != nullptr);
     439             :     LaneBitmask LM;
     440          71 :     for (const MachineOperand &DefOp : DefMI->defs()) {
     441          53 :       unsigned R = DefOp.getReg();
     442          53 :       if (R != LI.reg)
     443           0 :         continue;
     444          53 :       if (unsigned SR = DefOp.getSubReg())
     445           9 :         LM |= TRI.getSubRegIndexLaneMask(SR);
     446             :       else {
     447          44 :         LM = MRI.getMaxLaneMaskForVReg(R);
     448          44 :         break;
     449             :       }
     450             :     }
     451         212 :     for (LiveInterval::SubRange &S : LI.subranges())
     452         159 :       if ((S.LaneMask & LM).any())
     453         304 :         S.createDeadDef(Def, LIS.getVNInfoAllocator());
     454             :   }
     455             : }
     456             : 
     457      122473 : 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      244946 :   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
     465             : 
     466             :   // Create a new value.
     467      244946 :   VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
     468             : 
     469      122473 :   bool Force = LI->hasSubRanges();
     470      122473 :   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      244946 :     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      122473 :   if (!Force && InsP.second)
     478             :     return VNI;
     479             : 
     480             :   // If the previous value was a simple mapping, add liveness for it now.
     481       42764 :   if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
     482       11506 :     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       11506 :     InsP.first->second = ValueForcePair(nullptr, Force);
     487             :   }
     488             : 
     489             :   // This is a complex mapping, add liveness for VNI
     490       42764 :   addDeadDef(*LI, VNI, Original);
     491       42764 :   return VNI;
     492             : }
     493             : 
     494       55619 : void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {
     495      111238 :   ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];
     496             :   VNInfo *VNI = VFP.getPointer();
     497             : 
     498             :   // ParentVNI was either unmapped or already complex mapped. Either way, just
     499             :   // set the force bit.
     500       55619 :   if (!VNI) {
     501             :     VFP.setInt(true);
     502             :     return;
     503             :   }
     504             : 
     505             :   // This was previously a single mapping. Make sure the old def is represented
     506             :   // by a trivial live range.
     507       34592 :   addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
     508             : 
     509             :   // Mark as complex mapped, forced.
     510       17296 :   VFP = ValueForcePair(nullptr, true);
     511             : }
     512             : 
     513          15 : SlotIndex SplitEditor::buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg,
     514             :     MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
     515             :     unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) {
     516          15 :   const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
     517             :   bool FirstCopy = !Def.isValid();
     518          45 :   MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)
     519             :       .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)
     520          15 :               | getInternalReadRegState(!FirstCopy), SubIdx)
     521          15 :       .addReg(FromReg, 0, SubIdx);
     522             : 
     523          15 :   BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
     524          15 :   if (FirstCopy) {
     525           8 :     SlotIndexes &Indexes = *LIS.getSlotIndexes();
     526          16 :     Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
     527             :   } else {
     528           7 :     CopyMI->bundleWithPred();
     529             :   }
     530          30 :   LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx);
     531          30 :   DestLI.refineSubRanges(Allocator, LaneMask,
     532          16 :                          [Def, &Allocator](LiveInterval::SubRange& SR) {
     533          32 :     SR.createDeadDef(Def, Allocator);
     534             :   });
     535          15 :   return Def;
     536             : }
     537             : 
     538       48363 : SlotIndex SplitEditor::buildCopy(unsigned FromReg, unsigned ToReg,
     539             :     LaneBitmask LaneMask, MachineBasicBlock &MBB,
     540             :     MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {
     541       48363 :   const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
     542       48363 :   if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {
     543             :     // The full vreg is copied.
     544             :     MachineInstr *CopyMI =
     545       96710 :         BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg);
     546       48355 :     SlotIndexes &Indexes = *LIS.getSlotIndexes();
     547       96710 :     return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
     548             :   }
     549             : 
     550             :   // Only a subset of lanes needs to be copied. The following is a simple
     551             :   // heuristic to construct a sequence of COPYs. We could add a target
     552             :   // specific callback if this turns out to be suboptimal.
     553          16 :   LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));
     554             : 
     555             :   // First pass: Try to find a perfectly matching subregister index. If none
     556             :   // exists find the one covering the most lanemask bits.
     557             :   SmallVector<unsigned, 8> PossibleIndexes;
     558             :   unsigned BestIdx = 0;
     559             :   unsigned BestCover = 0;
     560           8 :   const TargetRegisterClass *RC = MRI.getRegClass(FromReg);
     561             :   assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");
     562         986 :   for (unsigned Idx = 1, E = TRI.getNumSubRegIndices(); Idx < E; ++Idx) {
     563             :     // Is this index even compatible with the given class?
     564         486 :     if (TRI.getSubClassWithSubReg(RC, Idx) != RC)
     565         439 :       continue;
     566          47 :     LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
     567             :     // Early exit if we found a perfect match.
     568          47 :     if (SubRegMask == LaneMask) {
     569             :       BestIdx = Idx;
     570             :       break;
     571             :     }
     572             : 
     573             :     // The index must not cover any lanes outside \p LaneMask.
     574          46 :     if ((SubRegMask & ~LaneMask).any())
     575          30 :       continue;
     576             : 
     577             :     unsigned PopCount = SubRegMask.getNumLanes();
     578          16 :     PossibleIndexes.push_back(Idx);
     579          16 :     if (PopCount > BestCover) {
     580             :       BestCover = PopCount;
     581           8 :       BestIdx = Idx;
     582             :     }
     583             :   }
     584             : 
     585             :   // Abort if we cannot possibly implement the COPY with the given indexes.
     586           8 :   if (BestIdx == 0)
     587           0 :     report_fatal_error("Impossible to implement partial COPY");
     588             : 
     589             :   SlotIndex Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore,
     590           8 :                                         BestIdx, DestLI, Late, SlotIndex());
     591             : 
     592             :   // Greedy heuristic: Keep iterating keeping the best covering subreg index
     593             :   // each time.
     594           8 :   LaneBitmask LanesLeft = LaneMask & ~(TRI.getSubRegIndexLaneMask(BestIdx));
     595          22 :   while (LanesLeft.any()) {
     596             :     unsigned BestIdx = 0;
     597             :     int BestCover = std::numeric_limits<int>::min();
     598          21 :     for (unsigned Idx : PossibleIndexes) {
     599          14 :       LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
     600             :       // Early exit if we found a perfect match.
     601          14 :       if (SubRegMask == LanesLeft) {
     602             :         BestIdx = Idx;
     603             :         break;
     604             :       }
     605             : 
     606             :       // Try to cover as much of the remaining lanes as possible but
     607             :       // as few of the already covered lanes as possible.
     608             :       int Cover = (SubRegMask & LanesLeft).getNumLanes()
     609           7 :                 - (SubRegMask & ~LanesLeft).getNumLanes();
     610           7 :       if (Cover > BestCover) {
     611             :         BestCover = Cover;
     612             :         BestIdx = Idx;
     613             :       }
     614             :     }
     615             : 
     616           7 :     if (BestIdx == 0)
     617           0 :       report_fatal_error("Impossible to implement partial COPY");
     618             : 
     619           7 :     buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,
     620             :                           DestLI, Late, Def);
     621           7 :     LanesLeft &= ~TRI.getSubRegIndexLaneMask(BestIdx);
     622             :   }
     623             : 
     624           8 :   return Def;
     625             : }
     626             : 
     627       71915 : VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
     628             :                                    VNInfo *ParentVNI,
     629             :                                    SlotIndex UseIdx,
     630             :                                    MachineBasicBlock &MBB,
     631             :                                    MachineBasicBlock::iterator I) {
     632             :   SlotIndex Def;
     633      143830 :   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
     634             : 
     635             :   // We may be trying to avoid interference that ends at a deleted instruction,
     636             :   // so always begin RegIdx 0 early and all others late.
     637       71915 :   bool Late = RegIdx != 0;
     638             : 
     639             :   // Attempt cheap-as-a-copy rematerialization.
     640       71915 :   unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
     641       71915 :   LiveInterval &OrigLI = LIS.getInterval(Original);
     642       71915 :   VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
     643             : 
     644       71915 :   unsigned Reg = LI->reg;
     645             :   bool DidRemat = false;
     646       71915 :   if (OrigVNI) {
     647             :     LiveRangeEdit::Remat RM(ParentVNI);
     648       71915 :     RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
     649       71915 :     if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
     650       23552 :       Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);
     651             :       ++NumRemats;
     652             :       DidRemat = true;
     653             :     }
     654             :   }
     655             :   if (!DidRemat) {
     656             :     LaneBitmask LaneMask;
     657       48363 :     if (LI->hasSubRanges()) {
     658             :       LaneMask = LaneBitmask::getNone();
     659         210 :       for (LiveInterval::SubRange &S : LI->subranges())
     660             :         LaneMask |= S.LaneMask;
     661             :     } else {
     662             :       LaneMask = LaneBitmask::getAll();
     663             :     }
     664             : 
     665             :     ++NumCopies;
     666       96726 :     Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);
     667             :   }
     668             : 
     669             :   // Define the value in Reg.
     670       71915 :   return defValue(RegIdx, ParentVNI, Def, false);
     671             : }
     672             : 
     673             : /// Create a new virtual register and live interval.
     674       38187 : unsigned SplitEditor::openIntv() {
     675             :   // Create the complement as index 0.
     676       76374 :   if (Edit->empty())
     677             :     Edit->createEmptyInterval();
     678             : 
     679             :   // Create the open interval.
     680       76374 :   OpenIdx = Edit->size();
     681             :   Edit->createEmptyInterval();
     682       38187 :   return OpenIdx;
     683             : }
     684             : 
     685           0 : void SplitEditor::selectIntv(unsigned Idx) {
     686             :   assert(Idx != 0 && "Cannot select the complement interval");
     687             :   assert(Idx < Edit->size() && "Can only select previously opened interval");
     688             :   LLVM_DEBUG(dbgs() << "    selectIntv " << OpenIdx << " -> " << Idx << '\n');
     689      168585 :   OpenIdx = Idx;
     690           0 : }
     691             : 
     692       31975 : SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
     693             :   assert(OpenIdx && "openIntv not called before enterIntvBefore");
     694             :   LLVM_DEBUG(dbgs() << "    enterIntvBefore " << Idx);
     695             :   Idx = Idx.getBaseIndex();
     696       31975 :   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
     697       18765 :   if (!ParentVNI) {
     698             :     LLVM_DEBUG(dbgs() << ": not live\n");
     699       13210 :     return Idx;
     700             :   }
     701             :   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
     702             :   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
     703             :   assert(MI && "enterIntvBefore called with invalid index");
     704             : 
     705       18765 :   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
     706       18765 :   return VNI->def;
     707             : }
     708             : 
     709        2253 : SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {
     710             :   assert(OpenIdx && "openIntv not called before enterIntvAfter");
     711             :   LLVM_DEBUG(dbgs() << "    enterIntvAfter " << Idx);
     712             :   Idx = Idx.getBoundaryIndex();
     713        2253 :   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
     714        2253 :   if (!ParentVNI) {
     715             :     LLVM_DEBUG(dbgs() << ": not live\n");
     716           0 :     return Idx;
     717             :   }
     718             :   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
     719             :   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
     720             :   assert(MI && "enterIntvAfter called with invalid index");
     721             : 
     722        2253 :   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
     723        2253 :                               std::next(MachineBasicBlock::iterator(MI)));
     724        2253 :   return VNI->def;
     725             : }
     726             : 
     727       12048 : SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
     728             :   assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
     729       12048 :   SlotIndex End = LIS.getMBBEndIdx(&MBB);
     730             :   SlotIndex Last = End.getPrevSlot();
     731             :   LLVM_DEBUG(dbgs() << "    enterIntvAtEnd " << printMBBReference(MBB) << ", "
     732             :                     << Last);
     733       12048 :   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
     734       12048 :   if (!ParentVNI) {
     735             :     LLVM_DEBUG(dbgs() << ": not live\n");
     736           0 :     return End;
     737             :   }
     738             :   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id);
     739       12048 :   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
     740       24096 :                               SA.getLastSplitPointIter(&MBB));
     741       12048 :   RegAssign.insert(VNI->def, End, OpenIdx);
     742             :   LLVM_DEBUG(dump());
     743       12048 :   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       11490 : void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
     752             :   assert(OpenIdx && "openIntv not called before useIntv");
     753             :   LLVM_DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
     754      168546 :   RegAssign.insert(Start, End, OpenIdx);
     755             :   LLVM_DEBUG(dump());
     756       11490 : }
     757             : 
     758       29748 : SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
     759             :   assert(OpenIdx && "openIntv not called before leaveIntvAfter");
     760             :   LLVM_DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
     761             : 
     762             :   // The interval must be live beyond the instruction at Idx.
     763             :   SlotIndex Boundary = Idx.getBoundaryIndex();
     764       29748 :   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
     765       23139 :   if (!ParentVNI) {
     766             :     LLVM_DEBUG(dbgs() << ": not live\n");
     767             :     return Boundary.getNextSlot();
     768             :   }
     769             :   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
     770             :   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       51184 :   if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
     778       13726 :       MI->readsVirtualRegister(Edit->getReg())) {
     779       13726 :     forceRecompute(0, *ParentVNI);
     780       13726 :     defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
     781       13726 :     return Idx;
     782             :   }
     783             : 
     784        9413 :   VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
     785        9413 :                               std::next(MachineBasicBlock::iterator(MI)));
     786        9413 :   return VNI->def;
     787             : }
     788             : 
     789        1305 : SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
     790             :   assert(OpenIdx && "openIntv not called before leaveIntvBefore");
     791             :   LLVM_DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
     792             : 
     793             :   // The interval must be live into the instruction at Idx.
     794             :   Idx = Idx.getBaseIndex();
     795        1305 :   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
     796        1305 :   if (!ParentVNI) {
     797             :     LLVM_DEBUG(dbgs() << ": not live\n");
     798             :     return Idx.getNextSlot();
     799             :   }
     800             :   LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
     801             : 
     802             :   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
     803             :   assert(MI && "No instruction at index");
     804        1305 :   VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
     805        1305 :   return VNI->def;
     806             : }
     807             : 
     808       13903 : SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
     809             :   assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
     810       13903 :   SlotIndex Start = LIS.getMBBStartIdx(&MBB);
     811             :   LLVM_DEBUG(dbgs() << "    leaveIntvAtTop " << printMBBReference(MBB) << ", "
     812             :                     << Start);
     813             : 
     814       13903 :   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
     815       13903 :   if (!ParentVNI) {
     816             :     LLVM_DEBUG(dbgs() << ": not live\n");
     817           0 :     return Start;
     818             :   }
     819             : 
     820       13903 :   VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
     821       13903 :                               MBB.SkipPHIsLabelsAndDebug(MBB.begin()));
     822       13903 :   RegAssign.insert(Start, VNI->def, OpenIdx);
     823             :   LLVM_DEBUG(dump());
     824       13903 :   return VNI->def;
     825             : }
     826             : 
     827          22 : void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
     828             :   assert(OpenIdx && "openIntv not called before overlapIntv");
     829          22 :   const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
     830             :   assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
     831             :          "Parent changes value in extended range");
     832             :   assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
     833             :          "Range cannot span basic blocks");
     834             : 
     835             :   // The complement interval will be extended as needed by LRCalc.extend().
     836          22 :   if (ParentVNI)
     837          22 :     forceRecompute(0, *ParentVNI);
     838             :   LLVM_DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
     839          22 :   RegAssign.insert(Start, End, OpenIdx);
     840             :   LLVM_DEBUG(dump());
     841          22 : }
     842             : 
     843             : //===----------------------------------------------------------------------===//
     844             : //                                  Spill modes
     845             : //===----------------------------------------------------------------------===//
     846             : 
     847       17391 : void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
     848       34782 :   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
     849             :   LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
     850             :   RegAssignMap::iterator AssignI;
     851       17391 :   AssignI.setMap(RegAssign);
     852             : 
     853       27920 :   for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
     854       21058 :     SlotIndex Def = Copies[i]->def;
     855             :     MachineInstr *MI = LIS.getInstructionFromIndex(Def);
     856             :     assert(MI && "No instruction for back-copy");
     857             : 
     858       10529 :     MachineBasicBlock *MBB = MI->getParent();
     859             :     MachineBasicBlock::iterator MBBI(MI);
     860             :     bool AtBegin;
     861             :     do AtBegin = MBBI == MBB->begin();
     862       10529 :     while (!AtBegin && (--MBBI)->isDebugInstr());
     863             : 
     864             :     LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
     865       10529 :     LIS.removeVRegDefAt(*LI, Def);
     866       10529 :     LIS.RemoveMachineInstrFromMaps(*MI);
     867       10529 :     MI->eraseFromParent();
     868             : 
     869             :     // Adjust RegAssign if a register assignment is killed at Def. We want to
     870             :     // avoid calculating the live range of the source register if possible.
     871       10529 :     AssignI.find(Def.getPrevSlot());
     872       10529 :     if (!AssignI.valid() || AssignI.start() >= Def)
     873        4048 :       continue;
     874             :     // If MI doesn't kill the assigned register, just leave it.
     875       10529 :     if (AssignI.stop() != Def)
     876        4048 :       continue;
     877        6481 :     unsigned RegIdx = AssignI.value();
     878       12281 :     if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
     879             :       LLVM_DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx
     880             :                         << '\n');
     881       12954 :       forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));
     882             :     } else {
     883          12 :       SlotIndex Kill = LIS.getInstructionIndex(*MBBI).getRegSlot();
     884             :       LLVM_DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
     885           4 :       AssignI.setStop(Kill);
     886             :     }
     887             :   }
     888       17391 : }
     889             : 
     890             : MachineBasicBlock*
     891        1319 : SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
     892             :                                   MachineBasicBlock *DefMBB) {
     893        1319 :   if (MBB == DefMBB)
     894             :     return MBB;
     895             :   assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
     896             : 
     897         834 :   const MachineLoopInfo &Loops = SA.Loops;
     898             :   const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
     899         834 :   MachineDomTreeNode *DefDomNode = MDT[DefMBB];
     900             : 
     901             :   // Best candidate so far.
     902             :   MachineBasicBlock *BestMBB = MBB;
     903             :   unsigned BestDepth = std::numeric_limits<unsigned>::max();
     904             : 
     905             :   while (true) {
     906             :     const MachineLoop *Loop = Loops.getLoopFor(MBB);
     907             : 
     908             :     // MBB isn't in a loop, it doesn't get any better.  All dominators have a
     909             :     // higher frequency by definition.
     910         531 :     if (!Loop) {
     911             :       LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
     912             :                         << " dominates " << printMBBReference(*MBB)
     913             :                         << " at depth 0\n");
     914             :       return MBB;
     915             :     }
     916             : 
     917             :     // We'll never be able to exit the DefLoop.
     918         531 :     if (Loop == DefLoop) {
     919             :       LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
     920             :                         << " dominates " << printMBBReference(*MBB)
     921             :                         << " in the same loop\n");
     922             :       return MBB;
     923             :     }
     924             : 
     925             :     // Least busy dominator seen so far.
     926         355 :     unsigned Depth = Loop->getLoopDepth();
     927         355 :     if (Depth < BestDepth) {
     928             :       BestMBB = MBB;
     929             :       BestDepth = Depth;
     930             :       LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
     931             :                         << " dominates " << printMBBReference(*MBB)
     932             :                         << " at depth " << Depth << '\n');
     933             :     }
     934             : 
     935             :     // Leave loop by going to the immediate dominator of the loop header.
     936             :     // This is a bigger stride than simply walking up the dominator tree.
     937         355 :     MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
     938             : 
     939             :     // Too far up the dominator tree?
     940         710 :     if (!IDom || !MDT.dominates(DefDomNode, IDom))
     941             :       return BestMBB;
     942             : 
     943         351 :     MBB = IDom->getBlock();
     944         351 :   }
     945             : }
     946             : 
     947         800 : void SplitEditor::computeRedundantBackCopies(
     948             :     DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
     949        1600 :   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
     950         800 :   LiveInterval *Parent = &Edit->getParent();
     951        2400 :   SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
     952             :   SmallPtrSet<VNInfo *, 8> DominatedVNIs;
     953             : 
     954             :   // Aggregate VNIs having the same value as ParentVNI.
     955        6012 :   for (VNInfo *VNI : LI->valnos) {
     956        2606 :     if (VNI->isUnused())
     957           0 :       continue;
     958        2606 :     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
     959        5212 :     EqualVNs[ParentVNI->id].insert(VNI);
     960             :   }
     961             : 
     962             :   // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
     963             :   // redundant VNIs to BackCopies.
     964        4208 :   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
     965             :     VNInfo *ParentVNI = Parent->getValNumInfo(i);
     966        2591 :     if (!NotToHoistSet.count(ParentVNI->id))
     967             :       continue;
     968        1634 :     SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
     969             :     SmallPtrSetIterator<VNInfo *> It2 = It1;
     970        6472 :     for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
     971             :       It2 = It1;
     972       13852 :       for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
     973        9077 :         if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
     974         343 :           continue;
     975             : 
     976        8328 :         MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
     977        8328 :         MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
     978        4164 :         if (MBB1 == MBB2) {
     979           0 :           DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
     980        8328 :         } else if (MDT.dominates(MBB1, MBB2)) {
     981          72 :           DominatedVNIs.insert(*It2);
     982        8184 :         } else if (MDT.dominates(MBB2, MBB1)) {
     983          31 :           DominatedVNIs.insert(*It1);
     984             :         }
     985             :       }
     986             :     }
     987         817 :     if (!DominatedVNIs.empty()) {
     988          39 :       forceRecompute(0, *ParentVNI);
     989         142 :       for (auto VNI : DominatedVNIs) {
     990         103 :         BackCopies.push_back(VNI);
     991             :       }
     992          39 :       DominatedVNIs.clear();
     993             :     }
     994             :   }
     995         800 : }
     996             : 
     997             : /// For SM_Size mode, find a common dominator for all the back-copies for
     998             : /// the same ParentVNI and hoist the backcopies to the dominator BB.
     999             : /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
    1000             : /// to do the hoisting, simply remove the dominated backcopies for the same
    1001             : /// ParentVNI.
    1002       17391 : void SplitEditor::hoistCopies() {
    1003             :   // Get the complement interval, always RegIdx 0.
    1004       34782 :   LiveInterval *LI = &LIS.getInterval(Edit->get(0));
    1005       17391 :   LiveInterval *Parent = &Edit->getParent();
    1006             : 
    1007             :   // Track the nearest common dominator for all back-copies for each ParentVNI,
    1008             :   // indexed by ParentVNI->id.
    1009             :   using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
    1010       34782 :   SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
    1011             :   // The total cost of all the back-copies for each ParentVNI.
    1012       34782 :   SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums());
    1013             :   // The ParentVNI->id set for which hoisting back-copies are not beneficial
    1014             :   // for Speed.
    1015             :   DenseSet<unsigned> NotToHoistSet;
    1016             : 
    1017             :   // Find the nearest common dominator for parent values with multiple
    1018             :   // back-copies.  If a single back-copy dominates, put it in DomPair.second.
    1019       91985 :   for (VNInfo *VNI : LI->valnos) {
    1020       37297 :     if (VNI->isUnused())
    1021           0 :       continue;
    1022       37297 :     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
    1023             :     assert(ParentVNI && "Parent not live at complement def");
    1024             : 
    1025             :     // Don't hoist remats.  The complement is probably going to disappear
    1026             :     // completely anyway.
    1027       74594 :     if (Edit->didRematerialize(ParentVNI))
    1028        9082 :       continue;
    1029             : 
    1030       28215 :     MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
    1031             : 
    1032       28215 :     DomPair &Dom = NearestDom[ParentVNI->id];
    1033             : 
    1034             :     // Keep directly defined parent values.  This is either a PHI or an
    1035             :     // instruction in the complement range.  All other copies of ParentVNI
    1036             :     // should be eliminated.
    1037       35669 :     if (VNI->def == ParentVNI->def) {
    1038             :       LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
    1039             :       Dom = DomPair(ValMBB, VNI->def);
    1040        7454 :       continue;
    1041             :     }
    1042             :     // Skip the singly mapped values.  There is nothing to gain from hoisting a
    1043             :     // single back-copy.
    1044       41522 :     if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
    1045             :       LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
    1046        2639 :       continue;
    1047             :     }
    1048             : 
    1049       18122 :     if (!Dom.first) {
    1050             :       // First time we see ParentVNI.  VNI dominates itself.
    1051             :       Dom = DomPair(ValMBB, VNI->def);
    1052       10437 :     } else if (Dom.first == ValMBB) {
    1053             :       // Two defs in the same block.  Pick the earlier def.
    1054           6 :       if (!Dom.second.isValid() || VNI->def < Dom.second)
    1055           2 :         Dom.second = VNI->def;
    1056             :     } else {
    1057             :       // Different basic blocks. Check if one dominates.
    1058             :       MachineBasicBlock *Near =
    1059       10433 :         MDT.findNearestCommonDominator(Dom.first, ValMBB);
    1060       10433 :       if (Near == ValMBB)
    1061             :         // Def ValMBB dominates.
    1062             :         Dom = DomPair(ValMBB, VNI->def);
    1063        9986 :       else if (Near != Dom.first)
    1064             :         // None dominate. Hoist to common dominator, need new def.
    1065             :         Dom = DomPair(Near, SlotIndex());
    1066       20866 :       Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
    1067             :     }
    1068             : 
    1069             :     LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'
    1070             :                       << VNI->def << " for parent " << ParentVNI->id << '@'
    1071             :                       << ParentVNI->def << " hoist to "
    1072             :                       << printMBBReference(*Dom.first) << ' ' << Dom.second
    1073             :                       << '\n');
    1074             :   }
    1075             : 
    1076             :   // Insert the hoisted copies.
    1077       83379 :   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
    1078       32994 :     DomPair &Dom = NearestDom[i];
    1079       78719 :     if (!Dom.first || Dom.second.isValid())
    1080       64167 :       continue;
    1081             :     // This value needs a hoisted copy inserted at the end of Dom.first.
    1082             :     VNInfo *ParentVNI = Parent->getValNumInfo(i);
    1083        1319 :     MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
    1084             :     // Get a less loopy dominator than Dom.first.
    1085        1319 :     Dom.first = findShallowDominator(Dom.first, DefMBB);
    1086        3455 :     if (SpillMode == SM_Speed &&
    1087        3957 :         MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
    1088         817 :       NotToHoistSet.insert(ParentVNI->id);
    1089         817 :       continue;
    1090             :     }
    1091        1004 :     SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
    1092         502 :     Dom.second =
    1093         502 :       defFromParent(0, ParentVNI, Last, *Dom.first,
    1094         502 :                     SA.getLastSplitPointIter(Dom.first))->def;
    1095             :   }
    1096             : 
    1097             :   // Remove redundant back-copies that are now known to be dominated by another
    1098             :   // def with the same value.
    1099             :   SmallVector<VNInfo*, 8> BackCopies;
    1100       92989 :   for (VNInfo *VNI : LI->valnos) {
    1101       37799 :     if (VNI->isUnused())
    1102           0 :       continue;
    1103       37799 :     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
    1104       37799 :     const DomPair &Dom = NearestDom[ParentVNI->id];
    1105       91250 :     if (!Dom.first || Dom.second == VNI->def ||
    1106       12845 :         NotToHoistSet.count(ParentVNI->id))
    1107       27373 :       continue;
    1108       10426 :     BackCopies.push_back(VNI);
    1109       10426 :     forceRecompute(0, *ParentVNI);
    1110             :   }
    1111             : 
    1112             :   // If it is not beneficial to hoist all the BackCopies, simply remove
    1113             :   // redundant BackCopies in speed mode.
    1114       34752 :   if (SpillMode == SM_Speed && !NotToHoistSet.empty())
    1115         800 :     computeRedundantBackCopies(NotToHoistSet, BackCopies);
    1116             : 
    1117       17391 :   removeBackCopies(BackCopies);
    1118       17391 : }
    1119             : 
    1120             : /// transferValues - Transfer all possible values to the new live ranges.
    1121             : /// Values that were rematerialized are left alone, they need LRCalc.extend().
    1122       28848 : bool SplitEditor::transferValues() {
    1123             :   bool Skipped = false;
    1124       57696 :   RegAssignMap::const_iterator AssignI = RegAssign.begin();
    1125      307528 :   for (const LiveRange::Segment &S : Edit->getParent()) {
    1126             :     LLVM_DEBUG(dbgs() << "  blit " << S << ':');
    1127      124916 :     VNInfo *ParentVNI = S.valno;
    1128             :     // RegAssign has holes where RegIdx 0 should be used.
    1129      124916 :     SlotIndex Start = S.start;
    1130      124916 :     AssignI.advanceTo(Start);
    1131             :     do {
    1132             :       unsigned RegIdx;
    1133      203081 :       SlotIndex End = S.end;
    1134             :       if (!AssignI.valid()) {
    1135             :         RegIdx = 0;
    1136      166647 :       } else if (AssignI.start() <= Start) {
    1137      102784 :         RegIdx = AssignI.value();
    1138      102784 :         if (AssignI.stop() < End) {
    1139       45319 :           End = AssignI.stop();
    1140       45319 :           ++AssignI;
    1141             :         }
    1142             :       } else {
    1143             :         RegIdx = 0;
    1144       63863 :         End = std::min(End, AssignI.start());
    1145             :       }
    1146             : 
    1147             :       // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
    1148             :       LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('
    1149             :                         << printReg(Edit->get(RegIdx)) << ')');
    1150      406162 :       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
    1151             : 
    1152             :       // Check for a simply defined value that can be blitted directly.
    1153      406162 :       ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
    1154      265111 :       if (VNInfo *VNI = VFP.getPointer()) {
    1155             :         LLVM_DEBUG(dbgs() << ':' << VNI->id);
    1156      124060 :         LI.addSegment(LiveInterval::Segment(Start, End, VNI));
    1157             :         Start = End;
    1158      241861 :         continue;
    1159             :       }
    1160             : 
    1161             :       // Skip values with forced recomputation.
    1162      258852 :       if (VFP.getInt()) {
    1163             :         LLVM_DEBUG(dbgs() << "(recalc)");
    1164             :         Skipped = true;
    1165      117801 :         Start = End;
    1166      117801 :         continue;
    1167             :       }
    1168             : 
    1169             :       LiveRangeCalc &LRC = getLRCalc(RegIdx);
    1170             : 
    1171             :       // This value has multiple defs in RegIdx, but it wasn't rematerialized,
    1172             :       // so the live range is accurate. Add live-in blocks in [Start;End) to the
    1173             :       // LiveInBlocks.
    1174       46500 :       MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
    1175             :       SlotIndex BlockStart, BlockEnd;
    1176       23250 :       std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
    1177             : 
    1178             :       // The first block may be live-in, or it may have its own def.
    1179       23250 :       if (Start != BlockStart) {
    1180       22772 :         VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
    1181             :         assert(VNI && "Missing def for complex mapped value");
    1182             :         LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB));
    1183             :         // MBB has its own def. Is it also live-out?
    1184       11386 :         if (BlockEnd <= End)
    1185             :           LRC.setLiveOutValue(&*MBB, VNI);
    1186             : 
    1187             :         // Skip to the next block for live-in.
    1188             :         ++MBB;
    1189       11386 :         BlockStart = BlockEnd;
    1190             :       }
    1191             : 
    1192             :       // Handle the live-in blocks covered by [Start;End).
    1193             :       assert(Start <= BlockStart && "Expected live-in block");
    1194       78725 :       while (BlockStart < End) {
    1195             :         LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB));
    1196      110950 :         BlockEnd = LIS.getMBBEndIdx(&*MBB);
    1197       55475 :         if (BlockStart == ParentVNI->def) {
    1198             :           // This block has the def of a parent PHI, so it isn't live-in.
    1199             :           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
    1200        1732 :           VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
    1201             :           assert(VNI && "Missing def for complex mapped parent PHI");
    1202         866 :           if (End >= BlockEnd)
    1203             :             LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
    1204             :         } else {
    1205             :           // This block needs a live-in value.  The last block covered may not
    1206             :           // be live-out.
    1207       54609 :           if (End < BlockEnd)
    1208        9179 :             LRC.addLiveInBlock(LI, MDT[&*MBB], End);
    1209             :           else {
    1210             :             // Live-through, and we don't know the value.
    1211       45430 :             LRC.addLiveInBlock(LI, MDT[&*MBB]);
    1212             :             LRC.setLiveOutValue(&*MBB, nullptr);
    1213             :           }
    1214             :         }
    1215       55475 :         BlockStart = BlockEnd;
    1216             :         ++MBB;
    1217             :       }
    1218             :       Start = End;
    1219      203081 :     } while (Start != S.end);
    1220             :     LLVM_DEBUG(dbgs() << '\n');
    1221             :   }
    1222             : 
    1223       28848 :   LRCalc[0].calculateValues();
    1224       28848 :   if (SpillMode)
    1225       17391 :     LRCalc[1].calculateValues();
    1226             : 
    1227       28848 :   return Skipped;
    1228             : }
    1229             : 
    1230        1609 : static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) {
    1231             :   const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
    1232        1609 :   if (Seg == nullptr)
    1233             :     return true;
    1234        1609 :   if (Seg->end != Def.getDeadSlot())
    1235             :     return false;
    1236             :   // This is a dead PHI. Remove it.
    1237             :   LR.removeSegment(*Seg, true);
    1238          30 :   return true;
    1239             : }
    1240             : 
    1241        1579 : void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC,
    1242             :                                  LiveRange &LR, LaneBitmask LM,
    1243             :                                  ArrayRef<SlotIndex> Undefs) {
    1244        5083 :   for (MachineBasicBlock *P : B.predecessors()) {
    1245        3504 :     SlotIndex End = LIS.getMBBEndIdx(P);
    1246        3504 :     SlotIndex LastUse = End.getPrevSlot();
    1247             :     // The predecessor may not have a live-out value. That is OK, like an
    1248             :     // undef PHI operand.
    1249        3504 :     LiveInterval &PLI = Edit->getParent();
    1250             :     // Need the cast because the inputs to ?: would otherwise be deemed
    1251             :     // "incompatible": SubRange vs LiveInterval.
    1252             :     LiveRange &PSR = !LM.all() ? getSubRangeForMask(LM, PLI)
    1253        7008 :                                : static_cast<LiveRange&>(PLI);
    1254        3504 :     if (PSR.liveAt(LastUse))
    1255        3504 :       LRC.extend(LR, End, /*PhysReg=*/0, Undefs);
    1256             :   }
    1257        1579 : }
    1258             : 
    1259       17028 : void SplitEditor::extendPHIKillRanges() {
    1260             :   // Extend live ranges to be live-out for successor PHI values.
    1261             : 
    1262             :   // Visit each PHI def slot in the parent live interval. If the def is dead,
    1263             :   // remove it. Otherwise, extend the live interval to reach the end indexes
    1264             :   // of all predecessor blocks.
    1265             : 
    1266       17028 :   LiveInterval &ParentLI = Edit->getParent();
    1267       59262 :   for (const VNInfo *V : ParentLI.valnos) {
    1268       42221 :     if (V->isUnused() || !V->isPHIDef())
    1269       19509 :       continue;
    1270             : 
    1271        1608 :     unsigned RegIdx = RegAssign.lookup(V->def);
    1272        3216 :     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
    1273             :     LiveRangeCalc &LRC = getLRCalc(RegIdx);
    1274        1608 :     MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
    1275        1608 :     if (!removeDeadSegment(V->def, LI))
    1276        1578 :       extendPHIRange(B, LRC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
    1277             :   }
    1278             : 
    1279             :   SmallVector<SlotIndex, 4> Undefs;
    1280       34056 :   LiveRangeCalc SubLRC;
    1281             : 
    1282       17133 :   for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
    1283         321 :     for (const VNInfo *V : PS.valnos) {
    1284         323 :       if (V->isUnused() || !V->isPHIDef())
    1285         107 :         continue;
    1286           1 :       unsigned RegIdx = RegAssign.lookup(V->def);
    1287           2 :       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
    1288             :       LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI);
    1289           1 :       if (removeDeadSegment(V->def, S))
    1290           0 :         continue;
    1291             : 
    1292           1 :       MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
    1293           1 :       SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
    1294           1 :                    &LIS.getVNInfoAllocator());
    1295             :       Undefs.clear();
    1296           1 :       LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
    1297           1 :       extendPHIRange(B, SubLRC, S, PS.LaneMask, Undefs);
    1298             :     }
    1299             :   }
    1300       17028 : }
    1301             : 
    1302             : /// rewriteAssigned - Rewrite all uses of Edit->getReg().
    1303       28848 : void SplitEditor::rewriteAssigned(bool ExtendRanges) {
    1304             :   struct ExtPoint {
    1305             :     ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
    1306         183 :       : MO(O), RegIdx(R), Next(N) {}
    1307             : 
    1308             :     MachineOperand MO;
    1309             :     unsigned RegIdx;
    1310             :     SlotIndex Next;
    1311             :   };
    1312             : 
    1313             :   SmallVector<ExtPoint,4> ExtPoints;
    1314             : 
    1315       28848 :   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
    1316      408237 :        RE = MRI.reg_end(); RI != RE;) {
    1317             :     MachineOperand &MO = *RI;
    1318      379389 :     MachineInstr *MI = MO.getParent();
    1319             :     ++RI;
    1320             :     // LiveDebugVariables should have handled all DBG_VALUE instructions.
    1321      379389 :     if (MI->isDebugValue()) {
    1322             :       LLVM_DEBUG(dbgs() << "Zapping " << *MI);
    1323           0 :       MO.setReg(0);
    1324           0 :       continue;
    1325             :     }
    1326             : 
    1327             :     // <undef> operands don't really read the register, so it doesn't matter
    1328             :     // which register we choose.  When the use operand is tied to a def, we must
    1329             :     // use the same register as the def, so just do that always.
    1330      379389 :     SlotIndex Idx = LIS.getInstructionIndex(*MI);
    1331      714712 :     if (MO.isDef() || MO.isUndef())
    1332             :       Idx = Idx.getRegSlot(MO.isEarlyClobber());
    1333             : 
    1334             :     // Rewrite to the mapped register at Idx.
    1335      379389 :     unsigned RegIdx = RegAssign.lookup(Idx);
    1336      758778 :     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
    1337      379389 :     MO.setReg(LI.reg);
    1338             :     LLVM_DEBUG(dbgs() << "  rewr " << printMBBReference(*MI->getParent())
    1339             :                       << '\t' << Idx << ':' << RegIdx << '\t' << *MI);
    1340             : 
    1341             :     // Extend liveness to Idx if the instruction reads reg.
    1342      759055 :     if (!ExtendRanges || MO.isUndef())
    1343       99214 :       continue;
    1344             : 
    1345             :     // Skip instructions that don't read Reg.
    1346      280175 :     if (MO.isDef()) {
    1347       57464 :       if (!MO.getSubReg() && !MO.isEarlyClobber())
    1348       19122 :         continue;
    1349             :       // We may want to extend a live range for a partial redef, or for a use
    1350             :       // tied to an early clobber.
    1351             :       Idx = Idx.getPrevSlot();
    1352          97 :       if (!Edit->getParent().liveAt(Idx))
    1353           1 :         continue;
    1354             :     } else
    1355             :       Idx = Idx.getRegSlot(true);
    1356             : 
    1357             :     SlotIndex Next = Idx.getNextSlot();
    1358      261052 :     if (LI.hasSubRanges()) {
    1359             :       // We have to delay extending subranges until we have seen all operands
    1360             :       // defining the register. This is because a <def,read-undef> operand
    1361             :       // will create an "undef" point, and we cannot extend any subranges
    1362             :       // until all of them have been accounted for.
    1363         195 :       if (MO.isUse())
    1364         183 :         ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
    1365             :     } else {
    1366             :       LiveRangeCalc &LRC = getLRCalc(RegIdx);
    1367      260857 :       LRC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
    1368             :     }
    1369             :   }
    1370             : 
    1371       29214 :   for (ExtPoint &EP : ExtPoints) {
    1372         366 :     LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
    1373             :     assert(LI.hasSubRanges());
    1374             : 
    1375         366 :     LiveRangeCalc SubLRC;
    1376         183 :     unsigned Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
    1377         135 :     LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
    1378         366 :                               : MRI.getMaxLaneMaskForVReg(Reg);
    1379         749 :     for (LiveInterval::SubRange &S : LI.subranges()) {
    1380         566 :       if ((S.LaneMask & LM).none())
    1381         558 :         continue;
    1382             :       // The problem here can be that the new register may have been created
    1383             :       // for a partially defined original register. For example:
    1384             :       //   %0:subreg_hireg<def,read-undef> = ...
    1385             :       //   ...
    1386             :       //   %1 = COPY %0
    1387         287 :       if (S.empty())
    1388           0 :         continue;
    1389         287 :       SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
    1390         287 :                    &LIS.getVNInfoAllocator());
    1391             :       SmallVector<SlotIndex, 4> Undefs;
    1392         287 :       LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
    1393         287 :       SubLRC.extend(S, EP.Next, 0, Undefs);
    1394             :     }
    1395             :   }
    1396             : 
    1397      191766 :   for (unsigned R : *Edit) {
    1398       67035 :     LiveInterval &LI = LIS.getInterval(R);
    1399       67035 :     if (!LI.hasSubRanges())
    1400       66955 :       continue;
    1401             :     LI.clear();
    1402          80 :     LI.removeEmptySubRanges();
    1403          80 :     LIS.constructMainRangeFromSubranges(LI);
    1404             :   }
    1405       28848 : }
    1406             : 
    1407       17028 : void SplitEditor::deleteRematVictims() {
    1408             :   SmallVector<MachineInstr*, 8> Dead;
    1409      118440 :   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
    1410       42192 :     LiveInterval *LI = &LIS.getInterval(*I);
    1411      305880 :     for (const LiveRange::Segment &S : LI->segments) {
    1412             :       // Dead defs end at the dead slot.
    1413      263688 :       if (S.end != S.valno->def.getDeadSlot())
    1414      245022 :         continue;
    1415        9333 :       if (S.valno->isPHIDef())
    1416           0 :         continue;
    1417        9333 :       MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
    1418             :       assert(MI && "Missing instruction for dead def");
    1419        9333 :       MI->addRegisterDead(LI->reg, &TRI);
    1420             : 
    1421        9333 :       if (!MI->allDefsAreDead())
    1422           0 :         continue;
    1423             : 
    1424             :       LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
    1425        9333 :       Dead.push_back(MI);
    1426             :     }
    1427             :   }
    1428             : 
    1429       17028 :   if (Dead.empty())
    1430             :     return;
    1431             : 
    1432       11808 :   Edit->eliminateDeadDefs(Dead, None, &AA);
    1433             : }
    1434             : 
    1435       10202 : void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {
    1436             :   // Fast-path for common case.
    1437       10202 :   if (!ParentVNI.isPHIDef()) {
    1438       69656 :     for (unsigned I = 0, E = Edit->size(); I != E; ++I)
    1439       24656 :       forceRecompute(I, ParentVNI);
    1440       10172 :     return;
    1441             :   }
    1442             : 
    1443             :   // Trace value through phis.
    1444             :   SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist.
    1445             :   SmallVector<const VNInfo *, 4> WorkList;
    1446          30 :   Visited.insert(&ParentVNI);
    1447          30 :   WorkList.push_back(&ParentVNI);
    1448             : 
    1449          30 :   const LiveInterval &ParentLI = Edit->getParent();
    1450          30 :   const SlotIndexes &Indexes = *LIS.getSlotIndexes();
    1451             :   do {
    1452          90 :     const VNInfo &VNI = *WorkList.back();
    1453             :     WorkList.pop_back();
    1454         726 :     for (unsigned I = 0, E = Edit->size(); I != E; ++I)
    1455         273 :       forceRecompute(I, VNI);
    1456          90 :     if (!VNI.isPHIDef())
    1457          60 :       continue;
    1458             : 
    1459          30 :     MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);
    1460          90 :     for (const MachineBasicBlock *Pred : MBB.predecessors()) {
    1461          60 :       SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
    1462          60 :       VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);
    1463             :       assert(PredVNI && "Value available in PhiVNI predecessor");
    1464          60 :       if (Visited.insert(PredVNI).second)
    1465          60 :         WorkList.push_back(PredVNI);
    1466             :     }
    1467          90 :   } while(!WorkList.empty());
    1468             : }
    1469             : 
    1470       28848 : void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
    1471             :   ++NumFinished;
    1472             : 
    1473             :   // At this point, the live intervals in Edit contain VNInfos corresponding to
    1474             :   // the inserted copies.
    1475             : 
    1476             :   // Add the original defs from the parent interval.
    1477      158878 :   for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
    1478       50591 :     if (ParentVNI->isUnused())
    1479          33 :       continue;
    1480       50558 :     unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
    1481       50558 :     defValue(RegIdx, ParentVNI, ParentVNI->def, true);
    1482             : 
    1483             :     // Force rematted values to be recomputed everywhere.
    1484             :     // The new live ranges may be truncated.
    1485      101116 :     if (Edit->didRematerialize(ParentVNI))
    1486       10202 :       forceRecomputeVNI(*ParentVNI);
    1487             :   }
    1488             : 
    1489             :   // Hoist back-copies to the complement interval when in spill mode.
    1490       28848 :   switch (SpillMode) {
    1491             :   case SM_Partition:
    1492             :     // Leave all back-copies as is.
    1493             :     break;
    1494       17391 :   case SM_Size:
    1495             :   case SM_Speed:
    1496             :     // hoistCopies will behave differently between size and speed.
    1497       17391 :     hoistCopies();
    1498             :   }
    1499             : 
    1500             :   // Transfer the simply mapped values, check if any are skipped.
    1501       28848 :   bool Skipped = transferValues();
    1502             : 
    1503             :   // Rewrite virtual registers, possibly extending ranges.
    1504       28848 :   rewriteAssigned(Skipped);
    1505             : 
    1506       28848 :   if (Skipped)
    1507       17028 :     extendPHIKillRanges();
    1508             :   else
    1509             :     ++NumSimple;
    1510             : 
    1511             :   // Delete defs that were rematted everywhere.
    1512       28848 :   if (Skipped)
    1513       17028 :     deleteRematVictims();
    1514             : 
    1515             :   // Get rid of unused values and set phi-kill flags.
    1516      191772 :   for (unsigned Reg : *Edit) {
    1517       67038 :     LiveInterval &LI = LIS.getInterval(Reg);
    1518       67038 :     LI.removeEmptySubRanges();
    1519       67038 :     LI.RenumberValues();
    1520             :   }
    1521             : 
    1522             :   // Provide a reverse mapping from original indices to Edit ranges.
    1523       28848 :   if (LRMap) {
    1524             :     LRMap->clear();
    1525      191772 :     for (unsigned i = 0, e = Edit->size(); i != e; ++i)
    1526       67038 :       LRMap->push_back(i);
    1527             :   }
    1528             : 
    1529             :   // Now check if any registers were separated into multiple components.
    1530       28848 :   ConnectedVNInfoEqClasses ConEQ(LIS);
    1531      191772 :   for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
    1532             :     // Don't use iterators, they are invalidated by create() below.
    1533       67038 :     unsigned VReg = Edit->get(i);
    1534       67038 :     LiveInterval &LI = LIS.getInterval(VReg);
    1535             :     SmallVector<LiveInterval*, 8> SplitLIs;
    1536       67038 :     LIS.splitSeparateComponents(LI, SplitLIs);
    1537       67038 :     unsigned Original = VRM.getOriginal(VReg);
    1538       83024 :     for (LiveInterval *SplitLI : SplitLIs)
    1539        7993 :       VRM.setIsSplitFromReg(SplitLI->reg, Original);
    1540             : 
    1541             :     // The new intervals all map back to i.
    1542       67038 :     if (LRMap)
    1543      134076 :       LRMap->resize(Edit->size(), i);
    1544             :   }
    1545             : 
    1546             :   // Calculate spill weight and allocation hints for new intervals.
    1547       28848 :   Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI);
    1548             : 
    1549             :   assert(!LRMap || LRMap->size() == Edit->size());
    1550       28848 : }
    1551             : 
    1552             : //===----------------------------------------------------------------------===//
    1553             : //                            Single Block Splitting
    1554             : //===----------------------------------------------------------------------===//
    1555             : 
    1556       62864 : bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,
    1557             :                                            bool SingleInstrs) const {
    1558             :   // Always split for multiple instructions.
    1559       62864 :   if (!BI.isOneInstr())
    1560             :     return true;
    1561             :   // Don't split for single instructions unless explicitly requested.
    1562       50724 :   if (!SingleInstrs)
    1563             :     return false;
    1564             :   // Splitting a live-through range always makes progress.
    1565         523 :   if (BI.LiveIn && BI.LiveOut)
    1566             :     return true;
    1567             :   // No point in isolating a copy. It has no register class constraints.
    1568             :   if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
    1569             :     return false;
    1570             :   // Finally, don't isolate an end point that was created by earlier splits.
    1571         390 :   return isOriginalEndpoint(BI.FirstInstr);
    1572             : }
    1573             : 
    1574       12616 : void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) {
    1575       12616 :   openIntv();
    1576       25232 :   SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
    1577             :   SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
    1578       25232 :     LastSplitPoint));
    1579       21899 :   if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
    1580       12594 :     useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
    1581             :   } else {
    1582             :       // The last use is after the last valid split point.
    1583          22 :     SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
    1584             :     useIntv(SegStart, SegStop);
    1585          22 :     overlapIntv(SegStop, BI.LastInstr);
    1586             :   }
    1587       12616 : }
    1588             : 
    1589             : //===----------------------------------------------------------------------===//
    1590             : //                    Global Live Range Splitting Support
    1591             : //===----------------------------------------------------------------------===//
    1592             : 
    1593             : // These methods support a method of global live range splitting that uses a
    1594             : // global algorithm to decide intervals for CFG edges. They will insert split
    1595             : // points and color intervals in basic blocks while avoiding interference.
    1596             : //
    1597             : // Note that splitSingleBlock is also useful for blocks where both CFG edges
    1598             : // are on the stack.
    1599             : 
    1600      131744 : void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
    1601             :                                         unsigned IntvIn, SlotIndex LeaveBefore,
    1602             :                                         unsigned IntvOut, SlotIndex EnterAfter){
    1603             :   SlotIndex Start, Stop;
    1604      131744 :   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
    1605             : 
    1606             :   LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop
    1607             :                     << ") intf " << LeaveBefore << '-' << EnterAfter
    1608             :                     << ", live-through " << IntvIn << " -> " << IntvOut);
    1609             : 
    1610             :   assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
    1611             : 
    1612             :   assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
    1613             :   assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
    1614             :   assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
    1615             : 
    1616      131744 :   MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
    1617             : 
    1618      131744 :   if (!IntvOut) {
    1619             :     LLVM_DEBUG(dbgs() << ", spill on entry.\n");
    1620             :     //
    1621             :     //        <<<<<<<<<    Possible LeaveBefore interference.
    1622             :     //    |-----------|    Live through.
    1623             :     //    -____________    Spill on entry.
    1624             :     //
    1625             :     selectIntv(IntvIn);
    1626       13903 :     SlotIndex Idx = leaveIntvAtTop(*MBB);
    1627             :     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
    1628             :     (void)Idx;
    1629             :     return;
    1630             :   }
    1631             : 
    1632      117841 :   if (!IntvIn) {
    1633             :     LLVM_DEBUG(dbgs() << ", reload on exit.\n");
    1634             :     //
    1635             :     //    >>>>>>>          Possible EnterAfter interference.
    1636             :     //    |-----------|    Live through.
    1637             :     //    ___________--    Reload on exit.
    1638             :     //
    1639             :     selectIntv(IntvOut);
    1640       10671 :     SlotIndex Idx = enterIntvAtEnd(*MBB);
    1641             :     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
    1642             :     (void)Idx;
    1643             :     return;
    1644             :   }
    1645             : 
    1646      315891 :   if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
    1647             :     LLVM_DEBUG(dbgs() << ", straight through.\n");
    1648             :     //
    1649             :     //    |-----------|    Live through.
    1650             :     //    -------------    Straight through, same intv, no interference.
    1651             :     //
    1652             :     selectIntv(IntvOut);
    1653             :     useIntv(Start, Stop);
    1654             :     return;
    1655             :   }
    1656             : 
    1657             :   // We cannot legally insert splits after LSP.
    1658        3451 :   SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
    1659             :   assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
    1660             : 
    1661        6436 :   if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
    1662             :                   LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
    1663             :     LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");
    1664             :     //
    1665             :     //    >>>>     <<<<    Non-overlapping EnterAfter/LeaveBefore interference.
    1666             :     //    |-----------|    Live through.
    1667             :     //    ------=======    Switch intervals between interference.
    1668             :     //
    1669             :     selectIntv(IntvOut);
    1670             :     SlotIndex Idx;
    1671        2985 :     if (LeaveBefore && LeaveBefore < LSP) {
    1672         791 :       Idx = enterIntvBefore(LeaveBefore);
    1673             :       useIntv(Idx, Stop);
    1674             :     } else {
    1675        1377 :       Idx = enterIntvAtEnd(*MBB);
    1676             :     }
    1677             :     selectIntv(IntvIn);
    1678             :     useIntv(Start, Idx);
    1679             :     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
    1680             :     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
    1681             :     return;
    1682             :   }
    1683             : 
    1684             :   LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");
    1685             :   //
    1686             :   //    >>><><><><<<<    Overlapping EnterAfter/LeaveBefore interference.
    1687             :   //    |-----------|    Live through.
    1688             :   //    ==---------==    Switch intervals before/after interference.
    1689             :   //
    1690             :   assert(LeaveBefore <= EnterAfter && "Missed case");
    1691             : 
    1692             :   selectIntv(IntvOut);
    1693        1283 :   SlotIndex Idx = enterIntvAfter(EnterAfter);
    1694             :   useIntv(Idx, Stop);
    1695             :   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
    1696             : 
    1697             :   selectIntv(IntvIn);
    1698        1283 :   Idx = leaveIntvBefore(LeaveBefore);
    1699             :   useIntv(Start, Idx);
    1700             :   assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
    1701             : }
    1702             : 
    1703       16728 : void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
    1704             :                                   unsigned IntvIn, SlotIndex LeaveBefore) {
    1705             :   SlotIndex Start, Stop;
    1706       16728 :   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
    1707             : 
    1708             :   LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
    1709             :                     << Stop << "), uses " << BI.FirstInstr << '-'
    1710             :                     << BI.LastInstr << ", reg-in " << IntvIn
    1711             :                     << ", leave before " << LeaveBefore
    1712             :                     << (BI.LiveOut ? ", stack-out" : ", killed in block"));
    1713             : 
    1714             :   assert(IntvIn && "Must have register in");
    1715             :   assert(BI.LiveIn && "Must be live-in");
    1716             :   assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
    1717             : 
    1718       30916 :   if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
    1719             :     LLVM_DEBUG(dbgs() << " before interference.\n");
    1720             :     //
    1721             :     //               <<<    Interference after kill.
    1722             :     //     |---o---x   |    Killed in block.
    1723             :     //     =========        Use IntvIn everywhere.
    1724             :     //
    1725             :     selectIntv(IntvIn);
    1726             :     useIntv(Start, BI.LastInstr);
    1727       16728 :     return;
    1728             :   }
    1729             : 
    1730        5664 :   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
    1731             : 
    1732        7780 :   if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
    1733             :     //
    1734             :     //               <<<    Possible interference after last use.
    1735             :     //     |---o---o---|    Live-out on stack.
    1736             :     //     =========____    Leave IntvIn after last use.
    1737             :     //
    1738             :     //                 <    Interference after last use.
    1739             :     //     |---o---o--o|    Live-out on stack, late last use.
    1740             :     //     ============     Copy to stack after LSP, overlap IntvIn.
    1741             :     //            \_____    Stack interval is live-out.
    1742             :     //
    1743        4828 :     if (BI.LastInstr < LSP) {
    1744             :       LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");
    1745             :       selectIntv(IntvIn);
    1746        4828 :       SlotIndex Idx = leaveIntvAfter(BI.LastInstr);
    1747             :       useIntv(Start, Idx);
    1748             :       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
    1749             :     } else {
    1750             :       LLVM_DEBUG(dbgs() << ", spill before last split point.\n");
    1751             :       selectIntv(IntvIn);
    1752           0 :       SlotIndex Idx = leaveIntvBefore(LSP);
    1753           0 :       overlapIntv(Idx, BI.LastInstr);
    1754             :       useIntv(Start, Idx);
    1755             :       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
    1756             :     }
    1757             :     return;
    1758             :   }
    1759             : 
    1760             :   // The interference is overlapping somewhere we wanted to use IntvIn. That
    1761             :   // means we need to create a local interval that can be allocated a
    1762             :   // different register.
    1763         836 :   unsigned LocalIntv = openIntv();
    1764             :   (void)LocalIntv;
    1765             :   LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
    1766             : 
    1767        1055 :   if (!BI.LiveOut || BI.LastInstr < LSP) {
    1768             :     //
    1769             :     //           <<<<<<<    Interference overlapping uses.
    1770             :     //     |---o---o---|    Live-out on stack.
    1771             :     //     =====----____    Leave IntvIn before interference, then spill.
    1772             :     //
    1773         836 :     SlotIndex To = leaveIntvAfter(BI.LastInstr);
    1774         836 :     SlotIndex From = enterIntvBefore(LeaveBefore);
    1775             :     useIntv(From, To);
    1776             :     selectIntv(IntvIn);
    1777             :     useIntv(Start, From);
    1778             :     assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
    1779             :     return;
    1780             :   }
    1781             : 
    1782             :   //           <<<<<<<    Interference overlapping uses.
    1783             :   //     |---o---o--o|    Live-out on stack, late last use.
    1784             :   //     =====-------     Copy to stack before LSP, overlap LocalIntv.
    1785             :   //            \_____    Stack interval is live-out.
    1786             :   //
    1787           0 :   SlotIndex To = leaveIntvBefore(LSP);
    1788           0 :   overlapIntv(To, BI.LastInstr);
    1789           0 :   SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
    1790             :   useIntv(From, To);
    1791             :   selectIntv(IntvIn);
    1792             :   useIntv(Start, From);
    1793             :   assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
    1794             : }
    1795             : 
    1796       16662 : void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
    1797             :                                    unsigned IntvOut, SlotIndex EnterAfter) {
    1798             :   SlotIndex Start, Stop;
    1799       16662 :   std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
    1800             : 
    1801             :   LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
    1802             :                     << Stop << "), uses " << BI.FirstInstr << '-'
    1803             :                     << BI.LastInstr << ", reg-out " << IntvOut
    1804             :                     << ", enter after " << EnterAfter
    1805             :                     << (BI.LiveIn ? ", stack-in" : ", defined in block"));
    1806             : 
    1807       33324 :   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
    1808             : 
    1809             :   assert(IntvOut && "Must have register out");
    1810             :   assert(BI.LiveOut && "Must be live-out");
    1811             :   assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
    1812             : 
    1813       31997 :   if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
    1814             :     LLVM_DEBUG(dbgs() << " after interference.\n");
    1815             :     //
    1816             :     //    >>>>             Interference before def.
    1817             :     //    |   o---o---|    Defined in block.
    1818             :     //        =========    Use IntvOut everywhere.
    1819             :     //
    1820             :     selectIntv(IntvOut);
    1821             :     useIntv(BI.FirstInstr, Stop);
    1822       15692 :     return;
    1823             :   }
    1824             : 
    1825        8426 :   if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
    1826             :     LLVM_DEBUG(dbgs() << ", reload after interference.\n");
    1827             :     //
    1828             :     //    >>>>             Interference before def.
    1829             :     //    |---o---o---|    Live-through, stack-in.
    1830             :     //    ____=========    Enter IntvOut before first use.
    1831             :     //
    1832             :     selectIntv(IntvOut);
    1833       10544 :     SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
    1834             :     useIntv(Idx, Stop);
    1835             :     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
    1836             :     return;
    1837             :   }
    1838             : 
    1839             :   // The interference is overlapping somewhere we wanted to use IntvOut. That
    1840             :   // means we need to create a local interval that can be allocated a
    1841             :   // different register.
    1842             :   LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");
    1843             :   //
    1844             :   //    >>>>>>>          Interference overlapping uses.
    1845             :   //    |---o---o---|    Live-through, stack-in.
    1846             :   //    ____---======    Create local interval for interference range.
    1847             :   //
    1848             :   selectIntv(IntvOut);
    1849         970 :   SlotIndex Idx = enterIntvAfter(EnterAfter);
    1850             :   useIntv(Idx, Stop);
    1851             :   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
    1852             : 
    1853         970 :   openIntv();
    1854        1940 :   SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
    1855             :   useIntv(From, Idx);
    1856             : }

Generated by: LCOV version 1.13