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

Next Topic
 
classic Classic list List threaded Threaded
83 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
           Reporter:  mrkkrp         |             Owner:  (none)
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:  8.6.1
          Component:  Compiler       |           Version:  8.6.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Sometimes.

 Here is the thread that explains the bug:

 https://github.com/haskell/containers/issues/568

 I originally reported this as a bug on `containers` issue tracker, but we
 seem to have concluded that this is probably a bug in the GHC optimizer
 itself.

 I think the shortest repro so far is this:

 {{{#!hs
 import qualified Data.Set as S

 main = print $
   let {-# noinline f #-}
       f () = T2
   in  S.fromList [f (), f ()]

 data T = T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9
   deriving (Show, Read, Eq, Ord, Bounded, Enum)
 }}}

 which prints

 {{{#!hs
 fromList [T2,T2]
 }}}

 The person who derived this from my original repro says:

 > And as I said earlier, comment out the T9 constructor => prints fromList
 [T2] as it should.

 Another interesting quote:

 > Can confirm. Tested with ghc-8.6.1, containers-0.6.0.1 and
 leancheck-0.7.5 (so it does not seem to depend on the testing framework).
 Error occurs:
 >
 > * with ghc -O1 and -O2 (but not with -O0)
 > * and if data type has at least 9 elements
 >
 > So, likely a bug in ghc's optimizer.
 >
 > in some cases, input has duplicates, but not always.

 This is a bad one, makes GHC 8.6.1 totally unusable for me.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by dfeuer):

 * priority:  normal => highest
 * cc: dfeuer (added)
 * failure:  None/Unknown => Incorrect result at runtime


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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 That's terrible!

 The following all produce the same (wrong) restul
 {{{
  S.fromList (map f [ () | _ <- [1..10] ])    -- T2,T2
  S.fromList [f (), f ()]                     -- T2,T2
  S.fromList [f (), f (), f()]                -- T2,T2
 }}}
 However this works fine
 {{{
  f () `S.insert` (f () `S.insert` S.empty)
 }}}
 The comparison operations generated by `deriving` look ok to me.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by osa1):

 * cc: osa1 (added)


