[GHC] #15696: Derived Ord instance for enumerations with more than 8 elements seems to be incorrect

[GHC]

#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  patch
        Priority:  highest           |            Milestone:  8.6.2
       Component:  Compiler          |              Version:  8.6.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Incorrect result  |  Unknown/Multiple
  at runtime                         |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D5196,
       Wiki Page:                    |  Phab:D5201
-------------------------------------+-------------------------------------

Comment (by osa1):

 So we mention this "optimisation" without describing what it is, and I
 realized
 that that may cause some confusion so let's define it.

 By "optimisation" I mean that in some cases when compiling `dataToTag#` we
 can
 avoid entering the argument, because we already know enough about it.

 - In compile time we sometimes know that the argument is definitely some
   constructor `C`. For example, in the example in comment:43, we know that
 `f`
   is `T2`, so we should be able to compile `dataToTag# f` to `1#`. Another
   example is `case foo of X -> ... dataToTag# foo ...`.

   Note that we currently (with GHC 8.6 and HEAD) don't do this for `f` in
   comment:43, even with -O2. However with Phab:D5201 `f` in comment:43 is
   optimised to `1#` in Cmm level. The case expression is optimised in all
   versions. (both diffs preserve Core transformations and rules, so
 anything
   optimised at Core level by GHC HEAD will still be optimised)

   (I don't know why `dataToTag# f` in comment:43 is not optimised in Core
 level,
   but perhaps that can be tracked in another ticket)

 - In compile time we sometimes know that a value is already evaluated, but
 we
   don't know specifics (i.e. which constructor it is). For example, in a
 pattern
   match, a variable binding a strict field should be evaluated. Another
 example
   is `let !foo = f x in ... dataToTag# foo ...`. In these cases we should
 be
   able to avoid entering the argument.

   There are a few problems with this:

   First, as #14677 demonstrates, we sometimes fail to tag values properly.
 So
   for example if a strict field's type is small, we still can't look at
 tag
   bits, we need to read the info table.

   Second, the analysis for this should be more strict than the current
   `exprIsHNF` or `isEvaldUnfolding` (see Note [Always introduce case
 around
   dataToTag# arg] in comment:30 for what goes wrong otherwise). However,
 we
   currently don't have an analysis for this, and I don't know how easy
 it'd be
   to implement in Core (remember that we don't know about CAFs in Core
 until
   CorePrep, and this information is necessary for this analysis). I don't
 know
   if going into the trouble of implementing a new analysis in Core just
 for
   this purpose is worth it.

 - For all other cases we need to enter the argument in runtime. If the
 argument
   is a small type then we can look at the tag bits, otherwise we read the
 info
   table.

 In other words, case (1) is when we know the constructor of the argument
 in
 compile time, case (2) is when we don't know the constructor, but we know
 that
 the argument is already evaluated, case (3) is when we don't know anything
 about
 the argument.

 Looking at the tag bits in (3) is currently only done by Phab:D5201, but
 it
 could be easily added to other implementations.

 (2) is currently only done by GHC 8.6 (and HEAD), but it's done
 incorrectly
 (thus this ticket). I think we should avoid this at least for now.

 (1) Is done best in Phab:D5201, because we check lambda form of the
 argument in
 Cmm, which optimises some code that escapes Core optimisations. However, I
 think
 we should be able to improve simplifier somehow to optimise `dataToTag# f`
 in
 comment:43. We can track this in another ticket.

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