LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - SlotIndexes.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 122 145 84.1 %
Date: 2017-09-14 15:23:50 Functions: 10 11 90.9 %
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    19820638 :     IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {}
      53             : 
      54             :     MachineInstr* getInstr() const { return mi; }
      55             :     void setInstr(MachineInstr *mi) {
      56     1548091 :       this->mi = mi;
      57             :     }
      58             : 
      59             :     unsigned getIndex() const { return index; }
      60             :     void setIndex(unsigned index) {
      61     4446157 :       this->index = index;
      62             :     }
      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   373905084 :       : 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  2772965352 :       return lie.getPointer();
     123             :     }
     124             : 
     125             :     unsigned getIndex() const {
     126  2220824128 :       return listEntry()->getIndex() | getSlot();
     127             :     }
     128             : 
     129             :     /// Returns the slot for this SlotIndex.
     130             :     Slot getSlot() const {
     131  2428011518 :       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   294460348 :     SlotIndex() : lie(nullptr, 0) {}
     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   192375428 :       return lie.getPointer();
     154             :     }
     155             : 
     156             :     /// Return true for a valid index.
     157      802174 :     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    59988963 :       return lie == other.lie;
     168             :     }
     169             :     /// Compare two SlotIndex objects for inequality.
     170             :     bool operator!=(SlotIndex other) const {
     171    20650588 :       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   462033168 :       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   352800880 :       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    71467444 :       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   213563824 :       return getIndex() >= other.getIndex();
     195             :     }
     196             : 
     197             :     /// isSameInstr - Return true if A and B refer to the same instruction.
     198      312179 :     static bool isSameInstr(SlotIndex A, SlotIndex B) {
     199    48594404 :       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    45924744 :       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    10546748 :       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     2097080 :       return (other.listEntry()->getIndex() - listEntry()->getIndex())
     223     1048540 :         / Slot_Count;
     224             :     }
     225             : 
     226             :     /// isBlock - Returns true if this is a block boundary slot.
     227    43605399 :     bool isBlock() const { return getSlot() == Slot_Block; }
     228             : 
     229             :     /// isEarlyClobber - Returns true if this is an early-clobber slot.
     230     2960936 :     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     2254203 :     bool isRegister() const { return getSlot() == Slot_Register; }
     235             : 
     236             :     /// isDead - Returns true if this is a dead def kill slot.
     237     5730288 :     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   155551936 :       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     1669830 :       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    83620277 :       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    23440036 :       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     1741513 :       Slot s = getSlot();
     272     1741513 :       if (s == Slot_Dead) {
     273       31495 :         return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
     274             :       }
     275     5205642 :       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       47508 :       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    45903181 :       Slot s = getSlot();
     292    45902818 :       if (s == Slot_Block) {
     293    10966090 :         return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
     294             :       }
     295   131129889 :       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       45714 :       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        5515 :     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     7804336 :     return IM.first < V;
     320             :   }
     321             : 
     322             :   struct Idx2MBBCompare {
     323             :     bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
     324     3411694 :       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      602359 :           static_cast<IndexListEntry *>(ileAllocator.Allocate(
     358     9910319 :               sizeof(IndexListEntry), alignof(IndexListEntry)));
     359             : 
     360    19820638 :       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      203532 :     SlotIndexes() : MachineFunctionPass(ID) {
     372       33922 :       initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
     373       33922 :     }
     374             : 
     375      235986 :     ~SlotIndexes() override {
     376             :       // The indexList's nodes are all allocated in the BumpPtrAllocator.
     377       67424 :       indexList.clearAndLeakNodesUnsafely();
     378       67425 :     }
     379             : 
     380             :     void getAnalysisUsage(AnalysisUsage &au) const override;
     381             :     void releaseMemory() override;
     382             : 
     383             :     bool runOnMachineFunction(MachineFunction &fn) override;
     384             : 
     385             :     /// Dump the indexes.
     386             :     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       52035 :       return SlotIndex(&indexList.front(), 0);
     400             :     }
     401             : 
     402             :     /// Returns the base index of the last slot in this analysis.
     403             :     SlotIndex getLastIndex() {
     404     3145656 :       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    19343428 :       return mi2iMap.count(&instr);
     411             :     }
     412             : 
     413             :     /// Returns the base index for the given instruction.
     414    47092354 :     SlotIndex getInstructionIndex(const MachineInstr &MI) const {
     415             :       // Instructions inside a bundle have the same number as the bundle itself.
     416   188369416 :       const MachineInstr &BundleStart = *getBundleStart(MI.getIterator());
     417    47092354 :       Mi2IndexMap::const_iterator itr = mi2iMap.find(&BundleStart);
     418             :       assert(itr != mi2iMap.end() && "Instruction not found in maps.");
     419    47092354 :       return itr->second;
     420             :     }
     421             : 
     422             :     /// Returns the instruction for the given index, or null if the given
     423             :     /// index has no instruction associated with it.
     424             :     MachineInstr* getInstructionFromIndex(SlotIndex index) const {
     425   101016720 :       return index.isValid() ? index.listEntry()->getInstr() : nullptr;
     426             :     }
     427             : 
     428             :     /// Returns the next non-null index, if one exists.
     429             :     /// Otherwise returns getLastIndex().
     430             :     SlotIndex getNextNonNullIndex(SlotIndex Index) {
     431     2754270 :       IndexList::iterator I = Index.listEntry()->getIterator();
     432     2754270 :       IndexList::iterator E = indexList.end();
     433     1933567 :       while (++I != E)
     434     1933555 :         if (I->getInstr())
     435     4131369 :           return SlotIndex(&*I, Index.getSlot());
     436             :       // We reached the end of the function.
     437             :       return getLastIndex();
     438             :     }
     439             : 
     440             :     /// getIndexBefore - Returns the index of the last indexed instruction
     441             :     /// before MI, or the start index of its basic block.
     442             :     /// MI is not required to have an index.
     443      276064 :     SlotIndex getIndexBefore(const MachineInstr &MI) const {
     444      276064 :       const MachineBasicBlock *MBB = MI.getParent();
     445             :       assert(MBB && "MI must be inserted inna basic block");
     446      552128 :       MachineBasicBlock::const_iterator I = MI, B = MBB->begin();
     447             :       while (true) {
     448      276324 :         if (I == B)
     449      276064 :           return getMBBStartIdx(MBB);
     450      264444 :         --I;
     451      528888 :         Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
     452      528888 :         if (MapItr != mi2iMap.end())
     453      264184 :           return MapItr->second;
     454         260 :       }
     455             :     }
     456             : 
     457             :     /// getIndexAfter - Returns the index of the first indexed instruction
     458             :     /// after MI, or the end index of its basic block.
     459             :     /// MI is not required to have an index.
     460       33131 :     SlotIndex getIndexAfter(const MachineInstr &MI) const {
     461       33131 :       const MachineBasicBlock *MBB = MI.getParent();
     462             :       assert(MBB && "MI must be inserted inna basic block");
     463       66262 :       MachineBasicBlock::const_iterator I = MI, E = MBB->end();
     464             :       while (true) {
     465       33131 :         ++I;
     466       33131 :         if (I == E)
     467       33131 :           return getMBBEndIdx(MBB);
     468       63928 :         Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
     469       63928 :         if (MapItr != mi2iMap.end())
     470       31964 :           return MapItr->second;
     471           0 :       }
     472             :     }
     473             : 
     474             :     /// Return the (start,end) range of the given basic block number.
     475             :     const std::pair<SlotIndex, SlotIndex> &
     476             :     getMBBRange(unsigned Num) const {
     477    69507626 :       return MBBRanges[Num];
     478             :     }
     479             : 
     480             :     /// Return the (start,end) range of the given basic block.
     481             :     const std::pair<SlotIndex, SlotIndex> &
     482             :     getMBBRange(const MachineBasicBlock *MBB) const {
     483    61140380 :       return getMBBRange(MBB->getNumber());
     484             :     }
     485             : 
     486             :     /// Returns the first index in the given basic block number.
     487             :     SlotIndex getMBBStartIdx(unsigned Num) const {
     488     1192038 :       return getMBBRange(Num).first;
     489             :     }
     490             : 
     491             :     /// Returns the first index in the given basic block.
     492             :     SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
     493    23135336 :       return getMBBRange(mbb).first;
     494             :     }
     495             : 
     496             :     /// Returns the last index in the given basic block number.
     497             :     SlotIndex getMBBEndIdx(unsigned Num) const {
     498             :       return getMBBRange(Num).second;
     499             :     }
     500             : 
     501             :     /// Returns the last index in the given basic block.
     502             :     SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
     503     5123075 :       return getMBBRange(mbb).second;
     504             :     }
     505             : 
     506             :     /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
     507             :     /// begin and basic block)
     508             :     using MBBIndexIterator = SmallVectorImpl<IdxMBBPair>::const_iterator;
     509             : 
     510             :     /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or
     511             :     /// equal to \p To.
     512             :     MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const {
     513     3522945 :       return std::lower_bound(I, idx2MBBMap.end(), To);
     514             :     }
     515             : 
     516             :     /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex
     517             :     /// that is greater or equal to \p Idx.
     518             :     MBBIndexIterator findMBBIndex(SlotIndex Idx) const {
     519     2823141 :       return advanceMBBIndex(idx2MBBMap.begin(), Idx);
     520             :     }
     521             : 
     522             :     /// Returns an iterator for the begin of the idx2MBBMap.
     523             :     MBBIndexIterator MBBIndexBegin() const {
     524      164786 :       return idx2MBBMap.begin();
     525             :     }
     526             : 
     527             :     /// Return an iterator for the end of the idx2MBBMap.
     528             :     MBBIndexIterator MBBIndexEnd() const {
     529     3016792 :       return idx2MBBMap.end();
     530             :     }
     531             : 
     532             :     /// Returns the basic block which the given index falls in.
     533    37067351 :     MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
     534    74134702 :       if (MachineInstr *MI = getInstructionFromIndex(index))
     535    36126981 :         return MI->getParent();
     536             : 
     537      940370 :       MBBIndexIterator I = findMBBIndex(index);
     538             :       // Take the pair containing the index
     539             :       MBBIndexIterator J =
     540     3625134 :         ((I != MBBIndexEnd() && I->first > index) ||
     541     1980458 :          (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I;
     542             : 
     543             :       assert(J != MBBIndexEnd() && J->first <= index &&
     544             :              index < getMBBEndIdx(J->second) &&
     545             :              "index does not correspond to an MBB");
     546      940370 :       return J->second;
     547             :     }
     548             : 
     549             :     /// Returns the MBB covering the given range, or null if the range covers
     550             :     /// more than one basic block.
     551             :     MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
     552             : 
     553             :       assert(start < end && "Backwards ranges not allowed.");
     554             :       MBBIndexIterator itr = findMBBIndex(start);
     555             :       if (itr == MBBIndexEnd()) {
     556             :         itr = std::prev(itr);
     557             :         return itr->second;
     558             :       }
     559             : 
     560             :       // Check that we don't cross the boundary into this block.
     561             :       if (itr->first < end)
     562             :         return nullptr;
     563             : 
     564             :       itr = std::prev(itr);
     565             : 
     566             :       if (itr->first <= start)
     567             :         return itr->second;
     568             : 
     569             :       return nullptr;
     570             :     }
     571             : 
     572             :     /// Insert the given machine instruction into the mapping. Returns the
     573             :     /// assigned index.
     574             :     /// If Late is set and there are null indexes between mi's neighboring
     575             :     /// instructions, create the new index after the null indexes instead of
     576             :     /// before them.
     577      309192 :     SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late = false) {
     578             :       assert(!MI.isInsideBundle() &&
     579             :              "Instructions inside bundles should use bundle start's slot.");
     580             :       assert(mi2iMap.find(&MI) == mi2iMap.end() && "Instr already indexed.");
     581             :       // Numbering DBG_VALUE instructions could cause code generation to be
     582             :       // affected by debug information.
     583             :       assert(!MI.isDebugValue() && "Cannot number DBG_VALUE instructions.");
     584             : 
     585             :       assert(MI.getParent() != nullptr && "Instr must be added to function.");
     586             : 
     587             :       // Get the entries where MI should be inserted.
     588      309192 :       IndexList::iterator prevItr, nextItr;
     589      309192 :       if (Late) {
     590             :         // Insert MI's index immediately before the following instruction.
     591       99393 :         nextItr = getIndexAfter(MI).listEntry()->getIterator();
     592             :         prevItr = std::prev(nextItr);
     593             :       } else {
     594             :         // Insert MI's index immediately after the preceding instruction.
     595      828183 :         prevItr = getIndexBefore(MI).listEntry()->getIterator();
     596             :         nextItr = std::next(prevItr);
     597             :       }
     598             : 
     599             :       // Get a number for the new instr, or 0 if there's no room currently.
     600             :       // In the latter case we'll force a renumber later.
     601      618384 :       unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
     602      309192 :       unsigned newNumber = prevItr->getIndex() + dist;
     603             : 
     604             :       // Insert a new list entry for MI.
     605             :       IndexList::iterator newItr =
     606      927576 :           indexList.insert(nextItr, createEntry(&MI, newNumber));
     607             : 
     608             :       // Renumber locally if we need to.
     609      309192 :       if (dist == 0)
     610       52267 :         renumberIndexes(newItr);
     611             : 
     612      618384 :       SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
     613     1236768 :       mi2iMap.insert(std::make_pair(&MI, newIndex));
     614      309192 :       return newIndex;
     615             :     }
     616             : 
     617             :     /// Removes machine instruction (bundle) \p MI from the mapping.
     618             :     /// This should be called before MachineInstr::eraseFromParent() is used to
     619             :     /// remove a whole bundle or an unbundled instruction.
     620             :     void removeMachineInstrFromMaps(MachineInstr &MI);
     621             : 
     622             :     /// Removes a single machine instruction \p MI from the mapping.
     623             :     /// This should be called before MachineInstr::eraseFromBundle() is used to
     624             :     /// remove a single instruction (out of a bundle).
     625             :     void removeSingleMachineInstrFromMaps(MachineInstr &MI);
     626             : 
     627             :     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
     628             :     /// maps used by register allocator. \returns the index where the new
     629             :     /// instruction was inserted.
     630      120039 :     SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) {
     631      120039 :       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
     632      360117 :       if (mi2iItr == mi2iMap.end())
     633           0 :         return SlotIndex();
     634      120039 :       SlotIndex replaceBaseIndex = mi2iItr->second;
     635      120039 :       IndexListEntry *miEntry(replaceBaseIndex.listEntry());
     636             :       assert(miEntry->getInstr() == &MI &&
     637             :              "Mismatched instruction in index tables.");
     638      240078 :       miEntry->setInstr(&NewMI);
     639      240078 :       mi2iMap.erase(mi2iItr);
     640      480156 :       mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex));
     641      120039 :       return replaceBaseIndex;
     642             :     }
     643             : 
     644             :     /// Add the given MachineBasicBlock into the maps.
     645           0 :     void insertMBBInMaps(MachineBasicBlock *mbb) {
     646             :       MachineFunction::iterator nextMBB =
     647           0 :         std::next(MachineFunction::iterator(mbb));
     648             : 
     649           0 :       IndexListEntry *startEntry = nullptr;
     650           0 :       IndexListEntry *endEntry = nullptr;
     651             :       IndexList::iterator newItr;
     652           0 :       if (nextMBB == mbb->getParent()->end()) {
     653           0 :         startEntry = &indexList.back();
     654           0 :         endEntry = createEntry(nullptr, 0);
     655           0 :         newItr = indexList.insertAfter(startEntry->getIterator(), endEntry);
     656             :       } else {
     657           0 :         startEntry = createEntry(nullptr, 0);
     658           0 :         endEntry = getMBBStartIdx(&*nextMBB).listEntry();
     659           0 :         newItr = indexList.insert(endEntry->getIterator(), startEntry);
     660             :       }
     661             : 
     662           0 :       SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
     663           0 :       SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
     664             : 
     665           0 :       MachineFunction::iterator prevMBB(mbb);
     666             :       assert(prevMBB != mbb->getParent()->end() &&
     667             :              "Can't insert a new block at the beginning of a function.");
     668           0 :       --prevMBB;
     669           0 :       MBBRanges[prevMBB->getNumber()].second = startIdx;
     670             : 
     671             :       assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
     672             :              "Blocks must be added in order");
     673           0 :       MBBRanges.push_back(std::make_pair(startIdx, endIdx));
     674           0 :       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
     675             : 
     676           0 :       renumberIndexes(newItr);
     677           0 :       std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
     678           0 :     }
     679             : 
     680             :     /// \brief Free the resources that were required to maintain a SlotIndex.
     681             :     ///
     682             :     /// Once an index is no longer needed (for instance because the instruction
     683             :     /// at that index has been moved), the resources required to maintain the
     684             :     /// index can be relinquished to reduce memory use and improve renumbering
     685             :     /// performance. Any remaining SlotIndex objects that point to the same
     686             :     /// index are left 'dangling' (much the same as a dangling pointer to a
     687             :     /// freed object) and should not be accessed, except to destruct them.
     688             :     ///
     689             :     /// Like dangling pointers, access to dangling SlotIndexes can cause
     690             :     /// painful-to-track-down bugs, especially if the memory for the index
     691             :     /// previously pointed to has been re-used. To detect dangling SlotIndex
     692             :     /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to
     693             :     /// be retained in a graveyard instead of being freed. Operations on indexes
     694             :     /// in the graveyard will trigger an assertion.
     695             :     void eraseIndex(SlotIndex index) {
     696             :       IndexListEntry *entry = index.listEntry();
     697             : #ifdef EXPENSIVE_CHECKS
     698             :       indexList.remove(entry);
     699             :       graveyardList.push_back(entry);
     700             :       entry->setPoison();
     701             : #else
     702             :       indexList.erase(entry);
     703             : #endif
     704             :     }
     705             :   };
     706             : 
     707             :   // Specialize IntervalMapInfo for half-open slot index intervals.
     708             :   template <>
     709             :   struct IntervalMapInfo<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> {
     710             :   };
     711             : 
     712             : } // end namespace llvm
     713             : 
     714             : #endif // LLVM_CODEGEN_SLOTINDEXES_H

Generated by: LCOV version 1.13