| 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
|