Worst-case execution time (WCET), average-case execution time (ACET), and code size are three statistics characterizing program quality. Compiler writers have developed optimizations by which a compiler can improve one or more of these statistics. Individual optimizations, such as common subexpression elimination and constant folding, can be carried out at one or more different points during the compilation. This leads to the concept of an optimization sequence to define the compiler’s behavior. The compiler writer chooses an optimization sequence that minimizes the statistic(s) of interest.

Unfortunately, changing the sequence to improve one statistic often worsens another. A Pareto improvement is one in which one statistic is improved without worsening any other; a Pareto optimal optimization sequence is one in which no change leads to a Pareto improvement. The combinatorial explosion of optimization sequences makes an exhaustive search for the best sequence impossible. The authors therefore use genetic algorithms to guide optimization sequence selection.

The paper covers two experiments. One seeks an optimization sequence that is Pareto optimal with respect to WCET and ACET, and the other seeks Pareto optimality with respect to WCET and code size. The search process is automated, and the paper describes both the search mechanisms and the results. Its descriptions are clear, and copious references are provided. Anyone interested in compiler optimization should become familiar with the principles laid out here.