1233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames//===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- C++ -*-===// 2233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 3233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// The LLVM Compiler Infrastructure 4233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 5233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// This file is distributed under the University of Illinois Open Source 6233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// License. See LICENSE.TXT for details. 7233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 8233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames//===----------------------------------------------------------------------===// 9233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 105fa301bfa9a318de177cbf19ff925f10a742695fNick Lewycky// This file implements SlotIndex and related classes. The purpose of SlotIndex 11233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// is to describe a position at which a register can become live, or cease to 12233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// be live. 13233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// 14233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which 15233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames// is held is LiveIntervals and provides the real numbering. This allows 16011e5910719265ba5d41e8af2290e55c5eb50526Jakob Stoklund Olesen// LiveIntervals to perform largely transparent renumbering. 17233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames//===----------------------------------------------------------------------===// 18233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 19233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#ifndef LLVM_CODEGEN_SLOTINDEXES_H 20233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#define LLVM_CODEGEN_SLOTINDEXES_H 21233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 22741981adf3a2bc0c6652c9c4ec846250950f3e68Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBundle.h" 23dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames#include "llvm/CodeGen/MachineFunction.h" 24233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/MachineFunctionPass.h" 25dd0fbda3e32797b8fc0812fa886aff222d741f37Chris Lattner#include "llvm/ADT/PointerIntPair.h" 26613dfb219c167717576b2383ee57573f4d8f53cfLang Hames#include "llvm/ADT/ilist.h" 27dd0fbda3e32797b8fc0812fa886aff222d741f37Chris Lattner#include "llvm/ADT/SmallVector.h" 28dd0fbda3e32797b8fc0812fa886aff222d741f37Chris Lattner#include "llvm/ADT/DenseMap.h" 29233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/Support/Allocator.h" 30233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 31233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesnamespace llvm { 32233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 33233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// This class represents an entry in the slot index list held in the 34233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// SlotIndexes pass. It should not be used directly. See the 35233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// SlotIndex & SlotIndexes classes for the public interface to this 36233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// information. 37613dfb219c167717576b2383ee57573f4d8f53cfLang Hames class IndexListEntry : public ilist_node<IndexListEntry> { 38233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineInstr *mi; 39233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames unsigned index; 40233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 41233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames public: 42233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 43f37712f48642bcca04c77083c0579e7fe8d4d916Jakob Stoklund Olesen IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {} 44e0710472c84e61acf085f101abb4213c6cb1f545Lang Hames 45233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineInstr* getInstr() const { return mi; } 46d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames void setInstr(MachineInstr *mi) { 47d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames this->mi = mi; 48d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames } 49233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 50233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames unsigned getIndex() const { return index; } 51d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames void setIndex(unsigned index) { 52d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames this->index = index; 53d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames } 54233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 55613dfb219c167717576b2383ee57573f4d8f53cfLang Hames }; 56613dfb219c167717576b2383ee57573f4d8f53cfLang Hames 57613dfb219c167717576b2383ee57573f4d8f53cfLang Hames template <> 58613dfb219c167717576b2383ee57573f4d8f53cfLang Hames struct ilist_traits<IndexListEntry> : public ilist_default_traits<IndexListEntry> { 59613dfb219c167717576b2383ee57573f4d8f53cfLang Hames private: 60613dfb219c167717576b2383ee57573f4d8f53cfLang Hames mutable ilist_half_node<IndexListEntry> Sentinel; 61613dfb219c167717576b2383ee57573f4d8f53cfLang Hames public: 62613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexListEntry *createSentinel() const { 63613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return static_cast<IndexListEntry*>(&Sentinel); 64d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6Lang Hames } 65613dfb219c167717576b2383ee57573f4d8f53cfLang Hames void destroySentinel(IndexListEntry *) const {} 66613dfb219c167717576b2383ee57573f4d8f53cfLang Hames 67613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexListEntry *provideInitialHead() const { return createSentinel(); } 68613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexListEntry *ensureHead(IndexListEntry*) const { return createSentinel(); } 69613dfb219c167717576b2383ee57573f4d8f53cfLang Hames static void noteHead(IndexListEntry*, IndexListEntry*) {} 70613dfb219c167717576b2383ee57573f4d8f53cfLang Hames void deleteNode(IndexListEntry *N) {} 71613dfb219c167717576b2383ee57573f4d8f53cfLang Hames 72613dfb219c167717576b2383ee57573f4d8f53cfLang Hames private: 73613dfb219c167717576b2383ee57573f4d8f53cfLang Hames void createNode(const IndexListEntry &); 74233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames }; 75233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 76233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// SlotIndex - An opaque wrapper around machine indexes. 77233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames class SlotIndex { 78233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames friend class SlotIndexes; 79233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 802debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen enum Slot { 812debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Basic block boundary. Used for live ranges entering and leaving a 822debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// block without being live in the layout neighbor. Also used as the 832debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// def slot of PHI-defs. 842debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Slot_Block, 852debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen 862debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Early-clobber register use/def slot. A live range defined at 872debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Slot_EarlyCLobber interferes with normal live ranges killed at 882debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Slot_Register. Also used as the kill slot for live ranges tied to an 892debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// early-clobber def. 902debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Slot_EarlyClobber, 912debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen 922debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Normal register use/def slot. Normal instructions kill and define 932debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// register live ranges at this slot. 942debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Slot_Register, 952debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen 962debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Dead def kill point. Kill slot for a live range that is defined by 972debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't 982debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// used anywhere. 992debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Slot_Dead, 1002debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen 1012debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Slot_Count 1022debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen }; 103dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen 104011e5910719265ba5d41e8af2290e55c5eb50526Jakob Stoklund Olesen PointerIntPair<IndexListEntry*, 2, unsigned> lie; 105233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 106011e5910719265ba5d41e8af2290e55c5eb50526Jakob Stoklund Olesen SlotIndex(IndexListEntry *entry, unsigned slot) 107f37712f48642bcca04c77083c0579e7fe8d4d916Jakob Stoklund Olesen : lie(entry, slot) {} 108233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 109613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexListEntry* listEntry() const { 110a97ff8a027259b1b9e4dbdb5b6f01cc2195a6948Jakob Stoklund Olesen assert(isValid() && "Attempt to compare reserved index."); 111613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return lie.getPointer(); 112233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 113233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 114233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames int getIndex() const { 115613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return listEntry()->getIndex() | getSlot(); 116233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 117233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 118dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen /// Returns the slot for this SlotIndex. 119dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen Slot getSlot() const { 120011e5910719265ba5d41e8af2290e55c5eb50526Jakob Stoklund Olesen return static_cast<Slot>(lie.getInt()); 121dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen } 122dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen 123233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames public: 124bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen enum { 125bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen /// The default distance between instructions as returned by distance(). 126bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen /// This may vary as instructions are inserted and removed. 1272debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen InstrDist = 4 * Slot_Count 128bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen }; 129bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen 130233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Construct an invalid index. 131f37712f48642bcca04c77083c0579e7fe8d4d916Jakob Stoklund Olesen SlotIndex() : lie(0, 0) {} 132233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 133011e5910719265ba5d41e8af2290e55c5eb50526Jakob Stoklund Olesen // Construct a new slot index from the given one, and set the slot. 134613dfb219c167717576b2383ee57573f4d8f53cfLang Hames SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) { 135233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(lie.getPointer() != 0 && 136233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "Attempt to construct index with 0 pointer."); 137233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 138233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 139233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns true if this is a valid index. Invalid indicies do 140233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// not point into an index table, and cannot be compared. 141233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool isValid() const { 142f37712f48642bcca04c77083c0579e7fe8d4d916Jakob Stoklund Olesen return lie.getPointer(); 143233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 144233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 145b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// Return true for a valid index. 146b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen operator bool() const { return isValid(); } 147b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 148233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Print this index to the given raw_ostream. 149233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void print(raw_ostream &os) const; 150233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 151233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Dump this index to stderr. 152233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void dump() const; 153233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 154233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Compare two SlotIndex objects for equality. 155233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool operator==(SlotIndex other) const { 156acf9f48c5e5fa2ce381d566aefc6285653ab2b5cJakob Stoklund Olesen return lie == other.lie; 157233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 158233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Compare two SlotIndex objects for inequality. 159233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool operator!=(SlotIndex other) const { 160acf9f48c5e5fa2ce381d566aefc6285653ab2b5cJakob Stoklund Olesen return lie != other.lie; 161233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 162613dfb219c167717576b2383ee57573f4d8f53cfLang Hames 163233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Compare two SlotIndex objects. Return true if the first index 164233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// is strictly lower than the second. 165233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool operator<(SlotIndex other) const { 166233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return getIndex() < other.getIndex(); 167233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 168233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Compare two SlotIndex objects. Return true if the first index 169233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// is lower than, or equal to, the second. 170233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool operator<=(SlotIndex other) const { 171233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return getIndex() <= other.getIndex(); 172233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 173233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 174233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Compare two SlotIndex objects. Return true if the first index 175233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// is greater than the second. 176233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool operator>(SlotIndex other) const { 177233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return getIndex() > other.getIndex(); 178233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 179233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 180233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Compare two SlotIndex objects. Return true if the first index 181233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// is greater than, or equal to, the second. 182233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool operator>=(SlotIndex other) const { 183233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return getIndex() >= other.getIndex(); 184233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 185233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 186a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen /// isSameInstr - Return true if A and B refer to the same instruction. 187a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen static bool isSameInstr(SlotIndex A, SlotIndex B) { 188a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen return A.lie.getPointer() == B.lie.getPointer(); 189a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen } 190a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 1912aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen /// isEarlierInstr - Return true if A refers to an instruction earlier than 1922aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen /// B. This is equivalent to A < B && !isSameInstr(A, B). 1932aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen static bool isEarlierInstr(SlotIndex A, SlotIndex B) { 194613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return A.listEntry()->getIndex() < B.listEntry()->getIndex(); 1952aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen } 1962aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen 197233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Return the distance from this index to the given one. 198233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames int distance(SlotIndex other) const { 199233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return other.getIndex() - getIndex(); 200233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 201233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 2022debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// isBlock - Returns true if this is a block boundary slot. 2032debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen bool isBlock() const { return getSlot() == Slot_Block; } 204dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen 2052debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// isEarlyClobber - Returns true if this is an early-clobber slot. 2062debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; } 207dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen 2082debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// isRegister - Returns true if this is a normal register use/def slot. 2092debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Note that early-clobber slots may also be used for uses and defs. 2102debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen bool isRegister() const { return getSlot() == Slot_Register; } 211dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen 2122debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// isDead - Returns true if this is a dead def kill slot. 2132debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen bool isDead() const { return getSlot() == Slot_Dead; } 214dfa28b157dd066eed4db9d2256f55c23b88df637Jakob Stoklund Olesen 215233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the base index for associated with this index. The base index 2162debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// is the one associated with the Slot_Block slot for the instruction 2172debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// pointed to by this index. 218233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getBaseIndex() const { 219613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry(), Slot_Block); 220233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 221233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 222233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the boundary index for associated with this index. The boundary 2232debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// index is the one associated with the Slot_Block slot for the instruction 224233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// pointed to by this index. 225233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getBoundaryIndex() const { 226613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry(), Slot_Dead); 227233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 228233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 2292debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Returns the register use/def slot in the current instruction for a 2302debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// normal or early-clobber def. 2312debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex getRegSlot(bool EC = false) const { 232613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register); 233233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 234233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 2352debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// Returns the dead def kill slot for the current instruction. 2362debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex getDeadSlot() const { 237613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry(), Slot_Dead); 238233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 239233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 240233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the next slot in the index list. This could be either the 241233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// next slot for the instruction pointed to by this index or, if this 242233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// index is a STORE, the first slot for the next instruction. 243233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// WARNING: This method is considerably more expensive than the methods 244233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// that return specific slots (getUseIndex(), etc). If you can - please 245233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// use one of those methods. 246233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getNextSlot() const { 247233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Slot s = getSlot(); 2482debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen if (s == Slot_Dead) { 249613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry()->getNextNode(), Slot_Block); 250233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 251613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry(), s + 1); 252233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 253233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 254233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the next index. This is the index corresponding to the this 255233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// index's slot, but for the next instruction. 256233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getNextIndex() const { 257613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry()->getNextNode(), getSlot()); 258233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 259233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 260233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the previous slot in the index list. This could be either the 261233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// previous slot for the instruction pointed to by this index or, if this 2622debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen /// index is a Slot_Block, the last slot for the previous instruction. 263233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// WARNING: This method is considerably more expensive than the methods 264233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// that return specific slots (getUseIndex(), etc). If you can - please 265233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// use one of those methods. 266233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getPrevSlot() const { 267233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Slot s = getSlot(); 2682debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen if (s == Slot_Block) { 269613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry()->getPrevNode(), Slot_Dead); 270233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 271613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry(), s - 1); 272233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 273233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 274233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the previous index. This is the index corresponding to this 275233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// index's slot, but for the previous instruction. 276233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getPrevIndex() const { 277613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(listEntry()->getPrevNode(), getSlot()); 278233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 279233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 280233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames }; 281233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 282729a8acc9f2f4bd0751da20d0e85a8c02bdc5375Chris Lattner template <> struct isPodLike<SlotIndex> { static const bool value = true; }; 283729a8acc9f2f4bd0751da20d0e85a8c02bdc5375Chris Lattner 284233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 285233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) { 286233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames li.print(os); 287233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return os; 288233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 289233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 290233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames typedef std::pair<SlotIndex, MachineBasicBlock*> IdxMBBPair; 291233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 292233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames inline bool operator<(SlotIndex V, const IdxMBBPair &IM) { 293233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return V < IM.first; 294233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 295233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 296233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames inline bool operator<(const IdxMBBPair &IM, SlotIndex V) { 297233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return IM.first < V; 298233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 299233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 300233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames struct Idx2MBBCompare { 301233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const { 302233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return LHS.first < RHS.first; 303233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 304233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames }; 305233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 306233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// SlotIndexes pass. 307233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// 308233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// This pass assigns indexes to each instruction. 309233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames class SlotIndexes : public MachineFunctionPass { 310233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames private: 311233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 312613dfb219c167717576b2383ee57573f4d8f53cfLang Hames typedef ilist<IndexListEntry> IndexList; 313613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexList indexList; 314613dfb219c167717576b2383ee57573f4d8f53cfLang Hames 315233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineFunction *mf; 316233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 317233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap; 318233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Mi2IndexMap mi2iMap; 319233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 320a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen /// MBBRanges - Map MBB number to (start, stop) indexes. 321a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen SmallVector<std::pair<SlotIndex, SlotIndex>, 8> MBBRanges; 322233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 323233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Idx2MBBMap - Sorted list of pairs of index of first instruction 324233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// and MBB id. 325a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen SmallVector<IdxMBBPair, 8> idx2MBBMap; 326233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 327233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // IndexListEntry allocator. 328233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames BumpPtrAllocator ileAllocator; 329233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 330233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames IndexListEntry* createEntry(MachineInstr *mi, unsigned index) { 331233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames IndexListEntry *entry = 332233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames static_cast<IndexListEntry*>( 333233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ileAllocator.Allocate(sizeof(IndexListEntry), 33416c3b647eb100fe404ee65f106d563ddef6c74b7Chris Lattner alignOf<IndexListEntry>())); 335233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 336233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames new (entry) IndexListEntry(mi, index); 337233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 338233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return entry; 339233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 340233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 341613dfb219c167717576b2383ee57573f4d8f53cfLang Hames /// Renumber locally after inserting curItr. 342613dfb219c167717576b2383ee57573f4d8f53cfLang Hames void renumberIndexes(IndexList::iterator curItr); 343979869c28e5bc68e2d4d546c7019525177f1d399Jakob Stoklund Olesen 344233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames public: 345233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames static char ID; 346233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 347613dfb219c167717576b2383ee57573f4d8f53cfLang Hames SlotIndexes() : MachineFunctionPass(ID) { 348081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 349081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 350233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 351233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames virtual void getAnalysisUsage(AnalysisUsage &au) const; 352613dfb219c167717576b2383ee57573f4d8f53cfLang Hames virtual void releaseMemory(); 353233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 354233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames virtual bool runOnMachineFunction(MachineFunction &fn); 355233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 356233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Dump the indexes. 357233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void dump() const; 358233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 359233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Renumber the index list, providing space for new instructions. 360b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames void renumberIndexes(); 361233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 362233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the zero index for this analysis. 363233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getZeroIndex() { 364613dfb219c167717576b2383ee57573f4d8f53cfLang Hames assert(indexList.front().getIndex() == 0 && "First index is not 0?"); 365613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(&indexList.front(), 0); 366233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 367233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 36854cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames /// Returns the base index of the last slot in this analysis. 36954cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames SlotIndex getLastIndex() { 370613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(&indexList.back(), 0); 37154cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames } 37254cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames 373233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns true if the given machine instr is mapped to an index, 374233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// otherwise returns false. 375233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool hasIndex(const MachineInstr *instr) const { 376da69f3b357097e75fbf9a5a2bbe1e7273d4b4271Benjamin Kramer return mi2iMap.count(instr); 377233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 378233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 379233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the base index for the given instruction. 380b62fbc5e469f532fd1747a3c24115fb1d0ba792fJakob Stoklund Olesen SlotIndex getInstructionIndex(const MachineInstr *MI) const { 381b62fbc5e469f532fd1747a3c24115fb1d0ba792fJakob Stoklund Olesen // Instructions inside a bundle have the same number as the bundle itself. 382741981adf3a2bc0c6652c9c4ec846250950f3e68Jakob Stoklund Olesen Mi2IndexMap::const_iterator itr = mi2iMap.find(getBundleStart(MI)); 383233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(itr != mi2iMap.end() && "Instruction not found in maps."); 384233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return itr->second; 385233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 386233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 387233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the instruction for the given index, or null if the given 388233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// index has no instruction associated with it. 389233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineInstr* getInstructionFromIndex(SlotIndex index) const { 390613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return index.isValid() ? index.listEntry()->getInstr() : 0; 391233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 392233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 393233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the next non-null index. 394233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getNextNonNullIndex(SlotIndex index) { 395613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexList::iterator itr(index.listEntry()); 396613dfb219c167717576b2383ee57573f4d8f53cfLang Hames ++itr; 397613dfb219c167717576b2383ee57573f4d8f53cfLang Hames while (itr != indexList.end() && itr->getInstr() == 0) { ++itr; } 398613dfb219c167717576b2383ee57573f4d8f53cfLang Hames return SlotIndex(itr, index.getSlot()); 399233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 400233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 4018e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// getIndexBefore - Returns the index of the last indexed instruction 402c8e41c591741b3da1077f7000274ad040bef8002Sylvestre Ledru /// before MI, or the start index of its basic block. 4038e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// MI is not required to have an index. 4048e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen SlotIndex getIndexBefore(const MachineInstr *MI) const { 4058e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen const MachineBasicBlock *MBB = MI->getParent(); 4068e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen assert(MBB && "MI must be inserted inna basic block"); 4078e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen MachineBasicBlock::const_iterator I = MI, B = MBB->begin(); 4088e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen for (;;) { 4098e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen if (I == B) 4108e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen return getMBBStartIdx(MBB); 4118e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen --I; 4128e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I); 4138e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen if (MapItr != mi2iMap.end()) 4148e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen return MapItr->second; 4158e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen } 4168e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen } 4178e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen 4188e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// getIndexAfter - Returns the index of the first indexed instruction 4198e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// after MI, or the end index of its basic block. 4208e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// MI is not required to have an index. 4218e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen SlotIndex getIndexAfter(const MachineInstr *MI) const { 4228e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen const MachineBasicBlock *MBB = MI->getParent(); 4238e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen assert(MBB && "MI must be inserted inna basic block"); 4248e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen MachineBasicBlock::const_iterator I = MI, E = MBB->end(); 4258e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen for (;;) { 4268e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen ++I; 4278e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen if (I == E) 4288e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen return getMBBEndIdx(MBB); 4298e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I); 4308e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen if (MapItr != mi2iMap.end()) 4318e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen return MapItr->second; 4328e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen } 4338e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen } 4348e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen 435a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen /// Return the (start,end) range of the given basic block number. 436a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen const std::pair<SlotIndex, SlotIndex> & 437a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen getMBBRange(unsigned Num) const { 438a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen return MBBRanges[Num]; 439a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen } 440a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen 441e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen /// Return the (start,end) range of the given basic block. 442e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen const std::pair<SlotIndex, SlotIndex> & 443a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen getMBBRange(const MachineBasicBlock *MBB) const { 444a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen return getMBBRange(MBB->getNumber()); 445e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen } 446e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen 4476c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen /// Returns the first index in the given basic block number. 4486c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex getMBBStartIdx(unsigned Num) const { 4496c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen return getMBBRange(Num).first; 4506c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen } 4516c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen 452e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen /// Returns the first index in the given basic block. 453e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 454e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen return getMBBRange(mbb).first; 455233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 456233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 4576c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen /// Returns the last index in the given basic block number. 4586c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex getMBBEndIdx(unsigned Num) const { 4596c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen return getMBBRange(Num).second; 4606c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen } 4616c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen 462233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the last index in the given basic block. 463233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 464e69b4ab82924359ca3d85215fb42aee2495de2f8Jakob Stoklund Olesen return getMBBRange(mbb).second; 465233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 466233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 467233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the basic block which the given index falls in. 468233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 4693d32202748f3ce3de31e48a183130d94e767e97cJakob Stoklund Olesen if (MachineInstr *MI = getInstructionFromIndex(index)) 4703d32202748f3ce3de31e48a183130d94e767e97cJakob Stoklund Olesen return MI->getParent(); 471a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen SmallVectorImpl<IdxMBBPair>::const_iterator I = 472233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index); 473233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Take the pair containing the index 474a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen SmallVectorImpl<IdxMBBPair>::const_iterator J = 475233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ((I != idx2MBBMap.end() && I->first > index) || 476233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I; 477233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 478233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(J != idx2MBBMap.end() && J->first <= index && 47974ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames index < getMBBEndIdx(J->second) && 480233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "index does not correspond to an MBB"); 481233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return J->second; 482233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 483233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 484233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool findLiveInMBBs(SlotIndex start, SlotIndex end, 485233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SmallVectorImpl<MachineBasicBlock*> &mbbs) const { 486a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen SmallVectorImpl<IdxMBBPair>::const_iterator itr = 487233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); 488233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool resVal = false; 489233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 490233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames while (itr != idx2MBBMap.end()) { 491233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (itr->first >= end) 492233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames break; 493233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mbbs.push_back(itr->second); 494233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames resVal = true; 495233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ++itr; 496233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 497233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return resVal; 498233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 499233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 500233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Returns the MBB covering the given range, or null if the range covers 501233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// more than one basic block. 502233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const { 503233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 504233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(start < end && "Backwards ranges not allowed."); 505233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 506a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen SmallVectorImpl<IdxMBBPair>::const_iterator itr = 507233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); 508233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 509233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (itr == idx2MBBMap.end()) { 510233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames itr = prior(itr); 511233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return itr->second; 512233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 513233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 514233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Check that we don't cross the boundary into this block. 515233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (itr->first < end) 516233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return 0; 517233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 518233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames itr = prior(itr); 519233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 520233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (itr->first <= start) 521233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return itr->second; 522233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 523233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return 0; 524233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 525233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 526b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames /// Insert the given machine instruction into the mapping. Returns the 527b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames /// assigned index. 5288e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// If Late is set and there are null indexes between mi's neighboring 5298e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// instructions, create the new index after the null indexes instead of 5308e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen /// before them. 5318e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen SlotIndex insertMachineInstrInMaps(MachineInstr *mi, bool Late = false) { 532ac597ecfbc0b519ffcbf5f4160262a2c39f59fe6Lang Hames assert(!mi->isInsideBundle() && 533ac597ecfbc0b519ffcbf5f4160262a2c39f59fe6Lang Hames "Instructions inside bundles should use bundle start's slot."); 534b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed."); 535a5f1a900df66178608d728708e0753015681d4c7Jakob Stoklund Olesen // Numbering DBG_VALUE instructions could cause code generation to be 536a5f1a900df66178608d728708e0753015681d4c7Jakob Stoklund Olesen // affected by debug information. 537a5f1a900df66178608d728708e0753015681d4c7Jakob Stoklund Olesen assert(!mi->isDebugValue() && "Cannot number DBG_VALUE instructions."); 538233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 53979142427a030baad468c90c54b66853e084507d3Chandler Carruth assert(mi->getParent() != 0 && "Instr must be added to function."); 540233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5418e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen // Get the entries where mi should be inserted. 542613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexList::iterator prevItr, nextItr; 5438e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen if (Late) { 5448e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen // Insert mi's index immediately before the following instruction. 545613dfb219c167717576b2383ee57573f4d8f53cfLang Hames nextItr = getIndexAfter(mi).listEntry(); 546613dfb219c167717576b2383ee57573f4d8f53cfLang Hames prevItr = prior(nextItr); 5478e33095cd45b8be6b8dba9be8b2e72164494a7feJakob Stoklund Olesen } else { 548d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // Insert mi's index immediately after the preceding instruction. 549613dfb219c167717576b2383ee57573f4d8f53cfLang Hames prevItr = getIndexBefore(mi).listEntry(); 550d2bfce15d4dd065760cfe70c0bf7958e190fa757Francois Pichet nextItr = llvm::next(prevItr); 551233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 552233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 553b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames // Get a number for the new instr, or 0 if there's no room currently. 554b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames // In the latter case we'll force a renumber later. 555613dfb219c167717576b2383ee57573f4d8f53cfLang Hames unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u; 556613dfb219c167717576b2383ee57573f4d8f53cfLang Hames unsigned newNumber = prevItr->getIndex() + dist; 557233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 558b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames // Insert a new list entry for mi. 559613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexList::iterator newItr = 560613dfb219c167717576b2383ee57573f4d8f53cfLang Hames indexList.insert(nextItr, createEntry(mi, newNumber)); 561233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 562979869c28e5bc68e2d4d546c7019525177f1d399Jakob Stoklund Olesen // Renumber locally if we need to. 563979869c28e5bc68e2d4d546c7019525177f1d399Jakob Stoklund Olesen if (dist == 0) 564613dfb219c167717576b2383ee57573f4d8f53cfLang Hames renumberIndexes(newItr); 565233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 566613dfb219c167717576b2383ee57573f4d8f53cfLang Hames SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block); 567979869c28e5bc68e2d4d546c7019525177f1d399Jakob Stoklund Olesen mi2iMap.insert(std::make_pair(mi, newIndex)); 568b3661585c0f87b6045f0d65b5cac16921ae27086Lang Hames return newIndex; 569233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 570233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 571233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// Remove the given machine instruction from the mapping. 572233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void removeMachineInstrFromMaps(MachineInstr *mi) { 573233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // remove index -> MachineInstr and 574233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // MachineInstr -> index mappings 575233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi); 576233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mi2iItr != mi2iMap.end()) { 577613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexListEntry *miEntry(mi2iItr->second.listEntry()); 578233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(miEntry->getInstr() == mi && "Instruction indexes broken."); 579233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // FIXME: Eventually we want to actually delete these indexes. 580233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames miEntry->setInstr(0); 581233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mi2iMap.erase(mi2iItr); 582233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 583233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 584233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 585233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in 586233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames /// maps used by register allocator. 587233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) { 588233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi); 589233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mi2iItr == mi2iMap.end()) 590233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return; 591233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex replaceBaseIndex = mi2iItr->second; 592613dfb219c167717576b2383ee57573f4d8f53cfLang Hames IndexListEntry *miEntry(replaceBaseIndex.listEntry()); 593233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(miEntry->getInstr() == mi && 594233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "Mismatched instruction in index tables."); 595233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames miEntry->setInstr(newMI); 596233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mi2iMap.erase(mi2iItr); 597233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex)); 598233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames } 599233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 600dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames /// Add the given MachineBasicBlock into the maps. 601dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames void insertMBBInMaps(MachineBasicBlock *mbb) { 602dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames MachineFunction::iterator nextMBB = 603dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames llvm::next(MachineFunction::iterator(mbb)); 604dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames IndexListEntry *startEntry = createEntry(0, 0); 6051e8e72d72a71ec3fb6c81bd35a34261f34436900Jakob Stoklund Olesen IndexListEntry *stopEntry = createEntry(0, 0); 606dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames IndexListEntry *nextEntry = 0; 607dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames 608dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames if (nextMBB == mbb->getParent()->end()) { 609613dfb219c167717576b2383ee57573f4d8f53cfLang Hames nextEntry = indexList.end(); 610dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames } else { 611613dfb219c167717576b2383ee57573f4d8f53cfLang Hames nextEntry = getMBBStartIdx(nextMBB).listEntry(); 612dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames } 613dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames 614613dfb219c167717576b2383ee57573f4d8f53cfLang Hames indexList.insert(nextEntry, startEntry); 615613dfb219c167717576b2383ee57573f4d8f53cfLang Hames indexList.insert(nextEntry, stopEntry); 616dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames 6172debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); 6182debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex endIdx(nextEntry, SlotIndex::Slot_Block); 619dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames 620a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen assert(unsigned(mbb->getNumber()) == MBBRanges.size() && 621a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen "Blocks must be added in order"); 622a122eaaee22750c4f92c33672e149eb2f0c538cbJakob Stoklund Olesen MBBRanges.push_back(std::make_pair(startIdx, endIdx)); 623dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames 624dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb)); 625dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames 626dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames renumberIndexes(); 627dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 628dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames } 629dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1fLang Hames 630233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames }; 631233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 632233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 6330613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen // Specialize IntervalMapInfo for half-open slot index intervals. 6340613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen template <typename> struct IntervalMapInfo; 6350613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen template <> struct IntervalMapInfo<SlotIndex> { 6360613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen static inline bool startLess(const SlotIndex &x, const SlotIndex &a) { 6370613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen return x < a; 6380613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen } 6390613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen static inline bool stopLess(const SlotIndex &b, const SlotIndex &x) { 6400613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen return b <= x; 6410613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen } 6420613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen static inline bool adjacent(const SlotIndex &a, const SlotIndex &b) { 6430613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen return a == b; 6440613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen } 6450613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen }; 6460613516b16466a92c68d60734801221506c85e86Jakob Stoklund Olesen 647233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames} 648233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 649613dfb219c167717576b2383ee57573f4d8f53cfLang Hames#endif // LLVM_CODEGEN_SLOTINDEXES_H 650