PDO: Models and Optimization Planners

The Continuous Compiler uses a set of models to guide its optimization decisions. We call the process of guiding optimization decisions Profit-Driven Optimization (PDO) because the benefit and cost of an optimization is taken into account when deciding how and what optimizations to apply. Here, the benefit is the "profit" of the applying the optimization. As shown in the figure above, these models are the code, optimization and resource model.

PDO Models

The code model is automatically constructed by extracting characteristics from the application source code that are effected by applying an optimization. For example, in classic loop optimizations, the code model abstracts information about a loop nest and its references for data locality optimizations. For scalar optimizations, the code model abstracts information about register pressure and instructions. The code model is constructed for each code context that is being considered for an optimization.

The optimization model is developed by a compiler writer to describe the semantic effects of applying an optimization. For example, in scalar optimizations, changes on the code are described as basic edits with deletions and insertions. The optimization model is applied to the extracted code model to determine a new code model that represents the optimized code.

The resource model is developed by a compiler writer to describe how machine resources (e.g., registers, code size, etc.) are impacted by a code model. For example, in scalar optimizations, the resource model captures the number and type of machine registers and instruction latencies. For data locality optimizations, the resource model describes the data cache.

Predicting Optimization Profit

Using the original code model and the optimized code model, PDO can make a prediction about the profit of an optimization. A prediction is an estimate of how the optimization affects some profit measure, such as performance. As an example, for loop optimizations, PDO makes a prediction about the profit of a data locality optimization by estimating whether data cache misses are increased or decreased. The predictions need to be only accurate enough that the correct decisions can be made. That is, PDO needs to only predict the profit trend accurately, rather than the absolute profit. Furthermore, because the original code model is constructed for a particular code context, very fine-grained decisions can be made about how and what optimizations to apply.

Optimization Planning

The profit predictions from PDO can be used to guide optimization planners that decide how to apply an optimization. For example, a simple planner is a "selectively applying" planner. This planner uses PDO to decide whether to apply a single optimization in a given code context. If the PDO predicts that there is a profit, the planner will apply the optimization. A more sophisticated planner can search for the best sequence of optimizations to apply in a context. We have built such planners based on genetic algorithms that use PDO to score optimization sequences. Our results show that PDO is very accurate and can successfully guide optimization planners.

[ Return to PDO Web Page ] [ Return to CoCo Home ]