aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/ADT/IntervalMap.h
Commit message (Collapse)AuthorAgeFilesLines
* Update aosp/master llvm for rebase to r233350Pirama Arumuga Nainar2015-04-091-14/+4
| | | | Change-Id: I07d935f8793ee8ec6b7da003f6483046594bca49
* Update aosp/master LLVM for rebase to r230699.Stephen Hines2015-03-231-1/+1
| | | | Change-Id: I2b5be30509658cb8266be782de0ab24f9099f9b9
* Update LLVM for 3.5 rebase (r209712).Stephen Hines2014-05-291-3/+3
| | | | Change-Id: I149556c940fb7dc92d075273c87ff584f400941f
* Fix -Wdocumentation warnings.Rafael Espindola2013-07-281-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187336 91177308-0d34-0410-b5e6-96231b3b80d8
* Use only explicit bool conversion operatorsDavid Blaikie2013-05-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | BitVector/SmallBitVector::reference::operator bool remain implicit since they model more exactly a bool, rather than something else that can be boolean tested. The most common (non-buggy) case are where such objects are used as return expressions in bool-returning functions or as boolean function arguments. In those cases I've used (& added if necessary) a named function to provide the equivalent (or sometimes negative, depending on convenient wording) test. One behavior change (YAMLParser) was made, though no test case is included as I'm not sure how to reach that code path. Essentially any comparison of llvm::yaml::document_iterators would be invalid if neither iterator was at the end. This helped uncover a couple of bugs in Clang - test cases provided for those in a separate commit along with similar changes to `operator bool` instances in Clang. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181868 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide a common half-open interval map info implementation, and justChandler Carruth2012-12-271-0/+20
| | | | | | | 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
* Sort the #include lines for the include/... tree with the script.Chandler Carruth2012-12-031-1/+1
| | | | | | | | | | 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
* Add a few missing 'template' keywordsDouglas Gregor2012-03-111-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152525 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed typo.Lang Hames2011-12-221-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147113 91177308-0d34-0410-b5e6-96231b3b80d8
* Add IntervalMap::const_iterator::atBegin().Jakob Stoklund Olesen2011-08-191-0/+3
| | | | | | 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
* Add an InterferenceCache class for caching per-block interference ranges.Jakob Stoklund Olesen2011-04-021-0/+4
| | | | | | | | 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
* Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo seesJakob Stoklund Olesen2010-12-171-11/+23
| | | | | | monotonic keys. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122093 91177308-0d34-0410-b5e6-96231b3b80d8
* It is allowed to call IntervalMap::const_iterator::advanceTo() with a key thatJakob Stoklund Olesen2010-12-171-0/+2
| | | | | | | | 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
* Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap.Jakob Stoklund Olesen2010-12-171-6/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122081 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide LiveIntervalUnion::Query::checkLoopInterference.Jakob Stoklund Olesen2010-12-171-1/+25
| | | | | | | | 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
* Add basic test exposing many bugs.Jakob Stoklund Olesen2010-12-161-6/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121995 91177308-0d34-0410-b5e6-96231b3b80d8
* Add IntervalMapOverlaps - An iterator for overlapping intervals in twoJakob Stoklund Olesen2010-12-161-0/+91
| | | | | | | | | | | 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
* Remove debugging code.Jakob Stoklund Olesen2010-12-141-66/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121738 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix begin() and end() on const IntervalMap.Jakob Stoklund Olesen2010-12-071-4/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121200 91177308-0d34-0410-b5e6-96231b3b80d8
* Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limitedJakob Stoklund Olesen2010-12-031-21/+172
| | | | | | | | | | | 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
* Don't use std::copy and std::copy_backward, run 10% faster.Jakob Stoklund Olesen2010-11-281-5/+8
| | | | | | | | 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
* Disallow overlapping inserts, even when inserting the same value.Jakob Stoklund Olesen2010-11-281-77/+45
| | | | | | | | | | | 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
* Tweak comments to make it clear that we are working in a namespace.Jakob Stoklund Olesen2010-11-281-18/+18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120256 91177308-0d34-0410-b5e6-96231b3b80d8
* Add default constructors for iterators.Jakob Stoklund Olesen2010-11-281-0/+6
| | | | | | | 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
* Implement const_iterator::advanceTo().Jakob Stoklund Olesen2010-11-281-2/+47
| | | | | | | 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
* Speed up simple insertions into an unbranched tree by not creating an iterator.Jakob Stoklund Olesen2010-11-281-1/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120232 91177308-0d34-0410-b5e6-96231b3b80d8
* Add more tests for erase(). Fix a few exposed bugs.Jakob Stoklund Olesen2010-11-271-4/+39
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
* Add test case with randomly ordered insertions, massive coalescing.Jakob Stoklund Olesen2010-11-271-26/+146
| | | | | | | | | | 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
* Add B+-tree test case that creates a height 3 tree with a smaller root node.Jakob Stoklund Olesen2010-11-261-16/+30
| | | | | | 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
* Extract template function adjustSiblingSizes(), allowing instances to be sharedJakob Stoklund Olesen2010-11-261-75/+86
| | | | | | between B+-trees using the same KeyT. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120170 91177308-0d34-0410-b5e6-96231b3b80d8
* Move tree navigation to a new Path class that doesn't have to be a template.Jakob Stoklund Olesen2010-11-261-295/+262
| | | | | | | | 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
* Generalize overflowLeaf to also handle overflows in branch nodes.Jakob Stoklund Olesen2010-11-241-29/+50
| | | | | | | 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
* Fix old GCC build error.Jakob Stoklund Olesen2010-11-201-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119884 91177308-0d34-0410-b5e6-96231b3b80d8
* Detemplatize NodeRef.Jakob Stoklund Olesen2010-11-201-96/+92
| | | | | | | | 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
* Rename NodeBase::{key,val} as {first,second} and swap the BranchNode arrays suchJakob Stoklund Olesen2010-11-201-24/+23
| | | | | | | | 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
* Implement IntervalMap destructor.Jakob Stoklund Olesen2010-11-191-0/+5
| | | | | | | | 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
* Implement IntervalMap::clear().Jakob Stoklund Olesen2010-11-191-3/+25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
* Support backwards iteration starting from end().Jakob Stoklund Olesen2010-11-191-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename methods for clarity instead of brevity. No functional changes.Jakob Stoklund Olesen2010-11-191-44/+46
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119820 91177308-0d34-0410-b5e6-96231b3b80d8
* Include raw_ostream.h unconditionally even if it is only used for debug code.Jakob Stoklund Olesen2010-11-191-3/+1
| | | | | | | 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
* Work around GCC 4.0 build error:Jakob Stoklund Olesen2010-11-191-3/+6
| | | | | | 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
* Add ADT/IntervalMap.Jakob Stoklund Olesen2010-11-191-0/+1705
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert "Add ADT/IntervalMap.", GCC doesn't like it.Jakob Stoklund Olesen2010-11-191-1695/+0
| | | | | | This reverts r119772. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ADT/IntervalMap.Jakob Stoklund Olesen2010-11-191-0/+1695
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 (git 2.25.1) at 2025-07-13 07:29:21 +0000