1//===-- SlotIndexes.cpp - Slot Indexes Pass ------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/CodeGen/SlotIndexes.h"
10#include "llvm/ADT/Statistic.h"
11#include "llvm/CodeGen/MachineFunction.h"
12#include "llvm/Config/llvm-config.h"
13#include "llvm/InitializePasses.h"
14#include "llvm/Support/Debug.h"
15#include "llvm/Support/raw_ostream.h"
16
17using namespace llvm;
18
19#define DEBUG_TYPE "slot-indexes"
20
21AnalysisKey SlotIndexesAnalysis::Key;
22
23SlotIndexesAnalysis::Result
24SlotIndexesAnalysis::run(MachineFunction &MF,
25 MachineFunctionAnalysisManager &) {
26 return Result(MF);
27}
28
29PreservedAnalyses
30SlotIndexesPrinterPass::run(MachineFunction &MF,
31 MachineFunctionAnalysisManager &MFAM) {
32 OS << "Slot indexes in machine function: " << MF.getName() << '\n';
33 MFAM.getResult<SlotIndexesAnalysis>(IR&: MF).print(OS);
34 return PreservedAnalyses::all();
35}
36char SlotIndexesWrapperPass::ID = 0;
37
38SlotIndexesWrapperPass::SlotIndexesWrapperPass() : MachineFunctionPass(ID) {}
39
40SlotIndexes::~SlotIndexes() {
41 // The indexList's nodes are all allocated in the BumpPtrAllocator.
42 indexList.clear();
43}
44
45INITIALIZE_PASS(SlotIndexesWrapperPass, DEBUG_TYPE, "Slot index numbering",
46 false, false)
47
48STATISTIC(NumLocalRenum, "Number of local renumberings");
49STATISTIC(NumDeadEntriesErased,
50 "Number of index list entries erased for deleted instructions");
51
52void SlotIndexesWrapperPass::getAnalysisUsage(AnalysisUsage &au) const {
53 au.setPreservesAll();
54 MachineFunctionPass::getAnalysisUsage(AU&: au);
55}
56
57void SlotIndexes::clear() {
58 mi2iMap.clear();
59 MBBRanges.clear();
60 idx2MBBMap.clear();
61 indexList.clear();
62 ileAllocator.Reset();
63}
64
65void SlotIndexes::analyze(MachineFunction &fn) {
66
67 // Compute numbering as follows:
68 // Grab an iterator to the start of the index list.
69 // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
70 // iterator in lock-step (though skipping it over indexes which have
71 // null pointers in the instruction field).
72 // At each iteration assert that the instruction pointed to in the index
73 // is the same one pointed to by the MI iterator. This
74
75 // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
76 // only need to be set up once after the first numbering is computed.
77
78 mf = &fn;
79
80 // Check that the list contains only the sentinel.
81 assert(indexList.empty() && "Index list non-empty at initial numbering?");
82 assert(idx2MBBMap.empty() &&
83 "Index -> MBB mapping non-empty at initial numbering?");
84 assert(MBBRanges.empty() &&
85 "MBB -> Index mapping non-empty at initial numbering?");
86 assert(mi2iMap.empty() &&
87 "MachineInstr -> Index mapping non-empty at initial numbering?");
88
89 unsigned index = 0;
90 MBBRanges.resize(N: mf->getMaxAnalysisBlockNumber());
91 idx2MBBMap.reserve(N: mf->size());
92
93 indexList.push_back(Node&: *createEntry(mi: nullptr, index));
94
95 // Iterate over the function.
96 for (MachineBasicBlock &MBB : *mf) {
97 // Insert an index for the MBB start.
98 SlotIndex blockStartIndex(&indexList.back(), SlotIndex::Slot_Block);
99
100 for (MachineInstr &MI : MBB) {
101 if (MI.isDebugOrPseudoInstr())
102 continue;
103
104 // Insert a store index for the instr.
105 indexList.push_back(Node&: *createEntry(mi: &MI, index: index += SlotIndex::InstrDist));
106
107 // Save this base index in the maps.
108 mi2iMap.insert(KV: std::make_pair(
109 x: &MI, y: SlotIndex(&indexList.back(), SlotIndex::Slot_Block)));
110 }
111
112 // We insert one blank instructions between basic blocks.
113 indexList.push_back(Node&: *createEntry(mi: nullptr, index: index += SlotIndex::InstrDist));
114
115 MBBRanges[MBB.getAnalysisNumber()].first = blockStartIndex;
116 MBBRanges[MBB.getAnalysisNumber()].second =
117 SlotIndex(&indexList.back(), SlotIndex::Slot_Block);
118 idx2MBBMap.push_back(Elt: IdxMBBPair(blockStartIndex, &MBB));
119 }
120
121 // Sort the Idx2MBBMap
122 llvm::sort(C&: idx2MBBMap, Comp: less_first());
123
124 LLVM_DEBUG(mf->print(dbgs(), this));
125}
126
127bool SlotIndexes::isBlockBoundaryIndex(SlotIndex Idx) const {
128 if (getInstructionFromIndex(index: Idx))
129 return false;
130
131 // Adjacent blocks share a boundary entry, so a boundary is either the start
132 // index of the block Idx falls in or the end index of the last block. A block
133 // dropped by removeMBBFromMaps() is gone from idx2MBBMap, so its start entry
134 // classifies as stale.
135 assert(!idx2MBBMap.empty() && "Index -> MBB mapping is empty");
136 SlotIndex Base = Idx.getBaseIndex();
137 MBBIndexIterator I = std::prev(x: getMBBUpperBound(Idx: Base));
138 return Base == I->first || Base == getMBBEndIdx(mbb: I->second);
139}
140
141SlotIndex SlotIndexes::canonicalizeIndex(SlotIndex Idx) const {
142 if (!isStaleIndex(Idx))
143 return Idx;
144
145 // The block start is a boundary entry, so it bounds the walk.
146 SlotIndex BlockStart = getMBBStartIdx(mbb: getMBBFromIndex(index: Idx));
147 IndexList::iterator I = Idx.listEntry()->getIterator();
148 while (&*I != BlockStart.listEntry()) {
149 --I;
150 if (I->getInstr())
151 return SlotIndex(&*I, SlotIndex::Slot_Register);
152 }
153 return BlockStart;
154}
155
156void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI,
157 bool AllowBundled) {
158 assert((AllowBundled || !MI.isBundledWithPred()) &&
159 "Use removeSingleMachineInstrFromMaps() instead");
160 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(Val: &MI);
161 if (mi2iItr == mi2iMap.end())
162 return;
163
164 SlotIndex MIIndex = mi2iItr->second;
165 IndexListEntry &MIEntry = *MIIndex.listEntry();
166 assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
167 mi2iMap.erase(I: mi2iItr);
168 // FIXME: Eventually we want to actually delete these indexes.
169 MIEntry.setInstr(nullptr);
170}
171
172void SlotIndexes::removeSingleMachineInstrFromMaps(MachineInstr &MI) {
173 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(Val: &MI);
174 if (mi2iItr == mi2iMap.end())
175 return;
176
177 SlotIndex MIIndex = mi2iItr->second;
178 IndexListEntry &MIEntry = *MIIndex.listEntry();
179 assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
180 mi2iMap.erase(I: mi2iItr);
181
182 // When removing the first instruction of a bundle update mapping to next
183 // instruction.
184 if (MI.isBundledWithSucc()) {
185 // Only the first instruction of a bundle should have an index assigned.
186 assert(!MI.isBundledWithPred() && "Should be first bundle instruction");
187
188 MachineBasicBlock::instr_iterator Next = std::next(x: MI.getIterator());
189 MachineInstr &NextMI = *Next;
190 MIEntry.setInstr(&NextMI);
191 mi2iMap.insert(KV: std::make_pair(x: &NextMI, y&: MIIndex));
192 return;
193 } else {
194 // FIXME: Eventually we want to actually delete these indexes.
195 MIEntry.setInstr(nullptr);
196 }
197}
198
199void SlotIndexes::removeMBBFromMaps(MachineBasicBlock &MBB) {
200 assert(&MBB != &MBB.getParent()->front() &&
201 "Can't remove the first block of a function.");
202
203 unsigned Num = MBB.getAnalysisNumber();
204 SlotIndex StartIdx = MBBRanges[Num].first;
205 SlotIndex EndIdx = MBBRanges[Num].second;
206
207 // Give MBB's slot range to its layout predecessor so blocks stay contiguous.
208 auto PrevMBB = std::prev(x: MBB.getIterator());
209 MBBRanges[PrevMBB->getAnalysisNumber()].second = EndIdx;
210
211 // Drop MBB's index -> MBB entry, which would dangle once MBB is erased.
212 auto It = getMBBLowerBound(Idx: StartIdx);
213 assert(It != MBBIndexEnd() && It->first == StartIdx && It->second == &MBB &&
214 "MBB not found in index -> MBB map");
215 idx2MBBMap.erase(CI: It);
216
217 // Clear the block-start boundary entry. MBBRanges is never renumbered, so
218 // MBB's now-stale slot is simply left in place.
219 StartIdx.listEntry()->setInstr(nullptr);
220}
221
222// Renumber indexes locally after curItr was inserted, but failed to get a new
223// index.
224void SlotIndexes::renumberIndexes(IndexList::iterator curItr) {
225 // Number indexes with half the default spacing so we can catch up quickly.
226 const unsigned Space = SlotIndex::InstrDist/2;
227 static_assert((Space & 3) == 0, "InstrDist must be a multiple of 2*NUM");
228
229 IndexList::iterator startItr = std::prev(x: curItr);
230 unsigned index = startItr->getIndex();
231 unsigned BeginIndex = index;
232 do {
233 curItr->setIndex(index += Space);
234 ++curItr;
235 // If the next index is bigger, we have caught up.
236 } while (curItr != indexList.end() && curItr->getIndex() <= index);
237
238 LLVM_DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex()
239 << '-' << index << " ***\n");
240
241 // If we repack more than 20% of a function, add spacing in between the
242 // instructions so that future renumberings are able to catch up
243 // without also renumbering so much.
244 if (index - BeginIndex >
245 (getLastIndex().getIndex() - getZeroIndex().getIndex()) / 5)
246 packIndexes();
247
248 ++NumLocalRenum;
249}
250
251// Repair indexes after adding and removing instructions.
252void SlotIndexes::repairIndexesInRange(MachineBasicBlock *MBB,
253 MachineBasicBlock::iterator Begin,
254 MachineBasicBlock::iterator End) {
255 bool includeStart = (Begin == MBB->begin());
256 SlotIndex startIdx;
257 if (includeStart)
258 startIdx = getMBBStartIdx(mbb: MBB);
259 else
260 startIdx = getInstructionIndex(MI: *--Begin);
261
262 SlotIndex endIdx;
263 if (End == MBB->end())
264 endIdx = getMBBEndIdx(mbb: MBB);
265 else
266 endIdx = getInstructionIndex(MI: *End);
267
268 // FIXME: Conceptually, this code is implementing an iterator on MBB that
269 // optionally includes an additional position prior to MBB->begin(), indicated
270 // by the includeStart flag. This is done so that we can iterate MIs in a MBB
271 // in parallel with SlotIndexes, but there should be a better way to do this.
272 IndexList::iterator ListB = startIdx.listEntry()->getIterator();
273 IndexList::iterator ListI = endIdx.listEntry()->getIterator();
274 MachineBasicBlock::iterator MBBI = End;
275 bool pastStart = false;
276 bool OldIndexesRemoved = false;
277 while (ListI != ListB || MBBI != Begin || (includeStart && !pastStart)) {
278 assert(ListI->getIndex() >= startIdx.getIndex() &&
279 (includeStart || !pastStart) &&
280 "Decremented past the beginning of region to repair.");
281
282 MachineInstr *SlotMI = ListI->getInstr();
283 MachineInstr *MI = (MBBI != MBB->end() && !pastStart) ? &*MBBI : nullptr;
284 bool MBBIAtBegin = MBBI == Begin && (!includeStart || pastStart);
285 bool MIIndexNotFound = MI && !mi2iMap.contains(Val: MI);
286 bool SlotMIRemoved = false;
287
288 if (SlotMI == MI && !MBBIAtBegin) {
289 --ListI;
290 if (MBBI != Begin)
291 --MBBI;
292 else
293 pastStart = true;
294 } else if (MIIndexNotFound || OldIndexesRemoved) {
295 if (MBBI != Begin)
296 --MBBI;
297 else
298 pastStart = true;
299 } else {
300 // We ran through all the indexes on the interval
301 // -> The only thing left is to go through all the
302 // remaining MBB instructions and update their indexes
303 if (ListI == ListB)
304 OldIndexesRemoved = true;
305 else
306 --ListI;
307 if (SlotMI) {
308 removeMachineInstrFromMaps(MI&: *SlotMI);
309 SlotMIRemoved = true;
310 }
311 }
312
313 MachineInstr *InstrToInsert = SlotMIRemoved ? SlotMI : MI;
314
315 // Insert instruction back into the maps after passing it/removing the index
316 if ((MIIndexNotFound || SlotMIRemoved) && InstrToInsert->getParent() &&
317 !InstrToInsert->isDebugOrPseudoInstr())
318 insertMachineInstrInMaps(MI&: *InstrToInsert);
319 }
320}
321
322void SlotIndexes::packIndexes() {
323 for (auto [Index, Entry] : enumerate(First&: indexList))
324 Entry.setIndex(Index * SlotIndex::InstrDist);
325}
326
327unsigned SlotIndexes::compactIndexes() {
328 if (indexList.empty())
329 return 0;
330
331 SmallPtrSet<const IndexListEntry *, 32> Keep;
332
333 // The first and last entries anchor getZeroIndex() and getLastIndex().
334 Keep.insert(Ptr: &indexList.front());
335 Keep.insert(Ptr: &indexList.back());
336
337 for (const auto &Range : MBBRanges) {
338 if (Range.first.isValid())
339 Keep.insert(Ptr: Range.first.listEntry());
340 if (Range.second.isValid())
341 Keep.insert(Ptr: Range.second.listEntry());
342 }
343
344 // Entries must be unlinked, not zero-width: that would break getNextSlot().
345 SmallVector<IndexListEntry *, 16> Erased;
346 unsigned Index = 0;
347 for (auto It = indexList.begin(), E = indexList.end(); It != E;) {
348 IndexListEntry &Entry = *It++;
349 if (Entry.getInstr() || Keep.contains(Ptr: &Entry)) {
350 Entry.setIndex(Index);
351 Index += SlotIndex::InstrDist;
352 continue;
353 }
354 // Take the surviving entry behind, so a stale index stays in program order.
355 assert(Index != 0 && "First entry is always kept");
356 Entry.setIndex(Index - SlotIndex::InstrDist);
357 Erased.push_back(Elt: &Entry);
358 indexList.remove(N&: Entry);
359 }
360
361 for (IndexListEntry *Entry : Erased)
362 Entry->setErased();
363
364 NumDeadEntriesErased += Erased.size();
365 return Erased.size();
366}
367
368void SlotIndexes::print(raw_ostream &OS) const {
369 for (const IndexListEntry &ILE : indexList) {
370 OS << ILE.getIndex() << ' ';
371
372 if (ILE.getInstr())
373 OS << *ILE.getInstr();
374 else
375 OS << '\n';
376 }
377
378 for (const MachineBasicBlock &MBB : *mf)
379 OS << printMBBReference(MBB) << "\t[" << getMBBStartIdx(mbb: &MBB) << ';'
380 << getMBBEndIdx(mbb: &MBB) << ")\n";
381}
382
383#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
384LLVM_DUMP_METHOD void SlotIndexes::dump() const { print(dbgs()); }
385#endif
386
387// Print a SlotIndex to a raw_ostream.
388void SlotIndex::print(raw_ostream &os) const {
389 if (isValid())
390 os << listEntry()->getIndex() << "Berd"[getSlot()];
391 else
392 os << "invalid";
393}
394
395#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
396// Dump a SlotIndex to stderr.
397LLVM_DUMP_METHOD void SlotIndex::dump() const {
398 print(dbgs());
399 dbgs() << "\n";
400}
401#endif
402