Opened 7 years ago

Closed 7 months ago

Last modified 6 months ago

#5129 closed bug (fixed)

"evaluate" optimized away

Reported by: dons Owned by:
Priority: normal Milestone: 8.4.2
Component: Compiler Version: 7.0.3
Keywords: seq, evaluate Cc: ezyang@…, alpmestan, michalt, simonmar, George
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Incorrect result at runtime Test Case:
Blocked By: Blocking:
Related Tickets: #13930 Differential Rev(s): Phab:D615, Phab:D4514
Wiki Page:

Description

Reported on Stackoverflow: http://stackoverflow.com/questions/5697159/testing-for-error-calls-in-hunit

With optimizations on, the following program, which normally succeeds (correctly generating an exception), instead fails, and the exception is optimized away.

import Control.Exception
import Test.HUnit

throwIfNegative :: Int -> String
throwIfNegative n | n < 0     = error "negative"
                  | otherwise = "no worries"
{-# NOINLINE throwIfNegative #-}

case_negative =
    handleJust errorCalls (const $ return ()) $ do
        evaluate $ throwIfNegative (-1)
        assertFailure "must throw when given a negative number"
  where errorCalls (ErrorCall _) = Just ()

main = runTestTT $ TestCase case_negative

Looking at the core, after a few iterations, the call to throwIfNegative is dropped as dead code.

Using seq instead of evaluate is happy enough:

case_negative =
    handleJust errorCalls (const $ return ()) $ do
        throwIfNegative (-1) `seq` assertFailure "must throw when given a negative number"
  where errorCalls (ErrorCall _) = Just ()

or a bang pattern:

case_negative =
    handleJust errorCalls (const $ return ()) $ do
        let !x = throwIfNegative (-1)
        assertFailure "must throw when given a negative number"
  where errorCalls (ErrorCall _) = Just ()

Possibly related to #2273

Change History (41)

comment:1 Changed 7 years ago by ezyang

Cc: ezyang@… added

comment:2 Changed 7 years ago by simonpj

Actually this ticket is a bit different to #2273. Here is what is happening.

Here are the background definitions:

evaluate :: a -> IO ()
-- Defined in GHC.IO.Base
evaluate x = x `seq` return ()

poss_err :: String 
-- Assume this doesn't get constant folded away
-- So poss_err isn't definitely bottom.
-- (You had a NOINLINE on throwIfNegative)
poss_err = if (-1) < 0 then error "urk" else "foo"

assertFailure :: String -> IO ()
-- Defined in Test.HUnit.Lang
assertFailure s = throw (userError "blah")

Now consider the term

...catch (evaluate poss_err >> assertFailure "foo")...

By the time we've inlined (>>) and evaluate, we get something like this

...catch (\s. case poss_err of _ -> assertFailure "foo" s)...

Now if GHC sees (case x of y { ...blah... }), and y is used strictly in ...blah..., it discards the case expression. After all, we reason that if x turned out to throw an exception, we'll get the exception later instead. And indeed, since ...blah... diverges (well, throws a different error), y is used strictly.

It's like the case in our imprecise-exception paper where we argue that we should not specify which of the two errors is thrown by (error "urk" + error "bok"). It's imprecise.

However, this is the IO monad, where the order of evaluation is defined, and the exceptions raise are too. There are two mistakes.

  • In GHC.IO.Base, the function evaluate is small and hence can be inlined. That exposes the fact that the state token is not affected by evaluating the argument. If we didn't inline evaluate we'd end up with something like
      \s.  case (evaluate poss_err s) of (# s1, _ #) -> assertFailure "blah" s1
    
    Now we can't drop the case because we need the state token s1. If we just put a {-# NOINLNE #-} on evaluate we'll hide this from GHC so it won't discard such cases.
  • In Test.HUnit.Lang, the function assertFailure has an IO type, but is defined using throw. It should be define using throwIO. The whole point of throwIO is that it consumes a state token, and that's what sequences it relative to earlier producers of the state token.

I'll fix evaluate, but someone else had better deal with HUnit.

Simon

comment:3 Changed 7 years ago by ezyang

It seems to me that we ought to be able to inline evaluate; if we emitted something directly like:

case (# touch s, poss_err #) of (# s1, _ #) -> assertFailure "blah" s1

where touch is some primitive that eventually becomes a no-op but enforces ordering (maybe we don’t even need it as it stands?). In this case the case wouldn't be dropped. NOINLINE works, but it seems a little wrong to me to add the overhead of a function application.

comment:4 Changed 7 years ago by simonpj

No -- GHC would just split them apart. You'd need a new primitive:

evaluate# :: o -> State# a -> State# a

That is, with the same type as touch# but it does evaluation, which touch# does not. Otherwise I can't see how to be certain that the eval will never be dropped; the only way I can see is to combine evaluation and state-token-transformation in a way that GHC can't disentangle, hence evaluate#.

I don't think this is common enough that the performance impact of an out-of-line call will be important.

Simon

comment:5 Changed 7 years ago by simonpj

Owner: set to simonmar

Simon and I have just agreed that the right thing is to implement a small family of primops:

touchS# :: a -> State# b -> State# b     -- The current touch#
seqS#   :: a -> State# b -> State# b     -- Used for 'evaluate'
parS#   :: a -> State# b -> State# b     -- Use for the par monad

comment:6 Changed 7 years ago by ezyang

One rather user-visible result of this ticket is that we should now discourage the use of the idiom

x `seq` return ()

I can see a few instances of this in base

ezyang@javelin:~/Dev/ghc-master/libraries/base$ grep -R '`seq` return ()' .
./Foreign/C/String.hs:        go [] n     = n `seq` return () -- make it strict in n
./Foreign/C/String.hs:        go [] n     = n `seq` return () -- make it strict in n
./GHC/IO/Handle/Text.hs:    c `seq` return ()
./GHC/Conc/Windows.hs:  r `seq` return () -- avoid space leak

and there are probably more elsewhere.

comment:7 Changed 7 years ago by simonpj

Indeed. Every one of these should be call to evaluate; that is what evaluate is for! Ian: can you make it so?

Simon

comment:8 Changed 7 years ago by simonpj

I'm just adding Don's comment and my response from ghc-users.

Don says: that's a very common idiom. Interestingly, we have:

-- | Strict (call-by-value) application, defined in terms of 'seq'.
($!)    :: (a -> b) -> a -> b
#ifdef __GLASGOW_HASKELL__
f $! x  = let !vx = x in f vx  -- see #2273 
#elif !defined(__HUGS__) f 
$! x  = x `seq` f x
#endif

Simon's response: It's very different, I think.

  • evaluate is in the IO monad, and (should) guarantee to evaluate the argument before proceeding, so if evaluating the argument to WHNF diverges or throws a exception, any exceptions thrown (in the IO monad at least) after the 'evaluate' should not happen. For example:
    evaluate (throw "first") >> throwIO (userError "second")
    
    should guaranteed to throw "first" and not "second". (The current bug is the 'evaluate' doesn't meet its guarantee.)
  • Strict application ($!) is not in the IO monad, so it merely makes a strictness guarantee. It doesn't guarantee to make exceptions in the argument "beat" exceptions in the function. For example
    ((:) $! (throw "second")) $! (throw "first")
    
    does not guaranteed to throw "first" rather than "second".

Does that distinction make sense? Perhaps the contrast is a useful one. I wonder where it might be documented?

comment:9 Changed 7 years ago by rl

Why is x `seq` return () discouraged? Why would I use evaluate if I want to make my code strict in x but don't care when it is evaluated? This seems to be what ezyang's examples are about (the ones in Foreign.C.String even say so explicitly) so I don't understand why these should be replaced with evaluate.

comment:10 Changed 7 years ago by simonpj

OK fair enough. If all you want is strictness, then seq should be fine. If you want exception ordering, or space-leak squashing, then evaluate is better.

comment:11 Changed 7 years ago by ezyang

I would like to understand this tradeoff better. I would like to be able to say "use evaluate whenever the IO monad is available" but it seems you might preclude some optimizations with this advice.

comment:12 Changed 7 years ago by simonmar

Right, it's quite common to use

   do ...
      return $! e

to avoid the thunk that would otherwise be created for e. My guess is that in most cases we don't care about the order of evaluation in these cases, so $! is fine.

It also occurs to me that the simplifier won't know how to optimise seqS# unless we teach it. For example, we want to eliminate seqS# when applied to a value.

comment:13 Changed 7 years ago by simonmar

See also Note [Desugaring seq] (1) and (2) in DsUtils.

comment:14 Changed 7 years ago by marlowsd@…

commit be5441799b7d94646dcd4bfea15407883537eaaa
Author: Simon Marlow <marlowsd@gmail.com>
Date:   Mon Jun 27 16:45:15 2011 +0100

    Add two new primops:
    
      seq#   :: a -> State# s -> (# State# s, a #)
      spark# :: a -> State# s -> (# State# s, a #)
    
    seq# is a version of seq that can be used in a State#-passing
    context.  We will use it to implement Control.Exception.evaluate and
    thus fix #5129.  Also we have plans to use it to fix #5262.
    
    spark# is to seq# as par is to pseq.  That is, it creates a spark in a
    State#-passing context.  We will use spark# and seq# to implement rpar
    and rseq respectively in an improved implementation of the Eval monad.

comment:15 Changed 7 years ago by simonmar

Status: newmerge

We now have a test for this, and once that is merged this ticket is done. The remaining issue with seq is tracked in #5262.

commit 5ba6997081dd2cba642e61d21d362d050e388e7a
Author: Simon Marlow <marlowsd@gmail.com>
Date:   Wed Jun 29 15:00:14 2011 +0100

    Add test for #5129

comment:16 Changed 7 years ago by igloo

Resolution: fixed
Status: mergeclosed

Merged

comment:17 Changed 4 years ago by simonpj

A later note, in the light of this email thread. Looking at the Haddock documentation for evaluate, Roman said: we seem to have three possible implementations for evaluate:

1) evaluate x  = return $! x
2) evaluate x  = (return $! x) >>= return
3) evaluate x = \s -> seq# x s

Now (1) is too strict: (evaluate (error "urk") True) should yield True.

And, contrary to my claim in the email thread, (2) suffers from comment:2 above: inlining can mean that the argument to evaluate never gets evaluated.

Consider, under (2)

evaluate = \x -> (return $! x) >>= return
         = \x. \s.  case return $! x s of (s1, r) -> return r s1
         = \x s. x `seq` case (s,x) of (s1, r) -> return r s1
         = \x s. x `seq` (s,x) 
         = \x s. case x of _ -> (s,x)

Now consider the call in comment:2:

evalutate poss_err >> assertFailure "foo"`

= (inline >>)
  \s -> case evaluate poss_err of (s1, _) -> assertFailure "foo" s1

= (inline evaluate)
  \s -> case (case x of _ -> (s,x)) of (s1, _) -> assertFailure "foo" s1

= (case of case)
  case x of _ -> assertFailure "foo" s1

and now, as explained in comment:2, since assertFailure diverges, GHC feel free to discard the case on x.

Using a primop seq# :: a -> State# -> (State#, a) means that the I/O options that follows, which consumes the state that comes out of the seq# simply can't start until the seq# has executed. And that is what we want for evaluate.

So only (3) will do.

The claim in the Haddock docs for evaluate that (2) is a correct definition is, I think, false. Simon M added this claim in commit aa73318a in (base repo). I think I'll simply delete it.

Last edited 4 years ago by simonpj (previous) (diff)

comment:18 Changed 4 years ago by Feuerbach

Thanks Simon. I'll try to digest what you've written, and based on my understanding I'll write a better documentation for evaluate that would explain the issue.

— Roman

Last edited 4 years ago by Feuerbach (previous) (diff)

comment:19 Changed 3 years ago by thomie

Differential Rev(s): Phab:D615

In commit de9a836cd920722a4c28dcb464ff2c8d5905acb9:

Author: Roman Cheplyaka <>
Date:   Mon Feb 9 13:44:03 2015 -0600

    Clarify the documentation for 'evaluate'
    
    Summary:
    See:
    
      https://www.haskell.org/pipermail/ghc-devs/2015-January/007900.html
      https://ghc.haskell.org/trac/ghc/ticket/5129#comment:17
    
    Reviewers: hvr, Mikolaj, austin
    
    Reviewed By: Mikolaj, austin
    
    Subscribers: ezyang, nomeata, thomie
    
    Differential Revision: https://phabricator.haskell.org/D615

comment:20 Changed 7 months ago by alpmestan

A recent ./validate --slow run I did revealed that this test doesn't pass anymore. I found out that something changed between 8.0.2 and 8.2.1:

$ nix-shell -p haskell.compiler.ghc821 --run 'ghc-8.2.1 -O -fforce-recomp ~/ghc/testsuite/tests/codeGen/should_run/T5129.hs && /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129'
  [1 of 1] Compiling Main             ( /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129.hs, /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129.o )
Linking /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129 ...
T5129: HUnitFailure "must throw when given a negative number"

$ nix-shell -p haskell.compiler.ghc802 --run 'ghc-8.0.2 -O -fforce-recomp ~/ghc/testsuite/tests/codeGen/should_run/T5129.hs && /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129'
[1 of 1] Compiling Main             ( /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129.hs, /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129.o )
Linking /home/alp/ghc/testsuite/tests/codeGen/should_run/T5129 ...
  
$

comment:21 Changed 7 months ago by bgamari

Owner: simonmar deleted
Resolution: fixed
Status: closednew

Let's reopen this (or open a new ticket to track these). These competing bottoms are tricky!

comment:22 Changed 7 months ago by alpmestan

Cc: alpmestan added

comment:23 Changed 7 months ago by michalt

Cc: michalt added

comment:24 Changed 7 months ago by osa1

Started looking into this,

With -O1 evaluate (and seq#, and the throwIfNegative call) vanishes, and the whole program is transformed into an assertFailure:

Main.main1
  = \ (eta2_a3iv :: GHC.Prim.State# GHC.Prim.RealWorld) ->
      GHC.Prim.catch#
        @ () @ SomeException Main.main3 Main.main2 eta2_a3iv

Main.main3
  = \ _ [Occ=Dead, OS=OneShot] -> case Main.main4 of wild_00 { }

Main.main4 = assertFailure_rCn @ (IO ()) lvl1_r4kE

Main.main2
  = \ (e1_a3iI [OS=OneShot] :: SomeException)
      (eta_B1 [OS=OneShot] :: GHC.Prim.State# GHC.Prim.RealWorld) ->
      case e1_a3iI of wild_a3jJ

With some debug prints I was able to find the simplifier call that eliminates seq#:

rebuildCase
  is_plain_seq
  expr ok for side effects: seq#
                              @ String @ RealWorld (throwIfNegative (I# -1#)) s_a3jI
  alts: [((#,#),
          [ipv_a3jL, ipv1_a3jM],
          case assertFailure
                 @ (IO ())
                 (build
                    @ Char
                    (\ (@ b_a3eo) ->
                       unpackFoldrCString#
                         @ b_a3eo "must throw when given a negative number"#))
          of {
          })]
  cont: Stop[BoringCtxt] (# State# RealWorld, () #)
  ret: (SimplFloats {lets:  FltLifted
                            []
                     joins: []
                     in_scope: InScope {...}},
        case assertFailure
               @ (IO ())
               (build
                  @ Char
                  (\ (@ b_a3eo) ->
                     unpackFoldrCString#
                       @ b_a3eo "must throw when given a negative number"#))
        of wild_00 {
        })

This basically says rebuildCase sees the seq# call in the scrutinee position, thinks that it's side-effect-free (because the primop is not marked as effectful), also thinks that it's a "plain seq", and eliminates the case expression.

"Plain seq" in this context is defined like this:

is_plain_seq   = all_dead_bndrs && isDeadBinder case_bndr -- Evaluation *only* for effect

So the code looks correct to me; primops is not marked as effectful, and this case expression is only for the (non-existent) effects, so it can be eliminated.

Looking at the discussion above, I think not marking seq# as effectful was deliberate (otherwise seq# becomes spark#). I guess the idea was to force sequencing via a dependency of State# RealWorld return value of seq# and the next IO action, but I'm not sure how is that supposed to work in pure code. Can anyone say a few words about how do we expect to keep seq# when it's not effectful, and its return value is not used?

comment:25 Changed 7 months ago by alexbiehl

comment:26 Changed 7 months ago by osa1

One way to fix this if we want to keep seq# as effect-free is avoiding inlining evaluate with {-# NOINLINE evaluate #-}.

comment:27 Changed 7 months ago by osa1

Confirmed that adding {-# NOINLINE evaluate #-} also fixes #13930.

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

In 5a1ad231/ghc:

Update test for #5129:

Make sure it runs with --fast validate with correct optimisation
settings (-O1 or above) so that it actually tests the bug.

Because the bug is in the simplifier running it with -O0 doesn't
test it.

comment:29 Changed 7 months ago by osa1

Differential Rev(s): Phab:D615Phab:D615, Phab:D4514

Submitted a patch for this. Assuming we want to keep seq# pure (e.g. has_side_effects = False in the primop definition) I think hiding evaluate from the simplifier makes sense.

comment:30 Changed 7 months ago by dfeuer

This NOINLINE strikes me as something fragile that doesn't really get at the point. I don't have this properly paged in right now, but see Exceptions/PreciseExceptions for some of my previous thoughts on the matter. I don't understand the sense in pretending it's "pure". I think we want to consider it side-effecting. I imagine it's already marked as lazy, but just in case it's not, it should be. There are situations where it's okay to remove seq#, but I'm less sure how to be sure that it remains safe after further transformations. The most obvious situation:

case seq# a s of
  (# s', a' #) -> seq# a' s'

-- ==>

seq# a s

A similar situation:

case x of
  !x' -> seq# x' s

Surely we don't want to force x twice, but we don't want to drop the seq#; we want to transform this to seq# x s.

Suppose we have

case x of
  !x' -> case f x of
     !y -> case seq# x' s of (# s', _ #) -> (# s', y #)

That's a bit trickier. It's certainly safe to transform it to

case seq# x s of
  (# s', x' #) -> case f x' of
      !y -> (# s', y #)

That might be too conservative, but I don't know if it will really hurt.

comment:31 Changed 7 months ago by osa1

In comment:24 I say that the case seq# ... of is eliminated because the result is not used and seq# is effect-free. The reason why the result is not used is because assertFailure is a pure function with type String -> a. Just wanted to post this update because I was confused about this for a long time (I thought assertFailure was an IO function).

comment:32 Changed 7 months ago by bgamari

Milestone: 8.4.2

comment:33 Changed 7 months ago by simonpj

One way to fix this if we want to keep seq# as effect-free is avoiding inlining evaluate with {-# NOINLINE evaluate #-}.

I'm very unhappy with this. It just sweeps the problem under the rug. What if the user wrote

..(case (seq# (throwIfNegative (I# -1#)) s) of <alts>)...

We don't want to discard the case.

Moreover we shouldn't. The "plain-seq" transformation in Simplify.hs looks like

  | is_plain_seq
  , exprOkForSideEffects scrut
  = ...

Well, should exprOkForSideEffects return False (as it does) for seq# (throwIfNegative (I# -1#)) s? The comments in CoreUtils say

-- Precisely, exprOkForSpeculation returns @True@ iff:
--  a) The expression guarantees to terminate,
--  b) soon,
--  c) without causing a write side effect (e.g. writing a mutable variable)
--  d) without throwing a Haskell exception
--  e) without risking an unchecked runtime exception (array out of bounds,
--     divide by zero)
--
-- For @exprOkForSideEffects@ the list is the same, but omitting (e).

So clearly exprOkForSideEffects should return False! That's the real bug!

Why does it return True? Because in arg_ok in CoreUtils.app_ok we see

    arg_ok (Anon ty) arg        -- A term argument
       | isUnliftedType ty = expr_ok primop_ok arg
       | otherwise         = True  -- See Note [Primops with lifted arguments]

Uh oh! It never even looks at the argument throwIfNegative minus_one!

I think that seq# is exception to the reasoning in Note [Primops with lifted arguments], which says that a primop doesn't evaluate a lifted argument. In effect seq# does.

So in the PrimOpId case of app_ok I think we want to add

        | SeqOp <- op
        -> all (expr_ok primop_ok) args

And sure enough that fixes it.

I'll make a patch.

comment:34 Changed 7 months ago by tdammers

Just to be sure; will this also solve #13930?

comment:35 Changed 7 months ago by simonmar

Cc: simonmar added

comment:36 Changed 7 months ago by Simon Peyton Jones <simonpj@…>

In abaf43d/ghc:

Fix seq# case of exprOkForSpeculation

This subtle patch fixes Trac #5129 (again; comment:20
and following).

I took the opportunity to document seq# properly; see
Note [seq# magic] in PrelRules, and Note [seq# and expr_ok]
in CoreUtils.

comment:37 Changed 7 months ago by osa1

Status: newmerge

Thanks Simon, the notes are really helpful.

comment:38 Changed 7 months ago by bgamari

Resolution: fixed
Status: mergeclosed
Last edited 7 months ago by bgamari (previous) (diff)

comment:39 Changed 6 months ago by George

Forgive me for asking what seems to be obvious: do we need to run validate ./slow more often? Maybe we have already decided to do that in which case it might be good to record that here.

comment:40 Changed 6 months ago by George

Cc: George added

comment:41 Changed 6 months ago by bgamari

George, indeed we do. Alp has recently been working on cleaning up the ./validate --slow output (#14890) so we can run it during CI.

Note: See TracTickets for help on using tickets.