Core Lint issues during slowtest

[bgamari]

I'm am seeing Core Lint failurse from the T5626 test,

*** Core Lint errors : in result of Simplifier ***                                                                                                                                   
<no location info>: warning:                                                                                                                                                         
    [RHS of go_s54c :: [Int] -> (Int, Int, Int, Int)]                                                                                                                                
    idArity 2 exceeds typeArity 1: go_s54c  

The relevant bits of the program are,

Rec {                                                                                                                                                                                
go_s54c [Occ=LoopBreaker] :: [Int] -> (Int, Int, Int, Int)                                                                                                                           
[LclId,                                                                                                                                                                              
 Arity=2,                                                                                                                                                                            
 CallArity=2,                                                                                                                                                                        
 Str=<B,U>b,                                                 
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,          
         WorkFree=True, Expandable=True, Guidance=NEVER}]              
go_s54c                                                                        
  = \ (ds_X35o :: [Int]) ->                                      
      case ds_X35o of {                                        
        [] -> case lvl_s4Vm of wild_00 { };      
        : y_a34y [Dmd=<B,A>] ys_a34z [Dmd=<B,U>] -> go_s54c ys_a34z
      }                                                            
end Rec }                

lvl_s54d :: (Int, Int, Int, Int)                                                  
[LclId,                                                             
 Arity=1,                                                         
 Str=x,                                                             
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=NEVER}]           
lvl_s54d = go_s54c ([] @ Int)      

[bgamari]

This is very strange since it seems that go_s54c is certainly arity one. Moreover, note how lvl_s54d's IdInfo thinks that it has arity 1 (which is presumably why go_s54c has call arity 2.

It looks like this is related to #10181, which is interesting since I also see some unexpected passes from tests marked as broken due to that ticket (e.g. read029).

[simonpj]

Joachim is going to look into this.

[nomeata]

The problem is that Call Arity has not been changed to know about the special semantics of join points. This is the code for in question:

f :: forall a. [Int] -> a
[LclIdX,
 Arity=1,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True, Guidance=IF_ARGS [0] 128 0}]
f = \ (@ a_a1iy) (a_XX6 :: [Int]) ->
      let {
        z_a34C :: Integer -> a_a1iy
        [LclId,
         CallArity=1,
         Unf=Unf{Src=<vanilla>, TopLvl=False, Value=False, ConLike=False,
                 WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 28 0}]
        z_a34C
          = joinrec {
              go_a34D [Occ=LoopBreaker] :: [Int] -> Integer -> a_a1iy
              [LclId[JoinId(1)],
               Arity=1,
               CallArity=2,
               Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True,
                       WorkFree=True, Expandable=True, Guidance=IF_ARGS [30] 24 0}]
              go_a34D (ds_a34E :: [Int])
                = case ds_a34E of {
                    [] -> case lvl_s4VT of wild_00 { };
                    : y_a34J ys_a34K -> jump go_a34D ys_a34K
                  }; } in
            jump go_a34D a_XX6 } in
      letrec {
        go_a34D [Occ=LoopBreaker] :: [Int] -> Integer -> a_a1iy
        [LclId,
         Arity=1,
         CallArity=2,
         Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True,
                 WorkFree=True, Expandable=True, Guidance=IF_ARGS [30] 40 0}]
        go_a34D
          = \ (ds_a34E :: [Int]) ->
              case ds_a34E of {
                [] -> z_a34C;
                : y_a34J ys_a34K -> go_a34D ys_a34K
              }; } in
      go_a34D a_XX6 lvl_s4VV

Call Arity (which analyzes things from bottom to top) correctly finds out that the bottom go_a34D should have arity 2 (it is called with two arguments, and keeps passing the second one around). This implies that z_a34C is called with one argument, so that gets CallArity=1. From this Call Arity follows that to first go_a34D (the join point) should also have arity two, and it records it so.

The subsequent simplification then eta-expands the go_a34D function, which turns it into a join point (yay!). But it does not *not* eta-expand the join point go_a34D (which gets renamed to go_X45x):

f = \ (@ a_a1iy) (a_XX6 :: [Int]) ->
      joinrec {
        go_a34D [Occ=LoopBreaker] :: [Int] -> Integer -> a_a1iy
        [LclId[JoinId(2)],
         Arity=2,
         CallArity=2,
         Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True,
                 WorkFree=True, Expandable=True, Guidance=IF_ARGS [36 0] 54 0}]
        go_a34D (ds_a34E :: [Int]) (eta_B1 :: Integer)
          = case ds_a34E of {
              [] ->
                joinrec {
                  go_X35x [Occ=LoopBreaker] :: [Int] -> a_a1iy
                  [LclId[JoinId(1)],
                   Arity=1,
                   CallArity=2,
                   Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True,
                           WorkFree=True, Expandable=True, Guidance=IF_ARGS [30] 24 0}]
                  go_X35x (ds_X35z :: [Int])
                    = case ds_X35z of {
                        [] -> case lvl_s4VT of wild_00 { };
                        : y_a34J ys_a34K -> jump go_X35x ys_a34K
                      }; } in
                jump go_X35x a_XX6;
              : y_a34J ys_a34K -> jump go_a34D ys_a34K eta_B1
            }; } in
      jump go_a34D a_XX6 lvl_s4VV

At this point, something went wrong. The now named go_X45x is still marked as having CallArity=2, but it does not actually have that arity!

Where did the argument eta_B1, which I would have expected to be passed to go_X35x, disappear? Was it “pushed into the branches”, and then into the empty set branches of the empty case there?

