Lack of eta expansion in NoFib's fft2
According to what I wrote in my Master's thesis a few years ago, the following example is inspired by NoFib's fft2 benchmark:
foo :: ([a] -> [a]) -> [a] -> [a]
foo f a = f a
{-# NOINLINE foo #-}
bar :: Int -> [Int] -> [Int]
bar n =
let bar' = bar (n-1) in
if sum [0..n] < 10
then \xs -> 10:xs
else \xs -> foo bar' xs
main = print ( bar 1 [2])
The point here is that even though bar has arity 1 as written, it could be eta-expanded: Assuming we'd eta-expand bar, the sharing of the pap bar' turns out unnecessary, because foo will call bar' only once, with one arg.
Neither Call Arity nor Demand Analysis is able to detect that:
- Call Arity doesn't see that
foowill callbar'only once, because it doesn't have a signature mechanism. Neither could it, because it analyses let body before RHS. - Demand Analysis computes a signature for
foofrom which it can tell thatbar'is only called once with one arg (MCM(L)). But likewise, it analysesbar's RHS before looking at how it's used. Thus, it doesn't see that the only external call inmainis one with two args. Thus, upon analysingbar's RHS, it has to assume that\xscan be entered many times, each of which might result in one call to the PAPbar'. Thus to DmdAnal, it appears as ifbar'is shared, which prohibits eta-expansion ofbar.
The DmdAnal variant of my Master's thesis was able to eta-expand bar. I believe !5349 is able to do so, too, but I can't tell at the moment because I don't have it checked out and built at the moment.
Simon and I are working on a way to do the same in a way that is explainable to someone else.