Tune coalescing in non-iterative register allocator

If iterative coalescing isn't turned on, then do a single aggressive
coalescing pass for the first build/color cycle and then back off to
conservative coalescing for subseqent passes.

Aggressive coalescing is a cheap way to eliminate lots of the reg-reg
moves, but it can make the graph less colorable - if we turn it on
for every pass then allocation for code with a large amount of register
pressure (ie SHA1) doesn't converge in a sensible number of cycles.

diff --git a/compiler/nativeGen/RegAllocColor.hs b/compiler/nativeGen/RegAllocColor.hs
index 40dd64c..21d7ed1 100644 (file)
--- a/compiler/nativeGen/RegAllocColor.hs
+++ b/compiler/nativeGen/RegAllocColor.hs
@@ -1,8 +1,6 @@
 -- | Graph coloring register allocator.
 --
--- TODO:
---     The function that choosing the potential spills could be a bit cleverer.
---     Colors in graphviz graphs could be nicer.
+-- TODO: The colors in graphviz graphs for x86_64 and ppc could be nicer.
 --
 {-# OPTIONS -fno-warn-missing-signatures #-}
 
@@ -81,20 +79,8 @@ regAlloc_spin dflags (spinCount :: Int) triv regsFree slotsFree debug_codeGraphs
                                                $ uniqSetToList $ unionManyUniqSets $ eltsUFM regsFree)
                $$ text "slotsFree   = " <> ppr (sizeUniqSet slotsFree))
 
-
-       -- Brig's algorithm does reckless coalescing for all but the first allocation stage
-       --      Doing this seems to reduce the number of reg-reg moves, but at the cost-
-       --      of creating more spills. Probably better just to stick with conservative 
-       --      coalescing in Color.colorGraph for now.
-       --
-       {- code_coalesced1      <- if (spinCount > 0) 
-                               then regCoalesce code
-                               else return code -}
-
-       let code_coalesced1     = code
-
        -- build a conflict graph from the code.
-       graph           <- {-# SCC "BuildGraph" #-} buildGraph code_coalesced1
+       graph           <- {-# SCC "BuildGraph" #-} buildGraph code
 
        -- VERY IMPORTANT:
        --      We really do want the graph to be fully evaluated _before_ we start coloring.
@@ -107,7 +93,7 @@ regAlloc_spin dflags (spinCount :: Int) triv regsFree slotsFree debug_codeGraphs
        -- build a map of the cost of spilling each instruction
        --      this will only actually be computed if we have to spill something.
        let spillCosts  = foldl' plusSpillCostInfo zeroSpillCostInfo
-                       $ map slurpSpillCostInfo code_coalesced1
+                       $ map slurpSpillCostInfo code
 
        -- the function to choose regs to leave uncolored
        let spill       = chooseSpill spillCosts
@@ -126,14 +112,15 @@ regAlloc_spin dflags (spinCount :: Int) triv regsFree slotsFree debug_codeGraphs
                        = {-# SCC "ColorGraph" #-}
                           Color.colorGraph
                                (dopt Opt_RegsIterative dflags)
+                               spinCount
                                regsFree triv spill graph
 
        -- rewrite regs in the code that have been coalesced
        let patchF reg  = case lookupUFM rmCoalesce reg of
                                Just reg'       -> patchF reg'
                                Nothing         -> reg
-       let code_coalesced2
-                       = map (patchEraseLive patchF) code_coalesced1
+       let code_coalesced
+                       = map (patchEraseLive patchF) code
 
 
        -- see if we've found a coloring
@@ -148,7 +135,7 @@ regAlloc_spin dflags (spinCount :: Int) triv regsFree slotsFree debug_codeGraphs
                                else graph_colored
 
                -- patch the registers using the info in the graph
-               let code_patched        = map (patchRegsFromGraph graph_colored_lint) code_coalesced2
+               let code_patched        = map (patchRegsFromGraph graph_colored_lint) code_coalesced
 
                -- clean out unneeded SPILL/RELOADs
                let code_spillclean     = map cleanSpills code_patched
@@ -195,7 +182,7 @@ regAlloc_spin dflags (spinCount :: Int) triv regsFree slotsFree debug_codeGraphs
 
                -- spill the uncolored regs
                (code_spilled, slotsFree', spillStats)
-                       <- regSpill code_coalesced2 slotsFree rsSpill
+                       <- regSpill code_coalesced slotsFree rsSpill
 
                -- recalculate liveness
                let code_nat    = map stripLive code_spilled

diff --git a/compiler/utils/GraphColor.hs b/compiler/utils/GraphColor.hs
index bd777b7..66eb0a1 100644 (file)
--- a/compiler/utils/GraphColor.hs
+++ b/compiler/utils/GraphColor.hs
@@ -39,6 +39,7 @@ colorGraph
           , Eq 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.
@@ -49,14 +50,22 @@ colorGraph
           , UniqFM  k )                -- map of regs (r1 -> r2) that were coaleced
                                        --       r1 should be replaced by r2 in the source
 
-colorGraph iterative colors triv spill graph0
+colorGraph iterative spinCount colors triv spill graph0
  = let
-       -- If we're not doing iterative coalescing then just do a conservative
-       --      coalescing stage at the front.
+       -- 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 not iterative
-                       then coalesceGraph True triv graph0
-                       else (graph0, [])
+        = 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)

diff --git a/compiler/utils/GraphOps.hs b/compiler/utils/GraphOps.hs
index 972dd07..a711df9 100644 (file)
--- a/compiler/utils/GraphOps.hs
+++ b/compiler/utils/GraphOps.hs
@@ -1,7 +1,5 @@
 -- | Basic operations on graphs.
 --
---     TODO: refine coalescing crieteria
-
 {-# OPTIONS -fno-warn-missing-signatures #-}
 
 module GraphOps (