next up previous
Next: Predicting Code Size and Up: Optimizer Design Previous: Knapsack Model

Predicting Execution Frequencies

The basic hypothesis behind heuristic branch prediction is that the structure of the source code can be used by the compiler to derive estimates on how frequently different sections of the code will be executed. In the following, we apply this idea to an interface definition.

Let tex2html_wrap_inline455 be the average number of occurrences of field i in all values of type t in a given workload. For estimating tex2html_wrap_inline455 , the following cases can be distinguished:

In the case of optional fields, special care must be taken. In many interface definition languages, optional fields can be used to construct recursive types. For our method to work, it must be ensured that the flow along a recursive path is smaller than 1. A flow greater or equal to 1 would correspond to an infinite recursion, which is impossible. Thus, an additional pass must be added to the frequency predictor that loops in the type reference graph caused by recursive optional fields.

We define the type reference graph of an interface specification as a tuple tex2html_wrap_inline489 . V' corresponds to the set of all type definition nodes in the interface specification's syntax graph. The set of weighted arcs ((E', w) is computed by locating all type reference nodes in the syntax graph, and adding an arc from the type definition node containing the type reference node to the type definition node that is referenced. The weight of this arc is equal to the value of tex2html_wrap_inline455 of the type reference node at which the arc originates.

The type reference graph is a weighted graph that can be interpreted as a Markov model for the behavior of the presentation conversion code. V' correspond to the states of the Markov model. The transition probabilities between the states can be derived from the weighted arcs (E', w). Following an approach proposed in (Ramamoorthy, 1965), the graph can be mapped onto a system of linear equations that represents the equations for determining the visit counts of the nodes. The frequency of each type definition node can be computed by solving this LEQ.


next up previous
Next: Predicting Code Size and Up: Optimizer Design Previous: Knapsack Model

Philipp Hoschka
Sun Oct 26 21:35:40 MET 1997