aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/ADT/IntervalMap.h
AgeCommit message (Collapse)Author
2012-12-27Provide a common half-open interval map info implementation, and justChandler Carruth
re-use that for SlotIndexes. This way other users who want half-open semantics can share the implementation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171158 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Sort the #include lines for the include/... tree with the script.Chandler Carruth
AKA: Recompile *ALL* the source code! This one went much better. No manual edits here. I spot-checked for silliness and grep-checked for really broken edits and everything seemed good. It all still compiles. Yell if you see something that looks goofy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-11Add a few missing 'template' keywordsDouglas Gregor
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152525 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-22Fixed typo.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147113 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-19Add IntervalMap::const_iterator::atBegin().Jakob Stoklund Olesen
It returns true when operator--() can be called. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138107 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-02Add an InterferenceCache class for caching per-block interference ranges.Jakob Stoklund Olesen
When the greedy register allocator is splitting multiple global live ranges, it tends to look at the same interference data many times. The InterferenceCache class caches queries for unaltered LiveIntervalUnions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128764 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo seesJakob Stoklund Olesen
monotonic keys. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122093 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17It is allowed to call IntervalMap::const_iterator::advanceTo() with a key thatJakob Stoklund Olesen
moves the iterator to end(), and it is valid to call it on end(). That means it is valid to call advanceTo() with any monotonic key sequence. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122092 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122081 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Provide LiveIntervalUnion::Query::checkLoopInterference.Jakob Stoklund Olesen
This is a three-way interval list intersection between a virtual register, a live interval union, and a loop. It will be used to identify interference-free loops for live range splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122034 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-16Add basic test exposing many bugs.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121995 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-16Add IntervalMapOverlaps - An iterator for overlapping intervals in twoJakob Stoklund Olesen
IntervalMaps. The IntervalMaps can have different template parameters, but the KeyT and Traits types must be the same. Tests are forthcoming. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121935 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Remove debugging code.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121738 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-07Fix begin() and end() on const IntervalMap.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121200 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-03Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limitedJakob Stoklund Olesen
editing of the current interval. These methods may cause coalescing, there are corresponding set*Unchecked methods for editing without coalescing. The non-coalescing methods are useful for applying monotonic transforms to all keys or values in a map without accidentally coalescing transformed and untransformed intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120829 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-28Don't use std::copy and std::copy_backward, run 10% faster.Jakob Stoklund Olesen
Sometimes std::copy can become a memmove call, and that is not a good idea when copying relatively few bytes as we are doing. We also get a small win by changing two loops into one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120265 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-28Disallow overlapping inserts, even when inserting the same value.Jakob Stoklund Olesen
We always disallowed overlapping inserts with different values, and this makes the insertion code smaller and faster. If an overwriting insert is needed, it can be added as a separate method that trims any existing intervals before inserting. The immediate use cases for IntervalMap don't need this - they only use disjoint insertions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120264 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-28Tweak comments to make it clear that we are working in a namespace.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120256 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-28Add default constructors for iterators.Jakob Stoklund Olesen
These iterators don't point anywhere, and they can't be compared to anything. They are only good for assigning to. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120239 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-28Implement const_iterator::advanceTo().Jakob Stoklund Olesen
This is a version of find() that always searches forwards and is faster for local searches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120237 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-28Speed up simple insertions into an unbranched tree by not creating an iterator.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120232 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-27Add more tests for erase(). Fix a few exposed bugs.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-27Add test case with randomly ordered insertions, massive coalescing.Jakob Stoklund Olesen
Implement iterator::erase() in a simple version that erases nodes when they become empty, but doesn't try to redistribute elements among siblings for better packing. Handle coalescing across leaf nodes which may require erasing entries. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120226 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-26Add B+-tree test case that creates a height 3 tree with a smaller root node.Jakob Stoklund Olesen
Change temporary debugging code to write a dot file directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120171 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-26Extract template function adjustSiblingSizes(), allowing instances to be sharedJakob Stoklund Olesen
between B+-trees using the same KeyT. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120170 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-26Move tree navigation to a new Path class that doesn't have to be a template.Jakob Stoklund Olesen
The path also holds a reference to the root node, and that allows important iterator accessors like start() and stop() to have no conditional code. (When the compiler is clever enough to remove it.) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120165 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-24Generalize overflowLeaf to also handle overflows in branch nodes.Jakob Stoklund Olesen
This doesn't quite work yet because the calls to treeDecrement and treeIncrement operate at the leaf level, not on pathNode(Level) as required. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120068 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-20Fix old GCC build error.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119884 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-20Detemplatize NodeRef.Jakob Stoklund Olesen
It is now possible to navigate the B+-tree using NodeRef::subtree() and NodeRef::size() without knowing the key and value template types used in the tree. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119880 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-20Rename NodeBase::{key,val} as {first,second} and swap the BranchNode arrays suchJakob Stoklund Olesen
that the noderefs are the first member in the object. This is in preparation of detemplatization of tree navigation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119879 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Implement IntervalMap destructor.Jakob Stoklund Olesen
Key and value objects may not be destructed instantly when they are erased from the container, but they will be destructed eventually by the IntervalMap destructor. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119873 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Implement IntervalMap::clear().Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Support backwards iteration starting from end().Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Rename methods for clarity instead of brevity. No functional changes.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119820 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Include raw_ostream.h unconditionally even if it is only used for debug code.Jakob Stoklund Olesen
We don't want any clients acidentally depending on this and then failing in a -Asserts build. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119818 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Work around GCC 4.0 build error:Jakob Stoklund Olesen
llvm/include/llvm/ADT/IntervalMap.h:334: error: '((llvm::IntervalMapImpl::DesiredNodeBytes / static_cast<unsigned int>(((2 * sizeof (KeyT)) + sizeof (ValT)))) >? 3u)' is not a valid template argument for type 'unsigned int' because it is a non-constant expression git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119790 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Add ADT/IntervalMap.Jakob Stoklund Olesen
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
2010-11-19Revert "Add ADT/IntervalMap.", GCC doesn't like it.Jakob Stoklund Olesen
This reverts r119772. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-19Add ADT/IntervalMap.Jakob Stoklund Olesen
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-26 09:40:26 +0000