arXiv:cs/0604043v1 [cs.DC] 11 Apr 2006

Demand-driven Inlining in a Region-based Optimizer for ILP
Architectures
Thomas P. Way
Department of Computing Sciences
Villanova University, Villanova, PA 19085
thomas.way@villanova.edu
Lori L. Pollock
Department of Computer & Information Sciences
University of Delaware, Newark, DE 19716
pollock@cis.udel.edu
September 25, 2017
Abstract
Region-based compilation repartitions a program into more desirable compilation units using profiling information and procedure inlining to enable region formation analysis. Heuristics play a key role in
determining when it is most beneficial to inline procedures during region formation. An ILP optimizing
compiler using a region-based approach restructures a program to better reflect dynamic behavior and
increase interprocedural optimization and scheduling opportunities. This paper presents an interprocedural compilation technique which performs procedure inlining on-demand, rather than as a separate
phase, to improve the ability of a region-based optimizer to control code growth, compilation time and
memory usage while improving performance. The interprocedural region formation algorithm utilizes
a demand-driven, heuristics-guided approach to inlining, restructuring an input program into interprocedural regions. Experimental results are presented to demonstrate the impact of the algorithm and
several inlining heuristics upon a number of traditional and novel compilation characteristics within a
region-based ILP compiler and simulator.

1

Introduction

Advanced instruction-level parallel (ILP) computer architectures require aggressive and potentially costly
whole program, or interprocedural, techniques for program analysis and optimization to fully exploit available parallelism. These interprocedural techniques are in contrast to intraprocedural code improvement
techniques employed in a traditional procedure-oriented compiler, where analysis and optimization phases
are independently applied to each procedure in isolation. [1]
An approach for ILP that reduces the cost of aggressive interprocedural analysis and optimization is
region-based compilation [20]. Region-based compilation is a generalized trace selection approach that partitions a program into units of compilation, or regions, based on profile information. Using procedure inlining,
where a procedure callsite is replaced by the body of the called procedure, and restructuring a program
into regions, the region-based compiler can perform code motion and other analyses and optimizations interprocedurally, while maintaining control over the compilation unit size and content. Unlike procedure-based
compilation, region-based techniques bound the compilation unit size to better control optimization costs [20].
The key component of a region-based compiler is the region formation phase which partitions the program
into regions using profile-guided heuristics with the intent that the ILP optimizer will be invoked with a scope
that is limited to a single region at a time. Thus, the quality of the generated code depends greatly upon
the ability of the region formation phase to create regions that a global optimizer can effectively transform
in isolation for improved ILP. Because region-based compilation relies on an initial aggressive inlining phase,
1

region formation remains quite costly, particularly for large programs with many procedures and calls [20].
Selective use of inlining can prevent excessive code growth and control register pressure while improving
analysis opportunities and performance [7].
In this paper, a strategy to overcome the issues caused by separate inlining and region formation phases
is described and evaluated. Presented is a demand-driven approach to inlining and a set of inlining heuristics which are integrated within a region-based optimizer. To evaluate these techniques, the algorithm and
various heuristics for guiding inlining decisions have been implemented within the Trimaran ILP research
compiler [28]. In addition to standard metrics such as compilation time, code growth and execution time,
novel metrics have been devised to compare the characteristics of regions, such as profile homogeneity and
interprocedural scope, to measure the effectiveness of this new approach.

2

Region-based Compilation

A common characteristic of compiler analysis techniques, including those specifically for ILP architectures,
is that they have been designed with the assumption that the original procedure boundaries created by the
programmer are immutable. Procedures serve as the de facto unit of compilation. As a result, there is the
potential for large procedures to either unacceptably increase compilation time or to be less aggressively
optimized (or not optimized at all) in order to control compilation costs and maintain scalability. Procedure
boundaries are a natural impediment to compilation effectiveness in many cases, requiring tradeoffs in terms
of quality of optimization versus compilation time and memory requirements.
Hank et al. [20] proposed the region-based compilation framework as a solution to the problem of exposing
interprocedural scheduling and optimization opportunities without the cost of very large procedure bodies
created through inlining, or the expense and complexity of sophisticated interprocedural analysis and code
motion. While it was shown to be especially beneficial in an ILP compiler, region-based compilation also can
achieve both interprocedural scope and scalability in program analysis.

2.1

Fundamental region formation

Figure 1 depicts the organization of a region-based compiler framework. The source code enters the Profiler,
where the source code is instrumented and executed to gather profile information which is then integrated
into the source code. Intermediate code with profiling information is input to the Aggressive Inliner phase,
where all inlining that can be done in the entire program, subject to some constraints, is performed. Next,
in the Region Formation phase, regions are formed throughout the whole program, and each region is
encapsulated as a procedure in the Encapsulation phase. The encapsulated regions are then passed to a
high-level Optimizer phase before Reintegration into their original procedures. The result is passed to the
Code Generator which includes a low-level optimization phase.
In this framework, a region is a collection of basic blocks and control flow edges selected for compilation
as a unit [20]. More formally, a region is a subgraph of the control flow graph (CFG) of a procedure, created
either based on the structure of the CFG or using profile information. Each region is encapsulated in a
single-entry, single-exit CFG by adding dummy prologue and epilogue CFG nodes and boundary condition
CFG nodes that convey pertinent data flow information. Regions are encapsulated in such a way that the
optimizer can be invoked with a scope that is limited to a given region, which then appears to the rest of the
compiler as a procedure. Side entries into regions can be removed by tail duplication, similar to superblock
formation [22]. After optimization, each region is reintegrated into the original procedure in which the region
existed by updating changes in data flow conditions, entry and exit points, and constraints on register
allocation. Code is generated from the reintegrated procedure.

2.2

Example

The original profile-sensitive region formation algorithm is comprised of the following steps, performed between aggressive inlining and region encapsulation. These steps are performed until all blocks in the program
have been included in some region. Figure 2 shows the results of performing the following steps of the algorithm. Figure 2(b) shows the code after aggressive inlining is performed on the code in Figure 2(a).
2

Source Program

Scanner

Profiler

Parser

Aggressive Inliner

Intermediate
Code Generator

Region Formation
call

Encapsulation
region

Optimizer

Reintegration
Code Generator
Target Program

Figure 1: Original region-based compilation framework. [20]
Step 1: Seed Selection - From among all basic blocks in the procedure not yet included in a region, select
the block with the highest execution frequency; this is the seed block for a new region. In this simplified
example, this is block 8, shown in Figure 2(b). Note that inlining was done previously.
Step 2: Region Expansion to Successors - A path of desirable successors is selected, starting at the
seed block. Region expansion is guided by heuristics which halt the growth under a set of conditions such
as [20]: (1) a procedure call is reached, (2) a minimum acceptable execution frequency for a successor block
is not met (e.g., at least 50% of the frequency of both its immediate predecessor in the region and that of
the seed block, which in this simplified example is why block 6 is not selected in this step), or (3) a region
size threshold (e.g., 200 basic blocks) is exceeded. The successors selected for seed block 8 are blocks 10, 11,
5 and 7.
Step 3: Region Expansion to Predecessors - A path of frequently executed predecessors to the seed
block is chosen analogous to the selection of desirable successors. The resulting path after this step is the
seed path of the region. In this case, blocks 2 and then 1 are added as predecessors of seed block 8.
Step 4: Region Expansion from All Blocks in the Seed Path - By selecting as above the desirable
successors of all current blocks in the region, the region is grown along multiple control flow paths. Thus,
block 3 is added to the region. The result of this step is a path-sensitive region. Blocks not yet in a region
(blocks 6 and 9) are used to form additional regions.
To summarize, three regions are formed in the example. The largest region consists of blocks 1, 2, 3,
5, 7, 8, 10, and 11. The remaining blocks 6 and 9 form single block regions. Note that original block 4
was replaced by the inlined procedure G. Limitations include the potential for excessive code growth and
unnecessary inlining due to the aggressive approach to inlining, leading to unscalability, and the training-data
effect of profile-guided compilation. While Hank’s approach can achieve scalability during program analysis
and optimization by allowing the compiler to control the size of regions, region formation is unscalable due
to aggressive inlining.

3

Region Formation Analysis with Demand-driven Inlining

