X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FnativeGen%2FGraphColor.hs;h=a0c54e4694493c97d1d6991427337da933b669d2;hb=94368126b8933a5a198bf5c59599f621087fbace;hp=ecebf2767350d183ca0e2772c4412ed7cbe00539;hpb=a7f409e855291efece19970927156fae4e527b6e;p=ghc-hetmet.git

diff --git a/compiler/nativeGen/GraphColor.hs b/compiler/nativeGen/GraphColor.hs
index ecebf27..a0c54e4 100644
--- a/compiler/nativeGen/GraphColor.hs
+++ b/compiler/nativeGen/GraphColor.hs
@@ -3,13 +3,7 @@
 --	This is a generic graph coloring library, abstracted over the type of
 --	the node keys, nodes and colors.
 --
-
-{-# OPTIONS -w #-}
--- The above warning supression flag is a temporary kludge.
--- While working on this module you are encouraged to remove it and fix
--- any warnings in the module. See
---     http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
--- for details
+{-# OPTIONS -fno-warn-missing-signatures #-}
 
 module GraphColor ( 
 	module GraphBase,
@@ -62,14 +56,16 @@ colorGraph colors triv spill graph0
 
  	-- run the scanner to slurp out all the trivially colorable nodes
   	(ksTriv, ksProblems)
-		= colorScan colors triv spill [] emptyUniqSet graph_coalesced
+		= colorScan triv spill graph_coalesced
  
 	-- color the trivially colorable nodes
+	--	as the keys were added to the front of the list while they were scanned,
+	--	this colors them in the reverse order they were found, as required by the algorithm.
 	(graph_triv, ksNoTriv)
 		= assignColors colors graph_coalesced ksTriv
 
  	-- try and color the problem nodes
-	(graph_prob, ksNoColor)	= assignColors colors graph_triv (uniqSetToList ksProblems)
+	(graph_prob, ksNoColor)	= assignColors colors graph_triv ksProblems
 
 	-- if the trivially colorable nodes didn't color then something is wrong
 	--	with the provided triv function.
@@ -85,6 +81,90 @@ colorGraph colors triv spill graph0
 	 	, mkUniqSet ksNoColor
 		, listToUFM rsCoalesce)
 	
+
+-- | Scan through the conflict graph separating out trivially colorable and
+--	potentially uncolorable (problem) nodes.
+--
+--	Checking whether a node is trivially colorable or not is a resonably expensive operation,
+--	so after a triv node is found and removed from the graph it's no good to return to the 'start'
+--	of the graph and recheck a bunch of nodes that will probably still be non-trivially colorable.
+--
+--	To ward against this, during each pass through the graph we collect up a list of triv nodes
+--	that were found, and only remove them once we've finished the pass. The more nodes we can delete
+--	at once the more likely it is that nodes we've already checked will become trivially colorable
+--	for the next pass.
+--
+colorScan
+	:: ( Uniquable k, Uniquable cls, Uniquable color)
+	=> 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.
+	-> Graph k cls color		-- ^ the graph to scan
+	-> ([k], [k])			--  triv colorable, problem nodes
+
+
+colorScan triv spill graph
+	= colorScan' triv spill graph
+		[]	[]
+		[]
+		(eltsUFM $ graphMap graph)
+
+-- we've reached the end of the candidates list
+colorScan' triv spill graph
+	ksTriv 	ksTrivFound
+	ksSpill
+	[]
+
+	-- if the graph is empty then we're done
+	| isNullUFM $ graphMap graph
+	= (ksTrivFound ++ ksTriv, ksSpill)
+
+	-- if we haven't found a trivially colorable node then we'll have to
+	--	choose a spill candidate and leave it uncolored
+	| []		<- ksTrivFound
+	, kSpill	<- spill graph			-- choose a spill candiate
+	, graph'	<- delNode kSpill graph		-- remove it from the graph
+	, nsRest'	<- eltsUFM $ graphMap graph'	-- graph has changed, so get new node list
+
+	= colorScan' triv spill graph'
+		ksTriv ksTrivFound
+		(kSpill : ksSpill)
+		nsRest'
+
+	-- we're at the end of the candidates list but we've found some triv nodes
+	--	along the way. We can delete them from the graph and go back for more.
+	| graph'	<- foldr delNode graph ksTrivFound
+	, nsRest'	<- eltsUFM $ graphMap graph'
+
+	= colorScan' triv spill graph'
+		(ksTrivFound ++ ksTriv) []
+		ksSpill
+		nsRest'
+
+-- check if the current node is triv colorable
+colorScan' triv spill graph
+	ksTriv	ksTrivFound
+	ksSpill
+	(node : nsRest)
+
+	-- node is trivially colorable
+	--	add it to the found nodes list and carry on.
+	| k	<- nodeId node
+	, triv (nodeClass node) (nodeConflicts node) (nodeExclusions node)
+
+	= colorScan' triv spill graph
+		ksTriv 	(k : ksTrivFound)
+		ksSpill
+		nsRest
+
+	-- node wasn't trivially colorable, skip over it and look in the rest of the list
+	| otherwise
+	= colorScan' triv spill graph
+		ksTriv ksTrivFound
+		ksSpill
+		nsRest
+
+{- -- This is cute and easy to understand, but too slow.. BL 2007/09
+
 colorScan colors triv spill safe prob graph
 
 	-- empty graphs are easy to color.
@@ -106,7 +186,8 @@ colorScan colors triv spill safe prob graph
 	| k		<- spill graph
 	= colorScan colors triv spill
 		safe (addOneToUniqSet prob k) (delNode k graph)
-		
+-}
+
 
 -- | Try to assign a color to all these nodes.
 
@@ -121,7 +202,7 @@ assignColors
 assignColors colors graph ks 
  	= assignColors' colors graph [] ks
 
- where	assignColors' colors graph prob []
+ where	assignColors' _ graph prob []
 		= (graph, prob)
 
 	assignColors' colors graph prob (k:ks)
@@ -147,8 +228,6 @@ assignColors colors graph ks
 --	taking into account preferences, neighbors and exclusions.
 --	returns Nothing if no color can be assigned to this node.
 --
---	TODO: avoid using the prefs of the neighbors, if at all possible.
---
 selectColor
 	:: ( Uniquable k, Uniquable cls, Uniquable color, Eq color)
 	=> UniqFM (UniqSet color)	-- ^ map of (node class -> set of colors available for this class).
@@ -176,28 +255,50 @@ selectColor colors graph u
 			$ catMaybes 
 			$ map nodeColor nsConflicts
 	
-	-- colors that are still ok
+	-- the prefs of our neighbors
+	colors_neighbor_prefs
+			= mkUniqSet
+			$ concat $ map nodePreference nsConflicts
+
+	-- colors that are still valid for us
 	colors_ok_ex	= minusUniqSet colors_avail (nodeExclusions node)
 	colors_ok	= minusUniqSet colors_ok_ex colors_conflict
 				
 	-- the colors that we prefer, and are still ok
 	colors_ok_pref	= intersectUniqSets
 				(mkUniqSet $ nodePreference node) colors_ok
-				
+
+	-- the colors that we could choose while being nice to our neighbors
+	colors_ok_nice	= minusUniqSet
+				colors_ok colors_neighbor_prefs
+
+	-- the best of all possible worlds..
+	colors_ok_pref_nice
+			= intersectUniqSets
+				colors_ok_nice colors_ok_pref
+
 	-- make the decision
 	chooseColor
 
-		-- we got one of our preferences, score!
+		-- everyone is happy, yay!
+		| not $ isEmptyUniqSet colors_ok_pref_nice
+		, c : _		<- filter (\x -> elementOfUniqSet x colors_ok_pref_nice)
+					(nodePreference node)
+		= Just c
+
+		-- we've got one of our preferences
 		| not $ isEmptyUniqSet colors_ok_pref	
-		, c : rest	<- uniqSetToList colors_ok_pref
+		, c : _		<- filter (\x -> elementOfUniqSet x colors_ok_pref)
+					(nodePreference node)
 		= Just c
 		
 		-- it wasn't a preference, but it was still ok
 		| not $ isEmptyUniqSet colors_ok
-		, c : rest	<- uniqSetToList colors_ok
+		, c : _		<- uniqSetToList colors_ok
 		= Just c
 		
-		-- leave this node uncolored
+		-- no colors were available for us this time.
+		--	looks like we're going around the loop again..
 		| otherwise
 		= Nothing