3rd Workshop on Compiler-Driven Performance

October 06, 2004
Hilton Suites Toronto/Markham Conference Centre
Markham, ON

Associated with CASCON 2004


Compiler Analyses for Improved Return Value Prediction

Christopher J.F. Pickett and Clark Verbrugge - McGill University

Speculative multithreading (SpMT) is a technique for automatic parallelisation of single-threaded programs. Speculative Method-Level Parallelism (SMLP), a variant of SpMT, performs significantly better in the presence of accurate return value prediction. We previously implemented and characterized some common value predictors in SableVM, and introduced a new memoization-based predictor. We now look to improving return value prediction further using Soot, our Java bytecode optimization and transformation framework. We present an interprocedural parameter dependence analysis that eliminates parameter inputs to our memoization predictor that do not affect the return value. This increases sharing in memoization lookup tables, improving accuracy and reducing size. We also present a return value use analysis to determine which return values are consumed, and furthermore label those that are only used inside boolean and branch expressions. This allows us to increase accuracy by substituting incorrect predictions at runtime, provided the relaxed constraints given by this analysis are met. We use Soot's attribute generation framework to enable SableVM to exploit the results of these analyses. This work has implications for non-speculative memoization strategies, and for general purpose load value prediction.

Presentation Slides.