Opened 8 months ago

Closed 8 months ago

Last modified 8 months ago

#16197 closed bug (fixed)

Strictness is not preserved under -O1

Reported by: alang9 Owned by:
Priority: normal Milestone: 8.8.1
Component: Compiler Version: 8.4.1
Keywords: DemandAnalysis Cc: me@…, nh2, akio
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Incorrect result at runtime Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

With -O0, the attached code prints:

> /usr/local/ghc/ghc-8.4.1.0/bin/ghc -O0 src/foo.hs; and ./src/foo
[1 of 1] Compiling Main             ( src/foo.hs, src/foo.o ) [Optimisation flags changed]
Linking src/foo ...
("exec",0)
("depth",0)
("exec",1)
("depth",0)

But with -O1, it prints:

> /usr/local/ghc/ghc-8.4.1.0/bin/ghc -O1 src/foo.hs; and ./src/foo
[1 of 1] Compiling Main             ( src/foo.hs, src/foo.o )
Linking src/foo ...
("depth",0)
("depth",0)

Reproduced with 8.4.1 and 8.6.2. Doesn't seem to happen under 8.2.0

Attachments (1)

foo.hs (1.7 KB) - added by alang9 8 months ago.

Download all attachments as: .zip

Change History (11)

Changed 8 months ago by alang9

Attachment: foo.hs added

comment:1 Changed 8 months ago by nh2

Cc: nh2 added

comment:2 Changed 8 months ago by carter

1) what rewrite rules are firing ? 2) more importantly: does disabling rewrite rules under 01 or 02 fix the bug?

comment:3 Changed 8 months ago by alang9

The bug still appears with -O1 -fno-enable-rewrite-rules. The following BUILTIN rules still fire:

Rule fired: Class op null (BUILTIN)
Rule fired: Class op foldl' (BUILTIN)
Rule fired: Class op null (BUILTIN)
Rule fired: Class op foldl' (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
Rule fired: Class op return (BUILTIN)
Rule fired: Class op return (BUILTIN)
Rule fired: Class op enumFromTo (BUILTIN)
Rule fired: Class op foldl' (BUILTIN)
Rule fired: Class op fromInteger (BUILTIN)
Rule fired: integerToInt (BUILTIN)
Rule fired: Class op show (BUILTIN)
Rule fired: Class op show (BUILTIN)
Rule fired: Class op return (BUILTIN)
Rule fired: Class op showsPrec (BUILTIN)
Rule fired: Class op showsPrec (BUILTIN)
Rule fired: Class op showsPrec (BUILTIN)
Rule fired: Class op showsPrec (BUILTIN)
Rule fired: ># (BUILTIN)
Rule fired: ==# (BUILTIN)

comment:4 Changed 8 months ago by akio

Cc: akio added

I made a smaller test case that I believe exhibits the same issue:

data T = T !Bool
data Box a = Box a

f :: Int -> T -> Box Bool
f n t
  | n <= 0 = case t of
      T b -> Box b
  | otherwise = f (n-2) t

f1 :: Int -> Bool -> Box Bool
f1 n t
  | n <= 0 = f (-n) $! T t
  | otherwise = f1 (n-2) t

g :: Int -> Bool
g k = if k <= 0 then error "crash" else False
{-# NOINLINE g #-}

main :: IO ()
main = case f1 4 (g 0) of
    Box _ -> return ()

With ghc-8.6.2, the above program crashes when compiled with -O0 but not when compiled with -O1.

It looks like the issue has something to do with strictness analysis. After the first pass of the demand analyzer, f gets the following strictness signature:

 Str=<S(S),1*U(U)><S(S),1*U(U)>m,

This means f is deeply strict in the second argument. This is correct in the sense that f n (T undefined) is undefined, but it doesn't mean f is going to deeply evaluate the second argument (it doesn't).

However, it looks like this strong strictness signature is then used in the next simplifier pass to justify dropping the implicit seq on t (arising from the field strictness of T) in f1. This seq is in fact the only thing in the program that forces the error thunk, so dropping it changes the program behavior.

