Add profiling counters

[apt1002]

Profiling counters are needed to collect statistics about the behaviour of the program, and thereby to decide what specializations to compile. Specializations in turn add more profiling counters and collect more detailed and relevant information.

Exploiting redundancy

We are interested in several different statistics:

• how often each fetch transition is executed
• how often each retire transition is executed
• how often each specialization is visited
• how often each specialized situation occurred, including when bypassed via a greater specialization

It is not necessary to count all of these, because the counts are redundant. We know that for every specialization the number of times control flow enters it is equal to the number of times control flow exits it. It suffices to have only one counter per specialization. The other counts can then be computed by induction on the specialization structure.

The best place to put the profiling counters is on the retire transitions. There are generally fewer retire than fetch transitions (i.e. we retire more instructions per transition), and there is opportunity to increment a counter in parallel with other things going on at the time.

Probability model

There are various circumstances in which we have to guess statistics about specializations that don't exist. For example:

• Compiling new code has a fairly large O(1) cost, e.g. calling mprotect and flushing and reloading caches. To amortize this cost, we must compile a reasonably large amount of code at a time. We must guess what specializations are going to be useful.

• After compiling new code, we must set the profiling counters to sensible values. We hope that the new code paths will be used in place of older, less specialized code paths. It would be wasteful to initialize to zero all the counters on the new code paths, because we have collected useful information about the old code paths. We should guess what values the counters would have reached if the specializations had been constructed earlier.

The following approximations are plausible (f(x) is the number of times specialization x has occurred, including the times it was bypassed):

• f(abc) / f(ab) is approximately f(bc) / f(b). They are both roughly the chance that b is followed by c; the additional information that b was preceded by a will usually make only a small difference.
• f(abc) / f(bc) is approximately f(ab) / f(b), similarly.

These two rules of thumb are equivalent, and perhaps a more practical expression is that f(abc) is approximately f(ab) * f(bc) / f(b).

Cost model

As compiling new code is expensive, we want to model the cost.

We resist compiling new code until the counter on a retire transition exceeds some threshold, e.g. 1000. Probably the best implementation is a counter that starts at 1000 and counts down to zero, but let's pretend that the counter counts upwards. The purpose of the counter is to ensure that we spend as much effort executing code as compiling it. Effectively, it prevents us compiling the cold code. The counter is the cheapest mechanism I can imagine that will do this job.

The total of all the counters is a measure of the total execution time. If we arrange that all counters are usually somewhere fairly random between 0 and 1000, their total will grow in proportion to the amount of code we generate. I don't think it's necessary to remove counts when we compile new code; instead we should reassign some of the counts to the new code, preserving the total.