CodeGen: Refactor renameDisconnectedComponents() as a pass

[MatzeB]

Summary

Refactor LiveIntervals::renameDisconnectedComponents() to be a pass.
Also change the name to "RenameIndependentSubregs":

• renameDisconnectedComponents() worked on a MachineFunction at a time so it is a natural candidate for an machine function pass.

• The algorithm is testable with a .mir test now.

• This also fixes a problem where the lazy renaming as part of the MachineScheduler introduced IMPLICIT_DEF instructions after the number of a nodes in a region were counted leading to a mismatch.

[MatzeB]

Add a .mir test for the RenameIndependentSubregs pass.

[MatzeB]

Actually include newly created RenameIndependentSubregs.cpp file.

[qcolombet]

Hi Matthias,

I’ll try to look at this next week.

Thanks for your patience!

Cheers,
-Quentin

[qcolombet]

Hi Matthias,

LGTM.

Nitpicks inlined.

Cheers,
-Quentin

lib/CodeGen/LiveRangeUtils.h

10

typo: functions

22

typo: to to

lib/CodeGen/RenameIndependentSubregs.cpp

1

Copy/paste :)

40

Could you add a DEBUG_TYPE and a few DEBUG statements in the pass to follow what is going on?

107

Period

122

DEBUG comment.
Like we could print the register here.

127

DEBUG comment.
And add a comment here to say we are going to check if that live-range has several component, etc.

137

Although the current implementation is correct, I was wondering what are your thoughts regarding relaxing the constraints on the register class and constraining them back when we rewrite the operands?
I actually do not expect that we would get much more freedom for regalloc afterwards, but who knows.

Note: the current implementation is the right thing to do, I was thinking in terms of follow-up patch.

201

DEBUG comment.
Print that number.

test/CodeGen/AMDGPU/rename-independent-subregs.mir

6

Could you add a comment explaining what configuration does this test check?
Basically, I would expecting something stating that this test checks that we correctly split %0 as it has three disjoint sets.

[MatzeB]

lib/CodeGen/RenameIndependentSubregs.cpp

40

I added some DEBUG printing that tells you how many equivalence classes were found and into which newly created vregs they were distributed. I opted to not print anything for vregs where no independent classes could be found to keep the debug output small.

107

I kept this as it is the officially recommended way in the llvm coding convention and what is done in most parts of llvm. I know it contradicts that other rule in the coding convention that states that you should write sentences ending in periods in your comments...

137

Yes this indeed something we could do in a follow-up commit, I added a TODO comment.
And for the record: We have the same issue in the LiveIntervals::splitSeparateComponents() code.

include/llvm/CodeGen/LiveInterval.h

public:
 
     /// Distribute values in \p LI into a separate LiveIntervals
     /// for each connected component. LIV must have an empty LiveInterval for
     /// each additional connected component. The first connected component is
     /// left in \p LI.
     void Distribute(LiveInterval &LI, LiveInterval *LIV[],
                     MachineRegisterInfo &MRI);
   };
-
-  /// Helper class that can divide MachineOperands of a virtual register into
-  /// equivalence classes of connected components.
-  /// MachineOperands belong to the same equivalence class when they are part of
-  /// the same SubRange segment or adjacent segments (adjacent in control
-  /// flow); Different subranges affected by the same MachineOperand belong to
-  /// the same equivalence class.
-  ///
-  /// Example:
-  ///   vreg0:sub0 = ...
-  ///   vreg0:sub1 = ...
-  ///   vreg0:sub2 = ...
-  ///   ...
-  ///   xxx        = op vreg0:sub1
-  ///   vreg0:sub1 = ...
-  ///   store vreg0:sub0_sub1
-  ///
-  /// The example contains 3 different equivalence classes:
-  ///   - One for the (dead) vreg0:sub2 definition
-  ///   - One containing the first vreg0:sub1 definition and its use,
-  ///     but not the second definition!
-  ///   - The remaining class contains all other operands involving vreg0.
-  ///
-  /// We provide a utility function here to rename disjunct classes to different
-  /// virtual registers.
-  class ConnectedSubRegClasses {
-    LiveIntervals &LIS;
-    MachineRegisterInfo &MRI;
-    const TargetInstrInfo &TII;
-
-  public:
-    ConnectedSubRegClasses(LiveIntervals &LIS, MachineRegisterInfo &MRI,
-                           const TargetInstrInfo &TII)
-      : LIS(LIS), MRI(MRI), TII(TII) {}
-
-    /// Split unrelated subregister components and rename them to new vregs.
-    void renameComponents(LiveInterval &LI) const;
-
-  private:
-    struct SubRangeInfo {
-      ConnectedVNInfoEqClasses ConEQ;
-      LiveInterval::SubRange *SR;
-      unsigned Index;
-
-      SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
-                   unsigned Index)
-        : ConEQ(LIS), SR(&SR), Index(Index) {}
-    };
-
-    /// \brief Build a vector of SubRange infos and a union find set of
-    /// equivalence classes.
-    /// Returns true if more than 1 equivalence class was found.
-    bool findComponents(IntEqClasses &Classes,
-                        SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                        LiveInterval &LI) const;
-
-    /// \brief Distribute the LiveInterval segments into the new LiveIntervals
-    /// belonging to their class.
-    void distribute(const IntEqClasses &Classes,
-                    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                    const SmallVectorImpl<LiveInterval*> &Intervals) const;
-
-    /// \brief Constructs main liverange and add missing undef+dead flags.
-    void computeMainRangesFixFlags(const IntEqClasses &Classes,
-        const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-        const SmallVectorImpl<LiveInterval*> &Intervals) const;
-
-    /// Rewrite Machine Operands to use the new vreg belonging to their class.
-    void rewriteOperands(const IntEqClasses &Classes,
-                         const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                         const SmallVectorImpl<LiveInterval*> &Intervals) const;
-  };
 }
 #endif

include/llvm/CodeGen/LiveIntervalAnalysis.h

public:
     /// Remove value number and related live segments of @p LI and its subranges
     /// that start at position @p Pos.
     void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos);
 
     /// Split separate components in LiveInterval \p LI into separate intervals.
     void splitSeparateComponents(LiveInterval &LI,
                                  SmallVectorImpl<LiveInterval*> &SplitLIs);
 
-    /// Assure dead subregister definitions have their own vreg assigned.
-    /// This calls ConnectedSubRegClasses::splitSeparateSubRegComponent()
-    /// on each virtual register.
-    void renameDisconnectedComponents();
-
     /// For live interval \p LI with correct SubRanges construct matching
     /// information for the main live range. Expects the main live range to not
     /// have any segments or value numbers.
     void constructMainRangeFromSubranges(LiveInterval &LI);
 
   private:
     /// Compute live intervals for all virtual registers.
     void computeVirtRegs();

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   ///
   Pass *createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset,
                               bool OnlyOptimizeForSize = false,
                               bool MergeExternalByDefault = false);
 
   /// This pass splits the stack into a safe stack and an unsafe stack to
   /// protect against stack-based overflow vulnerabilities.
   FunctionPass *createSafeStackPass(const TargetMachine *TM = nullptr);
+
+  /// This pass detects subregister lanes in a virtual register that are used
+  /// independently of other lanes and splits them into separate virtual
+  /// registers.
+  extern char &RenameIndependentSubregsID;
 } // End llvm namespace
 
 /// Target machine pass initializer for passes with dependencies. Use with
 /// INITIALIZE_TM_PASS_END.
 #define INITIALIZE_TM_PASS_BEGIN INITIALIZE_PASS_BEGIN
 
 /// Target machine pass initializer for passes with dependencies. Use with
 /// INITIALIZE_TM_PASS_BEGIN.

include/llvm/InitializePasses.h

 void initializeReassociateLegacyPassPass(PassRegistry&);
 void initializeRegBankSelectPass(PassRegistry &);
 void initializeRegToMemPass(PassRegistry&);
 void initializeRegionInfoPassPass(PassRegistry&);
 void initializeRegionOnlyPrinterPass(PassRegistry&);
 void initializeRegionOnlyViewerPass(PassRegistry&);
 void initializeRegionPrinterPass(PassRegistry&);
 void initializeRegionViewerPass(PassRegistry&);