Interprocedural regions that include instructions from more than one procedure enable region-based compilation to uncover optimizations missed due to procedure boundaries [20]. This section proposes an alternative
approach to building interprocedural regions which performs inlining on a demand-driven basis integrated
within region formation analysis is presented in this section. By delaying inlining decisions until region
formation analysis, the characteristics of inlined code can be better controlled, reducing code growth and
memory requirements. However, inlining performed in this demand-driven way introduces a number of issues
that are not present in existing region formation techniques; these issues are enumerated, and a technique is
3

proc F

11
00
00
11
1
00
11
00
11

990

proc G

1200

10

50

11

0
50

7

7
(a) Procedures F and G prior to
aggressive inlining.

(b) Procedure G is inlined into F.

0

0

81

5

5

8
9

00

10

1200

60

9

81

0

81

11

3

11
00
00
11
2
00
11
00
11
600
000
6 111
000
111
000
111
3
000
111
00
11
00
11
5
00
11
00
11
00
11
00
11
7
00
11
00
11
10

00

4

10

outside region

50

3

call
G

9

6

00

1200

00

600

6

600

60

2

8
60

10

2

00

8

00

50

990

successors
00
11
11
00
00
11
predecessors
00
11
00non-seed path
11
00
11

990

50

1500

0

1

1

0

1

seed

proc F

999

1

proc F

999

1

50

999

11
00
00
11
10
00
11

111
000
11
000
111
000
111

(c) Region formation is performed in new F.

Figure 2: Example of the steps in Hank’s region formation algorithm.
proposed to addresses them. In the remainder of this paper, the approach of aggressive inlining followed by
intraprocedural profile-sensitive region formation (i.e., Hank, et al.) is referred to as Phased region, and the
new demand-driven approach is called Demand region.

3.1

Challenges in Forming Interprocedural Regions

Major issues to consider in the design of Demand region are:
Issue 1. Inlining is driven by the demand placed at procedure callsites as regions are formed.
Callsites may be encountered as a most frequent successor or predecessor of a block on a path within the
current region being formed. The path selection process must determine at that point whether or not the
callee should be inlined, a decision dependent on the heuristics used to guide inlining. If the decision is
made to inline a procedure, it is inlined and region formation proceeds within the callee’s code. Thus,
interprocedural regions are identified by having the region formation process cross procedure boundaries by
inlining on demand.
Issue 2. Region formation analysis must deal with multiple calls to the same procedure as it
crosses procedure boundaries. While region formation on the flattened, aggressively inlined code of Phased region analyzes a distinct code segment for each callsite that has been inlined, region formation without
prior inlining analyzes the same code for a procedure’s body for each callsite to that procedure. Depending on
the context, a callee could be partitioned into different regions for different callsites. Demand region should
maintain separate information about a procedure for each inlinable callsite to that procedure, or partition
the procedure the same each time.
Issue 3. The ordering of procedures analyzed for region formation and inlining impacts compilation overhead. Performing demand-driven inlining can lead to large compilation and runtime memory
requirements similar to Phased region if the order in which inlining and region formation is performed is not
carefully considered. As a callsite is encountered in Demand region, the region formation algorithm begins
to form regions in the callee. Thus, the amount of code growth and the size of data structures needed during
region formation are dependent on the handling of the worklist of blocks for partitioning as region formation
crosses procedure boundaries.
Issue 4. Procedures may not be inlined at every callsite. While a procedure’s code is partitioned into
regions on demand at callsites, at some of those callsites the decision may be made not to inline, resulting
4

proc A

proc B

entry

proc C

11
00
entry
00
11
00
11
000
111
000
111
000
111

entry

00111100
01
0000
1111
0000
1111
000
111
000
111
11
00
call C
00
11
00
11

call B

111
000
000
111
000
111

1111
0000
0000
1111
0000
1111
0000
1111
0000
1111

exit

case 1: local C
only

exit

case 2: local B,
111
000
000
111
000entry region in C
111

exit

1111
0000
0000
1111
0000
1111

case 3: interproc.
pass-through B
case 4: local B,
exit region in C

Figure 3: Illustration of region classification for individual procedures.
in the procedure being partitioned into local regions in isolation of a calling context. Thus, a record of the
inlining of each procedure should be maintained to identify procedures that need to be processed in isolation
during region formation.
Issue 5. Total code growth is an imprecise limiting metric in Demand region since each region
will be analyzed and optimized separately. A limit on the memory requirements for Phased region
is achieved by restricting how large the program can grow in total size during the aggressive inlining pass;
however, individual procedures may be able to grow very large. This is problematic, since memory requirements during analysis are proportional to the size of the largest procedure. Demand-driven inlining can also
ensure that individual procedures do not grow excessively large by making use of heuristics that consider
the impact of inlining before it is performed.
Issue 6. Region formation may be partially completed in multiple procedures simultaneously.
With Demand region, region formation proceeds recursively. Region formation starts in a procedure, and
when a callsite is reached it may continue recursively into the callee, temporarily suspending region formation
in the caller. Thus, region formation is partially completed in the calling procedure and will only complete
after region formation is completed in the callee. When additional levels of recursive region formation occur,
region will be in various stages of completion along the entire call chain, completing as each callee invocation
returns.

3.2

A Classification of Regions of a Procedure

The interprocedural region formation algorithm addresses each of the described issues, based on a classification of regions in a single procedure. Regions are classified with respect to individual procedures and callsites
where they are invoked. Figure 3, which contains control flow graphs for three procedures and the formed
regions in different shadings, illustrates each of the different classifications of regions. A region in f that
includes either the entry or exit block of f is an interprocedural region. An interprocedural region can be
either entry, exit, or pass-through. For each procedure f , each callsite c with a call to f has a single entry
region associated with f , entryf,c which is the region that contains the entry block of f . At the one callsite
in A to procedure B in the figure, the entry region associated with B contains not only the entry block in
B but a path that passes through to the exit of B, and contains the exit of B also. At the callsite in B to
procedure C, the entry region associated with C contains the entry block in C and only two other blocks in
C.
Similarly, each callsite c to procedure f has a single exit region, exitf,c . As is the case for the one callsite
in A to B, entryf,c and exitf,c could in fact be the same region because the region follows a path that passes
through from entry to exit; in this case, it can be said that this region is an interprocedural pass-through
region of f at callsite c. All remaining regions containing blocks in f are local regions, or localf,c , as they
5

Source Program

Scanner

Profiler
e call

rsiv

recu

Parser
call

Intermediate
Code Generator

Region Formation

region

Demand-driven
Inliner

call

Encapsulation
region

Optimizer

Reintegration
Code Generator
Target Program

Figure 4: Demand-driven region-based compilation framework.
do not involve blocks from the caller of f . Note that f may not be partitioned into the same regions for
every callsite to f , since region formation within f is based on the context surrounding the callsite to f .

3.3

An Algorithm for Region Formation with Demand-driven Inlining

Figure 4 presents the organization of the Demand region framework, and Figure 5 presents the region
formation algorithm [33]. Demand region extends Phased region in several important ways in order to form
interprocedural regions without aggressive inlining. First, when a callsite is encountered as a region is being
grown, FormRegions recursively calls itself to continue to grow the current region in the callee in the context
of the caller, but without inlining at that time. Second, in order to minimize the size of the data structures
maintained at any given time during region formation, all regions within a called procedure will be identified
before FormRegions returns to region formation in the caller. Third, to enable formation of interprocedural
regions through this recursive approach, FormRegions operates on regions rather than just basic blocks.
FormRegions begins with a worklist B of all blocks in the current procedure f for which it is forming
regions. Successor and predecessor blocks are added to the current region only if they are desirable as defined
in Section 2; Desirable(x,y) plays this role. Non-callsite blocks are appended to the region as in Phased region. When a callsite c is reached in the analyzed code, the recursive call to FormRegions forms regions
local to the callee, say g, and then FormRegions returns with the entry and exit regions of g.
If there was not a pass-through region of g, entryg,c is concatenated with the region R currently being
formed in f when the callsite was encountered (which completes that interprocedural region), and this merged
region is added to the local Rlist of completed regions in f . Next, a new region R is begun, consisting solely of
exitg,c . If there is a pass-through region for g, this pass-through region is added to R, but R is not necessarily
complete at this point. Region formation continues in f by adding blocks to R. Once all blocks on procedure
f ’s worklist B are exhausted, the return parameters entryR and exitR are assigned the regions in f that
contain the entry and exit blocks, respectively. The local regions with respect to f (all regions except the
entry and exit regions of f ) are optimized and code is generated for them, prior to returning the entry and
exit regions.
The main steps of FormRegions are illustrated for a single callsite by the interprocedural CFGs in Figure 6.
For clarity, the same fill patterns are used to differentiate the steps of the Demand region algorithm in this
figure as were used to describe the Phased region algorithm in Figure 2. In this example, a pass-through
region of G exists, is returned to F by FormRegions as both entryR and exitR, and is appended to the
currently forming region R. Procedures that are not inlined at every callsite, not inlined at all, or are potential
procedure aliases, are identified after the region formation that began with the main program is complete.
The parameter to FormRegions named isolated is set for these isolated procedures to indicate that only
local regions are to be formed.
6

