diff options
| -rw-r--r-- | include/llvm/CodeGen/LiveInterval.h | 201 | ||||
| -rw-r--r-- | include/llvm/CodeGen/LiveIntervalAnalysis.h | 2 | ||||
| -rw-r--r-- | lib/CodeGen/LiveInterval.cpp | 130 | ||||
| -rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 107 | ||||
| -rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.cpp | 228 |
5 files changed, 316 insertions, 352 deletions
diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 844795d..f73cac1 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -30,6 +30,26 @@ namespace llvm { class MachineInstr; class MRegisterInfo; + struct LiveInterval; + + /// VNInfo - If the value number definition is undefined (e.g. phi + /// merge point), it contains ~0u,x. If the value number is not in use, it + /// contains ~1u,x to indicate that the value # is not used. + /// parent- LiveInterval parent. + /// def - Instruction # of the definition. + /// reg - Source reg iff val# is defined by a copy; zero otherwise. + /// kills - Instruction # of the kills. If a kill is an odd #, it means + /// the kill is a phi join point. + struct VNInfo { + LiveInterval *parent; + unsigned id; + unsigned def; + unsigned reg; + SmallVector<unsigned, 4> kills; + VNInfo() : parent(0), id(~1U), def(~1U), reg(0) {} + VNInfo(LiveInterval *p, unsigned i, unsigned d, unsigned r) + : parent(p), id(i), def(d), reg(r) {} + }; /// LiveRange structure - This represents a simple register range in the /// program, with an inclusive start point and an exclusive end point. @@ -37,9 +57,9 @@ namespace llvm { struct LiveRange { unsigned start; // Start point of the interval (inclusive) unsigned end; // End point of the interval (exclusive) - unsigned ValId; // identifier for the value contained in this interval. + VNInfo *valno; // identifier for the value contained in this interval. - LiveRange(unsigned S, unsigned E, unsigned V) : start(S), end(E), ValId(V) { + LiveRange(unsigned S, unsigned E, VNInfo *V) : start(S), end(E), valno(V) { assert(S < E && "Cannot create empty or backwards range"); } @@ -80,36 +100,18 @@ namespace llvm { /// state. struct LiveInterval { typedef SmallVector<LiveRange,4> Ranges; + typedef SmallVector<VNInfo*,4> VNInfoList; + unsigned reg; // the register of this interval unsigned preference; // preferred register to allocate for this interval float weight; // weight of this interval Ranges ranges; // the ranges in which this register is live - - /// ValueNumberInfo - If the value number definition is undefined (e.g. phi - /// merge point), it contains ~0u,x. If the value number is not in use, it - /// contains ~1u,x to indicate that the value # is not used. - /// def - Instruction # of the definition. - /// reg - Source reg iff val# is defined by a copy; zero otherwise. - /// kills - Instruction # of the kills. If a kill is an odd #, it means - /// the kill is a phi join point. - struct VNInfo { - unsigned def; - unsigned reg; - SmallVector<unsigned, 4> kills; - VNInfo() : def(~1U), reg(0) {} - VNInfo(unsigned d, unsigned r) : def(d), reg(r) {} - }; - - typedef std::vector<VNInfo> VNInfoList; - VNInfoList ValueNumberInfo; + unsigned numvals; // number of value#'s + VNInfoList valnos; // value#'s public: LiveInterval(unsigned Reg, float Weight) - : reg(Reg), preference(0), weight(Weight) { - } - - ~LiveInterval() { - ValueNumberInfo.clear(); + : reg(Reg), preference(0), weight(Weight), numvals(0) { } typedef Ranges::iterator iterator; @@ -121,12 +123,21 @@ namespace llvm { 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(); } + vni_iterator vni_begin() { return valnos.begin(); } + vni_iterator vni_end() { return valnos.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(); } + const_vni_iterator vni_begin() const { return valnos.begin(); } + const_vni_iterator vni_end() const { return valnos.end(); } + + ~LiveInterval() { + for (vni_iterator i = vni_begin(), e = vni_end(); i != e; ++i) { + VNInfo *VNI = *i; + if (VNI->parent == this) + delete VNI; + } + valnos.clear(); + } /// advanceTo - Advance the specified iterator to point to the LiveRange /// containing the specified position, or end() if the position is past the @@ -140,79 +151,39 @@ namespace llvm { return I; } - bool containsOneValue() const { return ValueNumberInfo.size() == 1; } + bool containsOneValue() const { return numvals == 1; } - unsigned getNumValNums() const { return ValueNumberInfo.size(); } + unsigned getNumValNums() const { return numvals; } - /// getValNumInfo - Returns a copy of the specified val#. + /// getFirstValNumInfo - Returns pointer to the first val#. /// - inline VNInfo& getValNumInfo(unsigned ValNo) { - return ValueNumberInfo[ValNo]; + inline VNInfo *getFirstValNumInfo() { + return valnos.front(); } - inline const VNInfo& getValNumInfo(unsigned ValNo) const { - return ValueNumberInfo[ValNo]; + inline const VNInfo *getFirstValNumInfo() const { + return valnos.front(); } /// 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; + void copyValNumInfo(VNInfo &DstValNo, VNInfo &SrcValNo) { + DstValNo.def = SrcValNo.def; + DstValNo.reg = SrcValNo.reg; + DstValNo.kills = SrcValNo.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) { - ValueNumberInfo.push_back(VNInfo(MIIdx, SrcReg)); - return ValueNumberInfo.size()-1; - } - - /// getDefForValNum - Return the machine instruction index that defines the - /// specified value number. - unsigned getDefForValNum(unsigned ValNo) const { - 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 { - return getValNumInfo(ValNo).reg; - } - - /// setDefForValNum - Set the machine instruction index that defines the - /// specified value number. - void setDefForValNum(unsigned ValNo, unsigned NewDef) { - getValNumInfo(ValNo).def = NewDef; - } - - /// setSrcRegForValNum - Set the source register of the specified value - /// number. - void setSrcRegForValNum(unsigned ValNo, unsigned NewReg) { - getValNumInfo(ValNo).reg = NewReg; - } - - /// getKillsForValNum - Return the kill instruction indexes of the specified - /// value number. - const SmallVector<unsigned, 4> &getKillsForValNum(unsigned ValNo) const { - return getValNumInfo(ValNo).kills; + VNInfo *getNextValue(unsigned MIIdx, unsigned SrcReg) { + VNInfo *VNI = new VNInfo(this, numvals++, MIIdx, SrcReg); + valnos.push_back(VNI); + return VNI; } /// addKillForValNum - Add a kill instruction index to the specified value /// number. - void addKillForValNum(unsigned ValNo, unsigned KillIdx) { - SmallVector<unsigned, 4> &kills = getValNumInfo(ValNo).kills; + static void addKill(VNInfo &VNI, unsigned KillIdx) { + SmallVector<unsigned, 4> &kills = VNI.kills; if (kills.empty()) { kills.push_back(KillIdx); } else { @@ -235,24 +206,6 @@ namespace llvm { } } - /// addKillsForValNum - Add a number of kills into the kills vector of - /// the specified value number. - void addKillsForValNum(unsigned ValNo, - const SmallVector<unsigned, 4> &kills) { - addKills(getValNumInfo(ValNo), kills); - } - - /// isKillForValNum - Returns true if KillIdx is a kill of the specified - /// val#. - bool isKillForValNum(unsigned ValNo, unsigned KillIdx) const { - const SmallVector<unsigned, 4> &kills = getValNumInfo(ValNo).kills; - SmallVector<unsigned, 4>::const_iterator - I = std::lower_bound(kills.begin(), kills.end(), KillIdx); - if (I == kills.end()) - return false; - return *I == KillIdx; - } - /// removeKill - Remove the specified kill from the list of kills of /// the specified val#. static bool removeKill(VNInfo &VNI, unsigned KillIdx) { @@ -266,49 +219,22 @@ namespace llvm { return false; } - /// removeKillForValNum - Remove the specified kill from the list of kills - /// of the specified val#. - bool removeKillForValNum(unsigned ValNo, unsigned KillIdx) { - return removeKill(getValNumInfo(ValNo), KillIdx); - } - - /// removeKillForValNum - Remove all the kills in specified range + /// removeKills - Remove all the kills in specified range /// [Start, End] of the specified val#. - void removeKillForValNum(unsigned ValNo, unsigned Start, unsigned End) { - SmallVector<unsigned, 4> &kills = getValNumInfo(ValNo).kills; + void removeKills(VNInfo &VNI, unsigned Start, unsigned End) { + SmallVector<unsigned, 4> &kills = VNI.kills; SmallVector<unsigned, 4>::iterator I = std::lower_bound(kills.begin(), kills.end(), Start); SmallVector<unsigned, 4>::iterator E = std::upper_bound(kills.begin(), kills.end(), End); kills.erase(I, E); } - - /// replaceKill - Replace a kill index of the specified value# with a new - /// kill. Returns true if OldKill was indeed a kill point. - static bool replaceKill(VNInfo &VNI, unsigned OldKill, unsigned NewKill) { - SmallVector<unsigned, 4> &kills = VNI.kills; - SmallVector<unsigned, 4>::iterator - I = std::lower_bound(kills.begin(), kills.end(), OldKill); - if (I != kills.end() && *I == OldKill) { - *I = NewKill; - return true; - } - return false; - } - - /// replaceKillForValNum - Replace a kill index of the specified value# with - /// a new kill. Returns true if OldKill was indeed a kill point. - bool replaceKillForValNum(unsigned ValNo, unsigned OldKill, - unsigned NewKill) { - assert(ValNo < ValueNumberInfo.size()); - return replaceKill(getValNumInfo(ValNo), OldKill, NewKill); - } /// 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 /// cause merging of V1/V2 values numbers and compaction of the value space. - void MergeValueNumberInto(unsigned V1, unsigned V2); + void MergeValueNumberInto(VNInfo *V1, VNInfo *V2); /// MergeInClobberRanges - For any live ranges that are not defined in the /// current interval, but are defined in the Clobbers interval, mark them @@ -320,7 +246,7 @@ namespace llvm { /// interval as the specified value number. The LiveRanges in RHS are /// allowed to overlap with LiveRanges in the current interval, but only if /// the overlapping LiveRanges have the specified value number. - void MergeRangesInAsValue(const LiveInterval &RHS, unsigned LHSValNo); + void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); bool empty() const { return ranges.empty(); } @@ -386,8 +312,7 @@ namespace llvm { /// mappings to the value numbers in the LHS/RHS intervals as specified. If /// the intervals are not joinable, this aborts. void join(LiveInterval &Other, int *ValNoAssignments, - int *RHSValNoAssignments, - SmallVector<VNInfo,16> &NewValueNumberInfo); + int *RHSValNoAssignments, SmallVector<VNInfo*, 16> &NewVNInfo); /// removeRange - Remove the specified range from this interval. Note that /// the range must already be in this interval in its entirety. diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 8e7a100..59d482e 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -239,7 +239,7 @@ namespace llvm { /// isReMaterializable - Returns true if the definition MI of the specified /// val# of the specified interval is re-materializable. - bool isReMaterializable(const LiveInterval &li, unsigned ValNum, + bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, MachineInstr *MI); /// tryFoldMemoryOperand - Attempts to fold a spill / restore from slot diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 0be4e9b..b10a721 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -108,13 +108,13 @@ bool LiveInterval::overlapsFrom(const LiveInterval& other, /// not invalidated. void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { assert(I != ranges.end() && "Not a valid interval!"); - unsigned ValId = I->ValId; + VNInfo *ValNo = I->valno; unsigned OldEnd = I->end; // Search for the first interval that we can't merge with. Ranges::iterator MergeTo = next(I); for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { - assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); + assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); } // If NewEnd was in the middle of an interval, make sure to get its endpoint. @@ -124,12 +124,12 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { ranges.erase(next(I), MergeTo); // Update kill info. - removeKillForValNum(ValId, OldEnd, I->end-1); + removeKills(*ValNo, OldEnd, I->end-1); // If the newly formed range now touches the range after it and if they have // the same value number, merge the two ranges into one range. Ranges::iterator Next = next(I); - if (Next != ranges.end() && Next->start <= I->end && Next->ValId == ValId) { + if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { I->end = Next->end; ranges.erase(Next); } @@ -142,7 +142,7 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { LiveInterval::Ranges::iterator LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { assert(I != ranges.end() && "Not a valid interval!"); - unsigned ValId = I->ValId; + VNInfo *ValNo = I->valno; // Search for the first interval that we can't merge with. Ranges::iterator MergeTo = I; @@ -152,13 +152,13 @@ LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { ranges.erase(MergeTo, I); return I; } - assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); + assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); --MergeTo; } while (NewStart <= MergeTo->start); // If we start in the middle of another interval, just delete a range and // extend that interval. - if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) { + if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { MergeTo->end = I->end; } else { // Otherwise, extend the interval right after. @@ -180,14 +180,14 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) { // another interval, just extend that interval to contain the range of LR. if (it != ranges.begin()) { iterator B = prior(it); - if (LR.ValId == B->ValId) { + if (LR.valno == B->valno) { if (B->start <= Start && B->end >= Start) { extendIntervalEndTo(B, End); return B; } } else { // Check to make sure that we are not overlapping two live ranges with - // different ValId's. + // different valno's. assert(B->end <= Start && "Cannot overlap two LiveRanges with differing ValID's" " (did you def the same reg twice in a MachineInstr?)"); @@ -197,7 +197,7 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) { // Otherwise, if this range ends in the middle of, or right next to, another // interval, merge it into that interval. if (it != ranges.end()) - if (LR.ValId == it->ValId) { + if (LR.valno == it->valno) { if (it->start <= End) { it = extendIntervalStartTo(it, Start); @@ -209,7 +209,7 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) { } } else { // Check to make sure that we are not overlapping two live ranges with - // different ValId's. + // different valno's. assert(it->start >= End && "Cannot overlap two LiveRanges with differing ValID's"); } @@ -233,7 +233,7 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) { // If the span we are removing is at the start of the LiveRange, adjust it. if (I->start == Start) { if (I->end == End) { - removeKillForValNum(I->ValId, Start, End); + removeKills(*I->valno, Start, End); ranges.erase(I); // Removed the whole LiveRange. } else I->start = End; @@ -243,7 +243,7 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) { // Otherwise if the span we are removing is at the end of the LiveRange, // adjust the other way. if (I->end == End) { - removeKillForValNum(I->ValId, Start, End); + removeKills(*I->valno, Start, End); I->end = Start; return; } @@ -253,7 +253,7 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) { I->end = Start; // Trim the old interval. // Insert the new one. - ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId)); + ranges.insert(next(I), LiveRange(End, OldEnd, I->valno)); } /// getLiveRangeContaining - Return the live range that contains the @@ -287,33 +287,44 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) { /// the intervals are not joinable, this aborts. void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, int *RHSValNoAssignments, - SmallVector<VNInfo, 16> &NewValueNumberInfo) { + SmallVector<VNInfo*, 16> &NewVNInfo) { + + // There might be some dead val#, create VNInfo for them. + for (unsigned i = 0, e = NewVNInfo.size(); i != e; ++i) { + VNInfo *VNI = NewVNInfo[i]; + if (!VNI) { + VNI = new VNInfo(this, i, ~1U, 0); + NewVNInfo[i] = VNI; + } + } // 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 (getDefForValNum(i) == ~1U) continue; // tombstone value # - if (i != (unsigned)LHSValNoAssignments[i]) { + for (vni_iterator i = vni_begin(), e = vni_end(); i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (VNI->def == ~1U) continue; // tombstone value # + if (VNI != NewVNInfo[LHSValNoAssignments[VN]]) { 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->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; ++OutIt; for (iterator I = OutIt, E = end(); I != E; ++I) { - OutIt->ValId = LHSValNoAssignments[I->ValId]; + OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; // 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) { + if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { (OutIt-1)->end = OutIt->end; } else { if (I != OutIt) { @@ -330,17 +341,29 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, ranges.erase(OutIt, end()); } - // Update val# info first. Increasing live ranges may invalidate some kills. - ValueNumberInfo.clear(); - for (SmallVector<VNInfo, 16>::iterator I = NewValueNumberInfo.begin(), - E = NewValueNumberInfo.end(); I != E; ++I) - ValueNumberInfo.push_back(*I); + // Remember assignements because val# ids are changing. + std::vector<unsigned> OtherAssignments; + for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) + OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); + + // Update val# info. Renumber them and make sure they all belong to this + // LiveInterval now. + valnos.clear(); + numvals = 0; + for (unsigned i = 0, e = NewVNInfo.size(); i != e; ++i) { + VNInfo *VNI = NewVNInfo[i]; + VNI->parent = this; + VNI->id = i; // Renumber val#. + valnos.push_back(VNI); + ++numvals; + } // 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. - I->ValId = RHSValNoAssignments[I->ValId]; + unsigned RangeNo = 0; + for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { + // Map the valno in the other live range to the current live range. + I->valno = NewVNInfo[OtherAssignments[RangeNo]]; InsertPos = addRangeFrom(*I, InsertPos); } @@ -354,13 +377,13 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, /// allowed to overlap with LiveRanges in the current interval, but only if /// the overlapping LiveRanges have the specified value number. void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, - unsigned LHSValNo) { + VNInfo *LHSValNo) { // TODO: Make this more efficient. iterator InsertPos = begin(); for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { - // Map the ValId in the other live range to the current live range. + // Map the valno in the other live range to the current live range. LiveRange Tmp = *I; - Tmp.ValId = LHSValNo; + Tmp.valno = LHSValNo; InsertPos = addRangeFrom(Tmp, InsertPos); } } @@ -375,7 +398,7 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers) { // Find a value # to use for the clobber ranges. If there is already a value# // for unknown values, use it. // FIXME: Use a single sentinal number for these! - unsigned ClobberValNo = getNextValue(~0U, 0); + VNInfo *ClobberValNo = getNextValue(~0U, 0); iterator IP = begin(); for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { @@ -404,7 +427,7 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers) { /// are found to be equivalent. This eliminates V1, replacing all /// LiveRanges with the V1 value number with the V2 value number. This can /// cause merging of V1/V2 values numbers and compaction of the value space. -void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { +void LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { assert(V1 != V2 && "Identical value#'s are always equivalent!"); // This code actually merges the (numerically) larger value number into the @@ -413,21 +436,21 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { // instruction that defines the result value. // Make sure V2 is smaller than V1. - if (V1 < V2) { - copyValNumInfo(V1, V2); + if (V1->id < V2->id) { + copyValNumInfo(*V1, *V2); std::swap(V1, V2); } // Merge V1 live ranges into V2. for (iterator I = begin(); I != end(); ) { iterator LR = I++; - if (LR->ValId != V1) continue; // Not a V1 LiveRange. + if (LR->valno != V1) continue; // Not a V1 LiveRange. // Okay, we found a V1 live range. If it had a previous, touching, V2 live // range, extend it. if (LR != begin()) { iterator Prev = LR-1; - if (Prev->ValId == V2 && Prev->end == LR->start) { + if (Prev->valno == V2 && Prev->end == LR->start) { Prev->end = LR->end; // Erase this live-range. @@ -439,13 +462,13 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { // Okay, now we have a V1 or V2 live range that is maximally merged forward. // Ensure that it is a V2 live-range. - LR->ValId = V2; + LR->valno = V2; // If we can merge it into later V2 live ranges, do so now. We ignore any // following V1 live ranges, as they will be merged in subsequent iterations // of the loop. if (I != end()) { - if (I->start == LR->end && I->ValId == V2) { + if (I->start == LR->end && I->valno == V2) { LR->end = I->end; ranges.erase(I); I = LR+1; @@ -456,12 +479,15 @@ 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 == getNumValNums()-1) { + if (V1->id == getNumValNums()-1) { do { - ValueNumberInfo.pop_back(); - } while (ValueNumberInfo.back().def == ~1U); + VNInfo *VNI = valnos.back(); + valnos.pop_back(); + delete VNI; + --numvals; + } while (valnos.back()->def == ~1U); } else { - setDefForValNum(V1, ~1U); + V1->def = ~1U; } } @@ -473,7 +499,7 @@ unsigned LiveInterval::getSize() const { } std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { - return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")"; + return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; } void LiveRange::dump() const { @@ -503,21 +529,21 @@ void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const { unsigned vnum = 0; for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; ++i, ++vnum) { - const VNInfo &vni = *i; + const VNInfo *vni = *i; if (vnum) OS << " "; OS << vnum << "@"; - if (vni.def == ~1U) { + if (vni->def == ~1U) { OS << "x"; } else { - if (vni.def == ~0U) + if (vni->def == ~0U) OS << "?"; else - OS << vni.def; - unsigned ee = vni.kills.size(); + OS << vni->def; + unsigned ee = vni->kills.size(); if (ee) { OS << "-("; for (unsigned j = 0; j != ee; ++j) { - OS << vni.kills[j]; + OS << vni->kills[j]; if (j != ee-1) OS << " "; } diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index b2121c9..7958ab7 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -205,8 +205,8 @@ static bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg, /// isReMaterializable - Returns true if the definition MI of the specified /// val# of the specified interval is re-materializable. -bool LiveIntervals::isReMaterializable(const LiveInterval &li, unsigned ValNum, - MachineInstr *MI) { +bool LiveIntervals::isReMaterializable(const LiveInterval &li, + const VNInfo *ValNo, MachineInstr *MI) { if (DisableReMat) return false; @@ -220,10 +220,12 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, unsigned ValNum, // This is a load from fixed stack slot. It can be rematerialized unless it's // re-defined by a two-address instruction. - for (unsigned i = 0, e = li.getNumValNums(); i != e; ++i) { - if (i == ValNum) + for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); + i != e; ++i) { + const VNInfo *VNI = *i; + if (VNI == ValNo) continue; - unsigned DefIdx = li.getDefForValNum(i); + unsigned DefIdx = VNI->def; if (DefIdx == ~1U) continue; // Dead val#. MachineInstr *DefMI = (DefIdx == ~0u) @@ -283,25 +285,27 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { unsigned slot = VirtRegMap::MAX_STACK_SLOT; bool NeedStackSlot = false; - for (unsigned i = 0; i != NumValNums; ++i) { - unsigned DefIdx = li.getDefForValNum(i); + for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); + i != e; ++i) { + const VNInfo *VNI = *i; + unsigned VN = VNI->id; + unsigned DefIdx = VNI->def; if (DefIdx == ~1U) continue; // Dead val#. // Is the def for the val# rematerializable? MachineInstr *DefMI = (DefIdx == ~0u) ? NULL : getInstructionFromIndex(DefIdx); - if (DefMI && isReMaterializable(li, i, DefMI)) { + if (DefMI && isReMaterializable(li, VNI, DefMI)) { // Remember how to remat the def of this val#. - ReMatOrigDefs[i] = DefMI; + ReMatOrigDefs[VN] = DefMI; // Original def may be modified so we have to make a copy here. vrm must // delete these! - ReMatDefs[i] = DefMI = DefMI->clone(); + ReMatDefs[VN] = DefMI = DefMI->clone(); vrm.setVirtIsReMaterialized(reg, DefMI); bool CanDelete = true; - const SmallVector<unsigned, 4> &kills = li.getKillsForValNum(i); - for (unsigned j = 0, ee = kills.size(); j != ee; ++j) { - unsigned KillIdx = kills[j]; + for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { + unsigned KillIdx = VNI->kills[j]; MachineInstr *KillMI = (KillIdx & 1) ? NULL : getInstructionFromIndex(KillIdx); // Kill is a phi node, not all of its uses can be rematerialized. @@ -316,7 +320,7 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { } if (CanDelete) - ReMatDelete.set(i); + ReMatDelete.set(VN); } else { // Need a stack slot if there is any live range where uses cannot be // rematerialized. @@ -330,10 +334,10 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { - MachineInstr *DefMI = ReMatDefs[I->ValId]; - MachineInstr *OrigDefMI = ReMatOrigDefs[I->ValId]; + MachineInstr *DefMI = ReMatDefs[I->valno->id]; + MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id]; bool DefIsReMat = DefMI != NULL; - bool CanDelete = ReMatDelete[I->ValId]; + bool CanDelete = ReMatDelete[I->valno->id]; int LdSlot = 0; bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot); unsigned index = getBaseIndex(I->start); @@ -407,11 +411,11 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { vrm.grow(); if (DefIsReMat) { vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/); - if (ReMatIds[I->ValId] == VirtRegMap::MAX_STACK_SLOT) { + if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) { // Each valnum may have its own remat id. - ReMatIds[I->ValId] = vrm.assignVirtReMatId(NewVReg); + ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg); } else { - vrm.assignVirtReMatId(NewVReg, ReMatIds[I->ValId]); + vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->id]); } if (!CanDelete || (HasUse && HasDef)) { // If this is a two-addr instruction then its use operands are @@ -482,15 +486,14 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (interval.empty()) { // Get the Idx of the defining instructions. unsigned defIndex = getDefIndex(MIIdx); - unsigned ValNum; + VNInfo *ValNo; unsigned SrcReg, DstReg; if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) - ValNum = interval.getNextValue(defIndex, 0); + ValNo = interval.getNextValue(defIndex, 0); else - ValNum = interval.getNextValue(defIndex, SrcReg); - - assert(ValNum == 0 && "First value in interval is not 0?"); - ValNum = 0; // Clue in the optimizer. + ValNo = interval.getNextValue(defIndex, SrcReg); + + assert(ValNo->id == 0 && "First value in interval is not 0?"); // Loop over all of the blocks that the vreg is defined in. There are // two cases we have to handle here. The most common case is a vreg @@ -509,10 +512,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (killIdx > defIndex) { assert(vi.AliveBlocks.none() && "Shouldn't be alive across any blocks!"); - LiveRange LR(defIndex, killIdx, ValNum); + LiveRange LR(defIndex, killIdx, ValNo); interval.addRange(LR); DOUT << " +" << LR << "\n"; - interval.addKillForValNum(ValNum, killIdx); + interval.addKill(*ValNo, killIdx); return; } } @@ -523,7 +526,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // range that goes from this definition to the end of the defining block. LiveRange NewLR(defIndex, getInstructionIndex(&mbb->back()) + InstrSlots::NUM, - ValNum); + ValNo); DOUT << " +" << NewLR; interval.addRange(NewLR); @@ -536,7 +539,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (!MBB->empty()) { LiveRange LR(getMBBStartIdx(i), getInstructionIndex(&MBB->back()) + InstrSlots::NUM, - ValNum); + ValNo); interval.addRange(LR); DOUT << " +" << LR; } @@ -549,9 +552,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineInstr *Kill = vi.Kills[i]; unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; LiveRange LR(getMBBStartIdx(Kill->getParent()), - killIdx, ValNum); + killIdx, ValNo); interval.addRange(LR); - interval.addKillForValNum(ValNum, killIdx); + interval.addKill(*ValNo, killIdx); DOUT << " +" << LR; } @@ -570,6 +573,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, unsigned RedefIndex = getDefIndex(MIIdx); const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); + VNInfo *OldValNo = OldLR->valno; unsigned OldEnd = OldLR->end; // Delete the initial value, which should be short and continuous, @@ -582,24 +586,24 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // The new value number (#1) is defined by the instruction we claimed // defined value #0. - unsigned ValNo = interval.getNextValue(0, 0); - interval.copyValNumInfo(ValNo, 0); + VNInfo *ValNo = interval.getNextValue(0, 0); + interval.copyValNumInfo(*ValNo, *OldValNo); // Value#0 is now defined by the 2-addr instruction. - interval.setDefForValNum(0, RedefIndex); - interval.setSrcRegForValNum(0, 0); + OldValNo->def = RedefIndex; + OldValNo->reg = 0; // Add the new live interval which replaces the range for the input copy. LiveRange LR(DefIndex, RedefIndex, ValNo); DOUT << " replace range with " << LR; interval.addRange(LR); - interval.addKillForValNum(ValNo, RedefIndex); - interval.removeKillForValNum(ValNo, RedefIndex, OldEnd); + interval.addKill(*ValNo, RedefIndex); + interval.removeKills(*ValNo, RedefIndex, OldEnd); // If this redefinition is dead, we need to add a dummy unit live // range covering the def slot. if (lv_->RegisterDefIsDead(mi, interval.reg)) - interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); + interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); DOUT << " RESULT: "; interval.print(DOUT, mri_); @@ -613,13 +617,14 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, "PHI elimination vreg should have one kill, the PHI itself!"); // Remove the old range that we now know has an incorrect number. + VNInfo *VNI = interval.getFirstValNumInfo(); MachineInstr *Killer = vi.Kills[0]; unsigned Start = getMBBStartIdx(Killer->getParent()); unsigned End = getUseIndex(getInstructionIndex(Killer))+1; DOUT << " Removing [" << Start << "," << End << "] from: "; interval.print(DOUT, mri_); DOUT << "\n"; interval.removeRange(Start, End); - interval.addKillForValNum(0, Start+1); // odd # means phi node + interval.addKill(*VNI, Start+1); // odd # means phi node DOUT << " RESULT: "; interval.print(DOUT, mri_); // Replace the interval with one of a NEW value number. Note that this @@ -627,7 +632,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, LiveRange LR(Start, End, interval.getNextValue(~0, 0)); DOUT << " replace range with " << LR; interval.addRange(LR); - interval.addKillForValNum(LR.ValId, End); + interval.addKill(*LR.valno, End); DOUT << " RESULT: "; interval.print(DOUT, mri_); } @@ -636,17 +641,17 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // rest of the live range. unsigned defIndex = getDefIndex(MIIdx); - unsigned ValNum; + VNInfo *ValNo; unsigned SrcReg, DstReg; if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) - ValNum = interval.getNextValue(defIndex, 0); + ValNo = interval.getNextValue(defIndex, 0); else - ValNum = interval.getNextValue(defIndex, SrcReg); + ValNo = interval.getNextValue(defIndex, SrcReg); unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; - LiveRange LR(defIndex, killIndex, ValNum); + LiveRange LR(defIndex, killIndex, ValNo); interval.addRange(LR); - interval.addKillForValNum(ValNum, killIndex-1); // odd # means phi node + interval.addKill(*ValNo, killIndex-1); // odd # means phi node DOUT << " +" << LR; } } @@ -707,11 +712,11 @@ exit: // Already exists? Extend old live interval. LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); - unsigned Id = (OldLR != interval.end()) - ? OldLR->ValId : interval.getNextValue(start, SrcReg); - LiveRange LR(start, end, Id); + VNInfo *ValNo = (OldLR != interval.end()) + ? OldLR->valno : interval.getNextValue(start, SrcReg); + LiveRange LR(start, end, ValNo); interval.addRange(LR); - interval.addKillForValNum(LR.ValId, end); + interval.addKill(*LR.valno, end); DOUT << " +" << LR << '\n'; } @@ -778,7 +783,7 @@ exit: LiveRange LR(start, end, interval.getNextValue(start, 0)); interval.addRange(LR); - interval.addKillForValNum(LR.ValId, end); + interval.addKill(*LR.valno, end); DOUT << " +" << LR << '\n'; } diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index d8d0ce2..703f9ff 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -85,24 +85,23 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte // 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); - unsigned BValNo = BLR->ValId; + VNInfo *BValNo = BLR->valno; // Get the location that B is defined at. Two options: either this value has // an unknown definition point or it is defined at CopyIdx. If unknown, we // can't process it. - unsigned BValNoDefIdx = IntB.getDefForValNum(BValNo); - if (!IntB.getSrcRegForValNum(BValNo)) return false; - assert(BValNoDefIdx == CopyIdx && + if (!BValNo->reg) return false; + assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); // AValNo is the value number in A that defines the copy, A0 in the example. LiveInterval::iterator AValLR = IntA.FindLiveRangeContaining(CopyIdx-1); - unsigned AValNo = AValLR->ValId; + VNInfo *AValNo = AValLR->valno; // If AValNo is defined as a copy from IntB, we can potentially process this. // Get the instruction that defines this value number. - unsigned SrcReg = IntA.getSrcRegForValNum(AValNo); + unsigned SrcReg = AValNo->reg; if (!SrcReg) return false; // Not defined by a copy. // If the value number is not defined by a copy instruction, ignore it. @@ -112,8 +111,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte if (rep(SrcReg) != IntB.reg) return false; // Get the LiveRange in IntB that this value number starts with. - unsigned AValNoInstIdx = IntA.getDefForValNum(AValNo); - LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1); + LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1); // Make sure that the end of the live range is inside the same block as // CopyMI. @@ -145,8 +143,8 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte // We are about to delete CopyMI, so need to remove it as the 'instruction // that defines this value #'. Update the the valnum with the new defining // instruction #. - IntB.setDefForValNum(BValNo, FillerStart); - IntB.setSrcRegForValNum(BValNo, 0); + BValNo->def = FillerStart; + BValNo->reg = 0; // Okay, we can merge them. We need to insert a new liverange: // [ValLR.end, BLR.begin) of either value number, then we merge the @@ -165,8 +163,8 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte } // Okay, merge "B1" into the same value number as "B0". - if (BValNo != ValLR->ValId) - IntB.MergeValueNumberInto(BValNo, ValLR->ValId); + if (BValNo != ValLR->valno) + IntB.MergeValueNumberInto(BValNo, ValLR->valno); DOUT << " result = "; IntB.print(DOUT, mri_); DOUT << "\n"; @@ -412,43 +410,42 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, /// 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<LiveInterval::VNInfo, 16> &ValueNumberInfo, - SmallVector<int, 16> &ThisFromOther, - SmallVector<int, 16> &OtherFromThis, +static unsigned ComputeUltimateVN(VNInfo *VNI, + SmallVector<VNInfo*, 16> &NewVNInfo, + SmallVector<VNInfo*, 16> &ThisFromOther, + SmallVector<VNInfo*, 16> &OtherFromThis, SmallVector<int, 16> &ThisValNoAssignments, - SmallVector<int, 16> &OtherValNoAssignments, - LiveInterval &ThisLI, LiveInterval &OtherLI) { + SmallVector<int, 16> &OtherValNoAssignments) { + unsigned VN = VNI->id; + // If the VN has already been computed, just return it. if (ThisValNoAssignments[VN] >= 0) return ThisValNoAssignments[VN]; // assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); - + // 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) { - ValueNumberInfo.push_back(ThisLI.getValNumInfo(VN)); - return ThisValNoAssignments[VN] = ValueNumberInfo.size()-1; + VNInfo *OtherValNo = ThisFromOther[VN]; + if (!OtherValNo) { + NewVNInfo.push_back(VNI); + return ThisValNoAssignments[VN] = NewVNInfo.size()-1; } // Otherwise, this *is* a copy from the RHS. If the other side has already // been computed, return it. - if (OtherValNoAssignments[OtherValNo] >= 0) - return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo]; + if (OtherValNoAssignments[OtherValNo->id] >= 0) + return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; // 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, ValueNumberInfo, - OtherFromThis, ThisFromOther, - OtherValNoAssignments, ThisValNoAssignments, - OtherLI, ThisLI); + ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, + OtherValNoAssignments, ThisValNoAssignments); return ThisValNoAssignments[VN] = UltimateVN; } -static bool InVector(unsigned Val, const SmallVector<unsigned, 8> &V) { +static bool InVector(VNInfo *Val, const SmallVector<VNInfo*, 8> &V) { return std::find(V.begin(), V.end(), Val) != V.end(); } @@ -477,7 +474,7 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) if (RHSIt != RHS.begin()) --RHSIt; } - SmallVector<unsigned, 8> EliminatedLHSVals; + SmallVector<VNInfo*, 8> EliminatedLHSVals; while (1) { // Determine if these live intervals overlap. @@ -493,13 +490,13 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // coalesce these live ranges and we bail out. if (Overlaps) { // If we haven't already recorded that this value # is safe, check it. - if (!InVector(LHSIt->ValId, EliminatedLHSVals)) { + if (!InVector(LHSIt->valno, EliminatedLHSVals)) { // Copy from the RHS? - unsigned SrcReg = LHS.getSrcRegForValNum(LHSIt->ValId); + unsigned SrcReg = LHSIt->valno->reg; if (rep(SrcReg) != RHS.reg) return false; // Nope, bail out. - EliminatedLHSVals.push_back(LHSIt->ValId); + EliminatedLHSVals.push_back(LHSIt->valno); } // We know this entire LHS live range is okay, so skip it now. @@ -516,15 +513,15 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // want to notice this copy (so that it gets coalesced away) even though // the live ranges don't actually overlap. if (LHSIt->start == RHSIt->end) { - if (InVector(LHSIt->ValId, EliminatedLHSVals)) { + if (InVector(LHSIt->valno, EliminatedLHSVals)) { // We already know that this value number is going to be merged in // if coalescing succeeds. Just skip the liverange. if (++LHSIt == LHSEnd) break; } else { // Otherwise, if this is a copy from the RHS, mark it as being merged // in. - if (rep(LHS.getSrcRegForValNum(LHSIt->ValId)) == RHS.reg) { - EliminatedLHSVals.push_back(LHSIt->ValId); + if (rep(LHSIt->valno->reg) == RHS.reg) { + EliminatedLHSVals.push_back(LHSIt->valno); // We know this entire LHS live range is okay, so skip it now. if (++LHSIt == LHSEnd) break; @@ -542,13 +539,13 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // optimize for it: if there is more than one value, we merge them all into // the lowest numbered one, then handle the interval as if we were merging // with one value number. - unsigned LHSValNo; + VNInfo *LHSValNo; if (EliminatedLHSVals.size() > 1) { // Loop through all the equal value numbers merging them into the smallest // one. - unsigned Smallest = EliminatedLHSVals[0]; + VNInfo *Smallest = EliminatedLHSVals[0]; for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) { - if (EliminatedLHSVals[i] < Smallest) { + if (EliminatedLHSVals[i]->id < Smallest->id) { // Merge the current notion of the smallest into the smaller one. LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]); Smallest = EliminatedLHSVals[i]; @@ -566,13 +563,13 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // Okay, now that there is a single LHS value number that we're merging the // RHS into, update the value number info for the LHS to indicate that the // value number is defined where the RHS value number was. - const LiveInterval::VNInfo VNI = RHS.getValNumInfo(0); - LHS.setDefForValNum(LHSValNo, VNI.def); - LHS.setSrcRegForValNum(LHSValNo, VNI.reg); + const VNInfo *VNI = RHS.getFirstValNumInfo(); + LHSValNo->def = VNI->def; + LHSValNo->reg = VNI->reg; // Okay, the final step is to loop over the RHS live intervals, adding them to // the LHS. - LHS.addKillsForValNum(LHSValNo, VNI.kills); + LHS.addKills(*LHSValNo, VNI->kills); LHS.MergeRangesInAsValue(RHS, LHSValNo); LHS.weight += RHS.weight; if (RHS.preference && !LHS.preference) @@ -592,9 +589,9 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, // coalesced. SmallVector<int, 16> LHSValNoAssignments; SmallVector<int, 16> RHSValNoAssignments; - SmallVector<int, 16> LHSValsDefinedFromRHS; - SmallVector<int, 16> RHSValsDefinedFromLHS; - SmallVector<LiveInterval::VNInfo, 16> ValueNumberInfo; + SmallVector<VNInfo*, 16> LHSValsDefinedFromRHS; + SmallVector<VNInfo*, 16> RHSValsDefinedFromLHS; + SmallVector<VNInfo*, 16> NewVNInfo; // If a live interval is a physical register, conservatively check if any // of its sub-registers is overlapping the live interval of the virtual @@ -617,6 +614,9 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, } } + LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), NULL); + RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), NULL); + // Compute ultimate value numbers for the LHS and RHS values. if (RHS.containsOneValue()) { // Copies from a liveinterval with a single value are simple to handle and @@ -626,8 +626,8 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, // Find out if the RHS is defined as a copy from some value in the LHS. int RHSVal0DefinedFromLHS = -1; int RHSValID = -1; - LiveInterval::VNInfo RHSValNoInfo; - unsigned RHSSrcReg = RHS.getSrcRegForValNum(0); + VNInfo *RHSValNoInfo = NULL; + unsigned RHSSrcReg = RHS.getFirstValNumInfo()->reg; if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) { // If RHS is not defined as a copy from the LHS, we can use simpler and // faster checks to see if the live ranges are coalescable. This joiner @@ -635,47 +635,48 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, if (!MRegisterInfo::isPhysicalRegister(RHS.reg)) { return SimpleJoin(LHS, RHS); } else { - RHSValNoInfo = RHS.getValNumInfo(0); + RHSValNoInfo = RHS.getFirstValNumInfo(); } } else { // It was defined as a copy from the LHS, find out what value # it is. - unsigned ValInst = RHS.getDefForValNum(0); - RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId; - RHSValNoInfo = LHS.getValNumInfo(RHSValID); + const VNInfo *VNI = RHS.getFirstValNumInfo(); + RHSValNoInfo = LHS.getLiveRangeContaining(VNI->def-1)->valno; + RHSValID = RHSValNoInfo->id; RHSVal0DefinedFromLHS = RHSValID; } LHSValNoAssignments.resize(LHS.getNumValNums(), -1); RHSValNoAssignments.resize(RHS.getNumValNums(), -1); - ValueNumberInfo.resize(LHS.getNumValNums()); + NewVNInfo.resize(LHS.getNumValNums(), NULL); // Okay, *all* of the values in LHS that are defined as a copy from RHS // should now get updated. - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - if (unsigned LHSSrcReg = LHS.getSrcRegForValNum(VN)) { + for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (unsigned LHSSrcReg = VNI->reg) { if (rep(LHSSrcReg) != RHS.reg) { // If this is not a copy from the RHS, its value number will be // unmodified by the coalescing. - ValueNumberInfo[VN] = LHS.getValNumInfo(VN); + NewVNInfo[VN] = VNI; LHSValNoAssignments[VN] = VN; } else if (RHSValID == -1) { // Otherwise, it is a copy from the RHS, and we don't already have a // value# for it. Keep the current value number, but remember it. LHSValNoAssignments[VN] = RHSValID = VN; - ValueNumberInfo[VN] = RHSValNoInfo; - RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN)); + NewVNInfo[VN] = RHSValNoInfo; + LHSValsDefinedFromRHS[VN] = VNI; } else { // Otherwise, use the specified value #. LHSValNoAssignments[VN] = RHSValID; - if (VN != (unsigned)RHSValID) - ValueNumberInfo[VN].def = ~1U; // Now this val# is dead. - else { - ValueNumberInfo[VN] = RHSValNoInfo; - RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN)); + if (VN == (unsigned)RHSValID) { // Else this val# is dead. + NewVNInfo[VN] = RHSValNoInfo; + LHSValsDefinedFromRHS[VN] = VNI; } } } else { - ValueNumberInfo[VN] = LHS.getValNumInfo(VN); + NewVNInfo[VN] = VNI; LHSValNoAssignments[VN] = VN; } } @@ -683,17 +684,17 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, assert(RHSValID != -1 && "Didn't find value #?"); RHSValNoAssignments[0] = RHSValID; if (RHSVal0DefinedFromLHS != -1) { - int LHSValId = LHSValNoAssignments[RHSVal0DefinedFromLHS]; - unsigned DefIdx = RHS.getDefForValNum(0); - LiveInterval::removeKill(ValueNumberInfo[LHSValId], DefIdx); - LHS.addKills(ValueNumberInfo[LHSValId], RHS.getKillsForValNum(0)); + const VNInfo *VNI = RHS.getFirstValNumInfo(); + RHSValsDefinedFromLHS[0] = LHS.getLiveRangeContaining(VNI->def-1)->valno; } } else { // Loop over the value numbers of the LHS, seeing if any are defined from // the RHS. - LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1); - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - unsigned ValSrcReg = LHS.getSrcRegForValNum(VN); + for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + unsigned ValSrcReg = VNI->reg; if (ValSrcReg == 0) // Src not defined by a copy? continue; @@ -703,15 +704,16 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, continue; // Figure out the value # from the RHS. - unsigned ValInst = LHS.getDefForValNum(VN); - LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId; + LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(VNI->def-1)->valno; } // Loop over the value numbers of the RHS, seeing if any are defined from // the LHS. - RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1); - for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { - unsigned ValSrcReg = RHS.getSrcRegForValNum(VN); + for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + unsigned ValSrcReg = VNI->reg; if (ValSrcReg == 0) // Src not defined by a copy? continue; @@ -721,34 +723,39 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, continue; // Figure out the value # from the LHS. - unsigned ValInst = RHS.getDefForValNum(VN); - RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId; + RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(VNI->def-1)->valno; } LHSValNoAssignments.resize(LHS.getNumValNums(), -1); RHSValNoAssignments.resize(RHS.getNumValNums(), -1); - ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); + NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - if (LHSValNoAssignments[VN] >= 0 || LHS.getDefForValNum(VN) == ~1U) + for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (LHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) continue; - ComputeUltimateVN(VN, ValueNumberInfo, + ComputeUltimateVN(VNI, NewVNInfo, LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, - LHSValNoAssignments, RHSValNoAssignments, LHS, RHS); + LHSValNoAssignments, RHSValNoAssignments); } - for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { - if (RHSValNoAssignments[VN] >= 0 || RHS.getDefForValNum(VN) == ~1U) + for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (RHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) continue; // If this value number isn't a copy from the LHS, it's a new number. - if (RHSValsDefinedFromLHS[VN] == -1) { - ValueNumberInfo.push_back(RHS.getValNumInfo(VN)); - RHSValNoAssignments[VN] = ValueNumberInfo.size()-1; + if (!RHSValsDefinedFromLHS[VN]) { + NewVNInfo.push_back(VNI); + RHSValNoAssignments[VN] = NewVNInfo.size()-1; continue; } - ComputeUltimateVN(VN, ValueNumberInfo, + ComputeUltimateVN(VNI, NewVNInfo, RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, - RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); + RHSValNoAssignments, LHSValNoAssignments); } } @@ -781,7 +788,8 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, if (Overlaps) { // If the live range overlap will map to the same value number in the // result liverange, we can still coalesce them. If not, we can't. - if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId]) + if (LHSValNoAssignments[I->valno->id] != + RHSValNoAssignments[J->valno->id]) return false; } @@ -795,23 +803,25 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, } // Update kill info. Some live ranges are extended due to copy coalescing. - for (unsigned i = 0, e = RHSValsDefinedFromLHS.size(); i != e; ++i) { - int LHSValId = RHSValsDefinedFromLHS[i]; - if (LHSValId == -1) + for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (VN >= RHSValsDefinedFromLHS.size() || !RHSValsDefinedFromLHS[VN]) continue; - unsigned RHSValId = RHSValNoAssignments[i]; - unsigned DefIdx = RHS.getDefForValNum(i); - LiveInterval::removeKill(ValueNumberInfo[RHSValId], DefIdx); - LHS.addKills(ValueNumberInfo[RHSValId], RHS.getKillsForValNum(i)); + unsigned RHSValID = RHSValNoAssignments[VN]; + LiveInterval::removeKill(*NewVNInfo[RHSValID], VNI->def); + LHS.addKills(*NewVNInfo[RHSValID], VNI->kills); } - for (unsigned i = 0, e = LHSValsDefinedFromRHS.size(); i != e; ++i) { - int RHSValId = LHSValsDefinedFromRHS[i]; - if (RHSValId == -1) + for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (VN >= LHSValsDefinedFromRHS.size() || !LHSValsDefinedFromRHS[VN]) continue; - unsigned LHSValId = LHSValNoAssignments[i]; - unsigned DefIdx = LHS.getDefForValNum(i); - LiveInterval::removeKill(ValueNumberInfo[LHSValId], DefIdx); - RHS.addKills(ValueNumberInfo[LHSValId], LHS.getKillsForValNum(i)); + unsigned LHSValID = LHSValNoAssignments[VN]; + LiveInterval::removeKill(*NewVNInfo[LHSValID], VNI->def); + RHS.addKills(*NewVNInfo[LHSValID], VNI->kills); } // If we get here, we know that we can coalesce the live ranges. Ask the @@ -819,12 +829,10 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, if ((RHS.ranges.size() > LHS.ranges.size() && MRegisterInfo::isVirtualRegister(LHS.reg)) || MRegisterInfo::isPhysicalRegister(RHS.reg)) { - RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], - ValueNumberInfo); + RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo); Swapped = true; } else { - LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], - ValueNumberInfo); + LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo); Swapped = false; } return true; |