ghc-6.12.3: The GHC APISource codeContentsIndex
GraphBase
Description
Types for the general graph colorer.
Synopsis
type Triv k cls color = cls -> UniqSet k -> UniqSet color -> Bool
data Graph k cls color = Graph {
graphMap :: UniqFM (Node k cls color)
}
initGraph :: Graph k cls color
graphMapModify :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color)) -> Graph k cls color -> Graph k cls color
data Node k cls color = Node {
nodeId :: k
nodeClass :: cls
nodeColor :: Maybe color
nodeConflicts :: UniqSet k
nodeExclusions :: UniqSet color
nodePreference :: [color]
nodeCoalesce :: UniqSet k
}
newNode :: k -> cls -> Node k cls color
Documentation
type Triv k cls color = cls -> UniqSet k -> UniqSet color -> BoolSource

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.

data Graph k cls color Source
The Interference graph. There used to be more fields, but they were turfed out in a previous revision. maybe we'll want more later..
Constructors
Graph
graphMap :: UniqFM (Node k cls color)All active nodes in the graph.
initGraph :: Graph k cls colorSource
An empty graph.
graphMapModify :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color)) -> Graph k cls color -> Graph k cls colorSource
Modify the finite map holding the nodes in the graph.
data Node k cls color Source
Graph nodes. Represents a thing that can conflict with another thing. For the register allocater the nodes represent registers.
Constructors
Node
nodeId :: kA unique identifier for this node.
nodeClass :: clsThe class of this node, determines the set of colors that can be used.
nodeColor :: Maybe colorThe color of this node, if any.
nodeConflicts :: UniqSet kNeighbors which must be colored differently to this node.
nodeExclusions :: UniqSet colorColors that cannot be used by this node.
nodePreference :: [color]Colors that this node would prefer to be, in decending order.
nodeCoalesce :: UniqSet kNeighbors that this node would like to be colored the same as.
newNode :: k -> cls -> Node k cls colorSource
An empty node.
Produced by Haddock version 2.6.1