GraphOps
Description
Basic operations on graphs.
- 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
addNode :: Uniquable k => k -> Node k cls color -> Graph k cls color -> Graph k cls colorSource
Add a node to the graph, linking up its edges
delNode :: (Uniquable k, Outputable k) => k -> Graph k cls color -> Maybe (Graph k cls color)Source
Delete a node and all its edges from the graph.
getNode :: Uniquable k => Graph k cls color -> k -> Node k cls colorSource
Get a node from the graph, throwing an error if it's not there
lookupNode :: Uniquable k => Graph k cls color -> k -> Maybe (Node k cls color)Source
Lookup a node from the graph.
modNode :: Uniquable k => (Node k cls color -> Node k cls color) -> k -> Graph k cls color -> Maybe (Graph k cls color)Source
Modify a node in the graph. returns Nothing if the node isn't present.
union :: Uniquable k => Graph k cls color -> Graph k cls color -> Graph k cls colorSource
Union two graphs together.
addConflict :: Uniquable k => (k, cls) -> (k, cls) -> Graph k cls color -> Graph k cls colorSource
Add a conflict between nodes to the graph, creating the nodes required. Conflicts are virtual regs which need to be colored differently.
delConflict :: Uniquable k => k -> k -> Graph k cls color -> Maybe (Graph k cls color)Source
Delete a conflict edge. k1 -> k2 returns Nothing if the node isn't in the graph
addConflicts :: Uniquable k => UniqSet k -> (k -> cls) -> Graph k cls color -> Graph k cls colorSource
Add some conflicts to the graph, creating nodes if required. All the nodes in the set are taken to conflict with each other.
addCoalesce :: Uniquable k => (k, cls) -> (k, cls) -> Graph k cls color -> Graph k cls colorSource
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.
delCoalesce :: Uniquable k => k -> k -> Graph k cls color -> Maybe (Graph k cls color)Source
Delete a coalescence edge (k1 -> k2) from the graph.
addExclusion :: (Uniquable k, Uniquable color) => k -> (k -> cls) -> color -> Graph k cls color -> Graph k cls colorSource
Add an exclusion to the graph, creating nodes if required. These are extra colors that the node cannot use.
addExclusions :: (Uniquable k, Uniquable color) => k -> (k -> cls) -> [color] -> Graph k cls color -> Graph k cls colorSource
addPreference :: Uniquable k => (k, cls) -> color -> Graph k cls color -> Graph k cls colorSource
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.
Arguments
| :: (Uniquable k, Ord k, Eq cls, Outputable k) | |
| => Bool | If True, coalesce nodes even if this might make the graph less colorable (aggressive coalescing) |
| -> Triv k cls color | |
| -> Graph k cls color | |
| -> (k, k) | keys of the nodes to be coalesced |
| -> (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
Arguments
| :: (Uniquable k, Ord k, Eq cls, Outputable k) | |
| => Bool | If True, coalesce nodes even if this might make the graph less colorable (aggressive coalescing) |
| -> 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.
Arguments
| :: Uniquable k | |
| => k | key of the node to freeze |
| -> Graph k cls color | the graph |
| -> Graph k cls color | graph with that node frozen |
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.
freezeOneInGraph :: (Uniquable k, Outputable k) => Graph k cls color -> (Graph k cls color, Bool)Source
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/non-move nodes.
freezeAllInGraph :: (Uniquable k, Outputable k) => Graph k cls color -> Graph k cls colorSource
Freeze all the nodes in the graph for debugging the iterative allocator.
scanGraph :: Uniquable k => (Node k cls color -> Bool) -> Graph k cls color -> [Node k cls color]Source
Find all the nodes in the graph that meet some criteria
setColor :: Uniquable k => k -> color -> Graph k cls color -> Graph k cls colorSource
Set the color of a certain node
Arguments
| :: (Uniquable k, Outputable k, Eq color) | |
| => SDoc | extra debugging info to display on error |
| -> Bool | whether this graph is supposed to be colored. |
| -> Graph k cls color | graph to validate |
| -> Graph k cls color | validated graph |
validate the internal structure of a graph all its edges should point to valid nodes If they don't then throw an error