Runaway inlining
Summary
Consider the following simple function:
runawayInlining :: [a] -> (a -> Bool) -> [a]
runawayInlining a predicate =
[x | x <- a ++ a, predicate x]
Under ghc 8.8.4 (-O2) we get the following core:
runawayInlining
= \ (@ a_a8Sd)
(a1_a6Lh :: [a_a8Sd])
(predicate_a6Li :: a_a8Sd -> Bool) ->
let {
z_ia9e :: [a_a8Sd]
[LclId]
z_ia9e
= letrec {
go_ia9f [Occ=LoopBreaker] :: [a_a8Sd] -> [a_a8Sd]
[LclId, Arity=1, Str=<S,1*U>, Unf=OtherCon []]
go_ia9f
= \ (ds_ia9g :: [a_a8Sd]) ->
case ds_ia9g of {
[] -> ghc-prim-0.5.3:GHC.Types.[] @ a_a8Sd;
: y_ia9l ys_ia9m ->
case predicate_a6Li y_ia9l of {
False -> go_ia9f ys_ia9m;
True ->
ghc-prim-0.5.3:GHC.Types.: @ a_a8Sd y_ia9l (go_ia9f ys_ia9m)
}
}; } in
go_ia9f a1_a6Lh } in
letrec {
go_ia9f [Occ=LoopBreaker] :: [a_a8Sd] -> [a_a8Sd]
[LclId, Arity=1, Str=<S,1*U>, Unf=OtherCon []]
go_ia9f
= \ (ds_ia9g :: [a_a8Sd]) ->
case ds_ia9g of {
[] -> z_ia9e;
: y_ia9l ys_ia9m ->
case predicate_a6Li y_ia9l of {
False -> go_ia9f ys_ia9m;
True ->
ghc-prim-0.5.3:GHC.Types.: @ a_a8Sd y_ia9l (go_ia9f ys_ia9m)
}
}; } in
go_ia9f a1_a6Lh
So we get two copies of the inner loop (function go_ia9f) which differ on what they return if the input list is empty -- besides that they are identical. Unfortunately this pattern continues indefinitely, i.e. if we change the function to append 'a' n times (as in a ++ a ++ ... ++ a) we get n "different" 'go' functions -- no inlining limit kicks in and we end up with lots and lots of code. The fact that 'a' is repeated does not make a difference -- the same thing happens if we were appending different lists together.
Steps to reproduce
As described above.
Expected behavior
Either come up with a different approach to compiling this or have some internal inlining limit kick in at some point to stop generating so much code.
Instead of n copies of the "go" function, could we not build n closures here (parametrized over what we return in the empty list case) and thus keep only one copy of the function? This would involve allocation but what we have now seems excessive.
Environment
- GHC version used: 8.8.4
Optional:
- Operating System: Ubuntu