CodeGen: Refactor renameDisconnectedComponents() as a pass
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 a 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.
Differential Revision: http://reviews.llvm.org/D20507
llvm-svn: 271345
diff --git a/llvm/lib/CodeGen/LiveInterval.cpp b/llvm/lib/CodeGen/LiveInterval.cpp
index 79b6a1a..10e25f1 100644
--- a/llvm/lib/CodeGen/LiveInterval.cpp
+++ b/llvm/lib/CodeGen/LiveInterval.cpp
@@ -20,16 +20,14 @@
#include "llvm/CodeGen/LiveInterval.h"
-#include "PHIEliminationUtils.h"
+#include "LiveRangeUtils.h"
#include "RegisterCoalescer.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include <algorithm>
using namespace llvm;
@@ -1176,40 +1174,6 @@
return EqClass.getNumClasses();
}
-template<typename LiveRangeT, typename EqClassesT>
-static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[],
- EqClassesT VNIClasses) {
- // Move segments to new intervals.
- LiveRange::iterator J = LR.begin(), E = LR.end();
- while (J != E && VNIClasses[J->valno->id] == 0)
- ++J;
- for (LiveRange::iterator I = J; I != E; ++I) {
- if (unsigned eq = VNIClasses[I->valno->id]) {
- assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) &&
- "New intervals should be empty");
- SplitLRs[eq-1]->segments.push_back(*I);
- } else
- *J++ = *I;
- }
- LR.segments.erase(J, E);
-
- // Transfer VNInfos to their new owners and renumber them.
- unsigned j = 0, e = LR.getNumValNums();
- while (j != e && VNIClasses[j] == 0)
- ++j;
- for (unsigned i = j; i != e; ++i) {
- VNInfo *VNI = LR.getValNumInfo(i);
- if (unsigned eq = VNIClasses[i]) {
- VNI->id = SplitLRs[eq-1]->getNumValNums();
- SplitLRs[eq-1]->valnos.push_back(VNI);
- } else {
- VNI->id = j;
- LR.valnos[j++] = VNI;
- }
- }
- LR.valnos.resize(j);
-}
-
void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[],
MachineRegisterInfo &MRI) {
// Rewrite instructions.
@@ -1276,232 +1240,3 @@
// 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);
- }
-}