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 #include "llvm/CodeGen/SlotIndexes.h" 11 #include "llvm/ADT/Statistic.h" 12 #include "llvm/CodeGen/MachineFunction.h" 13 #include "llvm/Support/Debug.h" 14 #include "llvm/Support/raw_ostream.h" 15 #include "llvm/Target/TargetInstrInfo.h" 16 17 using namespace llvm; 18 19 #define DEBUG_TYPE "slotindexes" 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(nullptr, index)); 70 71 // Iterate over the function. 72 for (MachineBasicBlock &MBB : *mf) { 73 // Insert an index for the MBB start. 74 SlotIndex blockStartIndex(&indexList.back(), SlotIndex::Slot_Block); 75 76 for (MachineInstr &MI : MBB) { 77 if (MI.isDebugValue()) 78 continue; 79 80 // Insert a store index for the instr. 81 indexList.push_back(createEntry(&MI, index += SlotIndex::InstrDist)); 82 83 // Save this base index in the maps. 84 mi2iMap.insert(std::make_pair( 85 &MI, SlotIndex(&indexList.back(), SlotIndex::Slot_Block))); 86 } 87 88 // We insert one blank instructions between basic blocks. 89 indexList.push_back(createEntry(nullptr, index += SlotIndex::InstrDist)); 90 91 MBBRanges[MBB.getNumber()].first = blockStartIndex; 92 MBBRanges[MBB.getNumber()].second = SlotIndex(&indexList.back(), 93 SlotIndex::Slot_Block); 94 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, &MBB)); 95 } 96 97 // Sort the Idx2MBBMap 98 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 99 100 DEBUG(mf->print(dbgs(), this)); 101 102 // And we're done! 103 return false; 104 } 105 106 void SlotIndexes::renumberIndexes() { 107 // Renumber updates the index of every element of the index list. 108 DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); 109 ++NumGlobalRenum; 110 111 unsigned index = 0; 112 113 for (IndexList::iterator I = indexList.begin(), E = indexList.end(); 114 I != E; ++I) { 115 I->setIndex(index); 116 index += SlotIndex::InstrDist; 117 } 118 } 119 120 // Renumber indexes locally after curItr was inserted, but failed to get a new 121 // index. 122 void SlotIndexes::renumberIndexes(IndexList::iterator curItr) { 123 // Number indexes with half the default spacing so we can catch up quickly. 124 const unsigned Space = SlotIndex::InstrDist/2; 125 static_assert((Space & 3) == 0, "InstrDist must be a multiple of 2*NUM"); 126 127 IndexList::iterator startItr = std::prev(curItr); 128 unsigned index = startItr->getIndex(); 129 do { 130 curItr->setIndex(index += Space); 131 ++curItr; 132 // If the next index is bigger, we have caught up. 133 } while (curItr != indexList.end() && curItr->getIndex() <= index); 134 135 DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex() << '-' 136 << index << " ***\n"); 137 ++NumLocalRenum; 138 } 139 140 // Repair indexes after adding and removing instructions. 141 void SlotIndexes::repairIndexesInRange(MachineBasicBlock *MBB, 142 MachineBasicBlock::iterator Begin, 143 MachineBasicBlock::iterator End) { 144 // FIXME: Is this really necessary? The only caller repairIntervalsForRange() 145 // does the same thing. 146 // Find anchor points, which are at the beginning/end of blocks or at 147 // instructions that already have indexes. 148 while (Begin != MBB->begin() && !hasIndex(*Begin)) 149 --Begin; 150 while (End != MBB->end() && !hasIndex(*End)) 151 ++End; 152 153 bool includeStart = (Begin == MBB->begin()); 154 SlotIndex startIdx; 155 if (includeStart) 156 startIdx = getMBBStartIdx(MBB); 157 else 158 startIdx = getInstructionIndex(*Begin); 159 160 SlotIndex endIdx; 161 if (End == MBB->end()) 162 endIdx = getMBBEndIdx(MBB); 163 else 164 endIdx = getInstructionIndex(*End); 165 166 // FIXME: Conceptually, this code is implementing an iterator on MBB that 167 // optionally includes an additional position prior to MBB->begin(), indicated 168 // by the includeStart flag. This is done so that we can iterate MIs in a MBB 169 // in parallel with SlotIndexes, but there should be a better way to do this. 170 IndexList::iterator ListB = startIdx.listEntry()->getIterator(); 171 IndexList::iterator ListI = endIdx.listEntry()->getIterator(); 172 MachineBasicBlock::iterator MBBI = End; 173 bool pastStart = false; 174 while (ListI != ListB || MBBI != Begin || (includeStart && !pastStart)) { 175 assert(ListI->getIndex() >= startIdx.getIndex() && 176 (includeStart || !pastStart) && 177 "Decremented past the beginning of region to repair."); 178 179 MachineInstr *SlotMI = ListI->getInstr(); 180 MachineInstr *MI = (MBBI != MBB->end() && !pastStart) ? &*MBBI : nullptr; 181 bool MBBIAtBegin = MBBI == Begin && (!includeStart || pastStart); 182 183 if (SlotMI == MI && !MBBIAtBegin) { 184 --ListI; 185 if (MBBI != Begin) 186 --MBBI; 187 else 188 pastStart = true; 189 } else if (MI && mi2iMap.find(MI) == mi2iMap.end()) { 190 if (MBBI != Begin) 191 --MBBI; 192 else 193 pastStart = true; 194 } else { 195 --ListI; 196 if (SlotMI) 197 removeMachineInstrFromMaps(*SlotMI); 198 } 199 } 200 201 // In theory this could be combined with the previous loop, but it is tricky 202 // to update the IndexList while we are iterating it. 203 for (MachineBasicBlock::iterator I = End; I != Begin;) { 204 --I; 205 MachineInstr &MI = *I; 206 if (!MI.isDebugValue() && mi2iMap.find(&MI) == mi2iMap.end()) 207 insertMachineInstrInMaps(MI); 208 } 209 } 210 211 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 212 LLVM_DUMP_METHOD void SlotIndexes::dump() const { 213 for (IndexList::const_iterator itr = indexList.begin(); 214 itr != indexList.end(); ++itr) { 215 dbgs() << itr->getIndex() << " "; 216 217 if (itr->getInstr()) { 218 dbgs() << *itr->getInstr(); 219 } else { 220 dbgs() << "\n"; 221 } 222 } 223 224 for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i) 225 dbgs() << "BB#" << i << "\t[" << MBBRanges[i].first << ';' 226 << MBBRanges[i].second << ")\n"; 227 } 228 #endif 229 230 // Print a SlotIndex to a raw_ostream. 231 void SlotIndex::print(raw_ostream &os) const { 232 if (isValid()) 233 os << listEntry()->getIndex() << "Berd"[getSlot()]; 234 else 235 os << "invalid"; 236 } 237 238 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 239 // Dump a SlotIndex to stderr. 240 LLVM_DUMP_METHOD void SlotIndex::dump() const { 241 print(dbgs()); 242 dbgs() << "\n"; 243 } 244 #endif 245 246