From 6d8fbef015ff836bcb8f64f52c49805e43f8ea9f Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 29 Aug 2006 23:18:15 +0000 Subject: Teach the coallescer to coallesce live intervals joined by an arbitrary number of copies, potentially defining live ranges that appear to have differing value numbers that become identical when coallsced. Among other things, this fixes CodeGen/X86/shift-coalesce.ll and PR687. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29968 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveInterval.cpp | 189 ++++++++++++++----------------------------- 1 file changed, 59 insertions(+), 130 deletions(-) (limited to 'lib/CodeGen/LiveInterval.cpp') diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 7f16b31823..8be9677929 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -101,101 +101,6 @@ bool LiveInterval::overlapsFrom(const LiveInterval& other, return false; } -/// NontrivialOverlap - Check to see if the two live ranges specified by i and j -/// overlap. If so, check to see if they have value numbers that are not -/// iIdx/jIdx respectively. If both conditions are true, return true. -static inline bool NontrivialOverlap(const LiveRange &I, const LiveRange &J, - unsigned iIdx, unsigned jIdx) { - if (I.start == J.start) { - // If this is not the allowed value merge, we cannot join. - if (I.ValId != iIdx || J.ValId != jIdx) - return true; - } else if (I.start < J.start) { - if (I.end > J.start && (I.ValId != iIdx || J.ValId != jIdx)) { - return true; - } - } else { - if (J.end > I.start && (I.ValId != iIdx || J.ValId != jIdx)) - return true; - } - - return false; -} - -/// joinable - Two intervals are joinable if the either don't overlap at all -/// or if the destination of the copy is a single assignment value, and it -/// only overlaps with one value in the source interval. -bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const { - const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1); - const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); - assert(SourceLR && DestLR && "Not joining due to a copy?"); - unsigned OtherValIdx = SourceLR->ValId; - unsigned ThisValIdx = DestLR->ValId; - - Ranges::const_iterator i = ranges.begin(); - Ranges::const_iterator ie = ranges.end(); - Ranges::const_iterator j = other.ranges.begin(); - Ranges::const_iterator je = other.ranges.end(); - - if (i->start < j->start) { - i = std::upper_bound(i, ie, j->start); - if (i != ranges.begin()) --i; - } else if (j->start < i->start) { - j = std::upper_bound(j, je, i->start); - if (j != other.ranges.begin()) --j; - } - - while (i != ie && j != je) { - if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx)) - return false; - - if (i->end < j->end) - ++i; - else - ++j; - } - - return true; -} - -/// getOverlapingRanges - Given another live interval which is defined as a -/// copy from this one, return a list of all of the live ranges where the -/// two overlap and have different value numbers. -void LiveInterval::getOverlapingRanges(const LiveInterval &other, - unsigned CopyIdx, - std::vector &Ranges) { - const LiveRange *SourceLR = getLiveRangeContaining(CopyIdx-1); - const LiveRange *DestLR = other.getLiveRangeContaining(CopyIdx); - assert(SourceLR && DestLR && "Not joining due to a copy?"); - unsigned OtherValIdx = SourceLR->ValId; - unsigned ThisValIdx = DestLR->ValId; - - Ranges::iterator i = ranges.begin(); - Ranges::iterator ie = ranges.end(); - Ranges::const_iterator j = other.ranges.begin(); - Ranges::const_iterator je = other.ranges.end(); - - if (i->start < j->start) { - i = std::upper_bound(i, ie, j->start); - if (i != ranges.begin()) --i; - } else if (j->start < i->start) { - j = std::upper_bound(j, je, i->start); - if (j != other.ranges.begin()) --j; - } - - while (i != ie && j != je) { - if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx)) - Ranges.push_back(&*i); - - if (i->end < j->end) - ++i; - else - ++j; - } -} - - - /// extendIntervalEndTo - This method is used when we want to extend the range /// specified by I to end at the specified endpoint. To do this, we should /// merge and eliminate all ranges that this will overlap with. The iterator is @@ -361,7 +266,7 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) const { LiveInterval::iterator LiveInterval::FindLiveRangeContaining(unsigned Idx) { iterator It = std::upper_bound(begin(), end(), Idx); - if (It != ranges.begin()) { + if (It != begin()) { --It; if (It->contains(Idx)) return It; @@ -370,10 +275,13 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) { return end(); } -/// join - Join two live intervals (this, and other) together. This operation -/// is the result of a copy instruction in the source program, that occurs at -/// index 'CopyIdx' that copies from 'Other' to 'this'. -void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) { +/// join - Join two live intervals (this, and other) together. This applies +/// mappings to the value numbers in the LHS/RHS intervals as specified. If +/// the intervals are not joinable, this aborts. +void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, + int *RHSValNoAssignments, + SmallVector &NewInstDefiningValue) { + // 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. @@ -385,39 +293,61 @@ void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) { MRegisterInfo::isVirtualRegister(reg)) || MRegisterInfo::isPhysicalRegister(Other.reg)) { swap(Other); - std::swap(ThisOffs, OtherOffs); + 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 (InstDefiningValue[i] == ~2U) continue; // tombstone value # + if (i != (unsigned)LHSValNoAssignments[i]) { + MustMapCurValNos = true; + break; + } + } + + // If we have to apply a mapping to our base interval assignment, rewrite it + // now. + if (MustMapCurValNos) { + // Map the first live range. + iterator OutIt = begin(); + OutIt->ValId = LHSValNoAssignments[OutIt->ValId]; + ++OutIt; + for (iterator I = OutIt, E = end(); I != E; ++I) { + OutIt->ValId = LHSValNoAssignments[I->ValId]; + + // If this live range has the same value # as its immediate predecessor, + // and if they are neighbors, remove one LiveRange. This happens when we + // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. + if (OutIt->ValId == (OutIt-1)->ValId && (OutIt-1)->end == OutIt->start) { + (OutIt-1)->end = OutIt->end; + } else { + if (I != OutIt) { + OutIt->start = I->start; + OutIt->end = I->end; + } + + // Didn't merge, on to the next one. + ++OutIt; + } + } + + // If we merge some live ranges, chop off the end. + ranges.erase(OutIt, end()); } - const LiveRange *SourceLR = Other.getLiveRangeContaining(CopyIdx-OtherOffs); - const LiveRange *DestLR = getLiveRangeContaining(CopyIdx-ThisOffs); - assert(SourceLR && DestLR && "Not joining due to a copy?"); - unsigned MergedSrcValIdx = SourceLR->ValId; - unsigned MergedDstValIdx = DestLR->ValId; - - // Join the ranges of other into the ranges of this interval. - std::map Dst2SrcIdxMap; + // Okay, now insert the RHS live ranges into the LHS. iterator InsertPos = begin(); for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) { // Map the ValId in the other live range to the current live range. - if (I->ValId == MergedSrcValIdx) - I->ValId = MergedDstValIdx; - else { - unsigned &NV = Dst2SrcIdxMap[I->ValId]; - if (NV == 0) NV = getNextValue(Other.getInstForValNum(I->ValId)); - I->ValId = NV; - } - + I->ValId = RHSValNoAssignments[I->ValId]; InsertPos = addRangeFrom(*I, InsertPos); } - - // Update the value number information for the value number defined by the - // copy. The copy is about to be removed, so ensure that the value is defined - // by whatever the other value is defined by. - if (InstDefiningValue[MergedDstValIdx] == CopyIdx) { - InstDefiningValue[MergedDstValIdx] = - Other.InstDefiningValue[MergedSrcValIdx]; - } - + + InstDefiningValue.clear(); + InstDefiningValue.append(NewInstDefiningValue.begin(), + NewInstDefiningValue.end()); weight += Other.weight; } @@ -511,10 +441,9 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { // Now that V1 is dead, remove it. If it is the largest value number, just // nuke it (and any other deleted values neighboring it), otherwise mark it as // ~1U so it can be nuked later. - if (V1 == NumValues-1) { + if (V1 == getNumValNums()-1) { do { InstDefiningValue.pop_back(); - --NumValues; } while (InstDefiningValue.back() == ~1U); } else { InstDefiningValue[V1] = ~1U; @@ -548,9 +477,9 @@ void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const { } // Print value number info. - if (NumValues) { + if (getNumValNums()) { OS << " "; - for (unsigned i = 0; i != NumValues; ++i) { + for (unsigned i = 0; i != getNumValNums(); ++i) { if (i) OS << " "; OS << i << "@"; if (InstDefiningValue[i] == ~0U) { -- cgit v1.2.3-18-g5258