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

Sun Oct 26 21:35:40 MET 1997