compiler/utils/GraphColor.hs

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