[GHC] #8456: Control flow optimisations duplicate blocks

[GHC]

#8456: Control flow optimisations duplicate blocks
--------------------------------------------+------------------------------
        Reporter:  jstolarek                |            Owner:
            Type:  bug                      |           Status:  new
        Priority:  highest                  |        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:
--------------------------------------------+------------------------------
Changes (by simonmar):

 * owner:  jstolarek =>
 * priority:  high => highest
 * status:  closed => new
 * resolution:  fixed =>


Comment:

 I looked at this patch, I think we need to revisit it.

 {{{
          | CmmBranch b' <- last
          , Just blk' <- mapLookup b' blocks
          , hasOnePredecessor b'
          , hasNotBeenMappedTo b' shortcut_map
 }}}

 In particular, the `hasNotBeenMappedTo` here is very suspicious:

 {{{
           hasNotBeenMappedTo :: BlockId -> BlockEnv BlockId -> Bool
           hasNotBeenMappedTo b successor_map = mapMember b successor_map
 }}}

 It looks like the condition is reversed.  Indeed, fixing this makes the
 performance problem go away, probably because this condition is preventing
 any block concatenation from happening at all, which means later phases
 are seeing a lot more code than they would if concatenation was happening.

 What's more, even when it is reversed, I don't think this condition does
 what you want, because what you actually wanted to do was look in the
 range of the map, not the domain.  And we don't want to do that, because
 searching the range of a map is O(n) operation, leaving the whole pass
 O(n^2).

 I suggest just deleting this condition.  If the block is in the
 `shortcut_map`, then it will also have another predecessor (the call
 itself), and we won't attempt to concatenate with it.

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