move generic graph-colouring code into util

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

diff --git a/compiler/nativeGen/GraphBase.hs b/compiler/nativeGen/GraphBase.hs
deleted file mode 100644 (file)
index 04eda96..0000000
--- a/compiler/nativeGen/GraphBase.hs
+++ /dev/null
@@ -1,111 +0,0 @@
-
--- | 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 k cls color
-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 }
-
-
-
-
-