| dce4a407a24b04eebc6a376f8e62b41aaa7b071f |
|
29-May-2014 |
Stephen Hines <srhines@google.com> |
Update LLVM for 3.5 rebase (r209712).
Change-Id: I149556c940fb7dc92d075273c87ff584f400941f
/external/llvm/lib/Support/IntervalMap.cpp
|
| 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/lib/Support/IntervalMap.cpp
|
| 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/lib/Support/IntervalMap.cpp
|
| 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/lib/Support/IntervalMap.cpp
|
| 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/lib/Support/IntervalMap.cpp
|
| 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/lib/Support/IntervalMap.cpp
|