procedure FormRegions(f, isolated, entryR, exitR) {
B = all blocks in proc f
Rlist = ∅
while (blocks remain in B) {
R = Seed(B)
seed = last block in R

7

// Add desirable successors to seed path
stack = R
while (stack 6= ∅) {
x = Pop(stack)
foreach successor of x, y ∈ B {
if (Desirable(x,y))
if (y is proc call && y is inlinable) {
FormRegions(callee(y), 0, entryR, exitR)
if (entryR 6= exitR) {
R = R ∪ entryR
Rlist = Rlist ∪ R
R=∅
}
S = exitR
}
else {
S = {y}
Push(stack,y)
B = B – {y}
}
R=R∪S
}}
// Copy tail & add region to Rlist
B = B ∪ TailDuplication(R)
Rlist = Rlist ∪ R

// Add successors to the region
x = seed
y = most frequent successor of x
while (y ∈
/ R && Desirable(x,y)) {
if (y is proc call && y is inlinable) {
FormRegions(callee(y), 0, entryR, exitR)
if (entryR 6= exitR) {
R = R ∪ entryR
Rlist = Rlist ∪ R
R=∅
}
S = exitR
}
else
S = {y}
R=R∪S
x=y
B = B – {y}
y = most frequent successor of x
}

}
// Remove entry & exit regions from list
// generate code for regions local to f
entryR = region in Rlist with entry of f
exitR = region in Rlist with exit of f
if (not isolated)
Rlist = Rlist - (entryR ∪ exitR)
CodeGen(Rlist)

// Add predecessors to region, analogous to adding
// successors - code omitted for space limitations

procedure Seed(B) {
s = block with maximum weight in B
B=B–s
if (s is proc call) {
FormRegions(callee(s), 0, entryR, exitR)
if (entryR 6= exitR) {
R = R ∪ entryR
Rlist = Rlist ∪ R
}
S = exitR
}
else
S = {s}
return S
}
procedure CodeGen(Rlist) {
foreach region R ∈ Rlist
optimize R
generate code for Rlist
}
Main() {
FormRegions(main, 1, entryR, exitR)
foreach proc f 6= main
if (not all callsites to f were inlined)
FormRegions(f, 1, entryR, exitR)
}

}

Figure 5: Interprocedural algorithm for region formation with demand-driven inlining

3

11
00
4 call
G
00
11
00
11

6

0
50

11

11
00
11
00
11
00
11

seed

7

successors
00
11
00
11
00predecessors
11
00non-seed path
11

6

0

1200

11
00
000
111
00
11
000
111
4 call
G
00
11
000
3 111
00
11
000
111
111
000
5
000
111
000
111

111
000
000
111
000
111

000
9 111
10
111
000
11
000
111
000
111

0

5

2
600

81

0
81

0

81

5

9

8

00

1200

990

10

60

10

600

11
00
00
11
10
00
11
00
11

proc G

1500
00

9

11
00
4 call
G
00
11
00
11

3

2

00

1200

600

60

2

10

8

00
60

10

6

00

8

1500
00
50

50

990

990

proc G

50
0

1

1500

1

11
00
00
11
1
00
11
00
11

50

proc G

1

1

-driven

999

1

demand

proc F

999

999

50

inlining

proc F
proc F

11
00
7
00
11
00
11

7

outside region

(a) Seed (block 2) is selected as it is
the most frequently executed block
in proc F. Successors (block 4) are
selected until a callsite is reached.

(b) Region formation is performed
recursively in callee G, where local
regions are formed. Blocks 8, 10 &
11 form one region, with block 9
as a local region. Region formation
then continues in F.

(c) Successor path is completed (5
& 7), predecessors are added (1), desirable successors are added (3). Local regions are formed from remaining
blocks (6). Region formation is complete.

Figure 6: Example of Demand region

3.4

Empirical Evaluation

An experimental comparison of the two region formation approaches, Demand region and Phased region, is
described in terms of compilation memory requirements, code growth and runtime performance. Analysis of
the characteristics of the resulting units of compilation, including the size, homogeneity of profile weights,
and code size is performed to explain the results.
3.4.1

Methodology

These experiments were conducted using the Trimaran compiler system [28]. With Phased region as an existing component, Trimaran was a natural choice for this research. Significant implementation was performed
to add the capability of demand-driven inlining, and to create a region formation module that incorporates
demand-driven inlining and optimization. Also added was the ability to annotate each basic block with its
procedure of origin to enable identification of code that was inlined. For this set of experiments, ten C
benchmarks were used from SPEC 92 and 95 (www.spec.org) representing a variety of computations, code
sizes and program characteristics. Table 1 includes numbers of source code lines and procedure definitions.
The benchmarks were compiled under three scenarios: (1) procedure-based compilation without any
inlining or region formation, (2) region-based compilation using the Phased region approach, and (3) regionbased compilation using the Demand region approach.
3.4.2

Results

Compilation memory requirements
Table 1 compares the compilation memory requirements for Phased region versus Demand region. Due to
design considerations of the Trimaran framework, direct measurement of memory requirements was not
possible. Instead, measurements of whole program size, procedure sizes, and static call chain lengths were
taken, and estimates of memory requirements were computed according to each strategy for region-based
compilation.
For Phased region, the compilation memory requirements are computed as code size after aggressive
inlining is performed, as measured in number of Lcode instructions, because the entire program may be
held in memory during region formation and optimization (in the worst case). For Demand region, first the
8

Table 1: Comparison of memory requirements during region formation, measured in Trimaran Lcode instructions.

Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

General
Lines of
Num.
C source
of
code
procs.
14850
361
3628
62
1503
16
29246
383
19092
252
205627
1170
7597
357
29259
473
27044
316
67202
1127
40505
452

Phased region
Memory
requirement
Total
73997
11738
2601
110842
55783
1050754
31552
112188
100063
302409
17363

Static
call chain
Avg. Max.
5
11
3
7
2
5
9
23
6
11
5
13
22
35
8
14
5
15
4
12
6
11

Demand region
Procedure
size
Avg. Max.
183
2059
230
1757
224
1761
117
1109
193
1537
202
1810
112
987
124
2510
140
1977
131
2301
162
1397

Memory
requirement
Avg. Worst
3186
5175
1156
2538
1270
1800
1076
3085
1195
1923
2666
4391
1640
3197
1385
2185
1498
2732
1166
2210
1274
2228

Table 2: Percentage difference in average and maximum memory requirements of Phased region and Demand region.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Demand region
%
Phased region
average maximum
4.3
7.0
9.8
21.6
48.8
69.2
1.0
2.8
2.1
3.4
0.3
0.4
5.2
10.1
1.2
1.9
1.5
2.7
0.4
0.7
7.5
12.0

average and maximum sizes of procedures in a benchmark were calculated. Next, the lengths of static acyclic
call chains were measured at the source code level. The call chain length and procedure size information
were then used to compute the average and maximum of the sum of procedure sizes along the average and
maximum length call chains. The average value provides a good estimate of typical compilation memory
usage for purposes of comparison, while the maximum value indicates the worst case.
The data in Table 2 shows that on average, Demand region uses about 7.5% of the memory required by
Phased region for region formation for the benchmarks studied, over a range of roughly <1% to 49%. In the
worst case, Demand region uses an average of 12% of the memory required by Phased region over a range
of about <1% to 69%. Benchmarks with larger numbers of procedures and procedure calls, and more and
longer call chains, benefited the most from Demand region. While smaller benchmarks showed some benefit,
the smallest, 026.compress, showed the least benefit, suggesting that Demand region may be best suited to
large applications.
Code growth
Code growth was measured as the percentage change in overall code size from the original program, shown
in Table 3 as the percentage increase or decrease in size. To measure their code size used to calculate code
growth, each benchmark was compiled in three ways: (1) without any inlining or region formation, (2) using
9

Table 3: Percentage change in code growth for Phased region and Demand region.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Phased region
21
24
26
22
21
22
20
21
22
21
22.0

Demand region
19
26
25
25
20
23
23
24
23
21
22.9.1

Demand region
− Phased region
-2
+2
-1
+3
-1
+1
+3
+3
+1
0
+0.9

Table 4: Percentage change in execution time for Phased region and Demand region compared to procedurebased.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Phased region
-6.13
-3.17
-3.11
-6.28
-4.65
-6.72
-8.49
-7.01
-4.22
-6.90
-5.67

Demand region
-1.12
-2.14
26.88
7.30
-2.40
-5.00
12.50
-5.99
-2.18
-3.72
2.41

Demand region
− Phased region
5.01
1.03
29.99
13.58
2.25
1.72
20.99
1.02
2.04
3.18
8.08

the Phased region strategy, and (3) using the Demand region strategy. Measurements were taken in terms of
Lcode instructions of the resulting compiled programs. An increase in code size is represented by a positive
value. For example, a value of 21 means that after compilation within a particular framework, the program
is 21% larger than the same program compiled using the procedure-based approach.
On average, Demand region introduces < 1% more code than Phased region, over a range of 2% less to
3% more growth. In general, differences in code growth are not dramatic, due to the use of the global static
code growth limit of 20% in both Phased region and Demand region. In practice, the 20% code growth limit
prevents inlining once the code size has grown to 20% or more above the original size. However, a benchmark
may grow to just below this limit, allowing one more instance of inlining to be performed. Demand region
shows slightly more code growth than Phased region because Demand region is inlining in a different order,
which can lead to the benchmark first growing to just below the limit, and then inlining a larger procedure
which exceeds the limit considerably.
Runtime performance
Table 4 reports the percentage change in execution time. Negative values for percentage change in execution
time indicate a performance speedup; the program ran faster compared to the procedure-based compilation.
The last column shows the difference in the change in execution time between Demand region and Phased region, with a negative value indicating that a benchmark compiled using Demand region ran faster than
when compiled with Phased region; a positive difference indicates that Phased region was faster.
For seven of the ten benchmarks, the results for execution time were quite similar for Phased region
and Demand region, separated only by a few percentage points, which equates to fractions of a second in
10

Table 5: Comparison of number of compilation units for procedure-based, Phased region and Demand region
(in Lcode instructions).
Number of Units
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Proc.-based

Phased region

Demand region

361
62
16
383
252
1170
357
473
316
1127
452

1787
436
117
1838
1336
6084
801
3575
822
5522
2232

1774
476
102
1888
1322
6047
793
3791
797
5616
2261

Demand region
− Phased region
-13
40
-15
50
-13
-37
-8
216
-25
94
29

wall clock time. In particular, there are little or no differences in performance for 008.espresso, 023.eqntott,
124.m88ksim, 126.gcc, 132.ijpeg, 134.perl and 147.vortex. The drop in performance from Phased region to
Demand region for 026.compress, 099.go and 130.li is due to naive heuristics for deciding whether to perform
demand-driven inlining at a given callsite, and the way the prototype system handles demand-driven inlining
of indirect recursive procedure calls. Specifically, with this implementation, it is possible for the code limit
to be reached before inlining is performed in some of the high execution frequency regions, resulting in
optimization loss. ILP processor utilization was also examined, with only insignificant variations noted.
Thus, while memory requirements are improved dramatically, runtime performance remains virtually unaffected in general. This improvement in memory requirements was the primary goal of performing demanddriven inlining during region formation in Demand region. Since Demand region is implemented using the
same region formation and inlining heuristics, leading to substantially similar regions, dramatic improvements to runtime performance could not be reasonably expected. The key innovation of Demand region is
to integrate demand-driven inlining into region formation to reduce the requirements for memory during
compilation.

3.5

Analysis of Compilation Unit Characteristics

Procedure restructuring affects the characteristics of the unit of compilation. Analyzing changes to program
characteristics, such as the size, profile homogeneity and interprocedural scope of the unit of compilation,
can further explain the impact on memory requirements, code growth and performance.
Unit size
Tables 5 and 6 report the total number of compilation units and average size in Lcode instructions for
each of the studied benchmarks under the three different strategies for compilation. The two region-based
compilation techniques result in very similar average region size and total number of regions, while the
procedure-based strategy produces far fewer, though far larger, compilation units. Slight variations in sizes
and numbers of regions are attributed to differences in the order in which callsites are inlined. The aggressive
inlining of Phased region favors inlining frequently executed, smaller procedures over larger procedures due
to the limit it places on total code growth and the inlining heuristic. Since the demand-driven inliner inlines
as it is creating a region and reaches a callsite, it can reach the same specified limit for code growth at a
different time due to different order of inlining. The demand-driven approach to inlining in Demand region
and the recursive nature of the algorithm lead to a bottom-up inlining of regions. That is, the inlining is
performed as the recursive calls to FormRegions return. The contribution of the Demand region approach is
that it can significantly reduce compilation memory requirement, while creating number and size of regions
comparable to those created by Phased region.
11

Table 6: Comparison of average size of compilation units for procedure-based, Phased region and Demand region in Lcode instructions).
Average unit size
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Proc.-based

Phased region

Demand region

183
169
152
234
155
530
81
137
206
161
201

50
33
28
55
31
62
47
38
51
35
43

49
31
32
51
30
57
49
37
49
34
42

Demand region
− Phased region
-1
-2
+4
-4
-1
-5
+2
-1
-2
-1
-1

Table 7: Comparison of percentage of invariant compilation units and profile variance (homogeneity) for
procedure-based, Phased region and Demand region.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Proc.-based
Profile
Pct. units
variance
invariant
0.362
88.7
0.017
96.1
0.313
90.7
0.292
87.1
0.272
92.1
0.132
89.0
0.198
90.3
0.273
88.8
0.212
88.7
0.310
90.7
0.238

90.2

Phased region
Profile
Pct. units
variance
invariant
0.340
81.2
0.001
97.6
0.245
87.5
0.293
88.2
0.249
92.9
0.108
90.1
0.208
88.5
0.254
86.7
0.195
89.3
0.259
91.1
0.215

89.3

Demand region
Profile
Pct. units
variance
invariant
0.342
94.1
0.020
97.6
0.375
90.8
0.293
91.0
0.292
93.3
0.108
93.2
0.203
94.2
0.310
91.1
0.187
90.3
0.261
93.1
0.239

92.9

Profile homogeneity
Profile homogeneity is defined as the measure of how similar the given unit of compilation is in terms of profile
weight per instruction, operation or basic block. This variation on code density provides an indicator for the
impact of region formation on optimization. More homogeneous compilation units enable the optimizer to
easily identify and isolate heavily executed regions, and then selectively focus more attention on these more
important regions and less attention elsewhere. This partitioning reduces the chance of leaving important
portions of the code unoptimized or spending excessive time optimizing unimportant code.
Within the context of units of compilation, the profile homogeneity, or profile variance, is defined to be
the measure of the degree of deviation, that is, the standard deviation, in profile weights for all basic blocks
within a compilation unit. Table 7 shows the average profile variance and percentage of compilation units
that are invariant for each benchmark. The average profile variance is an overall indication of how consistent
the profile weights are within each of the benchmarks’ units of compilation. The closer the profile variance is
to 0, the less variation there is in the profile weights overall for the benchmark, and the more homogeneous
the benchmark.
The results in Table 7 indicate that in every case Demand region improves percentage of invariant units
over both procedure-based compilation and Phased region. Phased region tended to gain in some cases and
lose in others over procedure-based compilation. When there is an increase in the percentage of invariant
code, there is generally also an increase in the profile variance of the code overall. This is due to the
procedure restructuring done by region formation, which favors grouping more frequently executed code
together, leaving less frequently executed code behind. Because less important code is not actively formed
into more homogeneous regions, the profile weights of their containing regions are slightly more variant than
12

