llvm-svn: 135992

The header file was already properly located. The previous need for it
in Support had to do with the version string printing which was fixed in
r135757.

Also update build dependencies where libraries that needed the
functionality of the Target library (in the form of the TargetRegistry)
were picking it up via Support. This is pretty pervasive, essentially
every TargetInfo library (ARMInfo, etc) uses TargetRegistry, making it
depend on Target. All of these were previously just sneaking by.

llvm-svn: 135760

Patch by: Jakub Staszak!

Introduces BranchProbability. Changes unsigned to uint32_t all over and
uint64_t only when overflow is expected.

llvm-svn: 132867

llvm-svn: 131606

llvm-svn: 131602

This implementation already exists as ConnectedVNInfoEqClasses in
LiveInterval.cpp, and it seems to be generally useful to have a light-weight way
of forming equivalence classes of small integers.

IntEqClasses doesn't allow enumeration of the elements in a class.

llvm-svn: 122293

llvm-svn: 121160

llvm-svn: 120329

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