-- | Graph Coloring.
-- This is a generic graph coloring library, abstracted over the type of
-- the node keys, nodes and colors.
--
module GraphColor (
module GraphBase,
module GraphOps,
module GraphPpr,
colorGraph
)
where
import GhcPrelude
import GraphBase
import GraphOps
import GraphPpr
import Unique
import UniqFM
import UniqSet
import Outputable
import Data.Maybe
import Data.List
-- | Try to color a graph with this set of colors.
-- Uses Chaitin's algorithm to color the graph.
-- The graph is scanned for nodes which are deamed 'trivially colorable'. These nodes
-- are pushed onto a stack and removed from the graph.
-- Once this process is complete the graph can be colored by removing nodes from
-- the stack (ie in reverse order) and assigning them colors different to their neighbors.
--
colorGraph
:: ( Uniquable k, Uniquable cls, Uniquable color
, Eq cls, Ord k
, Outputable k, Outputable cls, Outputable color)
=> Bool -- ^ whether to do iterative coalescing
-> Int -- ^ how many times we've tried to color this graph so far.
-> UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class).
-> Triv k cls color -- ^ fn to decide whether a node is trivially colorable.
-> (Graph k cls color -> k) -- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.
-> Graph k cls color -- ^ the graph to color.
-> ( Graph k cls color -- the colored graph.
, UniqSet k -- the set of nodes that we couldn't find a color for.
, UniqFM k ) -- map of regs (r1 -> r2) that were coalesced
-- r1 should be replaced by r2 in the source
colorGraph iterative spinCount colors triv spill graph0
= let
-- If we're not doing iterative coalescing then do an aggressive coalescing first time
-- around and then conservative coalescing for subsequent passes.
--
-- Aggressive coalescing is a quick way to get rid of many reg-reg moves. However, if
-- there is a lot of register pressure and we do it on every round then it can make the
-- graph less colorable and prevent the algorithm from converging in a sensible number
-- of cycles.
--
(graph_coalesced, kksCoalesce1)
= if iterative
then (graph0, [])
else if spinCount == 0
then coalesceGraph True triv graph0
else coalesceGraph False triv graph0
-- run the scanner to slurp out all the trivially colorable nodes
-- (and do coalescing if iterative coalescing is enabled)
(ksTriv, ksProblems, kksCoalesce2)
= colorScan iterative triv spill graph_coalesced
-- If iterative coalescing is enabled, the scanner will coalesce the graph as does its business.
-- We need to apply all the coalescences found by the scanner to the original
-- graph before doing assignColors.
--
-- Because we've got the whole, non-pruned graph here we turn on aggressive coalescing
-- to force all the (conservative) coalescences found during scanning.
--
(graph_scan_coalesced, _)
= mapAccumL (coalesceNodes True triv) graph_coalesced kksCoalesce2
-- color the trivially colorable nodes
-- during scanning, keys of triv nodes were added to the front of the list as they were found
-- this colors them in the reverse order, as required by the algorithm.
(graph_triv, ksNoTriv)
= assignColors colors graph_scan_coalesced ksTriv
-- try and color the problem nodes
-- problem nodes are the ones that were left uncolored because they weren't triv.
-- theres a change we can color them here anyway.
(graph_prob, ksNoColor)
= assignColors colors graph_triv ksProblems
-- if the trivially colorable nodes didn't color then something is probably wrong
-- with the provided triv function.
--
in if not $ null ksNoTriv
then pprPanic "colorGraph: trivially colorable nodes didn't color!" -- empty
( empty
$$ text "ksTriv = " <> ppr ksTriv
$$ text "ksNoTriv = " <> ppr ksNoTriv
$$ text "colors = " <> ppr colors
$$ empty
$$ dotGraph (\_ -> text "white") triv graph_triv)
else ( graph_prob
, mkUniqSet ksNoColor -- the nodes that didn't color (spills)
, if iterative
then (listToUFM kksCoalesce2)
else (listToUFM kksCoalesce1))
-- | Scan through the conflict graph separating out trivially colorable and
-- potentially uncolorable (problem) nodes.
--
-- Checking whether a node is trivially colorable or not is a reasonably expensive operation,
-- so after a triv node is found and removed from the graph it's no good to return to the 'start'
-- of the graph and recheck a bunch of nodes that will probably still be non-trivially colorable.
--
-- To ward against this, during each pass through the graph we collect up a list of triv nodes
-- that were found, and only remove them once we've finished the pass. The more nodes we can delete
-- at once the more likely it is that nodes we've already checked will become trivially colorable
-- for the next pass.
--
-- TODO: add work lists to finding triv nodes is easier.
-- If we've just scanned the graph, and removed triv nodes, then the only
-- nodes that we need to rescan are the ones we've removed edges from.
colorScan
:: ( Uniquable k, Uniquable cls, Uniquable color
, Ord k, Eq cls
, Outputable k, Outputable cls)
=> Bool -- ^ whether to do iterative coalescing
-> Triv k cls color -- ^ fn to decide whether a node is trivially colorable
-> (Graph k cls color -> k) -- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.
-> Graph k cls color -- ^ the graph to scan
-> ([k], [k], [(k, k)]) -- triv colorable nodes, problem nodes, pairs of nodes to coalesce
colorScan iterative triv spill graph
= colorScan_spin iterative triv spill graph [] [] []
colorScan_spin
:: ( Uniquable k, Uniquable cls, Uniquable color
, Ord k, Eq cls
, Outputable k, Outputable cls)
=> Bool
-> Triv k cls color
-> (Graph k cls color -> k)
-> Graph k cls color
-> [k]
-> [k]
-> [(k, k)]
-> ([k], [k], [(k, k)])
colorScan_spin iterative triv spill graph
ksTriv ksSpill kksCoalesce
-- if the graph is empty then we're done
| isNullUFM $ graphMap graph
= (ksTriv, ksSpill, reverse kksCoalesce)
-- Simplify:
-- Look for trivially colorable nodes.
-- If we can find some then remove them from the graph and go back for more.
--
| nsTrivFound@(_:_)
<- scanGraph (\node -> triv (nodeClass node) (nodeConflicts node) (nodeExclusions node)
-- for iterative coalescing we only want non-move related
-- nodes here
&& (not iterative || isEmptyUniqSet (nodeCoalesce node)))
$ graph
, ksTrivFound <- map nodeId nsTrivFound
, graph2 <- foldr (\k g -> let Just g' = delNode k g
in g')
graph ksTrivFound
= colorScan_spin iterative triv spill graph2
(ksTrivFound ++ ksTriv)
ksSpill
kksCoalesce
-- Coalesce:
-- If we're doing iterative coalescing and no triv nodes are available
-- then it's time for a coalescing pass.
| iterative
= case coalesceGraph False triv graph of
-- we were able to coalesce something
-- go back to Simplify and see if this frees up more nodes to be trivially colorable.
(graph2, kksCoalesceFound@(_:_))
-> colorScan_spin iterative triv spill graph2
ksTriv ksSpill (reverse kksCoalesceFound ++ kksCoalesce)
-- Freeze:
-- nothing could be coalesced (or was triv),
-- time to choose a node to freeze and give up on ever coalescing it.
(graph2, [])
-> case freezeOneInGraph graph2 of
-- we were able to freeze something
-- hopefully this will free up something for Simplify
(graph3, True)
-> colorScan_spin iterative triv spill graph3
ksTriv ksSpill kksCoalesce
-- we couldn't find something to freeze either
-- time for a spill
(graph3, False)
-> colorScan_spill iterative triv spill graph3
ksTriv ksSpill kksCoalesce
-- spill time
| otherwise
= colorScan_spill iterative triv spill graph
ksTriv ksSpill kksCoalesce
-- Select:
-- we couldn't find any triv nodes or things to freeze or coalesce,
-- and the graph isn't empty yet.. We'll have to choose a spill
-- candidate and leave it uncolored.
--
colorScan_spill
:: ( Uniquable k, Uniquable cls, Uniquable color
, Ord k, Eq cls
, Outputable k, Outputable cls)
=> Bool
-> Triv k cls color
-> (Graph k cls color -> k)
-> Graph k cls color
-> [k]
-> [k]
-> [(k, k)]
-> ([k], [k], [(k, k)])
colorScan_spill iterative triv spill graph
ksTriv ksSpill kksCoalesce
= let kSpill = spill graph
Just graph' = delNode kSpill graph
in colorScan_spin iterative triv spill graph'
ksTriv (kSpill : ksSpill) kksCoalesce
-- | Try to assign a color to all these nodes.
assignColors
:: ( Uniquable k, Uniquable cls, Uniquable color
, Outputable cls)
=> UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class).
-> Graph k cls color -- ^ the graph
-> [k] -- ^ nodes to assign a color to.
-> ( Graph k cls color -- the colored graph
, [k]) -- the nodes that didn't color.
assignColors colors graph ks
= assignColors' colors graph [] ks
where assignColors' _ graph prob []
= (graph, prob)
assignColors' colors graph prob (k:ks)
= case assignColor colors k graph of
-- couldn't color this node
Nothing -> assignColors' colors graph (k : prob) ks
-- this node colored ok, so do the rest
Just graph' -> assignColors' colors graph' prob ks
assignColor colors u graph
| Just c <- selectColor colors graph u
= Just (setColor u c graph)
| otherwise
= Nothing
-- | Select a color for a certain node
-- taking into account preferences, neighbors and exclusions.
-- returns Nothing if no color can be assigned to this node.
--
selectColor
:: ( Uniquable k, Uniquable cls, Uniquable color
, Outputable cls)
=> UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class).
-> Graph k cls color -- ^ the graph
-> k -- ^ key of the node to select a color for.
-> Maybe color
selectColor colors graph u
= let -- lookup the node
Just node = lookupNode graph u
-- lookup the available colors for the class of this node.
colors_avail
= case lookupUFM colors (nodeClass node) of
Nothing -> pprPanic "selectColor: no colors available for class " (ppr (nodeClass node))
Just cs -> cs
-- find colors we can't use because they're already being used
-- by a node that conflicts with this one.
Just nsConflicts
= sequence
$ map (lookupNode graph)
$ nonDetEltsUniqSet
$ nodeConflicts node
-- See Note [Unique Determinism and code generation]
colors_conflict = mkUniqSet
$ catMaybes
$ map nodeColor nsConflicts
-- the prefs of our neighbors
colors_neighbor_prefs
= mkUniqSet
$ concat $ map nodePreference nsConflicts
-- colors that are still valid for us
colors_ok_ex = minusUniqSet colors_avail (nodeExclusions node)
colors_ok = minusUniqSet colors_ok_ex colors_conflict
-- the colors that we prefer, and are still ok
colors_ok_pref = intersectUniqSets
(mkUniqSet $ nodePreference node) colors_ok
-- the colors that we could choose while being nice to our neighbors
colors_ok_nice = minusUniqSet
colors_ok colors_neighbor_prefs
-- the best of all possible worlds..
colors_ok_pref_nice
= intersectUniqSets
colors_ok_nice colors_ok_pref
-- make the decision
chooseColor
-- everyone is happy, yay!
| not $ isEmptyUniqSet colors_ok_pref_nice
, c : _ <- filter (\x -> elementOfUniqSet x colors_ok_pref_nice)
(nodePreference node)
= Just c
-- we've got one of our preferences
| not $ isEmptyUniqSet colors_ok_pref
, c : _ <- filter (\x -> elementOfUniqSet x colors_ok_pref)
(nodePreference node)
= Just c
-- it wasn't a preference, but it was still ok
| not $ isEmptyUniqSet colors_ok
, c : _ <- nonDetEltsUniqSet colors_ok
-- See Note [Unique Determinism and code generation]
= Just c
-- no colors were available for us this time.
-- looks like we're going around the loop again..
| otherwise
= Nothing
in chooseColor