[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 jstolarek):

 Simon Marlow says:

  I wonder if the right way to fix these issues is to not shortcut or
 concat a jump when the jump destination has not already been processed.
 This might be easier than keeping track of the predecessor counts
 accurately, and should give results that are just as good.

 Let me see if I understand this correctly. Consider again the same code as
 in the ticket report:

 {{{
 L1: goto L2
 L2: whatever
 L3: goto L1
 }}}

 According to your proposal L3 will not process its destination - L1 -
 because L1 itself has not been processed (we process blocks from the
 back). L1 however will concatenate with L2, causing L2 to be unreachable
 and removed from the graph later on:

 {{{
 L1: whatever
 L2: whatever -- UNREACHABLE, eliminated later
 L3: goto L1
 }}}

 Now consider this:

 {{{
 L1: goto L2
 L2: whatever
 L3: goto L1
 L4: goto L2
 }}}

 L3 will not shortcut its destination, because it has not been processed
 yet. L1 will not concatenate L2, because L2 has two predecessors. So this
 graph will not be modified in any way. However, using current algorithm
 (and providing that we correctly keep track of predecessors) we will
 optimise that graph to:

 {{{
 L1: goto L2 -- UNREACHABLE, eliminated later
 L2: whatever
 L3: goto L2
 L4: goto L2
 }}}

 Do I got this right?

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