Next: Control Dependence Analysis Up: Relaxing Control Flow Previous: Relaxing Control Flow

Speculation with Branch Prediction

While speculation on all possible paths is infeasible in practice, limited speculation is commonly used throughout computer systems to improve performance. For example, almost all modern processors prefetch the instructions following a conditional branch. Some machines such as the IBM 360/91 pursue both execution paths by also prefetching the instructions at the branch target.

A common technique to improve the efficiency of speculation is to only speculate on instructions from the most likely execution path. The success of this approach depends on the accuracy of branch prediction. Even for non-numeric code, both hardware and software prediction algorithms have been shown to be accurate over 85%of the time [8][6].

Extending speculative instruction fetching to speculative execution creates additional parallelism. However, unlike instruction fetching, speculatively executing an instruction may generate unwanted side effects. These side effects must be discarded if the branch prediction is incorrect. Both hardware and software techniques can be used to implement speculative execution.

Various hardware structures have been proposed to support speculative execution [16][13][11][7]. These structures store the results of the speculative instructions until the branch direction is determined. If the branch prediction was correct the results are committed, otherwise they are discarded. Hardware scheduling, however, is limited by the fact that an instruction simply cannot execute before it is fetched. It is difficult to fetch instructions from far ahead along the predicted execution path, especially for programs with complex control flow.

Software techniques overcome instruction fetch limitations by reordering instructions. Trace scheduling identifies the most commonly executed trace and schedules the instructions within the trace as if they belong to one large basic block [4][2]. However, implemented trace scheduling algorithms only employ very limited forms of speculation. Smith et al. extend software scheduling with hardware support for speculative execution [15]. Instructions to be speculatively executed are boosted before a conditional branch. These instructions are labeled so that their results are discarded or committed when the branch condition is determined. This combines the ability of software to eliminate fetch limitations and the ability of hardware to speculatively execute instructions with side effects.

Next: Control Dependence Analysis Up: Relaxing Control Flow Previous: Relaxing Control Flow

Bob Wilson