compiler/utils/GraphBase.hs

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