+void initializeRenameIndependentSubregsPass(PassRegistry&);
 void initializeReversePostOrderFunctionAttrsPass(PassRegistry&);
 void initializeRewriteStatepointsForGCPass(PassRegistry&);
 void initializeSafeStackPass(PassRegistry&);
 void initializeSCCPLegacyPassPass(PassRegistry &);
 void initializeSROALegacyPassPass(PassRegistry&);
 void initializeSROA_DTPass(PassRegistry&);
 void initializeSROA_SSAUpPass(PassRegistry&);
 void initializeSCEVAAWrapperPassPass(PassRegistry&);

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   RegAllocBasic.cpp
   RegAllocFast.cpp
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp
   RegisterScavenging.cpp
+  RenameIndependentSubregs.cpp
   SafeStack.cpp
   ScheduleDAG.cpp
   ScheduleDAGInstrs.cpp
   ScheduleDAGPrinter.cpp
   ScoreboardHazardRecognizer.cpp
   ShadowStackGCLowering.cpp
   ShrinkWrap.cpp
   SjLjEHPrepare.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializePHIEliminationPass(Registry);
   initializePeepholeOptimizerPass(Registry);
   initializePostMachineSchedulerPass(Registry);
   initializePostRAHazardRecognizerPass(Registry);
   initializePostRASchedulerPass(Registry);
   initializePreISelIntrinsicLoweringPass(Registry);
   initializeProcessImplicitDefsPass(Registry);
   initializeRegisterCoalescerPass(Registry);
+  initializeRenameIndependentSubregsPass(Registry);
   initializeShrinkWrapPass(Registry);
   initializeSlotIndexesPass(Registry);
   initializeStackColoringPass(Registry);
   initializeStackMapLivenessPass(Registry);
   initializeLiveDebugValuesPass(Registry);
   initializeSafeStackPass(Registry);
   initializeStackProtectorPass(Registry);
   initializeStackSlotColoringPass(Registry);

lib/CodeGen/LiveInterval.cpp

 // i.e. a range might look like [1,20), [50,65), [1000,1001).  Each
 // individual segment is represented as an instance of LiveRange::Segment,
 // and the whole range is represented as an instance of LiveRange.
 //
 //===----------------------------------------------------------------------===//
 
 #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;
 
 namespace {
 //===----------------------------------------------------------------------===//
 // Implementation of various methods necessary for calculation of live ranges.
 // The implementation of the methods abstracts from the concrete type of the
unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) {
   // Lump all the unused values in with the last used value.
   if (used && unused)
     EqClass.join(used->id, unused->id);
 
   EqClass.compress();
   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.
   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
        RE = MRI.reg_end(); RI != RE;) {
     MachineOperand &MO = *RI;
     MachineInstr *MI = RI->getParent();
     ++RI;
for (LiveInterval::SubRange &SR : LI.subranges()) {
       DistributeRange(SR, SubRanges.data(), VNIMapping);
     }
     LI.removeEmptySubRanges();
   }
 
   // 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);
-  }
-}

lib/CodeGen/LiveIntervalAnalysis.cpp

void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
   for (unsigned I = 1; I < NumComp; ++I) {
     unsigned NewVReg = MRI->createVirtualRegister(RegClass);
     LiveInterval &NewLI = createEmptyInterval(NewVReg);
     SplitLIs.push_back(&NewLI);
   }
   ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
 }
 
-void LiveIntervals::renameDisconnectedComponents() {
-  ConnectedSubRegClasses SubRegClasses(*this, *MRI, *TII);
-
-  // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
-  // created vregs end up with higher numbers but do not need to be visited as
-  // there can't be any further splitting.
-  for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
-    unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
-    LiveInterval *LI = VirtRegIntervals[Reg];
-    if (LI == nullptr || !LI->hasSubRanges())
-      continue;
-
-    SubRegClasses.renameComponents(*LI);
-  }
-}
-
 void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
   assert(LRCalc && "LRCalc not initialized.");
   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
   LRCalc->constructMainRangeFromSubranges(LI);
 }

lib/CodeGen/LiveRangeUtils.h

