1 files changed, 1 insertions, 266 deletions

diff --git a/llvm/lib/CodeGen/LiveInterval.cpp b/llvm/lib/CodeGen/LiveInterval.cpp
index 79b6a1a4404..10e25f1fb81 100644
--- a/llvm/lib/CodeGen/LiveInterval.cpp
+++ b/llvm/lib/CodeGen/LiveInterval.cpp
@@ -20,16 +20,14 @@
 
 #include "llvm/CodeGen/LiveInterval.h"
 
-#include "PHIEliminationUtils.h"
+#include "LiveRangeUtils.h"
 #include "RegisterCoalescer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include <algorithm>
 using namespace llvm;
@@ -1176,40 +1174,6 @@ unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) {
   return EqClass.getNumClasses();
 }
 
-template<typename LiveRangeT, typename EqClassesT>
-static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[],
-                            EqClassesT VNIClasses) {
-  // Move segments to new intervals.
-  LiveRange::iterator J = LR.begin(), E = LR.end();
-  while (J != E && VNIClasses[J->valno->id] == 0)
-    ++J;
-  for (LiveRange::iterator I = J; I != E; ++I) {
-    if (unsigned eq = VNIClasses[I->valno->id]) {
-      assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) &&
-             "New intervals should be empty");
-      SplitLRs[eq-1]->segments.push_back(*I);
-    } else
-      *J++ = *I;
-  }
-  LR.segments.erase(J, E);
-
-  // Transfer VNInfos to their new owners and renumber them.
-  unsigned j = 0, e = LR.getNumValNums();
-  while (j != e && VNIClasses[j] == 0)
-    ++j;
-  for (unsigned i = j; i != e; ++i) {
-    VNInfo *VNI = LR.getValNumInfo(i);
-    if (unsigned eq = VNIClasses[i]) {
-      VNI->id = SplitLRs[eq-1]->getNumValNums();
-      SplitLRs[eq-1]->valnos.push_back(VNI);
-    } else {
-      VNI->id = j;
-      LR.valnos[j++] = VNI;
-    }
-  }
-  LR.valnos.resize(j);
-}
-
 void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[],
                                           MachineRegisterInfo &MRI) {
   // Rewrite instructions.
@@ -1276,232 +1240,3 @@ void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[],
   // Distribute main liverange.
   DistributeRange(LI, LIV, EqClass);
 }
