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 be the average number of occurrences of field i in all values of type t in a given workload. For estimating , the following cases can be distinguished:

• field i is part of a union type: , where n is the number of fields in the union.
• field i is part of a structure type:
  • field i is not marked as optional: .
  • field i is marked as optional: , . As explained below, special care must be taken when calculating in the case of recursive types.
• field i is part of an array type:
  • the length of the array is unknown: .
  • the length of the array is known: , where n is the length of the array.

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 . 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 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.