300 lines · cpp
1//===-- SlotIndexes.cpp - Slot Indexes Pass ------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/CodeGen/SlotIndexes.h"10#include "llvm/ADT/Statistic.h"11#include "llvm/CodeGen/MachineFunction.h"12#include "llvm/Config/llvm-config.h"13#include "llvm/InitializePasses.h"14#include "llvm/Support/Debug.h"15#include "llvm/Support/raw_ostream.h"16 17using namespace llvm;18 19#define DEBUG_TYPE "slotindexes"20 21AnalysisKey SlotIndexesAnalysis::Key;22 23SlotIndexesAnalysis::Result24SlotIndexesAnalysis::run(MachineFunction &MF,25 MachineFunctionAnalysisManager &) {26 return Result(MF);27}28 29PreservedAnalyses30SlotIndexesPrinterPass::run(MachineFunction &MF,31 MachineFunctionAnalysisManager &MFAM) {32 OS << "Slot indexes in machine function: " << MF.getName() << '\n';33 MFAM.getResult<SlotIndexesAnalysis>(MF).print(OS);34 return PreservedAnalyses::all();35}36char SlotIndexesWrapperPass::ID = 0;37 38SlotIndexesWrapperPass::SlotIndexesWrapperPass() : MachineFunctionPass(ID) {39 initializeSlotIndexesWrapperPassPass(*PassRegistry::getPassRegistry());40}41 42SlotIndexes::~SlotIndexes() {43 // The indexList's nodes are all allocated in the BumpPtrAllocator.44 indexList.clear();45}46 47INITIALIZE_PASS(SlotIndexesWrapperPass, DEBUG_TYPE, "Slot index numbering",48 false, false)49 50STATISTIC(NumLocalRenum, "Number of local renumberings");51 52void SlotIndexesWrapperPass::getAnalysisUsage(AnalysisUsage &au) const {53 au.setPreservesAll();54 MachineFunctionPass::getAnalysisUsage(au);55}56 57void SlotIndexes::clear() {58 mi2iMap.clear();59 MBBRanges.clear();60 idx2MBBMap.clear();61 indexList.clear();62 ileAllocator.Reset();63}64 65void SlotIndexes::analyze(MachineFunction &fn) {66 67 // Compute numbering as follows:68 // Grab an iterator to the start of the index list.69 // Iterate over all MBBs, and within each MBB all MIs, keeping the MI70 // iterator in lock-step (though skipping it over indexes which have71 // null pointers in the instruction field).72 // At each iteration assert that the instruction pointed to in the index73 // is the same one pointed to by the MI iterator. This74 75 // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should76 // only need to be set up once after the first numbering is computed.77 78 mf = &fn;79 80 // Check that the list contains only the sentinel.81 assert(indexList.empty() && "Index list non-empty at initial numbering?");82 assert(idx2MBBMap.empty() &&83 "Index -> MBB mapping non-empty at initial numbering?");84 assert(MBBRanges.empty() &&85 "MBB -> Index mapping non-empty at initial numbering?");86 assert(mi2iMap.empty() &&87 "MachineInstr -> Index mapping non-empty at initial numbering?");88 89 unsigned index = 0;90 MBBRanges.resize(mf->getNumBlockIDs());91 idx2MBBMap.reserve(mf->size());92 93 indexList.push_back(*createEntry(nullptr, index));94 95 // Iterate over the function.96 for (MachineBasicBlock &MBB : *mf) {97 // Insert an index for the MBB start.98 SlotIndex blockStartIndex(&indexList.back(), SlotIndex::Slot_Block);99 100 for (MachineInstr &MI : MBB) {101 if (MI.isDebugOrPseudoInstr())102 continue;103 104 // Insert a store index for the instr.105 indexList.push_back(*createEntry(&MI, index += SlotIndex::InstrDist));106 107 // Save this base index in the maps.108 mi2iMap.insert(std::make_pair(109 &MI, SlotIndex(&indexList.back(), SlotIndex::Slot_Block)));110 }111 112 // We insert one blank instructions between basic blocks.113 indexList.push_back(*createEntry(nullptr, index += SlotIndex::InstrDist));114 115 MBBRanges[MBB.getNumber()].first = blockStartIndex;116 MBBRanges[MBB.getNumber()].second = SlotIndex(&indexList.back(),117 SlotIndex::Slot_Block);118 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, &MBB));119 }120 121 // Sort the Idx2MBBMap122 llvm::sort(idx2MBBMap, less_first());123 124 LLVM_DEBUG(mf->print(dbgs(), this));125}126 127void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI,128 bool AllowBundled) {129 assert((AllowBundled || !MI.isBundledWithPred()) &&130 "Use removeSingleMachineInstrFromMaps() instead");131 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);132 if (mi2iItr == mi2iMap.end())133 return;134 135 SlotIndex MIIndex = mi2iItr->second;136 IndexListEntry &MIEntry = *MIIndex.listEntry();137 assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");138 mi2iMap.erase(mi2iItr);139 // FIXME: Eventually we want to actually delete these indexes.140 MIEntry.setInstr(nullptr);141}142 143void SlotIndexes::removeSingleMachineInstrFromMaps(MachineInstr &MI) {144 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);145 if (mi2iItr == mi2iMap.end())146 return;147 148 SlotIndex MIIndex = mi2iItr->second;149 IndexListEntry &MIEntry = *MIIndex.listEntry();150 assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");151 mi2iMap.erase(mi2iItr);152 153 // When removing the first instruction of a bundle update mapping to next154 // instruction.155 if (MI.isBundledWithSucc()) {156 // Only the first instruction of a bundle should have an index assigned.157 assert(!MI.isBundledWithPred() && "Should be first bundle instruction");158 159 MachineBasicBlock::instr_iterator Next = std::next(MI.getIterator());160 MachineInstr &NextMI = *Next;161 MIEntry.setInstr(&NextMI);162 mi2iMap.insert(std::make_pair(&NextMI, MIIndex));163 return;164 } else {165 // FIXME: Eventually we want to actually delete these indexes.166 MIEntry.setInstr(nullptr);167 }168}169 170// Renumber indexes locally after curItr was inserted, but failed to get a new171// index.172void SlotIndexes::renumberIndexes(IndexList::iterator curItr) {173 // Number indexes with half the default spacing so we can catch up quickly.174 const unsigned Space = SlotIndex::InstrDist/2;175 static_assert((Space & 3) == 0, "InstrDist must be a multiple of 2*NUM");176 177 IndexList::iterator startItr = std::prev(curItr);178 unsigned index = startItr->getIndex();179 do {180 curItr->setIndex(index += Space);181 ++curItr;182 // If the next index is bigger, we have caught up.183 } while (curItr != indexList.end() && curItr->getIndex() <= index);184 185 LLVM_DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex()186 << '-' << index << " ***\n");187 ++NumLocalRenum;188}189 190// Repair indexes after adding and removing instructions.191void SlotIndexes::repairIndexesInRange(MachineBasicBlock *MBB,192 MachineBasicBlock::iterator Begin,193 MachineBasicBlock::iterator End) {194 bool includeStart = (Begin == MBB->begin());195 SlotIndex startIdx;196 if (includeStart)197 startIdx = getMBBStartIdx(MBB);198 else199 startIdx = getInstructionIndex(*--Begin);200 201 SlotIndex endIdx;202 if (End == MBB->end())203 endIdx = getMBBEndIdx(MBB);204 else205 endIdx = getInstructionIndex(*End);206 207 // FIXME: Conceptually, this code is implementing an iterator on MBB that208 // optionally includes an additional position prior to MBB->begin(), indicated209 // by the includeStart flag. This is done so that we can iterate MIs in a MBB210 // in parallel with SlotIndexes, but there should be a better way to do this.211 IndexList::iterator ListB = startIdx.listEntry()->getIterator();212 IndexList::iterator ListI = endIdx.listEntry()->getIterator();213 MachineBasicBlock::iterator MBBI = End;214 bool pastStart = false;215 bool OldIndexesRemoved = 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 bool MIIndexNotFound = MI && !mi2iMap.contains(MI);225 bool SlotMIRemoved = false;226 227 if (SlotMI == MI && !MBBIAtBegin) {228 --ListI;229 if (MBBI != Begin)230 --MBBI;231 else232 pastStart = true;233 } else if (MIIndexNotFound || OldIndexesRemoved) {234 if (MBBI != Begin)235 --MBBI;236 else237 pastStart = true;238 } else {239 // We ran through all the indexes on the interval240 // -> The only thing left is to go through all the241 // remaining MBB instructions and update their indexes242 if (ListI == ListB)243 OldIndexesRemoved = true;244 else245 --ListI;246 if (SlotMI) {247 removeMachineInstrFromMaps(*SlotMI);248 SlotMIRemoved = true;249 }250 }251 252 MachineInstr *InstrToInsert = SlotMIRemoved ? SlotMI : MI;253 254 // Insert instruction back into the maps after passing it/removing the index255 if ((MIIndexNotFound || SlotMIRemoved) && InstrToInsert->getParent() &&256 !InstrToInsert->isDebugOrPseudoInstr())257 insertMachineInstrInMaps(*InstrToInsert);258 }259}260 261void SlotIndexes::packIndexes() {262 for (auto [Index, Entry] : enumerate(indexList))263 Entry.setIndex(Index * SlotIndex::InstrDist);264}265 266void SlotIndexes::print(raw_ostream &OS) const {267 for (const IndexListEntry &ILE : indexList) {268 OS << ILE.getIndex() << ' ';269 270 if (ILE.getInstr())271 OS << *ILE.getInstr();272 else273 OS << '\n';274 }275 276 for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i)277 OS << "%bb." << i << "\t[" << MBBRanges[i].first << ';'278 << MBBRanges[i].second << ")\n";279}280 281#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)282LLVM_DUMP_METHOD void SlotIndexes::dump() const { print(dbgs()); }283#endif284 285// Print a SlotIndex to a raw_ostream.286void SlotIndex::print(raw_ostream &os) const {287 if (isValid())288 os << listEntry()->getIndex() << "Berd"[getSlot()];289 else290 os << "invalid";291}292 293#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)294// Dump a SlotIndex to stderr.295LLVM_DUMP_METHOD void SlotIndex::dump() const {296 print(dbgs());297 dbgs() << "\n";298}299#endif300