move generic graph-colouring code into util

It is needed by cmm/StackColor, and hence is needed even when there is no
native code generator.

1 files changed, 0 insertions, 111 deletions

diff --git a/compiler/nativeGen/GraphBase.hs b/compiler/nativeGen/GraphBase.hs
deleted file mode 100644
index 04eda96120..0000000000
--- a/compiler/nativeGen/GraphBase.hs
+++ /dev/null
@@ -1,111 +0,0 @@
-
--- | Types for the general graph colorer.
-
-module GraphBase (
-	Triv,
-	Graph (..),
-	initGraph,
-	graphMapModify,
-
-	Node  (..),	newNode,
-)
-	
-
-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.
---
---	For graph's who's color classes overlap, ie some colors alias other colors, then
---	this can be a bit more tricky. There is a general way to calculate this, but 
---	it's likely be too slow for use in the code. The coloring algorithm takes
---	a canned function which can be optimised by the user to be specific to the 
---	specific graph being colored.
---
---	for details, see  "A Generalised Algorithm for Graph-Coloring Register Allocation"
---				Smith, Ramsey, Holloway - PLDI 2004.
---
-type Triv k cls color
-	=  cls 			-- ^ the class of the node we're trying to color.
-	-> UniqSet k		-- ^ the node's neighbors.
-	-> UniqSet color 	-- ^ the node's exclusions.
-	-> Bool		
-
-
--- | The Interference graph.
---	There used to be more fields, but they were turfed out in a previous revision.
---	maybe we'll want more later..
---
-data Graph k cls color
-	= Graph { 
-	-- | All active nodes in the graph.
-	  graphMap		:: UniqFM (Node k cls color)  }
-
-
--- | An empty graph.	
-initGraph :: Graph k cls color
-initGraph
-	= Graph
-	{ graphMap		= emptyUFM }
-
-
--- | Modify the finite map holding the nodes in the graph.
-graphMapModify 
-	:: (UniqFM (Node k cls color) -> UniqFM (Node k cls color))
-	-> Graph k cls color -> Graph k cls color
-
-graphMapModify f graph
-	= graph { graphMap	= f (graphMap graph) }
-	
-		
-
--- | Graph nodes.
---	Represents a thing that can conflict with another thing.
---	For the register allocater the nodes represent registers.
---
-data Node k cls color
-	= Node { 	
-	-- | A unique identifier for this node.
-	  nodeId 		:: k
-
-	-- | The class of this node,
-	--	determines the set of colors that can be used.
-	, nodeClass		:: cls
-
-	-- | The color of this node, if any.
-	, nodeColor		:: Maybe color
-
-	-- | Neighbors which must be colored differently to this node.
-	, nodeConflicts		:: UniqSet k
-
-	-- | Colors that cannot be used by this node.
-	, nodeExclusions	:: UniqSet color
-
-	-- | Colors that this node would prefer to be, in decending order.
-	, nodePreference	:: [color]  
-
-	-- | Neighbors that this node would like to be colored the same as.
-	, nodeCoalesce		:: UniqSet k }
-
-
--- | An empty node.
-newNode :: k -> cls -> Node k cls color
-newNode k cls
-	= Node
-	{ nodeId		= k
-	, nodeClass		= cls
-	, nodeColor		= Nothing
-	, nodeConflicts		= emptyUniqSet
-	, nodeExclusions	= emptyUniqSet
-	, nodePreference	= [] 
-	, nodeCoalesce		= emptyUniqSet }
-
-
-
-
-