Exploring Parameter-Type Compiler Options
for Accelerating Program Execution
Takeo Saeki, Junya Goto, Nagisa Ishiura
School of Science and Technology, Kwansei Gakuin University
2-1 Gakuen, Sanda, Hyogo, 669-1337, Japan

Abstract—This paper proposes an extensive use ofparameter-type compiler optimization options to speed
up program execution. Compilers usually provide a lotof options to control their optimizers. However, existing
methods of exploring the best option sets for given
programs dealt only with switch-type options which
specifies activation/deactivation of individual optimizers.
This paper extends the search domain to parameter-type
options which control optimizers by numerical values. A
genetic algorithm is employed to explore the best combination of the parameters as well as the optimization
switches for given programs. An experiment on GCC
4.8.1 with four benchmark programs shows that theproposed method accelerates the program execution by
10.4%, at the cost of 38.0% increase in the exploration
time.

I. I NTRODUCTION
Optimization to enhance the efficiency of codesis the core task of compilers, and modern compilers
implement a lot of transformations for optimization.
Since the effects of the transformations depend on
the properties of the programs and some optimization
may even degrade the performance, some compilers provide options to control individual optimizers.
However, as the number of options increases, it getsdifficult to find option sets which best match withgiven programs. Since GCCs later than version 4.0
have more than 100 options, it is virtually impossible
to tune the option set manually.
To meet this issue, there have been a lot of researches to automate the searches for the best combinations of optimization options for given programs.
Pan [1] and Lin [2] attempted to find the option sets
by iterative methods and by an genetic algorithm,respectively. Their main target was the speed of theresulting codes and they succeeded in outperforming
GCCs’ -O3 option which turns a pre-selected set ofoptimization options. On the other hand, Patyk [3]tried to reduce energy consumption through automatic
selection of compiler options based on a statistical
non-parametric analysis. Haneda [4] used the similar
method to reduce the size of object codes.
All those researches have dealt only with switchtype options, which activate or deactivate optimizers. However, more recent compilers such as GCC

4.8.1 accept parameter-type options, through which
optimizers are controlled by numeric values. Such
options might further enhance the performance of theexecution codes, but there have been no research toextend the option set search to the parameter-typeoptions.
In this paper, a genetic algorithm based search
for the best options, considering both the switchtype and the parameter-type options, is proposed. A
vector of parameter values to the options (0 or 1 forthe switch-type options) is used as the chromosome
representation of an individual in a population. The
execution time of compiled codes is measured using
a UNIX time command where codes are run multiple
times to make the measurement precise.
An experiment on GCC 4.8.1 with four benchmark
programs shows that the utilization of parametertype options accelerated the program by 10.4% on anaverage, which makes the programs faster than -O3
option by 40.2%.
II. C OMPILER O PTION S ETS FOR O PTIMIZATION
Recent compilers implement many optimizing
transformation routines. They also provide commandline options to control each of the optimizers. The
options are classified into switch-type options andparameter-type options, where the former specify
activation/deactivation of the optimizers and the latter
feed numeric values to the optimizers.
For example, GCC 4.8.1 has 186 switch-type options. An -fdse command line option turns on adead code elimination routine and an -fno-dse
turns it off. Besides them, it has 154 parametertype options. A --param max-inline-insnssingle=100 option, for example, limits the numberof the instructions resulting from inline expansion
to 100. Options to specify optimization levels, suchas -O1 through -O3, set predefined values to theseoptions. For example, the -O1 option turns on 38 outof the 185 options.
Options sets tailored for given programs often
produce higher code performance than the standard
optimizing options. As will be shown in the experimental results, tuning of the switch-type options only- 725 -TABLE I
E XAMPLE OF SELECTION PROBABILITIES .

startgenerate initial population

fi
1.2
1.3
1.5
1.8
2.0

select two (parent) individuals
apply crossover and mutation
replace individuals

wi = (fmax − fi )20.64
0.49
0.25
0.04
0.00
fmax = 2.0,

W =pi = wi /W
45.1%
34.5%
17.6%
2.8%
0.0%!

wi = 1.42

r times?

III. I NCORPORATING PARAMETER -T YPE O PTIONSIN O PTION S ET S EARCH

example by a UNIX time command. Here, fluctuation becomes a problem, since the code execution
time varies largely depending on various conditions,such as the status of the cache or the other processes
running on the computer system.
To solve this problem, we run the code multiple
times and pick the smallest run time as the fitness
function value. We use the minimum time instead of
the average time because the factors outside of theprogram only delays the execution, so the minimum
time best reflects the effect of the optimizers.
We change the number (k) of runs during thesearch; we start with k = 1 (to curve total executiontime) and gradually increase k as the search converges(to increase accuracy).

A. Genetic Algorithm Based Search

D. Selection, Crossover, and Mutation

Given a source program, our goal is to find a setof the switch-type options to be turned on and avalue vectors to all the parameter-type options thatminimizes the execution time of the compiled code.
In this paper, a genetic algorithm is employed to findoptimal solutions.

Fig. 1 shows the flow of the search. It starts withgenerating an initial population. Let the populationconsist of n individuals. The option value vector foreach individual is randomly chosen.
Then, the loops are repeated for r times. First, twoindividuals (parents) are chosen from the population.
Crossover and mutation are applied to generate two
new individuals. Some two individuals in the population are replaced by the new individuals.
In our method, the parents are picked up by aroulette selection method. Namely, each of the two
individuals is chosen with the probability defined tothe individual. Let fi be the fitness value of theindividual i, and fmax be the maximum value of fiamong the population. Then individual i is selectedwith a probability proportional to its weight wi which
is defined as:

endFig. 1. Flow of genetic algorithm based search.

