-- Colors in graphviz graphs could be nicer.
--
+{-# 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
+
module RegAllocColor (
regAlloc,
regDotColor
import qualified GraphColor as Color
import RegLiveness
import RegSpill
+import RegSpillClean
import RegAllocStats
import MachRegs
import MachInstrs
-import RegCoalesce
import PprMach
import UniqSupply
-- | The top level of the graph coloring register allocator.
--
regAlloc
- :: UniqFM (UniqSet Reg) -- ^ the registers we can use for allocation
- -> UniqSet Int -- ^ the set of available spill slots.
- -> [LiveCmmTop] -- ^ code annotated with liveness information.
+ :: Bool -- ^ whether to generate RegAllocStats, or not.
+ -> UniqFM (UniqSet Reg) -- ^ the registers we can use for allocation
+ -> UniqSet Int -- ^ the set of available spill slots.
+ -> [LiveCmmTop] -- ^ code annotated with liveness information.
-> UniqSM
- ( [NatCmmTop] -- ^ code with registers allocated.
- , [RegAllocStats] ) -- ^ stats for each stage of allocation
+ ( [NatCmmTop] -- ^ code with registers allocated.
+ , [RegAllocStats] ) -- ^ stats for each stage of allocation
-regAlloc regsFree slotsFree code
+regAlloc dump regsFree slotsFree code
= do
(code_final, debug_codeGraphs, graph_final)
- <- regAlloc_spin 0 trivColorable regsFree slotsFree [] code
+ <- regAlloc_spin dump 0 trivColorable regsFree slotsFree [] code
return ( code_final
- , debug_codeGraphs )
+ , reverse debug_codeGraphs )
-regAlloc_spin (spinCount :: Int) triv regsFree slotsFree debug_codeGraphs code
+regAlloc_spin dump (spinCount :: Int) triv regsFree slotsFree debug_codeGraphs code
= do
-- check that we're not running off down the garden path.
when (spinCount > maxSpinCount)
-- build a conflict graph from the code.
graph <- buildGraph code
- -- build a map of how many instructions each reg lives for
- -- this lazy, it won't be computed unless we need to spill
+ -- build a map of how many instructions each reg lives for.
+ -- this is lazy, it won't be computed unless we need to spill
let fmLife = plusUFMs_C (\(r1, l1) (r2, l2) -> (r1, l1 + l2))
$ map lifetimeCount code
+ -- record startup state
+ let stat1 =
+ if spinCount == 0
+ then Just $ RegAllocStatsStart
+ { raLiveCmm = code
+ , raGraph = graph
+ , raLifetimes = fmLife }
+ else Nothing
+
+
-- the function to choose regs to leave uncolored
let spill = chooseSpill_maxLife fmLife
-- try and color the graph
- let (graph_colored, rsSpill)
+ let (graph_colored, rsSpill, rmCoalesce)
= Color.colorGraph regsFree triv spill graph
+ -- rewrite regs in the code that have been coalesced
+ let patchF reg = case lookupUFM rmCoalesce reg of
+ Just reg' -> reg'
+ Nothing -> reg
+ let code_coalesced
+ = map (patchEraseLive patchF) code
+
+
-- see if we've found a coloring
if isEmptyUniqSet rsSpill
then do
-- patch the registers using the info in the graph
- let code_patched = map (patchRegsFromGraph graph_colored) code
+ let code_patched = map (patchRegsFromGraph graph_colored) code_coalesced
+
+ -- clean out unneeded SPILL/RELOADs
+ let code_spillclean = map cleanSpills code_patched
+
+ -- strip off liveness information
let code_nat = map stripLive code_patched
+
+ -- rewrite SPILL/REALOAD pseudos into real instructions
+ let spillNatTop = mapGenBlockTop spillNatBlock
+ let code_final = map spillNatTop code_nat
-- record what happened in this stage for debugging
let stat =
RegAllocStatsColored
- { raLiveCmm = code
- , raGraph = graph_colored
- , raPatchedCmm = code_patched
- , raLifetimes = fmLife }
-
- return ( code_nat
- , debug_codeGraphs ++ [stat]
+ { raGraph = graph_colored
+ , raCoalesced = rmCoalesce
+ , raPatched = code_patched
+ , raSpillClean = code_spillclean
+ , raFinal = code_final
+ , raSRMs = foldl addSRM (0, 0, 0) $ map countSRMs code_spillclean }
+
+ return ( code_final
+ , if dump
+ then [stat] ++ maybeToList stat1 ++ debug_codeGraphs
+ else []
, graph_colored)
else do
-- spill the uncolored regs
(code_spilled, slotsFree', spillStats)
- <- regSpill code slotsFree rsSpill
+ <- regSpill code_coalesced slotsFree rsSpill
-- recalculate liveness
let code_nat = map stripLive code_spilled
-- record what happened in this stage for debugging
let stat =
RegAllocStatsSpill
- { raLiveCmm = code_spilled
- , raGraph = graph_colored
+ { raGraph = graph_colored
+ , raCoalesced = rmCoalesce
, raSpillStats = spillStats
- , raLifetimes = fmLife }
+ , raLifetimes = fmLife
+ , raSpilled = code_spilled }
-- try again
- regAlloc_spin (spinCount + 1) triv regsFree slotsFree'
- (debug_codeGraphs ++ [stat])
+ regAlloc_spin dump (spinCount + 1) triv regsFree slotsFree'
+ (if dump
+ then [stat] ++ maybeToList stat1 ++ debug_codeGraphs
+ else [])
code_relive
buildGraph code
= do
- -- Add the reg-reg conflicts to the graph
- let conflictSets = unionManyBags (map slurpConflicts code)
- let graph_conflict = foldrBag graphAddConflictSet Color.initGraph conflictSets
+ -- Slurp out the conflicts and reg->reg moves from this code
+ let (conflictList, moveList) =
+ unzip $ map slurpConflicts code
+
+ let conflictBag = unionManyBags conflictList
+ let moveBag = unionManyBags moveList
+ -- Add the reg-reg conflicts to the graph
+ let graph_conflict = foldrBag graphAddConflictSet Color.initGraph conflictBag
-- Add the coalescences edges to the graph.
- let coalesce = unionManyBags (map slurpJoinMovs code)
- let graph_coalesce = foldrBag graphAddCoalesce graph_conflict coalesce
+ let graph_coalesce = foldrBag graphAddCoalesce graph_conflict moveBag
- return $ graph_coalesce
+ return graph_coalesce
-- | Add some conflict edges to the graph.
--- Conflicts between virtual and real regs are recorded as exlusions.
+-- Conflicts between virtual and real regs are recorded as exclusions.
--
graphAddConflictSet
:: UniqSet Reg
in graph2
--- | Add some coalesences edges to the graph
+-- | Add some coalesence edges to the graph
-- Coalesences between virtual and real regs are recorded as preferences.
--
graphAddCoalesce