HaskellImplementorsWorkshop/2011/Heijer

Improving the GHC inliner: Smart loop breaker choice (Bas den Heijer)

Inlining recursive functions can be tricky business: the inliner should take care not go in an infinite loop inlining the same functions again and again. The GHC inliner deals with this problem by marking some functions as "loop breakers", which may never be inlined. Obviously there needs to be at least one loop breaker on each cycle of function calls, but we like to have as few loop breakers as possible. GHC currently uses a simple heuristic to choose breakers and makes little effort to be smart about it (breaking multiple cycles with one breaker is smart). The problem of finding the smallest set of breakers that would break all recursion cycles in a nest of functions is actually almost equivalent to the Directed Feedback Vertex Set problem, which is well studied. For my master's thesis I've built an algorithm that can find such a minimum set. Doing this for the real-nofib benchmark program takes about 2 seconds (compiling the programs with the current compiler with -01 takes 59 seconds on the same computer). A crude implementation in GHC 7.0.2 seem to yield a runtime decrease of about 1.5% in the nofib benchmark suite, without increasing binary sizes noticeably.