LiveInterval: Add utility class to rename independent subregister usage

[MatzeB]

Summary

This supersedes http://reviews.llvm.org/D14966

This renaming is necessary to avoid a subregister aware scheduler
accidentally creating liveness "holes" which are rejected by the
MachineVerifier.

Explanation as found in this patch:

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.

[atrick]

splitSeparateSubRegComponents is a bit long. Would you consider encapsulating some of the loops into helpers?

[MatzeB]

• Renamed main function to "renameComponents()"
• Split the implementation into several functions.

[atrick]

Comment struct SubRangeInfo. e.g. Index is its position in the containing vector.

Otherwise... Awesome!

llvm/trunk/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;
+
+  public:
+    ConnectedSubRegClasses(LiveIntervals &LIS, MachineRegisterInfo &MRI)
+      : LIS(LIS), MRI(MRI) {}
+
+    /// 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

llvm/trunk/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();
+
   private:
     /// Compute live intervals for all virtual registers.
     void computeVirtRegs();
 
     /// Compute RegMaskSlots and RegMaskBits.
     void computeRegMasks();
 
     /// Walk the values in @p LI and check for dead values:

llvm/trunk/lib/CodeGen/LiveInterval.cpp

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 (auto &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 (auto &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 (auto &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);
+  }
+}
+
+void ConnectedSubRegClasses::computeMainRangesFixFlags(
+    const IntEqClasses &Classes,
+    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
+    const SmallVectorImpl<LiveInterval*> &Intervals) const {
+  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
+  for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
+    LiveInterval *LI = Intervals[I];
+    LI->removeEmptySubRanges();
+    if (I == 0)
+      LI->clear();
+    LI->constructMainRangeFromSubranges(*LIS.getSlotIndexes(), Allocator);
+
+    for (MachineOperand &MO : MRI.reg_nodbg_operands(LI->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 kill
+      // flags in these cases.
+      if (!MO.isUndef()) {
+        SlotIndex Pos = LIS.getInstructionIndex(MO.getParent());
+        if (!LI->liveAt(Pos.getBaseIndex()))
+          MO.setIsUndef();
+      }
+      if (!MO.isDead()) {
+        SlotIndex Pos = LIS.getInstructionIndex(MO.getParent());
+        if (!LI->liveAt(Pos.getDeadSlot()))
+          MO.setIsDead();
+      }
+    }
+  }
+}

llvm/trunk/lib/CodeGen/LiveIntervalAnalysis.cpp

void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
   const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
   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);
+
+  // 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);
+  }
+}