blob: c0ae34301dc8fcaec3b23c9df299b0be666dad9b [file] [log] [blame]
Lang Hames233a60e2009-11-03 23:52:08 +00001//===-- 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"
Jakob Stoklund Olesen10c5f2d2011-03-04 18:08:29 +000013#include "llvm/ADT/Statistic.h"
Lang Hames233a60e2009-11-03 23:52:08 +000014#include "llvm/CodeGen/MachineFunction.h"
15#include "llvm/Support/Debug.h"
16#include "llvm/Support/raw_ostream.h"
Dale Johannesen1caedd02010-01-22 22:38:21 +000017#include "llvm/Target/TargetInstrInfo.h"
Lang Hames233a60e2009-11-03 23:52:08 +000018
19using namespace llvm;
20
Lang Hames233a60e2009-11-03 23:52:08 +000021char SlotIndexes::ID = 0;
Owen Andersond13db2c2010-07-21 22:09:45 +000022INITIALIZE_PASS(SlotIndexes, "slotindexes",
Owen Andersonce665bd2010-10-07 22:25:06 +000023 "Slot index numbering", false, false)
Lang Hames233a60e2009-11-03 23:52:08 +000024
Jakob Stoklund Olesen979869c2011-03-04 19:43:38 +000025STATISTIC(NumLocalRenum, "Number of local renumberings");
26STATISTIC(NumGlobalRenum, "Number of global renumberings");
Jakob Stoklund Olesen10c5f2d2011-03-04 18:08:29 +000027
Lang Hames233a60e2009-11-03 23:52:08 +000028void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const {
29 au.setPreservesAll();
30 MachineFunctionPass::getAnalysisUsage(au);
31}
32
33void SlotIndexes::releaseMemory() {
34 mi2iMap.clear();
35 mbb2IdxMap.clear();
36 idx2MBBMap.clear();
Lang Hames233a60e2009-11-03 23:52:08 +000037 clearList();
38}
39
40bool 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
Lang Hames233a60e2009-11-03 23:52:08 +000056 // 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;
Lang Hames233a60e2009-11-03 23:52:08 +000067 unsigned index = 0;
68
Lang Hames74ab5ee2009-12-22 00:11:50 +000069 push_back(createEntry(0, index));
70
Dan Gohmanf451cb82010-02-10 16:03:48 +000071 // Iterate over the function.
Lang Hames233a60e2009-11-03 23:52:08 +000072 for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end();
73 mbbItr != mbbEnd; ++mbbItr) {
74 MachineBasicBlock *mbb = &*mbbItr;
75
76 // Insert an index for the MBB start.
Lang Hames233a60e2009-11-03 23:52:08 +000077 SlotIndex blockStartIndex(back(), SlotIndex::LOAD);
78
Lang Hames233a60e2009-11-03 23:52:08 +000079 for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end();
80 miItr != miEnd; ++miItr) {
Chris Lattner518bb532010-02-09 19:54:29 +000081 MachineInstr *mi = miItr;
82 if (mi->isDebugValue())
Dale Johannesen1caedd02010-01-22 22:38:21 +000083 continue;
Lang Hames233a60e2009-11-03 23:52:08 +000084
Lang Hames233a60e2009-11-03 23:52:08 +000085 // Insert a store index for the instr.
Jakob Stoklund Olesenf0cf2d32011-03-04 18:51:09 +000086 push_back(createEntry(mi, index += SlotIndex::InstrDist));
Lang Hames233a60e2009-11-03 23:52:08 +000087
88 // Save this base index in the maps.
Jakob Stoklund Olesenf0cf2d32011-03-04 18:51:09 +000089 mi2iMap.insert(std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD)));
Lang Hames233a60e2009-11-03 23:52:08 +000090
91 ++functionSize;
Lang Hames233a60e2009-11-03 23:52:08 +000092 }
93
Jakob Stoklund Olesenf0cf2d32011-03-04 18:51:09 +000094 // We insert one blank instructions between basic blocks.
95 push_back(createEntry(0, index += SlotIndex::InstrDist));
Lang Hames74ab5ee2009-12-22 00:11:50 +000096
97 SlotIndex blockEndIndex(back(), SlotIndex::LOAD);
Lang Hames233a60e2009-11-03 23:52:08 +000098 mbb2IdxMap.insert(
99 std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex)));
100
101 idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb));
102 }
103
Lang Hames233a60e2009-11-03 23:52:08 +0000104 // Sort the Idx2MBBMap
105 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
106
107 DEBUG(dump());
108
109 // And we're done!
110 return false;
111}
112
Lang Hamesb3661582009-11-14 00:02:51 +0000113void SlotIndexes::renumberIndexes() {
Lang Hamesfbb8fa22009-11-05 22:20:57 +0000114 // Renumber updates the index of every element of the index list.
Jakob Stoklund Olesen97af9862011-02-03 20:29:41 +0000115 DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n");
Jakob Stoklund Olesen979869c2011-03-04 19:43:38 +0000116 ++NumGlobalRenum;
Lang Hames233a60e2009-11-03 23:52:08 +0000117
Lang Hamesfbb8fa22009-11-05 22:20:57 +0000118 unsigned index = 0;
Lang Hames233a60e2009-11-03 23:52:08 +0000119
Lang Hamesfbb8fa22009-11-05 22:20:57 +0000120 for (IndexListEntry *curEntry = front(); curEntry != getTail();
121 curEntry = curEntry->getNext()) {
Lang Hamesfbb8fa22009-11-05 22:20:57 +0000122 curEntry->setIndex(index);
Jakob Stoklund Olesenf0cf2d32011-03-04 18:51:09 +0000123 index += SlotIndex::InstrDist;
Lang Hamesfbb8fa22009-11-05 22:20:57 +0000124 }
Lang Hames233a60e2009-11-03 23:52:08 +0000125}
126
Jakob Stoklund Olesen979869c2011-03-04 19:43:38 +0000127// Renumber indexes locally after curEntry was inserted, but failed to get a new
128// index.
129void SlotIndexes::renumberIndexes(IndexListEntry *curEntry) {
130 // Number indexes with half the default spacing so we can catch up quickly.
131 const unsigned Space = SlotIndex::InstrDist/2;
132 assert((Space & 3) == 0 && "InstrDist must be a multiple of 2*NUM");
133
134 IndexListEntry *start = curEntry->getPrev();
135 unsigned index = start->getIndex();
136 IndexListEntry *tail = getTail();
137 do {
138 curEntry->setIndex(index += Space);
139 curEntry = curEntry->getNext();
140 // If the next index is bigger, we have caught up.
141 } while (curEntry != tail && curEntry->getIndex() <= index);
142
143 DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << start->getIndex() << '-'
144 << index << " ***\n");
145 ++NumLocalRenum;
146}
147
148
Lang Hames233a60e2009-11-03 23:52:08 +0000149void SlotIndexes::dump() const {
150 for (const IndexListEntry *itr = front(); itr != getTail();
151 itr = itr->getNext()) {
David Greene87b0efc2010-01-05 01:25:50 +0000152 dbgs() << itr->getIndex() << " ";
Lang Hames233a60e2009-11-03 23:52:08 +0000153
154 if (itr->getInstr() != 0) {
David Greene87b0efc2010-01-05 01:25:50 +0000155 dbgs() << *itr->getInstr();
Lang Hames233a60e2009-11-03 23:52:08 +0000156 } else {
David Greene87b0efc2010-01-05 01:25:50 +0000157 dbgs() << "\n";
Lang Hames233a60e2009-11-03 23:52:08 +0000158 }
159 }
160
Jeffrey Yasskin81cf4322009-11-10 01:02:17 +0000161 for (MBB2IdxMap::const_iterator itr = mbb2IdxMap.begin();
Lang Hames233a60e2009-11-03 23:52:08 +0000162 itr != mbb2IdxMap.end(); ++itr) {
David Greene87b0efc2010-01-05 01:25:50 +0000163 dbgs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - ["
Lang Hames233a60e2009-11-03 23:52:08 +0000164 << itr->second.first << ", " << itr->second.second << "]\n";
165 }
166}
167
168// Print a SlotIndex to a raw_ostream.
169void SlotIndex::print(raw_ostream &os) const {
Jakob Stoklund Olesen97af9862011-02-03 20:29:41 +0000170 if (isValid())
171 os << entry().getIndex() << "LudS"[getSlot()];
172 else
173 os << "invalid";
Lang Hames233a60e2009-11-03 23:52:08 +0000174}
175
176// Dump a SlotIndex to stderr.
177void SlotIndex::dump() const {
David Greene87b0efc2010-01-05 01:25:50 +0000178 print(dbgs());
179 dbgs() << "\n";
Lang Hames233a60e2009-11-03 23:52:08 +0000180}
181