Line data Source code
1 : //===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- C++ -*-===//
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 : // This file implements SlotIndex and related classes. The purpose of SlotIndex
11 : // is to describe a position at which a register can become live, or cease to
12 : // be live.
13 : //
14 : // SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which
15 : // is held is LiveIntervals and provides the real numbering. This allows
16 : // LiveIntervals to perform largely transparent renumbering.
17 : //===----------------------------------------------------------------------===//
18 :
19 : #ifndef LLVM_CODEGEN_SLOTINDEXES_H
20 : #define LLVM_CODEGEN_SLOTINDEXES_H
21 :
22 : #include "llvm/ADT/DenseMap.h"
23 : #include "llvm/ADT/IntervalMap.h"
24 : #include "llvm/ADT/PointerIntPair.h"
25 : #include "llvm/ADT/SmallVector.h"
26 : #include "llvm/ADT/ilist.h"
27 : #include "llvm/CodeGen/MachineBasicBlock.h"
28 : #include "llvm/CodeGen/MachineFunction.h"
29 : #include "llvm/CodeGen/MachineFunctionPass.h"
30 : #include "llvm/CodeGen/MachineInstr.h"
31 : #include "llvm/CodeGen/MachineInstrBundle.h"
32 : #include "llvm/Pass.h"
33 : #include "llvm/Support/Allocator.h"
34 : #include <algorithm>
35 : #include <cassert>
36 : #include <iterator>
37 : #include <utility>
38 :
39 : namespace llvm {
40 :
41 : class raw_ostream;
42 :
43 : /// This class represents an entry in the slot index list held in the
44 : /// SlotIndexes pass. It should not be used directly. See the
45 : /// SlotIndex & SlotIndexes classes for the public interface to this
46 : /// information.
47 : class IndexListEntry : public ilist_node<IndexListEntry> {
48 : MachineInstr *mi;
49 : unsigned index;
50 :
51 : public:
52 12255926 : IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {}
53 :
54 0 : MachineInstr* getInstr() const { return mi; }
55 0 : void setInstr(MachineInstr *mi) {
56 1863071 : this->mi = mi;
57 0 : }
58 :
59 0 : unsigned getIndex() const { return index; }
60 0 : void setIndex(unsigned index) {
61 4443156 : this->index = index;
62 0 : }
63 :
64 : #ifdef EXPENSIVE_CHECKS
65 : // When EXPENSIVE_CHECKS is defined, "erased" index list entries will
66 : // actually be moved to a "graveyard" list, and have their pointers
67 : // poisoned, so that dangling SlotIndex access can be reliably detected.
68 : void setPoison() {
69 : intptr_t tmp = reinterpret_cast<intptr_t>(mi);
70 : assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?");
71 : tmp |= 0x1;
72 : mi = reinterpret_cast<MachineInstr*>(tmp);
73 : }
74 :
75 : bool isPoisoned() const { return (reinterpret_cast<intptr_t>(mi) & 0x1) == 0x1; }
76 : #endif // EXPENSIVE_CHECKS
77 : };
78 :
79 : template <>
80 : struct ilist_alloc_traits<IndexListEntry>
81 : : public ilist_noalloc_traits<IndexListEntry> {};
82 :
83 : /// SlotIndex - An opaque wrapper around machine indexes.
84 : class SlotIndex {
85 : friend class SlotIndexes;
86 :
87 : enum Slot {
88 : /// Basic block boundary. Used for live ranges entering and leaving a
89 : /// block without being live in the layout neighbor. Also used as the
90 : /// def slot of PHI-defs.
91 : Slot_Block,
92 :
93 : /// Early-clobber register use/def slot. A live range defined at
94 : /// Slot_EarlyClobber interferes with normal live ranges killed at
95 : /// Slot_Register. Also used as the kill slot for live ranges tied to an
96 : /// early-clobber def.
97 : Slot_EarlyClobber,
98 :
99 : /// Normal register use/def slot. Normal instructions kill and define
100 : /// register live ranges at this slot.
101 : Slot_Register,
102 :
103 : /// Dead def kill point. Kill slot for a live range that is defined by
104 : /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't
105 : /// used anywhere.
106 : Slot_Dead,
107 :
108 : Slot_Count
109 : };
110 :
111 : PointerIntPair<IndexListEntry*, 2, unsigned> lie;
112 :
113 : SlotIndex(IndexListEntry *entry, unsigned slot)
114 : : lie(entry, slot) {}
115 :
116 : IndexListEntry* listEntry() const {
117 : assert(isValid() && "Attempt to compare reserved index.");
118 : #ifdef EXPENSIVE_CHECKS
119 : assert(!lie.getPointer()->isPoisoned() &&
120 : "Attempt to access deleted list-entry.");
121 : #endif // EXPENSIVE_CHECKS
122 349761437 : return lie.getPointer();
123 : }
124 :
125 : unsigned getIndex() const {
126 1923726476 : return listEntry()->getIndex() | getSlot();
127 : }
128 :
129 : /// Returns the slot for this SlotIndex.
130 : Slot getSlot() const {
131 45167803 : return static_cast<Slot>(lie.getInt());
132 : }
133 :
134 : public:
135 : enum {
136 : /// The default distance between instructions as returned by distance().
137 : /// This may vary as instructions are inserted and removed.
138 : InstrDist = 4 * Slot_Count
139 : };
140 :
141 : /// Construct an invalid index.
142 : SlotIndex() = default;
143 :
144 : // Construct a new slot index from the given one, and set the slot.
145 : SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) {
146 : assert(lie.getPointer() != nullptr &&
147 : "Attempt to construct index with 0 pointer.");
148 : }
149 :
150 : /// Returns true if this is a valid index. Invalid indices do
151 : /// not point into an index table, and cannot be compared.
152 : bool isValid() const {
153 60489269 : return lie.getPointer();
154 : }
155 :
156 : /// Return true for a valid index.
157 : explicit operator bool() const { return isValid(); }
158 :
159 : /// Print this index to the given raw_ostream.
160 : void print(raw_ostream &os) const;
161 :
162 : /// Dump this index to stderr.
163 : void dump() const;
164 :
165 : /// Compare two SlotIndex objects for equality.
166 : bool operator==(SlotIndex other) const {
167 18513331 : return lie == other.lie;
168 : }
169 : /// Compare two SlotIndex objects for inequality.
170 : bool operator!=(SlotIndex other) const {
171 8096671 : return lie != other.lie;
172 : }
173 :
174 : /// Compare two SlotIndex objects. Return true if the first index
175 : /// is strictly lower than the second.
176 : bool operator<(SlotIndex other) const {
177 1464 : return getIndex() < other.getIndex();
178 : }
179 : /// Compare two SlotIndex objects. Return true if the first index
180 : /// is lower than, or equal to, the second.
181 : bool operator<=(SlotIndex other) const {
182 124663 : return getIndex() <= other.getIndex();
183 : }
184 :
185 : /// Compare two SlotIndex objects. Return true if the first index
186 : /// is greater than the second.
187 : bool operator>(SlotIndex other) const {
188 781 : return getIndex() > other.getIndex();
189 : }
190 :
191 : /// Compare two SlotIndex objects. Return true if the first index
192 : /// is greater than, or equal to, the second.
193 : bool operator>=(SlotIndex other) const {
194 132 : return getIndex() >= other.getIndex();
195 : }
196 :
197 : /// isSameInstr - Return true if A and B refer to the same instruction.
198 324326 : static bool isSameInstr(SlotIndex A, SlotIndex B) {
199 1003325 : return A.lie.getPointer() == B.lie.getPointer();
200 : }
201 :
202 : /// isEarlierInstr - Return true if A refers to an instruction earlier than
203 : /// B. This is equivalent to A < B && !isSameInstr(A, B).
204 : static bool isEarlierInstr(SlotIndex A, SlotIndex B) {
205 16229373 : return A.listEntry()->getIndex() < B.listEntry()->getIndex();
206 : }
207 :
208 : /// Return true if A refers to the same instruction as B or an earlier one.
209 : /// This is equivalent to !isEarlierInstr(B, A).
210 : static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B) {
211 : return !isEarlierInstr(B, A);
212 : }
213 :
214 : /// Return the distance from this index to the given one.
215 : int distance(SlotIndex other) const {
216 6365482 : return other.getIndex() - getIndex();
217 : }
218 :
219 : /// Return the scaled distance from this index to the given one, where all
220 : /// slots on the same instruction have zero distance.
221 : int getInstrDistance(SlotIndex other) const {
222 1208881 : return (other.listEntry()->getIndex() - listEntry()->getIndex())
223 1208881 : / Slot_Count;
224 : }
225 :
226 : /// isBlock - Returns true if this is a block boundary slot.
227 : bool isBlock() const { return getSlot() == Slot_Block; }
228 :
229 : /// isEarlyClobber - Returns true if this is an early-clobber slot.
230 : bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; }
231 :
232 : /// isRegister - Returns true if this is a normal register use/def slot.
233 : /// Note that early-clobber slots may also be used for uses and defs.
234 : bool isRegister() const { return getSlot() == Slot_Register; }
235 :
236 : /// isDead - Returns true if this is a dead def kill slot.
237 : bool isDead() const { return getSlot() == Slot_Dead; }
238 :
239 : /// Returns the base index for associated with this index. The base index
240 : /// is the one associated with the Slot_Block slot for the instruction
241 : /// pointed to by this index.
242 : SlotIndex getBaseIndex() const {
243 : return SlotIndex(listEntry(), Slot_Block);
244 : }
245 :
246 : /// Returns the boundary index for associated with this index. The boundary
247 : /// index is the one associated with the Slot_Block slot for the instruction
248 : /// pointed to by this index.
249 : SlotIndex getBoundaryIndex() const {
250 : return SlotIndex(listEntry(), Slot_Dead);
251 : }
252 :
253 : /// Returns the register use/def slot in the current instruction for a
254 : /// normal or early-clobber def.
255 : SlotIndex getRegSlot(bool EC = false) const {
256 14623389 : return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register);
257 : }
258 :
259 : /// Returns the dead def kill slot for the current instruction.
260 : SlotIndex getDeadSlot() const {
261 : return SlotIndex(listEntry(), Slot_Dead);
262 : }
263 :
264 : /// Returns the next slot in the index list. This could be either the
265 : /// next slot for the instruction pointed to by this index or, if this
266 : /// index is a STORE, the first slot for the next instruction.
267 : /// WARNING: This method is considerably more expensive than the methods
268 : /// that return specific slots (getUseIndex(), etc). If you can - please
269 : /// use one of those methods.
270 : SlotIndex getNextSlot() const {
271 : Slot s = getSlot();
272 444985 : if (s == Slot_Dead) {
273 : return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
274 : }
275 437664 : return SlotIndex(listEntry(), s + 1);
276 : }
277 :
278 : /// Returns the next index. This is the index corresponding to the this
279 : /// index's slot, but for the next instruction.
280 : SlotIndex getNextIndex() const {
281 : return SlotIndex(&*++listEntry()->getIterator(), getSlot());
282 : }
283 :
284 : /// Returns the previous slot in the index list. This could be either the
285 : /// previous slot for the instruction pointed to by this index or, if this
286 : /// index is a Slot_Block, the last slot for the previous instruction.
287 : /// WARNING: This method is considerably more expensive than the methods
288 : /// that return specific slots (getUseIndex(), etc). If you can - please
289 : /// use one of those methods.
290 : SlotIndex getPrevSlot() const {
291 : Slot s = getSlot();
292 27204652 : if (s == Slot_Block) {
293 : return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
294 : }
295 24026415 : return SlotIndex(listEntry(), s - 1);
296 : }
297 :
298 : /// Returns the previous index. This is the index corresponding to this
299 : /// index's slot, but for the previous instruction.
300 : SlotIndex getPrevIndex() const {
301 : return SlotIndex(&*--listEntry()->getIterator(), getSlot());
302 : }
303 : };
304 :
305 : template <> struct isPodLike<SlotIndex> { static const bool value = true; };
306 :
307 : inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) {
308 6434 : li.print(os);
309 : return os;
310 : }
311 :
312 : using IdxMBBPair = std::pair<SlotIndex, MachineBasicBlock *>;
313 :
314 : inline bool operator<(SlotIndex V, const IdxMBBPair &IM) {
315 : return V < IM.first;
316 : }
317 :
318 : inline bool operator<(const IdxMBBPair &IM, SlotIndex V) {
319 : return IM.first < V;
320 : }
321 :
322 : struct Idx2MBBCompare {
323 0 : bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
324 0 : return LHS.first < RHS.first;
325 : }
326 : };
327 :
328 : /// SlotIndexes pass.
329 : ///
330 : /// This pass assigns indexes to each instruction.
331 : class SlotIndexes : public MachineFunctionPass {
332 : private:
333 : // IndexListEntry allocator.
334 : BumpPtrAllocator ileAllocator;
335 :
336 : using IndexList = ilist<IndexListEntry>;
337 : IndexList indexList;
338 :
339 : #ifdef EXPENSIVE_CHECKS
340 : IndexList graveyardList;
341 : #endif // EXPENSIVE_CHECKS
342 :
343 : MachineFunction *mf;
344 :
345 : using Mi2IndexMap = DenseMap<const MachineInstr *, SlotIndex>;
346 : Mi2IndexMap mi2iMap;
347 :
348 : /// MBBRanges - Map MBB number to (start, stop) indexes.
349 : SmallVector<std::pair<SlotIndex, SlotIndex>, 8> MBBRanges;
350 :
351 : /// Idx2MBBMap - Sorted list of pairs of index of first instruction
352 : /// and MBB id.
353 : SmallVector<IdxMBBPair, 8> idx2MBBMap;
354 :
355 : IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
356 : IndexListEntry *entry =
357 11925582 : static_cast<IndexListEntry *>(ileAllocator.Allocate(
358 : sizeof(IndexListEntry), alignof(IndexListEntry)));
359 :
360 : new (entry) IndexListEntry(mi, index);
361 :
362 : return entry;
363 : }
364 :
365 : /// Renumber locally after inserting curItr.
366 : void renumberIndexes(IndexList::iterator curItr);
367 :
368 : public:
369 : static char ID;
370 :
371 44429 : SlotIndexes() : MachineFunctionPass(ID) {
372 44429 : initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
373 44429 : }
374 :
375 132376 : ~SlotIndexes() override {
376 : // The indexList's nodes are all allocated in the BumpPtrAllocator.
377 : indexList.clearAndLeakNodesUnsafely();
378 88251 : }
379 44125 :
380 : void getAnalysisUsage(AnalysisUsage &au) const override;
381 : void releaseMemory() override;
382 44125 :
383 88251 : bool runOnMachineFunction(MachineFunction &fn) override;
384 :
385 : /// Dump the indexes.
386 44126 : void dump() const;
387 :
388 : /// Renumber the index list, providing space for new instructions.
389 : void renumberIndexes();
390 :
391 : /// Repair indexes after adding and removing instructions.
392 : void repairIndexesInRange(MachineBasicBlock *MBB,
393 : MachineBasicBlock::iterator Begin,
394 : MachineBasicBlock::iterator End);
395 :
396 : /// Returns the zero index for this analysis.
397 : SlotIndex getZeroIndex() {
398 : assert(indexList.front().getIndex() == 0 && "First index is not 0?");
399 : return SlotIndex(&indexList.front(), 0);
400 : }
401 :
402 : /// Returns the base index of the last slot in this analysis.
403 : SlotIndex getLastIndex() {
404 : return SlotIndex(&indexList.back(), 0);
405 : }
406 :
407 : /// Returns true if the given machine instr is mapped to an index,
408 : /// otherwise returns false.
409 : bool hasIndex(const MachineInstr &instr) const {
410 28772564 : return mi2iMap.count(&instr);
411 : }
412 :
413 : /// Returns the base index for the given instruction.
414 50734568 : SlotIndex getInstructionIndex(const MachineInstr &MI) const {
415 : // Instructions inside a bundle have the same number as the bundle itself.
416 50734568 : const MachineInstr &BundleStart = *getBundleStart(MI.getIterator());
417 : assert(!BundleStart.isDebugInstr() &&
418 88 : "Could not use a debug instruction to query mi2iMap.");
419 50734568 : Mi2IndexMap::const_iterator itr = mi2iMap.find(&BundleStart);
420 : assert(itr != mi2iMap.end() && "Instruction not found in maps.");
421 50734568 : return itr->second;
422 44 : }
423 :
424 44 : /// Returns the instruction for the given index, or null if the given
425 : /// index has no instruction associated with it.
426 0 : MachineInstr* getInstructionFromIndex(SlotIndex index) const {
427 50240445 : return index.isValid() ? index.listEntry()->getInstr() : nullptr;
428 : }
429 44 :
430 : /// Returns the next non-null index, if one exists.
431 : /// Otherwise returns getLastIndex().
432 : SlotIndex getNextNonNullIndex(SlotIndex Index) {
433 1668518 : IndexList::iterator I = Index.listEntry()->getIterator();
434 : IndexList::iterator E = indexList.end();
435 2429214 : while (++I != E)
436 2429203 : if (I->getInstr())
437 : return SlotIndex(&*I, Index.getSlot());
438 : // We reached the end of the function.
439 : return getLastIndex();
440 : }
441 :
442 : /// getIndexBefore - Returns the index of the last indexed instruction
443 : /// before MI, or the start index of its basic block.
444 : /// MI is not required to have an index.
445 299312 : SlotIndex getIndexBefore(const MachineInstr &MI) const {
446 299312 : const MachineBasicBlock *MBB = MI.getParent();
447 : assert(MBB && "MI must be inserted inna basic block");
448 : MachineBasicBlock::const_iterator I = MI, B = MBB->begin();
449 : while (true) {
450 299655 : if (I == B)
451 299312 : return getMBBStartIdx(MBB);
452 : --I;
453 573755 : Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
454 286944 : if (MapItr != mi2iMap.end())
455 286468 : return MapItr->second;
456 343 : }
457 : }
458 396 :
459 133 : /// getIndexAfter - Returns the index of the first indexed instruction
460 : /// after MI, or the end index of its basic block.
461 792 : /// MI is not required to have an index.
462 31182 : SlotIndex getIndexAfter(const MachineInstr &MI) const {
463 30919 : const MachineBasicBlock *MBB = MI.getParent();
464 263 : assert(MBB && "MI must be inserted inna basic block");
465 : MachineBasicBlock::const_iterator I = MI, E = MBB->end();
466 : while (true) {
467 : ++I;
468 30786 : if (I == E)
469 30786 : return getMBBEndIdx(MBB);
470 29355 : Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
471 29355 : if (MapItr != mi2iMap.end())
472 29355 : return MapItr->second;
473 0 : }
474 : }
475 :
476 0 : /// Return the (start,end) range of the given basic block number.
477 0 : const std::pair<SlotIndex, SlotIndex> &
478 0 : getMBBRange(unsigned Num) const {
479 17740185 : return MBBRanges[Num];
480 0 : }
481 0 :
482 : /// Return the (start,end) range of the given basic block.
483 : const std::pair<SlotIndex, SlotIndex> &
484 : getMBBRange(const MachineBasicBlock *MBB) const {
485 22328821 : return getMBBRange(MBB->getNumber());
486 : }
487 10 :
488 : /// Returns the first index in the given basic block number.
489 : SlotIndex getMBBStartIdx(unsigned Num) const {
490 639025 : return getMBBRange(Num).first;
491 : }
492 :
493 10 : /// Returns the first index in the given basic block.
494 : SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
495 14447984 : return getMBBRange(mbb).first;
496 : }
497 :
498 : /// Returns the last index in the given basic block number.
499 : SlotIndex getMBBEndIdx(unsigned Num) const {
500 : return getMBBRange(Num).second;
501 : }
502 :
503 10 : /// Returns the last index in the given basic block.
504 : SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
505 7510248 : return getMBBRange(mbb).second;
506 : }
507 :
508 : /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
509 : /// begin and basic block)
510 : using MBBIndexIterator = SmallVectorImpl<IdxMBBPair>::const_iterator;
511 :
512 : /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or
513 0 : /// equal to \p To.
514 : MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const {
515 : return std::lower_bound(I, idx2MBBMap.end(), To);
516 : }
517 :
518 : /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex
519 : /// that is greater or equal to \p Idx.
520 : MBBIndexIterator findMBBIndex(SlotIndex Idx) const {
521 1422790 : return advanceMBBIndex(idx2MBBMap.begin(), Idx);
522 : }
523 :
524 : /// Returns an iterator for the begin of the idx2MBBMap.
525 : MBBIndexIterator MBBIndexBegin() const {
526 : return idx2MBBMap.begin();
527 : }
528 :
529 : /// Return an iterator for the end of the idx2MBBMap.
530 : MBBIndexIterator MBBIndexEnd() const {
531 : return idx2MBBMap.end();
532 : }
533 :
534 : /// Returns the basic block which the given index falls in.
535 32042730 : MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
536 32042730 : if (MachineInstr *MI = getInstructionFromIndex(index))
537 30619940 : return MI->getParent();
538 :
539 : MBBIndexIterator I = findMBBIndex(index);
540 : // Take the pair containing the index
541 : MBBIndexIterator J =
542 1422790 : ((I != MBBIndexEnd() && I->first > index) ||
543 1520454 : (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I;
544 :
545 : assert(J != MBBIndexEnd() && J->first <= index &&
546 : index < getMBBEndIdx(J->second) &&
547 : "index does not correspond to an MBB");
548 1422790 : return J->second;
549 : }
550 :
551 : /// Returns the MBB covering the given range, or null if the range covers
552 : /// more than one basic block.
553 : MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
554 :
555 : assert(start < end && "Backwards ranges not allowed.");
556 : MBBIndexIterator itr = findMBBIndex(start);
557 : if (itr == MBBIndexEnd()) {
558 : itr = std::prev(itr);
559 : return itr->second;
560 : }
561 :
562 : // Check that we don't cross the boundary into this block.
563 : if (itr->first < end)
564 : return nullptr;
565 :
566 : itr = std::prev(itr);
567 :
568 : if (itr->first <= start)
569 : return itr->second;
570 :
571 : return nullptr;
572 : }
573 :
574 : /// Insert the given machine instruction into the mapping. Returns the
575 : /// assigned index.
576 : /// If Late is set and there are null indexes between mi's neighboring
577 : /// instructions, create the new index after the null indexes instead of
578 : /// before them.
579 330078 : SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late = false) {
580 : assert(!MI.isInsideBundle() &&
581 : "Instructions inside bundles should use bundle start's slot.");
582 : assert(mi2iMap.find(&MI) == mi2iMap.end() && "Instr already indexed.");
583 : // Numbering debug instructions could cause code generation to be
584 : // affected by debug information.
585 : assert(!MI.isDebugInstr() && "Cannot number debug instructions.");
586 :
587 133 : assert(MI.getParent() != nullptr && "Instr must be added to function.");
588 :
589 : // Get the entries where MI should be inserted.
590 : IndexList::iterator prevItr, nextItr;
591 330078 : if (Late) {
592 : // Insert MI's index immediately before the following instruction.
593 30786 : nextItr = getIndexAfter(MI).listEntry()->getIterator();
594 : prevItr = std::prev(nextItr);
595 : } else {
596 : // Insert MI's index immediately after the preceding instruction.
597 299292 : prevItr = getIndexBefore(MI).listEntry()->getIterator();
598 : nextItr = std::next(prevItr);
599 133 : }
600 :
601 0 : // Get a number for the new instr, or 0 if there's no room currently.
602 : // In the latter case we'll force a renumber later.
603 330078 : unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
604 330078 : unsigned newNumber = prevItr->getIndex() + dist;
605 133 :
606 : // Insert a new list entry for MI.
607 : IndexList::iterator newItr =
608 : indexList.insert(nextItr, createEntry(&MI, newNumber));
609 :
610 : // Renumber locally if we need to.
611 330211 : if (dist == 0)
612 51768 : renumberIndexes(newItr);
613 :
614 : SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
615 330078 : mi2iMap.insert(std::make_pair(&MI, newIndex));
616 330078 : return newIndex;
617 : }
618 :
619 133 : /// Removes machine instruction (bundle) \p MI from the mapping.
620 53 : /// This should be called before MachineInstr::eraseFromParent() is used to
621 : /// remove a whole bundle or an unbundled instruction.
622 : void removeMachineInstrFromMaps(MachineInstr &MI);
623 133 :
624 133 : /// Removes a single machine instruction \p MI from the mapping.
625 : /// This should be called before MachineInstr::eraseFromBundle() is used to
626 : /// remove a single instruction (out of a bundle).
627 : void removeSingleMachineInstrFromMaps(MachineInstr &MI);
628 :
629 : /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
630 : /// maps used by register allocator. \returns the index where the new
631 : /// instruction was inserted.
632 68467 : SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) {
633 68467 : Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
634 68467 : if (mi2iItr == mi2iMap.end())
635 0 : return SlotIndex();
636 68467 : SlotIndex replaceBaseIndex = mi2iItr->second;
637 : IndexListEntry *miEntry(replaceBaseIndex.listEntry());
638 : assert(miEntry->getInstr() == &MI &&
639 : "Mismatched instruction in index tables.");
640 : miEntry->setInstr(&NewMI);
641 : mi2iMap.erase(mi2iItr);
642 68467 : mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex));
643 68467 : return replaceBaseIndex;
644 : }
645 :
646 : /// Add the given MachineBasicBlock into the maps.
647 0 : void insertMBBInMaps(MachineBasicBlock *mbb) {
648 : MachineFunction::iterator nextMBB =
649 : std::next(MachineFunction::iterator(mbb));
650 :
651 : IndexListEntry *startEntry = nullptr;
652 : IndexListEntry *endEntry = nullptr;
653 : IndexList::iterator newItr;
654 0 : if (nextMBB == mbb->getParent()->end()) {
655 : startEntry = &indexList.back();
656 : endEntry = createEntry(nullptr, 0);
657 0 : newItr = indexList.insertAfter(startEntry->getIterator(), endEntry);
658 : } else {
659 : startEntry = createEntry(nullptr, 0);
660 : endEntry = getMBBStartIdx(&*nextMBB).listEntry();
661 0 : newItr = indexList.insert(endEntry->getIterator(), startEntry);
662 : }
663 :
664 : SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
665 : SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
666 :
667 : MachineFunction::iterator prevMBB(mbb);
668 : assert(prevMBB != mbb->getParent()->end() &&
669 : "Can't insert a new block at the beginning of a function.");
670 : --prevMBB;
671 0 : MBBRanges[prevMBB->getNumber()].second = startIdx;
672 :
673 : assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
674 : "Blocks must be added in order");
675 0 : MBBRanges.push_back(std::make_pair(startIdx, endIdx));
676 0 : idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
677 :
678 0 : renumberIndexes(newItr);
679 : llvm::sort(idx2MBBMap, Idx2MBBCompare());
680 0 : }
681 :
682 : /// Free the resources that were required to maintain a SlotIndex.
683 : ///
684 : /// Once an index is no longer needed (for instance because the instruction
685 : /// at that index has been moved), the resources required to maintain the
686 : /// index can be relinquished to reduce memory use and improve renumbering
687 : /// performance. Any remaining SlotIndex objects that point to the same
688 : /// index are left 'dangling' (much the same as a dangling pointer to a
689 : /// freed object) and should not be accessed, except to destruct them.
690 : ///
691 : /// Like dangling pointers, access to dangling SlotIndexes can cause
692 : /// painful-to-track-down bugs, especially if the memory for the index
693 : /// previously pointed to has been re-used. To detect dangling SlotIndex
694 : /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to
695 : /// be retained in a graveyard instead of being freed. Operations on indexes
696 : /// in the graveyard will trigger an assertion.
697 : void eraseIndex(SlotIndex index) {
698 : IndexListEntry *entry = index.listEntry();
699 : #ifdef EXPENSIVE_CHECKS
700 : indexList.remove(entry);
701 : graveyardList.push_back(entry);
702 : entry->setPoison();
703 : #else
704 : indexList.erase(entry);
705 : #endif
706 : }
707 : };
708 :
709 : // Specialize IntervalMapInfo for half-open slot index intervals.
710 : template <>
711 : struct IntervalMapInfo<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> {
712 : };
713 :
714 : } // end namespace llvm
715 :
716 : #endif // LLVM_CODEGEN_SLOTINDEXES_H
|
