compiler/nativeGen/GraphBase.hs

   1
   2 -- | Types for the general graph colorer.
   3 {-# OPTIONS_GHC -w #-}
   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
   8 -- for details
   9
  10 module GraphBase (
  11         Triv,
  12         Graph (..),
  13         initGraph,
  14         graphMapModify,
  15
  16         Node  (..),     newNode,
  17 )
  18
  19
  20 where
  21
  22 import UniqSet
  23 import UniqFM
  24
  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.
  28 --
  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.
  34 --
  35 --      for details, see  "A Generalised Algorithm for Graph-Coloring Register Allocation"
  36 --                              Smith, Ramsey, Holloway - PLDI 2004.
  37 --
  38 type Triv k cls color
  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.
  42         -> Bool
  43
  44
  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..
  48 --
  49 data Graph k cls color
  50         = Graph {
  51         -- | All active nodes in the graph.
  52           graphMap              :: UniqFM (Node k cls color)  }
  53
  54 -- | An empty graph.
  55 initGraph
  56         = Graph
  57         { graphMap              = emptyUFM }
  58
  59
  60 -- | Modify the finite map holding the nodes in the graph.
  61 graphMapModify
  62         :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color))
  63         -> Graph k cls color -> Graph k cls color
  64
  65 graphMapModify f graph
  66         = graph { graphMap      = f (graphMap graph) }
  67
  68
  69
  70 -- | Graph nodes.
  71 --      Represents a thing that can conflict with another thing.
  72 --      For the register allocater the nodes represent registers.
  73 --
  74 data Node k cls color
  75         = Node {
  76         -- | A unique identifier for this node.
  77           nodeId                :: k
  78
  79         -- | The class of this node,
  80         --      determines the set of colors that can be used.
  81         , nodeClass             :: cls
  82
  83         -- | The color of this node, if any.
  84         , nodeColor             :: Maybe color
  85
  86         -- | Neighbors which must be colored differently to this node.
  87         , nodeConflicts         :: UniqSet k
  88
  89         -- | Colors that cannot be used by this node.
  90         , nodeExclusions        :: UniqSet color
  91
  92         -- | Colors that this node would prefer to be, in decending order.
  93         , nodePreference        :: [color]
  94
  95         -- | Neighbors that this node would like to be colored the same as.
  96         , nodeCoalesce          :: UniqSet k }
  97
  98
  99 -- | An empty node.
 100 newNode :: k -> cls -> Node k cls color
 101 newNode k cls
 102         = Node
 103         { nodeId                = k
 104         , nodeClass             = cls
 105         , nodeColor             = Nothing
 106         , nodeConflicts         = emptyUniqSet
 107         , nodeExclusions        = emptyUniqSet
 108         , nodePreference        = []
 109         , nodeCoalesce          = emptyUniqSet }
 110
 111
 112
 113