Add graph coloring register allocator.

[ghc-hetmet.git] / compiler / nativeGen / GraphBase.hs

diff --git a/compiler/nativeGen/GraphBase.hs b/compiler/nativeGen/GraphBase.hs
new file mode 100644 (file)
index 0000000..efc59b9
--- /dev/null
+++ b/compiler/nativeGen/GraphBase.hs
@@ -0,0 +1,106 @@
+
+-- | Types for the general graph colorer.
+module GraphBase (
+       Triv,
+       Graph (..),
+       initGraph,
+       graphMapModify,
+
+       Node  (..),     newNode,
+)
+       
+
+where
+
+import UniqSet
+import UniqFM
+
+-- | A fn to check if a node is trivially colorable
+--     For graphs who's color classes are disjoint then a node is 'trivially colorable'
+--     when it has less neighbors and exclusions than available colors for that node.
+--
+--     For graph's who's color classes overlap, ie some colors alias other colors, then
+--     this can be a bit more tricky. There is a general way to calculate this, but 
+--     it's likely be too slow for use in the code. The coloring algorithm takes
+--     a canned function which can be optimised by the user to be specific to the 
+--     specific graph being colored.
+--
+--     for details, see  "A Generalised Algorithm for Graph-Coloring Register Allocation"
+--                             Smith, Ramsey, Holloway - PLDI 2004.
+--
+type Triv k cls color
+       =  cls                  -- ^ the class of the node we're trying to color.
+       -> UniqSet k            -- ^ the node's neighbors.
+       -> UniqSet color        -- ^ the node's exclusions.
+       -> Bool         
+
+
+-- | The Interference graph.
+--     There used to be more fields, but they were turfed out in a previous revision.
+--     maybe we'll want more later..
+--
+data Graph k cls color
+       = Graph { 
+       -- | All active nodes in the graph.
+         graphMap              :: UniqFM (Node k cls color)  }
+
+-- | An empty graph.   
+initGraph
+       = Graph
+       { graphMap              = emptyUFM }
+
+
+-- | Modify the finite map holding the nodes in the graph.
+graphMapModify 
+       :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color))
+       -> Graph k cls color -> Graph k cls color
+
+graphMapModify f graph
+       = graph { graphMap      = f (graphMap graph) }
+       
+               
+
+-- | Graph nodes.
+--     Represents a thing that can conflict with another thing.
+--     For the register allocater the nodes represent registers.
+--
+data Node k cls color
+       = Node {        
+       -- | A unique identifier for this node.
+         nodeId                :: k
+
+       -- | The class of this node,
+       --      determines the set of colors that can be used.
+       , nodeClass             :: cls
+
+       -- | The color of this node, if any.
+       , nodeColor             :: Maybe color
+
+       -- | Neighbors which must be colored differently to this node.
+       , nodeConflicts         :: UniqSet k
+
+       -- | Colors that cannot be used by this node.
+       , nodeExclusions        :: UniqSet color        
+
+       -- | Colors that this node would prefer to be, in decending order.
+       , nodePreference        :: [color]  
+
+       -- | Neighbors that this node would like to be colored the same as.
+       , nodeCoalesce          :: UniqSet k }
+
+
+-- | An empty node.
+newNode :: k -> cls -> Node k cls color
+newNode k cls
+       = Node
+       { nodeId                = k
+       , nodeClass             = cls
+       , nodeColor             = Nothing
+       , nodeConflicts         = emptyUniqSet
+       , nodeExclusions        = emptyUniqSet
+       , nodePreference        = [] 
+       , nodeCoalesce          = emptyUniqSet }
+
+
+
+