From 1a66f0a4f2348473263fab757d96588bc1e93554 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Tue, 28 Aug 2007 08:28:51 +0000 Subject: [PATCH] Recover most of the compile time regression due to recent live interval changes. 1. Eliminate the costly live interval "swapping". 2. Change ValueNumberInfo container from SmallVector to std::vector. The former performs slowly when the vector size is very large. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41536 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveInterval.h | 106 +++++++++--------- .../llvm/CodeGen/SimpleRegisterCoalescing.h | 2 +- lib/CodeGen/LiveInterval.cpp | 46 ++++---- lib/CodeGen/SimpleRegisterCoalescing.cpp | 44 +++++--- 4 files changed, 100 insertions(+), 98 deletions(-) diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 281e3af96c2..844795d30f5 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -99,14 +99,19 @@ namespace llvm { VNInfo() : def(~1U), reg(0) {} VNInfo(unsigned d, unsigned r) : def(d), reg(r) {} }; - private: - SmallVector ValueNumberInfo; - public: + typedef std::vector VNInfoList; + VNInfoList ValueNumberInfo; + + public: LiveInterval(unsigned Reg, float Weight) : reg(Reg), preference(0), weight(Weight) { } + ~LiveInterval() { + ValueNumberInfo.clear(); + } + typedef Ranges::iterator iterator; iterator begin() { return ranges.begin(); } iterator end() { return ranges.end(); } @@ -115,6 +120,13 @@ namespace llvm { const_iterator begin() const { return ranges.begin(); } const_iterator end() const { return ranges.end(); } + typedef VNInfoList::iterator vni_iterator; + vni_iterator vni_begin() { return ValueNumberInfo.begin(); } + vni_iterator vni_end() { return ValueNumberInfo.end(); } + + typedef VNInfoList::const_iterator const_vni_iterator; + const_vni_iterator vni_begin() const { return ValueNumberInfo.begin(); } + const_vni_iterator vni_end() const { return ValueNumberInfo.end(); } /// advanceTo - Advance the specified iterator to point to the LiveRange /// containing the specified position, or end() if the position is past the @@ -128,17 +140,37 @@ namespace llvm { return I; } - void swap(LiveInterval& other) { - std::swap(reg, other.reg); - std::swap(weight, other.weight); - std::swap(ranges, other.ranges); - std::swap(ValueNumberInfo, other.ValueNumberInfo); - } - bool containsOneValue() const { return ValueNumberInfo.size() == 1; } unsigned getNumValNums() const { return ValueNumberInfo.size(); } + /// getValNumInfo - Returns a copy of the specified val#. + /// + inline VNInfo& getValNumInfo(unsigned ValNo) { + return ValueNumberInfo[ValNo]; + } + inline const VNInfo& getValNumInfo(unsigned ValNo) const { + return ValueNumberInfo[ValNo]; + } + + /// copyValNumInfo - Copy the value number info for one value number to + /// another. + void copyValNumInfo(unsigned DstValNo, unsigned SrcValNo) { + VNInfo &vnd = getValNumInfo(DstValNo); + const VNInfo &vns = getValNumInfo(SrcValNo); + vnd.def = vns.def; + vnd.reg = vns.reg; + vnd.kills = vns.kills; + } + void copyValNumInfo(unsigned DstValNo, const LiveInterval &SrcLI, + unsigned SrcValNo) { + VNInfo &vnd = getValNumInfo(DstValNo); + const VNInfo &vns = SrcLI.getValNumInfo(SrcValNo); + vnd.def = vns.def; + vnd.reg = vns.reg; + vnd.kills = vns.kills; + } + /// getNextValue - Create a new value number and return it. MIIdx specifies /// the instruction that defines the value number. unsigned getNextValue(unsigned MIIdx, unsigned SrcReg) { @@ -149,44 +181,38 @@ namespace llvm { /// getDefForValNum - Return the machine instruction index that defines the /// specified value number. unsigned getDefForValNum(unsigned ValNo) const { - assert(ValNo < ValueNumberInfo.size()); - return ValueNumberInfo[ValNo].def; + return getValNumInfo(ValNo).def; } /// getSrcRegForValNum - If the machine instruction that defines the /// specified value number is a copy, returns the source register. Otherwise, /// returns zero. unsigned getSrcRegForValNum(unsigned ValNo) const { - assert(ValNo < ValueNumberInfo.size()); - return ValueNumberInfo[ValNo].reg; + return getValNumInfo(ValNo).reg; } /// setDefForValNum - Set the machine instruction index that defines the /// specified value number. void setDefForValNum(unsigned ValNo, unsigned NewDef) { - assert(ValNo < ValueNumberInfo.size()); - ValueNumberInfo[ValNo].def = NewDef; + getValNumInfo(ValNo).def = NewDef; } /// setSrcRegForValNum - Set the source register of the specified value /// number. void setSrcRegForValNum(unsigned ValNo, unsigned NewReg) { - assert(ValNo < ValueNumberInfo.size()); - ValueNumberInfo[ValNo].reg = NewReg; + getValNumInfo(ValNo).reg = NewReg; } /// getKillsForValNum - Return the kill instruction indexes of the specified /// value number. const SmallVector &getKillsForValNum(unsigned ValNo) const { - assert(ValNo < ValueNumberInfo.size()); - return ValueNumberInfo[ValNo].kills; + return getValNumInfo(ValNo).kills; } /// addKillForValNum - Add a kill instruction index to the specified value /// number. void addKillForValNum(unsigned ValNo, unsigned KillIdx) { - assert(ValNo < ValueNumberInfo.size()); - SmallVector &kills = ValueNumberInfo[ValNo].kills; + SmallVector &kills = getValNumInfo(ValNo).kills; if (kills.empty()) { kills.push_back(KillIdx); } else { @@ -213,14 +239,13 @@ namespace llvm { /// the specified value number. void addKillsForValNum(unsigned ValNo, const SmallVector &kills) { - addKills(ValueNumberInfo[ValNo], kills); + addKills(getValNumInfo(ValNo), kills); } /// isKillForValNum - Returns true if KillIdx is a kill of the specified /// val#. bool isKillForValNum(unsigned ValNo, unsigned KillIdx) const { - assert(ValNo < ValueNumberInfo.size()); - const SmallVector &kills = ValueNumberInfo[ValNo].kills; + const SmallVector &kills = getValNumInfo(ValNo).kills; SmallVector::const_iterator I = std::lower_bound(kills.begin(), kills.end(), KillIdx); if (I == kills.end()) @@ -244,15 +269,13 @@ namespace llvm { /// removeKillForValNum - Remove the specified kill from the list of kills /// of the specified val#. bool removeKillForValNum(unsigned ValNo, unsigned KillIdx) { - assert(ValNo < ValueNumberInfo.size()); - return removeKill(ValueNumberInfo[ValNo], KillIdx); + return removeKill(getValNumInfo(ValNo), KillIdx); } /// removeKillForValNum - Remove all the kills in specified range /// [Start, End] of the specified val#. void removeKillForValNum(unsigned ValNo, unsigned Start, unsigned End) { - assert(ValNo < ValueNumberInfo.size()); - SmallVector &kills = ValueNumberInfo[ValNo].kills; + SmallVector &kills = getValNumInfo(ValNo).kills; SmallVector::iterator I = std::lower_bound(kills.begin(), kills.end(), Start); SmallVector::iterator @@ -278,32 +301,9 @@ namespace llvm { bool replaceKillForValNum(unsigned ValNo, unsigned OldKill, unsigned NewKill) { assert(ValNo < ValueNumberInfo.size()); - return replaceKill(ValueNumberInfo[ValNo], OldKill, NewKill); + return replaceKill(getValNumInfo(ValNo), OldKill, NewKill); } - /// getValNumInfo - Returns a copy of the specified val#. - /// - VNInfo getValNumInfo(unsigned ValNo) const { - assert(ValNo < ValueNumberInfo.size()); - return ValueNumberInfo[ValNo]; - } - - /// setValNumInfo - Change the value number info for the specified - /// value number. - void setValNumInfo(unsigned ValNo, const VNInfo &I) { - ValueNumberInfo[ValNo] = I; - } - - /// copyValNumInfo - Copy the value number info for one value number to - /// another. - void copyValNumInfo(unsigned DstValNo, unsigned SrcValNo) { - ValueNumberInfo[DstValNo] = ValueNumberInfo[SrcValNo]; - } - void copyValNumInfo(unsigned DstValNo, const LiveInterval &SrcLI, - unsigned SrcValNo) { - ValueNumberInfo[DstValNo] = SrcLI.ValueNumberInfo[SrcValNo]; - } - /// MergeValueNumberInto - This method is called when two value nubmers /// are found to be equivalent. This eliminates V1, replacing all /// LiveRanges with the V1 value number with the V2 value number. This can diff --git a/include/llvm/CodeGen/SimpleRegisterCoalescing.h b/include/llvm/CodeGen/SimpleRegisterCoalescing.h index 892ab4873a6..2f363d585ea 100644 --- a/include/llvm/CodeGen/SimpleRegisterCoalescing.h +++ b/include/llvm/CodeGen/SimpleRegisterCoalescing.h @@ -105,7 +105,7 @@ namespace llvm { /// physreg, this method always canonicalizes DestInt to be it. The output /// "SrcInt" will not have been modified, so we can use this information /// below to update aliases. - bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS); + bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped); /// SimpleJoin - Attempt to join the specified interval into this one. The /// caller of this method must guarantee that the RHS only contains a single diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 9697d43bb4d..0be4e9bed41 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -288,25 +288,12 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) { void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, int *RHSValNoAssignments, SmallVector &NewValueNumberInfo) { - - // Try to do the least amount of work possible. In particular, if there are - // more liverange chunks in the other set than there are in the 'this' set, - // swap sets to merge the fewest chunks in possible. - // - // Also, if one range is a physreg and one is a vreg, we always merge from the - // vreg into the physreg, which leaves the vreg intervals pristine. - if ((Other.ranges.size() > ranges.size() && - MRegisterInfo::isVirtualRegister(reg)) || - MRegisterInfo::isPhysicalRegister(Other.reg)) { - swap(Other); - std::swap(LHSValNoAssignments, RHSValNoAssignments); - } // Determine if any of our live range values are mapped. This is uncommon, so // we want to avoid the interval scan if not. bool MustMapCurValNos = false; for (unsigned i = 0, e = getNumValNums(); i != e; ++i) { - if (ValueNumberInfo[i].def == ~1U) continue; // tombstone value # + if (getDefForValNum(i) == ~1U) continue; // tombstone value # if (i != (unsigned)LHSValNoAssignments[i]) { MustMapCurValNos = true; break; @@ -345,7 +332,9 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, // Update val# info first. Increasing live ranges may invalidate some kills. ValueNumberInfo.clear(); - ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end()); + for (SmallVector::iterator I = NewValueNumberInfo.begin(), + E = NewValueNumberInfo.end(); I != E; ++I) + ValueNumberInfo.push_back(*I); // Okay, now insert the RHS live ranges into the LHS. iterator InsertPos = begin(); @@ -472,7 +461,7 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { ValueNumberInfo.pop_back(); } while (ValueNumberInfo.back().def == ~1U); } else { - ValueNumberInfo[V1].def = ~1U; + setDefForValNum(V1, ~1U); } } @@ -511,22 +500,25 @@ void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const { // Print value number info. if (getNumValNums()) { OS << " "; - for (unsigned i = 0; i != getNumValNums(); ++i) { - if (i) OS << " "; - OS << i << "@"; - if (ValueNumberInfo[i].def == ~1U) { + unsigned vnum = 0; + for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; + ++i, ++vnum) { + const VNInfo &vni = *i; + if (vnum) OS << " "; + OS << vnum << "@"; + if (vni.def == ~1U) { OS << "x"; } else { - if (ValueNumberInfo[i].def == ~0U) + if (vni.def == ~0U) OS << "?"; else - OS << ValueNumberInfo[i].def; - unsigned e = ValueNumberInfo[i].kills.size(); - if (e) { + OS << vni.def; + unsigned ee = vni.kills.size(); + if (ee) { OS << "-("; - for (unsigned j = 0; j != e; ++j) { - OS << ValueNumberInfo[i].kills[j]; - if (j != e-1) + for (unsigned j = 0; j != ee; ++j) { + OS << vni.kills[j]; + if (j != ee-1) OS << " "; } OS << ")"; diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 276a5092f62..d8d0ce2ce4b 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -309,7 +309,8 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // Otherwise, if one of the intervals being joined is a physreg, this method // always canonicalizes DstInt to be it. The output "SrcInt" will not have // been modified, so we can use this information below to update aliases. - if (JoinIntervals(DstInt, SrcInt)) { + bool Swapped = false; + if (JoinIntervals(DstInt, SrcInt, Swapped)) { if (isDead) { // Result of the copy is dead. Propagate this property. if (SrcStart == 0) { @@ -330,8 +331,8 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, if (isShorten || isDead) { // Shorten the destination live interval. - if (repSrcReg == DstInt.reg) - DstInt.removeRange(RemoveStart, RemoveEnd); + if (Swapped) + SrcInt.removeRange(RemoveStart, RemoveEnd); } } else { // Coalescing failed. @@ -345,9 +346,12 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, return false; } - bool Swapped = repSrcReg == DstInt.reg; - if (Swapped) + LiveInterval *ResSrcInt = &SrcInt; + LiveInterval *ResDstInt = &DstInt; + if (Swapped) { std::swap(repSrcReg, repDstReg); + std::swap(ResSrcInt, ResDstInt); + } assert(MRegisterInfo::isVirtualRegister(repSrcReg) && "LiveInterval::join didn't work right!"); @@ -356,15 +360,15 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // have clobbered values for this range. if (MRegisterInfo::isPhysicalRegister(repDstReg)) { // Unset unnecessary kills. - if (!DstInt.containsOneValue()) { - for (LiveInterval::Ranges::const_iterator I = SrcInt.begin(), - E = SrcInt.end(); I != E; ++I) + if (!ResDstInt->containsOneValue()) { + for (LiveInterval::Ranges::const_iterator I = ResSrcInt->begin(), + E = ResSrcInt->end(); I != E; ++I) unsetRegisterKills(I->start, I->end, repDstReg); } // Update the liveintervals of sub-registers. for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS) - li_->getInterval(*AS).MergeInClobberRanges(SrcInt); + li_->getInterval(*AS).MergeInClobberRanges(*ResSrcInt); } else { // Merge use info if the destination is a virtual register. LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg); @@ -372,7 +376,7 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, dVI.NumUses += sVI.NumUses; } - DOUT << "\n\t\tJoined. Result = "; DstInt.print(DOUT, mri_); + DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, mri_); DOUT << "\n"; // Remember these liveintervals have been joined. @@ -380,10 +384,6 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, if (MRegisterInfo::isVirtualRegister(repDstReg)) JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister); - // If the intervals were swapped by Join, swap them back so that the register - // mapping (in the r2i map) is correct. - if (Swapped) SrcInt.swap(DstInt); - // repSrcReg is guarateed to be the register whose live interval that is // being merged. li_->removeInterval(repSrcReg); @@ -586,7 +586,8 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) /// physreg, this method always canonicalizes LHS to be it. The output /// "RHS" will not have been modified, so we can use this information /// below to update aliases. -bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { +bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, + LiveInterval &RHS, bool &Swapped) { // Compute the final value assignment, assuming that the live ranges can be // coalesced. SmallVector LHSValNoAssignments; @@ -815,8 +816,17 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH // If we get here, we know that we can coalesce the live ranges. Ask the // intervals to coalesce themselves now. - LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], - ValueNumberInfo); + if ((RHS.ranges.size() > LHS.ranges.size() && + MRegisterInfo::isVirtualRegister(LHS.reg)) || + MRegisterInfo::isPhysicalRegister(RHS.reg)) { + RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], + ValueNumberInfo); + Swapped = true; + } else { + LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], + ValueNumberInfo); + Swapped = false; + } return true; } -- 2.34.1