Recursive functions and constant parameter closures (inlining/strictness analyzer question)

[Max Bolingbroke]

2008/6/22 Simon Peyton-Jones <simonpj at microsoft.com>:
> | However, if I had to pick something out of the air, I'd say this: always do
> | SAT when the argument in question is a function.
>
> Yes, that might well be a good heuristic to try, if you are interested to pursue this, Max.  Making the function static means that it may be inlined, and that can make a tremendous difference by specializing the loop for that particular function. But that in turn only tends to happen if the enclosing function is inlined.  Consider foldr: the real payoff comes when foldr is inlined, so that the function at the call site becomes visible.

I spent quite a bit of time today playing with various heuristics for
the SAT including the one suggested above (which I agree sounded
promising) but didn't make much progress. The best results were
obtained by applying the SAT when:
1) At least two arguments are static, whatever their types
2) Or if at least one of the static arguments is a function type and
the SATed functions right hand side is small enough to inline
3) As long as the function is not likely to be compiled as a tail call
(because we effectively get staticness there by carrying arguments on
the stack)

If you just use criteria 2 then you get some bad worst cases in
runtime (e.g. Para.dropTail and Constraints.initTree) because the
additional inlining opportunity was not utilised enough to overcome
the heap allocation cost. If you don't SAT functions that have only
non-function static arguments then some other worst cases crop up
(e.g. Rsa.power) where we actually quite want to do it.

However this represents only a 0.3% decrease in allocations and
runtime from the previous heuristic for nofib! Furthermore, it was
necessary to run the SAT twice in the compiler pipeline to catch both
those functions that only become tail calls after e.g. the let-to-case
transform AND to identify the extra common subexpressions producted by
SAT early enough that they could have good use made of them by later
compiler passes.

I'm not particularly happy with the tail call criterion because it's
quite fragile to make inferences about how the function will be
treated by codegen as early in the pipeline as SAT is running. So in
summary I don't think this change is worth integrating.

Cheers,
Max