A Study of Irreducibility in C Programs

Compilers use a variety of techniques to optimize and Transform loops. However, many of these optimizations do not work when the loop is irreducible. Node splitting techniques transform irreducible loops into reducible loops, but many real-world compilers choose to leave them unoptimized. This article describes an empirical study of irreducibility in current versions of open-source software, and then compares them with older versions. We also study machine-generated C code from a number of software tools. We ?nd that irreducibility is extremely rare, and is becoming less common with time. We conclude that leaving irreducible loops unoptimized is a perfectly feasible future-proof option due to the rarity of its occurrence in non-trivial software. Copyright q 2011 John Wiley & Sons, Ltd.