(Paper #154)
Speculative multithreading (SpMT) promises to be an effective mechanism for parallelizing non-numeric programs. Data dependence is 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 determine accurate data dependence information. Determining this information has been an Achilles' heel in SpMT compilation. Existing interprocedural analyses are unsuitable for large programs, because 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 the 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.
Keywords:
Compilers
Programming Languages