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:

- 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.