-
-void ConnectedSubRegClasses::renameComponents(LiveInterval &LI) const {
-  // Shortcut: We cannot have split components with a single definition.
-  if (LI.valnos.size() < 2)
-    return;
-
-  SmallVector<SubRangeInfo, 4> SubRangeInfos;
-  IntEqClasses Classes;
-  if (!findComponents(Classes, SubRangeInfos, LI))
-    return;
-
-  // Create a new VReg for each class.
-  unsigned Reg = LI.reg;
-  const TargetRegisterClass *RegClass = MRI.getRegClass(Reg);
-  SmallVector<LiveInterval*, 4> Intervals;
-  Intervals.push_back(&LI);
-  for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
-       ++I) {
-    unsigned NewVReg = MRI.createVirtualRegister(RegClass);
-    LiveInterval &NewLI = LIS.createEmptyInterval(NewVReg);
-    Intervals.push_back(&NewLI);
-  }
-
-  rewriteOperands(Classes, SubRangeInfos, Intervals);
-  distribute(Classes, SubRangeInfos, Intervals);
-  computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
-}
-
-bool ConnectedSubRegClasses::findComponents(IntEqClasses &Classes,
-    SmallVectorImpl<ConnectedSubRegClasses::SubRangeInfo> &SubRangeInfos,
-    LiveInterval &LI) const {
-  // First step: Create connected components for the VNInfos inside the
-  // subranges and count the global number of such components.
-  unsigned NumComponents = 0;
-  for (LiveInterval::SubRange &SR : LI.subranges()) {
-    SubRangeInfos.push_back(SubRangeInfo(LIS, SR, NumComponents));
-    ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
-
-    unsigned NumSubComponents = ConEQ.Classify(SR);
-    NumComponents += NumSubComponents;
-  }
-  // Shortcut: With only 1 subrange, the normal separate component tests are
-  // enough and we do not need to perform the union-find on the subregister
-  // segments.
-  if (SubRangeInfos.size() < 2)
-    return false;
-
-  // Next step: Build union-find structure over all subranges and merge classes
-  // across subranges when they are affected by the same MachineOperand.
-  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
-  Classes.grow(NumComponents);
-  unsigned Reg = LI.reg;
-  for (const MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) {
-    if (!MO.isDef() && !MO.readsReg())
-      continue;
-    unsigned SubRegIdx = MO.getSubReg();
-    LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
-    unsigned MergedID = ~0u;
-    for (ConnectedSubRegClasses::SubRangeInfo &SRInfo : SubRangeInfos) {
-      const LiveInterval::SubRange &SR = *SRInfo.SR;
-      if ((SR.LaneMask & LaneMask) == 0)
-        continue;
-      SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent());
-      Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
-                       : Pos.getBaseIndex();
-      const VNInfo *VNI = SR.getVNInfoAt(Pos);
-      if (VNI == nullptr)
-        continue;
-
-      // Map to local representant ID.
-      unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
-      // Global ID
-      unsigned ID = LocalID + SRInfo.Index;
-      // Merge other sets
-      MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
-    }
-  }
-
-  // Early exit if we ended up with a single equivalence class.
-  Classes.compress();
-  unsigned NumClasses = Classes.getNumClasses();
-  return NumClasses > 1;
-}
-
-void ConnectedSubRegClasses::rewriteOperands(const IntEqClasses &Classes,
-    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
-  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
-  unsigned Reg = Intervals[0]->reg;;
-  for (MachineRegisterInfo::reg_nodbg_iterator I = MRI.reg_nodbg_begin(Reg),
-       E = MRI.reg_nodbg_end(); I != E; ) {
-    MachineOperand &MO = *I++;
-    if (!MO.isDef() && !MO.readsReg())
-      continue;
-
-    MachineInstr &MI = *MO.getParent();
-
-    SlotIndex Pos = LIS.getInstructionIndex(MI);
-    unsigned SubRegIdx = MO.getSubReg();
-    LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
-
-    unsigned ID = ~0u;
-    for (const SubRangeInfo &SRInfo : SubRangeInfos) {
-      const LiveInterval::SubRange &SR = *SRInfo.SR;
-      if ((SR.LaneMask & LaneMask) == 0)
-        continue;
-      LiveRange::const_iterator I = SR.find(Pos);
-      if (I == SR.end())
-        continue;
-
-      const VNInfo &VNI = *I->valno;
-      // Map to local representant ID.
-      unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
-      // Global ID
-      ID = Classes[LocalID + SRInfo.Index];
-      break;
-    }
-
-    unsigned VReg = Intervals[ID]->reg;
-    MO.setReg(VReg);
-  }
-}
-
-void ConnectedSubRegClasses::distribute(const IntEqClasses &Classes,
-    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
-  unsigned NumClasses = Classes.getNumClasses();
-  SmallVector<unsigned, 8> VNIMapping;
-  SmallVector<LiveInterval::SubRange*, 8> SubRanges;
-  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
-  for (const SubRangeInfo &SRInfo : SubRangeInfos) {
-    LiveInterval::SubRange &SR = *SRInfo.SR;
-    unsigned NumValNos = SR.valnos.size();
-    VNIMapping.clear();
-    VNIMapping.reserve(NumValNos);
-    SubRanges.clear();
-    SubRanges.resize(NumClasses-1, nullptr);
-    for (unsigned I = 0; I < NumValNos; ++I) {
-      const VNInfo &VNI = *SR.valnos[I];
-      unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
-      unsigned ID = Classes[LocalID + SRInfo.Index];
-      VNIMapping.push_back(ID);
-      if (ID > 0 && SubRanges[ID-1] == nullptr)
-        SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
-    }
-    DistributeRange(SR, SubRanges.data(), VNIMapping);
-  }
-}
-
-static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
-  for (const LiveInterval::SubRange &SR : LI.subranges()) {
-    if (SR.liveAt(Pos))
-      return true;
-  }
-  return false;
-}
-
-void ConnectedSubRegClasses::computeMainRangesFixFlags(
-    const IntEqClasses &Classes,
-    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
-  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
-  const SlotIndexes &Indexes = *LIS.getSlotIndexes();
-  for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
-    LiveInterval &LI = *Intervals[I];
-    unsigned Reg = LI.reg;
-
-    LI.removeEmptySubRanges();
-
-    // There must be a def (or live-in) before every use. Splitting vregs may
-    // violate this principle as the splitted vreg may not have a definition on
-    // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
-    for (const LiveInterval::SubRange &SR : LI.subranges()) {
-      // Search for "PHI" value numbers in the subranges. We must find a live
-      // value in each predecessor block, add an IMPLICIT_DEF where it is
-      // missing.
-      for (unsigned I = 0; I < SR.valnos.size(); ++I) {
-        const VNInfo &VNI = *SR.valnos[I];
-        if (VNI.isUnused() || !VNI.isPHIDef())
-          continue;
-
-        SlotIndex Def = VNI.def;
-        MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
-        for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
-          SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
-          if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
-            continue;
-
-          MachineBasicBlock::iterator InsertPos =
-            llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
-          const MCInstrDesc &MCDesc = TII.get(TargetOpcode::IMPLICIT_DEF);
-          MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
-                                               DebugLoc(), MCDesc, Reg);
-          SlotIndex DefIdx = LIS.InsertMachineInstrInMaps(*ImpDef);
-          SlotIndex RegDefIdx = DefIdx.getRegSlot();
-          for (LiveInterval::SubRange &SR : LI.subranges()) {
-            VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
-            SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
-          }
-        }
-      }
-    }
-
-    for (MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) {
-      if (!MO.isDef())
-        continue;
-      unsigned SubRegIdx = MO.getSubReg();
-      if (SubRegIdx == 0)
-        continue;
-      // After assigning the new vreg we may not have any other sublanes living
-      // in and out of the instruction anymore. We need to add new dead and
-      // undef flags in these cases.
-      if (!MO.isUndef()) {
-        SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent());
-        if (!subRangeLiveAt(LI, Pos))
-          MO.setIsUndef();
-      }
-      if (!MO.isDead()) {
-        SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()).getDeadSlot();
-        if (!subRangeLiveAt(LI, Pos))
-          MO.setIsDead();
-      }
-    }
-
-    if (I == 0)
-      LI.clear();
-    LIS.constructMainRangeFromSubranges(LI);
-  }
-}