Table 8: Comparison of percentage of interprocedural operations in Phased region and Demand region.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Phased region
% interproc.

Demand region
% interproc

20.7
18.0
23.5
28.4
22.9
19.3
30.2
23.0
20.0
23.0
22.9

24.3
23.8
25.9
26.7
24.9
25.4
28.0
25.1
24.9
25.7
25.5

Demand region
− Phased region
3.6
5.8
2.4
-1.7
2.0
6.1
-2.2
2.1
4.9
2.7
2.6

regions of frequently executed code. It can be hypothesized that Demand region produces less variant code
over Phased region because the integrated, demand-driven use of inlining within Demand region uses the
region formation desirability heuristic (50% or greater execution frequency) to also guide inlining. Overall,
the frequency of code inlined by Demand region is likely to be greater than the more general, aggressive
inlining approach in Phased region.

Interprocedural scope
When specifically comparing regions to procedures, and regions formed using different techniques, a change
in the number of interprocedural regions and the amount of interprocedural operations per region indicates the
change in interprocedural scope. Recall that an interprocedural region is a region that includes instructions
from more than one procedure. Interprocedural operations are the instructions in an interprocedural region
that are from procedures other than the procedure in which formation of the region began. Before inlining is
performed, all basic blocks are annotated with the block’s procedure of origin. With this origin information,
the impact of region formation on interprocedural scope in a unit of compilation can be measured directly by
calculating how much of the code within each unit originated outside itself. The percentage of interprocedural
code in the program is measured as a simple ratio of the number of interprocedural operations to total
operations.
Table 8 shows the average percent of code within regions that is from a procedure outside the region (i.e.,
interprocedural code). An improvement in the percentage is indicative of better interprocedural scope. An
increase in interprocedural scope within the unit of compilation means that the potential for interprocedural
optimization is increased without additional analysis.
In general, the percentage of interprocedural operations is similar for Phased region and Demand region.
The differences in interprocedural scope under the two techniques are slight. The interaction of various
factors leads to insight on how to improve the techniques. The slight increase in interprocedural scope
for 008.espresso occurs with a slight decrease in code growth and little or no change to profile variance.
For 023.eqntott, slight differences in code growth and variance would not indicate the larger increase in
interprocedural scope seen for Demand region. This change could be due to the slight reduction seen for
average size of the unit of compilation for Demand region for 023.eqntott, since the other factors were quite
similar. The improvements to interprocedural scope seen with 126.gcc, 132.ijpeg, 134.perl and 147.vortex are
likely due to slight decreases in the average size of the unit of compilation, which are magnified due to the
large sizes of the benchmarks. Most puzzling is the increase in interprocedural scope seen with Demand region
applied to 026.compress, 099.go, 130.li, and to a lesser extent, 124.m88ksim, which exhibit significantly more
variance and a definite reduction in runtime performance versus Phased region. This seeming contradiction
for these four benchmarks could be due to the effect of gaining interprocedural scope by restructuring, with
the side-effect of leaving behind more invariant code in the process. An increase in code growth appears to
be the cause of decreased interprocedural scope for 130.li.
13

Source Program

Scanner

Profiler
1st order heuristic

e call

rsiv

recu

Parser
call

Intermediate
Code Generator

Region Formation

Demand-driven
Inliner

region 2nd order heuristic
call

Encapsulation
region

Optimizer

Reintegration
Code Generator
Target Program

Figure 7: Relationship of first- and second-order heuristics to region formation and the demand-driven inliner.

4

Heuristics for Demand-driven Inlining

In the previous section, baseline heuristics were used to guide demand-driving inlining within region formation to establish the efficacy of the Demand region approach as compared with Phased region and traditional
procedure-based compilation. This section explores a variety of heuristics designed to improve the performance of Demand region, and discusses a number of classifications, factors and important issues that are
integral to inlining heuristics design.
Because region formation drives inlining, the heuristics for a demand-driven inliner must consider the
order that procedures are processed by the region formation phase and the characteristics of a callee at each
callsite as it is encountered during region formation [32]. Procedures that are analyzed later in the compilation
may result in less inlined code within them and thus be less optimized since code growth restrictions could
limit further inlining, and thus limit the interprocedural scope of that procedure. Therefore, procedures that
have the highest potential for optimization, particularly instruction scheduling for ILP architectures, should
be processed first by the region formation analysis phase. Thus, demand-driven inlining within a region-based
compiler involves two general classes of heuristics, defined as: first-order heuristics that determine the order
in which procedures are processed during region formation, and second-order heuristics that govern decisions
about whether to inline at each callsite. Figure 7 illustrates the location within a region-based compilation
framework of these two heuristics.

4.1

First-order Heuristics

First-order heuristics select the order to consider procedures for region formation, which will implicitly affect
the order of demand-driven inlining decisions. Because demand-driven inlining within a given procedure
is considered at callsites as region formation is performed for that procedure, the order of decisions for
demand-driven inlining follows the flow-directed manner in which region formation is performed within a
given procedure’s control flow graph.
The first-order heuristics studied in the research attempt to order procedures from most to least important
in terms of optimization opportunity. In particular, three possible first-order heuristics for demand-driven
inlining were examined. The most precise measurement of procedure importance is actual dynamic run-time
profiling which comes at the cost of an initial instrumentation, compilation and execution. Procedures are
ordered from highest to lowest percentage of overall run-time spent in the procedure, based on profiling
information. It is worth noting that procedures which consume larger portions of execution time are likely to
contain loops and callsites within the loops, which supports the importance of this heuristic to interprocedural
region formation in a demand-driven framework.
Static estimates of importance provide less costly heuristics, but also tend to produce less precise information. One heuristic based on static estimates orders procedures from most to least number of static callsites
14

within the procedure, and within that order from smallest to largest procedure size. More importance is
assigned to procedures with the highest percentage of callsites compared with code size. This increases the
chance that region formation will be performed interprocedurally, producing more scheduling and optimization opportunities, while controlling code growth by considering smaller procedures before larger ones.
Another ordering considered is based on the loop call weight of a procedure, assigning more importance
to procedures which contain more callsites within loops, and P
increased importance for those callsites that
n
are more deeply nested. The loop call weight is computed as: i=1 loopdepthi × W , where n is the number
of callsites in a procedure, and W is the loop depth weight constant. A value of 10 is used for W to assign an
order of magnitude increase in significance to successive loop depths, since, intuitively, interior loops consume
more execution cycles than do their enclosing loops.

4.2

Second-order Heuristics

Second-order heuristics involve the decision about whether to inline each callee within a procedure as region
formation reaches that callsite. While there are a number of heuristics already developed for this decision
making, they have all been applied within a separate inlining phase without consideration of the interactions with region formation analysis, and in particular, demand-driven inlining. The second-order heuristics
attempt to increase instruction scheduling and optimization opportunities while minimizing code growth.
For correctness, procedures where there are mismatches in the number and types of parameters between
the callsite and callee, when the compiler determines that memory regions associated with arguments to a
procedure may overlap or are pointers, are not inlined.
To avoid high code growth, inlining is prevented once the the overall code size has increased more than
20% percent above the original size. A code growth limit of 20% has been shown to minimize unnecessary
code growth while still allowing beneficial inlining [20]. Similarly, inlining is prevented for procedures that
are directly or indirectly recursive to avoid the potential for excessive code growth.
Procedures that are more frequently executed than a fixed frequency or with some desired ratio over
the frequency of the caller are inlined. Region formation already uses this second-order heuristic, such that
inlined procedures will always be executed at least 50% as frequently as the seed block of their enclosing
region. Only procedures that are less than a static maximum size are inlined to limit code growth, and
procedures with higher call overhead compared with their code size are inlined.

4.3

Empirical Evaluation

