X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FnativeGen%2FGraphColor.hs;h=307803a988109660ca35c224bb2f1b1c7e4436c5;hb=b8a64b8ec9cd3d8f6e3f23e44312c4903eccac45;hp=ecebf2767350d183ca0e2772c4412ed7cbe00539;hpb=a7f409e855291efece19970927156fae4e527b6e;p=ghc-hetmet.git diff --git a/compiler/nativeGen/GraphColor.hs b/compiler/nativeGen/GraphColor.hs index ecebf27..307803a 100644 --- a/compiler/nativeGen/GraphColor.hs +++ b/compiler/nativeGen/GraphColor.hs @@ -3,13 +3,7 @@ -- This is a generic graph coloring library, abstracted over the type of -- the node keys, nodes and colors. -- - -{-# OPTIONS -w #-} --- The above warning supression flag is a temporary kludge. --- While working on this module you are encouraged to remove it and fix --- any warnings in the module. See --- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings --- for details +{-# OPTIONS -fno-warn-missing-signatures #-} module GraphColor ( module GraphBase, @@ -44,7 +38,8 @@ colorGraph :: ( Uniquable k, Uniquable cls, Uniquable color , Eq color, Eq cls, Ord k , Outputable k, Outputable cls, Outputable color) - => UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class). + => Bool -- ^ whether to do iterative coalescing + -> 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. @@ -54,25 +49,46 @@ colorGraph , UniqFM k ) -- map of regs (r1 -> r2) that were coaleced -- r1 should be replaced by r2 in the source -colorGraph colors triv spill graph0 +colorGraph iterative colors triv spill graph0 = let - -- do aggressive coalesing on the graph - (graph_coalesced, rsCoalesce) - = coalesceGraph triv graph0 + -- if we're not doing iterative coalescing, then just do a single coalescing + -- pass at the front. This won't be as good but should still eat up a + -- lot of the reg-reg moves. + (graph_coalesced, kksCoalesce1) + = if not iterative + then coalesceGraph False triv graph0 + else (graph0, []) -- run the scanner to slurp out all the trivially colorable nodes - (ksTriv, ksProblems) - = colorScan colors triv spill [] emptyUniqSet graph_coalesced + -- (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_coalesced ksTriv + = assignColors colors graph_scan_coalesced ksTriv -- try and color the problem nodes - (graph_prob, ksNoColor) = assignColors colors graph_triv (uniqSetToList ksProblems) + -- 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 wrong + -- 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 @@ -82,31 +98,120 @@ colorGraph colors triv spill graph0 $$ dotGraph (\x -> text "white") triv graph1) -} else ( graph_prob - , mkUniqSet ksNoColor - , listToUFM rsCoalesce) + , mkUniqSet ksNoColor -- the nodes that didn't color (spills) + , if iterative + then (listToUFM kksCoalesce2) + else (listToUFM kksCoalesce1)) -colorScan colors triv spill safe prob graph - -- empty graphs are easy to color. +-- | 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 resonably 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 color) + => 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 iterative triv spill graph + ksTriv ksSpill kksCoalesce + + -- if the graph is empty then we're done | isNullUFM $ graphMap graph - = (safe, prob) - - -- Try and find a trivially colorable node. - | Just node <- find (\node -> triv (nodeClass node) - (nodeConflicts node) - (nodeExclusions node)) - $ eltsUFM $ graphMap graph - , k <- nodeId node - = colorScan colors triv spill - (k : safe) prob (delNode k graph) + = (ksTriv, ksSpill, 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 + , graph3 <- foldr (\k g -> let Just g' = delNode k g + in g') + graph ksTrivFound + + = colorScan_spin iterative triv spill graph3 + (ksTrivFound ++ ksTriv) + ksSpill + kksCoalesce + + -- Coalesce: + -- If we're doing iterative coalescing and no triv nodes are avaliable + -- then it's type for a coalescing pass. + | iterative + = case coalesceGraph False triv graph of + + -- we were able to coalesce something + -- go back and see if this frees up more nodes to be trivially colorable. + (graph2, kksCoalesceFound @(_:_)) + -> colorScan_spin iterative triv spill graph2 + ksTriv ksSpill (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 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 - -- There was no trivially colorable node, - -- Choose one to potentially leave uncolored. We /might/ be able to find - -- a color for this later on, but no guarantees. - | k <- spill graph - = colorScan colors triv spill - safe (addOneToUniqSet prob k) (delNode k graph) - -- | Try to assign a color to all these nodes. @@ -121,7 +226,7 @@ assignColors assignColors colors graph ks = assignColors' colors graph [] ks - where assignColors' colors graph prob [] + where assignColors' _ graph prob [] = (graph, prob) assignColors' colors graph prob (k:ks) @@ -147,8 +252,6 @@ assignColors colors graph ks -- taking into account preferences, neighbors and exclusions. -- returns Nothing if no color can be assigned to this node. -- --- TODO: avoid using the prefs of the neighbors, if at all possible. --- selectColor :: ( Uniquable k, Uniquable cls, Uniquable color, Eq color) => UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class). @@ -176,28 +279,50 @@ selectColor colors graph u $ catMaybes $ map nodeColor nsConflicts - -- colors that are still ok + -- 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 - -- we got one of our preferences, score! + -- 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 : rest <- uniqSetToList 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 : rest <- uniqSetToList colors_ok + , c : _ <- uniqSetToList colors_ok = Just c - -- leave this node uncolored + -- no colors were available for us this time. + -- looks like we're going around the loop again.. | otherwise = Nothing