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, 111 insertions, 0 deletions

diff --git a/compiler/utils/GraphBase.hs b/compiler/utils/GraphBase.hs
new file mode 100644
index 0000000000..04eda96120
--- /dev/null
+++ b/compiler/utils/GraphBase.hs
@@ -0,0 +1,111 @@
+
+-- | 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 }
+
+
+
+
+