Explicitly include <cassert> when using assert

Depending on the OS used, a module-enabled build can fail due to the
special handling <cassert> gets as textual header.

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[C++11] Make use of 'nullptr' in the Support library.

llvm-svn: 205697

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 edi

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.

llvm-svn: 120829

show more ...

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

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

llvm-svn: 120165

show more ...

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 int

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.

llvm-svn: 119787

show more ...

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 int

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.

llvm-svn: 119772

show more ...