lib/CodeGen/SlotIndexes.cpp

   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/CodeGen/MachineFunction.h"
  14 #include "llvm/Support/Debug.h"
  15 #include "llvm/Support/raw_ostream.h"
  16
  17 using namespace llvm;
  18
  19
  20 // Yep - these are thread safe. See the header for details.
  21 ManagedStatic<EmptyIndexListEntry> IndexListEntry::emptyKeyEntry;
  22 ManagedStatic<TombstoneIndexListEntry> IndexListEntry::tombstoneKeyEntry;
  23
  24 char SlotIndexes::ID = 0;
  25 static RegisterPass<SlotIndexes> X("slotindexes", "Slot index numbering");
  26
  27 void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const {
  28   au.setPreservesAll();
  29   MachineFunctionPass::getAnalysisUsage(au);
  30 }
  31
  32 void SlotIndexes::releaseMemory() {
  33   mi2iMap.clear();
  34   mbb2IdxMap.clear();
  35   idx2MBBMap.clear();
  36   terminatorGaps.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(mbb2IdxMap.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
  69   // Iterate over the the function.
  70   for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end();
  71        mbbItr != mbbEnd; ++mbbItr) {
  72     MachineBasicBlock *mbb = &*mbbItr;
  73
  74     // Insert an index for the MBB start.
  75     push_back(createEntry(0, index));
  76     SlotIndex blockStartIndex(back(), SlotIndex::LOAD);
  77
  78     index += SlotIndex::NUM;
  79
  80     for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end();
  81          miItr != miEnd; ++miItr) {
  82       MachineInstr *mi = &*miItr;
  83
  84       if (miItr == mbb->getFirstTerminator()) {
  85         push_back(createEntry(0, index));
  86         terminatorGaps.insert(
  87           std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT)));
  88         index += SlotIndex::NUM;
  89       }
  90
  91       // Insert a store index for the instr.
  92       push_back(createEntry(mi, index));
  93
  94       // Save this base index in the maps.
  95       mi2iMap.insert(
  96         std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD)));
  97
  98       ++functionSize;
  99
 100       unsigned Slots = mi->getDesc().getNumDefs();
 101       if (Slots == 0)
 102         Slots = 1;
 103
 104       index += (Slots + 1) * SlotIndex::NUM;
 105     }
 106
 107     if (mbb->getFirstTerminator() == mbb->end()) {
 108       push_back(createEntry(0, index));
 109       terminatorGaps.insert(
 110         std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT)));
 111       index += SlotIndex::NUM;
 112     }
 113
 114     SlotIndex blockEndIndex(back(), SlotIndex::STORE);
 115     mbb2IdxMap.insert(
 116       std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex)));
 117
 118     idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb));
 119   }
 120
 121   // One blank instruction at the end.
 122   push_back(createEntry(0, index));
 123
 124   // Sort the Idx2MBBMap
 125   std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
 126
 127   DEBUG(dump());
 128
 129   // And we're done!
 130   return false;
 131 }
 132
 133 void SlotIndexes::renumber() {
 134
 135   // Renumber updates the index of every element of the index list.
 136   // If all instrs in the function have been allocated an index (which has been
 137   // placed in the index list in the order of instruction iteration) then the
 138   // resulting numbering will match what would have been generated by the
 139   // pass during the initial numbering of the function if the new instructions
 140   // had been present.
 141
 142   functionSize = 0;
 143   unsigned index = 0;
 144
 145   for (IndexListEntry *curEntry = front(); curEntry != getTail();
 146        curEntry = curEntry->getNext()) {
 147
 148     curEntry->setIndex(index);
 149
 150     if (curEntry->getInstr() == 0) {
 151       // MBB start entry or terminator gap. Just step index by 1.
 152       index += SlotIndex::NUM;
 153     }
 154     else {
 155       ++functionSize;
 156       unsigned Slots = curEntry->getInstr()->getDesc().getNumDefs();
 157       if (Slots == 0)
 158         Slots = 1;
 159
 160       index += (Slots + 1) * SlotIndex::NUM;
 161
 162     }
 163   }
 164 }
 165
 166 void SlotIndexes::dump() const {
 167   for (const IndexListEntry *itr = front(); itr != getTail();
 168        itr = itr->getNext()) {
 169     errs() << itr->getIndex() << " ";
 170
 171     if (itr->getInstr() != 0) {
 172       errs() << *itr->getInstr();
 173     } else {
 174       errs() << "\n";
 175     }
 176   }
 177
 178   for (MBB2IdxMap::iterator itr = mbb2IdxMap.begin();
 179        itr != mbb2IdxMap.end(); ++itr) {
 180     errs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - ["
 181            << itr->second.first << ", " << itr->second.second << "]\n";
 182   }
 183 }
 184
 185 // Print a SlotIndex to a raw_ostream.
 186 void SlotIndex::print(raw_ostream &os) const {
 187   os << getIndex();
 188   if (isPHI())
 189     os << "*";
 190 }
 191
 192 // Dump a SlotIndex to stderr.
 193 void SlotIndex::dump() const {
 194   print(errs());
 195   errs() << "\n";
 196 }
 197