This thesis describes the use of program dependence graphs, as opposed to control flow graphs, as the basis for the partial evaluation of imperative programs. Partial evaluation is a program specialization operation in which programs with multiple inputs are specialized to take into account known values for some of their inputs. Thus, the result of partially evaluating a program given a division of its inputs into known or ``static'' inputs and unknown or ``dynamic'' inputs is a specialized version of the program, in which computations that require only the static inputs are absent. The specialized program produces exactly the same output, when run on the dynamic inputs, as that produced by the original program when run on all of its inputs.

A known problem with partial evaluators has been that in attempting to aggressively identify static code, they may fail to terminate on some subject programs. However, partial evaluators are increasingly being developed for heavily used languages, for which the goal is to allow an arbitrary user to improve the performance of his or her program by using a partial evaluator as a ``black box'' that optimizes code, in much the same way that optimizing compilers have been used for years. Therefore, it is necessary to ensure that partial evaluators provide a semantic guarantee of termination, while optimizing the common case.

A partial evaluator may fail to terminate on a subject program if its analysis phase (termed ``binding-time analysis'' or BTA) fails to identify variables whose values are built up in dynamic loops (i.e., loops whose predicates use dynamic data) as dynamic. We use program dependence graphs, which make both data dependences and control dependences explicit in their structure, as the basis for BTA algorithms that tackle this problem. As a result, our algorithms provide a termination guarantee for partial evaluation in the absence of ``static-infinite computations'' (roughly, infinite computations that use only static data). We argue that this is an appropriate termination guarantee for partial evaluation of imperative programs. In order to handle a real imperative language such as C, with complex features including arbitrary control flow and pointer variables, we identify a new form of program dependence, called ``loop dependence.'' Our BTA algorithm is able to use these dependences to provide a termination guarantee, without compromising the ability of the partial evaluator to aggressively identify static code and execute it at compile time.

In the case of functional programs that manipulate only list data, it is possible to design analysis algorithms that provide a termination guarantee for partial evaluation on all programs (including programs that contain static-infinite computations), without unduly compromising the ability of the analysis to identify static code. We present an analysis algorithm that uses generalized reachability properties on a dependence graph representation to provide such a termination guarantee.

Dependence graphs provide a natural basis for the analysis actions of partial evaluation because they make program dependences explicit in their structure. Another question that arises is whether dependence graphs provide a basis for the specialization actions of partial evaluation as well. We address this question by extending the specialization operation to dependence graphs.

Finally, we present experimental results obtained using our implementation of the ideas presented in this thesis.

(Click here to access the disseration.)