New PBQP solver, and updates to the PBQP graph.

The previous PBQP solver was very robust but consumed a lot of memory,
performed a lot of redundant computation, and contained some unnecessarily tight
coupling that prevented experimentation with novel solution techniques. This new
solver is an attempt to address these shortcomings.

Important/interesting changes:

1) The domain-independent PBQP solver class, HeuristicSolverImpl, is gone.
It is replaced by a register allocation specific solver, PBQP::RegAlloc::Solver
(see RegAllocSolver.h).

The optimal reduction rules and the backpropagation algorithm have been extracted
into stand-alone functions (see ReductionRules.h), which can be used to build
domain specific PBQP solvers. This provides many more opportunities for
domain-specific knowledge to inform the PBQP solvers' decisions. In theory this
should allow us to generate better solutions. In practice, we can at least test
out ideas now.

As a side benefit, I believe the new solver is more readable than the old one.

2) The solver type is now a template parameter of the PBQP graph.

This allows the graph to notify the solver of any modifications made (e.g. by
domain independent rules) without the overhead of a virtual call. It also allows
the solver to supply policy information to the graph (see below).

3) Significantly reduced memory overhead.

Memory management policy is now an explicit property of the PBQP graph (via
the CostAllocator typedef on the graph's solver template argument). Because PBQP
graphs for register allocation tend to contain many redundant instances of
single values (E.g. the value representing an interference constraint between
GPRs), the new RASolver class uses a uniquing scheme. This massively reduces
memory consumption for large register allocation problems. For example, looking
at the largest interference graph in each of the SPEC2006 benchmarks (the
largest graph will always set the memory consumption high-water mark for PBQP),
the average memory reduction for the PBQP costs was 400x. That's times, not
percent. The highest was 1400x. Yikes. So - this is fixed.

"PBQP: No longer feasting upon every last byte of your RAM".

Minor details:

- Fully C++11'd. Never copy-construct another vector/matrix!

- Cute tricks with cost metadata: Metadata that is derived solely from cost
matrices/vectors is attached directly to the cost instances themselves. That way
if you unique the costs you never have to recompute the metadata. 400x less
memory means 400x less cost metadata (re)computation.

Special thanks to Arnaud de Grandmaison, who has been the source of much
encouragement, and of many very useful test cases.

This new solver forms the basis for future work, of which there's plenty to do.
I will be adding TODO notes shortly.

- Lang.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202551 91177308-0d34-0410-b5e6-96231b3b80d8
Jumped the gun with r202551 and broke some bots that weren't yet C++11ified.

Reverting until the C++11 switch is complete.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202554 91177308-0d34-0410-b5e6-96231b3b80d8
Reflow isProfitableToMakeFastCC

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202555 91177308-0d34-0410-b5e6-96231b3b80d8
[CMake] Remove dead C backend option

Patch by Jevin Sweval!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202556 91177308-0d34-0410-b5e6-96231b3b80d8
SpillPlacement: fix a bug in iterate.

Inside iterate, we scan backwards then scan forwards in a loop. When iteration
is not zero, the last node was just updated so we can skip it. But when
iteration is zero, we can't skip the last node.

For the testing case, fixing this will save a spill and move register copies
from hot path to cold path.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202557 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] Emit 'restore' instead of 'restore %g0, %g0, %g0'. This improves the readability of the generated code.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202563 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] Add support for parsing directives in SparcAsmParser.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202564 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] 80 column rule. No functionality change.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202565 91177308-0d34-0410-b5e6-96231b3b80d8
[docs] Update the docs to remove my hedging about C++98 vs. C++11. =]
The switch has been thrown. While I'm still watching for any failures or
problems with this, the documentation can go ahead and move forward.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202566 91177308-0d34-0410-b5e6-96231b3b80d8
[C++11] Switch the CMake option from LLVM_ENABLE_CXX11 (default on) to
LLVM_ENABLE_CXX1Y (default *off*). =D C++98 is dead. Long live C++11.

I don't exactly recommend using C++1y just yet though...

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202567 91177308-0d34-0410-b5e6-96231b3b80d8
[C++11] Replace autoconf --enable-cxx11 with --enable-cxx1y. The
baseline is now C++11, and we unconditionally add -std=c++11 to the
flags.

This has the dim potential to break some non-GNU-compatible compiler (in
terms of -std flags) using the makefiles, but those makefiles are
littered with GNU-style compile flags so it would be very surprising to
me for it to actually happen in practice. As always, do let me know if
there is a toolchain you're using where this doesn't work, and I'll be
watching the bots.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202569 91177308-0d34-0410-b5e6-96231b3b80d8
Fix RWMutex to be thread-safe when pthread_rwlock is not available

lib/Support/RWMutex.cpp contains an implementation of RWMutex that
uses pthread_rwlock, but when pthread_rwlock is not available (such as
under NaCl, when using newlib), it silently falls back to using the
no-op definition in lib/Support/Unix/RWMutex.inc, which is not
thread-safe.

Fix this case to be thread-safe by using a normal mutex.

Differential Revision: http://llvm-reviews.chandlerc.com/D2892

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202570 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] Teach SparcAsmParser to emit correct relocations for PIC code.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202571 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] Implement writeNopData. Emit actual NOP instruction instead of just filling with zeroes.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202572 91177308-0d34-0410-b5e6-96231b3b80d8
Add support for parsing sun-style section flags in ELFAsmParser.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202573 91177308-0d34-0410-b5e6-96231b3b80d8
[C++11] Turn off compiler-based detection of R-value references, relying
on the fact that we now build in C++11 mode with modern compilers. This
should flush out any issues. If the build bots are happy with this, I'll
GC all the code for coping without R-value references.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202574 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] Add support to disassemble sparc memory instructions.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202575 91177308-0d34-0410-b5e6-96231b3b80d8
Rewrite a terrible comment about the machine model.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202576 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] Add support for decoding call instructions in the sparc disassembler.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202577 91177308-0d34-0410-b5e6-96231b3b80d8
[Sparc] Add support to decode negative simm13 operands in the sparc disassembler.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202578 91177308-0d34-0410-b5e6-96231b3b80d8