Exponential inlining in the Simplifier (again)
Consider this program:
{-# OPTIONS_GHC -fno-cse #-}
module Foo where
{-# NOINLINE f0 #-}
f0 x y = x+y
f0, f1, f2 :: Int -> Int -> Int
f1 x y = h (f0 x y) (f0 y x) (x+1)
f2 x y = h (f1 x y) (f1 y x) (x+1)
f3 x y = h (f2 x y) (f2 y x) (x+1)
f4 x y = h (f3 x y) (f3 y x) (x+1)
f5 x y = h (f4 x y) (f4 y x) (x+1)
f6 x y = h (f5 x y) (f5 y x) (x+1)
f7 x y = h (f6 x y) (f6 y x) (x+1)
f8 x y = h (f7 x y) (f7 y x) (x+1)
f9 x y = h (f8 x y) (f8 y x) (x+1)
h :: Int -> Int -> Int -> Int
h x y z = x+y+z
main = f9 3 4
Every call is "boring", and so does not inline as we simplify f0, f1, f2, etc.
BUT when we get to main
, the call to f9
is non-boring so we inline f9
.
And now both calls to f8
are non-boring, so we inline them.
Result: we inline everything: exponential behaviour: a 512-deep nested case expression!
(The -fno-cse
is to stop CSE getting rid of most of those cases, hiding the problem.)
This kind of program doesn't seem to happen in practice, except perhaps with join points which we treat specially anyway. But it's bad that GHC can give this exponential behaviour, so I thought I'd make a ticket with a nice small repro case to demonstrate it.
Possible cures
We have (or soon will have) seInlineDepth
. We could stop inlining at some depth.
Then we'd get something like
f4 x y = ...
main = ...lots of calls to f4....
To stop the cascade starting again in the next iteration of the simplifier we'd have to add a penalty for having lots of calls: lots of calls make something less eager to inline, somehow.