Line data Source code
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 : #include "llvm/CodeGen/SlotIndexes.h"
11 : #include "llvm/ADT/Statistic.h"
12 : #include "llvm/CodeGen/MachineFunction.h"
13 : #include "llvm/Config/llvm-config.h"
14 : #include "llvm/Support/Debug.h"
15 : #include "llvm/Support/raw_ostream.h"
16 :
17 : using namespace llvm;
18 :
19 : #define DEBUG_TYPE "slotindexes"
20 :
21 : char SlotIndexes::ID = 0;
22 642021 : INITIALIZE_PASS(SlotIndexes, DEBUG_TYPE,
23 : "Slot index numbering", false, false)
24 :
25 : STATISTIC(NumLocalRenum, "Number of local renumberings");
26 : STATISTIC(NumGlobalRenum, "Number of global renumberings");
27 :
28 44429 : void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const {
29 : au.setPreservesAll();
30 44429 : MachineFunctionPass::getAnalysisUsage(au);
31 44429 : }
32 :
33 429806 : void SlotIndexes::releaseMemory() {
34 429806 : mi2iMap.clear();
35 : MBBRanges.clear();
36 : idx2MBBMap.clear();
37 : indexList.clear();
38 429806 : ileAllocator.Reset();
39 429806 : }
40 :
41 429774 : bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
42 :
43 : // Compute numbering as follows:
44 : // Grab an iterator to the start of the index list.
45 : // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
46 : // iterator in lock-step (though skipping it over indexes which have
47 : // null pointers in the instruction field).
48 : // At each iteration assert that the instruction pointed to in the index
49 : // is the same one pointed to by the MI iterator. This
50 :
51 : // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
52 : // only need to be set up once after the first numbering is computed.
53 :
54 429774 : mf = &fn;
55 :
56 : // Check that the list contains only the sentinal.
57 : assert(indexList.empty() && "Index list non-empty at initial numbering?");
58 : assert(idx2MBBMap.empty() &&
59 : "Index -> MBB mapping non-empty at initial numbering?");
60 : assert(MBBRanges.empty() &&
61 : "MBB -> Index mapping non-empty at initial numbering?");
62 : assert(mi2iMap.empty() &&
63 : "MachineInstr -> Index mapping non-empty at initial numbering?");
64 :
65 : unsigned index = 0;
66 859548 : MBBRanges.resize(mf->getNumBlockIDs());
67 859548 : idx2MBBMap.reserve(mf->size());
68 :
69 : indexList.push_back(createEntry(nullptr, index));
70 :
71 : // Iterate over the function.
72 1363532 : for (MachineBasicBlock &MBB : *mf) {
73 : // Insert an index for the MBB start.
74 : SlotIndex blockStartIndex(&indexList.back(), SlotIndex::Slot_Block);
75 :
76 11411924 : for (MachineInstr &MI : MBB) {
77 : if (MI.isDebugInstr())
78 : continue;
79 :
80 : // Insert a store index for the instr.
81 10231971 : indexList.push_back(createEntry(&MI, index += SlotIndex::InstrDist));
82 :
83 : // Save this base index in the maps.
84 10231971 : mi2iMap.insert(std::make_pair(
85 10231971 : &MI, SlotIndex(&indexList.back(), SlotIndex::Slot_Block)));
86 : }
87 :
88 : // We insert one blank instructions between basic blocks.
89 933759 : indexList.push_back(createEntry(nullptr, index += SlotIndex::InstrDist));
90 :
91 1867518 : MBBRanges[MBB.getNumber()].first = blockStartIndex;
92 933759 : MBBRanges[MBB.getNumber()].second = SlotIndex(&indexList.back(),
93 : SlotIndex::Slot_Block);
94 1867518 : idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, &MBB));
95 : }
96 :
97 : // Sort the Idx2MBBMap
98 : llvm::sort(idx2MBBMap, Idx2MBBCompare());
99 :
100 : LLVM_DEBUG(mf->print(dbgs(), this));
101 :
102 : // And we're done!
103 429774 : return false;
104 : }
105 :
106 1179468 : void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI) {
107 : assert(!MI.isBundledWithPred() &&
108 : "Use removeSingleMachineInstrFromMaps() instread");
109 1179468 : Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
110 1179468 : if (mi2iItr == mi2iMap.end())
111 255 : return;
112 :
113 1179213 : SlotIndex MIIndex = mi2iItr->second;
114 : IndexListEntry &MIEntry = *MIIndex.listEntry();
115 : assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
116 : mi2iMap.erase(mi2iItr);
117 : // FIXME: Eventually we want to actually delete these indexes.
118 : MIEntry.setInstr(nullptr);
119 : }
120 :
121 615391 : void SlotIndexes::removeSingleMachineInstrFromMaps(MachineInstr &MI) {
122 615391 : Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
123 615391 : if (mi2iItr == mi2iMap.end())
124 6 : return;
125 :
126 615391 : SlotIndex MIIndex = mi2iItr->second;
127 : IndexListEntry &MIEntry = *MIIndex.listEntry();
128 : assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
129 : mi2iMap.erase(mi2iItr);
130 :
131 : // When removing the first instruction of a bundle update mapping to next
132 : // instruction.
133 615391 : if (MI.isBundledWithSucc()) {
134 : // Only the first instruction of a bundle should have an index assigned.
135 : assert(!MI.isBundledWithPred() && "Should have first bundle isntruction");
136 :
137 6 : MachineBasicBlock::instr_iterator Next = std::next(MI.getIterator());
138 : MachineInstr &NextMI = *Next;
139 : MIEntry.setInstr(&NextMI);
140 6 : mi2iMap.insert(std::make_pair(&NextMI, MIIndex));
141 : return;
142 : } else {
143 : // FIXME: Eventually we want to actually delete these indexes.
144 : MIEntry.setInstr(nullptr);
145 : }
146 : }
147 :
148 0 : void SlotIndexes::renumberIndexes() {
149 : // Renumber updates the index of every element of the index list.
150 : LLVM_DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n");
151 : ++NumGlobalRenum;
152 :
153 : unsigned index = 0;
154 :
155 : for (IndexList::iterator I = indexList.begin(), E = indexList.end();
156 0 : I != E; ++I) {
157 : I->setIndex(index);
158 0 : index += SlotIndex::InstrDist;
159 : }
160 0 : }
161 :
162 : // Renumber indexes locally after curItr was inserted, but failed to get a new
163 : // index.
164 51688 : void SlotIndexes::renumberIndexes(IndexList::iterator curItr) {
165 : // Number indexes with half the default spacing so we can catch up quickly.
166 : const unsigned Space = SlotIndex::InstrDist/2;
167 : static_assert((Space & 3) == 0, "InstrDist must be a multiple of 2*NUM");
168 :
169 : IndexList::iterator startItr = std::prev(curItr);
170 51688 : unsigned index = startItr->getIndex();
171 : do {
172 4443156 : curItr->setIndex(index += Space);
173 : ++curItr;
174 : // If the next index is bigger, we have caught up.
175 4443156 : } while (curItr != indexList.end() && curItr->getIndex() <= index);
176 :
177 : LLVM_DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex()
178 : << '-' << index << " ***\n");
179 : ++NumLocalRenum;
180 51688 : }
181 :
182 : // Repair indexes after adding and removing instructions.
183 27 : void SlotIndexes::repairIndexesInRange(MachineBasicBlock *MBB,
184 : MachineBasicBlock::iterator Begin,
185 : MachineBasicBlock::iterator End) {
186 : // FIXME: Is this really necessary? The only caller repairIntervalsForRange()
187 : // does the same thing.
188 : // Find anchor points, which are at the beginning/end of blocks or at
189 : // instructions that already have indexes.
190 27 : while (Begin != MBB->begin() && !hasIndex(*Begin))
191 : --Begin;
192 27 : while (End != MBB->end() && !hasIndex(*End))
193 : ++End;
194 :
195 : bool includeStart = (Begin == MBB->begin());
196 : SlotIndex startIdx;
197 27 : if (includeStart)
198 : startIdx = getMBBStartIdx(MBB);
199 : else
200 17 : startIdx = getInstructionIndex(*Begin);
201 :
202 : SlotIndex endIdx;
203 27 : if (End == MBB->end())
204 : endIdx = getMBBEndIdx(MBB);
205 : else
206 27 : endIdx = getInstructionIndex(*End);
207 :
208 : // FIXME: Conceptually, this code is implementing an iterator on MBB that
209 : // optionally includes an additional position prior to MBB->begin(), indicated
210 : // by the includeStart flag. This is done so that we can iterate MIs in a MBB
211 : // in parallel with SlotIndexes, but there should be a better way to do this.
212 27 : IndexList::iterator ListB = startIdx.listEntry()->getIterator();
213 27 : IndexList::iterator ListI = endIdx.listEntry()->getIterator();
214 27 : MachineBasicBlock::iterator MBBI = End;
215 : bool pastStart = false;
216 224 : while (ListI != ListB || MBBI != Begin || (includeStart && !pastStart)) {
217 : assert(ListI->getIndex() >= startIdx.getIndex() &&
218 : (includeStart || !pastStart) &&
219 : "Decremented past the beginning of region to repair.");
220 :
221 197 : MachineInstr *SlotMI = ListI->getInstr();
222 197 : MachineInstr *MI = (MBBI != MBB->end() && !pastStart) ? &*MBBI : nullptr;
223 197 : bool MBBIAtBegin = MBBI == Begin && (!includeStart || pastStart);
224 :
225 197 : if (SlotMI == MI && !MBBIAtBegin) {
226 : --ListI;
227 37 : if (MBBI != Begin)
228 : --MBBI;
229 : else
230 : pastStart = true;
231 160 : } else if (MI && mi2iMap.find(MI) == mi2iMap.end()) {
232 133 : if (MBBI != Begin)
233 : --MBBI;
234 : else
235 : pastStart = true;
236 : } else {
237 : --ListI;
238 27 : if (SlotMI)
239 27 : removeMachineInstrFromMaps(*SlotMI);
240 : }
241 : }
242 :
243 : // In theory this could be combined with the previous loop, but it is tricky
244 : // to update the IndexList while we are iterating it.
245 187 : for (MachineBasicBlock::iterator I = End; I != Begin;) {
246 : --I;
247 : MachineInstr &MI = *I;
248 160 : if (!MI.isDebugInstr() && mi2iMap.find(&MI) == mi2iMap.end())
249 133 : insertMachineInstrInMaps(MI);
250 : }
251 27 : }
252 :
253 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
254 : LLVM_DUMP_METHOD void SlotIndexes::dump() const {
255 : for (IndexList::const_iterator itr = indexList.begin();
256 : itr != indexList.end(); ++itr) {
257 : dbgs() << itr->getIndex() << " ";
258 :
259 : if (itr->getInstr()) {
260 : dbgs() << *itr->getInstr();
261 : } else {
262 : dbgs() << "\n";
263 : }
264 : }
265 :
266 : for (unsigned i = 0, e = MBBRanges.size(); i != e; ++i)
267 : dbgs() << "%bb." << i << "\t[" << MBBRanges[i].first << ';'
268 : << MBBRanges[i].second << ")\n";
269 : }
270 : #endif
271 :
272 : // Print a SlotIndex to a raw_ostream.
273 8076 : void SlotIndex::print(raw_ostream &os) const {
274 8076 : if (isValid())
275 8076 : os << listEntry()->getIndex() << "Berd"[getSlot()];
276 : else
277 0 : os << "invalid";
278 8076 : }
279 :
280 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
281 : // Dump a SlotIndex to stderr.
282 : LLVM_DUMP_METHOD void SlotIndex::dump() const {
283 : print(dbgs());
284 : dbgs() << "\n";
285 : }
286 : #endif
287 :
|