Comment:

 The problem is in this Core generated for this program:

 {{{
 -- RHS size: {terms: 5, types: 2, coercions: 0, joins: 0/0}
 f_r6li
 f_r6li = \ ds_d3M6 -> case ds_d3M6 of { () -> T2 }

 -- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0}
 lvl_r6lj
 lvl_r6lj = f_r6li ()

 main2
 main2
   = case dataToTag# lvl_r6lj of a#_a2rY { __DEFAULT ->
     case dataToTag# lvl_r6lj of b#_a2rZ { __DEFAULT ->
     ...
 }}}

 We get the tag of a CAF (`lvl_r6lj`) before evaluating it, so we get tag
 of a thunk. The need for evaluating argument of `dataToTag#` is explained
 in `Note [dataToTag#]` in primops.txt.pp. It seems like we're inlining
 `getTag`, and then somehow eliminating the case expression in `getTag` (to
 evaluate its argument). If I change the `INLINE` annotation of `getTag` to
 `NOINLINE` this works as expected.

 I don't know why we're elminating the `case` in `getTag` after inlining it
 yet.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by osa1):

 Ah, so it turns out we have a special case in CorePrep (which runs after
 simplifications) about `dataToTag#`, and we generate a case expression
 around its argument after all the simplifications. It's explained in `Note
 [dataToTag magic]` in CorePrep, and I can see in STG that it works as
 expected:

 {{{
 lvl_r6ru = \u [] f_r6rt ();

 lvl1_r6rv = CCS_DONT_CARE :! [lvl_r6ru []];

 main2 =
     \u []
         case
             case lvl_r6ru of sat_s6xD { __DEFAULT -> dataToTag#
 [sat_s6xD]; }
         of
         a#_s6xE
         { __DEFAULT ->
               case
                   case lvl_r6ru of sat_s6xF { __DEFAULT -> dataToTag#
 [sat_s6xF]; }
               of
               ...
 }}}

 So perhaps this is not because we get tag of a thunk. I don't know why not
 inlining `getTag` fixes this.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by j.waldmann):

 * cc: j.waldmann (added)


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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by RyanGlScott):

 Here's an example which doesn't depend on any code from `containers`. It
 also makes the derived `Ord` code explicit:

 {{{#!hs
 {-# LANGUAGE MagicHash #-}
 module Main where

 import qualified Data.Foldable as Foldable
 import GHC.Exts (dataToTag#, tagToEnum#, (==#), (<#))

 main :: IO ()
 main | not_ordered a b = print $ Foldable.foldl' (flip wumbo) (singleton
 a) b
      | otherwise       = pure ()
   where
     {-# NOINLINE f #-}
     f () = T2
     {-# NOINLINE a #-}
     a = f ()
     {-# NOINLINE b #-}
     b = [f ()]

 data T = T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9
   deriving (Eq, Show)

 instance Ord Main.T where
   compare a b
     = case dataToTag# a of
         a' -> case dataToTag# b of
                 b' -> if tagToEnum# (a' <# b') :: Bool then
                           LT
                       else
                           if tagToEnum# (a' ==# b') :: Bool then
                               EQ
                           else
                               GT

 data Set a = Bin !a !(Set a) !(Set a)
            | Tip
   deriving Show

 not_ordered :: Ord a => a -> [a] -> Bool
 not_ordered _ [] = False
 not_ordered x (y : _) = x >= y

 wumbo :: Ord a => a -> Set a -> Set a
 wumbo x0 = go x0 x0
   where
     go :: Ord a => a -> a -> Set a -> Set a
     go orig _ Tip = singleton orig
     go orig x t@(Bin y l r) = case compare x y of
         LT -> error "not used here"
         GT -> Bin y l (go orig x r)
         EQ -> t
 {-# INLINE wumbo #-}

 singleton :: a -> Set a
 singleton x = Bin x Tip Tip
 }}}

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 That's really helpful Ryan, thank you.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by RyanGlScott):

 Apologies, I meant to mention in comment:6 what `wumbo` actually is: it's
 a stripped down version of `insert` intended to highlight that it appears
 to behave differently between GHC 8.4.3 and 8.6.1. The semantics of
 `wumbo` differs from that of `insert`, but here is the important bit:

 {{{
 $ /opt/ghc/8.4.3/bin/ghc -O2 -fforce-recomp Bug.hs && ./Bug
 [1 of 1] Compiling Main             ( Bug.hs, Bug.o )
 Linking Bug ...
 Bin T2 Tip Tip

 $ /opt/ghc/8.6.1/bin/ghc -O2 -fforce-recomp Bug.hs && ./Bug
 [1 of 1] Compiling Main             ( Bug.hs, Bug.o )
 Linking Bug ...
 Bin T2 Tip (Bin T2 Tip Tip)
 }}}

 GHC 8.4.3's answer is definitely the correct one, since the only way you'd
 get 8.6.1's answer is by hitting the `GT` case of `wumbo` (which shouldn't
 happen if you're comparing `T2` to `T2`).

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by monoidal):

 I'm minimizing this.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by bgamari):

 * milestone:  8.6.1 => 8.6.2


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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Didn't we just recently start using some pointer tagging for types with
 more than 7 constructors? I'm thinking something could be a drop off in
 that code.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by monoidal):

 Here's a smaller version.

 `ghc T15696 && ./T15696` prints `EQ` correctly, `ghc -O T15696 &&
 ./T15696` prints `LT`.

 {{{
 #!hs
 {-# LANGUAGE MagicHash #-}
 module Main where

 import GHC.Exts (dataToTag#, tagToEnum#, (==#), (<#))

 main :: IO ()
 main = print $ compare a T2
   where
     {-# NOINLINE f #-}
     f = T2
     {-# NOINLINE a #-}
     a = f

 data T = T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9
   deriving (Eq, Show, Ord)

 {-
 instance Ord Main.T where
   compare a b
     = case dataToTag# a of
         a' -> case dataToTag# b of
                 b' -> if tagToEnum# (a' <# b') :: Bool then
                           LT
                       else
                           if tagToEnum# (a' ==# b') :: Bool then
                               EQ
                           else
                               GT
 -}
 }}}

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Avoiding the use of type classes:
 {{{
 main :: IO ()
 main = print $ cmpT a T2
   where
     {-# NOINLINE f #-}
     f = T2
     {-# NOINLINE a #-}
     a = f

 data T = T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9
 --  deriving (Eq, Show, Ord)

 cmpT a b
     = case dataToTag# a of
         a' -> case dataToTag# b of
                 b' -> if tagToEnum# (a' <# b') :: Bool then
                           LT
                       else
                           if tagToEnum# (a' ==# b') :: Bool then
                               EQ
                           else
                               GT
 }}}
 With `-O` we get `LT` for GHC 8.4 and 8.2 and earlier versions.  Without
 `-O` it returns `EQ` as it should.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Omer, might you look at this.  With `-ddump-stg` I see
 {{{
 Main.cmpT :: forall a1 a2. a1 -> a2 -> GHC.Types.Ordering
 [GblId, Arity=2, Caf=NoCafRefs, Str=<S,U><S,U>, Unf=OtherCon []] =
     [] \r [a2_s3tf b_s3tg]
         case
             case a2_s3tf of sat_s3th [Occ=Once] {
               __DEFAULT -> dataToTag# [sat_s3th];
             }
         of
         a'_s3ti
         { __DEFAULT ->
               case
                   case b_s3tg of sat_s3tj [Occ=Once] {
                     __DEFAULT -> dataToTag# [sat_s3tj];
                   }
               of
               b'_s3tk
               { __DEFAULT ->
                     case <# [a'_s3ti b'_s3tk] of {
                       __DEFAULT ->
                           case ==# [a'_s3ti b'_s3tk] of {
                             __DEFAULT -> GHC.Types.GT [];
                             1# -> GHC.Types.EQ [];
                           };
                       1# -> GHC.Types.LT [];
                     };
               };
         };
 }}}
 which looks right.  In another variant (I made `dataToTag#` lazy) I saw
 {{{
 Main.cmpT :: forall a1 a2. a1 -> a2 -> GHC.Types.Ordering
 [GblId,
  Arity=2,
  Caf=NoCafRefs,
  Str=<S,1*U><S,1*U>,
  Unf=OtherCon []] =
     [] \r [a2_s3tf b_s3tg]
         case a2_s3tf of x1_s3th [Occ=Once] {
           __DEFAULT ->
               case dataToTag# [x1_s3th] of a'_s3ti {
                 __DEFAULT ->
                     case b_s3tg of x2_s3tj [Occ=Once] {
                       __DEFAULT ->
                           case dataToTag# [x2_s3tj] of b'_s3tk {
                             __DEFAULT ->
                                 case <# [a'_s3ti b'_s3tk] of {
                                   __DEFAULT ->
                                       case ==# [a'_s3ti b'_s3tk] of {
                                         __DEFAULT -> GHC.Types.GT [];
                                         1# -> GHC.Types.EQ [];
                                       };
                                   1# -> GHC.Types.LT [];
                                 };
                           };
                     };
               };
         };

 }}}
 But both stubbornly return `LT` instead of `EQ`.  This must be a code-gen
 or RTS issue.  I have not looked at the Cmm.  Might you do so?

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by RyanGlScott):

 Weirdly enough, I get different answers than the ones simonpj reported for
 the program in comment:13. To be explicit, if I'm using this program:

 {{{#!hs
 {-# LANGUAGE MagicHash #-}
 module Main where

 import GHC.Exts (dataToTag#, tagToEnum#, (==#), (<#))

 main :: IO ()
 main = print $ compare a T2
   where
     {-# NOINLINE f #-}
     f = T2
     {-# NOINLINE a #-}
     a = f

 data T = T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9
   deriving (Eq, Show)

 instance Ord Main.T where
   compare a b
     = case dataToTag# a of
         a' -> case dataToTag# b of
                 b' -> if tagToEnum# (a' <# b') :: Bool then
                           LT
                       else
                           if tagToEnum# (a' ==# b') :: Bool then
                               EQ
                           else
                               GT
 }}}

 Then I consistently get `LT` regardless of optimization level:

 {{{
 $ /opt/ghc/8.6.1/bin/ghc -O0 -fforce-recomp Bug.hs && ./Bug
 [1 of 1] Compiling Main             ( Bug.hs, Bug.o )
 Linking Bug ...
 LT

 $ /opt/ghc/8.6.1/bin/ghc -O2 -fforce-recomp Bug.hs && ./Bug
 [1 of 1] Compiling Main             ( Bug.hs, Bug.o )
 Linking Bug ...
 LT
 }}}

 If I replace all uses of `dataToTag#` with `getTag`, however:

 {{{#!hs
 {-# LANGUAGE MagicHash #-}
 module Main where

 import GHC.Base (getTag)
 import GHC.Exts (tagToEnum#, (==#), (<#))

 main :: IO ()
 main = print $ compare a T2
   where
     {-# NOINLINE f #-}
     f = T2
     {-# NOINLINE a #-}
     a = f

 data T = T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9
   deriving (Eq, Show)

 instance Ord Main.T where
   compare a b
     = case getTag a of
         a' -> case getTag b of
                 b' -> if tagToEnum# (a' <# b') :: Bool then
                           LT
                       else
                           if tagToEnum# (a' ==# b') :: Bool then
                               EQ
                           else
                               GT
 }}}

 Only then do I get `EQ` without optimization:

 {{{
 $ /opt/ghc/8.6.1/bin/ghc -O0 -fforce-recomp Bug.hs && ./Bug
 [1 of 1] Compiling Main             ( Bug.hs, Bug.o )
 Linking Bug ...
 EQ

 $ /opt/ghc/8.6.1/bin/ghc -O2 -fforce-recomp Bug.hs && ./Bug
 [1 of 1] Compiling Main             ( Bug.hs, Bug.o )
 Linking Bug ...
 LT
 }}}

 What's more, I consistently get the same sets of results in each version
 of GHC dating back to 8.2.2. This makes me believe that the bug that was
 exposed here has actually been lurking for quite a while (but perhaps a
 difference in inlining behavior in 8.6 only just recently exposed it).

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by RyanGlScott):

 The fact that using `dataToTag#` directly produces incorrect results is
 perhaps not terribly surprising, giving that it
 [http://git.haskell.org/ghc.git/blob/21efbc7599e39ec93b8b13b7d7b84811226e6f6f:/compiler/prelude/primops.txt.pp#l2966
 must always be applied to an evalauted argument] (see `Note
 [dataToTag#]`). The fact that the version using `getTag` breaks is more
 worrisome, since `getTag` actually forces its argument (with a bang
 pattern).

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by maoe):

 * cc: maoe (added)


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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by RyanGlScott):

 It's also worth noting that you can trim `T` down to just two
 constructors:

 {{{#!hs
 {-# LANGUAGE MagicHash #-}
 module Main where

 import GHC.Base (getTag)
 import GHC.Exts (tagToEnum#, (==#), (<#))

 main :: IO ()
 main = print $ compare a T2
   where
     {-# NOINLINE f #-}
     f = T2
     {-# NOINLINE a #-}
     a = f

 data T = T1 | T2
   deriving (Eq, Show)

 instance Ord Main.T where
   compare a b
     = case getTag a of
         a' -> case getTag b of
                 b' -> if tagToEnum# (a' <# b') :: Bool then
                           LT
                       else
                           if tagToEnum# (a' ==# b') :: Bool then
                               EQ
                           else
                               GT
 }}}

 And the bug will still trigger. (If you define `data T = T2`, then the bug
 will go away.)

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

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

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15696: Derived Ord instance for enumerations with more than 8 elements seems to be
incorrect
-------------------------------------+-------------------------------------
        Reporter:  mrkkrp            |                Owner:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Replying to [comment:16 RyanGlScott]:
 > The fact that using `dataToTag#` directly produces incorrect results is
 perhaps not terribly surprising...

 Except that we have special code to make sure that always happens
 regardless. The STG Simon pasted looks right from that standpoint: it
 always applies `dataToTag#` under a case on its argument. So my bet is
 that Simon is right: something is going wrong in code generation or the
 RTS.

 Side note: it looks like I was wrong about tagging large types. I believe
 there was some talk of that, but it doesn't look like it's happened as
 yet.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
12345