X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FnativeGen%2FGraphColor.hs;h=a0c54e4694493c97d1d6991427337da933b669d2;hb=94368126b8933a5a198bf5c59599f621087fbace;hp=bdd708aed708743b829acf7309c7f4b28bddcaab;hpb=17b297d97d327620ed6bfab942f8992b2446f1bf;p=ghc-hetmet.git diff --git a/compiler/nativeGen/GraphColor.hs b/compiler/nativeGen/GraphColor.hs index bdd708a..a0c54e4 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_GHC -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/WorkingConventions#Warnings --- for details +{-# OPTIONS -fno-warn-missing-signatures #-} module GraphColor ( module GraphBase, @@ -41,25 +35,38 @@ import Data.List -- the stack (ie in reverse order) and assigning them colors different to their neighbors. -- colorGraph - :: ( Uniquable k, Uniquable cls, Uniquable color, Eq color + :: ( 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). -> 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. + + -> ( 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 coaleced + -- r1 should be replaced by r2 in the source colorGraph colors triv spill graph0 - = let -- run the scanner to slurp out all the trivially colorable nodes - (ksTriv, ksProblems) = colorScan colors triv spill [] emptyUniqSet graph0 + = let + -- do aggressive coalesing on the graph + (graph_coalesced, rsCoalesce) + = coalesceGraph triv graph0 + + -- run the scanner to slurp out all the trivially colorable nodes + (ksTriv, ksProblems) + = colorScan triv spill graph_coalesced -- color the trivially colorable nodes - (graph1, ksNoTriv) = assignColors colors graph0 ksTriv + -- as the keys were added to the front of the list while they were scanned, + -- this colors them in the reverse order they were found, as required by the algorithm. + (graph_triv, ksNoTriv) + = assignColors colors graph_coalesced ksTriv -- try and color the problem nodes - (graph2, ksNoColor) = assignColors colors graph1 (uniqSetToList ksProblems) - + (graph_prob, ksNoColor) = assignColors colors graph_triv ksProblems + -- if the trivially colorable nodes didn't color then something is wrong -- with the provided triv function. in if not $ null ksNoTriv @@ -69,9 +76,95 @@ colorGraph colors triv spill graph0 $$ text "ksNoTriv = " <> ppr ksNoTriv $$ empty $$ dotGraph (\x -> text "white") triv graph1) -} - else (graph2, mkUniqSet ksNoColor) - + + else ( graph_prob + , mkUniqSet ksNoColor + , listToUFM rsCoalesce) + +-- | 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. +-- +colorScan + :: ( Uniquable k, Uniquable cls, Uniquable color) + => 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]) -- triv colorable, problem nodes + + +colorScan triv spill graph + = colorScan' triv spill graph + [] [] + [] + (eltsUFM $ graphMap graph) + +-- we've reached the end of the candidates list +colorScan' triv spill graph + ksTriv ksTrivFound + ksSpill + [] + + -- if the graph is empty then we're done + | isNullUFM $ graphMap graph + = (ksTrivFound ++ ksTriv, ksSpill) + + -- if we haven't found a trivially colorable node then we'll have to + -- choose a spill candidate and leave it uncolored + | [] <- ksTrivFound + , kSpill <- spill graph -- choose a spill candiate + , graph' <- delNode kSpill graph -- remove it from the graph + , nsRest' <- eltsUFM $ graphMap graph' -- graph has changed, so get new node list + + = colorScan' triv spill graph' + ksTriv ksTrivFound + (kSpill : ksSpill) + nsRest' + + -- we're at the end of the candidates list but we've found some triv nodes + -- along the way. We can delete them from the graph and go back for more. + | graph' <- foldr delNode graph ksTrivFound + , nsRest' <- eltsUFM $ graphMap graph' + + = colorScan' triv spill graph' + (ksTrivFound ++ ksTriv) [] + ksSpill + nsRest' + +-- check if the current node is triv colorable +colorScan' triv spill graph + ksTriv ksTrivFound + ksSpill + (node : nsRest) + + -- node is trivially colorable + -- add it to the found nodes list and carry on. + | k <- nodeId node + , triv (nodeClass node) (nodeConflicts node) (nodeExclusions node) + + = colorScan' triv spill graph + ksTriv (k : ksTrivFound) + ksSpill + nsRest + + -- node wasn't trivially colorable, skip over it and look in the rest of the list + | otherwise + = colorScan' triv spill graph + ksTriv ksTrivFound + ksSpill + nsRest + +{- -- This is cute and easy to understand, but too slow.. BL 2007/09 + colorScan colors triv spill safe prob graph -- empty graphs are easy to color. @@ -93,7 +186,7 @@ colorScan colors triv spill safe prob graph | k <- spill graph = colorScan colors triv spill safe (addOneToUniqSet prob k) (delNode k graph) - +-} -- | Try to assign a color to all these nodes. @@ -109,7 +202,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) @@ -135,8 +228,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). @@ -152,7 +243,7 @@ selectColor colors graph u Just colors_avail = lookupUFM colors (nodeClass node) - -- colors we can't use because they're already being used + -- find colors we can't use because they're already being used -- by a node that conflicts with this one. Just nsConflicts = sequence @@ -164,28 +255,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