@MASTERSTHESIS\{IMM2007-05406,
    author       = "M. Queva",
    title        = "Phase-ordering in optimizing compilers",
    year         = "2007",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Assoc. Prof. Christian Probst, {IMM,} {DTU}.",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/5406-full.html",
    abstract     = "The “quality” of code generated by compilers largely depends on the analyses and optimizations applied to the code during the compilation process. While modern compilers could choose from a plethora of optimizations and analyses, in current compilers the order of these pairs of analyses/transformations is fixed once and for all by the compiler developer. Of course there exist some flags that allow a marginal control of what is executed and how, but the most important source of information regarding what analyses/optimizations to run is ignoredthe source code. Indeed, some optimizations might be better to be applied on some source code, while others would be preferable on another.

A new compilation model is developed in this thesis by implementing a Phase Manager. This Phase Manager has a set of analyses/transformations available, and can rank the different possible optimizations according to the current state of the intermediate representation. Based on this ranking, the Phase Manager can decide which phase should be run next.

Such a Phase Manager has been implemented for a compiler for a simple imperative language, the while language, which includes several Data-Flow analyses. The new approach consists in calculating coefficients, called metrics, after each optimization phase. These metrics are used to evaluate where the transformations will be applicable, and are used by the Phase Manager to rank the phases.

The metrics are calculated using a new algorithm that approximates the dataflow analyses for the while language. This algorithm skims through the intermediate representation of the program only once, and thus solves the analyses’ equations faster than classical worklist algorithms.

In order to evaluate the metric-based approach, a benchmark suite is created. This suite generates a large amount of regular expressions that express various orders of optimizations. The metric-based phase-ordering is applied on several benchmark programs and compared to the best regular expression on each of these programs.

Finally, this thesis considers the interactions between the transformations considered, as well as the effects of these transformations on the size and speed of the program to improve the metric-based algorithm. The resulting versions of the phase-ordering mechanism are then evaluated using the benchmark suite."
}