Improve GraphColor.colorScan
authorBen.Lippmeier@anu.edu.au <unknown>
Wed, 5 Sep 2007 16:44:01 +0000 (16:44 +0000)
committerBen.Lippmeier@anu.edu.au <unknown>
Wed, 5 Sep 2007 16:44:01 +0000 (16:44 +0000)
commit1dd44153dac634be2e6af2b68eff2ceb74a8c64c
tree7e1e66402a71d08b7e323b78091ece752ebc9f30
parent8155ba5048245c895718b5570ed015756b80073f
Improve GraphColor.colorScan

Testing whether a node in the conflict graph is trivially
colorable (triv) is still a somewhat expensive operation.

When we find a triv node during scanning, even though we remove
it and its edges from the graph, this is unlikely to to make the
nodes we've just scanned become triv - so there's not much point
re-scanning them right away.

Scanning now takes place in passes. We scan the whole graph for
triv nodes and remove all the ones found in a batch before rescanning
old nodes.

Register allocation for SHA1.lhs now takes (just) 40% of total
compile time with -O2 -fregs-graph on x86
compiler/nativeGen/AsmCodeGen.lhs
compiler/nativeGen/GraphColor.hs
compiler/nativeGen/RegAllocColor.hs