Opened 3 years ago

Closed 3 years ago

#13221 closed bug (fixed)

OccurAnal fails to rediscover join points

Reported by: lukemaurer Owned by: lukemaurer
Priority: high Milestone: 8.2.1
Component: Compiler Version: 8.1
Keywords: JoinPoints Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D3080
Wiki Page:

Description (last modified by simonpj)

Ben writes: I've noticed that a new WARN in OccurAnal seems to be quite loud. Validations now produce thousands of lines of the form,

WARNING: file compiler/simplCore/OccurAnal.hs, line 2633
  OccurAnal failed to rediscover join point(s): [$j_shTG]
WARNING: file compiler/simplCore/OccurAnal.hs, line 2633
  OccurAnal failed to rediscover join point(s): [$w$j_sl22]
WARNING: file compiler/simplCore/OccurAnal.hs, line 2633
  OccurAnal failed to rediscover join point(s): [$w$j_sl1W]
WARNING: file compiler/simplCore/OccurAnal.hs, line 2633
  OccurAnal failed to rediscover join point(s): [$w$j_sl1Q]

It is not clear why the warning from OccurAnal about rediscovering join points is ever firing. There's one circumstance I can think of, namely the special typing rule allowing jumps from β-redexes, but the warning fires repeatedly and β-redexes don't survive the simplifier.

This isn't hard evidence of something wrong, but it is deeply suspicious.

Change History (7)

comment:1 Changed 3 years ago by dfeuer

Milestone: 8.4.1

Can you please try to provide a test case, and an explanation of why this may be a problem?

comment:2 Changed 3 years ago by simonpj

Description: modified (diff)
Milestone: 8.4.18.2.1
Priority: normalhigh

Let's at least investigate before releasing 8.2. It's extremely fishy.

comment:3 Changed 3 years ago by lukemaurer

Differential Rev(s): D3080
Status: newpatch

Found two causes:

  • In several files, the problem was a mistake with occurrence-analyzing rules:
let $sj = \y ys -> ...
    {-# RULES "SC:j" forall y ys. j (y:ys) = $sj y ys #-}
    j = \xs -> ...
    in ...

Here j can be a join point of join arity 1. Since its rule matches exactly one argument (same as the join arity), the body of its RHS can contain tail calls (see Note [Rules and join points] in OccurAnal). Thus $sj can also be a join point, since its only occurrence is a tail call with two arguments.

But by mistake, OccurAnal is counting the binders of the rule, not the arguments on its RHS; since there are two binders and j's join arity is 1, $sj gets rejected as a potential join point.

The warning appears because in the case that j is a join point to begin with and SpecConstr specializes it, $sj will be created as a join point, so if OccurAnal doesn't think it can be a join point it issues the warning.

  • In T7796, the problem is that we're zapping too much when looking at stable unfoldings; we should be allowing unfoldings for join points to have tail calls.
let j1 = \x -> ...
    j2 [Unf=\y -> j1 y]
    j2 = \y -> j1 y
in ... j2 a {- tail call -} ...

Here both j1 and j2 should be made join points, but to know that we have to see that the call to j1 from the unfolding of j2 is a tail call. Again, the warning arises from a join point getting specialized; if j1 is a specialization of j2, failing to discover j1 as a join point produces the warning.

Submitted a patch to Phab. This doesn't fix all the instances of the warning, but it fixes the noisy ones that show up in test cases. (The remaining source of noise is beta redexes arising from the simple optimizer; that's an ongoing issue. Fortunately, when that causes a warning, it'll only show up once before the simplifier gets rid of the beta redex.)

comment:4 Changed 3 years ago by Ben Gamari <ben@…>

In 795bc49c/ghc:

Fixes for OccurAnal bugs (#13221)

- OccurAnal: When checking tail calls, count rule's LHS args, not bndrs
Pretty obvious error in retrospect:
```
let $sj = \y ys -> ...
    {-# RULES "SC:j" forall y ys. j (y:ys) = $sj y ys #-}
    j = \xs -> ...
    in ...
```
A jump on the RHS of a rule for a join point is only okay if the rule's
LHS is
saturated - in this case, since the LHS is j (y:ys) and j takes one
argument,
both j and $sj can become join points. See Note [Rules and join points]
in
OccurAnal. By mistake, OccAnal was counting the rule's binders (y and
ys) rather
than the args in its LHS, so $sj wasn't being made a join point.

- Don't zap tail calls in unfoldings

This was causing T7796 to squeal about join points not being
rediscovered.

Reviewers: bgamari, austin

Reviewed By: bgamari

Subscribers: thomie

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

comment:5 Changed 3 years ago by simonpj

The remaining source of noise is beta redexes arising from the simple optimizer; that's an ongoing issue

I'm working on that.

Are there any other join points that occur-anal doesn't find?

comment:6 Changed 3 years ago by bgamari

Differential Rev(s): D3080Phab:D3080

comment:7 Changed 3 years ago by bgamari

Resolution: fixed
Status: patchclosed

I believe this was resolved in 795bc49ceb12cecf46e0c53a570809c3df85ab9a.

Note: See TracTickets for help on using tickets.