Compiler-Assisted Sub-Block Reuse

The fact that instructions in programs often produce repetitive results has motivated researchers to explore various alternatives to exploit this value locality, such as value prediction and value reuse. Value prediction improves the available Instruction-Level Parallelism (ILP) by allowing dependent instructions to be executed speculatively after predicting the values of their operands. Value reuse, on the other hand, tries to remove redundant computations by buffering the previously produced results of instructions and skipping the execution of instructions with repeating inputs. Previous value reuse mechanisms use a single instruction or a naturally formed instruction group, such as a basic block, a trace, or a function, as the reuse unit. These naturally formed instruction groups are readily identifiable by the hardware at run-time without compiler assistance. However, the performance potential of a value reuse mechanism depends on its reuse detection time, the number of reuse opportunities, and the amount of work saved by skipping each reuse unit. Since larger instruction groups typically have fewer reuse opportunities than smaller groups, but also provide greater benefit for each reuse-detection process, it is very important to find the balance point that provides the largest overall performance gain. In this paper, we propose a new mechanism called sub-block reuse to intelligently group instructions into reuse units using compiler-assistance. The goal is to balance the reuse granularity and the number of reuse opportunities. The sub-blocks are produced by slicing the basic blocks at compile-time using appropriate dataflow considerations. Our simulations with the SPECint95 benchmarks show that sub-block reuse with compiler assistance has a substantial and consistent potential to improve the performance of superscalar processors with speedups ranging from 10-22%.