From fff4dee0483eda0b675057f8259a161ff16467f4 Mon Sep 17 00:00:00 2001 From: "Ben.Lippmeier@anu.edu.au" Date: Mon, 17 Sep 2007 13:26:14 +0000 Subject: [PATCH] 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. --- compiler/nativeGen/RegAllocColor.hs | 29 ++++++++--------------------- compiler/utils/GraphColor.hs | 21 +++++++++++++++------ compiler/utils/GraphOps.hs | 2 -- 3 files changed, 23 insertions(+), 29 deletions(-) diff --git a/compiler/nativeGen/RegAllocColor.hs b/compiler/nativeGen/RegAllocColor.hs index 40dd64c..21d7ed1 100644 --- 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 --- 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 --- 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 ( -- 1.7.10.4