2 -- | Types for the general graph colorer.
4 -- The above warning supression flag is a temporary kludge.
5 -- While working on this module you are encouraged to remove it and fix
6 -- any warnings in the module. See
7 -- http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions#Warnings
25 -- | A fn to check if a node is trivially colorable
26 -- For graphs who's color classes are disjoint then a node is 'trivially colorable'
27 -- when it has less neighbors and exclusions than available colors for that node.
29 -- For graph's who's color classes overlap, ie some colors alias other colors, then
30 -- this can be a bit more tricky. There is a general way to calculate this, but
31 -- it's likely be too slow for use in the code. The coloring algorithm takes
32 -- a canned function which can be optimised by the user to be specific to the
33 -- specific graph being colored.
35 -- for details, see "A Generalised Algorithm for Graph-Coloring Register Allocation"
36 -- Smith, Ramsey, Holloway - PLDI 2004.
39 = cls -- ^ the class of the node we're trying to color.
40 -> UniqSet k -- ^ the node's neighbors.
41 -> UniqSet color -- ^ the node's exclusions.
45 -- | The Interference graph.
46 -- There used to be more fields, but they were turfed out in a previous revision.
47 -- maybe we'll want more later..
49 data Graph k cls color
51 -- | All active nodes in the graph.
52 graphMap :: UniqFM (Node k cls color) }
57 { graphMap = emptyUFM }
60 -- | Modify the finite map holding the nodes in the graph.
62 :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color))
63 -> Graph k cls color -> Graph k cls color
65 graphMapModify f graph
66 = graph { graphMap = f (graphMap graph) }
71 -- Represents a thing that can conflict with another thing.
72 -- For the register allocater the nodes represent registers.
76 -- | A unique identifier for this node.
79 -- | The class of this node,
80 -- determines the set of colors that can be used.
83 -- | The color of this node, if any.
84 , nodeColor :: Maybe color
86 -- | Neighbors which must be colored differently to this node.
87 , nodeConflicts :: UniqSet k
89 -- | Colors that cannot be used by this node.
90 , nodeExclusions :: UniqSet color
92 -- | Colors that this node would prefer to be, in decending order.
93 , nodePreference :: [color]
95 -- | Neighbors that this node would like to be colored the same as.
96 , nodeCoalesce :: UniqSet k }
100 newNode :: k -> cls -> Node k cls color
105 , nodeColor = Nothing
106 , nodeConflicts = emptyUniqSet
107 , nodeExclusions = emptyUniqSet
108 , nodePreference = []
109 , nodeCoalesce = emptyUniqSet }