4c5e43da7792f75567b693105cc53e3f1992ad98 |
|
08-Apr-2015 |
Pirama Arumuga Nainar <pirama@google.com> |
Update aosp/master llvm for rebase to r233350 Change-Id: I07d935f8793ee8ec6b7da003f6483046594bca49
/external/llvm/include/llvm/ADT/IntervalMap.h
|
ebe69fe11e48d322045d5949c83283927a0d790b |
|
23-Mar-2015 |
Stephen Hines <srhines@google.com> |
Update aosp/master LLVM for rebase to r230699. Change-Id: I2b5be30509658cb8266be782de0ab24f9099f9b9
/external/llvm/include/llvm/ADT/IntervalMap.h
|
dce4a407a24b04eebc6a376f8e62b41aaa7b071f |
|
29-May-2014 |
Stephen Hines <srhines@google.com> |
Update LLVM for 3.5 rebase (r209712). Change-Id: I149556c940fb7dc92d075273c87ff584f400941f
/external/llvm/include/llvm/ADT/IntervalMap.h
|
15658b290817d6f198ab08910a2d754ba11164d1 |
|
29-Jul-2013 |
Rafael Espindola <rafael.espindola@gmail.com> |
Fix -Wdocumentation warnings. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187336 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
453f4f01302f00651aae2fc7658f6e23a2beadb0 |
|
15-May-2013 |
David Blaikie <dblaikie@gmail.com> |
Use only explicit bool conversion operators 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
edf315cd71334d5a7af31f4b882235d03b06f24d |
|
27-Dec-2012 |
Chandler Carruth <chandlerc@gmail.com> |
Provide a common half-open interval map info implementation, and just 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
255f89faee13dc491cb64fbeae3c763e7e2ea4e6 |
|
03-Dec-2012 |
Chandler Carruth <chandlerc@gmail.com> |
Sort the #include lines for the include/... tree with the script. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
87d8e60505b26960956996550c8b805c81e5b02b |
|
11-Mar-2012 |
Douglas Gregor <dgregor@apple.com> |
Add a few missing 'template' keywords git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152525 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
ab26da9e679afb26b6af589c2d414d50bf4a6441 |
|
22-Dec-2011 |
Lang Hames <lhames@gmail.com> |
Fixed typo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147113 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
cafe614035c8db70eb5da96dba00696db381674f |
|
20-Aug-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add IntervalMap::const_iterator::atBegin(). 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
5907d863659eb972ebb2afe07bc863a4c616f0ef |
|
02-Apr-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add an InterferenceCache class for caching per-block interference ranges. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
d715e07efe29451afe2849abd4bd362d0f75a004 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo sees monotonic keys. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122093 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
5049ee5b11fe55e5a553b5388406aab874717672 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
It is allowed to call IntervalMap::const_iterator::advanceTo() with a key that 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
4aec85ae01188f87e45e5e91baab4f303cbcd336 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122081 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
ff2e9b4225ab55ee049b33158a9cce1ef138c2f7 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Provide LiveIntervalUnion::Query::checkLoopInterference. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
460ee0fd19b13ba4c1410e43d8d253bf34673817 |
|
16-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add basic test exposing many bugs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121995 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
cb9e08f328892eaf46825d7426216995ca673a67 |
|
16-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add IntervalMapOverlaps - An iterator for overlapping intervals in two 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
2ece4dead7087ebf8d5fa8df77fcd76593c6a6a5 |
|
14-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Remove debugging code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121738 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
da2fdcbb639de168738c27089bafa9ca10b731bd |
|
08-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Fix begin() and end() on const IntervalMap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121200 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
7a26aca73ff2c8c4cb3205a776cc6743949b1fb7 |
|
03-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limited 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
08d55342e337fd4e80a68b81b8b0cbb100ea0a23 |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Don't use std::copy and std::copy_backward, run 10% faster. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
5f456cda98c57b6dea8bc716978b69776d0d0e8f |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Disallow overlapping inserts, even when inserting the same value. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
bf953eaba3442f8e25926b8f41423d4d126960f6 |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Tweak comments to make it clear that we are working in a namespace. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120256 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
9a08ca318e63912e4c19977abc1173f30866b704 |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add default constructors for iterators. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
180e1247ca330b047eabafbc72926ce9bfd8bf8e |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Implement const_iterator::advanceTo(). 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
79283768a36746bcb5885746637752312af9e4ac |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Speed up simple insertions into an unbranched tree by not creating an iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120232 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
055942529bbc8487f86b47940dbd6a790516573e |
|
27-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add more tests for erase(). Fix a few exposed bugs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
b0b7214fc90febbbe71e1e989130194ce2b70a36 |
|
27-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add test case with randomly ordered insertions, massive coalescing. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
53bb5c009b04f4a5dd2388b25efe88b5579b282c |
|
26-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add B+-tree test case that creates a height 3 tree with a smaller root node. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9 |
|
26-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Extract template function adjustSiblingSizes(), allowing instances to be shared between B+-trees using the same KeyT. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120170 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
706da9d8ca207c93d38855ffd96cf9722996d706 |
|
26-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Move tree navigation to a new Path class that doesn't have to be a template. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
6c76f5fa2fb839c736c572f45c138e5b3f549530 |
|
24-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Generalize overflowLeaf to also handle overflows in branch nodes. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
487a5b786f7f70c9ed71dadbfcd03a918e5b0ea1 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Fix old GCC build error. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119884 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
ddd0e65dba1de71eaa8901cd6f787754e34c3fe0 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Detemplatize NodeRef. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Rename NodeBase::{key,val} as {first,second} and swap the BranchNode arrays such 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
785ab18a054373f1a2f8d0f6f04db2d458878bd9 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Implement IntervalMap destructor. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
655fbb4f9b46ea93eddf0815eaed0020e9347416 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Implement IntervalMap::clear(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
db52566d684a36cf1f320f91ca5c15d5cd075b95 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Support backwards iteration starting from end(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
33fa490c5011b610ccf7b1206bbabb85d9a8cbaa |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Rename methods for clarity instead of brevity. No functional changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119820 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
805f105da0e15c3c63c5d5e9df0140d3421b4a55 |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Include raw_ostream.h unconditionally even if it is only used for debug code. 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
528900d9a46cf4acde3a90494f286116159d5e59 |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Work around GCC 4.0 build error: 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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
8dc926755f287e33765a8da0c4b3922a289a9d2d |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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
/external/llvm/include/llvm/ADT/IntervalMap.h
|
737d2816c42c1f9a63524e39ccfa7560777b6b42 |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Revert "Add ADT/IntervalMap.", GCC doesn't like it. This reverts r119772. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/IntervalMap.h
|
8408edffcbd7f436c05018fafbfb9911146b208a |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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
/external/llvm/include/llvm/ADT/IntervalMap.h
|