+//===-- LiveRangeUtils.h - Live Range modification utilities ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// This file contains helper function to modify live ranges.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_CODEGEN_LIVERANGEUTILS_H
+#define LLVM_LIB_CODEGEN_LIVERANGEUTILS_H
+
+#include "llvm/CodeGen/LiveInterval.h"
+
+namespace llvm {
+
+/// Helper function to to split live segments assigned to different classes to
+/// new live range objects.
+template<typename LiveRangeT, typename EqClassesT>
+static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[],
+                            EqClassesT VNIClasses) {
+  // Move segments to new intervals.
+  typename LiveRangeT::iterator J = LR.begin(), E = LR.end();
+  while (J != E && VNIClasses[J->valno->id] == 0)
+    ++J;
+  for (typename LiveRangeT::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);
+}
+
+} // End llvm namespace
+
+#endif

lib/CodeGen/MachineScheduler.cpp

void ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb,
 
   // For convenience remember the end of the liveness region.
   LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd);
 
   SUPressureDiffs.clear();
 
   ShouldTrackPressure = SchedImpl->shouldTrackPressure();
   ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks();
-
-  if (ShouldTrackLaneMasks) {
-    if (!ShouldTrackPressure)
-      report_fatal_error("ShouldTrackLaneMasks requires ShouldTrackPressure");
-    // Dead subregister defs have no users and therefore no dependencies,
-    // moving them around may cause liveintervals to degrade into multiple
-    // components. Change independent components to have their own vreg to avoid
-    // this.
-    if (!DisconnectedComponentsRenamed)
-      LIS->renameDisconnectedComponents();
-  }
 }
 
 // Setup the register pressure trackers for the top scheduled top and bottom
 // scheduled regions.
 void ScheduleDAGMILive::initRegPressure() {
   TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin,
                     ShouldTrackLaneMasks, false);
   BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,

lib/CodeGen/RenameIndependentSubregs.cpp

+//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// Rename independent subregisters looks for virtual registers with
+/// independently used subregisters and renames them to new virtual registers.
+/// Example: In the following:
+///   %vreg0:sub0<read-undef> = ...
+///   %vreg0:sub1 = ...
+///   use %vreg0:sub0
+///   %vreg0:sub0 = ...
+///   use %vreg0:sub0
+///   use %vreg0:sub1
+/// sub0 and sub1 are never used together, and we have two independent sub0
+/// definitions. This pass will rename to:
+///   %vreg0:sub0<read-undef> = ...
+///   %vreg1:sub1<read-undef> = ...
+///   use %vreg1:sub1
+///   %vreg2:sub1<read-undef> = ...
+///   use %vreg2:sub1
+///   use %vreg0:sub0
+//
+//===----------------------------------------------------------------------===//
+
+#include "LiveRangeUtils.h"
+#include "PHIEliminationUtils.h"
+#include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+
+using namespace llvm;
+
+namespace {
+
+class RenameIndependentSubregs : public MachineFunctionPass {
+public:
+  static char ID;
+  RenameIndependentSubregs() : MachineFunctionPass(ID) {}
+
+  const char *getPassName() const override {
+    return "Rename Disconnected Subregister Components";
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addRequired<LiveIntervals>();
+    AU.addPreserved<LiveIntervals>();
+    AU.addRequired<SlotIndexes>();
+    AU.addPreserved<SlotIndexes>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+private:
+  struct SubRangeInfo {
+    ConnectedVNInfoEqClasses ConEQ;
+    LiveInterval::SubRange *SR;
+    unsigned Index;
+
+    SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
+                 unsigned Index)
+      : ConEQ(LIS), SR(&SR), Index(Index) {}
+  };
+
+  /// Split unrelated subregister components and rename them to new vregs.
+  bool renameComponents(LiveInterval &LI) const;
+
+  /// \brief Build a vector of SubRange infos and a union find set of
+  /// equivalence classes.
+  /// Returns true if more than 1 equivalence class was found.
+  bool findComponents(IntEqClasses &Classes,
+                      SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
+                      LiveInterval &LI) const;
+
+  /// \brief Distribute the LiveInterval segments into the new LiveIntervals
+  /// belonging to their class.
+  void distribute(const IntEqClasses &Classes,
+                  const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
+                  const SmallVectorImpl<LiveInterval*> &Intervals) const;
+
+  /// \brief Constructs main liverange and add missing undef+dead flags.
+  void computeMainRangesFixFlags(const IntEqClasses &Classes,
+      const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
+      const SmallVectorImpl<LiveInterval*> &Intervals) const;
+
+  /// Rewrite Machine Operands to use the new vreg belonging to their class.
+  void rewriteOperands(const IntEqClasses &Classes,
+                       const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
+                       const SmallVectorImpl<LiveInterval*> &Intervals) const;
+
+
+  LiveIntervals *LIS;
+  MachineRegisterInfo *MRI;
+  const TargetInstrInfo *TII;
+};
+
+} // end anonymous namespace
+
+char RenameIndependentSubregs::ID;
+
+char &llvm::RenameIndependentSubregsID = RenameIndependentSubregs::ID;
+
+INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, "rename-independent-subregs",
+                      "Rename Independent Subregisters", false, false)
+INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
+INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
+INITIALIZE_PASS_END(RenameIndependentSubregs, "rename-independent-subregs",
+                    "Rename Independent Subregisters", false, false)
+
+bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
+  // Shortcut: We cannot have split components with a single definition.
+  if (LI.valnos.size() < 2)
+    return false;
+
+  SmallVector<SubRangeInfo, 4> SubRangeInfos;
+  IntEqClasses Classes;
+  if (!findComponents(Classes, SubRangeInfos, LI))
+    return false;
+
+  // 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);
+  return true;
+}
+
+bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
+    SmallVectorImpl<RenameIndependentSubregs::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 (RenameIndependentSubregs::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 RenameIndependentSubregs::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 RenameIndependentSubregs::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 RenameIndependentSubregs::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);
+  }
+}
+
+bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
+  // Skip renaming if liveness of subregister is not tracked.
+  if (!MF.getSubtarget().enableSubRegLiveness())
+    return false;
+
+  LIS = &getAnalysis<LiveIntervals>();
+  MRI = &MF.getRegInfo();
+  TII = MF.getSubtarget().getInstrInfo();
+
+  // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
+  // created vregs end up with higher numbers but do not need to be visited as
+  // there can't be any further splitting.
+  bool Changed = false;
+  for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
+    unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
+    if (!LIS->hasInterval(Reg))
+      continue;
+    LiveInterval &LI = LIS->getInterval(Reg);
+    if (!LI.hasSubRanges())
+      continue;
+
+    Changed |= renameComponents(LI);
+  }
+
+  return Changed;
+}

