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 clearList(); 38 } 39 40 bool 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::LOAD); 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(), SlotIndex::LOAD))); 92 93 ++functionSize; 94 } 95 96 // We insert one blank instructions between basic blocks. 97 push_back(createEntry(0, index += SlotIndex::InstrDist)); 98 99 MBBRanges[mbb->getNumber()].first = blockStartIndex; 100 MBBRanges[mbb->getNumber()].second = SlotIndex(back(), SlotIndex::LOAD); 101 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); 102 } 103 104 // Sort the Idx2MBBMap 105 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 106 107 DEBUG(dump()); 108 109 // And we're done! 110 return false; 111 } 112 113 void SlotIndexes::renumberIndexes() { 114 // Renumber updates the index of every element of the index list. 115 DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); 116 ++NumGlobalRenum; 117 118 unsigned index = 0; 119 120 for (IndexListEntry *curEntry = front(); curEntry != getTail(); 121 curEntry = curEntry->getNext()) { 122 curEntry->setIndex(index); 123 index += SlotIndex::InstrDist; 124 } 125 } 126 127 // Renumber indexes locally after curEntry was inserted, but failed to get a new 128 // index. 129 void SlotIndexes::renumberIndexes(IndexListEntry *curEntry) { 130 // Number indexes with half the default spacing so we can catch up quickly. 131 const unsigned Space = SlotIndex::InstrDist/2; 132 assert((Space & 3) == 0 && "InstrDist must be a multiple of 2*NUM"); 133 134 IndexListEntry *start = curEntry->getPrev(); 135 unsigned index = start->getIndex(); 136 IndexListEntry *tail = getTail(); 137 do { 138 curEntry->setIndex(index += Space); 139 curEntry = curEntry->getNext(); 140 // If the next index is bigger, we have caught up. 141 } while (curEntry != tail && curEntry->getIndex() <= index); 142 143 DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << start->getIndex() << '-' 144 << index << " ***\n"); 145 ++NumLocalRenum; 146 } 147 148 149 void SlotIndexes::dump() const { 150 for (const IndexListEntry *itr = front(); itr != getTail(); 151 itr = itr->getNext()) { 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 << entry().getIndex() << "LudS"[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
