never executed always true always false

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