compiler/nativeGen/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 -- | 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
  37
  38
  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)  }
  47
  48 -- | An empty graph.
  49 initGraph :: Graph k cls color
  50 initGraph
  51         = Graph
  52         { graphMap              = emptyUFM }
  53
  54
  55 -- | Modify the finite map holding the nodes in the graph.
  56 graphMapModify
  57         :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color))
  58         -> Graph k cls color -> Graph k cls color
  59
  60 graphMapModify f graph
  61         = graph { graphMap      = f (graphMap graph) }
  62
  63
  64
  65 -- | Graph nodes.
  66 --      Represents a thing that can conflict with another thing.
  67 --      For the register allocater the nodes represent registers.
  68 --
  69 data Node k cls color
  70         = Node {
  71         -- | A unique identifier for this node.
  72           nodeId                :: k
  73
  74         -- | The class of this node,
  75         --      determines the set of colors that can be used.
  76         , nodeClass             :: cls
  77
  78         -- | The color of this node, if any.
  79         , nodeColor             :: Maybe color
  80
  81         -- | Neighbors which must be colored differently to this node.
  82         , nodeConflicts         :: UniqSet k
  83
  84         -- | Colors that cannot be used by this node.
  85         , nodeExclusions        :: UniqSet color
  86
  87         -- | Colors that this node would prefer to be, in decending order.
  88         , nodePreference        :: [color]
  89
  90         -- | Neighbors that this node would like to be colored the same as.
  91         , nodeCoalesce          :: UniqSet k }
  92
  93
  94 -- | An empty node.
  95 newNode :: k -> cls -> Node k cls color
  96 newNode k cls
  97         = Node
  98         { nodeId                = k
  99         , nodeClass             = cls
 100         , nodeColor             = Nothing
 101         , nodeConflicts         = emptyUniqSet
 102         , nodeExclusions        = emptyUniqSet
 103         , nodePreference        = []
 104         , nodeCoalesce          = emptyUniqSet }
 105
 106
 107
 108