Semantics-Preserving Procedure Extraction

Raghavan Komondoor and Susan Horwitz
University of Wisconsin

Procedure extraction is an important program transformation that can be used to make programs easier to understand and maintain, to facilitate code reuse, and to convert ``monolithic'' code to modular or object-oriented code. Procedure extraction involves the following steps:

This paper addresses step 2: in particular, the conditions under which it is possible to move a set of selected statements together so that they become ``extractable'', while preserving semantics. Since semantic equivalence is, in general, undecidable, we identify sufficient conditions based on control and data dependences, and define an algorithm that moves the selected statements together when the conditions hold. We also include an outline of a proof that our algorithm is semantics-preserving. While there has been considerable previous work on procedure extraction, we believe that this is the first paper to provide an algorithm for semantics-preserving procedure extraction given an arbitrary set of selected statements in an arbitrary control-flow graph.