LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - SlotIndexes.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 105 132 79.5 %
Date: 2018-10-20 13:21:21 Functions: 10 17 58.8 %
Legend: Lines: hit not hit

          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

Generated by: LCOV version 1.13