| |||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||

Description | |||||||||||||||||||||||||||||||||||||||||||||

Basic operations on graphs. | |||||||||||||||||||||||||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||

Documentation | |||||||||||||||||||||||||||||||||||||||||||||

addNode :: Uniquable k => k -> Node k cls color -> Graph k cls color -> Graph k cls color | |||||||||||||||||||||||||||||||||||||||||||||

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) | |||||||||||||||||||||||||||||||||||||||||||||

Delete a node and all its edges from the graph. | |||||||||||||||||||||||||||||||||||||||||||||

getNode :: Uniquable k => Graph k cls color -> k -> Node k cls color | |||||||||||||||||||||||||||||||||||||||||||||

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) | |||||||||||||||||||||||||||||||||||||||||||||

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) | |||||||||||||||||||||||||||||||||||||||||||||

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

size :: Uniquable k => Graph k cls color -> Int | |||||||||||||||||||||||||||||||||||||||||||||

Get the size of the graph, O(n) | |||||||||||||||||||||||||||||||||||||||||||||

union :: Uniquable k => Graph k cls color -> Graph k cls color -> Graph k cls color | |||||||||||||||||||||||||||||||||||||||||||||

Union two graphs together. | |||||||||||||||||||||||||||||||||||||||||||||

addConflict :: Uniquable k => (k, cls) -> (k, cls) -> Graph k cls color -> Graph k cls color | |||||||||||||||||||||||||||||||||||||||||||||

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) | |||||||||||||||||||||||||||||||||||||||||||||

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 color | |||||||||||||||||||||||||||||||||||||||||||||

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 color | |||||||||||||||||||||||||||||||||||||||||||||

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) | |||||||||||||||||||||||||||||||||||||||||||||

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 color | |||||||||||||||||||||||||||||||||||||||||||||

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

addPreference :: Uniquable k => (k, cls) -> color -> Graph k cls color -> Graph k cls color | |||||||||||||||||||||||||||||||||||||||||||||

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. | |||||||||||||||||||||||||||||||||||||||||||||

coalesceNodes | |||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||

coalesceGraph | |||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||

freezeNode | |||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||

freezeOneInGraph :: (Uniquable k, Outputable k) => Graph k cls color -> (Graph k cls color, Bool) | |||||||||||||||||||||||||||||||||||||||||||||

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 color | |||||||||||||||||||||||||||||||||||||||||||||

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] | |||||||||||||||||||||||||||||||||||||||||||||

Find all the nodes in the graph that meet some criteria | |||||||||||||||||||||||||||||||||||||||||||||

setColor :: Uniquable k => k -> color -> Graph k cls color -> Graph k cls color | |||||||||||||||||||||||||||||||||||||||||||||

Set the color of a certain node | |||||||||||||||||||||||||||||||||||||||||||||

validateGraph | |||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||

slurpNodeConflictCount | |||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 2.4.2 |