SlotIndexes.cpp revision d6a717cba117dae9a90a373698f691d9452c9c49
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 17using namespace llvm; 18 19std::auto_ptr<IndexListEntry> SlotIndex::emptyKeyPtr(0), 20 SlotIndex::tombstoneKeyPtr(0); 21 22char SlotIndexes::ID = 0; 23static RegisterPass<SlotIndexes> X("slotindexes", "Slot index numbering"); 24 25void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const { 26 au.setPreservesAll(); 27 MachineFunctionPass::getAnalysisUsage(au); 28} 29 30void SlotIndexes::releaseMemory() { 31 mi2iMap.clear(); 32 mbb2IdxMap.clear(); 33 idx2MBBMap.clear(); 34 terminatorGaps.clear(); 35 clearList(); 36} 37 38bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) { 39 40 // Compute numbering as follows: 41 // Grab an iterator to the start of the index list. 42 // Iterate over all MBBs, and within each MBB all MIs, keeping the MI 43 // iterator in lock-step (though skipping it over indexes which have 44 // null pointers in the instruction field). 45 // At each iteration assert that the instruction pointed to in the index 46 // is the same one pointed to by the MI iterator. This 47 48 // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should 49 // only need to be set up once after the first numbering is computed. 50 51 mf = &fn; 52 initList(); 53 54 const unsigned gap = 1; 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 /* 68 for (unsigned s = 0; s < SlotIndex::NUM; ++s) { 69 indexList.push_back(createEntry(0, s)); 70 } 71 72 unsigned index = gap * SlotIndex::NUM; 73 */ 74 75 unsigned index = 0; 76 77 // Iterate over the the function. 78 for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end(); 79 mbbItr != mbbEnd; ++mbbItr) { 80 MachineBasicBlock *mbb = &*mbbItr; 81 82 // Insert an index for the MBB start. 83 push_back(createEntry(0, index)); 84 SlotIndex blockStartIndex(back(), SlotIndex::LOAD); 85 86 index += gap * SlotIndex::NUM; 87 88 for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end(); 89 miItr != miEnd; ++miItr) { 90 MachineInstr *mi = &*miItr; 91 92 if (miItr == mbb->getFirstTerminator()) { 93 push_back(createEntry(0, index)); 94 terminatorGaps.insert( 95 std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT))); 96 index += gap * SlotIndex::NUM; 97 } 98 99 // Insert a store index for the instr. 100 push_back(createEntry(mi, index)); 101 102 // Save this base index in the maps. 103 mi2iMap.insert( 104 std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD))); 105 106 ++functionSize; 107 108 unsigned Slots = mi->getDesc().getNumDefs(); 109 if (Slots == 0) 110 Slots = 1; 111 112 index += (Slots + 1) * gap * SlotIndex::NUM; 113 } 114 115 if (mbb->getFirstTerminator() == mbb->end()) { 116 push_back(createEntry(0, index)); 117 terminatorGaps.insert( 118 std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT))); 119 index += gap * SlotIndex::NUM; 120 } 121 122 SlotIndex blockEndIndex(back(), SlotIndex::STORE); 123 mbb2IdxMap.insert( 124 std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex))); 125 126 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); 127 } 128 129 // One blank instruction at the end. 130 push_back(createEntry(0, index)); 131 132 // Sort the Idx2MBBMap 133 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 134 135 DEBUG(dump()); 136 137 // And we're done! 138 return false; 139} 140 141void SlotIndexes::renumber() { 142 assert(false && "SlotIndexes::runmuber is not fully implemented yet."); 143 144 // Compute numbering as follows: 145 // Grab an iterator to the start of the index list. 146 // Iterate over all MBBs, and within each MBB all MIs, keeping the MI 147 // iterator in lock-step (though skipping it over indexes which have 148 // null pointers in the instruction field). 149 // At each iteration assert that the instruction pointed to in the index 150 // is the same one pointed to by the MI iterator. This 151 152 // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should 153 // only need to be set up once - when the first numbering is computed. 154 155 assert(false && "Renumbering not supported yet."); 156} 157 158void SlotIndexes::dump() const { 159 for (const IndexListEntry *itr = front(); itr != getTail(); 160 itr = itr->getNext()) { 161 errs() << itr->getIndex() << " "; 162 163 if (itr->getInstr() != 0) { 164 errs() << *itr->getInstr(); 165 } else { 166 errs() << "\n"; 167 } 168 } 169 170 for (MBB2IdxMap::iterator itr = mbb2IdxMap.begin(); 171 itr != mbb2IdxMap.end(); ++itr) { 172 errs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - [" 173 << itr->second.first << ", " << itr->second.second << "]\n"; 174 } 175} 176 177// Print a SlotIndex to a raw_ostream. 178void SlotIndex::print(raw_ostream &os) const { 179 os << getIndex(); 180 if (isPHI()) 181 os << "*"; 182} 183 184// Dump a SlotIndex to stderr. 185void SlotIndex::dump() const { 186 print(errs()); 187 errs() << "\n"; 188} 189 190