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
foo
will 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
foo
from 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 inmain
is one with two args. Thus, upon analysingbar
's RHS, it has to assume that\xs
can 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.