accelerates the code by 27.0% as compared with the-O3 option, so its worth exploring the option sets.
However, switch-type options of GCC 4.8.1 alone
result in 2186 possible combinations. Since it is infeasible to find the best one by hand or by exhaustive
search, there have been researches to search optimal
solutions for given programs by meta heuristics, machine learning, etc.

B. Encoding of Option Set
A solution, or an individual in a population, isrepresented simply by a vector of the values tothe options, where the value for each switch-type
option is 0 or 1, meaning deactivation or activation, respectively. Some parameter-type options may
have large domains. To curve the search complexity,
we reduce the domains to the set of representative values. For example, when an option’s domain
is {1, 2, 3, 4, 5, · · · , 1024} (of 1024 elements), we
assume a reduced domain {1, 2, 4, 8, · · · , 2014} (of11 elements). The representative values are selectedtaking the properties of the options into account.
C. Fitness Function
Since our goal is the reduction of the execution
time of a given program, the fitness function of eachindividual is defined as the execution time of thecode generated with the option set encoded in theindividual.
We assume that the time is in terms of the real
run time on a target computer, which is measured for

wi = (fmax − fi )2
Let W be the sum of wi over all the individuals, thenthe probability pi with which i is chosen is pi =wi /W .
TABLE I shows an example of the selection probabilities, where the population consists of individuals
with fitness values 1.2, 1.3, 1.5, 1.8, and 2.0. The
second column and third column are the weights andthe probabilities of the individuals. The weight isdesigned so that individuals with better fitness values
may be selected more probably.

- 726 -TABLE II
E XPERIMENTAL RESULT.

programb queen.c
fasta.c
nbody.cbitcnts.cratio [%]

-O0
5.42
6.19
14.17
4.24
563.0

Compiler:
CPU:
Memory:OS:execution [s]
-O3
sw
1.41
1.08
1.60
1.07
2.16
1.97
1.59
1.31
140.2
110.4

sw+p0.86
1.10
1.71
1.24
100.0exploration [h]
sw
sw+p
2.71
4.67
3.13
5.20
6.40
6.72
4.06
4.90
100.0
138.0

GCC 4.8.1 (x86)Intel Core i2 (1.4 GHz)
3.8 GB
Ubuntu 13.10

Crossover and mutation operations in our method
are very conventional. A uniform crossover operation
is employed. During mutation, the value of each chromosome is changed at a certain mutation probability.
New two individuals generated from the parents
are inserted into the population. Instead, the two
individuals with the worst fitness values are discarded.

row “ratio” shows the geometric means normalized tosw+p for execution time and sw for exploration time.
We can see that the programs were accelerated by
10.4% by incorporating the parameter-type options
into the search. This was a speed-up by 40.2% ascompared with the -O3 options. The search time wasincreased by 38.0% which we believe is reasonable.
V. C ONCLUSION

IV. E XPERIMENTAL R ESULT
Based on the method stated so far, a search program
has been implemented in Perl 5 which runs on Unix
operating systems.
An experiment was done on four C programs. The
compiler used in the experiment was GCC 4.8.1 forx86 target. Out of all the optimizing, those caused
errors or warnings were excluded. This resulted in
164 switch-type and 134 parameter-type options. The
program was run on Ubuntu 13.10 on Intel Core i2
CPU (1.4 GHz) with a 3.8 GB memory.
The parameter settings for the genetic algorithm
were as follows:
population size: 100• iteration: 1,000• mutation probability: 0.05
•Candidate option sets obtained during the search weregiven to GCC compiler together with the -O3 option.
This is because the GCC has implicit optimizing
options which can only be activated by either of thestandard optimization option. Generated codes wereexecuted 1 to 5 times, depending on the iteration
count, to measure the execution time of the codes.
TABLE II shows the result of the experiment.
Columns -O0 and -O3 are the execution time (seconds) of the generated codes by GCC’s standard optimization options, where -O0 means no optimizationand -O3 optimization with the highest level. The next
two columns are the execution time resulted from option set search with the switch-type options only (sw)
and with the options of the both types (sw+p), where
the latter is the proposed method in this paper. The
last two columns indicate time (hours) consumed forthe option set search for the two methods. The bottom

This paper has proposed the utilization ofparameter-type compiler options as well as switchtype options to enhance the performance of compiled codes. An experimental result demonstrated thatgenetic algorithm based search successfully foundoption sets which accelerates the execution speed of
the code.
Future work includes refinement of the genetic
search procedure, and consideration of other objectives such as the size or power consumption of thegenerated codes.
ACKNOWLEDGMENT
We would like to thank Prof. Tomiyama of Ritsumeikan University for his advice on the definitionof fitness function. Authors would like to express ourthanks to all the members of Ishiura Laboratoriesof Kwansei Gakuin University for their advice anddiscussion for this work.
R EFERENCES[1] Z. Pan and R. Eigenmann: “Fast and Effective Orchestration ofCompiler Optimizations for Automatic Performance Tuning,”
in Proc. International Symposium On Code Generation andOptimization, pp. 319–332 (Mar. 2006).
[2] San-Chih Lin, Chi-Kuang Chang, and Nai-Wei Lin: “Automatic Selection of GCC Optimization Options Using a Gene
Weighted Genetic Algorithm,” in Proc. Computer Systems
Architecture Conference, pp. 1–8 (Aug. 2008).
[3] T. Patyk, H. Hannula, P. Kellomaki, and J. Takala: “Energy
Consumption Reduction by Automatic Selection of Compiler
Options,” in Proc. International Symposium on Signals, Circuits and Systems, 2009, pp. 1–4 (July 2009).
[4] M. Haneda, P. M. W. Knijnenburg, and H. A. G. Wijshoff:“Code Size Reduction by Compiler Tuning,” in Proc. International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, pp. 186–195 (July 2006).

- 727 -