Index: include/llvm/CodeGen/LiveInterval.h =================================================================== --- include/llvm/CodeGen/LiveInterval.h +++ include/llvm/CodeGen/LiveInterval.h @@ -864,5 +864,39 @@ 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) {} + + void splitSeparateSubRegComponents(LiveInterval &LI) const; + }; } #endif Index: include/llvm/CodeGen/LiveIntervalAnalysis.h =================================================================== --- include/llvm/CodeGen/LiveIntervalAnalysis.h +++ include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -406,6 +406,11 @@ void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl &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(); Index: lib/CodeGen/LiveInterval.cpp =================================================================== --- lib/CodeGen/LiveInterval.cpp +++ lib/CodeGen/LiveInterval.cpp @@ -1466,3 +1466,170 @@ // Distribute main liverange. DistributeRange(LI, LIV, EqClass); } + +void ConnectedSubRegClasses::splitSeparateSubRegComponents(LiveInterval &LI) + const { + // Shortcut: We cannot have split components with a single definition. + if (LI.valnos.size() < 2) + return; + + struct SubRangeInfo { + ConnectedVNInfoEqClasses ConEQ; + LiveInterval::SubRange *SR; + unsigned Index; + + SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR, unsigned Index) + : ConEQ(LIS), SR(&SR), Index(Index) {} + }; + + // First step: Create connected components for the VNInfos inside the + // subranges and count the global number of such components. + SmallVector SubRangeInfos; + 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; + + // 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(); + IntEqClasses Classes(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(); + if (NumClasses == 1) + return; + + // Create a new VReg for each class. + const TargetRegisterClass *RegClass = MRI.getRegClass(Reg); + SmallVector Intervals; + Intervals.push_back(&LI); + for (unsigned I = 1; I < NumClasses; ++I) { + unsigned NewVReg = MRI.createVirtualRegister(RegClass); + LiveInterval &NewLI = LIS.createEmptyInterval(NewVReg); + Intervals.push_back(&NewLI); + } + + // Rewrite Machine Operands to the new vreg belonging to their class. + 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); + } + + // Distribute the segments in the subregister liveranges. + SmallVector VNIMapping; + SmallVector 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); + } + + // Construct new main liveranges based on the subranges and add missing + // Undef and Dead flags. + 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(); + } + } + } +} Index: lib/CodeGen/LiveIntervalAnalysis.cpp =================================================================== --- lib/CodeGen/LiveIntervalAnalysis.cpp +++ lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1459,3 +1459,19 @@ } 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.splitSeparateSubRegComponents(*LI); + } +}