SlotIndexes.cpp revision 16dcaf59960d699735a57b1623092d561c18a165
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#include "llvm/Support/ManagedStatic.h" 17 18using namespace llvm; 19 20 21// Yep - these are thread safe. See the header for details. 22namespace { 23 24 25 class EmptyIndexListEntry : public IndexListEntry { 26 public: 27 EmptyIndexListEntry() : IndexListEntry(EMPTY_KEY) {} 28 }; 29 30 class TombstoneIndexListEntry : public IndexListEntry { 31 public: 32 TombstoneIndexListEntry() : IndexListEntry(TOMBSTONE_KEY) {} 33 }; 34 35 // The following statics are thread safe. They're read only, and you 36 // can't step from them to any other list entries. 37 ManagedStatic<EmptyIndexListEntry> IndexListEntryEmptyKey; 38 ManagedStatic<TombstoneIndexListEntry> IndexListEntryTombstoneKey; 39} 40 41char SlotIndexes::ID = 0; 42static RegisterPass<SlotIndexes> X("slotindexes", "Slot index numbering"); 43 44IndexListEntry* IndexListEntry::getEmptyKeyEntry() { 45 return &*IndexListEntryEmptyKey; 46} 47 48IndexListEntry* IndexListEntry::getTombstoneKeyEntry() { 49 return &*IndexListEntryTombstoneKey; 50} 51 52 53void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const { 54 au.setPreservesAll(); 55 MachineFunctionPass::getAnalysisUsage(au); 56} 57 58void SlotIndexes::releaseMemory() { 59 mi2iMap.clear(); 60 mbb2IdxMap.clear(); 61 idx2MBBMap.clear(); 62 terminatorGaps.clear(); 63 clearList(); 64} 65 66bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) { 67 68 // Compute numbering as follows: 69 // Grab an iterator to the start of the index list. 70 // Iterate over all MBBs, and within each MBB all MIs, keeping the MI 71 // iterator in lock-step (though skipping it over indexes which have 72 // null pointers in the instruction field). 73 // At each iteration assert that the instruction pointed to in the index 74 // is the same one pointed to by the MI iterator. This 75 76 // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should 77 // only need to be set up once after the first numbering is computed. 78 79 mf = &fn; 80 initList(); 81 82 // Check that the list contains only the sentinal. 83 assert(indexListHead->getNext() == 0 && 84 "Index list non-empty at initial numbering?"); 85 assert(idx2MBBMap.empty() && 86 "Index -> MBB mapping non-empty at initial numbering?"); 87 assert(mbb2IdxMap.empty() && 88 "MBB -> Index mapping non-empty at initial numbering?"); 89 assert(mi2iMap.empty() && 90 "MachineInstr -> Index mapping non-empty at initial numbering?"); 91 92 functionSize = 0; 93 unsigned index = 0; 94 95 // Iterate over the the function. 96 for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end(); 97 mbbItr != mbbEnd; ++mbbItr) { 98 MachineBasicBlock *mbb = &*mbbItr; 99 100 // Insert an index for the MBB start. 101 push_back(createEntry(0, index)); 102 SlotIndex blockStartIndex(back(), SlotIndex::LOAD); 103 104 index += SlotIndex::NUM; 105 106 for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end(); 107 miItr != miEnd; ++miItr) { 108 MachineInstr *mi = &*miItr; 109 110 if (miItr == mbb->getFirstTerminator()) { 111 push_back(createEntry(0, index)); 112 terminatorGaps.insert( 113 std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT))); 114 index += SlotIndex::NUM; 115 } 116 117 // Insert a store index for the instr. 118 push_back(createEntry(mi, index)); 119 120 // Save this base index in the maps. 121 mi2iMap.insert( 122 std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD))); 123 124 ++functionSize; 125 126 unsigned Slots = mi->getDesc().getNumDefs(); 127 if (Slots == 0) 128 Slots = 1; 129 130 index += (Slots + 1) * SlotIndex::NUM; 131 } 132 133 if (mbb->getFirstTerminator() == mbb->end()) { 134 push_back(createEntry(0, index)); 135 terminatorGaps.insert( 136 std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT))); 137 index += SlotIndex::NUM; 138 } 139 140 SlotIndex blockEndIndex(back(), SlotIndex::STORE); 141 mbb2IdxMap.insert( 142 std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex))); 143 144 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); 145 } 146 147 // One blank instruction at the end. 148 push_back(createEntry(0, index)); 149 150 // Sort the Idx2MBBMap 151 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 152 153 DEBUG(dump()); 154 155 // And we're done! 156 return false; 157} 158 159void SlotIndexes::renumber() { 160 161 // Renumber updates the index of every element of the index list. 162 // If all instrs in the function have been allocated an index (which has been 163 // placed in the index list in the order of instruction iteration) then the 164 // resulting numbering will match what would have been generated by the 165 // pass during the initial numbering of the function if the new instructions 166 // had been present. 167 168 functionSize = 0; 169 unsigned index = 0; 170 171 for (IndexListEntry *curEntry = front(); curEntry != getTail(); 172 curEntry = curEntry->getNext()) { 173 174 curEntry->setIndex(index); 175 176 if (curEntry->getInstr() == 0) { 177 // MBB start entry or terminator gap. Just step index by 1. 178 index += SlotIndex::NUM; 179 } 180 else { 181 ++functionSize; 182 unsigned Slots = curEntry->getInstr()->getDesc().getNumDefs(); 183 if (Slots == 0) 184 Slots = 1; 185 186 index += (Slots + 1) * SlotIndex::NUM; 187 188 } 189 } 190} 191 192void SlotIndexes::dump() const { 193 for (const IndexListEntry *itr = front(); itr != getTail(); 194 itr = itr->getNext()) { 195 errs() << itr->getIndex() << " "; 196 197 if (itr->getInstr() != 0) { 198 errs() << *itr->getInstr(); 199 } else { 200 errs() << "\n"; 201 } 202 } 203 204 for (MBB2IdxMap::iterator itr = mbb2IdxMap.begin(); 205 itr != mbb2IdxMap.end(); ++itr) { 206 errs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - [" 207 << itr->second.first << ", " << itr->second.second << "]\n"; 208 } 209} 210 211// Print a SlotIndex to a raw_ostream. 212void SlotIndex::print(raw_ostream &os) const { 213 os << getIndex(); 214 if (isPHI()) 215 os << "*"; 216} 217 218// Dump a SlotIndex to stderr. 219void SlotIndex::dump() const { 220 print(errs()); 221 errs() << "\n"; 222} 223 224