LLVM  10.0.0svn
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 
15 namespace llvm {
16 namespace IntervalMapImpl {
17 
18 void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
19  assert(!path.empty() && "Can't replace missing root");
20  path.front() = Entry(Root, Size, Offsets.first);
21  path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
22 }
23 
25  // The root has no siblings.
26  if (Level == 0)
27  return NodeRef();
28 
29  // Go up the tree until we can go left.
30  unsigned l = Level - 1;
31  while (l && path[l].offset == 0)
32  --l;
33 
34  // We can't go left.
35  if (path[l].offset == 0)
36  return NodeRef();
37 
38  // NR is the subtree containing our left sibling.
39  NodeRef NR = path[l].subtree(path[l].offset - 1);
40 
41  // Keep right all the way down.
42  for (++l; l != Level; ++l)
43  NR = NR.subtree(NR.size() - 1);
44  return NR;
45 }
46 
47 void Path::moveLeft(unsigned Level) {
48  assert(Level != 0 && "Cannot move the root node");
49 
50  // Go up the tree until we can go left.
51  unsigned l = 0;
52  if (valid()) {
53  l = Level - 1;
54  while (path[l].offset == 0) {
55  assert(l != 0 && "Cannot move beyond begin()");
56  --l;
57  }
58  } else if (height() < Level)
59  // end() may have created a height=0 path.
60  path.resize(Level + 1, Entry(nullptr, 0, 0));
61 
62  // NR is the subtree containing our left sibling.
63  --path[l].offset;
64  NodeRef NR = subtree(l);
65 
66  // Get the rightmost node in the subtree.
67  for (++l; l != Level; ++l) {
68  path[l] = Entry(NR, NR.size() - 1);
69  NR = NR.subtree(NR.size() - 1);
70  }
71  path[l] = Entry(NR, NR.size() - 1);
72 }
73 
75  // The root has no siblings.
76  if (Level == 0)
77  return NodeRef();
78 
79  // Go up the tree until we can go right.
80  unsigned l = Level - 1;
81  while (l && atLastEntry(l))
82  --l;
83 
84  // We can't go right.
85  if (atLastEntry(l))
86  return NodeRef();
87 
88  // NR is the subtree containing our right sibling.
89  NodeRef NR = path[l].subtree(path[l].offset + 1);
90 
91  // Keep left all the way down.
92  for (++l; l != Level; ++l)
93  NR = NR.subtree(0);
94  return NR;
95 }
96 
97 void Path::moveRight(unsigned Level) {
98  assert(Level != 0 && "Cannot move the root node");
99 
100  // Go up the tree until we can go right.
101  unsigned l = Level - 1;
102  while (l && atLastEntry(l))
103  --l;
104 
105  // NR is the subtree containing our right sibling. If we hit end(), we have
106  // offset(0) == node(0).size().
107  if (++path[l].offset == path[l].size)
108  return;
109  NodeRef NR = subtree(l);
110 
111  for (++l; l != Level; ++l) {
112  path[l] = Entry(NR, 0);
113  NR = NR.subtree(0);
114  }
115  path[l] = Entry(NR, 0);
116 }
117 
118 
119 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
120  const unsigned *CurSize, unsigned NewSize[],
121  unsigned Position, bool Grow) {
122  assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements");
123  assert(Position <= Elements && "Invalid position");
124  if (!Nodes)
125  return IdxPair();
126 
127  // Trivial algorithm: left-leaning even distribution.
128  const unsigned PerNode = (Elements + Grow) / Nodes;
129  const unsigned Extra = (Elements + Grow) % Nodes;
130  IdxPair PosPair = IdxPair(Nodes, 0);
131  unsigned Sum = 0;
132  for (unsigned n = 0; n != Nodes; ++n) {
133  Sum += NewSize[n] = PerNode + (n < Extra);
134  if (PosPair.first == Nodes && Sum > Position)
135  PosPair = IdxPair(n, Position - (Sum - NewSize[n]));
136  }
137  assert(Sum == Elements + Grow && "Bad distribution sum");
138 
139  // Subtract the Grow element that was added.
140  if (Grow) {
141  assert(PosPair.first < Nodes && "Bad algebra");
142  assert(NewSize[PosPair.first] && "Too few elements to need Grow");
143  --NewSize[PosPair.first];
144  }
145 
146 #ifndef NDEBUG
147  Sum = 0;
148  for (unsigned n = 0; n != Nodes; ++n) {
149  assert(NewSize[n] <= Capacity && "Overallocated node");
150  Sum += NewSize[n];
151  }
152  assert(Sum == Elements && "Bad distribution sum");
153 #endif
154 
155  return PosPair;
156 }
157 
158 } // namespace IntervalMapImpl
159 } // namespace llvm
160 
NodeRef getRightSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
Definition: IntervalMap.cpp:74
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
void moveLeft(unsigned Level)
moveLeft - Move path to the left sibling at Level.
Definition: IntervalMap.cpp:47
Offsets
Offsets in bytes from the start of the input buffer.
Definition: SIInstrInfo.h:1100
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:18
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:24
std::pair< unsigned, unsigned > IdxPair
Definition: IntervalMap.h:190
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:467
void moveRight(unsigned Level)
moveRight - Move path to the left sibling at Level.
Definition: IntervalMap.cpp:97
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
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
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())
void resize(size_type N)
Definition: SmallVector.h:344