Strictness analyser missing useful strictness

[simonpj]

Roman Beslik (beroal@…) writes: I provide a sample program which causes a strange behavior of strictness analyzer.

variant 1

module StrictUnusedArg (main) where
f2 :: Int -> Int -> Int
f2 x1 = if x1 == 0 then (\x0 -> x0) else let
     y = x1 - 1
     in f3 y y
f3 :: Int -> Int -> Int -> Int
f3 x2 = if x2 == 0 then f2 else let
     y = x2 - 1
     in f4 y y
f4 :: Int -> Int -> Int -> Int -> Int
f4 x3 = if x3 == 0 then f3 else let
     y = x3 - 1
     in \x2 x1 x0 -> f4 y x2 x1 (y + x0)
main = print (f2 100 0)

I expect that all arguments will be unboxed. "-ddump-simpl" reveals that actually types are

f2 :: Int# -> Int -> Int
f3 :: Int# -> Int -> Int -> Int

So when "f3" calls "f2" it unboxes the argument named "x1" and when "f2" calls "f3" it boxes the argument named "x1". "-ddump-stranal" knows strictness only for the "x2" of "f3" and "x1" of "f2".

f2:
[Arity 1
  Str: DmdType U(L)]
f3:
[Arity 1
  Str: DmdType U(L)]

I also can force the analyzer to think that "x1" and "x0" are strict by eta-expanding "f3": variant 2

f3 x2 x1 x0 = if x2 == 0 then f2 x1 x0 else let
     y = x2 - 1
     in f4 y y x1 x0

"-ddump-stranal" yields:

f3:
[Arity 3
  Str: DmdType U(L)U(L)U(L)m]
f2:
[Arity 2
  Str: DmdType U(L)U(L)m]

I even do not use ($!). So, the questions: Is it possible to change the strictness analyzer so it will treat "variant 1" as "variant 2"? Are these changes big?

Compiled with options:

$ ghc --make -fstrictness -fPIC -O3 -fforce-recomp blah-blah-blah
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.12.1

[simonpj]

Max Bolingbroke responds: There seem to be two issues here.

1. GHC only figures out and records strictness information on lambdas that are syntactically together. I'm not sure how hard it would be to change this, but probably not totally straightforward.

2. GHC does not seem to be eta-expanding as much as it could get away with. Generally eta expansion has the following effects:
   • Decreases work sharing, by pushing let-binding and case decomposition within the lambda
   • Increases the efficiency of function calls and of the strictness analyser by pushing together several lambdas

In this case the work that would be lost by eta expanding looks pretty minimal (its generally very cheap primops that we could easily recompute). However, to spot that this is actually safe GHC has to eta-expand all of the "f" functions simultaneously, because they are mutually recursive, and it turns out that their "cheapness" depends on the "cheapness" of every other function in the loop. The simplifier is not smart enough for this - you need a fixed point analysis.

I did toy with an arity analysis that has been proposed to spot such opportunities, but I found that it could in some cases lose unbounded amounts of ostensibly "cheap" work - and it didn't seem to have much effect on nofib anyway, so this went nowhere.

Looking at the Core, I think that if the arities were fixed up the strictness analyser would do the Right Thing here - so this might be another vote for an arity analysis :-) (See the "Arity" section of  http://hackage.haskell.org/trac/ghc/wiki/Status/SLPJ-Tickets - it might be worth filing a bug on GHC Trac with your nice simple example too).

Out of curiosity, did you spot this in a real program?