Better analysis of loop exits

See also !9479 (comment 466884)

Problem

Consider this code, which comes from bcp_generator in nofib/imaginary/paraffins, just before Phase=0 simplification.

(\a b. case a of                )
(        [] -> b                ) a (go xs)
(        (a:as) -> foldr k  b as)

This will beta-reduce to

let b = go xs
in case a of
     [] -> b
     (a:as) -> foldr k b as

Now because of Note [Inline small things to avoid creating a thunk] in GHC.Core.Opt.Simplify.Utils, we'll inline that b to give

case a of
  [] -> go xs
  (a:as) -> foldr k (go xs) as

We'd duplicated the (go xs) into two branches, but it's small, and we thereby avoid allocating it on the [] path.

But suppose we take the original expression and simplify the lambda first, inlining foldr. (The "make rules win" MR !8897 (merged) has precisely this effect.):

(\a b. case a of                                    )
(        [] -> b                                    ) a (go xs)
(        (a:as) -> letrec go vs = case vs of        )
(                                    [] -> b        )
(                                    (v:vs) -> ...  )
(                   in go as                        )

Now b occurs under a lambda, so Note [Inline small things to avoid creating a thunk] doesn't work; so we end up allocating b on both paths, rather than just in the (a:as) case. Although the saving is in the cold path, in the paraffins benchmark, that somehow meant that a letrec didn't turn into a joinrec -- I'm not quite sure why.

It turned out (again see !8897 (merged)) that a similar small regression in nofib/spectral/cryptarithm2 had precisely the same cause.

Opportunity

The optimiser should not be so fragile. Given:

  let exit = blah   -- Unnecessary allocation!
  in letrec go vs = case vs of
                     []     -> exit
                     (v:vs) -> ...   -- go is not necessarily tail-called
  in ...(go xs)...  -- Not necessarily a tail call!

we wan to spot that exit is evaluated only on the exit of the loop, and inline exit at its occurrence site:

  letrec go vs = case vs of
                     []     -> blah
                     (v:vs) -> ...
  in ...(go xs)...  -- Not necessarily a tail call!

This is higly reminiscent of what the Exitification pass does -- except that go is not a join point.

Idea 1. Surely demand analysis shoud spot that exit is evaluated at most once -- and that's why it can be inlined under a lambda. @sgraf812

Idea 2. Occurrence anaysis already identifies join points. Perhaps it could be modified to identify exits lithe one above, and switch off the "inside lambda" flag on their OccInfo.

• The recursive calls don't have to be join points, but they must be saturarated, and no more than one in each branch of a case.
• The calls in the body of the letrec don't have to be join points, but again they must be saturated, and no more than one in each branch of a case.
• The occurrence of exit must be in tail position. E.g. this is no good:

  let xit = blah
  in letrec go xs = case xs of
                       [] -> e1
                       (x:xs) -> xit + go xs

Nota bene:

• FloatOut might float blah out again if we aren't careful!
• If we had Idea 2, maybe that would strictly subsume the entire exitification pass?