Experiments were conducted to study the effectiveness of a number of heuristic combinations (Table 9), and
to determine which strategies can improve characteristics of the program and its runtime performance. The
heuristic combinations were compared by measuring three effects in terms of the percentage change of each
combination versus HØ, the baseline method. In particular, the effects that were evaluated include: (1) code
growth, (2) compilation time, including the time to compile the source code up through region formation
and region-based optimization, and (3) execution time, which measures more directly the impact of inlining
heuristics on region formation and region-based optimization, and ultimately on runtime performance. Note
that the results in this section cannot be compared directly to those in Section 3, due to slight variations in
implementation needed to incorporate the newer inlining heuristics.
When designing inlining heuristics, first-order heuristics should not ignore the goals of second-order heuristics. In particular, first-order heuristics should anticipate second-order heuristics by processing procedures
early in the compilation that will benefit most from the interprocedural scope gained from demand-driven
inlining. Second-order heuristics should rely on first-order heuristics to provide more important procedures
earlier in the compilation, while constraining code growth so that procedures remaining to be handled by
region formation can still benefit from demand-driven inlining. While the heuristics are the same for Phased region in Section 3 and H1 in this section, for example, the implementation of the heuristics was modified
to enable consistent comparison of results with the newer heuristics. Experimental results reported in Section 3 enable the initial valid comparison of Demand region with the original, unmodified Phased region
framework.
15

Table 9: Summary of heuristic combinations.
Name
HØ

First-order

Second-order

None

None

H1

Run-time profile ordering.

H2

Order by descending
number of static callsites,
then ascending procedure
size.
Same as H2.

Inlined procedures guaranteed to be executed at
least 50% as frequently
as seed block in their region [20].
Same as H1, plus only inline if callee size ≤ 25 [19].

H3

H4

H5

H6

4.3.1

Same as H1, plus prevent
inlining direct or indirect
recursion.

Order by decreasing loop
call weight, then ascending procedure size.
Order by decreasing execution cycles, then ascending procedure size.

Same as H3.

Same as H5.

Same as H3, plus minimum loop call weight of
10 to inline. (Note: a procedure containing a single loop is assigned a loop
call weight of 10.)

Same as H3.

Intuition/Motivation
Baseline version of original region-based compilation. No inlining is performed.
Original region-based compilation. Aggressive inlining with standard code growth limit, then region
formation; first- and second-order inlining heuristics as defined by [20].
Demand-driven inlining with simple static heuristics; avoid more costly analysis in order to potentially improve compilation time.
Demand-driven inlining with simple static heuristics. Increase number of procedures into which inlining is performed before code growth limit is
reached, preventing successive inlining of recursive
procedures.
Static estimation of profile information by equating
loop characteristics with predicted execution frequency, for improved compilation time.
Actual runtime profile information should provide
most precise information for guiding region formation and demand-driven inlining, for improved runtime performance.
Only inline if contains at least 1 call within at least
one loop. Combines profile information to prioritize
compilation of procedures, with potentially faster
static loop characteristic estimation for making inlining decisions; should improve compilation time.

Methodology

Implementation of the described techniques and experiments has been conducted in context of the Trimaran
compiler [28]. The existing region formation module was enhanced to incorporate additional first-order
inlining heuristics. The demand-driven inliner within Demand region was extended with a number of new
second-order inlining heuristics. In addition, the demand-driven inliner was more tightly integrated into the
compiler, enabling a meaningful measurement of compilation time. The experiments were performed on the
same set of benchmarks (Table 1, p. 9).

4.3.2

Results

Code growth
Table 10 reports the percentage increase in code growth for heuristics H1 through H6 versus the baseline
compilation HØ. Code growth was measured directly by counting the number of Lcode instructions resulting
from compilation using each of the heuristics.
Heuristic H2 does a significantly better job than any of the other methods at limiting code growth.
This is not surprising, since it uses a simple, static threshold that only allows inlining of small procedures. In
general, heuristic H1, or Phased region in its basic form, does a little better in most cases than the remaining
heuristics based on demand-driven inlining. The changes in code growth are generally slight, and in nearly all
cases remained under the static limit of 20% used in earlier experiments, indicating these heuristics provide
improved code growth control. Code growth for compress exceeded 20% for H3, H4, H5 and H6. This is
due to an order of region formation, and therefore inlining, that causes a very large procedure to be inlined
when the code growth limit had already nearly been reached.
16

Table 10: Percentage change in code growth over HØ.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

H1
8
6
17
9
8
10
8
14
11
15
11

H2
1
0
0
3
1
2
0
3
1
3
1

H3
20
18
23
12
16
15
8
17
18
16
16

H4
20
18
23
11
15
15
6
17
17
16
16

H5
17
15
21
8
12
8
4
15
12
13
13

H6
17
15
21
8
12
8
4
15
12
13
13

Table 11: Percentage change in compilation time over HØ.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

H1
2.1
1.8
-8.3
3.0
4.0
2.9
4.5
3.5
2.8
3.7
2.0

H2
0.0
-0.1
-1.3
-2.5
-2.1
-0.3
0.0
-1.0
-1.4
0.1
-0.9

H3
2.0
2.4
-2.8
6.5
27.6
21.1
26.8
13.9
14.8
4.8
11.7

H4
4.2
4.8
0.0
7.8
18.4
15.2
24.5
13.5
14.2
7.8
11.0

H5
4.9
9.3
5.6
10.0
27.6
15.4
25.6
14.0
15.3
3.0
13.1

H6
4.5
7.9
2.8
9.3
27.4
15.2
24.9
13.8
15.1
3.0
12.4

Compilation time
Results for compilation time for the heuristics are presented in Table 11. The change in compilation time as
compared with HØ is shown as a percentage increase (positive) or decrease (negative). Compilation time
for each heuristic was measured by timing the compilation through the optimized Lcode phase, just prior
to the point when Trimaran outputs instrumented code for simulated execution on the target architecture.
This timing includes any applicable phases for profiling, intermediate code generation, aggressive inlining,
region formation (which may or may not include demand-driven inlining), and region-based optimization.
The timings used were system times (i.e., wall clock times) accurate to the nearest 10th of a seconds, and
were on the order of minutes or hours (not unusual for a research compiler).
In general, compilation time improves the most for H2 which uses the simplest inlining heuristic, and
H1, the Phased region compilation method. Due to the overhead introduced in the current implementation
of demand-driven inlining, unusually high increases in compilation time were seen in most other cases where
demand-driven inlining is used (H3 through H6).
It is interesting to note that for some of the benchmarks, 008.espresso, 023.eqntott, 026.compress, and
147.vortex, compilation time increased only slightly over H1 and H2 for the remaining heuristics. This
indicates that other more complex factors may be helping to control compilation time in spite of the more
advanced and time-consuming inlining heuristics being used.
Runtime performance
Relative changes in performance between the baseline heuristic HØ and the others are shown in Table 12.
Performance was measured by running the programs using the Trimaran simulator, which involved an addi17

Table 12: Percentage change in execution time over HØ.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

H1
-4.01
-3.17
-3.11
-3.19
-6.13
-5.20
-8.49
-2.98
-5.50
-3.05
-4.48

H2
0.50
1.31
0.00
0.07
-1.31
-1.03
-2.16
0.12
-1.90
-1.71
-0.61

H3
-5.50
-4.02
-3.11
2.30
-3.90
-4.15
-4.01
-4.77
-4.79
-5.10
-3.71

H4
-7.35
-6.11
-3.11
-4.20
-9.22
-0.24
-12.53
-7.33
-10.43
-9.25
-6.98

H5
1.75
-1.90
-2.98
-4.10
-9.13
-10.20
-12.20
-6.97
-9.54
-9.21
-6.45

H6
1.75
-1.90
-2.98
-4.10
-9.13
-10.20
-12.20
-6.97
-9.54
-9.21
-6.45

tional phase of compilation to instrument the Lcode output from region formation to execute in the simulated
EPIC environment described earlier.
H3 was competitive with H1, but H4, H5 and H6 all showed general improvements in performance
over H1. Overall, the best performance speedup was consistently demonstrated with heuristic H4, which
uses the static loop call weight estimator and recursion prevention to guide inlining decisions. There was also
little or no significant change in processor utilization (i.e., CPI ) for most of the benchmarks under most of
the heuristics.
4.3.3

