18#ifndef LLVM_CODEGEN_SLOTINDEXES_H
19#define LLVM_CODEGEN_SLOTINDEXES_H
102 unsigned getIndex()
const {
103 return listEntry()->
getIndex() | getSlot();
107 Slot getSlot()
const {
108 return static_cast<Slot
>(lie.
getInt());
129 "Attempt to construct index with 0 pointer.");
149 return lie == other.lie;
153 return lie != other.lie;
159 return getIndex() < other.getIndex();
164 return getIndex() <= other.getIndex();
170 return getIndex() > other.getIndex();
176 return getIndex() >= other.getIndex();
181 return A.lie.getPointer() ==
B.lie.getPointer();
187 return A.listEntry()->getIndex() <
B.listEntry()->getIndex();
198 return other.getIndex() - getIndex();
208 return (other.listEntry()->
getIndex() - listEntry()->getIndex())
213 bool isBlock()
const {
return getSlot() == Slot_Block; }
220 bool isRegister()
const {
return getSlot() == Slot_Register; }
223 bool isDead()
const {
return getSlot() == Slot_Dead; }
229 return SlotIndex(listEntry(), Slot_Block);
236 return SlotIndex(listEntry(), Slot_Dead);
242 return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register);
247 return SlotIndex(listEntry(), Slot_Dead);
258 if (s == Slot_Dead) {
259 return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
267 return SlotIndex(&*++listEntry()->getIterator(), getSlot());
278 if (s == Slot_Block) {
279 return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
287 return SlotIndex(&*--listEntry()->getIterator(), getSlot());
296 using IdxMBBPair = std::pair<SlotIndex, MachineBasicBlock *>;
356 assert(indexList.front().getIndex() == 0 &&
"First index is not 0?");
373 bool IgnoreBundle =
false)
const {
382 "Could not use a debug instruction to query mi2iMap.");
384 assert(itr != mi2iMap.
end() &&
"Instruction not found in maps.");
411 assert(
MBB &&
"MI must be inserted in a basic block");
418 if (MapItr != mi2iMap.
end())
419 return MapItr->second;
428 assert(
MBB &&
"MI must be inserted in a basic block");
435 if (MapItr != mi2iMap.
end())
436 return MapItr->second;
441 const std::pair<SlotIndex, SlotIndex> &
443 return MBBRanges[Num];
447 const std::pair<SlotIndex, SlotIndex> &
479 return std::partition_point(
481 [=](
const IdxMBBPair &IM) { return IM.first < To; });
492 return idx2MBBMap.
begin();
497 return idx2MBBMap.
end();
503 return MI->getParent();
513 "index does not correspond to an MBB");
524 "Instructions inside bundles should use bundle start's slot.");
528 assert(!
MI.isDebugInstr() &&
"Cannot number debug instructions.");
530 assert(
MI.getParent() !=
nullptr &&
"Instr must be added to function.");
537 prevItr = std::prev(nextItr);
541 nextItr = std::next(prevItr);
546 unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
547 unsigned newNumber = prevItr->getIndex() + dist;
551 indexList.
insert(nextItr, createEntry(&
MI, newNumber));
555 renumberIndexes(newItr);
557 SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
558 mi2iMap.
insert(std::make_pair(&
MI, newIndex));
569 bool AllowBundled =
false);
581 if (mi2iItr == mi2iMap.
end())
583 SlotIndex replaceBaseIndex = mi2iItr->second;
586 "Mismatched instruction in index tables.");
588 mi2iMap.
erase(mi2iItr);
589 mi2iMap.
insert(std::make_pair(&NewMI, replaceBaseIndex));
590 return replaceBaseIndex;
599 "Can't insert a new block at the beginning of a function.");
607 mbb->
empty() ? endEntry
612 SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
613 SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
615 MBBRanges[prevMBB->getNumber()].second = startIdx;
618 "Blocks must be added in order");
619 MBBRanges.
push_back(std::make_pair(startIdx, endIdx));
622 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.
@ InstrDist
The default distance between instructions as returned by distance().
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.
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.
MBBIndexIterator findMBBIndex(SlotIndex Idx) const
Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex that is greater or equal to Idx...
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 advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const
Move iterator to the next IdxMBBPair where the SlotIndex is greater or equal to To.
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 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)
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()
base_list_type::iterator iterator
iterator insert(iterator where, pointer New)
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
This class implements an extremely fast bulk output stream that can only output to a stream.
This file defines classes to implement an intrusive doubly linked list class (i.e.
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)
Use delete by default for iplist and ilist.
Custom traits to do nothing on deletion.
Function object to check whether the first component of a container supported by std::get (like std::...