Add iterative coalescing to graph coloring allocator
authorBen.Lippmeier@anu.edu.au <unknown>
Fri, 7 Sep 2007 17:23:15 +0000 (17:23 +0000)
committerBen.Lippmeier@anu.edu.au <unknown>
Fri, 7 Sep 2007 17:23:15 +0000 (17:23 +0000)
commit12d0b38821771fd9820d655ed73b29c688cb7b59
tree74382fa50e140d937bed73154d1cf072015e394f
parent18f671cc4b459195c24f0ea3b16fc600d5e7a4bf
Add iterative coalescing to graph coloring allocator

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..
compiler/main/DynFlags.hs
compiler/nativeGen/AsmCodeGen.lhs
compiler/nativeGen/GraphBase.hs
compiler/nativeGen/GraphColor.hs
compiler/nativeGen/GraphOps.hs
compiler/nativeGen/RegAllocColor.hs