So the simplifier uses the function tryEtaExpandRhs to try to eta-expand if Call Arity tells it to do so, but it does not even try that for join points (see completeBind in Simplify). I am a bit lost in the code right now and cannot quite reproduce what precisely is happening here. Something related to simplJoinRHS and “Context goes *inside* the lambdas.” Certainly, Luke’s opinion would be welcome.

In any case, I believe the fix is to have the simplifier to simply zap Call Arity information. It is the only place where it is actually used, and as this demonstrates, the simplifier does not preserve Call Arity information. I will prepare a PR for this.

[nomeata]

Patch ready and under scrutinee by Harbormaster and perf.haskell.org.

[Joachim Breitner <mail@…>]

In e07211f/ghc:

Zap Call Arity info in the simplifier

As #13479 shows, there are corner cases where the simplifier decides to
not eta-expand a function as much as its call arity would suggest, but
instead transforms the code that the call arity annotation becomes a
lie.

As the call arity information is only meant to be used by the
immediatelly following simplifier run, it makes sense to simply zap the
information there.

Differential Revision: https://phabricator.haskell.org/D3390

[nomeata]

Fixed, please merge.

[bgamari]

Merged to ghc-8.2 as d88d0258204bf8d4aadd57280b8322890e5b98b3.

[simonpj]

Joachim, I think a better fix would be not to attach call-arity info to JoinIds at all, rather than to involve the simplifier.

Consider this:

   let g = \y. h y True
   in g 3 7

Ignore the fact that g will be inlined; I'm just keeping it simple. What will Call Arity say about h? It'll say that h is definitely called with three arguments, right? Becuase g is called with two arguemts, one is eaten by the \y, so h gets three.

But suppose instead it was

   let g = \y. join j v = h y v
               in case y of
                  True  -> j False
                  False -> j True
   in g 3 7

Now, we could analyse this by treating j like a normal function, and compute its join arity. That's what we do now. But it's simpler and more direct simply to propagate the "apply to 1 arg" info that we apply to the body of g directly into the RHS of j. Completely ignore the occurrences of j, don't compute their join arity.

Roughly:

callArityAnal arity int (Let (NonRec join_id rhs) let_body)
  | Just join_arity <- isJoinId_maybe join_id
  = ( ae_join_body `lubRes` ae_let_body
    , Let (NonRec join_id (mkLams join_bndrs join_body') let_body') )
  where
    (join_bndrs, join_body) = collectNBinders join_arity rhs
    (ae_join_body, join_body') = callArityAnal arity int join_body
    (ae_let_body,  let_body')  = callArityAnal arity int let_body

Now that is pretty simple! (Something similar for Rec.) In effect, we are pushing the evaluation context into the join RHS, just as described in the paper.

I agree that this is extra code... the existing code is still needed. But I think it's possible that it might give beter results in the recursive case. And it's more efficient. And it doesn't bogusly compute a call-arity for a join point.

Worth considering? I'll re-open for you to consider it.

Simon

[nomeata]

Worth considering? I'll re-open for you to consider it.

Definitely worth considering! With my limited experience with join points, this sounds reasonable.

[nomeata]

But it's simpler and more direct simply to propagate the "apply to 1 arg" info that we apply to the body of g directly into the RHS of j. Completely ignore the occurrences of j, don't compute their join arity.

I thought about it a bit. This should yield precisely the same analysis result, right? (In particular, when analyzing a join point j, then the incoming arity of j should always be the incoming arity of the whole join j = … in …, plus the arity of j itself, so once we are past the lambdas on the RHS of the j, we have – as you say – the same informatin. Furthermore, the join point is called once.). So adding this code would (potentially) cut some corners, but it adds complexity to the code without any gain in precision. So unless this there is a compiler performance bottle neck to be fixed, that does not seem to really be a good trade off, does it?

(We could omit setting the call arity on join points, or – as now – ignoring it in the simplifier. Doesn’t seem to make a big difference either way.)

[simonpj]

I think that's true. I'm not certain about the Rec case though. Conceivably the direct approach might do better? Maybe not, I'm not sure.

Doing it directly just seems a bit more ... direct. But I don't feel strongly. A Note at least?

Regardless I certainly think it'd be better not to set a call-arity on a join point, instead of messing about in the simplifier (which is really innocent).

[nomeata]

But I don't feel strongly. A Note at least?

Me neither. Direct is nice, less code is nice. I’ll add a note, and not set the call arity annotation.

(Although it is debatable whether the simplifier is really innocent. The annotation is *true* even on join points; it is the simplifier that is stubbornly (but with good reason) refusing to eta-expand the join point!)

[nomeata]

I’ll add a note, and not set the call arity annotation.

(Although it is debatable whether the simplifier is really innocent. The annotation is *true* even on join points; it is the simplifier that is stubbornly (but with good reason) refusing to eta-expand the join point!)

I have a patch that does this, but I don’t like it. The Call Arity analysis uses the idCallArity fields internally as well (in particular callArityRecEnv reads it), and if I don’t set the Call Arity annotation, then things can go wrong. Some refactoring of the analysis could avoid this, of course, but given that the call arity annotation is not *wrong* on join points, I do not see the advantage of special-casing join-points here.

Also zapping the call arity information in the simplifier is the right thing to do in any case. So the current state of affair seems fine with me.

I did add a Note, though.

[Joachim Breitner <mail@…>]

In 87377f74/ghc:

Add a Note [Call Arity and Join Points]

as discussed in #13479.