From 0253df9a897ce541d56146699cedd79c464bda5e Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Thu, 7 Oct 2010 23:34:34 +0000 Subject: [PATCH] After splitting, the remaining LiveInterval may be fragmented into multiple connected components. These components should be allocated different virtual registers because there is no reason for them to be allocated together. Add the ConnectedVNInfoEqClasses class to calculate the connected components, and move values to new LiveIntervals. Use it from SplitKit::rewrite by creating new virtual registers for the components. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116006 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveInterval.h | 41 ++++++++++- lib/CodeGen/LiveInterval.cpp | 110 ++++++++++++++++++++++++++++ lib/CodeGen/SplitKit.cpp | 35 ++++++--- 3 files changed, 174 insertions(+), 12 deletions(-) diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 720fb830e47..57f0b624244 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -544,6 +544,45 @@ namespace llvm { LI.print(OS); return OS; } -} + /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a + /// LiveInterval into equivalence clases of connected components. A + /// LiveInterval that has multiple connected components can be broken into + /// multiple LiveIntervals. + /// + /// Given a LiveInterval that may have multiple connected components, run: + /// + /// unsigned numComps = ConEQ.Classify(LI); + /// if (numComps > 1) { + /// // allocate numComps-1 new LiveIntervals into LIS[1..] + /// ConEQ.Distribute(LIS); + /// } + + class ConnectedVNInfoEqClasses { + LiveIntervals &lis_; + + // Map each value number to its equivalence class. + // The invariant is that EqClass[x] <= x. + // Two values are connected iff EqClass[x] == EqClass[b]. + SmallVector eqClass_; + + // Note that values a and b are connected. + void Connect(unsigned a, unsigned b); + + unsigned Renumber(); + + public: + explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : lis_(lis) {} + + /// Classify - Classify the values in LI into connected components. + /// Return the number of connected components. + unsigned Classify(const LiveInterval *LI); + + // Distribute values in LIV[0] into a separate LiveInterval for each connected + // component. LIV must have a LiveInterval for each connected component. + // The LiveIntervals in Liv[1..] must be empty. + void Distribute(LiveInterval *LIV[]); + }; + +} #endif diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index fad11fa0806..2ed4d124972 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -702,3 +702,113 @@ void LiveInterval::dump() const { void LiveRange::print(raw_ostream &os) const { os << *this; } + +/// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a +/// LiveInterval into equivalence clases of connected components. A +/// LiveInterval that has multiple connected components can be broken into +/// multiple LiveIntervals. + +void ConnectedVNInfoEqClasses::Connect(unsigned a, unsigned b) { + // Add new eq classes as needed. + for (unsigned i = eqClass_.size(), m = std::max(a, b); i <= m; ++i) + eqClass_.push_back(i); + + unsigned eqa = eqClass_[a]; + unsigned eqb = eqClass_[b]; + if (eqa == eqb) + return; + if (eqa > eqb) + std::swap(eqa, eqb); + // Now, eqa < eqb. Switch all eqb members over to eqa. + for (unsigned i = eqb, e = eqClass_.size(); i != e; ++i) + if (eqClass_[i] == eqb) + eqClass_[i] = eqa; +} + +unsigned ConnectedVNInfoEqClasses::Renumber() { + // No values at all. + if (eqClass_.empty()) + return 0; + + // Common case: A single connected component. + if (eqClass_.back() == 0) + return 1; + + // Renumber classes. We use the fact that eqClass_[i] == i for class leaders. + unsigned count = 0; + for (unsigned i = 0, e = eqClass_.size(); i != e; ++i) { + unsigned q = eqClass_[i]; + if (q == i) + eqClass_[i] = count++; + else + eqClass_[i] = eqClass_[q]; + } + + return count; +} + +unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { + // Determine connections. + eqClass_.clear(); + for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); + I != E; ++I) { + const VNInfo *VNI = *I; + if (VNI->id == eqClass_.size()) + eqClass_.push_back(VNI->id); + assert(!VNI->isUnused() && "Cannot handle unused values"); + if (VNI->isPHIDef()) { + const MachineBasicBlock *MBB = lis_.getMBBFromIndex(VNI->def); + assert(MBB && "Phi-def has no defining MBB"); + // Connect to values live out of predecessors. + for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), + PE = MBB->pred_end(); PI != PE; ++PI) + if (const VNInfo *PVNI = + LI->getVNInfoAt(lis_.getMBBEndIdx(*PI).getPrevSlot())) + Connect(VNI->id, PVNI->id); + } else { + // Normal value defined by an instruction. Check for two-addr redef. + // FIXME: This could be coincidental. Should we really check for a tied + // operand constraint? + if (const VNInfo *UVNI = LI->getVNInfoAt(VNI->def.getUseIndex())) + Connect(VNI->id, UVNI->id); + } + } + return Renumber(); +} + +void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[]) { + assert(LIV[0] && "LIV[0] must be set"); + LiveInterval &LI = *LIV[0]; + // Check that they likely ran Classify() on LIV[0] first. + assert(eqClass_.size() == LI.getNumValNums() && "Bad classification data"); + + // First move runs to new intervals. + LiveInterval::iterator J = LI.begin(), E = LI.end(); + while (J != E && eqClass_[J->valno->id] == 0) + ++J; + for (LiveInterval::iterator I = J; I != E; ++I) { + if (unsigned eq = eqClass_[I->valno->id]) { + assert(LIV[eq]->empty() || LIV[eq]->expiredAt(I->start) && + "New intervals should be empty"); + LIV[eq]->ranges.push_back(*I); + } else + *J++ = *I; + } + LI.ranges.erase(J, E); + + // Transfer VNInfos to their new owners and renumber them. + unsigned j = 0, e = LI.getNumValNums(); + while (j != e && eqClass_[j] == 0) + ++j; + for (unsigned i = j; i != e; ++i) { + VNInfo *VNI = LI.getValNumInfo(i); + if (unsigned eq = eqClass_[i]) { + VNI->id = LIV[eq]->getNumValNums(); + LIV[eq]->valnos.push_back(VNI); + } else { + VNI->id = j; + LI.valnos[j++] = VNI; + } + } + LI.valnos.resize(j); +} diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index 7f98bc13a36..19733e4e68d 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -828,7 +828,29 @@ void SplitEditor::rewrite() { } } + // Get rid of unused values and set phi-kill flags. + dupli_.getLI()->RenumberValues(lis_); + + // Now check if dupli was separated into multiple connected components. + ConnectedVNInfoEqClasses ConEQ(lis_); + if (unsigned NumComp = ConEQ.Classify(dupli_.getLI())) { + DEBUG(dbgs() << " Remainder has " << NumComp << " connected components: " + << *dupli_.getLI() << '\n'); + unsigned firstComp = intervals_.size(); + intervals_.push_back(dupli_.getLI()); + // Did the remainder break up? Create intervals for all the components. + if (NumComp > 1) { + for (unsigned i = 1; i != NumComp; ++i) + intervals_.push_back(createInterval()); + ConEQ.Distribute(&intervals_[firstComp]); + } + } else { + DEBUG(dbgs() << " dupli became empty?\n"); + lis_.removeInterval(dupli_.getLI()->reg); + dupli_.reset(0); + } + // Rewrite instructions. const LiveInterval *curli = sa_.getCurLI(); for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(curli->reg), RE = mri_.reg_end(); RI != RE;) { @@ -843,7 +865,7 @@ void SplitEditor::rewrite() { } SlotIndex Idx = lis_.getInstructionIndex(MI); Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); - LiveInterval *LI = dupli_.getLI(); + LiveInterval *LI = 0; for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) { LiveInterval *testli = intervals_[i]; if (testli->liveAt(Idx)) { @@ -851,21 +873,12 @@ void SplitEditor::rewrite() { break; } } + assert(LI && "No register was live at use"); MO.setReg(LI->reg); DEBUG(dbgs() << " rewrite BB#" << MI->getParent()->getNumber() << '\t' << Idx << '\t' << *MI); } - // dupli_ goes in last, after rewriting. - if (dupli_.getLI()->empty()) { - DEBUG(dbgs() << " dupli became empty?\n"); - lis_.removeInterval(dupli_.getLI()->reg); - dupli_.reset(0); - } else { - dupli_.getLI()->RenumberValues(lis_); - intervals_.push_back(dupli_.getLI()); - } - // Calculate spill weight and allocation hints for new intervals. VirtRegAuxInfo vrai(vrm_.getMachineFunction(), lis_, sa_.loops_); for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) { -- 2.34.1