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