From 8408edffcbd7f436c05018fafbfb9911146b208a Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 19 Nov 2010 01:14:40 +0000 Subject: 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@119772 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/CMakeLists.txt | 1 + 1 file changed, 1 insertion(+) (limited to 'unittests/CMakeLists.txt') diff --git a/unittests/CMakeLists.txt b/unittests/CMakeLists.txt index 36aace5bc4..e251bdbd5c 100644 --- a/unittests/CMakeLists.txt +++ b/unittests/CMakeLists.txt @@ -45,6 +45,7 @@ add_llvm_unittest(ADT ADT/DenseSetTest.cpp ADT/ilistTest.cpp ADT/ImmutableSetTest.cpp + ADT/IntervalMapTest.cpp ADT/SmallBitVectorTest.cpp ADT/SmallStringTest.cpp ADT/SmallVectorTest.cpp -- cgit v1.2.3-18-g5258