IntervalMap.cpp Source File (original) (raw)

14#include

16namespace llvm {

20 assert(!path.empty() && "Can't replace missing root");

21 path.front() = Entry(Root, Size, Offsets.first);

22 path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));

23}

27 if (Level == 0)

31 unsigned l = Level - 1;

32 while (l && path[l].offset == 0)

33 --l;

36 if (path[l].offset == 0)

43 for (++l; l != Level; ++l)

45 return NR;

46}

49 assert(Level != 0 && "Cannot move the root node");

52 unsigned l = 0;

54 l = Level - 1;

55 while (path[l].offset == 0) {

56 assert(l != 0 && "Cannot move beyond begin()");

57 --l;

58 }

59 } else if (height() < Level)

61 path.resize(Level + 1, Entry(nullptr, 0, 0));

64 --path[l].offset;

68 for (++l; l != Level; ++l) {

69 path[l] = Entry(NR, NR.size() - 1);

71 }

72 path[l] = Entry(NR, NR.size() - 1);

73}

77 if (Level == 0)

81 unsigned l = Level - 1;

83 --l;

93 for (++l; l != Level; ++l)

95 return NR;

96}

99 assert(Level != 0 && "Cannot move the root node");

100

101

102 unsigned l = Level - 1;

104 --l;

105

106

107

108 if (++path[l].offset == path[l].size)

109 return;

111

112 for (++l; l != Level; ++l) {

113 path[l] = Entry(NR, 0);

115 }

116 path[l] = Entry(NR, 0);

117}

118

119

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");

125 if (!Nodes)

127

128

129 const unsigned PerNode = (Elements + Grow) / Nodes;

130 const unsigned Extra = (Elements + Grow) % Nodes;

132 unsigned Sum = 0;

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]));

137 }

138 assert(Sum == Elements + Grow && "Bad distribution sum");

139

140

141 if (Grow) {

142 assert(PosPair.first < Nodes && "Bad algebra");

143 assert(NewSize[PosPair.first] && "Too few elements to need Grow");

144 --NewSize[PosPair.first];

145 }

146

147#ifndef NDEBUG

148 Sum = 0;

149 for (unsigned n = 0; n != Nodes; ++n) {

150 assert(NewSize[n] <= Capacity && "Overallocated node");

151 Sum += NewSize[n];

152 }

153 assert(Sum == Elements && "Bad distribution sum");

154#endif

155

156 return PosPair;

157}

158

159}

160}

161

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements a coalescing interval map for small objects.

unsigned size() const

size - Return the number of elements in the referenced node.

NodeRef & subtree(unsigned i) const

subtree - Access the i'th subtree reference in a branch node.

LLVM_ABI void replaceRoot(void *Root, unsigned Size, IdxPair Offsets)

replaceRoot - Replace the current root node with two new entries after the tree height has increased.

Definition IntervalMap.cpp:19

bool valid() const

valid - Return true if path is at a valid node, not at end().

LLVM_ABI NodeRef getLeftSibling(unsigned Level) const

getLeftSibling - Get the left sibling node at Level, or a null NodeRef.

Definition IntervalMap.cpp:25

unsigned offset(unsigned Level) const

bool atLastEntry(unsigned Level) const

atLastEntry - Return true if the path is at the last entry of the node at Level.

unsigned height() const

height - Return the height of the tree corresponding to this path.

LLVM_ABI void moveRight(unsigned Level)

moveRight - Move path to the left sibling at Level.

Definition IntervalMap.cpp:98

LLVM_ABI NodeRef getRightSibling(unsigned Level) const

getLeftSibling - Get the left sibling node at Level, or a null NodeRef.

Definition IntervalMap.cpp:75

unsigned size(unsigned Level) const

LLVM_ABI void moveLeft(unsigned Level)

moveLeft - Move path to the left sibling at Level.

Definition IntervalMap.cpp:48

NodeRef & subtree(unsigned Level) const

subtree - Get the subtree referenced from Level.

IntervalMapImpl - Namespace used for IntervalMap implementation details.

std::pair< unsigned, unsigned > IdxPair

LLVM_ABI 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...

Definition IntervalMap.cpp:120

This is an optimization pass for GlobalISel generic memory operations.