GitLab

Coalescences must be applied to the unsimplified graph in the same order 
they were found by the iterative coalescing algorithm - otherwise
the vreg rewrite mapping will be wrong and badness will ensue.

On further testing it turns out that using Chaitin's spill cost formula
of counting the number of uses of a var and then dividing by the degree
of the node isn't actually a win. Perhaps because this isn't counting 
the number of actual spills inserted in the output code.

This would be worth revisiting if other work manages to increase the 
register pressure in the native code.

It is needed by cmm/StackColor, and hence is needed even when there is no
native code generator.

Iterative coalescing interleaves conservative coalesing with the regular
simplify/scan passes. This increases the chance that nodes will be coalesced
as they will have a lower degree than at the beginning of simplify. The end
result is that more register to register moves will be eliminated in the
output code, though the iterative nature of the algorithm makes it slower
compared to non-iterative coloring.

Use -fregs-iterative  for graph coloring allocation with iterative coalescing
    -fregs-graph      for non-iterative coalescing.

The plan is for iterative coalescing to be enabled with -O2 and have a 
quicker, non-iterative algorithm otherwise. The time/benefit tradeoff
between iterative and not is still being tuned - optimal graph coloring
is NP-hard, afterall..

We now do a deep seq on the graph after it is 'built', but before coloring.
Without this, the colorer will just force bits of it and the heap will
fill up with half evaluated pieces of graph from previous build/spill
stages and zillions of apply thunks.

When selecting a color for a node, try and avoid using colors that
conflicting nodes prefer. Not sure if this'll make much difference,
but it was easy enough to add..

Testing whether a node in the conflict graph is trivially 
colorable (triv) is still a somewhat expensive operation.

When we find a triv node during scanning, even though we remove
it and its edges from the graph, this is unlikely to to make the
nodes we've just scanned become triv - so there's not much point
re-scanning them right away.

Scanning now takes place in passes. We scan the whole graph for
triv nodes and remove all the ones found in a batch before rescanning
old nodes.

Register allocation for SHA1.lhs now takes (just) 40% of total
compile time with -O2 -fregs-graph on x86

Avoid coalescing nodes in the register conflict graph if the
new node will not be trivially colorable. Also remove the
front end aggressive coalescing pass.
  
For typical Haskell code the graph coloring allocator now does
about as well as the linear allocator.
  
For code with a large amount of register pressure it does much
better, but takes longer.
  
For SHA1.lhs from darcs on x86
   
          spills    reloads    reg-reg-moves
          inserted   inserted  left in code   compile-time
  linear    1068      1311        229            7.69(s)
  graph      387       902        340           16.12(s)

Older GHCs can't parse OPTIONS_GHC.
This also changes the URL referenced for the -w options from
WorkingConventions#Warnings to CodingStyle#Warnings for the compiler
modules.

Conservative and iterative coalescing come next.

Refactored linear allocator into separate liveness annotation and allocation stages.
Added graph coloring allocator, use -fregs-graph to enable.
  New dump flags are
    -ddump-asm-native          -- output of cmm -> native transform.
    -ddump-asm-liveness        -- code annotated with register liveness info
    -ddump-asm-coalesce        -- output of register move coalescing
                                    (this is a separate pass when using the coloring allocator)
                                    (this could change in the future)
    -ddump-asm-regalloc        -- code after register allocation
    -ddump-asm-regalloc-stages -- blocks after each build/spill stage of coloring allocator
    -ddump-asm-conflicts       -- a global register liveness graph in graphviz format 
        
The new register allocator will allocate some registers, but it's not
quite ready for prime-time yet. The spill code generator needs some work...