compiler/nativeGen/GraphBase.hs

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