[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:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Before deciding on a ''solution'', let's record what the ''problem'' is.

 The original thinking was this.

 * `dataToTag#` is a primop, so it has no business doing anything as
 complicated as evaluating its argument; we already have `case` expressions
 that the code-gen knows how to compile.

 * So `dataToTag#` expects an evaluated argument; in fact, stronger than
 that, it expects a pointer ''to the data value itself'', so that it can
 extract the tag directly from the info table.

 * But if it so happens that the value in question already ''is''
 evaluated, that's a waste.  Example
 {{{
 f x = case x of y -> ...(dataToTag# y)...
 }}}
   It seems a bit silly for `dataToTag#` to re-evaluate `y`.

 * Hence, in `CorePrep` (see `Note [dataToTag magic]`) we add a `case`
 around the argument to `dataToTag#` ''unless'' the argument is already
 evaluated.

 * The "already-evaluated" test is `exprIsHNF`.

 * '''But alas''', while `exprIsHNF` guarantees that the thing will
 evaluate in O(1) time, it does ''not'' guarantee that we have a pointer to
 the data value itself.  Omer accurately diagnoses this problem in the Note
 in his draft Phab:D5196:
 {{{
 Note [Always introduce case around dataToTag# arg]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 We used to only generate a case expression around dataToTag# argument when
 it's
 not known to be evaluated (checked with `exprIsHNF`), but this is
 incorrect.
 Here's an example:

   data T = T1 | T2

   main = print (I# (dataToTag# a))
     where
       {-# NOINLINE f #-}
       f = T2
       {-# NOINLINE a #-}
       a = f

 `f` is a static closure

   f_r1zz :: Main.T
   [GblId, Caf=NoCafRefs, Unf=OtherCon []] =
       CCS_DONT_CARE Main.T2! [];

 but `a` is an _updatable_ CAF!

   a_r1zA :: Main.T
   [GblId, Unf=OtherCon []] =
       [] \u [] f_r1zz;

 An updatable CAF is not in HNF (entering the closure does the `newCAF()`
 stuff
 and updates the closure with an IND_STATIC, the usual CAF evaluation
 routines),
 but according to `exprIsHNF` `a` is!
 }}}

 * I thought of having a more conservative test in `CorePrep`.  But the rot
 goes further.  Consider this, from `Note [dataToTag magic]`
 {{{
    data T = MkT !Bool
    f v = case v of
             MkT y -> dataToTag# y
 }}}
   We certainly know that `y` will be evaluated, because `MkT` is a strict
 constructor.  But does it guarantee to point directly to the data value?
 No!  The case-to-let transformation in the Simplifier
 (`Simplify.doCaseToLet`) uses `exprIsHNF` and hence will drop the eval on
 `MkT`'s argument for things like Omer's `a` binding.  And that is right in
 a way: the argument to `MkT a` certainly isn't bottom!  But nor does it
 point to the data value.

 So that is a problem.  But I think there is another.  Look in comment:13
 and comment:14. Here we have the extra `case` expressions correctly
 inserted, but we ''still'' get the wrong answer.  '''So I think there may
 be ''two'' bugs'''.

 I'd like to understand the second before looking for a fix.  Omer: could
 you investigate why comments 13 and 14 go wrong?

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