[GHC] #14684: combineIdenticalAlts is only partially implemented

[GHC]

#14684: combineIdenticalAlts is only partially implemented
-------------------------------------+-------------------------------------
        Reporter:  mpickering        |                Owner:  sjakobi
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.2.2
      Resolution:                    |             Keywords:  newcomer
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4419
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by sjakobi):

 Replying to [comment:8 simonpj]:
 > It's invisible in the message above, but I think this commit is only on
 branch `wip/T14684`.  Is that what you intended?  Or did you mean to
 commit to HEAD?

 We agreed that the new most-common-RHS code should be moved into `-O2`
 before it can land in `master`.

 BTW, regarding [comment:2 your comment above]:
 > Fortunately, we now have `TrieMap.CoreMap`, an efficient finite map
 whose keys are `CoreExprs`. Using this I think we can efficiently ask (as
 we iterate oover the alternatives) "have I seen this RHS in an earlier
 alternative?". More advanced: find the RHS that occurs most often. Take
 care that in the common case the RHSs are (a) large and (b) different,
 then the test does not exhaustively traverse the RHSs; just looks far
 enough to establish they are different.

 In the common case you describe, my code will still insert every
 alternative into the `CoreMap`. I haven't been able to find a less
 expensive way to establish that the alternatives are all different, but
 I'd love to hear about any ideas!

 I have also found `CSE.combineAlts`:

 {{{
 {- Note [Combine case alternatives]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 combineAlts is just a more heavyweight version of the use of
 combineIdenticalAlts in SimplUtils.prepareAlts.  The basic idea is
 to transform

     DEFAULT -> e1
     K x     -> e1
     W y z   -> e2
 ===>
    DEFAULT -> e1
    W y z   -> e2

 In the simplifier we use cheapEqExpr, because it is called a lot.
 But here in CSE we use the full eqExpr.  After all, two alternatives
 usually
 differ near the root, so it probably isn't expensive to compare the full
 alternative.  It seems like the same kind of thing that CSE is supposed
 to be doing, which is why I put it here.
 }}}

 Should `combineAlts` get the same optimization as `combineIdenticalAlts`?
 Might `combineAlts` even be the ''better'' place to apply the
 optimization?

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