18#ifndef LLVM_CODEGEN_SLOTINDEXES_H
19#define LLVM_CODEGEN_SLOTINDEXES_H
98 unsigned getIndex()
const {
99 return listEntry()->
getIndex() | getSlot();
103 Slot getSlot()
const {
104 return static_cast<Slot
>(lie.
getInt());
124 assert(
isValid() &&
"Attempt to construct index with 0 pointer.");
144 return lie == other.lie;
148 return lie != other.lie;
154 return getIndex() < other.getIndex();
159 return getIndex() <= other.getIndex();
165 return getIndex() > other.getIndex();
171 return getIndex() >= other.getIndex();
176 return A.listEntry() ==
B.listEntry();
182 return A.listEntry()->getIndex() <
B.listEntry()->getIndex();
193 return other.getIndex() - getIndex();
203 return (other.listEntry()->
getIndex() - listEntry()->getIndex())
208 bool isBlock()
const {
return getSlot() == Slot_Block; }
215 bool isRegister()
const {
return getSlot() == Slot_Register; }
218 bool isDead()
const {
return getSlot() == Slot_Dead; }
224 return SlotIndex(listEntry(), Slot_Block);
231 return SlotIndex(listEntry(), Slot_Dead);
237 return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register);
242 return SlotIndex(listEntry(), Slot_Dead);
253 if (s == Slot_Dead) {
254 return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
262 return SlotIndex(&*++listEntry()->getIterator(), getSlot());
273 if (s == Slot_Block) {
274 return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
282 return SlotIndex(&*--listEntry()->getIterator(), getSlot());
291 using IdxMBBPair = std::pair<SlotIndex, MachineBasicBlock *>;
351 assert(indexList.
front().getIndex() == 0 &&
"First index is not 0?");
368 bool IgnoreBundle =
false)
const {
377 "Could not use a debug instruction to query mi2iMap.");
379 assert(itr != mi2iMap.
end() &&
"Instruction not found in maps.");
386 return index.listEntry()->
getInstr();
406 assert(
MBB &&
"MI must be inserted in a basic block");
413 if (MapItr != mi2iMap.
end())
414 return MapItr->second;
423 assert(
MBB &&
"MI must be inserted in a basic block");
430 if (MapItr != mi2iMap.
end())
431 return MapItr->second;
436 const std::pair<SlotIndex, SlotIndex> &
438 return MBBRanges[Num];
442 const std::pair<SlotIndex, SlotIndex> &
476 return std::lower_bound(
487 return std::upper_bound(
494 return idx2MBBMap.
begin();
499 return idx2MBBMap.
end();
505 return MI->getParent();
510 "index does not correspond to an MBB");
521 "Instructions inside bundles should use bundle start's slot.");
525 assert(!
MI.isDebugInstr() &&
"Cannot number debug instructions.");
527 assert(
MI.getParent() !=
nullptr &&
"Instr must be added to function.");
534 prevItr = std::prev(nextItr);
538 nextItr = std::next(prevItr);
543 unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
544 unsigned newNumber = prevItr->getIndex() + dist;
548 indexList.
insert(nextItr, *createEntry(&
MI, newNumber));
552 renumberIndexes(newItr);
554 SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
555 mi2iMap.
insert(std::make_pair(&
MI, newIndex));
566 bool AllowBundled =
false);
578 if (mi2iItr == mi2iMap.
end())
580 SlotIndex replaceBaseIndex = mi2iItr->second;
583 "Mismatched instruction in index tables.");
585 mi2iMap.
erase(mi2iItr);
586 mi2iMap.
insert(std::make_pair(&NewMI, replaceBaseIndex));
587 return replaceBaseIndex;
596 "Can't insert a new block at the beginning of a function.");
604 mbb->
empty() ? endEntry
609 SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
610 SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
612 MBBRanges[prevMBB->getNumber()].second = startIdx;
615 "Blocks must be added in order");
616 MBBRanges.
push_back(std::make_pair(startIdx, endIdx));
619 renumberIndexes(newItr);
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file implements a coalescing interval map for small objects.
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
Allocate memory in an ever growing pool, as if by bump-pointer.
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
This class represents an entry in the slot index list held in the SlotIndexes pass.
IndexListEntry(MachineInstr *mi, unsigned index)
void setInstr(MachineInstr *mi)
MachineInstr * getInstr() const
void setIndex(unsigned index)
unsigned getIndex() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const MachineBasicBlock & front() const
Representation of each machine instruction.
bool isDebugInstr() const
PointerIntPair - This class implements a pair of a pointer and small integer.
PointerTy getPointer() const
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
SlotIndex getNextIndex() const
Returns the next index.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
SlotIndex()=default
Construct an invalid index.
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
bool operator>=(SlotIndex other) const
Compare two SlotIndex objects.
int distance(SlotIndex other) const
Return the distance from this index to the given one.
bool operator>(SlotIndex other) const
Compare two SlotIndex objects.
bool isValid() const
Returns true if this is a valid index.
bool isRegister() const
isRegister - Returns true if this is a normal register use/def slot.
bool operator!=(SlotIndex other) const
Compare two SlotIndex objects for inequality.
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
@ InstrDist
The default distance between instructions as returned by distance().
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex(IndexListEntry *entry, unsigned slot)
void dump() const
Dump this index to stderr.
SlotIndex(const SlotIndex &li, Slot s)
SlotIndex getPrevIndex() const
Returns the previous index.
void print(raw_ostream &os) const
Print this index to the given raw_ostream.
SlotIndex getNextSlot() const
Returns the next slot in the index list.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
bool operator<(SlotIndex other) const
Compare two SlotIndex objects.
bool operator<=(SlotIndex other) const
Compare two SlotIndex objects.
int getApproxInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
bool operator==(SlotIndex other) const
Compare two SlotIndex objects for equality.
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
void getAnalysisUsage(AnalysisUsage &au) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
void dump() const
Dump the indexes.
void repairIndexesInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End)
Repair indexes after adding and removing instructions.
bool runOnMachineFunction(MachineFunction &fn) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
MBBIndexIterator getMBBLowerBound(MBBIndexIterator Start, SlotIndex Idx) const
Get an iterator pointing to the first IdxMBBPair with SlotIndex greater than or equal to Idx.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
void removeSingleMachineInstrFromMaps(MachineInstr &MI)
Removes a single machine instruction MI from the mapping.
MBBIndexIterator getMBBLowerBound(SlotIndex Idx) const
MBBIndexIterator MBBIndexBegin() const
Returns an iterator for the begin of the idx2MBBMap.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
MBBIndexIterator MBBIndexEnd() const
Return an iterator for the end of the idx2MBBMap.
SmallVectorImpl< IdxMBBPair >::const_iterator MBBIndexIterator
Iterator over the idx2MBBMap (sorted pairs of slot index of basic block begin and basic block)
MBBIndexIterator getMBBUpperBound(SlotIndex Idx) const
Get an iterator pointing to the first IdxMBBPair with SlotIndex greater than Idx.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
SlotIndex getIndexAfter(const MachineInstr &MI) const
getIndexAfter - Returns the index of the first indexed instruction after MI, or the end index of its ...
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
void packIndexes()
Renumber all indexes using the default instruction distance.
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
SlotIndex getIndexBefore(const MachineInstr &MI) const
getIndexBefore - Returns the index of the last indexed instruction before MI, or the start index of i...
SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in maps used by register allocat...
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Returns the last index in the given basic block.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Returns the first index in the given basic block.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(const MachineBasicBlock *MBB) const
Return the (start,end) range of the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
typename SuperClass::const_iterator const_iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, false, false >::type iterator
This is an optimization pass for GlobalISel generic memory operations.
MachineBasicBlock::instr_iterator getBundleStart(MachineBasicBlock::instr_iterator I)
Returns an iterator to the first instruction in the bundle containing I.
std::pair< SlotIndex, MachineBasicBlock * > IdxMBBPair
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
void sort(IteratorTy Start, IteratorTy End)
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Function object to check whether the first component of a container supported by std::get (like std::...