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

1 files changed, 3 insertions, 0 deletions

diff --git a/compiler/nativeGen/GraphBase.hs b/compiler/nativeGen/GraphBase.hs
index b980ba2261..04eda96120 100644
--- a/compiler/nativeGen/GraphBase.hs
+++ b/compiler/nativeGen/GraphBase.hs
@@ -16,6 +16,7 @@ where
 import UniqSet
 import UniqFM
 
+
 -- | A fn to check if a node is trivially colorable
 --	For graphs who's color classes are disjoint then a node is 'trivially colorable'
 --	when it has less neighbors and exclusions than available colors for that node.
@@ -45,6 +46,7 @@ data Graph k cls color
 	-- | All active nodes in the graph.
 	  graphMap		:: UniqFM (Node k cls color)  }
 
+
 -- | An empty graph.	
 initGraph :: Graph k cls color
 initGraph
@@ -106,3 +108,4 @@ newNode k cls
 
 
 
+