[GHC] #8456: Control flow optimisations duplicate blocks

[GHC]

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

 * owner:   => jstolarek


Comment:

 > It looks like the condition is reversed
 Yes, you're right.


 > what you actually wanted to do was look in the range of the map, not the
 domain.
 Argh... I don't know why I assumed that it looks in the range :-/


 > searching the range of a map is O(n) operation
 According to documentation of !IntMap `lookup` has O(min(n,W)) complexity:

  Many operations have a worst-case complexity of O(min(n,W)). This means
 that the operation can become linear in the number of elements with a
 maximum of W -- the number of bits in an Int (32 or 64).

 I'm not sure if I understand correctly, but this means that for n < W
 `lookup` is linear, right?

 > 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.
 Not any more - see third guard and `update_cont` function. I wanted to
 avoid this kind of hidden invariants, because they often cause us trouble.

 My idea here would be to replace

 {{{
 , hasNotBeenMappedTo b' shortcut_map
 }}}

 with

 {{{
 , Nothing <- mapLookup b' shortcut_map
 }}}

 Would that be acceptable? I think that for the most time we keep a small
 number of entries in `shortcut_map`, so `lookup` will be linear, but then
 again if these numbers are small it shouldn't be that much of a problem?

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