llvm/lib/CodeGen/SlotIndexes.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-exception
   6 //
   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
  17 using namespace llvm;
  18
  19 #define DEBUG_TYPE "slotindexes"
  20
  21 AnalysisKey SlotIndexesAnalysis::Key;
  22
  23 SlotIndexesAnalysis::Result
  24 SlotIndexesAnalysis::run(MachineFunction &MF,
  25                          MachineFunctionAnalysisManager &) {
  26   return Result(MF);
  27 }
  28
  29 PreservedAnalyses
  30 SlotIndexesPrinterPass::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 }
  36 char SlotIndexesWrapperPass::ID = 0;
  37
  38 SlotIndexesWrapperPass::SlotIndexesWrapperPass() : MachineFunctionPass(ID) {
  39   initializeSlotIndexesWrapperPassPass(*PassRegistry::getPassRegistry());
  40 }
  41
  42 SlotIndexes::~SlotIndexes() {
  43   // The indexList's nodes are all allocated in the BumpPtrAllocator.
  44   indexList.clear();
  45 }
  46
  47 INITIALIZE_PASS(SlotIndexesWrapperPass, DEBUG_TYPE, "Slot index numbering",
  48                 false, false)
  49
  50 STATISTIC(NumLocalRenum,  "Number of local renumberings");
  51
  52 void SlotIndexesWrapperPass::getAnalysisUsage(AnalysisUsage &au) const {
  53   au.setPreservesAll();
  54   MachineFunctionPass::getAnalysisUsage(au);
  55 }
  56
  57 void SlotIndexes::clear() {
  58   mi2iMap.clear();
  59   MBBRanges.clear();
  60   idx2MBBMap.clear();
  61   indexList.clear();
  62   ileAllocator.Reset();
  63 }
  64
  65 void 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 MI
  70   // iterator in lock-step (though skipping it over indexes which have
  71   // null pointers in the instruction field).
  72   // At each iteration assert that the instruction pointed to in the index
  73   // is the same one pointed to by the MI iterator. This
  74
  75   // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
  76   // 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 Idx2MBBMap
 122   llvm::sort(idx2MBBMap, less_first());
 123
 124   LLVM_DEBUG(mf->print(dbgs(), this));
 125 }
 126
 127 void 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
 143 void 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 next
 154   // 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 new
 171 // index.
 172 void 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.
 191 void 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   else
 199     startIdx = getInstructionIndex(*--Begin);
 200
 201   SlotIndex endIdx;
 202   if (End == MBB->end())
 203     endIdx = getMBBEndIdx(MBB);
 204   else
 205     endIdx = getInstructionIndex(*End);
 206
 207   // FIXME: Conceptually, this code is implementing an iterator on MBB that
 208   // optionally includes an additional position prior to MBB->begin(), indicated
 209   // by the includeStart flag. This is done so that we can iterate MIs in a MBB
 210   // 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   while (ListI != ListB || MBBI != Begin || (includeStart && !pastStart)) {
 216     assert(ListI->getIndex() >= startIdx.getIndex() &&
 217            (includeStart || !pastStart) &&
 218            "Decremented past the beginning of region to repair.");
 219
 220     MachineInstr *SlotMI = ListI->getInstr();
 221     MachineInstr *MI = (MBBI != MBB->end() && !pastStart) ? &*MBBI : nullptr;
 222     bool MBBIAtBegin = MBBI == Begin && (!includeStart || pastStart);
 223
 224     if (SlotMI == MI && !MBBIAtBegin) {
 225       --ListI;
 226       if (MBBI != Begin)
 227         --MBBI;
 228       else
 229         pastStart = true;
 230     } else if (MI && !mi2iMap.contains(MI)) {
 231       if (MBBI != Begin)
 232         --MBBI;
 233       else
 234         pastStart = true;
 235     } else {
 236       --ListI;
 237       if (SlotMI)
 238         removeMachineInstrFromMaps(*SlotMI);
 239     }
 240   }
 241
 242   // In theory this could be combined with the previous loop, but it is tricky
 243   // to update the IndexList while we are iterating it.
 244   for (MachineBasicBlock::iterator I = End; I != Begin;) {
 245     --I;
 246     MachineInstr &MI = *I;
 247     if (!MI.isDebugOrPseudoInstr() && !mi2iMap.contains(&MI))
 248       insertMachineInstrInMaps(MI);
 249   }
 250 }
 251
 252 void SlotIndexes::packIndexes() {
 253   for (auto [Index, Entry] : enumerate(indexList))
 254     Entry.setIndex(Index * SlotIndex::InstrDist);
 255 }
 256
 257 void SlotIndexes::print(raw_ostream &OS) const {
 258   for (const IndexListEntry &ILE : indexList) {
 259     OS << ILE.getIndex() << ' ';
 260
 261     if (ILE.getInstr())
 262       OS << *ILE.getInstr();
 263     else
 264       OS << '\n';
 265   }
 266
 267   for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i)
 268     OS << "%bb." << i << "\t[" << MBBRanges[i].first << ';'
 269        << MBBRanges[i].second << ")\n";
 270 }
 271
 272 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 273 LLVM_DUMP_METHOD void SlotIndexes::dump() const { print(dbgs()); }
 274 #endif
 275
 276 // Print a SlotIndex to a raw_ostream.
 277 void SlotIndex::print(raw_ostream &os) const {
 278   if (isValid())
 279     os << listEntry()->getIndex() << "Berd"[getSlot()];
 280   else
 281     os << "invalid";
 282 }
 283
 284 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 285 // Dump a SlotIndex to stderr.
 286 LLVM_DUMP_METHOD void SlotIndex::dump() const {
 287   print(dbgs());
 288   dbgs() << "\n";
 289 }
 290 #endif