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:

1. The statements to be extracted are identified (by the programmer
   or by a programming tool).

2. If the statements are not contiguous, they are moved together so
   that they form a sequence that can be extracted into a procedure,
   and so that the semantics of the original code is preserved.

3. The statements are extracted into a new procedure, and are replaced
   with an appropriate call.

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.