X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSlotIndexes.cpp;h=6a7666e8e25f54270730b9113aaede829ec5e99d;hb=d782bae970e888572f0458ac05369bbd7752f05a;hp=f3ad0d1cc0a7251bffdce7c4ec5d5ab812bd04b0;hpb=0368e500eb7f5f03313e1a7af5b8fa48465c0560;p=oota-llvm.git diff --git a/lib/CodeGen/SlotIndexes.cpp b/lib/CodeGen/SlotIndexes.cpp index f3ad0d1cc0a..6a7666e8e25 100644 --- a/lib/CodeGen/SlotIndexes.cpp +++ b/lib/CodeGen/SlotIndexes.cpp @@ -10,17 +10,20 @@ #define DEBUG_TYPE "slotindexes" #include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" using namespace llvm; -std::auto_ptr IndexListEntry::emptyKeyEntry, - IndexListEntry::tombstoneKeyEntry; - char SlotIndexes::ID = 0; -static RegisterPass X("slotindexes", "Slot index numbering"); +INITIALIZE_PASS(SlotIndexes, "slotindexes", + "Slot index numbering", false, false) + +STATISTIC(NumLocalRenum, "Number of local renumberings"); +STATISTIC(NumGlobalRenum, "Number of global renumberings"); void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const { au.setPreservesAll(); @@ -29,9 +32,8 @@ void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const { void SlotIndexes::releaseMemory() { mi2iMap.clear(); - mbb2IdxMap.clear(); + MBBRanges.clear(); idx2MBBMap.clear(); - terminatorGaps.clear(); clearList(); } @@ -51,84 +53,56 @@ bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) { mf = &fn; initList(); - const unsigned gap = 1; - // Check that the list contains only the sentinal. assert(indexListHead->getNext() == 0 && "Index list non-empty at initial numbering?"); assert(idx2MBBMap.empty() && "Index -> MBB mapping non-empty at initial numbering?"); - assert(mbb2IdxMap.empty() && + assert(MBBRanges.empty() && "MBB -> Index mapping non-empty at initial numbering?"); assert(mi2iMap.empty() && "MachineInstr -> Index mapping non-empty at initial numbering?"); functionSize = 0; - /* - for (unsigned s = 0; s < SlotIndex::NUM; ++s) { - indexList.push_back(createEntry(0, s)); - } - - unsigned index = gap * SlotIndex::NUM; - */ - unsigned index = 0; + MBBRanges.resize(mf->getNumBlockIDs()); + idx2MBBMap.reserve(mf->size()); + + push_back(createEntry(0, index)); - // Iterate over the the function. + // Iterate over the function. for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end(); mbbItr != mbbEnd; ++mbbItr) { MachineBasicBlock *mbb = &*mbbItr; // Insert an index for the MBB start. - push_back(createEntry(0, index)); - SlotIndex blockStartIndex(back(), SlotIndex::LOAD); - - index += gap * SlotIndex::NUM; + SlotIndex blockStartIndex(back(), SlotIndex::Slot_Block); for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end(); miItr != miEnd; ++miItr) { - MachineInstr *mi = &*miItr; - - if (miItr == mbb->getFirstTerminator()) { - push_back(createEntry(0, index)); - terminatorGaps.insert( - std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT))); - index += gap * SlotIndex::NUM; - } + MachineInstr *mi = miItr; + if (mi->isDebugValue()) + continue; // Insert a store index for the instr. - push_back(createEntry(mi, index)); + push_back(createEntry(mi, index += SlotIndex::InstrDist)); // Save this base index in the maps. - mi2iMap.insert( - std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD))); + mi2iMap.insert(std::make_pair(mi, SlotIndex(back(), + SlotIndex::Slot_Block))); ++functionSize; - - unsigned Slots = mi->getDesc().getNumDefs(); - if (Slots == 0) - Slots = 1; - - index += (Slots + 1) * gap * SlotIndex::NUM; } - if (mbb->getFirstTerminator() == mbb->end()) { - push_back(createEntry(0, index)); - terminatorGaps.insert( - std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT))); - index += gap * SlotIndex::NUM; - } - - SlotIndex blockEndIndex(back(), SlotIndex::STORE); - mbb2IdxMap.insert( - std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex))); + // We insert one blank instructions between basic blocks. + push_back(createEntry(0, index += SlotIndex::InstrDist)); + MBBRanges[mbb->getNumber()].first = blockStartIndex; + MBBRanges[mbb->getNumber()].second = SlotIndex(back(), + SlotIndex::Slot_Block); idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); } - // One blank instruction at the end. - push_back(createEntry(0, index)); - // Sort the Idx2MBBMap std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); @@ -138,52 +112,70 @@ bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) { return false; } -void SlotIndexes::renumber() { - assert(false && "SlotIndexes::runmuber is not fully implemented yet."); +void SlotIndexes::renumberIndexes() { + // Renumber updates the index of every element of the index list. + DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); + ++NumGlobalRenum; - // Compute numbering as follows: - // Grab an iterator to the start of the index list. - // Iterate over all MBBs, and within each MBB all MIs, keeping the MI - // iterator in lock-step (though skipping it over indexes which have - // null pointers in the instruction field). - // At each iteration assert that the instruction pointed to in the index - // is the same one pointed to by the MI iterator. This + unsigned index = 0; - // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should - // only need to be set up once - when the first numbering is computed. + for (IndexListEntry *curEntry = front(); curEntry != getTail(); + curEntry = curEntry->getNext()) { + curEntry->setIndex(index); + index += SlotIndex::InstrDist; + } +} - assert(false && "Renumbering not supported yet."); +// Renumber indexes locally after curEntry was inserted, but failed to get a new +// index. +void SlotIndexes::renumberIndexes(IndexListEntry *curEntry) { + // Number indexes with half the default spacing so we can catch up quickly. + const unsigned Space = SlotIndex::InstrDist/2; + assert((Space & 3) == 0 && "InstrDist must be a multiple of 2*NUM"); + + IndexListEntry *start = curEntry->getPrev(); + unsigned index = start->getIndex(); + IndexListEntry *tail = getTail(); + do { + curEntry->setIndex(index += Space); + curEntry = curEntry->getNext(); + // If the next index is bigger, we have caught up. + } while (curEntry != tail && curEntry->getIndex() <= index); + + DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << start->getIndex() << '-' + << index << " ***\n"); + ++NumLocalRenum; } + void SlotIndexes::dump() const { for (const IndexListEntry *itr = front(); itr != getTail(); itr = itr->getNext()) { - errs() << itr->getIndex() << " "; + dbgs() << itr->getIndex() << " "; if (itr->getInstr() != 0) { - errs() << *itr->getInstr(); + dbgs() << *itr->getInstr(); } else { - errs() << "\n"; + dbgs() << "\n"; } } - for (MBB2IdxMap::iterator itr = mbb2IdxMap.begin(); - itr != mbb2IdxMap.end(); ++itr) { - errs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - [" - << itr->second.first << ", " << itr->second.second << "]\n"; - } + for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i) + dbgs() << "BB#" << i << "\t[" << MBBRanges[i].first << ';' + << MBBRanges[i].second << ")\n"; } // Print a SlotIndex to a raw_ostream. void SlotIndex::print(raw_ostream &os) const { - os << getIndex(); - if (isPHI()) - os << "*"; + if (isValid()) + os << entry().getIndex() << "Berd"[getSlot()]; + else + os << "invalid"; } // Dump a SlotIndex to stderr. void SlotIndex::dump() const { - print(errs()); - errs() << "\n"; + print(dbgs()); + dbgs() << "\n"; }