[GHC] #8456: Control flow optimisations duplicate blocks

[GHC]

#8456: Control flow optimisations duplicate blocks
--------------------------------------------+------------------------------
        Reporter:  jstolarek                |            Owner:  jstolarek
            Type:  bug                      |           Status:  new
        Priority:  high                     |        Milestone:
       Component:  Compiler                 |          Version:  7.7
      Resolution:                           |         Keywords:
Operating System:  Unknown/Multiple         |     Architecture:
 Type of failure:  Runtime performance bug  |  Unknown/Multiple
       Test Case:                           |       Difficulty:  Unknown
        Blocking:  8275                     |       Blocked By:
                                            |  Related Tickets:
--------------------------------------------+------------------------------

Comment (by simonpj):

 About `CmmContFlowOpt`, it looks to me as if there may be other bugs.
 When deciding in `shouldConcatWith` whether the destination block is
 small, we look in `blocks`; but those are the original un-rewritten
 blocks, and we might have already rewritten the destination block.

 I think it might be better to consider this algorithm as something that
 rewrites a full graph to a graph (both represented as usual as a finite
 map).  The algorithm takes a post-order DFS list of block-ids (not
 blocks!) which is used as the list of blocks to consider, one by one.
 Look up that block id to find the block, consider whether to rewrite it;
 if so, rewrite it and replace it in the finite map, and move on to the
 next one.

 You are right that rewriting changes predecessor counts, so you'd need to
 maintain that alongside the current graph.  An easy approximiation would
 be this: keep a set of block-ids that are referenced exactly once, and
 delete things from it when necessary.  (But never add anything.)  That
 would be an approximation, but probably a reasonable one.

 I don't agree with Simon M that "not shortcut or concat backward jumps"
 will give results that are at least as good.  Imagine a backward goto to a
 goto!

 Thanks for working on this Jan

 Simon

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8456#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler