Compile-Time Memory Disambiguation for C Programs.
Publication Year:
  Ben-Chung Cheng
  PhD thesis, Department of Computer Science, University of Illinois, Urbana, IL, May 2000
Static memory disambiguation is a compile-time technique which determines whether or not two memory instructions access the same memory location at run-time. With fully disambiguated memory accesses, instruction scheduling and code optimization can be conducted in a much more aggressive manner. As the speed gap between the processor and memory widens, the value of optimized memory accesses will scale accordingly. To disambiguate memory accesses beyond scalar local variables, a critical task in an optimizing compiler is to perform interprocedural pointer analysis in order to handle indirect memory accesses through pointers in the presence of function calls with side-effects. Interprocedural pointer analysis has long been considered as too expensive to addord. Therefore unlike function inlining, register allocation, and SSA analysis, interprocedural pointer analysis has not been integrated into commercial compilers. The core of this dissertation is a new modular interprocedural pointer analysis algorithm which significantly improves the feasibility of static memory disambiguation. The proposed algorithm can handle much larger C programs with realistic language features. Due to its modular feature, the amounts of time and memory requirements are greatly reduced. The dissertation also evaluates the effectiveness of the proposed algorithm on the complete SPECcint92 and SPECcint95 benchmark suites. Significant performance improvements are observed from these pointer-intensive programs.