


Description 
Basic operations on graphs.


Synopsis 

addNode :: Uniquable k => k > Node k cls color > Graph k cls color > Graph k cls color   delNode :: (Uniquable k, Outputable k) => k > Graph k cls color > Maybe (Graph k cls color)   getNode :: Uniquable k => Graph k cls color > k > Node k cls color   lookupNode :: Uniquable k => Graph k cls color > k > Maybe (Node k cls color)   modNode :: Uniquable k => (Node k cls color > Node k cls color) > k > Graph k cls color > Maybe (Graph k cls color)   size :: Uniquable k => Graph k cls color > Int   union :: Uniquable k => Graph k cls color > Graph k cls color > Graph k cls color   addConflict :: Uniquable k => (k, cls) > (k, cls) > Graph k cls color > Graph k cls color   delConflict :: Uniquable k => k > k > Graph k cls color > Maybe (Graph k cls color)   addConflicts :: Uniquable k => UniqSet k > (k > cls) > Graph k cls color > Graph k cls color   addCoalesce :: Uniquable k => (k, cls) > (k, cls) > Graph k cls color > Graph k cls color   delCoalesce :: Uniquable k => k > k > Graph k cls color > Maybe (Graph k cls color)   addExclusion :: (Uniquable k, Uniquable color) => k > (k > cls) > color > Graph k cls color > Graph k cls color   addExclusions :: (Uniquable k, Uniquable color) => k > (k > cls) > [color] > Graph k cls color > Graph k cls color   addPreference :: Uniquable k => (k, cls) > color > Graph k cls color > Graph k cls color   coalesceNodes :: (Uniquable k, Ord k, Eq cls, Outputable k) => Bool > Triv k cls color > Graph k cls color > (k, k) > (Graph k cls color, Maybe (k, k))   coalesceGraph :: (Uniquable k, Ord k, Eq cls, Outputable k) => Bool > Triv k cls color > Graph k cls color > (Graph k cls color, [(k, k)])   freezeNode :: Uniquable k => k > Graph k cls color > Graph k cls color   freezeOneInGraph :: (Uniquable k, Outputable k) => Graph k cls color > (Graph k cls color, Bool)   freezeAllInGraph :: (Uniquable k, Outputable k) => Graph k cls color > Graph k cls color   scanGraph :: Uniquable k => (Node k cls color > Bool) > Graph k cls color > [Node k cls color]   setColor :: Uniquable k => k > color > Graph k cls color > Graph k cls color   validateGraph :: (Uniquable k, Outputable k, Eq color) => SDoc > Bool > Graph k cls color > Graph k cls color   slurpNodeConflictCount :: Uniquable k => Graph k cls color > UniqFM (Int, Int) 


Documentation 


Add a node to the graph, linking up its edges



Delete a node and all its edges from the graph.



Get a node from the graph, throwing an error if it's not there



Lookup a node from the graph.



Modify a node in the graph.
returns Nothing if the node isn't present.



Get the size of the graph, O(n)



Union two graphs together.



Add a conflict between nodes to the graph, creating the nodes required.
Conflicts are virtual regs which need to be colored differently.



Delete a conflict edge. k1 > k2
returns Nothing if the node isn't in the graph



Add some conflicts to the graph, creating nodes if required.
All the nodes in the set are taken to conflict with each other.



Add a coalescence edge to the graph, creating nodes if requried.
It is considered adventageous to assign the same color to nodes in a coalesence.



Delete a coalescence edge (k1 > k2) from the graph.



Add an exclusion to the graph, creating nodes if required.
These are extra colors that the node cannot use.





Add a color preference to the graph, creating nodes if required.
The most recently added preference is the most prefered.
The algorithm tries to assign a node it's prefered color if possible.



:: (Uniquable k, Ord k, Eq cls, Outputable k)   => Bool   > Triv k cls color   > Graph k cls color  keys of the nodes to be coalesced
 > (k, k)   > (Graph k cls color, Maybe (k, k))   Coalesce this pair of nodes unconditionally / agressively.
The resulting node is the one with the least key.
returns: Just the pair of keys if the nodes were coalesced
the second element of the pair being the least one
Nothing if either of the nodes weren't in the graph




:: (Uniquable k, Ord k, Eq cls, Outputable k)   => Bool   > Triv k cls color   > Graph k cls color   > (Graph k cls color, [(k, k)])   Do agressive coalescing on this graph.
returns the new graph and the list of pairs of nodes that got coaleced together.
for each pair, the resulting node will have the least key and be second in the pair.




:: Uniquable k   => k  the graph
 > Graph k cls color  graph with that node frozen
 > Graph k cls color   Freeze a node
This is for the iterative coalescer.
By freezing a node we give up on ever coalescing it.
Move all its coalesce edges into the frozen set  and update
back edges from other nodes.




Freeze one node in the graph
This if for the iterative coalescer.
Look for a move related node of low degree and freeze it.
We probably don't need to scan the whole graph looking for the node of absolute
lowest degree. Just sample the first few and choose the one with the lowest
degree out of those. Also, we don't make any distinction between conflicts of different
classes.. this is just a heuristic, after all.
IDEA: freezing a node might free it up for Simplify.. would be good to check for triv
right here, and add it to a worklist if known triv/nonmove nodes.



Freeze all the nodes in the graph
for debugging the iterative allocator.



Find all the nodes in the graph that meet some criteria



Set the color of a certain node



:: (Uniquable k, Outputable k, Eq color)   => SDoc  whether this graph is supposed to be colored.
 > Bool  graph to validate
 > Graph k cls color  validated graph
 > Graph k cls color   validate the internal structure of a graph
all its edges should point to valid nodes
If they don't then throw an error




:: Uniquable k   => Graph k cls color  (conflict neighbours, num nodes with that many conflicts)
 > UniqFM (Int, Int)   Slurp out a map of how many nodes had a certain number of conflict neighbours



Produced by Haddock version 2.6.0 