llvm-svn: 120298

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

This reverts r119772.

llvm-svn: 119773

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

llvm-svn: 116682

llvm-svn: 116003

llvm-svn: 114999

llvm-svn: 111669

llvm-svn: 109598

ADT: Add DAGDeltaAlgorithm, which is a DAG minimization algorithm built on top of the standard 'delta debugging' algorithm.
 - This can give substantial speedups in the delta process for inputs we can construct dependency information for.

llvm-svn: 105612

llvm-svn: 92003

SmallVectorBase::grow_pod out of line, finally satisfying PR3758.

llvm-svn: 91529

 - This is a pretty slow / memory intensive implementation, and I will likely
   change it to an iterative model, but it works.

llvm-svn: 90447

llvm-svn: 82087

llvm-svn: 81577

llvm-svn: 80680

implementation.

llvm-svn: 80493

llvm-svn: 79959

llvm-svn: 79876

llvm-svn: 77709

llvm-svn: 76957

llvm-svn: 75746

llvm-svn: 75677

llvm-svn: 74936

llvm-svn: 74285

llvm-svn: 73844

llvm-svn: 73708

llvm-svn: 73516

llvm-svn: 72480

llvm-svn: 66160

llvm-svn: 56419