comment:5 Changed 8 months ago by simonpj

I can reproduce this with 8.6, but not with HEAD, so I think perhaps it is fixed. Hooray.

Indeed we have made some recent changes to the handling of strictness on data constructors:

commit d77501cd5b9060e38acd50e11e0c5aae89d75b65
Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Wed Dec 12 17:22:07 2018 +0000

    Improvements to demand analysis
    
    This patch collects a few improvements triggered by Trac #15696,
    and fixing Trac #16029
    
    * Stop making toCleanDmd behave specially for unlifted types.
      This special case was the cause of stupid behaviour in Trac
      #16029.  And to my joy I discovered the let/app invariant
      rendered it unnecessary.  (Maybe the special case pre-dated
      the let/app invariant.)
    
      Result: less special-case handling in the compiler, and
      better perf for the compiled code.
    
    * In WwLib.mkWWstr_one, treat seqDmd like U(AAA).  It was not
      being so treated before, which again led to stupid code.
    
    * Update and improve Notes
    
    There are .stderr test wibbles because we get slightly different
    strictness signatures for an argumment of unlifted type:
        <L,U> rather than <S,U>        for Int#
        <S,U> rather than <S(S),U(U)>  for Int

commit d549c081f19925dd0e4c70d45bded0497c649d49
Author: Ben Gamari <bgamari.foss@gmail.com>
Date:   Tue Dec 11 13:34:47 2018 -0500

    dmdAnal: Move handling of datacon strictness to mkWWstr_one
    
    Previously datacon strictness was accounted for when we demand analysed a case
    analysis. However, this results in pessimistic demands in some cases. For
    instance, consider the program (from T10482)
    
        data family Bar a
        data instance Bar (a, b) = BarPair !(Bar a) !(Bar b)
        newtype instance Bar Int = Bar Int
    
        foo :: Bar ((Int, Int), Int) -> Int -> Int
        foo f k =
          case f of
            BarPair x y -> case burble of
                              True -> case x of
                                        BarPair p q -> ...
                              False -> ...
    
    We really should be able to assume that `p` is already evaluated since it came
    from a strict field of BarPair.
    
    However, as written the demand analyser can not conclude this since we may end
    up in the False branch of the case on `burble` (which places no demand on `x`).
    By accounting for the data con strictness later, applied to the demand of the
    RHS, we get the strict demand signature we want.
    
    See Note [Add demands for strict constructors] for a more comprehensive
    discussion.
    

commit c5b477c29127d8375b3f23d37f877278b52547f6
Author: Ömer Sinan Ağacan <omeragacan@gmail.com>
Date:   Mon Oct 15 13:48:53 2018 -0400

    Fix cardinality change of fields in addDataConStrictness

And indeed the strictness of f is now

 Str=<S,1*U(U)><S,1*U(U)>m,

I had previously regarded these patches as clean-ups, improving the generated code, rather than actual bug fixes. So your example is very interesting: it shows that the "clean-up" actually fixed a bug.

Ben/Omer: could you add comment:4 as a regression test?

comment:6 Changed 8 months ago by osa1

Status: newpatch

Added the test in https://gitlab.haskell.org/ghc/ghc/merge_requests/132

We should probably merge these commits to 8.8 branch if they're not merged already. Ben, updating status to "merge", please close the ticket if the commits on comment:5 are already merged. (I don't know where the 8.8 branch is so I can't check)

comment:7 Changed 8 months ago by osa1

Status: patchmerge

comment:8 Changed 8 months ago by Ömer Sinan Ağacan <omeragacan@…>

In a1e9cd6/ghc:

Add test for #16197

comment:9 Changed 8 months ago by bgamari

Milestone: 8.8.1
Resolution: fixed
Status: mergeclosed

I'm just going to bump the ghc-8.8 branch to match master as of today.

comment:10 Changed 8 months ago by simonpj

Keywords: DemandAnalysis added
Note: See TracTickets for help on using tickets.