X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2Futils%2FGraphColor.hs;h=e381fbf7f65f57c85a52425a4028e13de8306c27;hb=21a85c38819cfc951c6c8b440d9ea74f3fa02d55;hp=307803a988109660ca35c224bb2f1b1c7e4436c5;hpb=b01110d1352de5d972d8fb63f28c244d2c1ff99b;p=ghc-hetmet.git

diff --git a/compiler/utils/GraphColor.hs b/compiler/utils/GraphColor.hs
index 307803a..e381fbf 100644
--- a/compiler/utils/GraphColor.hs
+++ b/compiler/utils/GraphColor.hs
@@ -1,9 +1,9 @@
+{-# OPTIONS -fno-warn-missing-signatures #-}
 
 -- | Graph Coloring.
 --	This is a generic graph coloring library, abstracted over the type of
 --	the node keys, nodes and colors.
 --
-{-# OPTIONS -fno-warn-missing-signatures #-}
 
 module GraphColor ( 
 	module GraphBase,
@@ -19,7 +19,7 @@ import GraphOps
 import GraphPpr
 
 import Unique
-import UniqFM
+import LazyUniqFM
 import UniqSet
 import Outputable	
 
@@ -39,6 +39,7 @@ colorGraph
 	   , Eq color, Eq cls, Ord k
 	   , Outputable k, Outputable cls, Outputable color)
 	=> Bool				-- ^ whether to do iterative coalescing
+	-> Int				-- ^ how many times we've tried to color this graph so far.
 	-> UniqFM (UniqSet color)	-- ^ map of (node class -> set of colors available for this class).
 	-> Triv   k cls color 		-- ^ fn to decide whether a node is trivially colorable.
 	-> (Graph k cls color -> k)	-- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.
@@ -49,15 +50,22 @@ colorGraph
 	   , UniqFM  k )		-- map of regs (r1 -> r2) that were coaleced
 	   				--	 r1 should be replaced by r2 in the source
 
-colorGraph iterative colors triv spill graph0
+colorGraph iterative spinCount colors triv spill graph0
  = let
-	-- if we're not doing iterative coalescing, then just do a single coalescing
-	--	pass at the front. This won't be as good but should still eat up a
-	--	lot of the reg-reg moves.
+	-- If we're not doing iterative coalescing then do an aggressive coalescing first time
+	--	around and then conservative coalescing for subsequent passes.
+	--
+	--	Aggressive coalescing is a quick way to get rid of many reg-reg moves. However, if
+	--	there is a lot of register pressure and we do it on every round then it can make the
+	--	graph less colorable and prevent the algorithm from converging in a sensible number
+	--	of cycles.
+	--
 	(graph_coalesced, kksCoalesce1)
-		= if not iterative
-			then coalesceGraph False triv graph0
-			else (graph0, [])
+	 = if iterative
+		then (graph0, [])
+		else if spinCount == 0
+			then coalesceGraph True  triv graph0
+			else coalesceGraph False triv graph0
 
  	-- run the scanner to slurp out all the trivially colorable nodes
 	--	(and do coalescing if iterative coalescing is enabled)
@@ -139,7 +147,7 @@ colorScan_spin iterative triv spill graph
 
 	-- if the graph is empty then we're done
 	| isNullUFM $ graphMap graph
-	= (ksTriv, ksSpill, kksCoalesce)
+	= (ksTriv, ksSpill, reverse kksCoalesce)
 
 	-- Simplify:
 	--	Look for trivially colorable nodes.
@@ -154,26 +162,26 @@ colorScan_spin iterative triv spill graph
 			$ graph
 
 	, ksTrivFound	<- map nodeId nsTrivFound
-	, graph3	<- foldr (\k g -> let Just g' = delNode k g
+	, graph2	<- foldr (\k g -> let Just g' = delNode k g
 	   				  in  g')
 				graph ksTrivFound
 
-	= colorScan_spin iterative triv spill graph3
+	= colorScan_spin iterative triv spill graph2
 		(ksTrivFound ++ ksTriv)
 		ksSpill
 		kksCoalesce
 
 	-- Coalesce:
 	-- 	If we're doing iterative coalescing and no triv nodes are avaliable
-	--	then it's type for a coalescing pass.
+	--	then it's time for a coalescing pass.
 	| iterative
 	= case coalesceGraph False triv graph of
 
 		-- we were able to coalesce something
-		--	go back and see if this frees up more nodes to be trivially colorable.
+		--	go back to Simplify and see if this frees up more nodes to be trivially colorable.
 		(graph2, kksCoalesceFound @(_:_))
 		 -> colorScan_spin iterative triv spill graph2
-			ksTriv ksSpill (kksCoalesceFound ++ kksCoalesce)
+			ksTriv ksSpill (reverse kksCoalesceFound ++ kksCoalesce)
 
 		-- Freeze:
 		-- nothing could be coalesced (or was triv),