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/Config/llvm-config.h" 14 #include "llvm/Support/Debug.h" 15 #include "llvm/Support/raw_ostream.h" 16 17 using namespace llvm; 18 19 #define DEBUG_TYPE "slotindexes" 20 21 char SlotIndexes::ID = 0; 22 INITIALIZE_PASS(SlotIndexes, DEBUG_TYPE, 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.isDebugInstr()) 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 llvm::sort(idx2MBBMap, Idx2MBBCompare()); 99 100 LLVM_DEBUG(mf->print(dbgs(), this)); 101 102 // And we're done! 103 return false; 104 } 105 106 void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI) { 107 assert(!MI.isBundledWithPred() && 108 "Use removeSingleMachineInstrFromMaps() instread"); 109 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI); 110 if (mi2iItr == mi2iMap.end()) 111 return; 112 113 SlotIndex MIIndex = mi2iItr->second; 114 IndexListEntry &MIEntry = *MIIndex.listEntry(); 115 assert(MIEntry.getInstr() == &MI && "Instruction indexes broken."); 116 mi2iMap.erase(mi2iItr); 117 // FIXME: Eventually we want to actually delete these indexes. 118 MIEntry.setInstr(nullptr); 119 } 120 121 void SlotIndexes::removeSingleMachineInstrFromMaps(MachineInstr &MI) { 122 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI); 123 if (mi2iItr == mi2iMap.end()) 124 return; 125 126 SlotIndex MIIndex = mi2iItr->second; 127 IndexListEntry &MIEntry = *MIIndex.listEntry(); 128 assert(MIEntry.getInstr() == &MI && "Instruction indexes broken."); 129 mi2iMap.erase(mi2iItr); 130 131 // When removing the first instruction of a bundle update mapping to next 132 // instruction. 133 if (MI.isBundledWithSucc()) { 134 // Only the first instruction of a bundle should have an index assigned. 135 assert(!MI.isBundledWithPred() && "Should have first bundle isntruction"); 136 137 MachineBasicBlock::instr_iterator Next = std::next(MI.getIterator()); 138 MachineInstr &NextMI = *Next; 139 MIEntry.setInstr(&NextMI); 140 mi2iMap.insert(std::make_pair(&NextMI, MIIndex)); 141 return; 142 } else { 143 // FIXME: Eventually we want to actually delete these indexes. 144 MIEntry.setInstr(nullptr); 145 } 146 } 147 148 void SlotIndexes::renumberIndexes() { 149 // Renumber updates the index of every element of the index list. 150 LLVM_DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); 151 ++NumGlobalRenum; 152 153 unsigned index = 0; 154 155 for (IndexList::iterator I = indexList.begin(), E = indexList.end(); 156 I != E; ++I) { 157 I->setIndex(index); 158 index += SlotIndex::InstrDist; 159 } 160 } 161 162 // Renumber indexes locally after curItr was inserted, but failed to get a new 163 // index. 164 void SlotIndexes::renumberIndexes(IndexList::iterator curItr) { 165 // Number indexes with half the default spacing so we can catch up quickly. 166 const unsigned Space = SlotIndex::InstrDist/2; 167 static_assert((Space & 3) == 0, "InstrDist must be a multiple of 2*NUM"); 168 169 IndexList::iterator startItr = std::prev(curItr); 170 unsigned index = startItr->getIndex(); 171 do { 172 curItr->setIndex(index += Space); 173 ++curItr; 174 // If the next index is bigger, we have caught up. 175 } while (curItr != indexList.end() && curItr->getIndex() <= index); 176 177 LLVM_DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex() 178 << '-' << index << " ***\n"); 179 ++NumLocalRenum; 180 } 181 182 // Repair indexes after adding and removing instructions. 183 void SlotIndexes::repairIndexesInRange(MachineBasicBlock *MBB, 184 MachineBasicBlock::iterator Begin, 185 MachineBasicBlock::iterator End) { 186 // FIXME: Is this really necessary? The only caller repairIntervalsForRange() 187 // does the same thing. 188 // Find anchor points, which are at the beginning/end of blocks or at 189 // instructions that already have indexes. 190 while (Begin != MBB->begin() && !hasIndex(*Begin)) 191 --Begin; 192 while (End != MBB->end() && !hasIndex(*End)) 193 ++End; 194 195 bool includeStart = (Begin == MBB->begin()); 196 SlotIndex startIdx; 197 if (includeStart) 198 startIdx = getMBBStartIdx(MBB); 199 else 200 startIdx = getInstructionIndex(*Begin); 201 202 SlotIndex endIdx; 203 if (End == MBB->end()) 204 endIdx = getMBBEndIdx(MBB); 205 else 206 endIdx = getInstructionIndex(*End); 207 208 // FIXME: Conceptually, this code is implementing an iterator on MBB that 209 // optionally includes an additional position prior to MBB->begin(), indicated 210 // by the includeStart flag. This is done so that we can iterate MIs in a MBB 211 // in parallel with SlotIndexes, but there should be a better way to do this. 212 IndexList::iterator ListB = startIdx.listEntry()->getIterator(); 213 IndexList::iterator ListI = endIdx.listEntry()->getIterator(); 214 MachineBasicBlock::iterator MBBI = End; 215 bool pastStart = false; 216 while (ListI != ListB || MBBI != Begin || (includeStart && !pastStart)) { 217 assert(ListI->getIndex() >= startIdx.getIndex() && 218 (includeStart || !pastStart) && 219 "Decremented past the beginning of region to repair."); 220 221 MachineInstr *SlotMI = ListI->getInstr(); 222 MachineInstr *MI = (MBBI != MBB->end() && !pastStart) ? &*MBBI : nullptr; 223 bool MBBIAtBegin = MBBI == Begin && (!includeStart || pastStart); 224 225 if (SlotMI == MI && !MBBIAtBegin) { 226 --ListI; 227 if (MBBI != Begin) 228 --MBBI; 229 else 230 pastStart = true; 231 } else if (MI && mi2iMap.find(MI) == mi2iMap.end()) { 232 if (MBBI != Begin) 233 --MBBI; 234 else 235 pastStart = true; 236 } else { 237 --ListI; 238 if (SlotMI) 239 removeMachineInstrFromMaps(*SlotMI); 240 } 241 } 242 243 // In theory this could be combined with the previous loop, but it is tricky 244 // to update the IndexList while we are iterating it. 245 for (MachineBasicBlock::iterator I = End; I != Begin;) { 246 --I; 247 MachineInstr &MI = *I; 248 if (!MI.isDebugInstr() && mi2iMap.find(&MI) == mi2iMap.end()) 249 insertMachineInstrInMaps(MI); 250 } 251 } 252 253 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 254 LLVM_DUMP_METHOD void SlotIndexes::dump() const { 255 for (IndexList::const_iterator itr = indexList.begin(); 256 itr != indexList.end(); ++itr) { 257 dbgs() << itr->getIndex() << " "; 258 259 if (itr->getInstr()) { 260 dbgs() << *itr->getInstr(); 261 } else { 262 dbgs() << "\n"; 263 } 264 } 265 266 for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i) 267 dbgs() << "%bb." << i << "\t[" << MBBRanges[i].first << ';' 268 << MBBRanges[i].second << ")\n"; 269 } 270 #endif 271 272 // Print a SlotIndex to a raw_ostream. 273 void SlotIndex::print(raw_ostream &os) const { 274 if (isValid()) 275 os << listEntry()->getIndex() << "Berd"[getSlot()]; 276 else 277 os << "invalid"; 278 } 279 280 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 281 // Dump a SlotIndex to stderr. 282 LLVM_DUMP_METHOD void SlotIndex::dump() const { 283 print(dbgs()); 284 dbgs() << "\n"; 285 } 286 #endif 287 288