Opened 10 months ago

Last modified 9 days ago

#15091 new task

Better occurrence analysis for join points

Reported by: simonpj Owned by:
Priority: normal Milestone: 8.10.1
Component: Compiler Version: 8.2.2
Keywords: JoinPoints Cc: sgraf, runeks
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Consider this

let x = ... in
join j y = x+y in
case v of
  A -> x
  B -> j 1
  C -> j 2
  D -> 3

What does OccAnal say about x's usage? It says ManyOccs!

But it's plain as a pikestaff that x is used at most once:

  • Either in the A branch,
  • or in the B or C branches via j.

If instead we had inlined j we'd have

let x = ... in
join j y = x+y in
case v of
  A -> x
  B -> x + 1
  C -> x + 2
  D -> 3

and now it's all more obvious: x's occurrence info should be OneOcc { occ_one_br = False }, not ManyOccs.

Does this matter? Not a great deal, but there is a reason for having OneOcc with occ_one_br = False, and it seems a shame not to take advantage.

One case in point is the definition of `SimplUtils.isExitJoinId

isExitJoinId :: Var -> Bool
isExitJoinId id = isJoinId id && isOneOcc (idOccInfo id) && occ_in_lam (idOccInfo id)

Something does not cease to be an exit-join-point if it is mentioned in multiple places as above.

Another use for this info is postInlineUnconditionally.

Could we improve this situation? I think it'd be quite easy. For non-recursive join points j = rhs

  • Gather occurrence info from the RHS
  • Bind j to its occurrence info
  • Unleash that occurrence info at each jump-site for j, just as if it had been inlined.

See Trac #14152, comment:40.

Change History (4)

comment:1 Changed 10 months ago by sgraf

Cc: sgraf added

Sounds a lot like how the demand analyser always uses LetDown to handle join points. Note [Demand analysis for join points] might be relevant.

I found that occurrence analysis, usage analysis and call arity (to an extent) are strongly related, as they all try to compute max cardinality info. So they should agree on how to handle join points. ticket:13479#comment:10 hints about this for Call Arity. Appearently, Note [Call Arity and Join Points] explains we currently don't do this because of complexity concerns, probably because Call Arity has no analogue of LetDown.

comment:2 Changed 8 months ago by bgamari

Milestone: 8.6.18.8.1

These won't be addressed for GHC 8.6.

comment:3 Changed 8 weeks ago by osa1

Milestone: 8.8.18.10.1

Bumping milestones of low-priority tickets.

comment:4 Changed 9 days ago by runeks

Cc: runeks added
Note: See TracTickets for help on using tickets.