Go to the documentation of this file.
17 namespace IntervalMapImpl {
20 assert(!path.empty() &&
"Can't replace missing root");
21 path.front() = Entry(Root, Size,
Offsets.first);
56 assert(
l != 0 &&
"Cannot move beyond begin()");
69 path[
l] = Entry(NR, NR.
size() - 1);
72 path[
l] = Entry(NR, NR.
size() - 1);
113 path[
l] = Entry(NR, 0);
116 path[
l] = Entry(NR, 0);
121 const unsigned *CurSize,
unsigned NewSize[],
122 unsigned Position,
bool Grow) {
123 assert(Elements + Grow <= Nodes * Capacity &&
"Not enough room for elements");
124 assert(Position <= Elements &&
"Invalid position");
129 const unsigned PerNode = (Elements + Grow) / Nodes;
130 const unsigned Extra = (Elements + Grow) % Nodes;
133 for (
unsigned n = 0;
n != Nodes; ++
n) {
134 Sum += NewSize[
n] = PerNode + (
n < Extra);
135 if (PosPair.first == Nodes && Sum > Position)
136 PosPair =
IdxPair(
n, Position - (Sum - NewSize[
n]));
138 assert(Sum == Elements + Grow &&
"Bad distribution sum");
142 assert(PosPair.first < Nodes &&
"Bad algebra");
143 assert(NewSize[PosPair.first] &&
"Too few elements to need Grow");
144 --NewSize[PosPair.first];
149 for (
unsigned n = 0;
n != Nodes; ++
n) {
150 assert(NewSize[
n] <= Capacity &&
"Overallocated node");
153 assert(Sum == Elements &&
"Bad distribution sum");
This is an optimization pass for GlobalISel generic memory operations.
NodeRef getLeftSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
bool valid() const
valid - Return true if path is at a valid node, not at end().
IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, const unsigned *CurSize, unsigned NewSize[], unsigned Position, bool Grow)
IntervalMapImpl::distribute - Compute a new distribution of node elements after an overflow or underf...
NodeRef & subtree(unsigned Level) const
subtree - Get the subtree referenced from Level.
std::pair< unsigned, unsigned > IdxPair
unsigned size() const
size - Return the number of elements in the referenced node.
unsigned offset(unsigned Level) const
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
std::pair< NodeId, LaneBitmask > NodeRef
void moveRight(unsigned Level)
moveRight - Move path to the left sibling at Level.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned height() const
height - Return the height of the tree corresponding to this path.
void moveLeft(unsigned Level)
moveLeft - Move path to the left sibling at Level.
NodeRef getRightSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
NodeRef & subtree(unsigned i) const
subtree - Access the i'th subtree reference in a branch node.
unsigned size(unsigned Level) const
void replaceRoot(void *Root, unsigned Size, IdxPair Offsets)
replaceRoot - Replace the current root node with two new entries after the tree height has increased.
bool atLastEntry(unsigned Level) const
atLastEntry - Return true if the path is at the last entry of the node at Level.
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
iterator insert(iterator I, T &&Elt)