LLVM  11.0.0git
IntervalMap.cpp
Go to the documentation of this file.
1 //===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the few non-templated functions in IntervalMap.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/ADT/IntervalMap.h"
14 #include <cassert>
15 
16 namespace llvm {
17 namespace IntervalMapImpl {
18 
19 void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
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 }
24 
26  // The root has no siblings.
27  if (Level == 0)
28  return NodeRef();
29 
30  // Go up the tree until we can go left.
31  unsigned l = Level - 1;
32  while (l && path[l].offset == 0)
33  --l;
34 
35  // We can't go left.
36  if (path[l].offset == 0)
37  return NodeRef();
38 
39  // NR is the subtree containing our left sibling.
40  NodeRef NR = path[l].subtree(path[l].offset - 1);
41 
42  // Keep right all the way down.
43  for (++l; l != Level; ++l)
44  NR = NR.subtree(NR.size() - 1);
45  return NR;
46 }
47 
48 void Path::moveLeft(unsigned Level) {
49  assert(Level != 0 && "Cannot move the root node");
50 
51  // Go up the tree until we can go left.
52  unsigned l = 0;
53  if (valid()) {
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)
60  // end() may have created a height=0 path.
61  path.resize(Level + 1, Entry(nullptr, 0, 0));
62 
63  // NR is the subtree containing our left sibling.
64  --path[l].offset;
65  NodeRef NR = subtree(l);
66 
67  // Get the rightmost node in the subtree.
68  for (++l; l != Level; ++l) {
69  path[l] = Entry(NR, NR.size() - 1);
70  NR = NR.subtree(NR.size() - 1);
71  }
72  path[l] = Entry(NR, NR.size() - 1);
73 }
74 
76  // The root has no siblings.
77  if (Level == 0)
78  return NodeRef();
79 
80  // Go up the tree until we can go right.
81  unsigned l = Level - 1;
82  while (l && atLastEntry(l))
83  --l;
84 
85  // We can't go right.
86  if (atLastEntry(l))
87  return NodeRef();
88 
89  // NR is the subtree containing our right sibling.
90  NodeRef NR = path[l].subtree(path[l].offset + 1);
91 
92  // Keep left all the way down.
93  for (++l; l != Level; ++l)
94  NR = NR.subtree(0);
95  return NR;
96 }
97 
98 void Path::moveRight(unsigned Level) {
99  assert(Level != 0 && "Cannot move the root node");
100 
101  // Go up the tree until we can go right.
102  unsigned l = Level - 1;
103  while (l && atLastEntry(l))
104  --l;
105 
106  // NR is the subtree containing our right sibling. If we hit end(), we have
107  // offset(0) == node(0).size().
108  if (++path[l].offset == path[l].size)
109  return;
110  NodeRef NR = subtree(l);
111 
112  for (++l; l != Level; ++l) {
113  path[l] = Entry(NR, 0);
114  NR = NR.subtree(0);
115  }
116  path[l] = Entry(NR, 0);
117 }
118 
119 
120 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
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)
126  return IdxPair();
127 
128  // Trivial algorithm: left-leaning even distribution.
129  const unsigned PerNode = (Elements + Grow) / Nodes;
130  const unsigned Extra = (Elements + Grow) % Nodes;
131  IdxPair PosPair = IdxPair(Nodes, 0);
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  // Subtract the Grow element that was added.
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 } // namespace IntervalMapImpl
160 } // namespace llvm
161 
NodeRef getRightSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
Definition: IntervalMap.cpp:75
bool valid() const
valid - Return true if path is at a valid node, not at end().
Definition: IntervalMap.h:810
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:69
void moveLeft(unsigned Level)
moveLeft - Move path to the left sibling at Level.
Definition: IntervalMap.cpp:48
Offsets
Offsets in bytes from the start of the input buffer.
Definition: SIInstrInfo.h:1156
Position
Position to insert a new instruction relative to an existing instruction.
unsigned height() const
height - Return the height of the tree corresponding to this path.
Definition: IntervalMap.h:816
NodeRef & subtree(unsigned i) const
subtree - Access the i&#39;th subtree reference in a branch node.
Definition: IntervalMap.h:520
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...
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
NodeRef & subtree(unsigned Level) const
subtree - Get the subtree referenced from Level.
Definition: IntervalMap.h:821
unsigned size(unsigned Level) const
Definition: IntervalMap.h:797
NodeRef getLeftSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
Definition: IntervalMap.cpp:25
std::pair< unsigned, unsigned > IdxPair
Definition: IntervalMap.h:190
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:513
void moveRight(unsigned Level)
moveRight - Move path to the left sibling at Level.
Definition: IntervalMap.cpp:98
unsigned offset(unsigned Level) const
Definition: IntervalMap.h:798
unsigned size() const
size - Return the number of elements in the referenced node.
Definition: IntervalMap.h:512
uint32_t Size
Definition: Profile.cpp:46
bool atLastEntry(unsigned Level) const
atLastEntry - Return true if the path is at the last entry of the node at Level.
Definition: IntervalMap.h:907
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Level
Definition: Debugify.cpp:33
void resize(size_type N)
Definition: SmallVector.h:390