next up previous
Next: The Region Graph Up: Interprocedural Framework Previous: Region-Based Flow-Sensitive Analysis.

Selective Procedure Cloning.

For procedures invoked on multiple distinct paths through a program, traditional interprocedural analysis forms a conservative approximation of the information entering the procedure that is correct for all paths. Such approximations can affect the precision of analysis if a procedure is invoked along paths that contribute very different information. Path-specific interprocedural information has previously been obtained either by inline substitution or by tagging data-flow sets with a path history through the call graph, incurring a data-flow set expansion problem corresponding to the code explosion problem of inlining [8,16,17,18]. To avoid such excessive space usage, we utilize path-specific information only when it may provide opportunities for improved optimization. Our system incorporates selective procedure cloning, a program restructuring in which the compiler replicates the analysis results for a procedure to analyze it in the context of distinct calling environments [4]. By applying cloning selectively according to the unique data-flow information it exposes, we can obtain the same precision as full inlining without unnecessary replication.

Saman Amarasinghe
Mon Oct 2 11:00:22 PDT 1995