diff options
Diffstat (limited to 'lib/CodeGen')
| -rw-r--r-- | lib/CodeGen/LiveInterval.cpp | 110 | ||||
| -rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 349 | ||||
| -rw-r--r-- | lib/CodeGen/PreAllocSplitting.cpp | 153 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 47 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocPBQP.cpp | 3 | ||||
| -rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.cpp | 171 | ||||
| -rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.h | 9 | ||||
| -rw-r--r-- | lib/CodeGen/Spiller.cpp | 80 | ||||
| -rw-r--r-- | lib/CodeGen/StrongPHIElimination.cpp | 31 | ||||
| -rw-r--r-- | lib/CodeGen/VirtRegMap.h | 11 |
10 files changed, 517 insertions, 447 deletions
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 805b6728f2..4eb3eab539 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -28,6 +28,11 @@ #include <algorithm> using namespace llvm; +// Print a MachineInstrIndex to a raw_ostream. +void MachineInstrIndex::print(raw_ostream &os) const { + os << (index & ~PHI_BIT); +} + // An example for liveAt(): // // this = [1,4), liveAt(0) will return false. The instruction defining this @@ -35,7 +40,7 @@ using namespace llvm; // variable it represents. This is because slot 1 is used (def slot) and spans // up to slot 3 (store slot). // -bool LiveInterval::liveAt(unsigned I) const { +bool LiveInterval::liveAt(MachineInstrIndex I) const { Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); if (r == ranges.begin()) @@ -48,7 +53,7 @@ bool LiveInterval::liveAt(unsigned I) const { // liveBeforeAndAt - Check if the interval is live at the index and the index // just before it. If index is liveAt, check if it starts a new live range. // If it does, then check if the previous live range ends at index-1. -bool LiveInterval::liveBeforeAndAt(unsigned I) const { +bool LiveInterval::liveBeforeAndAt(MachineInstrIndex I) const { Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); if (r == ranges.begin()) @@ -126,7 +131,7 @@ bool LiveInterval::overlapsFrom(const LiveInterval& other, /// overlaps - Return true if the live interval overlaps a range specified /// by [Start, End). -bool LiveInterval::overlaps(unsigned Start, unsigned End) const { +bool LiveInterval::overlaps(MachineInstrIndex Start, MachineInstrIndex End) const { assert(Start < End && "Invalid range"); const_iterator I = begin(); const_iterator E = end(); @@ -144,10 +149,10 @@ bool LiveInterval::overlaps(unsigned Start, unsigned End) const { /// 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 /// not invalidated. -void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { +void LiveInterval::extendIntervalEndTo(Ranges::iterator I, MachineInstrIndex NewEnd) { assert(I != ranges.end() && "Not a valid interval!"); VNInfo *ValNo = I->valno; - unsigned OldEnd = I->end; + MachineInstrIndex OldEnd = I->end; // Search for the first interval that we can't merge with. Ranges::iterator MergeTo = next(I); @@ -162,7 +167,7 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { ranges.erase(next(I), MergeTo); // Update kill info. - removeKills(ValNo, OldEnd, I->end-1); + ValNo->removeKills(OldEnd, I->end.prevSlot()); // 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. @@ -178,7 +183,7 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { /// specified by I to start at the specified endpoint. To do this, we should /// merge and eliminate all ranges that this will overlap with. LiveInterval::Ranges::iterator -LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { +LiveInterval::extendIntervalStartTo(Ranges::iterator I, MachineInstrIndex NewStart) { assert(I != ranges.end() && "Not a valid interval!"); VNInfo *ValNo = I->valno; @@ -211,7 +216,7 @@ LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { LiveInterval::iterator LiveInterval::addRangeFrom(LiveRange LR, iterator From) { - unsigned Start = LR.start, End = LR.end; + MachineInstrIndex Start = LR.start, End = LR.end; iterator it = std::upper_bound(From, ranges.end(), Start); // If the inserted interval starts in the middle or right at the end of @@ -245,7 +250,7 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) { extendIntervalEndTo(it, End); else if (End < it->end) // Overlapping intervals, there might have been a kill here. - removeKill(it->valno, End); + it->valno->removeKill(End); return it; } } else { @@ -261,33 +266,32 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) { return ranges.insert(it, LR); } -/// isInOneLiveRange - Return true if the range specified is entirely in the +/// isInOneLiveRange - Return true if the range specified is entirely in /// a single LiveRange of the live interval. -bool LiveInterval::isInOneLiveRange(unsigned Start, unsigned End) { +bool LiveInterval::isInOneLiveRange(MachineInstrIndex Start, MachineInstrIndex End) { Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); if (I == ranges.begin()) return false; --I; - return I->contains(Start) && I->contains(End-1); + return I->containsRange(Start, End); } /// removeRange - Remove the specified range from this interval. Note that /// the range must be in a single LiveRange in its entirety. -void LiveInterval::removeRange(unsigned Start, unsigned End, +void LiveInterval::removeRange(MachineInstrIndex Start, MachineInstrIndex End, bool RemoveDeadValNo) { // Find the LiveRange containing this span. Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); assert(I != ranges.begin() && "Range is not in interval!"); --I; - assert(I->contains(Start) && I->contains(End-1) && - "Range is not entirely in interval!"); + assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); // If the span we are removing is at the start of the LiveRange, adjust it. VNInfo *ValNo = I->valno; if (I->start == Start) { if (I->end == End) { - removeKills(I->valno, Start, End); + ValNo->removeKills(Start, End); if (RemoveDeadValNo) { // Check if val# is dead. bool isDead = true; @@ -321,13 +325,13 @@ 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) { - removeKills(ValNo, Start, End); + ValNo->removeKills(Start, End); I->end = Start; return; } // Otherwise, we are splitting the LiveRange into two pieces. - unsigned OldEnd = I->end; + MachineInstrIndex OldEnd = I->end; I->end = Start; // Trim the old interval. // Insert the new one. @@ -361,11 +365,12 @@ void LiveInterval::removeValNo(VNInfo *ValNo) { /// scaleNumbering - Renumber VNI and ranges to provide gaps for new /// instructions. + void LiveInterval::scaleNumbering(unsigned factor) { // Scale ranges. for (iterator RI = begin(), RE = end(); RI != RE; ++RI) { - RI->start = InstrSlots::scale(RI->start, factor); - RI->end = InstrSlots::scale(RI->end, factor); + RI->start = RI->start.scale(factor); + RI->end = RI->end.scale(factor); } // Scale VNI info. @@ -373,20 +378,20 @@ void LiveInterval::scaleNumbering(unsigned factor) { VNInfo *vni = *VNI; if (vni->isDefAccurate()) - vni->def = InstrSlots::scale(vni->def, factor); + vni->def = vni->def.scale(factor); for (unsigned i = 0; i < vni->kills.size(); ++i) { - if (!vni->kills[i].isPHIKill) - vni->kills[i].killIdx = - InstrSlots::scale(vni->kills[i].killIdx, factor); + if (!vni->kills[i].isPHIIndex()) + vni->kills[i] = vni->kills[i].scale(factor); } } } + /// getLiveRangeContaining - Return the live range that contains the /// specified index, or null if there is none. LiveInterval::const_iterator -LiveInterval::FindLiveRangeContaining(unsigned Idx) const { +LiveInterval::FindLiveRangeContaining(MachineInstrIndex Idx) const { const_iterator It = std::upper_bound(begin(), end(), Idx); if (It != ranges.begin()) { --It; @@ -398,7 +403,7 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) const { } LiveInterval::iterator -LiveInterval::FindLiveRangeContaining(unsigned Idx) { +LiveInterval::FindLiveRangeContaining(MachineInstrIndex Idx) { iterator It = std::upper_bound(begin(), end(), Idx); if (It != begin()) { --It; @@ -409,17 +414,27 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) { return end(); } -/// findDefinedVNInfo - Find the VNInfo that's defined at the specified index -/// (register interval) or defined by the specified register (stack inteval). -VNInfo *LiveInterval::findDefinedVNInfo(unsigned DefIdxOrReg) const { - VNInfo *VNI = NULL; +/// findDefinedVNInfo - Find the VNInfo defined by the specified +/// index (register interval). +VNInfo *LiveInterval::findDefinedVNInfoForRegInt(MachineInstrIndex Idx) const { for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); - i != e; ++i) - if ((*i)->def == DefIdxOrReg) { - VNI = *i; - break; - } - return VNI; + i != e; ++i) { + if ((*i)->def == Idx) + return *i; + } + + return 0; +} + +/// findDefinedVNInfo - Find the VNInfo defined by the specified +/// register (stack inteval). +VNInfo *LiveInterval::findDefinedVNInfoForStackInt(unsigned reg) const { + for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); + i != e; ++i) { + if ((*i)->getReg() == reg) + return *i; + } + return 0; } /// join - Join two live intervals (this, and other) together. This applies @@ -546,7 +561,7 @@ void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS, for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { if (I->valno != RHSValNo) continue; - unsigned Start = I->start, End = I->end; + MachineInstrIndex Start = I->start, End = I->end; IP = std::upper_bound(IP, end(), Start); // If the start of this range overlaps with an existing liverange, trim it. if (IP != begin() && IP[-1].end > Start) { @@ -622,20 +637,21 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers, else if (UnusedValNo) ClobberValNo = UnusedValNo; else { - UnusedValNo = ClobberValNo = getNextValue(0, 0, false, VNInfoAllocator); + UnusedValNo = ClobberValNo = + getNextValue(MachineInstrIndex(), 0, false, VNInfoAllocator); ValNoMaps.insert(std::make_pair(I->valno, ClobberValNo)); } bool Done = false; - unsigned Start = I->start, End = I->end; + MachineInstrIndex Start = I->start, End = I->end; // If a clobber range starts before an existing range and ends after // it, the clobber range will need to be split into multiple ranges. // Loop until the entire clobber range is handled. while (!Done) { Done = true; IP = std::upper_bound(IP, end(), Start); - unsigned SubRangeStart = Start; - unsigned SubRangeEnd = End; + MachineInstrIndex SubRangeStart = Start; + MachineInstrIndex SubRangeEnd = End; // If the start of this range overlaps with an existing liverange, trim it. if (IP != begin() && IP[-1].end > SubRangeStart) { @@ -671,11 +687,13 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers, } } -void LiveInterval::MergeInClobberRange(unsigned Start, unsigned End, +void LiveInterval::MergeInClobberRange(MachineInstrIndex Start, + MachineInstrIndex End, BumpPtrAllocator &VNInfoAllocator) { // Find a value # to use for the clobber ranges. If there is already a value# // for unknown values, use it. - VNInfo *ClobberValNo = getNextValue(0, 0, false, VNInfoAllocator); + VNInfo *ClobberValNo = + getNextValue(MachineInstrIndex(), 0, false, VNInfoAllocator); iterator IP = begin(); IP = std::upper_bound(IP, end(), Start); @@ -788,7 +806,7 @@ void LiveInterval::Copy(const LiveInterval &RHS, unsigned LiveInterval::getSize() const { unsigned Sum = 0; for (const_iterator I = begin(), E = end(); I != E; ++I) - Sum += I->end - I->start; + Sum += I->start.distance(I->end); return Sum; } @@ -862,8 +880,8 @@ void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { if (ee || vni->hasPHIKill()) { OS << "-("; for (unsigned j = 0; j != ee; ++j) { - OS << vni->kills[j].killIdx; - if (vni->kills[j].isPHIKill) + OS << vni->kills[j]; + if (vni->kills[j].isPHIIndex()) OS << "*"; if (j != ee-1) OS << " "; diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 96afda47d5..b3e6aa7292 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -254,6 +254,7 @@ void LiveIntervals::processImplicitDefs() { } } + void LiveIntervals::computeNumbering() { Index2MiMap OldI2MI = i2miMap_; std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap; @@ -268,15 +269,16 @@ void LiveIntervals::computeNumbering() { // Number MachineInstrs and MachineBasicBlocks. // Initialize MBB indexes to a sentinal. - MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); + MBB2IdxMap.resize(mf_->getNumBlockIDs(), + std::make_pair(MachineInstrIndex(),MachineInstrIndex())); - unsigned MIIndex = 0; + MachineInstrIndex MIIndex; for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); MBB != E; ++MBB) { - unsigned StartIdx = MIIndex; + MachineInstrIndex StartIdx = MIIndex; // Insert an empty slot at the beginning of each block. - MIIndex += InstrSlots::NUM; + MIIndex = MIIndex.nextIndex(); i2miMap_.push_back(0); for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); @@ -285,47 +287,51 @@ void LiveIntervals::computeNumbering() { if (I == MBB->getFirstTerminator()) { // Leave a gap for before terminators, this is where we will point // PHI kills. + MachineInstrIndex tGap(true, MIIndex); bool inserted = - terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second; + terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second; assert(inserted && "Multiple 'first' terminators encountered during numbering."); inserted = inserted; // Avoid compiler warning if assertions turned off. i2miMap_.push_back(0); - MIIndex += InstrSlots::NUM; + MIIndex = MIIndex.nextIndex(); } bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; assert(inserted && "multiple MachineInstr -> index mappings"); inserted = true; i2miMap_.push_back(I); - MIIndex += InstrSlots::NUM; + MIIndex = MIIndex.nextIndex(); FunctionSize++; // Insert max(1, numdefs) empty slots after every instruction. unsigned Slots = I->getDesc().getNumDefs(); if (Slots == 0) Slots = 1; - MIIndex += InstrSlots::NUM * Slots; - while (Slots--) + while (Slots--) { + MIIndex = MIIndex.nextIndex(); i2miMap_.push_back(0); + } + } if (MBB->getFirstTerminator() == MBB->end()) { // Leave a gap for before terminators, this is where we will point // PHI kills. + MachineInstrIndex tGap(true, MIIndex); bool inserted = - terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second; + terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second; assert(inserted && "Multiple 'first' terminators encountered during numbering."); inserted = inserted; // Avoid compiler warning if assertions turned off. i2miMap_.push_back(0); - MIIndex += InstrSlots::NUM; + MIIndex = MIIndex.nextIndex(); } // Set the MBB2IdxMap entry for this MBB. - MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); + MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex.prevSlot()); Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); } @@ -340,9 +346,9 @@ void LiveIntervals::computeNumbering() { // number, or our best guess at what it _should_ correspond to if the // original instruction has been erased. This is either the following // instruction or its predecessor. - unsigned index = LI->start / InstrSlots::NUM; - unsigned offset = LI->start % InstrSlots::NUM; - if (offset == InstrSlots::LOAD) { + unsigned index = LI->start.getVecIndex(); + MachineInstrIndex::Slot offset = LI->start.getSlot(); + if (LI->start.isLoad()) { std::vector<IdxMBBPair>::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); // Take the pair containing the index @@ -351,29 +357,34 @@ void LiveIntervals::computeNumbering() { LI->start = getMBBStartIdx(J->second); } else { - LI->start = mi2iMap_[OldI2MI[index]] + offset; + LI->start = MachineInstrIndex( + MachineInstrIndex(mi2iMap_[OldI2MI[index]]), + (MachineInstrIndex::Slot)offset); } // Remap the ending index in the same way that we remapped the start, // except for the final step where we always map to the immediately // following instruction. - index = (LI->end - 1) / InstrSlots::NUM; - offset = LI->end % InstrSlots::NUM; - if (offset == InstrSlots::LOAD) { + index = (LI->end.prevSlot()).getVecIndex(); + offset = LI->end.getSlot(); + if (LI->end.isLoad()) { // VReg dies at end of block. std::vector<IdxMBBPair>::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); --I; - LI->end = getMBBEndIdx(I->second) + 1; + LI->end = getMBBEndIdx(I->second).nextSlot(); } else { unsigned idx = index; while (index < OldI2MI.size() && !OldI2MI[index]) ++index; if (index != OldI2MI.size()) - LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0); + LI->end = + MachineInstrIndex(mi2iMap_[OldI2MI[index]], + (idx == index ? offset : MachineInstrIndex::LOAD)); else - LI->end = InstrSlots::NUM * i2miMap_.size(); + LI->end = + MachineInstrIndex(MachineInstrIndex::NUM * i2miMap_.size()); } } @@ -385,9 +396,9 @@ void LiveIntervals::computeNumbering() { // start indices above. VN's with special sentinel defs // don't need to be remapped. if (vni->isDefAccurate() && !vni->isUnused()) { - unsigned index = vni->def / InstrSlots::NUM; - unsigned offset = vni->def % InstrSlots::NUM; - if (offset == InstrSlots::LOAD) { + unsigned index = vni->def.getVecIndex(); + MachineInstrIndex::Slot offset = vni->def.getSlot(); + if (vni->def.isLoad()) { std::vector<IdxMBBPair>::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); // Take the pair containing the index @@ -396,19 +407,17 @@ void LiveIntervals::computeNumbering() { vni->def = getMBBStartIdx(J->second); } else { - vni->def = mi2iMap_[OldI2MI[index]] + offset; + vni->def = MachineInstrIndex(mi2iMap_[OldI2MI[index]], offset); } } // Remap the VNInfo kill indices, which works the same as // the end indices above. for (size_t i = 0; i < vni->kills.size(); ++i) { - unsigned killIdx = vni->kills[i].killIdx; + unsigned index = vni->kills[i].prevSlot().getVecIndex(); + MachineInstrIndex::Slot offset = vni->kills[i].getSlot(); - unsigned index = (killIdx - 1) / InstrSlots::NUM; - unsigned offset = killIdx % InstrSlots::NUM; - - if (offset == InstrSlots::LOAD) { + if (vni->kills[i].isLoad()) { assert("Value killed at a load slot."); /*std::vector<IdxMBBPair>::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); @@ -416,15 +425,15 @@ void LiveIntervals::computeNumbering() { vni->kills[i] = getMBBEndIdx(I->second);*/ } else { - if (vni->kills[i].isPHIKill) { + if (vni->kills[i].isPHIIndex()) { std::vector<IdxMBBPair>::const_iterator I = - std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index); + std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); --I; - vni->kills[i].killIdx = terminatorGaps[I->second]; + vni->kills[i] = terminatorGaps[I->second]; } else { assert(OldI2MI[index] != 0 && "Kill refers to instruction not present in index maps."); - vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset; + vni->kills[i] = MachineInstrIndex(mi2iMap_[OldI2MI[index]], offset); } /* @@ -454,18 +463,18 @@ void LiveIntervals::scaleNumbering(int factor) { Idx2MBBMap.clear(); for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end(); MBB != MBBE; ++MBB) { - std::pair<unsigned, unsigned> &mbbIndices = MBB2IdxMap[MBB->getNumber()]; - mbbIndices.first = InstrSlots::scale(mbbIndices.first, factor); - mbbIndices.second = InstrSlots::scale(mbbIndices.second, factor); + std::pair<MachineInstrIndex, MachineInstrIndex> &mbbIndices = MBB2IdxMap[MBB->getNumber()]; + mbbIndices.first = mbbIndices.first.scale(factor); + mbbIndices.second = mbbIndices.second.scale(factor); Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); } std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); // Scale terminator gaps. - for (DenseMap<MachineBasicBlock*, unsigned>::iterator + for (DenseMap<MachineBasicBlock*, MachineInstrIndex>::iterator TGI = terminatorGaps.begin(), TGE = terminatorGaps.end(); TGI != TGE; ++TGI) { - terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor); + terminatorGaps[TGI->first] = TGI->second.scale(factor); } // Scale the intervals. @@ -475,19 +484,20 @@ void LiveIntervals::scaleNumbering(int factor) { // Scale MachineInstrs. Mi2IndexMap oldmi2iMap = mi2iMap_; - unsigned highestSlot = 0; + MachineInstrIndex highestSlot; for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end(); MI != ME; ++MI) { - unsigned newSlot = InstrSlots::scale(MI->second, factor); + MachineInstrIndex newSlot = MI->second.scale(factor); mi2iMap_[MI->first] = newSlot; highestSlot = std::max(highestSlot, newSlot); } + unsigned highestVIndex = highestSlot.getVecIndex(); i2miMap_.clear(); - i2miMap_.resize(highestSlot + 1); + i2miMap_.resize(highestVIndex + 1); for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end(); MI != ME; ++MI) { - i2miMap_[MI->second] = const_cast<MachineInstr *>(MI->first); + i2miMap_[MI->second.getVecIndex()] = const_cast<MachineInstr *>(MI->first); } } @@ -541,12 +551,12 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { - for (unsigned index = getBaseIndex(I->start), - end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; - index += InstrSlots::NUM) { + for (MachineInstrIndex index = getBaseIndex(I->start), + end = getBaseIndex(I->end.prevSlot()).nextIndex(); index != end; + index = index.nextIndex()) { // skip deleted instructions while (index != end && !getInstructionFromIndex(index)) - index += InstrSlots::NUM; + index = index.nextIndex(); if (index == end) break; MachineInstr *MI = getInstructionFromIndex(index); @@ -582,16 +592,16 @@ bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, SmallPtrSet<MachineInstr*,32> &JoinedCopies) { for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { - for (unsigned index = getBaseIndex(I->start), - end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; - index += InstrSlots::NUM) { + for (MachineInstrIndex index = getBaseIndex(I->start), + end = getBaseIndex(I->end.prevSlot()).nextIndex(); index != end; + index = index.nextIndex()) { // Skip deleted instructions. MachineInstr *MI = 0; while (index != end) { MI = getInstructionFromIndex(index); if (MI) break; - index += InstrSlots::NUM; + index = index.nextIndex(); } if (index == end) break; @@ -625,7 +635,8 @@ void LiveIntervals::printRegName(unsigned reg) const { void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineBasicBlock::iterator mi, - unsigned MIIdx, MachineOperand& MO, + MachineInstrIndex MIIdx, + MachineOperand& MO, unsigned MOIdx, LiveInterval &interval) { DEBUG({ @@ -640,7 +651,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); if (interval.empty()) { // Get the Idx of the defining instructions. - unsigned defIndex = getDefIndex(MIIdx); + MachineInstrIndex defIndex = getDefIndex(MIIdx); // Earlyclobbers move back one. if (MO.isEarlyClobber()) defIndex = getUseIndex(MIIdx); @@ -663,11 +674,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // will be a single kill, in MBB, which comes after the definition. if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { // FIXME: what about dead vars? - unsigned killIdx; + MachineInstrIndex killIdx; if (vi.Kills[0] != mi) - killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; + killIdx = getUseIndex(getInstructionIndex(vi.Kills[0])).nextSlot(); else - killIdx = defIndex+1; + killIdx = defIndex.nextSlot(); // If the kill happens after the definition, we have an intra-block // live range. @@ -677,7 +688,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, LiveRange LR(defIndex, killIdx, ValNo); interval.addRange(LR); DEBUG(errs() << " +" << LR << "\n"); - interval.addKill(ValNo, killIdx, false); + ValNo->addKill(killIdx); return; } } @@ -686,7 +697,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // of the defining block, potentially live across some blocks, then is // live into some number of blocks, but gets killed. Start by adding a // range that goes from this definition to the end of the defining block. - LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo); + LiveRange NewLR(defIndex, getMBBEndIdx(mbb).nextSlot(), ValNo); DEBUG(errs() << " +" << NewLR); interval.addRange(NewLR); @@ -696,7 +707,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), E = vi.AliveBlocks.end(); I != E; ++I) { LiveRange LR(getMBBStartIdx(*I), - getMBBEndIdx(*I)+1, // MBB ends at -1. + getMBBEndIdx(*I).nextSlot(), // MBB ends at -1. ValNo); interval.addRange(LR); DEBUG(errs() << " +" << LR); @@ -706,11 +717,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // block to the 'use' slot of the killing instruction. for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { MachineInstr *Kill = vi.Kills[i]; - unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; + MachineInstrIndex killIdx = getUseIndex(getInstructionIndex(Kill)).nextSlot(); LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); interval.addRange(LR); - interval.addKill(ValNo, killIdx, false); + ValNo->addKill(killIdx); DEBUG(errs() << " +" << LR); } @@ -726,12 +737,12 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // need to take the LiveRegion that defines this register and split it // into two values. assert(interval.containsOneValue()); - unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); - unsigned RedefIndex = getDefIndex(MIIdx); + MachineInstrIndex DefIndex = getDefIndex(interval.getValNumInfo(0)->def); + MachineInstrIndex RedefIndex = getDefIndex(MIIdx); if (MO.isEarlyClobber()) RedefIndex = getUseIndex(MIIdx); - const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); + const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex.prevSlot()); VNInfo *OldValNo = OldLR->valno; // Delete the initial value, which should be short and continuous, @@ -759,12 +770,12 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, LiveRange LR(DefIndex, RedefIndex, ValNo); DEBUG(errs() << " replace range with " << LR); interval.addRange(LR); - interval.addKill(ValNo, RedefIndex, false); + ValNo->addKill(RedefIndex); // If this redefinition is dead, we need to add a dummy unit live // range covering the def slot. if (MO.isDead()) - interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); + interval.addRange(LiveRange(RedefIndex, RedefIndex.nextSlot(), OldValNo)); DEBUG({ errs() << " RESULT: "; @@ -781,8 +792,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Remove the old range that we now know has an incorrect number. VNInfo *VNI = interval.getValNumInfo(0); MachineInstr *Killer = vi.Kills[0]; - unsigned Start = getMBBStartIdx(Killer->getParent()); - unsigned End = getUseIndex(getInstructionIndex(Killer))+1; + MachineInstrIndex Start = getMBBStartIdx(Killer->getParent()); + MachineInstrIndex End = getUseIndex(getInstructionIndex(Killer)).nextSlot(); DEBUG({ errs() << " Removing [" << Start << "," << End << "] from: "; interval.print(errs(), tri_); @@ -791,8 +802,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, interval.removeRange(Start, End); assert(interval.ranges.size() == 1 && "newly discovered PHI interval has >1 ranges."); - MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber()); - interval.addKill(VNI, terminatorGaps[killMBB], true); + MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); + VNI->addKill(terminatorGaps[killMBB]); VNI->setHasPHIKill(true); DEBUG({ errs() << " RESULT: "; @@ -802,11 +813,12 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Replace the interval with one of a NEW value number. Note that this // value number isn't actually defined by an instruction, weird huh? :) LiveRange LR(Start, End, - interval.getNextValue(mbb->getNumber(), 0, false, VNInfoAllocator)); + interval.getNextValue(MachineInstrIndex(mbb->getNumber()), + 0, false, VNInfoAllocator)); LR.valno->setIsPHIDef(true); DEBUG(errs() << " replace range with " << LR); interval.addRange(LR); - interval.addKill(LR.valno, End, false); + LR.valno->addKill(End); DEBUG({ errs() << " RESULT: "; interval.print(errs(), tri_); @@ -816,7 +828,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // In the case of PHI elimination, each variable definition is only // live until the end of the block. We've already taken care of the // rest of the live range. - unsigned defIndex = getDefIndex(MIIdx); + MachineInstrIndex defIndex = getDefIndex(MIIdx); if (MO.isEarlyClobber()) defIndex = getUseIndex(MIIdx); @@ -830,10 +842,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, CopyMI = mi; ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); - unsigned killIndex = getMBBEndIdx(mbb) + 1; + MachineInstrIndex killIndex = getMBBEndIdx(mbb).nextSlot(); LiveRange LR(defIndex, killIndex, ValNo); interval.addRange(LR); - interval.addKill(ValNo, terminatorGaps[mbb], true); + ValNo->addKill(terminatorGaps[mbb]); ValNo->setHasPHIKill(true); DEBUG(errs() << " +" << LR); } @@ -844,7 +856,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi, - unsigned MIIdx, + MachineInstrIndex MIIdx, MachineOperand& MO, LiveInterval &interval, MachineInstr *CopyMI) { @@ -855,33 +867,33 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, printRegName(interval.reg); }); - unsigned baseIndex = MIIdx; - unsigned start = getDefIndex(baseIndex); + MachineInstrIndex baseIndex = MIIdx; + MachineInstrIndex start = getDefIndex(baseIndex); // Earlyclobbers move back one. if (MO.isEarlyClobber()) start = getUseIndex(MIIdx); - unsigned end = start; + MachineInstrIndex end = start; // If it is not used after definition, it is considered dead at // the instruction defining it. Hence its interval is: // [defSlot(def), defSlot(def)+1) if (MO.isDead()) { DEBUG(errs() << " dead"); - end = start + 1; + end = start.nextSlot(); goto exit; } // If it is not dead on definition, it must be killed by a // subsequent instruction. Hence its interval is: // [defSlot(def), useSlot(kill)+1) - baseIndex += InstrSlots::NUM; + baseIndex = baseIndex.nextIndex(); while (++mi != MBB->end()) { - while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + while (baseIndex.getVecIndex() < i2miMap_.size() && getInstructionFromIndex(baseIndex) == 0) - baseIndex += InstrSlots::NUM; + baseIndex = baseIndex.nextIndex(); if (mi->killsRegister(interval.reg, tri_)) { DEBUG(errs() << " killed"); - end = getUseIndex(baseIndex) + 1; + end = getUseIndex(baseIndex).nextSlot(); goto exit; } else { int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); @@ -897,20 +909,20 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *M |