patch applied (ghc-6.8/ghc): Add iterative coalescing to graph
ben.lippmeier at anu.edu.au
Wed Sep 12 06:06:30 EDT 2007
Fri Sep 7 10:23:15 PDT 2007 Ben.Lippmeier at anu.edu.au
* 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..
M ./compiler/main/DynFlags.hs -1 +3
M ./compiler/nativeGen/AsmCodeGen.lhs -18 +12
M ./compiler/nativeGen/GraphBase.hs +3
M ./compiler/nativeGen/GraphColor.hs -86 +103
M ./compiler/nativeGen/GraphOps.hs -17 +125
M ./compiler/nativeGen/RegAllocColor.hs -6 +19
More information about the Cvs-ghc