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

were not hashing to the same value.  Analysis
and patch by Frits van Bommel!

llvm-svn: 119770

llvm-svn: 119769

llvm-svn: 119768

llvm-svn: 119767

llvm-svn: 119762

llvm-svn: 119761

Fix .o emission of ARM movt/movw. MCSymbolRefExpr::VK_ARM_(HI||LO)16 for the .o path now works for ARM.
Note: lo16AllZero remains in ARMInstrInfo.td - It can be factored out when Thumb movt is repaired.
Existing tests cover this update.

llvm-svn: 119760

llvm-svn: 119759

llvm-svn: 119756

llvm-svn: 119755

llvm-svn: 119754

llvm-svn: 119753

Fix bug in DAGCombiner for ARM that was trying to do a ShiftCombine on illegal types (vector should be split first).
Added test case.

llvm-svn: 119749

should delete what when the object gets copied around. It's also making valgrind
upset.

llvm-svn: 119747

llvm-svn: 119744

llvm-svn: 119743

This makes it symmetric with the 'u' modifier that forces an unsigned type.
This is needed for unsigned vector shifts, where the shift amount still needs
to be signed.  PR8482 (Radar 8603521).

llvm-svn: 119742

llvm-svn: 119740

not anyext(select).  Spotted by Frits van Bommel.

llvm-svn: 119739

This function was being called from two different places for completely
unrelated reasons.  During type legalization, it was called to expand 64-bit
shift operations.  During operation legalization, it was called to handle
Neon vector shifts.  The vector shift code was not written to check for
illegal types, since it was assumed to be only called after type legalization.
Fixed this by splitting off the 64-bit shift expansion into a separate
function.  I don't have a particular testcase for this; I just noticed it
by inspection.

llvm-svn: 119738

llvm-svn: 119737

llvm-svn: 119733

if the extension types were not the same.  The result was that if you
fed a select with sext and zext loads, as in the testcase, then it
would get turned into a zext (or sext) of the select, which is wrong
in the cases when it should have been an sext (resp. zext).  Reported
and diagnosed by Sebastien Deldon.

llvm-svn: 119728

preserves LCSSA form out of ScalarEvolution and into the LoopInfo
class.  Use it to check that SimplifyInstruction simplifications
are not breaking LCSSA form.  Fixes PR8622.

llvm-svn: 119727

llvm-svn: 119726

Remove movePastCSLoadStoreOps and associated code for simple pointer
increments. Update routines that depended upon other opcodes for save/restore.

Adjust all testcases accordingly.

llvm-svn: 119725

LLVMContext, causing memory errors.  Patch by Peter Collingbourne.

llvm-svn: 119721

Use thread-safe statics to avoid a static constructor here.  This isn't thread-safe on MSVC, but we don't
support threaded LLVM there anyways.

llvm-svn: 119718

llvm-svn: 119717

llvm-svn: 119716

Completely rework the datastructure GVN uses to represent the value number to leader mapping.  Previously,
this was a tree of hashtables, and a query recursed into the table for the immediate dominator ad infinitum
if the initial lookup failed.  This led to really bad performance on tall, narrow CFGs.

We can instead replace it with what is conceptually a multimap of value numbers to leaders (actually
represented by a hashtable with a list of Value*'s as the value type), and then
determine which leader from that set to use very cheaply thanks to the DFS numberings maintained by
DominatorTree.  Because there are typically few duplicates of a given value, this scan tends to be
quite fast.  Additionally, we use a custom linked list and BumpPtr allocation to avoid any unnecessary
allocation in representing the value-side of the multimap.

This change brings with it a 15% (!) improvement in the total running time of GVN on 403.gcc, which I
think is pretty good considering that includes all the "real work" being done by MemDep as well.

The one downside to this approach is that we can no longer use GVN to perform simple conditional progation,
but that seems like an acceptable loss since we now have LVI and CorrelatedValuePropagation to pick up
the slack.  If you see conditional propagation that's not happening, please file bugs against LVI or CVP.

llvm-svn: 119714

instruction. Any that may be expanded otherwise by MC lowering should
override this value. rdar://8683274

llvm-svn: 119713

llvm-svn: 119712

llvm-svn: 119711

llvm-svn: 119708

simple form of INITIALIZE_PASS.

llvm-svn: 119707

llvm-svn: 119706

llvm-svn: 119705

enabling more PRE. PR8586.

llvm-svn: 119704