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 functionSize = 0; 66 unsigned index = 0; 67 MBBRanges.resize(mf->getNumBlockIDs()); 68 idx2MBBMap.reserve(mf->size()); 69 70 indexList.push_back(createEntry(0, index)); 71 72 // Iterate over the function. 73 for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end(); 74 mbbItr != mbbEnd; ++mbbItr) { 75 MachineBasicBlock *mbb = &*mbbItr; 76 77 // Insert an index for the MBB start. 78 SlotIndex blockStartIndex(&indexList.back(), SlotIndex::Slot_Block); 79 80 for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end(); 81 miItr != miEnd; ++miItr) { 82 MachineInstr *mi = miItr; 83 if (mi->isDebugValue()) 84 continue; 85 86 // Insert a store index for the instr. 87 indexList.push_back(createEntry(mi, index += SlotIndex::InstrDist)); 88 89 // Save this base index in the maps. 90 mi2iMap.insert(std::make_pair(mi, SlotIndex(&indexList.back(), 91 SlotIndex::Slot_Block))); 92 93 ++functionSize; 94 } 95 96 // We insert one blank instructions between basic blocks. 97 indexList.push_back(createEntry(0, index += SlotIndex::InstrDist)); 98 99 MBBRanges[mbb->getNumber()].first = blockStartIndex; 100 MBBRanges[mbb->getNumber()].second = SlotIndex(&indexList.back(), 101 SlotIndex::Slot_Block); 102 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); 103 } 104 105 // Sort the Idx2MBBMap 106 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 107 108 DEBUG(mf->print(dbgs(), this)); 109 110 // And we're done! 111 return false; 112 } 113 114 void SlotIndexes::renumberIndexes() { 115 // Renumber updates the index of every element of the index list. 116 DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); 117 ++NumGlobalRenum; 118 119 unsigned index = 0; 120 121 for (IndexList::iterator I = indexList.begin(), E = indexList.end(); 122 I != E; ++I) { 123 I->setIndex(index); 124 index += SlotIndex::InstrDist; 125 } 126 } 127 128 // Renumber indexes locally after curItr was inserted, but failed to get a new 129 // index. 130 void SlotIndexes::renumberIndexes(IndexList::iterator curItr) { 131 // Number indexes with half the default spacing so we can catch up quickly. 132 const unsigned Space = SlotIndex::InstrDist/2; 133 assert((Space & 3) == 0 && "InstrDist must be a multiple of 2*NUM"); 134 135 IndexList::iterator startItr = prior(curItr); 136 unsigned index = startItr->getIndex(); 137 do { 138 curItr->setIndex(index += Space); 139 ++curItr; 140 // If the next index is bigger, we have caught up. 141 } while (curItr != indexList.end() && curItr->getIndex() <= index); 142 143 DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex() << '-' 144 << index << " ***\n"); 145 ++NumLocalRenum; 146 } 147 148 149 void SlotIndexes::dump() const { 150 for (IndexList::const_iterator itr = indexList.begin(); 151 itr != indexList.end(); ++itr) { 152 dbgs() << itr->getIndex() << " "; 153 154 if (itr->getInstr() != 0) { 155 dbgs() << *itr->getInstr(); 156 } else { 157 dbgs() << "\n"; 158 } 159 } 160 161 for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i) 162 dbgs() << "BB#" << i << "\t[" << MBBRanges[i].first << ';' 163 << MBBRanges[i].second << ")\n"; 164 } 165 166 // Print a SlotIndex to a raw_ostream. 167 void SlotIndex::print(raw_ostream &os) const { 168 if (isValid()) 169 os << listEntry()->getIndex() << "Berd"[getSlot()]; 170 else 171 os << "invalid"; 172 } 173 174 // Dump a SlotIndex to stderr. 175 void SlotIndex::dump() const { 176 print(dbgs()); 177 dbgs() << "\n"; 178 } 179 180
