INTERPROCEDURAL DATA-FLOW ANALYSIS IN AN EXECUTABLE OPTIMIZER

Interprocedural dataflow information enables link-time and post-link-t ime optimizers to perform analyses and code transformations that are n ot possible in a traditional compiler. This paper describes the interp rocedural dataflow analysis techniques used by Spike, a post-link-time optimizer for Alpha/NT executables. Spike uses dataflow analysis to s ummarize the register definitions, uses, and kills that occur external to each routine, allowing Spike to perform a variety of optimizations that require interprocedural dataflow information. Because Spike is d esigned to optimize large PC applications, the time required to perfor m interprocedural dataflow analysis could potentially be unacceptably long, limiting Spike's effectiveness and applicability. To decrease da taflow analysis time, Spike uses a compact representation of a program 's intraprocedural and interprocedural control flow that efficiently s ummarizes the register definitions and uses that occur in the program. Experimental results are presented for the SPEC95 integer benchmarks and eight large PC applications. The results show that the compact rep resentation allows Spike to compute interprocedural dataflow informati on in less than 2 seconds for each of the SPEC95 integer benchmarks. E ven for the largest FC application containing over 1.7 million instruc tions in 340 thousand basic blocks, interprocedural dataflow analysis requires just 12 seconds.