Discussion

The code growth, compilation time and runtime performance for the benchmarks under different inlining
heuristics interact in a number of ways. For the cases that cause more code growth, execution time also
improves. The more naive heuristics of H2 lead to the smallest increases in code size and compilation time,
but also do not improve performance as much as the other more sophisticated methods. Larger increases in
code growth and compilation time do not always translate to improvements in execution time, indicating
that bounding code growth is indeed important, as was believed. For example, when H3 was applied to
099.go, code size and compilation time increased more than with H2 while execution took longer, possibly
due to recursive inlining of less important code.
The more scientific codes (124.m88ksim, 132.ijpeg, 147.vortex ), tend to benefit the most from increases
in code growth and compilation time (which is also optimization and scheduling time) in terms of their
speedup, particularly for the most advanced profile-estimating (H4) and profile-based (H5 and H6) methods.
Smaller benchmarks (026.compress, 023.eqntott ), by both size and number of procedures, are less predictable,
although significant performance gains are seen with H3 through H6, with most showing improvement over
the original region-based technique (H1). Benchmarks with more recursion (026.compress, 099.go, 130.li)
require more compilation time and gain comparatively less in performance improvements than the others.
The combination of heuristics in H4 proved consistently to be the most effective at controlling code growth
and compilation time while improving runtime performance. The fact that H4 bases inlining decisions on the
static loop call weight, which estimates runtime behavior, rather than the actual profiling information itself,
as in H5 and H6, is significant, indicating that profiling may not be necessary for making good demanddriven inlining decisions during region formation. Profiling generally is more precise than static estimates
because it directly measures program behavior at runtime, but requires more overhead and depends on the
data used for the profiling.

4.4

Impact on Compilation Unit Characteristics

The experimental study in Section 3 examined how runtime performance can be improved by increasing
interprocedural scope of compilation units, and reducing the profile variance of each unit. To test this hypothesis further, the characteristics of the compiled Lcode were measured after region formation for heuristics
18

Table 13: Comparison of number and average size of compilation units for three heuristics.

Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

Avg
size
183
169
152
234
155
530
81
137
206
161
201

HØ
Units
(proc.)
361
62
16
383
252
1170
357
473
316
1127
452

Avg
size
15.9
16.6
16.8
17.0
18.6
15.3
14.9
14.1
15.2
16.9
16.1

H1
Units
(reg.)
4267
656
206
5424
3494
41613
2427
4720
4395
11026
7823

Avg
size
15.0
16.2
16.4
16.9
17.7
14.9
15.6
13.8
14.9
16.2
15.8

H4
Units
(reg.)
4710
755
218
5921
4027
43971
2516
5109
4891
11713
8383

HØ (the baseline, with no inlining or region formation), H1 (Phased region, for comparison) and H4 (the
overall best performing heuristic).
Unit size
Table 13 compares the compilation unit size characteristics resulting from the three heuristics, HØ, H1,
and H4. Both H1 and H4 show significant improvement in control of the size of the unit of compilation,
with average region sizes ranging from 3% to 19% of the original average procedure sizes. H4 consistently
produces more compilation units than H1, which is reflective of comparative code growth measurements for
the two heuristics. The average size of the unit of compilation decreases slightly from H1 to H4 by 0.1 to 0.9
Lcode instructions. Although such a slight decrease in the average sizes of compilation units cannot directly
account for the longer compilation times seen with H4, the more significant increase factor is code growth
which results from the increase in the number of compilation units that results from a decrease in average
size; with more code to compile, compilation time naturally is increased.
Profile homogeneity
Table 14 shows the profile homogeneity and percentage of invariant code for these three heuristics. In most
cases, H4 improved upon the amount of invariant code versus H1, while showing slight to moderate increases
in the profile variance. The consistent increase in variance with the attending increase in percentage of
invariant compilation units indicates that H4, as compared with H1, is simultaneously improving the profile
homogeneity of more compilation units while increasing the variance of a smaller number of compilation
units by relocating the more variant code. The benefit seen to the percentage of invariant compilation units
reflects the improvement in runtime performance for H4 over H1.
Interprocedural scope
Table 14 also compares the change in interprocedural scope for H1 and H4 compared to the baseline heuristic
HØ, which had 0% interprocedural code since no inlining was performed. Interprocedural scope improved
in all cases when using the demand-driven heuristics of H4, which showed improvements of 1.2% to 8.7%
over H1, as well. Improvements for H4 as compared with H1 were less significant for 008.espresso, 099.go,
and 134.perl, which have more instances of direct recursion than 130.li, which exhibits significant indirect
recursion. Indirect recursion within region formation leads to increased interprocedural regions as procedures
are inlined into other procedures. Direct recursion, or self-recursion, leads only to the inlining of a procedure
into itself, if at all. The smaller size and lower number of procedures in 023.eqntott and 026.compress led to
the larger improvements to interprocedural scope due to a higher proportion of smaller procedures.
19

Table 14: Comparison of percentage of invariant compilation units and profile variance (homogeneity) for
three heuristics, and resulting interprocedural scope.
Benchmark
008.espresso
023.eqntott
026.compress
099.go
124.m88ksim
126.gcc
130.li
132.ijpeg
134.perl
147.vortex
average

5

Profile
variance
0.368
0.020
0.313
0.372
0.308
0.323
0.208
0.281
0.270
0.280
0.274

HØ
Pct. units
invariant
93.1
97.7
92.1
91.5
93.9
92.9
93.7
93.2
94.3
93.1
93.6

Profile
variance
0.288
0.001
0.210
0.310
0.260
0.262
0.208
0.201
0.189
0.211
0.214

H1
Pct. units
invariant
93.7
97.8
93.7
91.9
94.4
93.4
93.7
93.8
94.5
93.8
94.1

Profile
variance
0.361
0.022
0.275
0.331
0.311
0.300
0.203
0.239
0.249
0.271
0.256

H4
Pct. units
invariant
94.0
98.6
93.8
93.1
94.9
93.9
94.2
94.2
95.2
94.1
94.6

Pct. interproc.
ops.
H1
H4
18.0
19.2
15.1
23.8
21.7
25.9
23.1
24.9
17.1
19.8
18.2
20.4
24.4
27.6
17.3
19.3
16.9
18.1
19.0
20.5
19.9
24.1

Related Work

Region-based compilation remains an active area of research, with promising applications to a Java virtual machine [9, 31] including a variety of adaptive techniques [5], and ILP optimization and scheduling
frameworks [26, 35, 37]. Region formation is a form of interprocedural data flow analysis, a well-researched
area with many benefits to ILP [17, 19, 29]. Disadvantages are that during analysis it can have unscalable
memory requirements [16] or require exponential time with respect to program size [16]. Advances address
the issue of unscalable memory and time requirements by using modular [25, 30] and demand-driven [16]
approaches, while profile-driven analysis and optimization [3, 7, 10, 11, 12] are vital to code improvement
and performance.
Procedure inlining is used to eliminate call overhead [6, 8] leading to fewer and faster calls [4], improve
compiler analysis and optimization [4, 8], register usage, code locality and execution speed [8], provide more
precise data flow information to generate more efficient code specialized to the callee [4, 6], and enable intraprocedural analysis and optimizations such as constant propagation and elimination of redundant operations
to be applied at interprocedural scope [8, 19]. However, inlining can increase register pressure [6, 8, 15],
code size [6, 8], instruction cache misses [4, 6, 8], and compilation time, which is more critical during dynamic compilation [6]. Extensive research into inlining heuristics and the factors that bolster or limit their
effectiveness within procedure-oriented compilers has been performed [2, 4, 7, 8, 13, 15, 21, 23, 24, 36].

6

Conclusions and Future Work

