diff options
Diffstat (limited to 'lib/CodeGen')
| -rw-r--r-- | lib/CodeGen/LiveInterval.cpp | 189 | ||||
| -rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 215 |
2 files changed, 249 insertions, 155 deletions
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<LiveRange*> &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<unsigned, 16> &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<unsigned, unsigned> 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) { diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 4f34881cf0..a26feb3023 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -629,8 +629,9 @@ void LiveIntervals::computeIntervals() { /// This returns true if an interval was modified. /// bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, - MachineInstr *CopyMI, - unsigned CopyIdx) { + MachineInstr *CopyMI) { + unsigned CopyIdx = getDefIndex(getInstructionIndex(CopyMI)); + // BValNo is a value number in B that is defined by a copy from A. 'B3' in // the example above. LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); @@ -768,34 +769,22 @@ bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, std::cerr << " and "; DestInt.print(std::cerr, mri_); std::cerr << ": "); - // If two intervals contain a single value and are joined by a copy, it - // does not matter if the intervals overlap, they can always be joined. + // Okay, attempt to join these two intervals. On failure, this returns false. + // Otherwise, if one of the intervals being joined is a 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. + if (!JoinIntervals(DestInt, SrcInt)) { + // Coallescing failed. + + // If we can eliminate the copy without merging the live ranges, do so now. + if (AdjustCopiesBackFrom(SrcInt, DestInt, CopyMI)) + return true; - bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue(); - - unsigned MIDefIdx = getDefIndex(getInstructionIndex(CopyMI)); - - // If the intervals think that this is joinable, do so now. - if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx)) - Joinable = true; - - // If DestInt is actually a copy from SrcInt (which we know) that is used - // to define another value of SrcInt, we can change the other range of - // SrcInt to be the value of the range that defines DestInt, simplying the - // interval an promoting coallescing. - if (!Joinable && AdjustCopiesBackFrom(SrcInt, DestInt, CopyMI, MIDefIdx)) - return true; - - if (!Joinable) { + // Otherwise, we are unable to join the intervals. DEBUG(std::cerr << "Interference!\n"); return false; } - // Okay, we can join these two intervals. If one of the intervals being - // joined is a physreg, this method always canonicalizes DestInt to be it. - // The output "SrcInt" will not have been modified. - DestInt.join(SrcInt, MIDefIdx); - bool Swapped = SrcReg == DestInt.reg; if (Swapped) std::swap(SrcReg, DstReg); @@ -823,6 +812,182 @@ bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, return true; } +/// ComputeUltimateVN - Assuming we are going to join two live intervals, +/// compute what the resultant value numbers for each value in the input two +/// ranges will be. This is complicated by copies between the two which can +/// and will commonly cause multiple value numbers to be merged into one. +/// +/// VN is the value number that we're trying to resolve. InstDefiningValue +/// keeps track of the new InstDefiningValue assignment for the result +/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of +/// whether a value in this or other is a copy from the opposite set. +/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have +/// already been assigned. +/// +/// ThisFromOther[x] - If x is defined as a copy from the other interval, this +/// contains the value number the copy is from. +/// +static unsigned ComputeUltimateVN(unsigned VN, + SmallVector<unsigned, 16> &InstDefiningValue, + SmallVector<int, 16> &ThisFromOther, + SmallVector<int, 16> &OtherFromThis, + SmallVector<int, 16> &ThisValNoAssignments, + SmallVector<int, 16> &OtherValNoAssignments, + LiveInterval &ThisLI, LiveInterval &OtherLI) { + // If the VN has already been computed, just return it. + if (ThisValNoAssignments[VN] >= 0) + return ThisValNoAssignments[VN]; + assert(ThisValNoAssignments[VN] != -2 && "FIXME: Cyclic case, handle it!"); + + // If this val is not a copy from the other val, then it must be a new value + // number in the destination. + int OtherValNo = ThisFromOther[VN]; + if (OtherValNo == -1) { + InstDefiningValue.push_back(ThisLI.getInstForValNum(VN)); + return ThisValNoAssignments[VN] = InstDefiningValue.size()-1; + } + + // Otherwise, this *is* a copy from the RHS. Mark this value number as + // currently being computed, then ask what the ultimate value # of the other + // value is. + ThisValNoAssignments[VN] = -2; + unsigned UltimateVN = + ComputeUltimateVN(OtherValNo, InstDefiningValue, + OtherFromThis, ThisFromOther, + OtherValNoAssignments, ThisValNoAssignments, + OtherLI, ThisLI); + return ThisValNoAssignments[VN] = UltimateVN; +} + + +/// JoinIntervals - Attempt to join these two intervals. On failure, this +/// returns false. Otherwise, if one of the intervals being joined is a +/// 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 LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { + // Loop over the value numbers of the LHS, seeing if any are defined from the + // RHS. + SmallVector<int, 16> LHSValsDefinedFromRHS; + LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1); + for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { + unsigned ValInst = LHS.getInstForValNum(VN); + if (ValInst == ~0U || ValInst == ~1U) + continue; + + // If the instruction defining the LHS's value is a copy. + MachineInstr *ValInstMI = getInstructionFromIndex(ValInst); + + // If the value number is not defined by a copy instruction, ignore it. + unsigned SrcReg, DstReg; + if (!tii_->isMoveInstr(*ValInstMI, SrcReg, DstReg)) + continue; + + // DstReg is known to be a register in the LHS interval. If the src is from + // the RHS interval, we can use its value #. + if (rep(SrcReg) != RHS.reg) + continue; + + // Figure out the value # from the RHS. + LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId; + } + + // Loop over the value numbers of the RHS, seeing if any are defined from the + // LHS. + SmallVector<int, 16> RHSValsDefinedFromLHS; + RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1); + for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { + unsigned ValInst = RHS.getInstForValNum(VN); + if (ValInst == ~0U || ValInst == ~1U) + continue; + + // If the instruction defining the RHS's value is a copy. + MachineInstr *ValInstMI = getInstructionFromIndex(ValInst); + + // If the value number is not defined by a copy instruction, ignore it. + unsigned SrcReg, DstReg; + if (!tii_->isMoveInstr(*ValInstMI, SrcReg, DstReg)) + continue; + + // DstReg is known to be a register in the RHS interval. If the src is from + // the LHS interval, we can use its value #. + if (rep(SrcReg) != LHS.reg) + continue; + + // Figure out the value # from the LHS. + RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId; + } + + // Now that we know the value mapping, compute the final value assignment, + // assuming that the live ranges can be coallesced. + SmallVector<int, 16> LHSValNoAssignments; + SmallVector<int, 16> RHSValNoAssignments; + SmallVector<unsigned, 16> InstDefiningValue; + LHSValNoAssignments.resize(LHS.getNumValNums(), -1); + RHSValNoAssignments.resize(RHS.getNumValNums(), -1); + + // Compute ultimate value numbers for the LHS and RHS values. + for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { + if (LHS.getInstForValNum(VN) == ~2U) continue; + ComputeUltimateVN(VN, InstDefiningValue, + LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, + LHSValNoAssignments, RHSValNoAssignments, LHS, RHS); + } + for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { + if (RHS.getInstForValNum(VN) == ~2U) continue; + ComputeUltimateVN(VN, InstDefiningValue, + RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, + RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); + } + + // Armed with the mappings of LHS/RHS values to ultimate values, walk the + // interval lists to see if these intervals are coallescable. + LiveInterval::const_iterator I = LHS.begin(); + LiveInterval::const_iterator IE = LHS.end(); + LiveInterval::const_iterator J = RHS.begin(); + LiveInterval::const_iterator JE = RHS.end(); + + // Skip ahead until the first place of potential sharing. + if (I->start < J->start) { + I = std::upper_bound(I, IE, J->start); + if (I != LHS.begin()) --I; + } else if (J->start < I->start) { + J = std::upper_bound(J, JE, I->start); + if (J != RHS.begin()) --J; + } + + while (1) { + // Determine if these two live ranges overlap. + bool Overlaps; + if (I->start < J->start) { + Overlaps = I->end > J->start; + } else { + Overlaps = J->end > I->start; + } + + // If so, check value # info to determine if they are really different. + if (Overlaps) { + // If the live range overlap will map to the same value number in the + // result liverange, we can still coallesce them. If not, we can't. + if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId]) + return false; + } + + if (I->end < J->end) { + ++I; + if (I == IE) break; + } else { + ++J; + if (J == JE) break; + } + } + + // If we get here, we know that we can coallesce the live ranges. Ask the + // intervals to coallesce themselves now. + LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], + InstDefiningValue); + return true; +} namespace { |