Avoid coalescing nodes in the register conflict graph if the
new node will not be trivially colorable. Also remove the
front end aggressive coalescing pass.
For typical Haskell code the graph coloring allocator now does
about as well as the linear allocator.
For code with a large amount of register pressure it does much
better, but takes longer.
For SHA1.lhs from darcs on x86
spills reloads reg-reg-moves
inserted inserted left in code compile-time
linear 1068 1311 229 7.69(s)
graph 387 902 340 16.12(s)
| Opt_D_dump_asm
| Opt_D_dump_asm_native
| Opt_D_dump_asm_liveness
| Opt_D_dump_asm
| Opt_D_dump_asm_native
| Opt_D_dump_asm_liveness
- | Opt_D_dump_asm_coalesce
| Opt_D_dump_asm_regalloc
| Opt_D_dump_asm_regalloc_stages
| Opt_D_dump_asm_conflicts
| Opt_D_dump_asm_regalloc
| Opt_D_dump_asm_regalloc_stages
| Opt_D_dump_asm_conflicts
, ( "ddump-asm", setDumpFlag Opt_D_dump_asm)
, ( "ddump-asm-native", setDumpFlag Opt_D_dump_asm_native)
, ( "ddump-asm-liveness", setDumpFlag Opt_D_dump_asm_liveness)
, ( "ddump-asm", setDumpFlag Opt_D_dump_asm)
, ( "ddump-asm-native", setDumpFlag Opt_D_dump_asm_native)
, ( "ddump-asm-liveness", setDumpFlag Opt_D_dump_asm_liveness)
- , ( "ddump-asm-coalesce", setDumpFlag Opt_D_dump_asm_coalesce)
- , ( "ddump-asm-regalloc", setDumpFlag Opt_D_dump_asm_regalloc)
, ( "ddump-asm-conflicts", setDumpFlag Opt_D_dump_asm_conflicts)
, ( "ddump-asm-conflicts", setDumpFlag Opt_D_dump_asm_conflicts)
+ , ( "ddump-asm-regalloc", setDumpFlag Opt_D_dump_asm_regalloc)
, ( "ddump-asm-regalloc-stages",
setDumpFlag Opt_D_dump_asm_regalloc_stages)
, ( "ddump-asm-stats", setDumpFlag Opt_D_dump_asm_stats)
, ( "ddump-asm-regalloc-stages",
setDumpFlag Opt_D_dump_asm_regalloc_stages)
, ( "ddump-asm-stats", setDumpFlag Opt_D_dump_asm_stats)
emptyUFM
$ map RealReg allocatableRegs
emptyUFM
$ map RealReg allocatableRegs
- -- aggressively coalesce moves between virtual regs
- let (coalesced, usCoalesce)
- = {-# SCC "regCoalesce" #-}
- initUs usLive $ regCoalesce withLiveness
-
- dumpIfSet_dyn dflags
- Opt_D_dump_asm_coalesce "Reg-Reg moves coalesced"
- (vcat $ map ppr coalesced)
-
-- if any of these dump flags are turned on we want to hang on to
-- intermediate structures in the allocator - otherwise tell the
-- allocator to ditch them early so we don't end up creating space leaks.
-- if any of these dump flags are turned on we want to hang on to
-- intermediate structures in the allocator - otherwise tell the
-- allocator to ditch them early so we don't end up creating space leaks.
-- graph coloring register allocation
let ((alloced, regAllocStats), usAlloc)
= {-# SCC "regAlloc(color)" #-}
-- graph coloring register allocation
let ((alloced, regAllocStats), usAlloc)
= {-# SCC "regAlloc(color)" #-}
$ Color.regAlloc
generateRegAllocStats
alloc_regs
(mkUniqSet [0..maxSpillSlots])
$ Color.regAlloc
generateRegAllocStats
alloc_regs
(mkUniqSet [0..maxSpillSlots])
-- dump out what happened during register allocation
dumpIfSet_dyn dflags
-- dump out what happened during register allocation
dumpIfSet_dyn dflags
= let
-- do aggressive coalesing on the graph
(graph_coalesced, rsCoalesce)
= 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)
-- run the scanner to slurp out all the trivially colorable nodes
(ksTriv, ksProblems)
--
coalesceGraph
:: (Uniquable k, Ord k, Eq cls, Outputable k)
--
coalesceGraph
:: (Uniquable k, Ord k, Eq cls, Outputable k)
+ => Triv k cls color
+ -> Graph k cls color
-> (Graph k cls color, [(k, k)])
-> (Graph k cls color, [(k, k)])
+coalesceGraph triv graph
= let
-- find all the nodes that have coalescence edges
cNodes = filter (\node -> not $ isEmptyUniqSet (nodeCoalesce node))
= let
-- find all the nodes that have coalescence edges
cNodes = filter (\node -> not $ isEmptyUniqSet (nodeCoalesce node))
-- do the coalescing, returning the new graph and a list of pairs of keys
-- that got coalesced together.
(graph', mPairs)
-- do the coalescing, returning the new graph and a list of pairs of keys
-- that got coalesced together.
(graph', mPairs)
- = mapAccumL coalesceNodes graph cList
+ = mapAccumL (coalesceNodes False triv) graph cList
in (graph', catMaybes mPairs)
in (graph', catMaybes mPairs)
coalesceNodes
:: (Uniquable k, Ord k, Eq cls, Outputable k)
coalesceNodes
:: (Uniquable k, Ord k, Eq cls, Outputable k)
+ => Bool -- ^ If True, coalesce nodes even if this might make the graph
+ -- less colorable (aggressive coalescing)
+ -> Triv k cls color
+ -> Graph k cls color
-> (k, k) -- ^ keys of the nodes to be coalesced
-> (Graph k cls color, Maybe (k, k))
-> (k, k) -- ^ keys of the nodes to be coalesced
-> (Graph k cls color, Maybe (k, k))
-coalesceNodes graph (k1, k2)
+coalesceNodes aggressive triv graph (k1, k2)
| (kMin, kMax) <- if k1 < k2
then (k1, k2)
else (k2, k1)
| (kMin, kMax) <- if k1 < k2
then (k1, k2)
else (k2, k1)
- -- nodes must be in the graph
- , Just nMin <- lookupNode graph kMin
- , Just nMax <- lookupNode graph kMax
+ -- the nodes being coalesced must be in the graph
+ , Just nMin <- lookupNode graph kMin
+ , Just nMax <- lookupNode graph kMax
- -- can't coalesce conflicting nodes
+ -- can't coalesce conflicting modes
, not $ elementOfUniqSet kMin (nodeConflicts nMax)
, not $ elementOfUniqSet kMax (nodeConflicts nMin)
, not $ elementOfUniqSet kMin (nodeConflicts nMax)
, not $ elementOfUniqSet kMax (nodeConflicts nMin)
- = coalesceNodes' graph kMin kMax nMin nMax
-
-
+ = coalesceNodes_merge aggressive triv graph kMin kMax nMin nMax
- -- one of the nodes wasn't in the graph anymore
+ -- don't do the coalescing after all
| otherwise
= (graph, Nothing)
| otherwise
= (graph, Nothing)
-coalesceNodes' graph kMin kMax nMin nMax
+coalesceNodes_merge aggressive triv graph kMin kMax nMin nMax
-- sanity checks
| nodeClass nMin /= nodeClass nMax
-- sanity checks
| nodeClass nMin /= nodeClass nMax
`delOneFromUniqSet` kMax
}
`delOneFromUniqSet` kMax
}
- -- delete the old nodes from the graph and add the new one
- graph' = addNode kMin node
- $ delNode kMin
+ in coalesceNodes_check aggressive triv graph kMin kMax node
+
+coalesceNodes_check aggressive triv graph kMin kMax node
+
+ -- Unless we're coalescing aggressively, if the result node is not trivially
+ -- colorable then don't do the coalescing.
+ | not aggressive
+ , not $ triv (nodeClass node) (nodeConflicts node) (nodeExclusions node)
+ = (graph, Nothing)
+
+ | otherwise
+ = let -- delete the old nodes from the graph and add the new one
+ graph' = addNode kMin node
+ $ delNode kMin