SlotIndexes.cpp revision 97af98678cc943050cf23951a66c89e922cf21c4
1233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames//===-- SlotIndexes.cpp - Slot Indexes Pass ------------------------------===// 2233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 3233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// The LLVM Compiler Infrastructure 4233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 5233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// This file is distributed under the University of Illinois Open Source 6233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// License. See LICENSE.TXT for details. 7233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 8233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames//===----------------------------------------------------------------------===// 9233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 10233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#define DEBUG_TYPE "slotindexes" 11233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 12233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/SlotIndexes.h" 13233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/MachineFunction.h" 14233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Support/Debug.h" 15233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Support/raw_ostream.h" 1616dcaf59960d699735a57b1623092d561c18a165Lang Hames#include "llvm/Support/ManagedStatic.h" 171caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen#include "llvm/Target/TargetInstrInfo.h" 18233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 19233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesusing namespace llvm; 20233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 21d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames 22d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames// Yep - these are thread safe. See the header for details. 2316dcaf59960d699735a57b1623092d561c18a165Lang Hamesnamespace { 2416dcaf59960d699735a57b1623092d561c18a165Lang Hames 2516dcaf59960d699735a57b1623092d561c18a165Lang Hames 2616dcaf59960d699735a57b1623092d561c18a165Lang Hames class EmptyIndexListEntry : public IndexListEntry { 2716dcaf59960d699735a57b1623092d561c18a165Lang Hames public: 2816dcaf59960d699735a57b1623092d561c18a165Lang Hames EmptyIndexListEntry() : IndexListEntry(EMPTY_KEY) {} 2916dcaf59960d699735a57b1623092d561c18a165Lang Hames }; 3016dcaf59960d699735a57b1623092d561c18a165Lang Hames 3116dcaf59960d699735a57b1623092d561c18a165Lang Hames class TombstoneIndexListEntry : public IndexListEntry { 3216dcaf59960d699735a57b1623092d561c18a165Lang Hames public: 3316dcaf59960d699735a57b1623092d561c18a165Lang Hames TombstoneIndexListEntry() : IndexListEntry(TOMBSTONE_KEY) {} 3416dcaf59960d699735a57b1623092d561c18a165Lang Hames }; 3516dcaf59960d699735a57b1623092d561c18a165Lang Hames 3616dcaf59960d699735a57b1623092d561c18a165Lang Hames // The following statics are thread safe. They're read only, and you 3716dcaf59960d699735a57b1623092d561c18a165Lang Hames // can't step from them to any other list entries. 3816dcaf59960d699735a57b1623092d561c18a165Lang Hames ManagedStatic<EmptyIndexListEntry> IndexListEntryEmptyKey; 3916dcaf59960d699735a57b1623092d561c18a165Lang Hames ManagedStatic<TombstoneIndexListEntry> IndexListEntryTombstoneKey; 4016dcaf59960d699735a57b1623092d561c18a165Lang Hames} 41233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 42233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hameschar SlotIndexes::ID = 0; 43d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(SlotIndexes, "slotindexes", 44ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Slot index numbering", false, false) 45233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 4616dcaf59960d699735a57b1623092d561c18a165Lang HamesIndexListEntry* IndexListEntry::getEmptyKeyEntry() { 4716dcaf59960d699735a57b1623092d561c18a165Lang Hames return &*IndexListEntryEmptyKey; 4816dcaf59960d699735a57b1623092d561c18a165Lang Hames} 4916dcaf59960d699735a57b1623092d561c18a165Lang Hames 5016dcaf59960d699735a57b1623092d561c18a165Lang HamesIndexListEntry* IndexListEntry::getTombstoneKeyEntry() { 5116dcaf59960d699735a57b1623092d561c18a165Lang Hames return &*IndexListEntryTombstoneKey; 5216dcaf59960d699735a57b1623092d561c18a165Lang Hames} 5316dcaf59960d699735a57b1623092d561c18a165Lang Hames 5416dcaf59960d699735a57b1623092d561c18a165Lang Hames 55233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const { 56233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames au.setPreservesAll(); 57233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineFunctionPass::getAnalysisUsage(au); 58233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 59233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 60233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid SlotIndexes::releaseMemory() { 61233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mi2iMap.clear(); 62233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mbb2IdxMap.clear(); 63233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames idx2MBBMap.clear(); 64233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames clearList(); 65233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 66233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 67233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool SlotIndexes::runOnMachineFunction(MachineFunction &fn) { 68233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 69233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Compute numbering as follows: 70233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Grab an iterator to the start of the index list. 71233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Iterate over all MBBs, and within each MBB all MIs, keeping the MI 72233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // iterator in lock-step (though skipping it over indexes which have 73233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // null pointers in the instruction field). 74233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // At each iteration assert that the instruction pointed to in the index 75233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // is the same one pointed to by the MI iterator. This 76233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 77233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should 78233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // only need to be set up once after the first numbering is computed. 79233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 80233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mf = &fn; 81233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames initList(); 82233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 83233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Check that the list contains only the sentinal. 84233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(indexListHead->getNext() == 0 && 85233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "Index list non-empty at initial numbering?"); 86233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(idx2MBBMap.empty() && 87233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "Index -> MBB mapping non-empty at initial numbering?"); 88233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(mbb2IdxMap.empty() && 89233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "MBB -> Index mapping non-empty at initial numbering?"); 90233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(mi2iMap.empty() && 91233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "MachineInstr -> Index mapping non-empty at initial numbering?"); 92233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 93233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames functionSize = 0; 94233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames unsigned index = 0; 95233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 9674ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames push_back(createEntry(0, index)); 9774ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames 98f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Iterate over the function. 99233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end(); 100233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mbbItr != mbbEnd; ++mbbItr) { 101233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb = &*mbbItr; 102233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 103233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Insert an index for the MBB start. 104233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex blockStartIndex(back(), SlotIndex::LOAD); 105233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 106fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames index += SlotIndex::NUM; 107233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 108233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end(); 109233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames miItr != miEnd; ++miItr) { 110518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner MachineInstr *mi = miItr; 111518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (mi->isDebugValue()) 1121caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 113233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 114233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Insert a store index for the instr. 115233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames push_back(createEntry(mi, index)); 116233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 117233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Save this base index in the maps. 118233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mi2iMap.insert( 119233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD))); 120233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 121233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ++functionSize; 122233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 123233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames unsigned Slots = mi->getDesc().getNumDefs(); 124233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (Slots == 0) 125233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Slots = 1; 126233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 127fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames index += (Slots + 1) * SlotIndex::NUM; 128233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 129233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1301e8e72d72a71ec3fb6c81bd35a34261f34436900Jakob Stoklund Olesen // We insert two blank instructions between basic blocks. 1311e8e72d72a71ec3fb6c81bd35a34261f34436900Jakob Stoklund Olesen // One to represent live-out registers and one to represent live-ins. 1321e8e72d72a71ec3fb6c81bd35a34261f34436900Jakob Stoklund Olesen push_back(createEntry(0, index)); 1331e8e72d72a71ec3fb6c81bd35a34261f34436900Jakob Stoklund Olesen index += SlotIndex::NUM; 1341e8e72d72a71ec3fb6c81bd35a34261f34436900Jakob Stoklund Olesen 1351e8e72d72a71ec3fb6c81bd35a34261f34436900Jakob Stoklund Olesen push_back(createEntry(0, index)); 13674ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames 13774ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex blockEndIndex(back(), SlotIndex::LOAD); 138233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mbb2IdxMap.insert( 139233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex))); 140233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 141233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb)); 142233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 143233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 144233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Sort the Idx2MBBMap 145233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 146233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 147233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames DEBUG(dump()); 148233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 149233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // And we're done! 150233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return false; 151233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 152233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 153b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hamesvoid SlotIndexes::renumberIndexes() { 154233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 155fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames // Renumber updates the index of every element of the index list. 156fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames // If all instrs in the function have been allocated an index (which has been 157fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames // placed in the index list in the order of instruction iteration) then the 158fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames // resulting numbering will match what would have been generated by the 159fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames // pass during the initial numbering of the function if the new instructions 160fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames // had been present. 16197af98678cc943050cf23951a66c89e922cf21c4Jakob Stoklund Olesen DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n"); 162233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 163fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames functionSize = 0; 164fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames unsigned index = 0; 165fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames 166fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames for (IndexListEntry *curEntry = front(); curEntry != getTail(); 167fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames curEntry = curEntry->getNext()) { 168fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames 169fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames curEntry->setIndex(index); 170fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames 171fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames if (curEntry->getInstr() == 0) { 1721803b37bad85cca19a15c0040979719240f48626Jakob Stoklund Olesen // MBB start entry. Just step index by 1. 173fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames index += SlotIndex::NUM; 174fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames } 175fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames else { 176fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames ++functionSize; 177fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames unsigned Slots = curEntry->getInstr()->getDesc().getNumDefs(); 178fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames if (Slots == 0) 179fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames Slots = 1; 180233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 181fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames index += (Slots + 1) * SlotIndex::NUM; 182fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames } 183fbb8fa247ec13067d9ad3f0c426e2029d15222b2Lang Hames } 184233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 185233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 186233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid SlotIndexes::dump() const { 187233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (const IndexListEntry *itr = front(); itr != getTail(); 188233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames itr = itr->getNext()) { 18987b0efc86dcc1dac30fcd6b4d1c51110f707a28cDavid Greene dbgs() << itr->getIndex() << " "; 190233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 191233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (itr->getInstr() != 0) { 19287b0efc86dcc1dac30fcd6b4d1c51110f707a28cDavid Greene dbgs() << *itr->getInstr(); 193233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } else { 19487b0efc86dcc1dac30fcd6b4d1c51110f707a28cDavid Greene dbgs() << "\n"; 195233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 196233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 197233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 19881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin for (MBB2IdxMap::const_iterator itr = mbb2IdxMap.begin(); 199233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames itr != mbb2IdxMap.end(); ++itr) { 20087b0efc86dcc1dac30fcd6b4d1c51110f707a28cDavid Greene dbgs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - [" 201233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames << itr->second.first << ", " << itr->second.second << "]\n"; 202233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 203233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 204233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 205233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// Print a SlotIndex to a raw_ostream. 206233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid SlotIndex::print(raw_ostream &os) const { 20797af98678cc943050cf23951a66c89e922cf21c4Jakob Stoklund Olesen if (isValid()) 20897af98678cc943050cf23951a66c89e922cf21c4Jakob Stoklund Olesen os << entry().getIndex() << "LudS"[getSlot()]; 20997af98678cc943050cf23951a66c89e922cf21c4Jakob Stoklund Olesen else 21097af98678cc943050cf23951a66c89e922cf21c4Jakob Stoklund Olesen os << "invalid"; 211233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 212233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 213233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// Dump a SlotIndex to stderr. 214233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid SlotIndex::dump() const { 21587b0efc86dcc1dac30fcd6b4d1c51110f707a28cDavid Greene print(dbgs()); 21687b0efc86dcc1dac30fcd6b4d1c51110f707a28cDavid Greene dbgs() << "\n"; 217233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 218233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 219