Opened 9 years ago

Closed 15 months ago

Last modified 15 months ago

#3123 closed feature request (invalid)

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

Reported by: claus Owned by:
Priority: lowest Milestone:
Component: Compiler Version: 6.11
Keywords: Cc: batterseapower@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by bgamari)

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:OldInlining

Change History (20)

comment:1 Changed 9 years ago by igloo

difficulty: Unknown
Milestone: 6.12 branch

comment:2 Changed 9 years ago by 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).

comment:3 Changed 9 years ago by 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

comment:4 Changed 8 years ago by batterseapower

Cc: batterseapower@… added

comment:5 Changed 8 years ago by 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.

comment:6 Changed 7 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:7 Changed 7 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:8 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:9 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:10 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:11 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:12 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:13 Changed 3 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:14 Changed 3 years ago by thomie

Type of failure: Runtime performance bug

comment:15 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:16 Changed 3 years ago by thoughtpolice

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:17 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:18 Changed 21 months ago by thomie

Milestone: 8.0.1

comment:19 Changed 15 months ago by mpickering

Resolution: invalid
Status: newclosed

I'm going to close this as it isn't exactly clear what the suggestion is. Currently recursive definitions can be inlined but loop breakers are not inlined.

comment:20 Changed 15 months ago by bgamari

Description: modified (diff)
Note: See TracTickets for help on using tickets.