#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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: | -------------------------------------+------------------------------------- Description changed by hvr: Old description:

When compiling and running `text-containers`'s test-suite, the test-cases involving lookup functions (e.g. `member :: Key -> TextSet -> Bool`) fail indeterministically.

''more details to follow''

New description: When compiling and running `text-containers`'s test-suite, the test-cases involving lookup functions (e.g. `member :: Key -> TextSet -> Bool`) fail indeterministically. NB: The code in question works perfectly for GHC 7.10.3/8.0.2/8.2.1; and I've also verified this isn't related to the new `compareByteArray#` primop; in fact you get the very same failures if you force `text- containers` to use the memcmp FFI (by editing the respective `if` conditional in the .cabal file). Repro instructions (sorry, haven't had time to minimize it yet): {{{#!sh # get wip/ghc-T14361 branch of `text-containers` git clone https://github.com/hvr/text-containers.git -b wip/ghc-T14361 cd text-containers/ # generate cabal.project.local cat > cabal.project.local <http://head.hackage.haskell.org/ secure: True root-keys: 07c59cb65787dedfaef5bd5f987ceb5f7e5ebf88b904bbd4c5cbdeb2ff71b740 2e8555dde16ebd8df076f1a8ef13b8f14c66bad8eafefd7d9e37d0ed711821fb 8f79fd2389ab2967354407ec852cbe73f2e8635793ac446d09461ffb99527f6e key-threshold: 3 allow-newer: *:base, tagged-0.8.5:template-haskell EOF # update head.hackage package index if needed; # use https://github.com/hvr/head.hackage/blob/master/scripts/head.hackage.sh script head.hackage.sh update }}} You can now build & run the test-suite via (if you need, you can replace `ghc-8.3.20171016` by the full path to your `inplace/bin/ghc-stage2` executable): {{{ cabal new-test -w ghc-8.3.20171016 }}} ...and this will report {{{ ... All 44 tests passed (3.81s) Test suite text-containers: PASS Test suite logged to: dist-newstyle/build/x86_64-linux/ghc-8.3.20171016/text- containers-0.1.0.0/t/text-containers/test/text-containers-0.1.0.0-text- containers.log 1 of 1 test suites (1 of 1 test cases) passed. }}} If however, you edit `src/Internal2.hs` and disable either the - `{-# OPTIONS_GHC -fno-strictness #-}` or the - `{-# NOINLINE cmpBA2OfsLen #-}` pragmas, and re-run the test-suite, those 6 of the 44 tests which test the `member`/`lookup{GE,LE}` operations will start failing, e.g. {{{ ... null: OK (0.06s) +++ OK, passed 100 tests. member: FAIL *** Failed! Falsifiable (after 25 tests and 6 shrinks): Ps [("\74914\869082\952045\187526\US",18),("\444739R^\DC3\RSpr",-20),("Je\5900LfM\SI\622028\13867\861002\\+?\49284Mi",9),("\ETB",-3),("\EOT,3/{wdirM\66595\829945R\17707_9\1079715DA\SOH5",0),("Md",-13),("gSY\ESC3N\DLEE\864876'~\184683z\ESCy<\r\448917\787640\SYN\752866",15)] Use --quickcheck-replay=592157 to reproduce. (!?): FAIL *** Failed! Falsifiable (after 18 tests and 2 shrinks): Ps [("\DC3|X|\488551)|8\NAKa\278082an\649221\v\843318",1),("\603109\SYN\EOT\999535http://ghc.haskell.org/trac/ghc/ticket/14361#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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 bgamari): For better or worse I am able to reproduce this. Hrmph. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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 hvr): To make things easier, here's a smaller repro-case which doesn't require building the test-suite of `text-containers`: {{{#!hs {-# LANGUAGE OverloadedLists #-} {-# LANGUAGE OverloadedStrings #-} module Main where import Control.Monad import qualified Data.List as List import Data.String import qualified Data.TextSet.Unboxed as TS main :: IO () main = do putStrLn "START" forM_ ([ 0 .. 10 ] :: [Int]) $ \_ -> do forM_ (zip [ 1::Int .. ] (List.inits testData)) $ \(j,xs) -> do unless (all (`TS.member` (TS.fromList xs)) xs) $ putStr (show j ++ " ") forM_ (zip [ 1::Int .. ] (List.tails testData)) $ \(j,xs) -> do unless (all (`TS.member` (TS.fromList xs)) xs) $ putStr (show (-j) ++ " ") putStrLn "" putStrLn "DONE" return () testData :: [TS.Key] testData = [ fromString [c] | c <- ['A' .. 'Z'] ] }}} If you have Cabal 2.1+, you can simply use its generated GHC environment file via {{{ # solve & build *only* the library component, and generate .ghc.environment.* file $ cabal new-build lib:text-containers --disable-tests -w ghc-8.3.20171016 # build test program $ ghc-8.3.20171016 --make -Wall -O1 bug-t14361.hs [1 of 1] Compiling Main ( bug-t14361.hs, bug-t14361.o ) Linking bug-t14361 ... # run test program $ ./bug-t14361 START 22 -2 -23 -3 -1 26 -1 -15 11 12 13 -8 7 15 18 -11 19 -2 -1 26 -1 26 -1 DONE }}} If the program was executed correctly the output would have no numbers, i.e. it would look like {{{ START DONE }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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 bgamari): I should also note that the problem appears to be an interaction between the strictness signature of `Internal2.cmpBA2OfsLen` and one of the call- sites in `Data.TextSet.Unboxed.lookupIndexNear`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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 bgamari): One thing that I've noticed while looking at the Core here I noticed what I believe is a slight performance papercut in our Core: In the Core we essentially have this: {{{#!hs data IdxOfsLen = IdxOfsLen !Int !Int !Int }}} Inside of `lookupIndexNear` we end up with a join point: {{{#!hs $j_sjcd [Dmd=] :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> IdxOfsLen -> LRes [LclId[JoinId(4)], Arity=4, Str=, Unf=OtherCon []] $j_sjcd (ww5_scRL [OS=OneShot] :: GHC.Prim.Int#) (ww6_scRM [OS=OneShot] :: GHC.Prim.Int#) (ww7_scRN [OS=OneShot] :: GHC.Prim.Int#) (ww4_scRK [OS=OneShot] :: IdxOfsLen Unf=OtherCon []) = case Internal2.$wcmpBA2OfsLen y_a4lB ww_sjnB ww6_scRM ww7_scRN of { LT -> Data.TextSet.Unboxed.LResBelow ww4_scRK; EQ -> Data.TextSet.Unboxed.LResExact ww4_scRK; GT -> {- some expression with no dependence on any of the above arguments -} }}} Where the call sites all look like, {{{#!hs jump $j_sjcd a b c (Internal.IdxOfsLen a b c) }}} That is, we essentially pass the same arguments twice, once unboxed and once inside a `IdxOfsLen` constructor. It seems the reason for this is that we always need the unboxed values for the call to `$wcmpBA2OfsLen` but also sometimes need the `IdxOfsLen`. It seems like it would be better to either only pass the constructor and extract the needed values out of it inside the join point, or to only pass the unboxed arguments, and construct the constructor when needed. I doubt this makes much of a difference in this particular case, but I suspect there are others where it will matter quite a bit. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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 bgamari): Alright, the problem was overzealous CBE due to a bug. See Phab:D4152. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: patch Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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): Crumbs. From Phab:D4152: {{{ Previously CBE computed equality by taking the lists of middle nodes of the blocks being compared and zipping them together. It would then map over this list with the equality relation, and accumulate the result. However, this is completely wrong: Consider what will happen when we compare a block with no middle nodes with one with one or more. The result of zip will be empty and consequently the pass may conclude that the two are indeed equivalent (if their last nodes also match). }}} That's truly terrible! Well caught. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: patch Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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 Ben Gamari ): In [changeset:"6f990c54f922beae80362fe62426beededc21290/ghc" 6f990c54/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="6f990c54f922beae80362fe62426beededc21290" cmm/CBE: Fix comparison between blocks of different lengths Previously CBE computed equality by taking the lists of middle nodes of the blocks being compared and zipping them together. It would then map over this list with the equality relation, and accumulate the result. However, this is completely wrong: Consider what will happen when we compare a block with no middle nodes with one with one or more. The result of `zip` will be empty and consequently the pass may conclude that the two are indeed equivalent (if their last nodes also match). This is very bad and the cause of #14361. The solution I chose was just to write out an explicit recursion, like I distinctly recall considering doing when I first wrote this code. Unfortunately I was feeling clever at the time. Unfortunately this case was just rare enough not to be triggered by the testsuite. I still need to find a testcase that doesn't have external dependencies. Test Plan: Need to find a more minimal testcase Reviewers: austin, simonmar, michalt Reviewed By: michalt Subscribers: michalt, rwbarton, thomie, hvr GHC Trac Issues: #14361 Differential Revision: https://phabricator.haskell.org/D4152 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14361: GHC HEAD miscompiles `text-containers` -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: merge Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.3 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): * status: patch => merge -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14361#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler