third_party/llvm-10.0/llvm/lib/CodeGen/RenameIndependentSubregs.cpp - SwiftShader - Git at Google

 //===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// Rename independent subregisters looks for virtual registers with
 /// independently used subregisters and renames them to new virtual registers.
 /// Example: In the following:
 ///   %0:sub0<read-undef> = ...
 ///   %0:sub1 = ...
 ///   use %0:sub0
 ///   %0:sub0 = ...
 ///   use %0:sub0
 ///   use %0:sub1
 /// sub0 and sub1 are never used together, and we have two independent sub0
 /// definitions. This pass will rename to:
 ///   %0:sub0<read-undef> = ...
 ///   %1:sub1<read-undef> = ...
 ///   use %1:sub1
 ///   %2:sub1<read-undef> = ...
 ///   use %2:sub1
 ///   use %0:sub0
 //
 //===----------------------------------------------------------------------===//

 #include "LiveRangeUtils.h"
 #include "PHIEliminationUtils.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/InitializePasses.h"

 using namespace llvm;

 #define DEBUG_TYPE "rename-independent-subregs"

 namespace {

 class RenameIndependentSubregs : public MachineFunctionPass {
 public:
   static char ID;
   RenameIndependentSubregs() : MachineFunctionPass(ID) {}

   StringRef 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;

   /// 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;

   /// 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;

   /// 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, DEBUG_TYPE,
                       "Rename Independent Subregisters", false, false)
 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 INITIALIZE_PASS_END(RenameIndependentSubregs, DEBUG_TYPE,
                     "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);
   LLVM_DEBUG(dbgs() << printReg(Reg) << ": Found " << Classes.getNumClasses()
                     << " equivalence classes.\n");
   LLVM_DEBUG(dbgs() << printReg(Reg) << ": Splitting into newly created:");
   for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
        ++I) {
     Register NewVReg = MRI->createVirtualRegister(RegClass);
     LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
     Intervals.push_back(&NewLI);
     LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));
   }
   LLVM_DEBUG(dbgs() << '\n');

   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).none())
         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;

     auto *MI = MO.getParent();
     SlotIndex Pos = LIS->getInstructionIndex(*MI);
     Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
                      : Pos.getBaseIndex();
     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).none())
         continue;
       const VNInfo *VNI = SR.getVNInfoAt(Pos);
       if (VNI == nullptr)
         continue;

       // 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);

     if (MO.isTied() && Reg != VReg) {
       /// Undef use operands are not tracked in the equivalence class,
       /// but need to be updated if they are tied; take care to only
       /// update the tied operand.
       unsigned OperandNo = MI->getOperandNo(&MO);
       unsigned TiedIdx = MI->findTiedOperandIdx(OperandNo);
       MI->getOperand(TiedIdx).setReg(VReg);

       // above substitution breaks the iterator, so restart.
       I = MRI->reg_nodbg_begin(Reg);
     }
   }
   // TODO: We could attempt to recompute new register classes while visiting
   // the operands: Some of the split register may be fine with less constraint
   // classes than the original 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);
     // A def of a subregister may be a use of other register lanes. Replacing
     // such a def with a def of a different register will eliminate the use,
     // and may cause the recorded live range to be larger than the actual
     // liveness in the program IR.
     LIS->shrinkToUses(&LI);
   }
 }

 bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
   // Skip renaming if liveness of subregister is not tracked.
   MRI = &MF.getRegInfo();
   if (!MRI->subRegLivenessEnabled())
     return false;

   LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
                     << MF.getName() << '\n');

   LIS = &getAnalysis<LiveIntervals>();
   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 = Register::index2VirtReg(I);
     if (!LIS->hasInterval(Reg))
       continue;
     LiveInterval &LI = LIS->getInterval(Reg);
     if (!LI.hasSubRanges())
       continue;

     Changed |= renameComponents(LI);
   }

   return Changed;
 }
	//===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	/// Rename independent subregisters looks for virtual registers with
	/// independently used subregisters and renames them to new virtual registers.
	/// Example: In the following:
	/// %0:sub0<read-undef> = ...
	/// %0:sub1 = ...
	/// use %0:sub0
	/// %0:sub0 = ...
	/// use %0:sub0
	/// use %0:sub1
	/// sub0 and sub1 are never used together, and we have two independent sub0
	/// definitions. This pass will rename to:
	/// %0:sub0<read-undef> = ...
	/// %1:sub1<read-undef> = ...
	/// use %1:sub1
	/// %2:sub1<read-undef> = ...
	/// use %2:sub1
	/// use %0:sub0
	//
	//===----------------------------------------------------------------------===//

	#include "LiveRangeUtils.h"
	#include "PHIEliminationUtils.h"
	#include "llvm/CodeGen/LiveInterval.h"
	#include "llvm/CodeGen/LiveIntervals.h"
	#include "llvm/CodeGen/MachineFunctionPass.h"
	#include "llvm/CodeGen/MachineInstrBuilder.h"
	#include "llvm/CodeGen/MachineRegisterInfo.h"
	#include "llvm/CodeGen/Passes.h"
	#include "llvm/CodeGen/TargetInstrInfo.h"
	#include "llvm/InitializePasses.h"

	using namespace llvm;

	#define DEBUG_TYPE "rename-independent-subregs"

	namespace {

	class RenameIndependentSubregs : public MachineFunctionPass {
	public:
	static char ID;
	RenameIndependentSubregs() : MachineFunctionPass(ID) {}

	StringRef 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;

	/// 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;

	/// 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;

	/// 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, DEBUG_TYPE,
	"Rename Independent Subregisters", false, false)
	INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
	INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
	INITIALIZE_PASS_END(RenameIndependentSubregs, DEBUG_TYPE,
	"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);
	LLVM_DEBUG(dbgs() << printReg(Reg) << ": Found " << Classes.getNumClasses()
	<< " equivalence classes.\n");
	LLVM_DEBUG(dbgs() << printReg(Reg) << ": Splitting into newly created:");
	for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
	++I) {
	Register NewVReg = MRI->createVirtualRegister(RegClass);
	LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
	Intervals.push_back(&NewLI);
	LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));
	}
	LLVM_DEBUG(dbgs() << '\n');

	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).none())
	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;

	auto *MI = MO.getParent();
	SlotIndex Pos = LIS->getInstructionIndex(*MI);
	Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
	: Pos.getBaseIndex();
	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).none())
	continue;
	const VNInfo *VNI = SR.getVNInfoAt(Pos);
	if (VNI == nullptr)
	continue;

	// 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);

	if (MO.isTied() && Reg != VReg) {
	/// Undef use operands are not tracked in the equivalence class,
	/// but need to be updated if they are tied; take care to only
	/// update the tied operand.
	unsigned OperandNo = MI->getOperandNo(&MO);
	unsigned TiedIdx = MI->findTiedOperandIdx(OperandNo);
	MI->getOperand(TiedIdx).setReg(VReg);

	// above substitution breaks the iterator, so restart.
	I = MRI->reg_nodbg_begin(Reg);
	}
	}
	// TODO: We could attempt to recompute new register classes while visiting
	// the operands: Some of the split register may be fine with less constraint
	// classes than the original 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);
	// A def of a subregister may be a use of other register lanes. Replacing
	// such a def with a def of a different register will eliminate the use,
	// and may cause the recorded live range to be larger than the actual
	// liveness in the program IR.
	LIS->shrinkToUses(&LI);
	}
	}

	bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
	// Skip renaming if liveness of subregister is not tracked.
	MRI = &MF.getRegInfo();
	if (!MRI->subRegLivenessEnabled())
	return false;

	LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
	<< MF.getName() << '\n');

	LIS = &getAnalysis<LiveIntervals>();
	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 = Register::index2VirtReg(I);
	if (!LIS->hasInterval(Reg))
	continue;
	LiveInterval &LI = LIS->getInterval(Reg);
	if (!LI.hasSubRanges())
	continue;

	Changed \|= renameComponents(LI);
	}

	return Changed;
	}