+
+-- | 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 }
+
+
+
+
+