a fast approximate interprocedural analysis for speculative multithreading compilers
Speculative multithreading (SpMT) promises to be very effective for parallelizing non-numeric programs. Data dependences are perhaps the most important factor in the crucial step of deciding the thread boundaries, and SpMT compilers need to estimate data dependences as precisely as possible. Interprocedural points-to and side-effects information is essential to accurately determine data dependences. Determining this information has been an Achilles' heel in SpMT compilation. Existing interprocedural analyses are unsuitable for large programs, as they have high complexity or generate imprecise (very conservative) information that is not useful for aggressive speculative parallelization.This paper presents a novel interprocedural analysis scheme that is highly effective for use in SpMT compilers. It has running time and memory requirement almost linear in the number of procedures in the input program. The information it generates is comparable in accuracy with those generated by highly accurate context-sensitive interprocedural analyses, although it does not guarantee safe information (which is not a requirement for SpMT compilers any way). We implemented this interprocedural analysis in our SpMT compiler, and parallelized large non-numeric programs from the SPEC 2000 suite. Parallel execution of these threads in an SpMT simulator demonstrate good speedups for these non-numeric programs.
approximation interprocedural analysis procedure speculating multithreading thread compilation speculative multithreading (spmt) effect parallel program data dependencies factor estimates informal complexity use paper scheme timing memorialized requirements input accuracy context-sensitivity simulation demonstrate speedup point pointer analysis thread-level parallelism (tlp)