Add ADT/IntervalMap.
This is a sorted interval map data structure for small keys and values with
automatic coalescing and bidirectional iteration over coalesced intervals.
Except for coalescing intervals, it provides similar functionality to std::map.
It is however much more compact for small keys and values, and hopefully faster
too.
The container object itself can hold the first few intervals without any
allocations, then it switches to a cache conscious B+-tree representation. A
recycling allocator can be shared between many containers, even between
containers holding different types.
The IntervalMap is initially intended to be used with SlotIndex intervals for:
- Backing store for LiveIntervalUnion that is smaller and faster than std::set.
- Backing store for LiveInterval with less overhead than std::vector for typical
intervals and O(N log N) merging of large intervals. 99% of virtual registers
need 4 entries or less and would benefit from the small object optimization.
- Backing store for LiveDebugVariable which doesn't exist yet, but will track
debug variables during register allocation.
This is a work in progress. Missing items are:
- Performance metrics.
- erase().
- insert() shrinkage.
- clear().
- More performance metrics.
- Simplification and detemplatization.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119787 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Support/IntervalMap.cpp b/lib/Support/IntervalMap.cpp
new file mode 100644
index 0000000..9f5c72f
--- /dev/null
+++ b/lib/Support/IntervalMap.cpp
@@ -0,0 +1,60 @@
+//===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the few non-templated functions in IntervalMap.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/IntervalMap.h"
+
+namespace llvm {
+namespace IntervalMapImpl {
+
+IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
+ const unsigned *CurSize, unsigned NewSize[],
+ unsigned Position, bool Grow) {
+ assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements");
+ assert(Position <= Elements && "Invalid position");
+ if (!Nodes)
+ return IdxPair();
+
+ // Trivial algorithm: left-leaning even distribution.
+ const unsigned PerNode = (Elements + Grow) / Nodes;
+ const unsigned Extra = (Elements + Grow) % Nodes;
+ IdxPair PosPair = IdxPair(Nodes, 0);
+ unsigned Sum = 0;
+ for (unsigned n = 0; n != Nodes; ++n) {
+ Sum += NewSize[n] = PerNode + (n < Extra);
+ if (PosPair.first == Nodes && Sum > Position)
+ PosPair = IdxPair(n, Position - (Sum - NewSize[n]));
+ }
+ assert(Sum == Elements + Grow && "Bad distribution sum");
+
+ // Subtract the Grow element that was added.
+ if (Grow) {
+ assert(PosPair.first < Nodes && "Bad algebra");
+ assert(NewSize[PosPair.first] && "Too few elements to need Grow");
+ --NewSize[PosPair.first];
+ }
+
+#ifndef NDEBUG
+ Sum = 0;
+ for (unsigned n = 0; n != Nodes; ++n) {
+ assert(NewSize[n] <= Capacity && "Overallocated node");
+ Sum += NewSize[n];
+ }
+ assert(Sum == Elements && "Bad distribution sum");
+#endif
+
+ return PosPair;
+}
+
+} // namespace IntervalMapImpl
+} // namespace llvm
+