SlotIndexes.cpp revision 1ce6a36610f06a1fb4047ddde1e9bc2f071c0bfb
1//===-- SlotIndexes.cpp - Slot Indexes Pass ------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#define DEBUG_TYPE "slotindexes" 11 12#include "llvm/CodeGen/SlotIndexes.h" 13#include "llvm/ADT/Statistic.h" 14#include "llvm/CodeGen/MachineFunction.h" 15#include "llvm/Support/Debug.h" 16#include "llvm/Support/raw_ostream.h" 17#include "llvm/Target/TargetInstrInfo.h" 18 19using namespace llvm; 20 21char SlotIndexes::ID = 0; 22INITIALIZE_PASS(SlotIndexes, "slotindexes", 23 "Slot index numbering", false, false) 24 25STATISTIC(NumLocalRenum, "Number of local renumberings"); 26STATISTIC(NumGlobalRenum, "Number of global renumberings"); 27 28void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const { 29 au.setPreservesAll(); 30 MachineFunctionPass::getAnalysisUsage(au); 31} 32 33void SlotIndexes::releaseMemory() { 34 mi2iMap.clear(); 35 MBBRanges.clear(); 36 idx2MBBMap.clear(); 37 clearList(); 38} 39 40bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) { 41 42 // Compute numbering as follows: 43 // Grab an iterator to the start of the index list. 44 // Iterate over all MBBs, and within each MBB all MIs, keeping the MI 45 // iterator in lock-step (though skipping it over indexes which have 46 // null pointers in the instruction field). 47 // At each iteration assert that the instruction pointed to in the index 48 // is the same one pointed to by the MI iterator. This 49 50 // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should 51 // only need to be set up once after the first numbering is computed. 52 53 mf = &fn; 54 initList(); 55 56 // Check that the list contains only the sentinal. 57 assert(indexListHead->getNext() == 0 && 58 "Index list non-empty at initial numbering?"); 59 assert(idx2MBBMap.empty() && 60 "Index -> MBB mapping non-empty at initial numbering?"); 61 assert(MBBRanges.empty() && 62 "MBB -> Index mapping non-empty at initial numbering?"); 63 assert(mi2iMap.empty() && 64 "MachineInstr -> Index mapping non-empty at initial numbering?"); 65 66 functionSize = 0; 67 unsigned index = 0; 68 MBBRanges.resize(mf->getNumBlockIDs()); 69 idx2MBBMap.reserve(mf->size()); 70 71 push_back(createEntry(0, index)); 72 73 // Iterate over the function. 74 for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end(); 75 mbbItr != mbbEnd; ++mbbItr) { 76 MachineBasicBlock *mbb = &*mbbItr; 77 78 // Insert an index for the MBB start. 79 SlotIndex blockStartIndex(back(), SlotIndex::Slot_Block); 80 81 for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end(); 82 miItr != miEnd; ++miItr) { 83 MachineInstr *mi = miItr; 84 if (mi->isDebugValue()) 85 continue; 86 87 // Insert a store index for the instr. 88 push_back(createEntry(mi, index += SlotIndex::InstrDist)); 89 90 // Save this base index in the maps. 91 mi2iMap.insert(std::make_pair(mi, SlotIndex(back(), 92 SlotIndex::Slot_Block))); 93 94 ++functionSize; 95 } 96 97 // We insert one blank instructions between basic blocks. 98 push_back(createEntry(0, index += SlotIndex::InstrDist)); 99 100 MBBRanges[mbb->getNumber()].first = blockStartIndex; 101 MBBRanges[mbb->getNumber()].second = SlotIndex(back(), 102 SlotIndex::Slot_Block); 103 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); 104 } 105 106 // Sort the Idx2MBBMap 107 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 108 109 DEBUG(mf->print(dbgs(), this)); 110 111 // And we're done! 112 return false; 113} 114 115void SlotIndexes::renumberIndexes() { 116 // Renumber updates the index of every element of the index list. 117 DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); 118 ++NumGlobalRenum; 119 120 unsigned index = 0; 121 122 for (IndexListEntry *curEntry = front(); curEntry != getTail(); 123 curEntry = curEntry->getNext()) { 124 curEntry->setIndex(index); 125 index += SlotIndex::InstrDist; 126 } 127} 128 129// Renumber indexes locally after curEntry was inserted, but failed to get a new 130// index. 131void SlotIndexes::renumberIndexes(IndexListEntry *curEntry) { 132 // Number indexes with half the default spacing so we can catch up quickly. 133 const unsigned Space = SlotIndex::InstrDist/2; 134 assert((Space & 3) == 0 && "InstrDist must be a multiple of 2*NUM"); 135 136 IndexListEntry *start = curEntry->getPrev(); 137 unsigned index = start->getIndex(); 138 IndexListEntry *tail = getTail(); 139 do { 140 curEntry->setIndex(index += Space); 141 curEntry = curEntry->getNext(); 142 // If the next index is bigger, we have caught up. 143 } while (curEntry != tail && curEntry->getIndex() <= index); 144 145 DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << start->getIndex() << '-' 146 << index << " ***\n"); 147 ++NumLocalRenum; 148} 149 150 151void SlotIndexes::dump() const { 152 for (const IndexListEntry *itr = front(); itr != getTail(); 153 itr = itr->getNext()) { 154 dbgs() << itr->getIndex() << " "; 155 156 if (itr->getInstr() != 0) { 157 dbgs() << *itr->getInstr(); 158 } else { 159 dbgs() << "\n"; 160 } 161 } 162 163 for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i) 164 dbgs() << "BB#" << i << "\t[" << MBBRanges[i].first << ';' 165 << MBBRanges[i].second << ")\n"; 166} 167 168// Print a SlotIndex to a raw_ostream. 169void SlotIndex::print(raw_ostream &os) const { 170 if (isValid()) 171 os << entry().getIndex() << "Berd"[getSlot()]; 172 else 173 os << "invalid"; 174} 175 176// Dump a SlotIndex to stderr. 177void SlotIndex::dump() const { 178 print(dbgs()); 179 dbgs() << "\n"; 180} 181 182