LLVM  13.0.0git
IntervalMap.h
Go to the documentation of this file.
1 //===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
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 a coalescing interval map for small objects.
10 //
11 // KeyT objects are mapped to ValT objects. Intervals of keys that map to the
12 // same value are represented in a compressed form.
13 //
14 // Iterators provide ordered access to the compressed intervals rather than the
15 // individual keys, and insert and erase operations use key intervals as well.
16 //
17 // Like SmallVector, IntervalMap will store the first N intervals in the map
18 // object itself without any allocations. When space is exhausted it switches to
19 // a B+-tree representation with very small overhead for small key and value
20 // objects.
21 //
22 // A Traits class specifies how keys are compared. It also allows IntervalMap to
23 // work with both closed and half-open intervals.
24 //
25 // Keys and values are not stored next to each other in a std::pair, so we don't
26 // provide such a value_type. Dereferencing iterators only returns the mapped
27 // value. The interval bounds are accessible through the start() and stop()
28 // iterator methods.
29 //
30 // IntervalMap is optimized for small key and value objects, 4 or 8 bytes each
31 // is the optimal size. For large objects use std::map instead.
32 //
33 //===----------------------------------------------------------------------===//
34 //
35 // Synopsis:
36 //
37 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
38 // class IntervalMap {
39 // public:
40 // typedef KeyT key_type;
41 // typedef ValT mapped_type;
42 // typedef RecyclingAllocator<...> Allocator;
43 // class iterator;
44 // class const_iterator;
45 //
46 // explicit IntervalMap(Allocator&);
47 // ~IntervalMap():
48 //
49 // bool empty() const;
50 // KeyT start() const;
51 // KeyT stop() const;
52 // ValT lookup(KeyT x, Value NotFound = Value()) const;
53 //
54 // const_iterator begin() const;
55 // const_iterator end() const;
56 // iterator begin();
57 // iterator end();
58 // const_iterator find(KeyT x) const;
59 // iterator find(KeyT x);
60 //
61 // void insert(KeyT a, KeyT b, ValT y);
62 // void clear();
63 // };
64 //
65 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
66 // class IntervalMap::const_iterator {
67 // public:
68 // using iterator_category = std::bidirectional_iterator_tag;
69 // using value_type = ValT;
70 // using difference_type = std::ptrdiff_t;
71 // using pointer = value_type *;
72 // using reference = value_type &;
73 //
74 // bool operator==(const const_iterator &) const;
75 // bool operator!=(const const_iterator &) const;
76 // bool valid() const;
77 //
78 // const KeyT &start() const;
79 // const KeyT &stop() const;
80 // const ValT &value() const;
81 // const ValT &operator*() const;
82 // const ValT *operator->() const;
83 //
84 // const_iterator &operator++();
85 // const_iterator &operator++(int);
86 // const_iterator &operator--();
87 // const_iterator &operator--(int);
88 // void goToBegin();
89 // void goToEnd();
90 // void find(KeyT x);
91 // void advanceTo(KeyT x);
92 // };
93 //
94 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
95 // class IntervalMap::iterator : public const_iterator {
96 // public:
97 // void insert(KeyT a, KeyT b, Value y);
98 // void erase();
99 // };
100 //
101 //===----------------------------------------------------------------------===//
102 
103 #ifndef LLVM_ADT_INTERVALMAP_H
104 #define LLVM_ADT_INTERVALMAP_H
105 
106 #include "llvm/ADT/PointerIntPair.h"
107 #include "llvm/ADT/SmallVector.h"
108 #include "llvm/ADT/bit.h"
109 #include "llvm/Support/AlignOf.h"
110 #include "llvm/Support/Allocator.h"
112 #include <algorithm>
113 #include <cassert>
114 #include <cstdint>
115 #include <iterator>
116 #include <new>
117 #include <utility>
118 
119 namespace llvm {
120 
121 //===----------------------------------------------------------------------===//
122 //--- Key traits ---//
123 //===----------------------------------------------------------------------===//
124 //
125 // The IntervalMap works with closed or half-open intervals.
126 // Adjacent intervals that map to the same value are coalesced.
127 //
128 // The IntervalMapInfo traits class is used to determine if a key is contained
129 // in an interval, and if two intervals are adjacent so they can be coalesced.
130 // The provided implementation works for closed integer intervals, other keys
131 // probably need a specialized version.
132 //
133 // The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
134 //
135 // It is assumed that (a;b] half-open intervals are not used, only [a;b) is
136 // allowed. This is so that stopLess(a, b) can be used to determine if two
137 // intervals overlap.
138 //
139 //===----------------------------------------------------------------------===//
140 
141 template <typename T>
143  /// startLess - Return true if x is not in [a;b].
144  /// This is x < a both for closed intervals and for [a;b) half-open intervals.
145  static inline bool startLess(const T &x, const T &a) {
146  return x < a;
147  }
148 
149  /// stopLess - Return true if x is not in [a;b].
150  /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
151  static inline bool stopLess(const T &b, const T &x) {
152  return b < x;
153  }
154 
155  /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
156  /// This is a+1 == b for closed intervals, a == b for half-open intervals.
157  static inline bool adjacent(const T &a, const T &b) {
158  return a+1 == b;
159  }
160 
161  /// nonEmpty - Return true if [a;b] is non-empty.
162  /// This is a <= b for a closed interval, a < b for [a;b) half-open intervals.
163  static inline bool nonEmpty(const T &a, const T &b) {
164  return a <= b;
165  }
166 };
167 
168 template <typename T>
170  /// startLess - Return true if x is not in [a;b).
171  static inline bool startLess(const T &x, const T &a) {
172  return x < a;
173  }
174 
175  /// stopLess - Return true if x is not in [a;b).
176  static inline bool stopLess(const T &b, const T &x) {
177  return b <= x;
178  }
179 
180  /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
181  static inline bool adjacent(const T &a, const T &b) {
182  return a == b;
183  }
184 
185  /// nonEmpty - Return true if [a;b) is non-empty.
186  static inline bool nonEmpty(const T &a, const T &b) {
187  return a < b;
188  }
189 };
190 
191 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
192 /// It should be considered private to the implementation.
193 namespace IntervalMapImpl {
194 
195 using IdxPair = std::pair<unsigned,unsigned>;
196 
197 //===----------------------------------------------------------------------===//
198 //--- IntervalMapImpl::NodeBase ---//
199 //===----------------------------------------------------------------------===//
200 //
201 // Both leaf and branch nodes store vectors of pairs.
202 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
203 //
204 // Keys and values are stored in separate arrays to avoid padding caused by
205 // different object alignments. This also helps improve locality of reference
206 // when searching the keys.
207 //
208 // The nodes don't know how many elements they contain - that information is
209 // stored elsewhere. Omitting the size field prevents padding and allows a node
210 // to fill the allocated cache lines completely.
211 //
212 // These are typical key and value sizes, the node branching factor (N), and
213 // wasted space when nodes are sized to fit in three cache lines (192 bytes):
214 //
215 // T1 T2 N Waste Used by
216 // 4 4 24 0 Branch<4> (32-bit pointers)
217 // 8 4 16 0 Leaf<4,4>, Branch<4>
218 // 8 8 12 0 Leaf<4,8>, Branch<8>
219 // 16 4 9 12 Leaf<8,4>
220 // 16 8 8 0 Leaf<8,8>
221 //
222 //===----------------------------------------------------------------------===//
223 
224 template <typename T1, typename T2, unsigned N>
225 class NodeBase {
226 public:
227  enum { Capacity = N };
228 
230  T2 second[N];
231 
232  /// copy - Copy elements from another node.
233  /// @param Other Node elements are copied from.
234  /// @param i Beginning of the source range in other.
235  /// @param j Beginning of the destination range in this.
236  /// @param Count Number of elements to copy.
237  template <unsigned M>
238  void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
239  unsigned j, unsigned Count) {
240  assert(i + Count <= M && "Invalid source range");
241  assert(j + Count <= N && "Invalid dest range");
242  for (unsigned e = i + Count; i != e; ++i, ++j) {
243  first[j] = Other.first[i];
244  second[j] = Other.second[i];
245  }
246  }
247 
248  /// moveLeft - Move elements to the left.
249  /// @param i Beginning of the source range.
250  /// @param j Beginning of the destination range.
251  /// @param Count Number of elements to copy.
252  void moveLeft(unsigned i, unsigned j, unsigned Count) {
253  assert(j <= i && "Use moveRight shift elements right");
254  copy(*this, i, j, Count);
255  }
256 
257  /// moveRight - Move elements to the right.
258  /// @param i Beginning of the source range.
259  /// @param j Beginning of the destination range.
260  /// @param Count Number of elements to copy.
261  void moveRight(unsigned i, unsigned j, unsigned Count) {
262  assert(i <= j && "Use moveLeft shift elements left");
263  assert(j + Count <= N && "Invalid range");
264  while (Count--) {
265  first[j + Count] = first[i + Count];
266  second[j + Count] = second[i + Count];
267  }
268  }
269 
270  /// erase - Erase elements [i;j).
271  /// @param i Beginning of the range to erase.
272  /// @param j End of the range. (Exclusive).
273  /// @param Size Number of elements in node.
274  void erase(unsigned i, unsigned j, unsigned Size) {
275  moveLeft(j, i, Size - j);
276  }
277 
278  /// erase - Erase element at i.
279  /// @param i Index of element to erase.
280  /// @param Size Number of elements in node.
281  void erase(unsigned i, unsigned Size) {
282  erase(i, i+1, Size);
283  }
284 
285  /// shift - Shift elements [i;size) 1 position to the right.
286  /// @param i Beginning of the range to move.
287  /// @param Size Number of elements in node.
288  void shift(unsigned i, unsigned Size) {
289  moveRight(i, i + 1, Size - i);
290  }
291 
292  /// transferToLeftSib - Transfer elements to a left sibling node.
293  /// @param Size Number of elements in this.
294  /// @param Sib Left sibling node.
295  /// @param SSize Number of elements in sib.
296  /// @param Count Number of elements to transfer.
297  void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
298  unsigned Count) {
299  Sib.copy(*this, 0, SSize, Count);
300  erase(0, Count, Size);
301  }
302 
303  /// transferToRightSib - Transfer elements to a right sibling node.
304  /// @param Size Number of elements in this.
305  /// @param Sib Right sibling node.
306  /// @param SSize Number of elements in sib.
307  /// @param Count Number of elements to transfer.
308  void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
309  unsigned Count) {
310  Sib.moveRight(0, Count, SSize);
311  Sib.copy(*this, Size-Count, 0, Count);
312  }
313 
314  /// adjustFromLeftSib - Adjust the number if elements in this node by moving
315  /// elements to or from a left sibling node.
316  /// @param Size Number of elements in this.
317  /// @param Sib Right sibling node.
318  /// @param SSize Number of elements in sib.
319  /// @param Add The number of elements to add to this node, possibly < 0.
320  /// @return Number of elements added to this node, possibly negative.
321  int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
322  if (Add > 0) {
323  // We want to grow, copy from sib.
324  unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
325  Sib.transferToRightSib(SSize, *this, Size, Count);
326  return Count;
327  } else {
328  // We want to shrink, copy to sib.
329  unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
330  transferToLeftSib(Size, Sib, SSize, Count);
331  return -Count;
332  }
333  }
334 };
335 
336 /// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
337 /// @param Node Array of pointers to sibling nodes.
338 /// @param Nodes Number of nodes.
339 /// @param CurSize Array of current node sizes, will be overwritten.
340 /// @param NewSize Array of desired node sizes.
341 template <typename NodeT>
342 void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
343  unsigned CurSize[], const unsigned NewSize[]) {
344  // Move elements right.
345  for (int n = Nodes - 1; n; --n) {
346  if (CurSize[n] == NewSize[n])
347  continue;
348  for (int m = n - 1; m != -1; --m) {
349  int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
350  NewSize[n] - CurSize[n]);
351  CurSize[m] -= d;
352  CurSize[n] += d;
353  // Keep going if the current node was exhausted.
354  if (CurSize[n] >= NewSize[n])
355  break;
356  }
357  }
358 
359  if (Nodes == 0)
360  return;
361 
362  // Move elements left.
363  for (unsigned n = 0; n != Nodes - 1; ++n) {
364  if (CurSize[n] == NewSize[n])
365  continue;
366  for (unsigned m = n + 1; m != Nodes; ++m) {
367  int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
368  CurSize[n] - NewSize[n]);
369  CurSize[m] += d;
370  CurSize[n] -= d;
371  // Keep going if the current node was exhausted.
372  if (CurSize[n] >= NewSize[n])
373  break;
374  }
375  }
376 
377 #ifndef NDEBUG
378  for (unsigned n = 0; n != Nodes; n++)
379  assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
380 #endif
381 }
382 
383 /// IntervalMapImpl::distribute - Compute a new distribution of node elements
384 /// after an overflow or underflow. Reserve space for a new element at Position,
385 /// and compute the node that will hold Position after redistributing node
386 /// elements.
387 ///
388 /// It is required that
389 ///
390 /// Elements == sum(CurSize), and
391 /// Elements + Grow <= Nodes * Capacity.
392 ///
393 /// NewSize[] will be filled in such that:
394 ///
395 /// sum(NewSize) == Elements, and
396 /// NewSize[i] <= Capacity.
397 ///
398 /// The returned index is the node where Position will go, so:
399 ///
400 /// sum(NewSize[0..idx-1]) <= Position
401 /// sum(NewSize[0..idx]) >= Position
402 ///
403 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
404 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
405 /// before the one holding the Position'th element where there is room for an
406 /// insertion.
407 ///
408 /// @param Nodes The number of nodes.
409 /// @param Elements Total elements in all nodes.
410 /// @param Capacity The capacity of each node.
411 /// @param CurSize Array[Nodes] of current node sizes, or NULL.
412 /// @param NewSize Array[Nodes] to receive the new node sizes.
413 /// @param Position Insert position.
414 /// @param Grow Reserve space for a new element at Position.
415 /// @return (node, offset) for Position.
416 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
417  const unsigned *CurSize, unsigned NewSize[],
418  unsigned Position, bool Grow);
419 
420 //===----------------------------------------------------------------------===//
421 //--- IntervalMapImpl::NodeSizer ---//
422 //===----------------------------------------------------------------------===//
423 //
424 // Compute node sizes from key and value types.
425 //
426 // The branching factors are chosen to make nodes fit in three cache lines.
427 // This may not be possible if keys or values are very large. Such large objects
428 // are handled correctly, but a std::map would probably give better performance.
429 //
430 //===----------------------------------------------------------------------===//
431 
432 enum {
433  // Cache line size. Most architectures have 32 or 64 byte cache lines.
434  // We use 64 bytes here because it provides good branching factors.
438 };
439 
440 template <typename KeyT, typename ValT>
441 struct NodeSizer {
442  enum {
443  // Compute the leaf node branching factor that makes a node fit in three
444  // cache lines. The branching factor must be at least 3, or some B+-tree
445  // balancing algorithms won't work.
446  // LeafSize can't be larger than CacheLineBytes. This is required by the
447  // PointerIntPair used by NodeRef.
449  static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
452  };
453 
455 
456  enum {
457  // Now that we have the leaf branching factor, compute the actual allocation
458  // unit size by rounding up to a whole number of cache lines.
460 
461  // Determine the branching factor for branch nodes.
463  static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
464  };
465 
466  /// Allocator - The recycling allocator used for both branch and leaf nodes.
467  /// This typedef is very likely to be identical for all IntervalMaps with
468  /// reasonably sized entries, so the same allocator can be shared among
469  /// different kinds of maps.
470  using Allocator =
472 };
473 
474 //===----------------------------------------------------------------------===//
475 //--- IntervalMapImpl::NodeRef ---//
476 //===----------------------------------------------------------------------===//
477 //
478 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
479 // pointer that can point to both kinds.
480 //
481 // All nodes are cache line aligned and the low 6 bits of a node pointer are
482 // always 0. These bits are used to store the number of elements in the
483 // referenced node. Besides saving space, placing node sizes in the parents
484 // allow tree balancing algorithms to run without faulting cache lines for nodes
485 // that may not need to be modified.
486 //
487 // A NodeRef doesn't know whether it references a leaf node or a branch node.
488 // It is the responsibility of the caller to use the correct types.
489 //
490 // Nodes are never supposed to be empty, and it is invalid to store a node size
491 // of 0 in a NodeRef. The valid range of sizes is 1-64.
492 //
493 //===----------------------------------------------------------------------===//
494 
495 class NodeRef {
496  struct CacheAlignedPointerTraits {
497  static inline void *getAsVoidPointer(void *P) { return P; }
498  static inline void *getFromVoidPointer(void *P) { return P; }
499  static constexpr int NumLowBitsAvailable = Log2CacheLine;
500  };
502 
503 public:
504  /// NodeRef - Create a null ref.
505  NodeRef() = default;
506 
507  /// operator bool - Detect a null ref.
508  explicit operator bool() const { return pip.getOpaqueValue(); }
509 
510  /// NodeRef - Create a reference to the node p with n elements.
511  template <typename NodeT>
512  NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
513  assert(n <= NodeT::Capacity && "Size too big for node");
514  }
515 
516  /// size - Return the number of elements in the referenced node.
517  unsigned size() const { return pip.getInt() + 1; }
518 
519  /// setSize - Update the node size.
520  void setSize(unsigned n) { pip.setInt(n - 1); }
521 
522  /// subtree - Access the i'th subtree reference in a branch node.
523  /// This depends on branch nodes storing the NodeRef array as their first
524  /// member.
525  NodeRef &subtree(unsigned i) const {
526  return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
527  }
528 
529  /// get - Dereference as a NodeT reference.
530  template <typename NodeT>
531  NodeT &get() const {
532  return *reinterpret_cast<NodeT*>(pip.getPointer());
533  }
534 
535  bool operator==(const NodeRef &RHS) const {
536  if (pip == RHS.pip)
537  return true;
538  assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
539  return false;
540  }
541 
542  bool operator!=(const NodeRef &RHS) const {
543  return !operator==(RHS);
544  }
545 };
546 
547 //===----------------------------------------------------------------------===//
548 //--- IntervalMapImpl::LeafNode ---//
549 //===----------------------------------------------------------------------===//
550 //
551 // Leaf nodes store up to N disjoint intervals with corresponding values.
552 //
553 // The intervals are kept sorted and fully coalesced so there are no adjacent
554 // intervals mapping to the same value.
555 //
556 // These constraints are always satisfied:
557 //
558 // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
559 //
560 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
561 //
562 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
563 // - Fully coalesced.
564 //
565 //===----------------------------------------------------------------------===//
566 
567 template <typename KeyT, typename ValT, unsigned N, typename Traits>
568 class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
569 public:
570  const KeyT &start(unsigned i) const { return this->first[i].first; }
571  const KeyT &stop(unsigned i) const { return this->first[i].second; }
572  const ValT &value(unsigned i) const { return this->second[i]; }
573 
574  KeyT &start(unsigned i) { return this->first[i].first; }
575  KeyT &stop(unsigned i) { return this->first[i].second; }
576  ValT &value(unsigned i) { return this->second[i]; }
577 
578  /// findFrom - Find the first interval after i that may contain x.
579  /// @param i Starting index for the search.
580  /// @param Size Number of elements in node.
581  /// @param x Key to search for.
582  /// @return First index with !stopLess(key[i].stop, x), or size.
583  /// This is the first interval that can possibly contain x.
584  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
585  assert(i <= Size && Size <= N && "Bad indices");
586  assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
587  "Index is past the needed point");
588  while (i != Size && Traits::stopLess(stop(i), x)) ++i;
589  return i;
590  }
591 
592  /// safeFind - Find an interval that is known to exist. This is the same as
593  /// findFrom except is it assumed that x is at least within range of the last
594  /// interval.
595  /// @param i Starting index for the search.
596  /// @param x Key to search for.
597  /// @return First index with !stopLess(key[i].stop, x), never size.
598  /// This is the first interval that can possibly contain x.
599  unsigned safeFind(unsigned i, KeyT x) const {
600  assert(i < N && "Bad index");
601  assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
602  "Index is past the needed point");
603  while (Traits::stopLess(stop(i), x)) ++i;
604  assert(i < N && "Unsafe intervals");
605  return i;
606  }
607 
608  /// safeLookup - Lookup mapped value for a safe key.
609  /// It is assumed that x is within range of the last entry.
610  /// @param x Key to search for.
611  /// @param NotFound Value to return if x is not in any interval.
612  /// @return The mapped value at x or NotFound.
613  ValT safeLookup(KeyT x, ValT NotFound) const {
614  unsigned i = safeFind(0, x);
615  return Traits::startLess(x, start(i)) ? NotFound : value(i);
616  }
617 
618  unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
619 };
620 
621 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
622 /// possible. This may cause the node to grow by 1, or it may cause the node
623 /// to shrink because of coalescing.
624 /// @param Pos Starting index = insertFrom(0, size, a)
625 /// @param Size Number of elements in node.
626 /// @param a Interval start.
627 /// @param b Interval stop.
628 /// @param y Value be mapped.
629 /// @return (insert position, new size), or (i, Capacity+1) on overflow.
630 template <typename KeyT, typename ValT, unsigned N, typename Traits>
632 insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
633  unsigned i = Pos;
634  assert(i <= Size && Size <= N && "Invalid index");
635  assert(!Traits::stopLess(b, a) && "Invalid interval");
636 
637  // Verify the findFrom invariant.
638  assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
639  assert((i == Size || !Traits::stopLess(stop(i), a)));
640  assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
641 
642  // Coalesce with previous interval.
643  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
644  Pos = i - 1;
645  // Also coalesce with next interval?
646  if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
647  stop(i - 1) = stop(i);
648  this->erase(i, Size);
649  return Size - 1;
650  }
651  stop(i - 1) = b;
652  return Size;
653  }
654 
655  // Detect overflow.
656  if (i == N)
657  return N + 1;
658 
659  // Add new interval at end.
660  if (i == Size) {
661  start(i) = a;
662  stop(i) = b;
663  value(i) = y;
664  return Size + 1;
665  }
666 
667  // Try to coalesce with following interval.
668  if (value(i) == y && Traits::adjacent(b, start(i))) {
669  start(i) = a;
670  return Size;
671  }
672 
673  // We must insert before i. Detect overflow.
674  if (Size == N)
675  return N + 1;
676 
677  // Insert before i.
678  this->shift(i, Size);
679  start(i) = a;
680  stop(i) = b;
681  value(i) = y;
682  return Size + 1;
683 }
684 
685 //===----------------------------------------------------------------------===//
686 //--- IntervalMapImpl::BranchNode ---//
687 //===----------------------------------------------------------------------===//
688 //
689 // A branch node stores references to 1--N subtrees all of the same height.
690 //
691 // The key array in a branch node holds the rightmost stop key of each subtree.
692 // It is redundant to store the last stop key since it can be found in the
693 // parent node, but doing so makes tree balancing a lot simpler.
694 //
695 // It is unusual for a branch node to only have one subtree, but it can happen
696 // in the root node if it is smaller than the normal nodes.
697 //
698 // When all of the leaf nodes from all the subtrees are concatenated, they must
699 // satisfy the same constraints as a single leaf node. They must be sorted,
700 // sane, and fully coalesced.
701 //
702 //===----------------------------------------------------------------------===//
703 
704 template <typename KeyT, typename ValT, unsigned N, typename Traits>
705 class BranchNode : public NodeBase<NodeRef, KeyT, N> {
706 public:
707  const KeyT &stop(unsigned i) const { return this->second[i]; }
708  const NodeRef &subtree(unsigned i) const { return this->first[i]; }
709 
710  KeyT &stop(unsigned i) { return this->second[i]; }
711  NodeRef &subtree(unsigned i) { return this->first[i]; }
712 
713  /// findFrom - Find the first subtree after i that may contain x.
714  /// @param i Starting index for the search.
715  /// @param Size Number of elements in node.
716  /// @param x Key to search for.
717  /// @return First index with !stopLess(key[i], x), or size.
718  /// This is the first subtree that can possibly contain x.
719  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
720  assert(i <= Size && Size <= N && "Bad indices");
721  assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
722  "Index to findFrom is past the needed point");
723  while (i != Size && Traits::stopLess(stop(i), x)) ++i;
724  return i;
725  }
726 
727  /// safeFind - Find a subtree that is known to exist. This is the same as
728  /// findFrom except is it assumed that x is in range.
729  /// @param i Starting index for the search.
730  /// @param x Key to search for.
731  /// @return First index with !stopLess(key[i], x), never size.
732  /// This is the first subtree that can possibly contain x.
733  unsigned safeFind(unsigned i, KeyT x) const {
734  assert(i < N && "Bad index");
735  assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
736  "Index is past the needed point");
737  while (Traits::stopLess(stop(i), x)) ++i;
738  assert(i < N && "Unsafe intervals");
739  return i;
740  }
741 
742  /// safeLookup - Get the subtree containing x, Assuming that x is in range.
743  /// @param x Key to search for.
744  /// @return Subtree containing x
746  return subtree(safeFind(0, x));
747  }
748 
749  /// insert - Insert a new (subtree, stop) pair.
750  /// @param i Insert position, following entries will be shifted.
751  /// @param Size Number of elements in node.
752  /// @param Node Subtree to insert.
753  /// @param Stop Last key in subtree.
754  void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
755  assert(Size < N && "branch node overflow");
756  assert(i <= Size && "Bad insert position");
757  this->shift(i, Size);
758  subtree(i) = Node;
759  stop(i) = Stop;
760  }
761 };
762 
763 //===----------------------------------------------------------------------===//
764 //--- IntervalMapImpl::Path ---//
765 //===----------------------------------------------------------------------===//
766 //
767 // A Path is used by iterators to represent a position in a B+-tree, and the
768 // path to get there from the root.
769 //
770 // The Path class also contains the tree navigation code that doesn't have to
771 // be templatized.
772 //
773 //===----------------------------------------------------------------------===//
774 
775 class Path {
776  /// Entry - Each step in the path is a node pointer and an offset into that
777  /// node.
778  struct Entry {
779  void *node;
780  unsigned size;
781  unsigned offset;
782 
783  Entry(void *Node, unsigned Size, unsigned Offset)
784  : node(Node), size(Size), offset(Offset) {}
785 
786  Entry(NodeRef Node, unsigned Offset)
787  : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
788 
789  NodeRef &subtree(unsigned i) const {
790  return reinterpret_cast<NodeRef*>(node)[i];
791  }
792  };
793 
794  /// path - The path entries, path[0] is the root node, path.back() is a leaf.
796 
797 public:
798  // Node accessors.
799  template <typename NodeT> NodeT &node(unsigned Level) const {
800  return *reinterpret_cast<NodeT*>(path[Level].node);
801  }
802  unsigned size(unsigned Level) const { return path[Level].size; }
803  unsigned offset(unsigned Level) const { return path[Level].offset; }
804  unsigned &offset(unsigned Level) { return path[Level].offset; }
805 
806  // Leaf accessors.
807  template <typename NodeT> NodeT &leaf() const {
808  return *reinterpret_cast<NodeT*>(path.back().node);
809  }
810  unsigned leafSize() const { return path.back().size; }
811  unsigned leafOffset() const { return path.back().offset; }
812  unsigned &leafOffset() { return path.back().offset; }
813 
814  /// valid - Return true if path is at a valid node, not at end().
815  bool valid() const {
816  return !path.empty() && path.front().offset < path.front().size;
817  }
818 
819  /// height - Return the height of the tree corresponding to this path.
820  /// This matches map->height in a full path.
821  unsigned height() const { return path.size() - 1; }
822 
823  /// subtree - Get the subtree referenced from Level. When the path is
824  /// consistent, node(Level + 1) == subtree(Level).
825  /// @param Level 0..height-1. The leaves have no subtrees.
826  NodeRef &subtree(unsigned Level) const {
827  return path[Level].subtree(path[Level].offset);
828  }
829 
830  /// reset - Reset cached information about node(Level) from subtree(Level -1).
831  /// @param Level 1..height. The node to update after parent node changed.
832  void reset(unsigned Level) {
833  path[Level] = Entry(subtree(Level - 1), offset(Level));
834  }
835 
836  /// push - Add entry to path.
837  /// @param Node Node to add, should be subtree(path.size()-1).
838  /// @param Offset Offset into Node.
839  void push(NodeRef Node, unsigned Offset) {
840  path.push_back(Entry(Node, Offset));
841  }
842 
843  /// pop - Remove the last path entry.
844  void pop() {
845  path.pop_back();
846  }
847 
848  /// setSize - Set the size of a node both in the path and in the tree.
849  /// @param Level 0..height. Note that setting the root size won't change
850  /// map->rootSize.
851  /// @param Size New node size.
852  void setSize(unsigned Level, unsigned Size) {
853  path[Level].size = Size;
854  if (Level)
855  subtree(Level - 1).setSize(Size);
856  }
857 
858  /// setRoot - Clear the path and set a new root node.
859  /// @param Node New root node.
860  /// @param Size New root size.
861  /// @param Offset Offset into root node.
862  void setRoot(void *Node, unsigned Size, unsigned Offset) {
863  path.clear();
864  path.push_back(Entry(Node, Size, Offset));
865  }
866 
867  /// replaceRoot - Replace the current root node with two new entries after the
868  /// tree height has increased.
869  /// @param Root The new root node.
870  /// @param Size Number of entries in the new root.
871  /// @param Offsets Offsets into the root and first branch nodes.
872  void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
873 
874  /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
875  /// @param Level Get the sibling to node(Level).
876  /// @return Left sibling, or NodeRef().
877  NodeRef getLeftSibling(unsigned Level) const;
878 
879  /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
880  /// unaltered.
881  /// @param Level Move node(Level).
882  void moveLeft(unsigned Level);
883 
884  /// fillLeft - Grow path to Height by taking leftmost branches.
885  /// @param Height The target height.
886  void fillLeft(unsigned Height) {
887  while (height() < Height)
888  push(subtree(height()), 0);
889  }
890 
891  /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
892  /// @param Level Get the sibling to node(Level).
893  /// @return Left sibling, or NodeRef().
894  NodeRef getRightSibling(unsigned Level) const;
895 
896  /// moveRight - Move path to the left sibling at Level. Leave nodes below
897  /// Level unaltered.
898  /// @param Level Move node(Level).
899  void moveRight(unsigned Level);
900 
901  /// atBegin - Return true if path is at begin().
902  bool atBegin() const {
903  for (unsigned i = 0, e = path.size(); i != e; ++i)
904  if (path[i].offset != 0)
905  return false;
906  return true;
907  }
908 
909  /// atLastEntry - Return true if the path is at the last entry of the node at
910  /// Level.
911  /// @param Level Node to examine.
912  bool atLastEntry(unsigned Level) const {
913  return path[Level].offset == path[Level].size - 1;
914  }
915 
916  /// legalizeForInsert - Prepare the path for an insertion at Level. When the
917  /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
918  /// ensures that node(Level) is real by moving back to the last node at Level,
919  /// and setting offset(Level) to size(Level) if required.
920  /// @param Level The level where an insertion is about to take place.
921  void legalizeForInsert(unsigned Level) {
922  if (valid())
923  return;
924  moveLeft(Level);
925  ++path[Level].offset;
926  }
927 };
928 
929 } // end namespace IntervalMapImpl
930 
931 //===----------------------------------------------------------------------===//
932 //--- IntervalMap ----//
933 //===----------------------------------------------------------------------===//
934 
935 template <typename KeyT, typename ValT,
936  unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
937  typename Traits = IntervalMapInfo<KeyT>>
938 class IntervalMap {
941  using Branch =
944  using IdxPair = IntervalMapImpl::IdxPair;
945 
946  // The RootLeaf capacity is given as a template parameter. We must compute the
947  // corresponding RootBranch capacity.
948  enum {
949  DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
950  (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
951  RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
952  };
953 
954  using RootBranch =
956 
957  // When branched, we store a global start key as well as the branch node.
958  struct RootBranchData {
959  KeyT start;
961  };
962 
963 public:
964  using Allocator = typename Sizer::Allocator;
965  using KeyType = KeyT;
966  using ValueType = ValT;
967  using KeyTraits = Traits;
968 
969 private:
970  // The root data is either a RootLeaf or a RootBranchData instance.
972 
973  // Tree height.
974  // 0: Leaves in root.
975  // 1: Root points to leaf.
976  // 2: root->branch->leaf ...
977  unsigned height;
978 
979  // Number of entries in the root node.
980  unsigned rootSize;
981 
982  // Allocator used for creating external nodes.
983  Allocator &allocator;
984 
985  /// Represent data as a node type without breaking aliasing rules.
986  template <typename T> T &dataAs() const { return *bit_cast<T *>(&data); }
987 
988  const RootLeaf &rootLeaf() const {
989  assert(!branched() && "Cannot acces leaf data in branched root");
990  return dataAs<RootLeaf>();
991  }
992  RootLeaf &rootLeaf() {
993  assert(!branched() && "Cannot acces leaf data in branched root");
994  return dataAs<RootLeaf>();
995  }
996 
997  RootBranchData &rootBranchData() const {
998  assert(branched() && "Cannot access branch data in non-branched root");
999  return dataAs<RootBranchData>();
1000  }
1001  RootBranchData &rootBranchData() {
1002  assert(branched() && "Cannot access branch data in non-branched root");
1003  return dataAs<RootBranchData>();
1004  }
1005 
1006  const RootBranch &rootBranch() const { return rootBranchData().node; }
1007  RootBranch &rootBranch() { return rootBranchData().node; }
1008  KeyT rootBranchStart() const { return rootBranchData().start; }
1009  KeyT &rootBranchStart() { return rootBranchData().start; }
1010 
1011  template <typename NodeT> NodeT *newNode() {
1012  return new(allocator.template Allocate<NodeT>()) NodeT();
1013  }
1014 
1015  template <typename NodeT> void deleteNode(NodeT *P) {
1016  P->~NodeT();
1017  allocator.Deallocate(P);
1018  }
1019 
1020  IdxPair branchRoot(unsigned Position);
1021  IdxPair splitRoot(unsigned Position);
1022 
1023  void switchRootToBranch() {
1024  rootLeaf().~RootLeaf();
1025  height = 1;
1026  new (&rootBranchData()) RootBranchData();
1027  }
1028 
1029  void switchRootToLeaf() {
1030  rootBranchData().~RootBranchData();
1031  height = 0;
1032  new(&rootLeaf()) RootLeaf();
1033  }
1034 
1035  bool branched() const { return height > 0; }
1036 
1037  ValT treeSafeLookup(KeyT x, ValT NotFound) const;
1038  void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
1039  unsigned Level));
1040  void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
1041 
1042 public:
1043  explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
1044  assert((uintptr_t(&data) & (alignof(RootLeaf) - 1)) == 0 &&
1045  "Insufficient alignment");
1046  new(&rootLeaf()) RootLeaf();
1047  }
1048 
1050  clear();
1051  rootLeaf().~RootLeaf();
1052  }
1053 
1054  /// empty - Return true when no intervals are mapped.
1055  bool empty() const {
1056  return rootSize == 0;
1057  }
1058 
1059  /// start - Return the smallest mapped key in a non-empty map.
1060  KeyT start() const {
1061  assert(!empty() && "Empty IntervalMap has no start");
1062  return !branched() ? rootLeaf().start(0) : rootBranchStart();
1063  }
1064 
1065  /// stop - Return the largest mapped key in a non-empty map.
1066  KeyT stop() const {
1067  assert(!empty() && "Empty IntervalMap has no stop");
1068  return !branched() ? rootLeaf().stop(rootSize - 1) :
1069  rootBranch().stop(rootSize - 1);
1070  }
1071 
1072  /// lookup - Return the mapped value at x or NotFound.
1074  if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1075  return NotFound;
1076  return branched() ? treeSafeLookup(x, NotFound) :
1077  rootLeaf().safeLookup(x, NotFound);
1078  }
1079 
1080  /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1081  /// It is assumed that no key in the interval is mapped to another value, but
1082  /// overlapping intervals already mapped to y will be coalesced.
1083  void insert(KeyT a, KeyT b, ValT y) {
1084  if (branched() || rootSize == RootLeaf::Capacity)
1085  return find(a).insert(a, b, y);
1086 
1087  // Easy insert into root leaf.
1088  unsigned p = rootLeaf().findFrom(0, rootSize, a);
1089  rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
1090  }
1091 
1092  /// clear - Remove all entries.
1093  void clear();
1094 
1095  class const_iterator;
1096  class iterator;
1097  friend class const_iterator;
1098  friend class iterator;
1099 
1101  const_iterator I(*this);
1102  I.goToBegin();
1103  return I;
1104  }
1105 
1107  iterator I(*this);
1108  I.goToBegin();
1109  return I;
1110  }
1111 
1113  const_iterator I(*this);
1114  I.goToEnd();
1115  return I;
1116  }
1117 
1119  iterator I(*this);
1120  I.goToEnd();
1121  return I;
1122  }
1123 
1124  /// find - Return an iterator pointing to the first interval ending at or
1125  /// after x, or end().
1127  const_iterator I(*this);
1128  I.find(x);
1129  return I;
1130  }
1131 
1133  iterator I(*this);
1134  I.find(x);
1135  return I;
1136  }
1137 
1138  /// overlaps(a, b) - Return true if the intervals in this map overlap with the
1139  /// interval [a;b].
1140  bool overlaps(KeyT a, KeyT b) {
1141  assert(Traits::nonEmpty(a, b));
1142  const_iterator I = find(a);
1143  if (!I.valid())
1144  return false;
1145  // [a;b] and [x;y] overlap iff x<=b and a<=y. The find() call guarantees the
1146  // second part (y = find(a).stop()), so it is sufficient to check the first
1147  // one.
1148  return !Traits::stopLess(b, I.start());
1149  }
1150 };
1151 
1152 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1153 /// branched root.
1154 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1155 ValT IntervalMap<KeyT, ValT, N, Traits>::
1156 treeSafeLookup(KeyT x, ValT NotFound) const {
1157  assert(branched() && "treeLookup assumes a branched root");
1158 
1159  IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
1160  for (unsigned h = height-1; h; --h)
1161  NR = NR.get<Branch>().safeLookup(x);
1162  return NR.get<Leaf>().safeLookup(x, NotFound);
1163 }
1164 
1165 // branchRoot - Switch from a leaf root to a branched root.
1166 // Return the new (root offset, node offset) corresponding to Position.
1167 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1168 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1169 branchRoot(unsigned Position) {
1170  using namespace IntervalMapImpl;
1171  // How many external leaf nodes to hold RootLeaf+1?
1172  const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1173 
1174  // Compute element distribution among new nodes.
1175  unsigned size[Nodes];
1176  IdxPair NewOffset(0, Position);
1177 
1178  // Is is very common for the root node to be smaller than external nodes.
1179  if (Nodes == 1)
1180  size[0] = rootSize;
1181  else
1182  NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size,
1183  Position, true);
1184 
1185  // Allocate new nodes.
1186  unsigned pos = 0;
1187  NodeRef node[Nodes];
1188  for (unsigned n = 0; n != Nodes; ++n) {
1189  Leaf *L = newNode<Leaf>();
1190  L->copy(rootLeaf(), pos, 0, size[n]);
1191  node[n] = NodeRef(L, size[n]);
1192  pos += size[n];
1193  }
1194 
1195  // Destroy the old leaf node, construct branch node instead.
1196  switchRootToBranch();
1197  for (unsigned n = 0; n != Nodes; ++n) {
1198  rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1199  rootBranch().subtree(n) = node[n];
1200  }
1201  rootBranchStart() = node[0].template get<Leaf>().start(0);
1202  rootSize = Nodes;
1203  return NewOffset;
1204 }
1205 
1206 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
1207 // Return the new (root offset, node offset) corresponding to Position.
1208 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1209 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1210 splitRoot(unsigned Position) {
1211  using namespace IntervalMapImpl;
1212  // How many external leaf nodes to hold RootBranch+1?
1213  const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1214 
1215  // Compute element distribution among new nodes.
1216  unsigned Size[Nodes];
1217  IdxPair NewOffset(0, Position);
1218 
1219  // Is is very common for the root node to be smaller than external nodes.
1220  if (Nodes == 1)
1221  Size[0] = rootSize;
1222  else
1223  NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size,
1224  Position, true);
1225 
1226  // Allocate new nodes.
1227  unsigned Pos = 0;
1228  NodeRef Node[Nodes];
1229  for (unsigned n = 0; n != Nodes; ++n) {
1230  Branch *B = newNode<Branch>();
1231  B->copy(rootBranch(), Pos, 0, Size[n]);
1232  Node[n] = NodeRef(B, Size[n]);
1233  Pos += Size[n];
1234  }
1235 
1236  for (unsigned n = 0; n != Nodes; ++n) {
1237  rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1238  rootBranch().subtree(n) = Node[n];
1239  }
1240  rootSize = Nodes;
1241  ++height;
1242  return NewOffset;
1243 }
1244 
1245 /// visitNodes - Visit each external node.
1246 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1247 void IntervalMap<KeyT, ValT, N, Traits>::
1248 visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1249  if (!branched())
1250  return;
1251  SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1252 
1253  // Collect level 0 nodes from the root.
1254  for (unsigned i = 0; i != rootSize; ++i)
1255  Refs.push_back(rootBranch().subtree(i));
1256 
1257  // Visit all branch nodes.
1258  for (unsigned h = height - 1; h; --h) {
1259  for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1260  for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1261  NextRefs.push_back(Refs[i].subtree(j));
1262  (this->*f)(Refs[i], h);
1263  }
1264  Refs.clear();
1265  Refs.swap(NextRefs);
1266  }
1267 
1268  // Visit all leaf nodes.
1269  for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1270  (this->*f)(Refs[i], 0);
1271 }
1272 
1273 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1274 void IntervalMap<KeyT, ValT, N, Traits>::
1275 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1276  if (Level)
1277  deleteNode(&Node.get<Branch>());
1278  else
1279  deleteNode(&Node.get<Leaf>());
1280 }
1281 
1282 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1285  if (branched()) {
1286  visitNodes(&IntervalMap::deleteNode);
1287  switchRootToLeaf();
1288  }
1289  rootSize = 0;
1290 }
1291 
1292 //===----------------------------------------------------------------------===//
1293 //--- IntervalMap::const_iterator ----//
1294 //===----------------------------------------------------------------------===//
1295 
1296 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1297 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator {
1298  friend class IntervalMap;
1299 
1300 public:
1301  using iterator_category = std::bidirectional_iterator_tag;
1302  using value_type = ValT;
1303  using difference_type = std::ptrdiff_t;
1304  using pointer = value_type *;
1306 
1307 protected:
1308  // The map referred to.
1309  IntervalMap *map = nullptr;
1310 
1311  // We store a full path from the root to the current position.
1312  // The path may be partially filled, but never between iterator calls.
1314 
1315  explicit const_iterator(const IntervalMap &map) :
1316  map(const_cast<IntervalMap*>(&map)) {}
1317 
1318  bool branched() const {
1319  assert(map && "Invalid iterator");
1320  return map->branched();
1321  }
1322 
1323  void setRoot(unsigned Offset) {
1324  if (branched())
1325  path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1326  else
1327  path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
1328  }
1329 
1330  void pathFillFind(KeyT x);
1331  void treeFind(KeyT x);
1332  void treeAdvanceTo(KeyT x);
1333 
1334  /// unsafeStart - Writable access to start() for iterator.
1335  KeyT &unsafeStart() const {
1336  assert(valid() && "Cannot access invalid iterator");
1337  return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1338  path.leaf<RootLeaf>().start(path.leafOffset());
1339  }
1340 
1341  /// unsafeStop - Writable access to stop() for iterator.
1342  KeyT &unsafeStop() const {
1343  assert(valid() && "Cannot access invalid iterator");
1344  return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1345  path.leaf<RootLeaf>().stop(path.leafOffset());
1346  }
1347 
1348  /// unsafeValue - Writable access to value() for iterator.
1349  ValT &unsafeValue() const {
1350  assert(valid() && "Cannot access invalid iterator");
1351  return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1352  path.leaf<RootLeaf>().value(path.leafOffset());
1353  }
1354 
1355 public:
1356  /// const_iterator - Create an iterator that isn't pointing anywhere.
1357  const_iterator() = default;
1358 
1359  /// setMap - Change the map iterated over. This call must be followed by a
1360  /// call to goToBegin(), goToEnd(), or find()
1361  void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
1362 
1363  /// valid - Return true if the current position is valid, false for end().
1364  bool valid() const { return path.valid(); }
1365 
1366  /// atBegin - Return true if the current position is the first map entry.
1367  bool atBegin() const { return path.atBegin(); }
1368 
1369  /// start - Return the beginning of the current interval.
1370  const KeyT &start() const { return unsafeStart(); }
1371 
1372  /// stop - Return the end of the current interval.
1373  const KeyT &stop() const { return unsafeStop(); }
1374 
1375  /// value - Return the mapped value at the current interval.
1376  const ValT &value() const { return unsafeValue(); }
1377 
1378  const ValT &operator*() const { return value(); }
1379 
1380  bool operator==(const const_iterator &RHS) const {
1381  assert(map == RHS.map && "Cannot compare iterators from different maps");
1382  if (!valid())
1383  return !RHS.valid();
1384  if (path.leafOffset() != RHS.path.leafOffset())
1385  return false;
1386  return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1387  }
1388 
1389  bool operator!=(const const_iterator &RHS) const {
1390  return !operator==(RHS);
1391  }
1392 
1393  /// goToBegin - Move to the first interval in map.
1394  void goToBegin() {
1395  setRoot(0);
1396  if (branched())
1397  path.fillLeft(map->height);
1398  }
1399 
1400  /// goToEnd - Move beyond the last interval in map.
1401  void goToEnd() {
1402  setRoot(map->rootSize);
1403  }
1404 
1405  /// preincrement - Move to the next interval.
1407  assert(valid() && "Cannot increment end()");
1408  if (++path.leafOffset() == path.leafSize() && branched())
1409  path.moveRight(map->height);
1410  return *this;
1411  }
1412 
1413  /// postincrement - Don't do that!
1415  const_iterator tmp = *this;
1416  operator++();
1417  return tmp;
1418  }
1419 
1420  /// predecrement - Move to the previous interval.
1422  if (path.leafOffset() && (valid() || !branched()))
1423  --path.leafOffset();
1424  else
1425  path.moveLeft(map->height);
1426  return *this;
1427  }
1428 
1429  /// postdecrement - Don't do that!
1431  const_iterator tmp = *this;
1432  operator--();
1433  return tmp;
1434  }
1435 
1436  /// find - Move to the first interval with stop >= x, or end().
1437  /// This is a full search from the root, the current position is ignored.
1438  void find(KeyT x) {
1439  if (branched())
1440  treeFind(x);
1441  else
1442  setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
1443  }
1444 
1445  /// advanceTo - Move to the first interval with stop >= x, or end().
1446  /// The search is started from the current position, and no earlier positions
1447  /// can be found. This is much faster than find() for small moves.
1448  void advanceTo(KeyT x) {
1449  if (!valid())
1450  return;
1451  if (branched())
1452  treeAdvanceTo(x);
1453  else
1454  path.leafOffset() =
1455  map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1456  }
1457 };
1458 
1459 /// pathFillFind - Complete path by searching for x.
1460 /// @param x Key to search for.
1461 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1464  IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1465  for (unsigned i = map->height - path.height() - 1; i; --i) {
1466  unsigned p = NR.get<Branch>().safeFind(0, x);
1467  path.push(NR, p);
1468  NR = NR.subtree(p);
1469  }
1470  path.push(NR, NR.get<Leaf>().safeFind(0, x));
1471 }
1472 
1473 /// treeFind - Find in a branched tree.
1474 /// @param x Key to search for.
1475 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1478  setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1479  if (valid())
1480  pathFillFind(x);
1481 }
1482 
1483 /// treeAdvanceTo - Find position after the current one.
1484 /// @param x Key to search for.
1485 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1488  // Can we stay on the same leaf node?
1489  if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1490  path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1491  return;
1492  }
1493 
1494  // Drop the current leaf.
1495  path.pop();
1496 
1497  // Search towards the root for a usable subtree.
1498  if (path.height()) {
1499  for (unsigned l = path.height() - 1; l; --l) {
1500  if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1501  // The branch node at l+1 is usable
1502  path.offset(l + 1) =
1503  path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
1504  return pathFillFind(x);
1505  }
1506  path.pop();
1507  }
1508  // Is the level-1 Branch usable?
1509  if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1510  path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
1511  return pathFillFind(x);
1512  }
1513  }
1514 
1515  // We reached the root.
1516  setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1517  if (valid())
1518  pathFillFind(x);
1519 }
1520 
1521 //===----------------------------------------------------------------------===//
1522 //--- IntervalMap::iterator ----//
1523 //===----------------------------------------------------------------------===//
1524 
1525 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1526 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1527  friend class IntervalMap;
1528 
1529  using IdxPair = IntervalMapImpl::IdxPair;
1530 
1531  explicit iterator(IntervalMap &map) : const_iterator(map) {}
1532 
1533  void setNodeStop(unsigned Level, KeyT Stop);
1534  bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1535  template <typename NodeT> bool overflow(unsigned Level);
1536  void treeInsert(KeyT a, KeyT b, ValT y);
1537  void eraseNode(unsigned Level);
1538  void treeErase(bool UpdateRoot = true);
1539  bool canCoalesceLeft(KeyT Start, ValT x);
1540  bool canCoalesceRight(KeyT Stop, ValT x);
1541 
1542 public:
1543  /// iterator - Create null iterator.
1544  iterator() = default;
1545 
1546  /// setStart - Move the start of the current interval.
1547  /// This may cause coalescing with the previous interval.
1548  /// @param a New start key, must not overlap the previous interval.
1549  void setStart(KeyT a);
1550 
1551  /// setStop - Move the end of the current interval.
1552  /// This may cause coalescing with the following interval.
1553  /// @param b New stop key, must not overlap the following interval.
1554  void setStop(KeyT b);
1555 
1556  /// setValue - Change the mapped value of the current interval.
1557  /// This may cause coalescing with the previous and following intervals.
1558  /// @param x New value.
1559  void setValue(ValT x);
1560 
1561  /// setStartUnchecked - Move the start of the current interval without
1562  /// checking for coalescing or overlaps.
1563  /// This should only be used when it is known that coalescing is not required.
1564  /// @param a New start key.
1565  void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
1566 
1567  /// setStopUnchecked - Move the end of the current interval without checking
1568  /// for coalescing or overlaps.
1569  /// This should only be used when it is known that coalescing is not required.
1570  /// @param b New stop key.
1572  this->unsafeStop() = b;
1573  // Update keys in branch nodes as well.
1574  if (this->path.atLastEntry(this->path.height()))
1575  setNodeStop(this->path.height(), b);
1576  }
1577 
1578  /// setValueUnchecked - Change the mapped value of the current interval
1579  /// without checking for coalescing.
1580  /// @param x New value.
1581  void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
1582 
1583  /// insert - Insert mapping [a;b] -> y before the current position.
1584  void insert(KeyT a, KeyT b, ValT y);
1585 
1586  /// erase - Erase the current interval.
1587  void erase();
1588 
1591  return *this;
1592  }
1593 
1595  iterator tmp = *this;
1596  operator++();
1597  return tmp;
1598  }
1599 
1602  return *this;
1603  }
1604 
1606  iterator tmp = *this;
1607  operator--();
1608  return tmp;
1609  }
1610 };
1611 
1612 /// canCoalesceLeft - Can the current interval coalesce to the left after
1613 /// changing start or value?
1614 /// @param Start New start of current interval.
1615 /// @param Value New value for current interval.
1616 /// @return True when updating the current interval would enable coalescing.
1617 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1619 iterator::canCoalesceLeft(KeyT Start, ValT Value) {
1620  using namespace IntervalMapImpl;
1621  Path &P = this->path;
1622  if (!this->branched()) {
1623  unsigned i = P.leafOffset();
1624  RootLeaf &Node = P.leaf<RootLeaf>();
1625  return i && Node.value(i-1) == Value &&
1626  Traits::adjacent(Node.stop(i-1), Start);
1627  }
1628  // Branched.
1629  if (unsigned i = P.leafOffset()) {
1630  Leaf &Node = P.leaf<Leaf>();
1631  return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
1632  } else if (NodeRef NR = P.getLeftSibling(P.height())) {
1633  unsigned i = NR.size() - 1;
1634  Leaf &Node = NR.get<Leaf>();
1635  return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
1636  }
1637  return false;
1638 }
1639 
1640 /// canCoalesceRight - Can the current interval coalesce to the right after
1641 /// changing stop or value?
1642 /// @param Stop New stop of current interval.
1643 /// @param Value New value for current interval.
1644 /// @return True when updating the current interval would enable coalescing.
1645 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1646 bool IntervalMap<KeyT, ValT, N, Traits>::
1647 iterator::canCoalesceRight(KeyT Stop, ValT Value) {
1648  using namespace IntervalMapImpl;
1649  Path &P = this->path;
1650  unsigned i = P.leafOffset() + 1;
1651  if (!this->branched()) {
1652  if (i >= P.leafSize())
1653  return false;
1654  RootLeaf &Node = P.leaf<RootLeaf>();
1655  return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1656  }
1657  // Branched.
1658  if (i < P.leafSize()) {
1659  Leaf &Node = P.leaf<Leaf>();
1660  return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1661  } else if (NodeRef NR = P.getRightSibling(P.height())) {
1662  Leaf &Node = NR.get<Leaf>();
1663  return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
1664  }
1665  return false;
1666 }
1667 
1668 /// setNodeStop - Update the stop key of the current node at level and above.
1669 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1670 void IntervalMap<KeyT, ValT, N, Traits>::
1671 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1672  // There are no references to the root node, so nothing to update.
1673  if (!Level)
1674  return;
1675  IntervalMapImpl::Path &P = this->path;
1676  // Update nodes pointing to the current node.
1677  while (--Level) {
1678  P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1679  if (!P.atLastEntry(Level))
1680  return;
1681  }
1682  // Update root separately since it has a different layout.
1683  P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1684 }
1685 
1686 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1689  assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");
1690  KeyT &CurStart = this->unsafeStart();
1691  if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
1692  CurStart = a;
1693  return;
1694  }
1695  // Coalesce with the interval to the left.
1696  --*this;
1697  a = this->start();
1698  erase();
1699  setStartUnchecked(a);
1700 }
1701 
1702 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1705  assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");
1706  if (Traits::startLess(b, this->stop()) ||
1707  !canCoalesceRight(b, this->value())) {
1708  setStopUnchecked(b);
1709  return;
1710  }
1711  // Coalesce with interval to the right.
1712  KeyT a = this->start();
1713  erase();
1714  setStartUnchecked(a);
1715 }
1716 
1717 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1721  if (canCoalesceRight(this->stop(), x)) {
1722  KeyT a = this->start();
1723  erase();
1724  setStartUnchecked(a);
1725  }
1726  if (canCoalesceLeft(this->start(), x)) {
1727  --*this;
1728  KeyT a = this->start();
1729  erase();
1730  setStartUnchecked(a);
1731  }
1732 }
1733 
1734 /// insertNode - insert a node before the current path at level.
1735 /// Leave the current path pointing at the new node.
1736 /// @param Level path index of the node to be inserted.
1737 /// @param Node The node to be inserted.
1738 /// @param Stop The last index in the new node.
1739 /// @return True if the tree height was increased.
1740 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1743  assert(Level && "Cannot insert next to the root");
1744  bool SplitRoot = false;
1745  IntervalMap &IM = *this->map;
1746  IntervalMapImpl::Path &P = this->path;
1747 
1748  if (Level == 1) {
1749  // Insert into the root branch node.
1750  if (IM.rootSize < RootBranch::Capacity) {
1751  IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1752  P.setSize(0, ++IM.rootSize);
1753  P.reset(Level);
1754  return SplitRoot;
1755  }
1756 
1757  // We need to split the root while keeping our position.
1758  SplitRoot = true;
1759  IdxPair Offset = IM.splitRoot(P.offset(0));
1760  P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1761 
1762  // Fall through to insert at the new higher level.
1763  ++Level;
1764  }
1765 
1766  // When inserting before end(), make sure we have a valid path.
1767  P.legalizeForInsert(--Level);
1768 
1769  // Insert into the branch node at Level-1.
1770  if (P.size(Level) == Branch::Capacity) {
1771  // Branch node is full, handle handle the overflow.
1772  assert(!SplitRoot && "Cannot overflow after splitting the root");
1773  SplitRoot = overflow<Branch>(Level);
1774  Level += SplitRoot;
1775  }
1776  P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1777  P.setSize(Level, P.size(Level) + 1);
1778  if (P.atLastEntry(Level))
1779  setNodeStop(Level, Stop);
1780  P.reset(Level + 1);
1781  return SplitRoot;
1782 }
1783 
1784 // insert
1785 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1788  if (this->branched())
1789  return treeInsert(a, b, y);
1790  IntervalMap &IM = *this->map;
1791  IntervalMapImpl::Path &P = this->path;
1792 
1793  // Try simple root leaf insert.
1794  unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
1795 
1796  // Was the root node insert successful?
1797  if (Size <= RootLeaf::Capacity) {
1798  P.setSize(0, IM.rootSize = Size);
1799  return;
1800  }
1801 
1802  // Root leaf node is full, we must branch.
1803  IdxPair Offset = IM.branchRoot(P.leafOffset());
1804  P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1805 
1806  // Now it fits in the new leaf.
1807  treeInsert(a, b, y);
1808 }
1809 
1810 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1813  using namespace IntervalMapImpl;
1814  Path &P = this->path;
1815 
1816  if (!P.valid())
1817  P.legalizeForInsert(this->map->height);
1818 
1819  // Check if this insertion will extend the node to the left.
1820  if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1821  // Node is growing to the left, will it affect a left sibling node?
1822  if (NodeRef Sib = P.getLeftSibling(P.height())) {
1823  Leaf &SibLeaf = Sib.get<Leaf>();
1824  unsigned SibOfs = Sib.size() - 1;
1825  if (SibLeaf.value(SibOfs) == y &&
1826  Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1827  // This insertion will coalesce with the last entry in SibLeaf. We can
1828  // handle it in two ways:
1829  // 1. Extend SibLeaf.stop to b and be done, or
1830  // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
1831  // We prefer 1., but need 2 when coalescing to the right as well.
1832  Leaf &CurLeaf = P.leaf<Leaf>();
1833  P.moveLeft(P.height());
1834  if (Traits::stopLess(b, CurLeaf.start(0)) &&
1835  (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
1836  // Easy, just extend SibLeaf and we're done.
1837  setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
1838  return;
1839  } else {
1840  // We have both left and right coalescing. Erase the old SibLeaf entry
1841  // and continue inserting the larger interval.
1842  a = SibLeaf.start(SibOfs);
1843  treeErase(/* UpdateRoot= */false);
1844  }
1845  }
1846  } else {
1847  // No left sibling means we are at begin(). Update cached bound.
1848  this->map->rootBranchStart() = a;
1849  }
1850  }
1851 
1852  // When we are inserting at the end of a leaf node, we must update stops.
1853  unsigned Size = P.leafSize();
1854  bool Grow = P.leafOffset() == Size;
1855  Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
1856 
1857  // Leaf insertion unsuccessful? Overflow and try again.
1858  if (Size > Leaf::Capacity) {
1859  overflow<Leaf>(P.height());
1860  Grow = P.leafOffset() == P.leafSize();
1861  Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1862  assert(Size <= Leaf::Capacity && "overflow() didn't make room");
1863  }
1864 
1865  // Inserted, update offset and leaf size.
1866  P.setSize(P.height(), Size);
1867 
1868  // Insert was the last node entry, update stops.
1869  if (Grow)
1870  setNodeStop(P.height(), b);
1871 }
1872 
1873 /// erase - erase the current interval and move to the next position.
1874 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1877  IntervalMap &IM = *this->map;
1878  IntervalMapImpl::Path &P = this->path;
1879  assert(P.valid() && "Cannot erase end()");
1880  if (this->branched())
1881  return treeErase();
1882  IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
1883  P.setSize(0, --IM.rootSize);
1884 }
1885 
1886 /// treeErase - erase() for a branched tree.
1887 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1889 iterator::treeErase(bool UpdateRoot) {
1890  IntervalMap &IM = *this->map;
1891  IntervalMapImpl::Path &P = this->path;
1892  Leaf &Node = P.leaf<Leaf>();
1893 
1894  // Nodes are not allowed to become empty.
1895  if (P.leafSize() == 1) {
1896  IM.deleteNode(&Node);
1897  eraseNode(IM.height);
1898  // Update rootBranchStart if we erased begin().
1899  if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
1900  IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1901  return;
1902  }
1903 
1904  // Erase current entry.
1905  Node.erase(P.leafOffset(), P.leafSize());
1906  unsigned NewSize = P.leafSize() - 1;
1907  P.setSize(IM.height, NewSize);
1908  // When we erase the last entry, update stop and move to a legal position.
1909  if (P.leafOffset() == NewSize) {
1910  setNodeStop(IM.height, Node.stop(NewSize - 1));
1911  P.moveRight(IM.height);
1912  } else if (UpdateRoot && P.atBegin())
1913  IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1914 }
1915 
1916 /// eraseNode - Erase the current node at Level from its parent and move path to
1917 /// the first entry of the next sibling node.
1918 /// The node must be deallocated by the caller.
1919 /// @param Level 1..height, the root node cannot be erased.
1920 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1921 void IntervalMap<KeyT, ValT, N, Traits>::
1922 iterator::eraseNode(unsigned Level) {
1923  assert(Level && "Cannot erase root node");
1924  IntervalMap &IM = *this->map;
1925  IntervalMapImpl::Path &P = this->path;
1926 
1927  if (--Level == 0) {
1928  IM.rootBranch().erase(P.offset(0), IM.rootSize);
1929  P.setSize(0, --IM.rootSize);
1930  // If this cleared the root, switch to height=0.
1931  if (IM.empty()) {
1932  IM.switchRootToLeaf();
1933  this->setRoot(0);
1934  return;
1935  }
1936  } else {
1937  // Remove node ref from branch node at Level.
1938  Branch &Parent = P.node<Branch>(Level);
1939  if (P.size(Level) == 1) {
1940  // Branch node became empty, remove it recursively.
1941  IM.deleteNode(&Parent);
1942  eraseNode(Level);
1943  } else {
1944  // Branch node won't become empty.
1945  Parent.erase(P.offset(Level), P.size(Level));
1946  unsigned NewSize = P.size(Level) - 1;
1947  P.setSize(Level, NewSize);
1948  // If we removed the last branch, update stop and move to a legal pos.
1949  if (P.offset(Level) == NewSize) {
1950  setNodeStop(Level, Parent.stop(NewSize - 1));
1951  P.moveRight(Level);
1952  }
1953  }
1954  }
1955  // Update path cache for the new right sibling position.
1956  if (P.valid()) {
1957  P.reset(Level + 1);
1958  P.offset(Level + 1) = 0;
1959  }
1960 }
1961 
1962 /// overflow - Distribute entries of the current node evenly among
1963 /// its siblings and ensure that the current node is not full.
1964 /// This may require allocating a new node.
1965 /// @tparam NodeT The type of node at Level (Leaf or Branch).
1966 /// @param Level path index of the overflowing node.
1967 /// @return True when the tree height was changed.
1968 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1969 template <typename NodeT>
1970 bool IntervalMap<KeyT, ValT, N, Traits>::
1971 iterator::overflow(unsigned Level) {
1972  using namespace IntervalMapImpl;
1973  Path &P = this->path;
1974  unsigned CurSize[4];
1975  NodeT *Node[4];
1976  unsigned Nodes = 0;
1977  unsigned Elements = 0;
1978  unsigned Offset = P.offset(Level);
1979 
1980  // Do we have a left sibling?
1981  NodeRef LeftSib = P.getLeftSibling(Level);
1982  if (LeftSib) {
1983  Offset += Elements = CurSize[Nodes] = LeftSib.size();
1984  Node[Nodes++] = &LeftSib.get<NodeT>();
1985  }
1986 
1987  // Current node.
1988  Elements += CurSize[Nodes] = P.size(Level);
1989  Node[Nodes++] = &P.node<NodeT>(Level);
1990 
1991  // Do we have a right sibling?
1992  NodeRef RightSib = P.getRightSibling(Level);
1993  if (RightSib) {
1994  Elements += CurSize[Nodes] = RightSib.size();
1995  Node[Nodes++] = &RightSib.get<NodeT>();
1996  }
1997 
1998  // Do we need to allocate a new node?
1999  unsigned NewNode = 0;
2000  if (Elements + 1 > Nodes * NodeT::Capacity) {
2001  // Insert NewNode at the penultimate position, or after a single node.
2002  NewNode = Nodes == 1 ? 1 : Nodes - 1;
2003  CurSize[Nodes] = CurSize[NewNode];
2004  Node[Nodes] = Node[NewNode];
2005  CurSize[NewNode] = 0;
2006  Node[NewNode] = this->map->template newNode<NodeT>();
2007  ++Nodes;
2008  }
2009 
2010  // Compute the new element distribution.
2011  unsigned NewSize[4];
2012  IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
2013  CurSize, NewSize, Offset, true);
2014  adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
2015 
2016  // Move current location to the leftmost node.
2017  if (LeftSib)
2018  P.moveLeft(Level);
2019 
2020  // Elements have been rearranged, now update node sizes and stops.
2021  bool SplitRoot = false;
2022  unsigned Pos = 0;
2023  while (true) {
2024  KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2025  if (NewNode && Pos == NewNode) {
2026  SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2027  Level += SplitRoot;
2028  } else {
2029  P.setSize(Level, NewSize[Pos]);
2030  setNodeStop(Level, Stop);
2031  }
2032  if (Pos + 1 == Nodes)
2033  break;
2034  P.moveRight(Level);
2035  ++Pos;
2036  }
2037 
2038  // Where was I? Find NewOffset.
2039  while(Pos != NewOffset.first) {
2040  P.moveLeft(Level);
2041  --Pos;
2042  }
2043  P.offset(Level) = NewOffset.second;
2044  return SplitRoot;
2045 }
2046 
2047 //===----------------------------------------------------------------------===//
2048 //--- IntervalMapOverlaps ----//
2049 //===----------------------------------------------------------------------===//
2050 
2051 /// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
2052 /// IntervalMaps. The maps may be different, but the KeyT and Traits types
2053 /// should be the same.
2054 ///
2055 /// Typical uses:
2056 ///
2057 /// 1. Test for overlap:
2058 /// bool overlap = IntervalMapOverlaps(a, b).valid();
2059 ///
2060 /// 2. Enumerate overlaps:
2061 /// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
2062 ///
2063 template <typename MapA, typename MapB>
2065  using KeyType = typename MapA::KeyType;
2066  using Traits = typename MapA::KeyTraits;
2067 
2068  typename MapA::const_iterator posA;
2069  typename MapB::const_iterator posB;
2070 
2071  /// advance - Move posA and posB forward until reaching an overlap, or until
2072  /// either meets end.
2073  /// Don't move the iterators if they are already overlapping.
2074  void advance() {
2075  if (!valid())
2076  return;
2077 
2078  if (Traits::stopLess(posA.stop(), posB.start())) {
2079  // A ends before B begins. Catch up.
2080  posA.advanceTo(posB.start());
2081  if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2082  return;
2083  } else if (Traits::stopLess(posB.stop(), posA.start())) {
2084  // B ends before A begins. Catch up.
2085  posB.advanceTo(posA.start());
2086  if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2087  return;
2088  } else
2089  // Already overlapping.
2090  return;
2091 
2092  while (true) {
2093  // Make a.end > b.start.
2094  posA.advanceTo(posB.start());
2095  if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2096  return;
2097  // Make b.end > a.start.
2098  posB.advanceTo(posA.start());
2099  if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2100  return;
2101  }
2102  }
2103 
2104 public:
2105  /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
2106  IntervalMapOverlaps(const MapA &a, const MapB &b)
2107  : posA(b.empty() ? a.end() : a.find(b.start())),
2108  posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
2109 
2110  /// valid - Return true if iterator is at an overlap.
2111  bool valid() const {
2112  return posA.valid() && posB.valid();
2113  }
2114 
2115  /// a - access the left hand side in the overlap.
2116  const typename MapA::const_iterator &a() const { return posA; }
2117 
2118  /// b - access the right hand side in the overlap.
2119  const typename MapB::const_iterator &b() const { return posB; }
2120 
2121  /// start - Beginning of the overlapping interval.
2122  KeyType start() const {
2123  KeyType ak = a().start();
2124  KeyType bk = b().start();
2125  return Traits::startLess(ak, bk) ? bk : ak;
2126  }
2127 
2128  /// stop - End of the overlapping interval.
2129  KeyType stop() const {
2130  KeyType ak = a().stop();
2131  KeyType bk = b().stop();
2132  return Traits::startLess(ak, bk) ? ak : bk;
2133  }
2134 
2135  /// skipA - Move to the next overlap that doesn't involve a().
2136  void skipA() {
2137  ++posA;
2138  advance();
2139  }
2140 
2141  /// skipB - Move to the next overlap that doesn't involve b().
2142  void skipB() {
2143  ++posB;
2144  advance();
2145  }
2146 
2147  /// Preincrement - Move to the next overlap.
2149  // Bump the iterator that ends first. The other one may have more overlaps.
2150  if (Traits::startLess(posB.stop(), posA.stop()))
2151  skipB();
2152  else
2153  skipA();
2154  return *this;
2155  }
2156 
2157  /// advanceTo - Move to the first overlapping interval with
2158  /// stopLess(x, stop()).
2159  void advanceTo(KeyType x) {
2160  if (!valid())
2161  return;
2162  // Make sure advanceTo sees monotonic keys.
2163  if (Traits::stopLess(posA.stop(), x))
2164  posA.advanceTo(x);
2165  if (Traits::stopLess(posB.stop(), x))
2166  posB.advanceTo(x);
2167  advance();
2168  }
2169 };
2170 
2171 } // end namespace llvm
2172 
2173 #endif // LLVM_ADT_INTERVALMAP_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::IntervalMap::find
iterator find(KeyT x)
Definition: IntervalMap.h:1132
i
i
Definition: README.txt:29
llvm::IntervalMapImpl::NodeBase::first
T1 first[N]
Definition: IntervalMap.h:229
llvm::IntervalMap::const_iterator::setRoot
void setRoot(unsigned Offset)
Definition: IntervalMap.h:1323
llvm::IntervalMap::end
iterator end()
Definition: IntervalMap.h:1118
llvm::IntervalMapInfo::nonEmpty
static bool nonEmpty(const T &a, const T &b)
nonEmpty - Return true if [a;b] is non-empty.
Definition: IntervalMap.h:163
llvm::IntervalMapImpl::NodeSizer::DesiredLeafSize
@ DesiredLeafSize
Definition: IntervalMap.h:448
llvm::IntervalMap::clear
void clear()
clear - Remove all entries.
Definition: IntervalMap.h:1284
llvm
Definition: AllocatorList.h:23
llvm::IntervalMapImpl::NodeSizer::BranchSize
@ BranchSize
Definition: IntervalMap.h:462
llvm::IntervalMap::insert
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
Definition: IntervalMap.h:1083
KeyT
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::IntervalMap::iterator::operator++
iterator & operator++()
Definition: IntervalMap.h:1589
llvm::IntervalMap::const_iterator::stop
const KeyT & stop() const
stop - Return the end of the current interval.
Definition: IntervalMap.h:1373
llvm::IntervalMap::~IntervalMap
~IntervalMap()
Definition: IntervalMap.h:1049
llvm::IntervalMapImpl::BranchNode::subtree
NodeRef & subtree(unsigned i)
Definition: IntervalMap.h:711
llvm::IntervalMapImpl::LeafNode::start
KeyT & start(unsigned i)
Definition: IntervalMap.h:574
llvm::IntervalMapImpl::Path::leafSize
unsigned leafSize() const
Definition: IntervalMap.h:810
llvm::IntervalMapHalfOpenInfo::adjacent
static bool adjacent(const T &a, const T &b)
adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
Definition: IntervalMap.h:181
llvm::IntervalMapImpl::BranchNode::insert
void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop)
insert - Insert a new (subtree, stop) pair.
Definition: IntervalMap.h:754
llvm::IntervalMapImpl::Path::getLeftSibling
NodeRef getLeftSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
Definition: IntervalMap.cpp:25
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::IntervalMapImpl::LeafNode
Definition: IntervalMap.h:568
llvm::IntervalMap::const_iterator::operator*
const ValT & operator*() const
Definition: IntervalMap.h:1378
llvm::SmallVector< Entry, 4 >
llvm::IntervalMapImpl::Path::setSize
void setSize(unsigned Level, unsigned Size)
setSize - Set the size of a node both in the path and in the tree.
Definition: IntervalMap.h:852
Allocator.h
llvm::IntervalMapImpl::Path::valid
bool valid() const
valid - Return true if path is at a valid node, not at end().
Definition: IntervalMap.h:815
llvm::IntervalMap::IntervalMap
IntervalMap(Allocator &a)
Definition: IntervalMap.h:1043
llvm::IntervalMapImpl::distribute
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
llvm::IntervalMap< IndexT, char >::KeyType
IndexT KeyType
Definition: IntervalMap.h:965
llvm::IntervalMap::iterator
Definition: IntervalMap.h:1526
llvm::IntervalMapImpl::NodeBase::erase
void erase(unsigned i, unsigned j, unsigned Size)
erase - Erase elements [i;j).
Definition: IntervalMap.h:274
llvm::IntervalMapImpl::CacheLineBytes
@ CacheLineBytes
Definition: IntervalMap.h:436
llvm::IntervalMapImpl::BranchNode::stop
KeyT & stop(unsigned i)
Definition: IntervalMap.h:710
llvm::IntervalMapImpl::NodeBase::erase
void erase(unsigned i, unsigned Size)
erase - Erase element at i.
Definition: IntervalMap.h:281
llvm::IntervalMapImpl::Path::setRoot
void setRoot(void *Node, unsigned Size, unsigned Offset)
setRoot - Clear the path and set a new root node.
Definition: IntervalMap.h:862
llvm::IntervalMap::begin
iterator begin()
Definition: IntervalMap.h:1106
T1
#define T1
Definition: Mips16ISelLowering.cpp:340
llvm::IntervalMapImpl::NodeBase::second
T2 second[N]
Definition: IntervalMap.h:230
llvm::IntervalMap::empty
bool empty() const
empty - Return true when no intervals are mapped.
Definition: IntervalMap.h:1055
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::IntervalMapImpl::Path::subtree
NodeRef & subtree(unsigned Level) const
subtree - Get the subtree referenced from Level.
Definition: IntervalMap.h:826
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::IntervalMapImpl::NodeRef::operator!=
bool operator!=(const NodeRef &RHS) const
Definition: IntervalMap.h:542
llvm::IntervalMap::const_iterator::const_iterator
const_iterator(const IntervalMap &map)
Definition: IntervalMap.h:1315
llvm::IntervalMap::const_iterator
Definition: IntervalMap.h:1297
llvm::IntervalMapImpl::Path::offset
unsigned & offset(unsigned Level)
Definition: IntervalMap.h:804
llvm::IntervalMapImpl::NodeSizer::AllocBytes
@ AllocBytes
Definition: IntervalMap.h:459
AlignOf.h
llvm::IntervalMap::const_iterator::treeAdvanceTo
void treeAdvanceTo(KeyT x)
treeAdvanceTo - Find position after the current one.
Definition: IntervalMap.h:1487
llvm::IntervalMapImpl::IdxPair
std::pair< unsigned, unsigned > IdxPair
Definition: IntervalMap.h:195
llvm::IntervalMapImpl::LeafNode::safeLookup
ValT safeLookup(KeyT x, ValT NotFound) const
safeLookup - Lookup mapped value for a safe key.
Definition: IntervalMap.h:613
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
SpecialSubKind::allocator
@ allocator
llvm::IntervalMapImpl::LeafNode::value
const ValT & value(unsigned i) const
Definition: IntervalMap.h:572
llvm::AlignedCharArrayUnion
A suitably aligned and sized character array member which can hold elements of any type.
Definition: AlignOf.h:27
llvm::IntervalMapInfo::stopLess
static bool stopLess(const T &b, const T &x)
stopLess - Return true if x is not in [a;b].
Definition: IntervalMap.h:151
llvm::IntervalMapImpl::NodeRef::size
unsigned size() const
size - Return the number of elements in the referenced node.
Definition: IntervalMap.h:517
p
the resulting code requires compare and branches when and if * p
Definition: README.txt:396
llvm::IntervalMapImpl::NodeBase::Capacity
@ Capacity
Definition: IntervalMap.h:227
llvm::IntervalMapImpl::Path::offset
unsigned offset(unsigned Level) const
Definition: IntervalMap.h:803
llvm::IntervalMapImpl::LeafNode::value
ValT & value(unsigned i)
Definition: IntervalMap.h:576
llvm::IntervalMapImpl::LeafNode::stop
const KeyT & stop(unsigned i) const
Definition: IntervalMap.h:571
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::IntervalMapImpl::adjustSiblingSizes
void adjustSiblingSizes(NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[])
IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
Definition: IntervalMap.h:342
PointerIntPair.h
llvm::IntervalMapImpl::LeafNode::safeFind
unsigned safeFind(unsigned i, KeyT x) const
safeFind - Find an interval that is known to exist.
Definition: IntervalMap.h:599
llvm::IntervalMap::const_iterator::goToBegin
void goToBegin()
goToBegin - Move to the first interval in map.
Definition: IntervalMap.h:1394
llvm::IntervalMap::const_iterator::unsafeValue
ValT & unsafeValue() const
unsafeValue - Writable access to value() for iterator.
Definition: IntervalMap.h:1349
llvm::IntervalMapImpl::NodeSizer
Definition: IntervalMap.h:441
llvm::IntervalMapImpl::NodeSizer::MinLeafSize
@ MinLeafSize
Definition: IntervalMap.h:450
llvm::IntervalMapImpl::BranchNode::safeFind
unsigned safeFind(unsigned i, KeyT x) const
safeFind - Find a subtree that is known to exist.
Definition: IntervalMap.h:733
llvm::IntervalMap::const_iterator::start
const KeyT & start() const
start - Return the beginning of the current interval.
Definition: IntervalMap.h:1370
llvm::LegalizeActions::NotFound
@ NotFound
Sentinel value for when no action was found in the specified table.
Definition: LegalizerInfo.h:92
llvm::IntervalMap::const_iterator::operator++
const_iterator & operator++()
preincrement - Move to the next interval.
Definition: IntervalMap.h:1406
f
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
llvm::IntervalMapImpl::LeafNode::findFrom
unsigned findFrom(unsigned i, unsigned Size, KeyT x) const
findFrom - Find the first interval after i that may contain x.
Definition: IntervalMap.h:584
llvm::IntervalMapOverlaps::valid
bool valid() const
valid - Return true if iterator is at an overlap.
Definition: IntervalMap.h:2111
llvm::IntervalMapImpl::NodeRef::setSize
void setSize(unsigned n)
setSize - Update the node size.
Definition: IntervalMap.h:520
llvm::IntervalMapImpl::Path::leafOffset
unsigned leafOffset() const
Definition: IntervalMap.h:811
llvm::IntervalMap::iterator::setStart
void setStart(KeyT a)
setStart - Move the start of the current interval.
Definition: IntervalMap.h:1688
llvm::IntervalMap::iterator::setStartUnchecked
void setStartUnchecked(KeyT a)
setStartUnchecked - Move the start of the current interval without checking for coalescing or overlap...
Definition: IntervalMap.h:1565
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
l
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
Definition: README.txt:100
llvm::IntervalMap::start
KeyT start() const
start - Return the smallest mapped key in a non-empty map.
Definition: IntervalMap.h:1060
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::IntervalMap::const_iterator::operator++
const_iterator operator++(int)
postincrement - Don't do that!
Definition: IntervalMap.h:1414
llvm::IntervalMap::iterator::operator++
iterator operator++(int)
Definition: IntervalMap.h:1594
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::IntervalMapImpl::BranchNode::findFrom
unsigned findFrom(unsigned i, unsigned Size, KeyT x) const
findFrom - Find the first subtree after i that may contain x.
Definition: IntervalMap.h:719
llvm::IntervalMap::iterator::setValueUnchecked
void setValueUnchecked(ValT x)
setValueUnchecked - Change the mapped value of the current interval without checking for coalescing.
Definition: IntervalMap.h:1581
llvm::IntervalMapImpl::NodeBase::adjustFromLeftSib
int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add)
adjustFromLeftSib - Adjust the number if elements in this node by moving elements to or from a left s...
Definition: IntervalMap.h:321
llvm::IntervalMap::iterator
friend class iterator
Definition: IntervalMap.h:1098
llvm::IntervalMapImpl::Path::moveRight
void moveRight(unsigned Level)
moveRight - Move path to the left sibling at Level.
Definition: IntervalMap.cpp:98
llvm::IntervalMap::const_iterator::goToEnd
void goToEnd()
goToEnd - Move beyond the last interval in map.
Definition: IntervalMap.h:1401
llvm::IntervalMap< IndexT, char >::Allocator
typename Sizer::Allocator Allocator
Definition: IntervalMap.h:964
llvm::IntervalMapOverlaps::advanceTo
void advanceTo(KeyType x)
advanceTo - Move to the first overlapping interval with stopLess(x, stop()).
Definition: IntervalMap.h:2159
llvm::IntervalMapInfo::adjacent
static bool adjacent(const T &a, const T &b)
adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
Definition: IntervalMap.h:157
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:59
llvm::IntervalMap::const_iterator::valid
bool valid() const
valid - Return true if the current position is valid, false for end().
Definition: IntervalMap.h:1364
llvm::IntervalMapImpl::Path::atBegin
bool atBegin() const
atBegin - Return true if path is at begin().
Definition: IntervalMap.h:902
llvm::IntervalMap::const_iterator::setMap
void setMap(const IntervalMap &m)
setMap - Change the map iterated over.
Definition: IntervalMap.h:1361
llvm::IntervalMap::const_iterator::path
IntervalMapImpl::Path path
Definition: IntervalMap.h:1313
llvm::IntervalMap::const_iterator::advanceTo
void advanceTo(KeyT x)
advanceTo - Move to the first interval with stop >= x, or end().
Definition: IntervalMap.h:1448
llvm::IntervalMapImpl::NodeRef::NodeRef
NodeRef(NodeT *p, unsigned n)
NodeRef - Create a reference to the node p with n elements.
Definition: IntervalMap.h:512
llvm::IntervalMapImpl::NodeBase
Definition: IntervalMap.h:225
llvm::IntervalMapImpl::Path::fillLeft
void fillLeft(unsigned Height)
fillLeft - Grow path to Height by taking leftmost branches.
Definition: IntervalMap.h:886
llvm::IntervalMap::const_iterator::unsafeStart
KeyT & unsafeStart() const
unsafeStart - Writable access to start() for iterator.
Definition: IntervalMap.h:1335
llvm::IntervalMapOverlaps::start
KeyType start() const
start - Beginning of the overlapping interval.
Definition: IntervalMap.h:2122
llvm::IntervalMapImpl::Path::push
void push(NodeRef Node, unsigned Offset)
push - Add entry to path.
Definition: IntervalMap.h:839
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::IntervalMap::const_iterator::operator==
bool operator==(const const_iterator &RHS) const
Definition: IntervalMap.h:1380
llvm::IntervalMap::const_iterator::value
const ValT & value() const
value - Return the mapped value at the current interval.
Definition: IntervalMap.h:1376
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:58
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::PointerIntPair::getInt
IntType getInt() const
Definition: PointerIntPair.h:61
llvm::IntervalMapImpl::NodeBase::shift
void shift(unsigned i, unsigned Size)
shift - Shift elements [i;size) 1 position to the right.
Definition: IntervalMap.h:288
node
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper node
Definition: README-SSE.txt:406
llvm::IntervalMap::const_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: IntervalMap.h:1301
llvm::IntervalMapImpl::NodeBase::transferToRightSib
void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)
transferToRightSib - Transfer elements to a right sibling node.
Definition: IntervalMap.h:308
llvm::IntervalMap::lookup
ValT lookup(KeyT x, ValT NotFound=ValT()) const
lookup - Return the mapped value at x or NotFound.
Definition: IntervalMap.h:1073
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::IntervalMapHalfOpenInfo::startLess
static bool startLess(const T &x, const T &a)
startLess - Return true if x is not in [a;b).
Definition: IntervalMap.h:171
llvm::IntervalMap::find
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end().
Definition: IntervalMap.h:1126
llvm::IntervalMapImpl::BranchNode::subtree
const NodeRef & subtree(unsigned i) const
Definition: IntervalMap.h:708
llvm::IntervalMapImpl::Path::leafOffset
unsigned & leafOffset()
Definition: IntervalMap.h:812
llvm::IntervalMapImpl::Log2CacheLine
@ Log2CacheLine
Definition: IntervalMap.h:435
llvm::IntervalMapHalfOpenInfo::stopLess
static bool stopLess(const T &b, const T &x)
stopLess - Return true if x is not in [a;b).
Definition: IntervalMap.h:176
llvm::IntervalMapInfo::startLess
static bool startLess(const T &x, const T &a)
startLess - Return true if x is not in [a;b].
Definition: IntervalMap.h:145
llvm::IntervalMapImpl::NodeBase::copy
void copy(const NodeBase< T1, T2, M > &Other, unsigned i, unsigned j, unsigned Count)
copy - Copy elements from another node.
Definition: IntervalMap.h:238
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2035
llvm::IntervalMap::overlaps
bool overlaps(KeyT a, KeyT b)
overlaps(a, b) - Return true if the intervals in this map overlap with the interval [a;b].
Definition: IntervalMap.h:1140
llvm::IntervalMapImpl::BranchNode::stop
const KeyT & stop(unsigned i) const
Definition: IntervalMap.h:707
llvm::IntervalMapImpl::NodeRef
Definition: IntervalMap.h:495
llvm::IntervalMapImpl::DesiredNodeBytes
@ DesiredNodeBytes
Definition: IntervalMap.h:437
llvm::IntervalMapOverlaps::IntervalMapOverlaps
IntervalMapOverlaps(const MapA &a, const MapB &b)
IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
Definition: IntervalMap.h:2106
llvm::IntervalMap::const_iterator::atBegin
bool atBegin() const
atBegin - Return true if the current position is the first map entry.
Definition: IntervalMap.h:1367
llvm::IntervalMapHalfOpenInfo
Definition: IntervalMap.h:169
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1486
llvm::IntervalMap::iterator::insert
void insert(KeyT a, KeyT b, ValT y)
insert - Insert mapping [a;b] -> y before the current position.
Definition: IntervalMap.h:1787
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::IntervalMap::end
const_iterator end() const
Definition: IntervalMap.h:1112
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
const_iterator
llvm::IntervalMapImpl::NodeSizer::LeafBase
NodeBase< std::pair< KeyT, KeyT >, ValT, LeafSize > LeafBase
Definition: IntervalMap.h:454
llvm::IntervalMapImpl::BranchNode
Definition: IntervalMap.h:705
llvm::IntervalMap::const_iterator::operator--
const_iterator & operator--()
predecrement - Move to the previous interval.
Definition: IntervalMap.h:1421
llvm::IntervalMapImpl::NodeRef::operator==
bool operator==(const NodeRef &RHS) const
Definition: IntervalMap.h:535
llvm::PICLevel::Level
Level
Definition: CodeGen.h:33
llvm::IntervalMap::iterator::setValue
void setValue(ValT x)
setValue - Change the mapped value of the current interval.
Definition: IntervalMap.h:1719
Node
Definition: ItaniumDemangle.h:114
llvm::IntervalMapOverlaps::stop
KeyType stop() const
stop - End of the overlapping interval.
Definition: IntervalMap.h:2129
llvm::IntervalMapHalfOpenInfo::nonEmpty
static bool nonEmpty(const T &a, const T &b)
nonEmpty - Return true if [a;b) is non-empty.
Definition: IntervalMap.h:186
llvm::IntervalMap::iterator::IntervalMap
friend class IntervalMap
Definition: IntervalMap.h:1527
llvm::IntervalMapImpl::NodeBase::moveRight
void moveRight(unsigned i, unsigned j, unsigned Count)
moveRight - Move elements to the right.
Definition: IntervalMap.h:261
j
return j(j<< 16)
llvm::RecyclingAllocator
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
Definition: RecyclingAllocator.h:26
llvm::IntervalMapOverlaps
IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two IntervalMaps.
Definition: IntervalMap.h:2064
llvm::IntervalMapImpl::LeafNode::stop
KeyT & stop(unsigned i)
Definition: IntervalMap.h:575
llvm::IntervalMapImpl::Path::legalizeForInsert
void legalizeForInsert(unsigned Level)
legalizeForInsert - Prepare the path for an insertion at Level.
Definition: IntervalMap.h:921
llvm::IntervalMapImpl::LeafNode::start
const KeyT & start(unsigned i) const
Definition: IntervalMap.h:570
bit.h
llvm::IntervalMapOverlaps::skipA
void skipA()
skipA - Move to the next overlap that doesn't involve a().
Definition: IntervalMap.h:2136
llvm::IntervalMapImpl::NodeBase::transferToLeftSib
void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)
transferToLeftSib - Transfer elements to a left sibling node.
Definition: IntervalMap.h:297
llvm::IntervalMapImpl::Path::leaf
NodeT & leaf() const
Definition: IntervalMap.h:807
llvm::MCID::Branch
@ Branch
Definition: MCInstrDesc.h:157
llvm::IntervalMapOverlaps::a
const MapA::const_iterator & a() const
a - access the left hand side in the overlap.
Definition: IntervalMap.h:2116
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::IntervalMap::const_iterator::map
IntervalMap * map
Definition: IntervalMap.h:1309
x
TODO unsigned x
Definition: README.txt:10
llvm::IntervalMapImpl::Path::reset
void reset(unsigned Level)
reset - Reset cached information about node(Level) from subtree(Level -1).
Definition: IntervalMap.h:832
llvm::IntervalMapImpl::NodeSizer::Allocator
RecyclingAllocator< BumpPtrAllocator, char, AllocBytes, CacheLineBytes > Allocator
Allocator - The recycling allocator used for both branch and leaf nodes.
Definition: IntervalMap.h:471
y
into llvm powi allowing the code generator to produce balanced multiplication trees the intrinsic needs to be extended to support and second the code generator needs to be enhanced to lower these to multiplication trees Interesting testcase for add shift mul int y
Definition: README.txt:61
llvm::IntervalMapOverlaps::b
const MapB::const_iterator & b() const
b - access the right hand side in the overlap.
Definition: IntervalMap.h:2119
llvm::PointerIntPair::getOpaqueValue
void * getOpaqueValue() const
Definition: PointerIntPair.h:91
llvm::IntervalMap::const_iterator::find
void find(KeyT x)
find - Move to the first interval with stop >= x, or end().
Definition: IntervalMap.h:1438
RecyclingAllocator.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::IntervalMapImpl::Path::height
unsigned height() const
height - Return the height of the tree corresponding to this path.
Definition: IntervalMap.h:821
llvm::IntervalMap::iterator::operator--
iterator operator--(int)
Definition: IntervalMap.h:1605
llvm::IntervalMap::const_iterator::difference_type
std::ptrdiff_t difference_type
Definition: IntervalMap.h:1303
llvm::PointerIntPair::setInt
void setInt(IntType IntVal) LLVM_LVALUE_FUNCTION
Definition: PointerIntPair.h:67
llvm::IntervalMap::iterator::setStopUnchecked
void setStopUnchecked(KeyT b)
setStopUnchecked - Move the end of the current interval without checking for coalescing or overlaps.
Definition: IntervalMap.h:1571
llvm::IntervalMapImpl::Path::pop
void pop()
pop - Remove the last path entry.
Definition: IntervalMap.h:844
llvm::IntervalMapOverlaps::skipB
void skipB()
skipB - Move to the next overlap that doesn't involve b().
Definition: IntervalMap.h:2142
llvm::PointerIntPair< void *, Log2CacheLine, unsigned, CacheAlignedPointerTraits >
llvm::IntervalMapImpl::Path::moveLeft
void moveLeft(unsigned Level)
moveLeft - Move path to the left sibling at Level.
Definition: IntervalMap.cpp:48
llvm::IntervalMapImpl::LeafNode::insertFrom
unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y)
insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as possible.
Definition: IntervalMap.h:632
SmallVector.h
llvm::IntervalMapImpl::Path::getRightSibling
NodeRef getRightSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
Definition: IntervalMap.cpp:75
N
#define N
llvm::IntervalMapOverlaps::operator++
IntervalMapOverlaps & operator++()
Preincrement - Move to the next overlap.
Definition: IntervalMap.h:2148
llvm::IntervalMapImpl::NodeRef::subtree
NodeRef & subtree(unsigned i) const
subtree - Access the i'th subtree reference in a branch node.
Definition: IntervalMap.h:525
llvm::IntervalMap::begin
const_iterator begin() const
Definition: IntervalMap.h:1100
llvm::IntervalMapImpl::Path::node
NodeT & node(unsigned Level) const
Definition: IntervalMap.h:799
llvm::IntervalMap
Definition: IntervalMap.h:938
shift
http eax xorl edx cl sete al setne dl sall eax sall edx But that requires good bit subreg support this might be better It s an extra shift
Definition: README.txt:30
llvm::IntervalMapImpl::NodeBase::moveLeft
void moveLeft(unsigned i, unsigned j, unsigned Count)
moveLeft - Move elements to the left.
Definition: IntervalMap.h:252
llvm::IntervalMapImpl::Path::size
unsigned size(unsigned Level) const
Definition: IntervalMap.h:802
llvm::IntervalMap::const_iterator
friend class const_iterator
Definition: IntervalMap.h:1096
h
the multiplication has a latency of four as opposed to two cycles for the movl lea variant It appears gcc place string data with linkonce linkage in section coalesced instead of section coalesced Take a look at darwin h
Definition: README.txt:261
llvm::IntervalMapImpl::Path::replaceRoot
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
llvm::IntervalMapImpl::NodeRef::get
NodeT & get() const
get - Dereference as a NodeT reference.
Definition: IntervalMap.h:531
llvm::IntervalMap::iterator::operator--
iterator & operator--()
Definition: IntervalMap.h:1600
llvm::IntervalMapImpl::NodeRef::NodeRef
NodeRef()=default
NodeRef - Create a null ref.
llvm::IntervalMapImpl::Path::atLastEntry
bool atLastEntry(unsigned Level) const
atLastEntry - Return true if the path is at the last entry of the node at Level.
Definition: IntervalMap.h:912
llvm::IntervalMap::const_iterator::operator--
const_iterator operator--(int)
postdecrement - Don't do that!
Definition: IntervalMap.h:1430
llvm::IntervalMap::const_iterator::pathFillFind
void pathFillFind(KeyT x)
pathFillFind - Complete path by searching for x.
Definition: IntervalMap.h:1463
ValT
llvm::IntervalMap< IndexT, char >::ValueType
char ValueType
Definition: IntervalMap.h:966
llvm::SI::KernelInputOffsets::Offsets
Offsets
Offsets in bytes from the start of the input buffer.
Definition: SIInstrInfo.h:1224
d
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
Definition: README.txt:418
n
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
Definition: README.txt:685
llvm::IntervalMapImpl::Path
Definition: IntervalMap.h:775
llvm::IntervalMap::const_iterator::unsafeStop
KeyT & unsafeStop() const
unsafeStop - Writable access to stop() for iterator.
Definition: IntervalMap.h:1342
llvm::IntervalMapInfo
Definition: IntervalMap.h:142
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::IntervalMap::const_iterator::operator!=
bool operator!=(const const_iterator &RHS) const
Definition: IntervalMap.h:1389
llvm::IntervalMap::iterator::erase
void erase()
erase - Erase the current interval.
Definition: IntervalMap.h:1876
llvm::IntervalMap::const_iterator::treeFind
void treeFind(KeyT x)
treeFind - Find in a branched tree.
Definition: IntervalMap.h:1477
llvm::IntervalMap::const_iterator::branched
bool branched() const
Definition: IntervalMap.h:1318
llvm::IntervalMap::iterator::setStop
void setStop(KeyT b)
setStop - Move the end of the current interval.
Definition: IntervalMap.h:1704
llvm::IntervalMapImpl::BranchNode::safeLookup
NodeRef safeLookup(KeyT x) const
safeLookup - Get the subtree containing x, Assuming that x is in range.
Definition: IntervalMap.h:745
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1163
llvm::IntervalMap::stop
KeyT stop() const
stop - Return the largest mapped key in a non-empty map.
Definition: IntervalMap.h:1066