variable is decremented, reflecting the fact that a mispredicted branch was taken. The presence of such possibly negative corrections imply that the MAXPATH value now also has to act as a safety barrier with respect to subtractions occurring right after a reset of the consumption variable by the triggerConsume() method. If MAXPATH is too small, the consumption variable might then overflow on the negative side, to become strongly positive, which is of course wrong.
This example also shows that entirely new accounting blocks (im- plemented by the additional else block) sometimes have to be added to the control-flow graph in order to implement corrections due to mispredictions. Another case that requires the insertion of dedicated accounting blocks is the following: if a block constitutes the join point of two execution paths that both are considered as mispredictions, then it will not be able to do the accounting correction for the two of them. To solve this, we create a second accounting block so that each path may implement its own correction.
6.2.2. Chosen Heuristics It is a challenge to define adequate heuristics for identifying successful paths, only on the basis of the bytecode that is being processed. Such heuristics should be relatively inexpensive to evaluate, and, for simplic- ity, use only information available from the control flow graph. This is, first, because we know from the aggressive approximation experiment that the margin for improvement is relatively narrow (see Table II). Another reason is that there is a trend towards load-time, or even run- time instrumentation practices, which in turn urge for the development of computationally efficient transformation tools.
The heuristics are expressed relative to the control flow graph, where each node is a primitive accounting block. The heuristics we explored try to identify the following kinds of branches (loosely following the classification of ):
Loop entry branches are branches that decide whether execution will continue into a subsequent loop or avoid it. These are expected to lead into the loop.
Loop branches are branches inside a loop that determine whether execution will continue inside or exit the loop.
exit branches are predicted to fail;
backward branches are predicted to succeed;
Non-loop branches, i.e. branches that are not inside loops, or that are inside a loop, but do not exit or branch backwards: