2 -- | Types for the general graph colorer.
3 module GraphBase (
4 Triv,
5 Graph (..),
6 initGraph,
7 graphMapModify,
9 Node (..), newNode,
10 )
13 where
15 import UniqSet
16 import UniqFM
19 -- | A fn to check if a node is trivially colorable
20 -- For graphs who's color classes are disjoint then a node is 'trivially colorable'
21 -- when it has less neighbors and exclusions than available colors for that node.
22 --
23 -- For graph's who's color classes overlap, ie some colors alias other colors, then
24 -- this can be a bit more tricky. There is a general way to calculate this, but
25 -- it's likely be too slow for use in the code. The coloring algorithm takes
26 -- a canned function which can be optimised by the user to be specific to the
27 -- specific graph being colored.
28 --
29 -- for details, see "A Generalised Algorithm for Graph-Coloring Register Allocation"
30 -- Smith, Ramsey, Holloway - PLDI 2004.
31 --
32 type Triv k cls color
33 = cls -- the class of the node we're trying to color.
34 -> UniqSet k -- the node's neighbors.
35 -> UniqSet color -- the node's exclusions.
36 -> Bool
39 -- | The Interference graph.
40 -- There used to be more fields, but they were turfed out in a previous revision.
41 -- maybe we'll want more later..
42 --
43 data Graph k cls color
44 = Graph {
45 -- | All active nodes in the graph.
46 graphMap :: UniqFM (Node k cls color) }
49 -- | An empty graph.
50 initGraph :: Graph k cls color
51 initGraph
52 = Graph
53 { graphMap = emptyUFM }
56 -- | Modify the finite map holding the nodes in the graph.
57 graphMapModify
58 :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color))
59 -> Graph k cls color -> Graph k cls color
61 graphMapModify f graph
62 = graph { graphMap = f (graphMap graph) }
66 -- | Graph nodes.
67 -- Represents a thing that can conflict with another thing.
68 -- For the register allocater the nodes represent registers.
69 --
70 data Node k cls color
71 = Node {
72 -- | A unique identifier for this node.
73 nodeId :: k
75 -- | The class of this node,
76 -- determines the set of colors that can be used.
77 , nodeClass :: cls
79 -- | The color of this node, if any.
80 , nodeColor :: Maybe color
82 -- | Neighbors which must be colored differently to this node.
83 , nodeConflicts :: UniqSet k
85 -- | Colors that cannot be used by this node.
86 , nodeExclusions :: UniqSet color
88 -- | Colors that this node would prefer to be, in decending order.
89 , nodePreference :: [color]
91 -- | Neighbors that this node would like to be colored the same as.
92 , nodeCoalesce :: UniqSet k }
95 -- | An empty node.
96 newNode :: k -> cls -> Node k cls color
97 newNode k cls
98 = Node
99 { nodeId = k
100 , nodeClass = cls
101 , nodeColor = Nothing
102 , nodeConflicts = emptyUniqSet
103 , nodeExclusions = emptyUniqSet
104 , nodePreference = []
105 , nodeCoalesce = emptyUniqSet }