loopbreaker: inline self-recursive definitions

[ bsd3, library, plugin ] [ Propose Tags ]

Please see the README file on Github for more info


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.1.0, 0.1.1.1
Change log ChangeLog.md
Dependencies base (>=4.7 && <5), containers (>=0.6 && <0.7), ghc (>=8.6 && <8.9), syb (>=0.7 && <0.8) [details]
License BSD-3-Clause
Copyright 2019 Matej Nižník, 2019 Sandy Maguire
Author Matej Nižník, Sandy Maguire
Maintainer matten@tuta.io
Category Plugin
Home page https://github.com/polysemy-research/loopbreaker#readme
Bug tracker https://github.com/polysemy-research/loopbreaker/issues
Source repo head: git clone https://github.com/polysemy-research/loopbreaker
Uploaded by TheMatten at 2019-10-04T18:34:54Z
Distributions
Reverse Dependencies 1 direct, 78 indirect [details]
Downloads 1512 total (7 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2019-10-04 [all 1 reports]

Readme for loopbreaker-0.1.1.1

[back to package description]

loopbreaker

Performance of libraries like polysemy depends on code being aggresively inlined. Problem is that GHC is not very keen on inlining self-recursive definitions. Luckily, there's a way we can trick compiler to do so: by introducing intermediate loopbreaker that simply calls our original function:

fact :: Int -> Int
fact 0 = 1
fact n = n * fact' (n - 1)
{-# INLINE fact #-}

fact' :: Int -> Int
fact' = fact
{-# NOINLINE fact' #-}

But because this is ugly boilerplate nobody wants to write, we created GHC plugin that searches for such recursive definitions and automatically inserts loopbreakers during compilation.

To quote isovector:

As described in Writing Custom Optimization Passes, The polysemy-plugin has had support for creating explicit loopbreakers for self-recursive functions. The result is pretty dramatic code improvements in a lot of cases when -O2 is turned on.

Rather embarrassingly, after publishing that post, it turned out that my implementation didn't in fact improve optimizations. Sure, it spit out the correct code, but it was being done too late, and some special analysis passes had already run. The result: we'd generate loopbreakers, but they wouldn't be used.

TheMatten took it upon himself to fix this. There's no trick --- just do the same transformations after renaming, rather than after typechecking. We realized this plugin is useful outside of polysemy, so it's been released as a standalone package.

Usage

Add -fplugin=Loopbreaker into your package.yaml or specific module. This will cause the plugin to generate explicit loopbreakers for any self-recursive functions marked as INLINE, which can dramatically improve their performance. See documentation for more info.