Loss of full laziness in mapFB

I've just discovered this

g4 x expensive ys = let h = \7 -> y + expensive x
                    in map h ys

Of course we'd expect the (expensive x) call to be floated out of the \y-abstraction, so that it is only done once.

But it isn't! Here's the simplified core with -O:

g4 = \ (@ b_aPG)
       (@ p_atr)
       ($dNum_aPP :: Num b)
       (x_arW :: p)
       (expensive_arX :: p -> b)
       (ys_arY :: [b]) ->
       map @ b @ b
         (\ (y_as0 [OS=ProbOneShot] :: b) ->
            + @ b $dNum_aPP y_as0 (expensive_arX x_arW))
         ys_arY

Yikes! What is happening?

Answer: look at that suspicious ProbOneShot on the \y above. Read Note [Computing one-shot info, and ProbOneShot] in Demand.hs.

When FloatOut runs we have

g4 = \ (@ b_aPL)
       (@ p_atw)
       ($dNum_aPU :: Num b)
       (x_as1 :: p)
       (expensive_as2 :: p -> b)
       (ys_as3 :: [b]) ->
       GHC.Base.build @ b
         (\ (@ b1_aQs)
            (c_aQt [OS=OneShot] :: b -> b1 -> b1)
            (n_aQu [OS=OneShot] :: b1) ->
            GHC.Base.foldr @ b @ b1
              (GHC.Base.mapFB @ b @ b1 @ b
                 c_aQt
                 (\ (y_as5 [OS=ProbOneShot] :: b) ->
                    + @ b $dNum_aPU y_as5 (expensive_as2 x_as1)))
              n_aQu
              ys_as3)

Why is the \y marked ProbOneShot? Because the occurrence analyser marked it so, based on the cardinality info from mapFB, even though mapFB was not saturated.

So Demand.argsOneShots makes a deliberate choice to play risky, and that choice backfires badly for use of map. Not good!

The offending commit, which introduced this behaviour, is (I think)

commit 80989de947dc7edb55999456d1c1e8c337efc951
Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Fri Nov 22 17:13:05 2013 +0000

    Improve the handling of used-once stuff
    
    Joachim and I are committing this onto a branch so that we can share it,
    but we expect to do a bit more work before merging it onto head.
    
    Nofib staus:
      - Most programs, no change
      - A few improve
      - A couple get worse (cacheprof, tak, rfib)
    Investigating the "get worse" set is what's holding up putting this
    on head.
    
    The major issue is this.  Consider
    
        map (f g) ys
    
    where f's demand signature looks like
    
       f :: <L,C1(C1(U))> -> <L,U> -> .
    
    So 'f' is not saturated.  What demand do we place on g?
    Answer
            C(C1(U))
    That is, the inner C1 should stay, even though f is not saturated.
    
    I found that this made a significant difference in the demand signatures
    inferred in GHC.IO, which uses lots of higher-order exception handlers.
    
    I also had to add used-once demand signatures for some of the
    'catch' primops, so that we know their handlers are only called once.

The commit isn't explicit about exactly what the "significant differences" are. Moreover note that in the comment the outer C1 is replaced by C, but nothing like that seems to happen in the code.

This needs investigation.

Trac metadata

Trac field	Value
Version	8.0.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture