Optimal Loop Breaker Choice for Inlining

Abstract

When inlining recursive functions care must be taken to ensure termination of the inliner. The Glasgow Haskell Compiler does this by choosing a loop breaker (which may never be inlined) for each recursion loop in the program. These breakers are currently chosen by a simple heuristic which makes little effort to minimise the number of breaker vertices chosen, even though there are several cases where a smarter choice of of a set of loop breaker vertices can be much smaller. In this paper we apply algorithmic techniques (related to the Directed Feedback Vertex Set and Feedback Arc Set) to determine the minimum size set of breakers necessary to break every loop. Our approach requires significantly fewer loop breakers.