The most important task of a compiler designed to exploit
instruction-level parallelism (ILP) is instruction scheduling. If
higher levels of ILP are to be achieved, the compiler must use, as the
unit of scheduling, regions consisting of multiple basic
blocks--preferably those that frequently execute consecutively, and
which capture cycles in the program's execution. Traditionally,
compilers have been built using the function as the unit of
compilation. In this framework, function boundaries often act as
barriers to the formation of the most suitable scheduling regions.
Function inlining may be used to circumvent this problem by assembling
strongly coupled functions into the same compilation unit, but at the
cost of very large function bodies. Consequently, global
optimizations whose compile time and space requirements are
superlinear in the size of the compilation unit, may be rendered
prohibitively expensive. This paper introduces a new approach, called
region-based compilation, wherein the compiler, after inlining,
repartitions the program into more desirable compilation units, termed
regions. Region-based compilation allows the compiler to control
problem size and complexity while exposing inter-procedural
scheduling, optimization and code motion opportunities.