make INLINE work for recursive definitions (generalized loop peeling/loop unrolling)

[claus]

Inlining refers to the unfolding of definitions, ie replacing uses of identifiers with the definitions bound to them. Doing this at compile time can expose potential for other optimizations. As described in the User Guide, this is currently limited to non-recursive definitions, to avoid non-terminating recursion in the inliner. Unfolding Recursions

Since many definitions in non-trivial programs are either recursive themselves or are built from recursion combinators, leaving recursion out of inlining alltogether is a serious limitation, especially in view of the encoding of loops via tail recursion. In conventional languages, loop transformations such as loop unrolling are at the heart of optimizing high performance code (for a useful overview, see Compiler Transformations for High-Performance Computing, ACM Computing Surveys, 1994). As a consequence, many performance-critical Haskell programs contain hand-unrolled and hand-peeled recursions, which is error-prone and obscures declarative contents.

More details, examples, and an informal spec: wiki:Inlining

[augustss]

See also #2353. Using INLINE doesn't even always force inlining normally. So even carefully crafted INLINE pragmas will not help because ghc thinks it's more clever than I and refuses to inline (thereby missing other optimisation opportunities).

[simonpj]

I have a months-old project, now so-nearly complete, to make INLINE do what it says, and be much easier to morph to explore other possibilities. Stay tuned.

Simon

[batterseapower]

Implemented as a compiler plugin ( http://github.com/batterseapower/unroll-plugin/tree/master). Has some unfortunate limitations:

• Annotations can only occur on top level things, so we can't unroll local definitions
• Ugly annotation syntax :-)
• If your functions require dictionaries, the annotated functions sometimes don't 'look' recursive before the simplifier / specialiser has had a go at them, because they call directly into a recursive worker. Workaround: always give your functions monomorphic types! I've tried to avoid this by simplifying a bit before we hit the unroller, though.