Region-based compilation has already been shown to help increase ILP performance by enabling interprocedural code motion without the expense of large compilation units or interprocedural data flow analysis. This research has focused on improving the effectiveness of region-based compilation that integrates
heuristics-guided inlining into region formation analysis. Experimental results comparing two region-based
approaches demonstrated that a demand-driven approach to inlining, as compared to a phased aggressive
inlining approach, can reduce memory requirements and code growth while improving runtime performance
due to increased profile homogeneity and interprocedural scope. These improvements are further enhanced
by making more informed inlining decisions, and reordering the processing of procedures by a region-based
compiler, leading to further improvements to compilation unit characteristics, reflected as improved performance. Heuristics based on static analysis can be as effective as profile-based heuristics at guiding inlining
decisions.
Partial inlining is an inlining technique that selectively inlines portions of a callee procedure into a callsite
rather than the entire body of the callee [9, 14, 18, 27]. Region-based compilation naturally enables a form of
partial inlining for the optimization phase of compilation [20]. The approach presented in this paper is being
extended to the design of an algorithm for incorporating partial inlining into region-based compilation [34],
including its applicability to object-oriented programming.
20

References
[1] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools.
Addison-Wesley Publishing Company, 1988.
[2] R. Allen and S. Johnson. Compiling C for vectorization, parallelization, and inline expansion. ACM
SIGPLAN Conference on Programming Language Design and Implementation, pages 241–249, 1988.
[3] Glenn Ammons and James R. Larus. Improving data-flow analysis with path profiles. In ACM SIGPLAN
Conference on Programming Language Design and Implementation, pages 72–84, June 1998.
[4] Andrew Appel. Compiling with Continuations. Cambridge University Press, 1992.
[5] Matthew Arnold, Stephen Fink, David Grove, Michael Hind, and Peter F. Sweeney. A survey of adaptive
optimization in virtual machines. In Proceedings of the IEEE, pages 449–466, February 2005.
[6] Matthew Arnold, Stephen Fink, Vivek Sarkar, and Peter F. Sweeney. A comparative study of static and
dynamic heuristics for inlining. In ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation
and Optimization (Dynamo 2000), pages 52–64, January 2000.
[7] Andrew Ayers, Richard Schooler, and Robert Gottlieb. Aggressive inlining. ACM SIGPLAN Conference
on Programming Language Design and Implementation, pages 134–145, 1997.
[8] David F. Bacon, Susan L. Graham, and Oliver J. Sharp. Compiler transformations for high-performance
computing. Computing Systems, 26(4):345–420, 1994.
[9] Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia. Dynamo: A transparent dynamic optimization
system. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages
1–12, Vancouver, Canada, June 2000.
[10] Thomas Ball, Peter Mataga, and Mooly Sagiv. Edge profiling versus path profiling: The showdown. In
ACM SIGPLAN Symposium on the Principles of Programming Languages, pages 134–148, 1998.
[11] Rastislav Bodik, Rajiv Gupta, and Mary Lou Soffa. Complete removal of redundant expressions. In
ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1–14, June
1998.
[12] Brad Calder, Peter Feller, and Alan Eustace. Value profiling. In IEEE/ACM International Symposium
on Microarchitecture (MICRO), pages 259–269, December 1997.
[13] Pohua P. Chang, Scott A. Mahlke, William Y. Chen, and W. W. Hwu. Profile-guided automatic inline
expansion for C programs. Software Practice and Experience, 22(5):349–369, May 1992.
[14] Keith D. Cooper and Nathaniel McIntosh. Enhanced code compression for embedded RISC processors.
In ACM SIGPLAN Conference on Programming Language Design and Implementation, May 1999.
[15] J. W. Davidson and A. M. Holler. A study of a C function inliner. Software Practice and Experience,
18(8):775–790, August 1988.
[16] Evelyn Duesterwald, Rajiv Gupta, and Mary Lou Soffa. A practical framework for demand-driven interprocedural data flow analysis. ACM Transactions on Programming Languages and Systems, 19(6):992–
1030, 1997.
[17] David W. Goodwin. Interprocedural dataflow analysis in an executable optimizer. In ACM SIGPLAN
Conference on Programming Language Design and Implementation, pages 122–133, June 1997.
[18] Jean Goubault. Generalized boxings, congruences and partial inlining. In 1st Static Analysis Symposium
(SAS ’94), number 864 in Lecture Notes in Computer Science, pages 147–161. Springer Verlag, Namur,
Belgium, September 1994.
21

[19] Mary W. Hall, Brian R. Murphy, and Saman P. Amarasinghe. Interprocedural analysis for parallelization: Design and experience. In SIAM Conference on Parallel Processing for Scientific Computing, pages
650–655, February 1995.
[20] R. E. Hank, W. W. Hwu, and B. R. Rau. Region-based compilation: Introduction, motivation, and
initial experience. International Journal of Parallel Programming, 25(2):113–146, April 1997.
[21] W. W. Hwu and P. P. Chang. Inline function expansion for compiling C programs. ACM SIGPLAN
Conference on Programming Language Design and Implementation, pages 246–257, 1989.
[22] W. W. Hwu, S. A. Mahlke, W. Y. Chen, P. P. Chang, N. J. Warter, R. A. Bringmann, R. G. Ouellette,
R. E. Hank, T. Kiyohara, G. E. Haab, J. G. Holm, and D. M. Lavery. The superblock: An effective
structure for VLIW and superscalar compilation. Journal of Supercomputing, 7:229–248, July 1993.
[23] Suresh Jagannathan and Andrew Wright. Flow-directed inlining. ACM SIGPLAN Conference on
Programming Language Design and Implementation, pages 193–205, 1996.
[24] O. Kaser and C. R. Ramakrishnan. Evaluating inlining techniques. Computer Languages, 24:55–72,
1998.
[25] D. Lian and M. J. Harrold. Efficient points-to analysis for whole-program analysis. In ACM SIGSOFT
International Symposium on the Foundations of Software Engineering (FSE), pages 199–215, September
1999.
[26] Yang Liu, Zhaoquing Zhang, Ruliang Qiao, and Roy Dz ching Ju. A region-based compilation infrastructure. In Seventh Workshop on Interaction between Compilers and Computer Architectures, pages
75–84, Anaheim, California, February 2003.
[27] Stefan Monnier and Zhong Shao. Inlining as staged computation. Technical Report TR-1193, Department of Computer Science, Yale University, March 2000.
[28] Amitabh Nene, Suren Talla, Benjamin Goldberg, and Rodric M. Rabbah. Trimaran - an infrastructure
for compiler research in instruction-level parallelism - user manual, 1998. http://www.trimaran.org.
New York University.
[29] Thomas Reps, Susan Horowitz, and Mooly Sagiv. Precise interprocedural dataflow analysis via graph
reachability. In ACM SIGPLAN Symposium on the Principles of Programming Languages, pages 49–61,
San Francisco, California, January 1995.
[30] Atanas Rountev, Barbara G. Ryder, and William Landi. Data-flow analysis of program fragments. In
ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE), pages
235–252, September 1999.
[31] Toshio Suganuma, Toshiaki Yasue, and Toshio Nakatani. A region-based compilation technique for
a java just-in-time compiler. In ACM SIGPLAN Conference on Programming Language Design and
Implementation, pages 312–323, June 2003.
[32] Tom Way, Ben Breech, Wei Du, and Lori Pollock. Demand-driven inlining heuristics in a region-based
optimizing compiler for ILP architectures. In International Conference on Parallel and Distributed
Computing and Systems, pages 90–95, Anaheim, California, 2001.
[33] Tom Way, Ben Breech, and Lori Pollock. Region formation analysis with demand-driven inlining for
region-based optimization. In International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 24–33, Philadelphia, Pennsylvania, October 2000.
[34] Tom Way and Lori Pollock. A region-based partial inlining algorithm for an ILP optimizing compiler. In
International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA),
pages 552–556, Las Vegas, Nevada, 2002.
22

[35] Ziangyu Zhang and Rajiv Gupta. Whole execution traces. In IEEE/ACM International Symposium on
Microarchitecture (MICRO), pages 105–116, Portland, Oregon, December 2004.
[36] Peng Zhao and José Nelson Amaral. To inline or not to inline? In 16th Workshop on Languages and
Compilers for Parallel Computing LCPC, pages 405–419, College Station, Texas, October 2003.
[37] Huiyang Zhou, Matthew D. Jennings, and Thomas M. Conte. Tree traversal scheduling: A global
scheduling technique for VLIW/EPIC processors. In 14th Workshop on Languages and Compilers for
Parallel Computing LCPC, pages 223–238, Cumberland Falls, Kentucky, August 2001.

23

