October 06, 2004
Hilton Suites Toronto/Markham Conference Centre
Markham, ON
Associated with CASCON 2004
(http://www.cas.ibm.com/cascon)
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.