lib/CodeGen/TargetPassConfig.cpp

void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
 
   // Eventually, we want to run LiveIntervals before PHI elimination.
   if (EarlyLiveIntervals)
     addPass(&LiveIntervalsID, false);
 
   addPass(&TwoAddressInstructionPassID, false);
   addPass(&RegisterCoalescerID);
 
+  addPass(&RenameIndependentSubregsID);
+
   // PreRA instruction scheduling.
   addPass(&MachineSchedulerID);
 
   if (RegAllocPass) {
     // Add the selected register allocation pass.
     addPass(RegAllocPass);
 
     // Allow targets to change the register assignments before rewriting.

test/CodeGen/AMDGPU/rename-independent-subregs.mir

+# RUN: llc -march=amdgcn -run-pass rename-independent-subregs -o /dev/null %s 2>&1 | FileCheck %s
+--- |
+  define void @test0() { ret void }
+...
+---
+# CHECK-LABEL: name: test0
+# CHECK: S_NOP 0, implicit-def undef %0:sub0
+# CHECK: S_NOP 0, implicit-def undef %2:sub1
+# CHECK: S_NOP 0, implicit %2:sub1
+# CHECK: S_NOP 0, implicit-def undef %1:sub1
+# CHECK: S_NOP 0, implicit %1:sub1
+# CHECK: S_NOP 0, implicit-def %0:sub1
+# CHECK: S_NOP 0, implicit %0
+name: test0
+isSSA: true
+registers:
+  - { id: 0, class: sreg_128 }
+body: |
+  bb.0:
+    S_NOP 0, implicit-def undef %0:sub0
+    S_NOP 0, implicit-def %0:sub1
+    S_NOP 0, implicit %0:sub1
+    S_NOP 0, implicit-def %0:sub1
+    S_NOP 0, implicit %0:sub1
+    S_NOP 0, implicit-def %0:sub1
+    S_NOP 0, implicit %0
+...