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());
128 assert(
isValid() &&
"Attempt to construct index with 0 pointer.");
148 return lie == other.lie;
152 return lie != other.lie;
158 return getIndex() < other.getIndex();
163 return getIndex() <= other.getIndex();
169 return getIndex() > other.getIndex();
175 return getIndex() >= other.getIndex();
180 return A.listEntry() ==
B.listEntry();
186 return A.listEntry()->getIndex() <
B.listEntry()->getIndex();
197 return other.getIndex() - getIndex();
207 return (other.listEntry()->
getIndex() - listEntry()->getIndex())
212 bool isBlock()
const {
return getSlot() == Slot_Block; }
219 bool isRegister()
const {
return getSlot() == Slot_Register; }
222 bool isDead()
const {
return getSlot() == Slot_Dead; }
228 return SlotIndex(listEntry(), Slot_Block);
235 return SlotIndex(listEntry(), Slot_Dead);
241 return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register);
246 return SlotIndex(listEntry(), Slot_Dead);
257 if (s == Slot_Dead) {
258 return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
266 return SlotIndex(&*++listEntry()->getIterator(), getSlot());
277 if (s == Slot_Block) {
278 return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
286 return SlotIndex(&*--listEntry()->getIterator(), getSlot());
295 using IdxMBBPair = std::pair<SlotIndex, MachineBasicBlock *>;
355 assert(indexList.front().getIndex() == 0 &&
"First index is not 0?");
372 bool IgnoreBundle =
false)
const {
381 "Could not use a debug instruction to query mi2iMap.");
383 assert(itr != mi2iMap.
end() &&
"Instruction not found in maps.");
390 return index.listEntry()->
getInstr();
410 assert(
MBB &&
"MI must be inserted in a basic block");
417 if (MapItr != mi2iMap.
end())
418 return MapItr->second;
427 assert(
MBB &&
"MI must be inserted in a basic block");
434 if (MapItr != mi2iMap.
end())
435 return MapItr->second;
440 const std::pair<SlotIndex, SlotIndex> &
442 return MBBRanges[Num];
446 const std::pair<SlotIndex, SlotIndex> &
480 return std::lower_bound(
491 return std::upper_bound(
498 return idx2MBBMap.
begin();
503 return idx2MBBMap.
end();
509 return MI->getParent();
514 "index does not correspond to an MBB");
525 "Instructions inside bundles should use bundle start's slot.");
529 assert(!
MI.isDebugInstr() &&
"Cannot number debug instructions.");
531 assert(
MI.getParent() !=
nullptr &&
"Instr must be added to function.");
538 prevItr = std::prev(nextItr);
542 nextItr = std::next(prevItr);
547 unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
548 unsigned newNumber = prevItr->getIndex() + dist;
552 indexList.
insert(nextItr, createEntry(&
MI, newNumber));
556 renumberIndexes(newItr);
558 SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
559 mi2iMap.
insert(std::make_pair(&
MI, newIndex));
570 bool AllowBundled =
false);
582 if (mi2iItr == mi2iMap.
end())
584 SlotIndex replaceBaseIndex = mi2iItr->second;
587 "Mismatched instruction in index tables.");
589 mi2iMap.
erase(mi2iItr);
590 mi2iMap.
insert(std::make_pair(&NewMI, replaceBaseIndex));
591 return replaceBaseIndex;
600 "Can't insert a new block at the beginning of a function.");
608 mbb->
empty() ? endEntry
613 SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
614 SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
616 MBBRanges[prevMBB->getNumber()].second = startIdx;
619 "Blocks must be added in order");
620 MBBRanges.
push_back(std::make_pair(startIdx, endIdx));
623 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.
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()
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::...