2008/6/22 Simon Peyton-Jones
| 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