llvm-svn: 120330

llvm-svn: 120329

llvm-svn: 120298

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.

llvm-svn: 120264

These iterators don't point anywhere, and they can't be compared to anything.
They are only good for assigning to.

llvm-svn: 120239

This is a version of find() that always searches forwards and is faster for
local searches.

llvm-svn: 120237

llvm-svn: 120227

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.

llvm-svn: 120226

GNU ld/PECOFF accepts but ignores them below;
  --version-script
  --export-dynamic
  --rpath

FIXME: autoconf should be aware of them.
llvm-svn: 120179

Change temporary debugging code to write a dot file directly.

llvm-svn: 120171

llvm-svn: 120105

llvm-svn: 120103

llvm-svn: 120101

to use lowercase letters for the start of most
method names and to replace some method names
with more descriptive names (e.g., "getLeft()"
instead of "Left()").  No real functionality
change.

llvm-svn: 120070

being in terms of excessively complex template logic.

llvm-svn: 119992

llvm-svn: 119872

llvm-svn: 119871

llvm-svn: 119870

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

CMake can pass *.def to link.exe.

llvm-svn: 119783

MSVC9 and 8 cannot compile ValueMapTest.cpp due to their bug.
See issue#331418 in Visual Studio.

llvm-svn: 119782

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

This is because of bug 331418 on Microsoft Connect.

llvm-svn: 119600

llvm-svn: 119040

llvm-svn: 117646

UnitTests for building all the unit tests.

llvm-svn: 117545

until other LLVM projects using these are cleaned up.

llvm-svn: 117200

llvm-svn: 117057

llvm-svn: 116834

Get rid of static constructors for pass registration.  Instead, every pass exposes an initializeMyPassFunction(), which
must be called in the pass's constructor.  This function uses static dependency declarations to recursively initialize
the pass's dependencies.

Clients that only create passes through the createFooPass() APIs will require no changes.  Clients that want to use the
CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h
before parsing commandline arguments.

I have tested this with all standard configurations of clang and llvm-gcc on Darwin.  It is possible that there are problems
with the static dependencies that will only be visible with non-standard options.  If you encounter any crash in pass
registration/creation, please send the testcase to me directly.

llvm-svn: 116820

llvm-svn: 116252

This time correctly.

llvm-svn: 116247

This reverts commit 116234.

It compiled just fine with MSVC and clang...

llvm-svn: 116242

llvm-svn: 116235

llvm-svn: 116234

llvm-svn: 115503

also fixes PR8250.

llvm-svn: 114972

llvm-svn: 114835