Partial evaluation using dependence graphs
Manuvir Das, Thomas Reps · Minds at UW (University of Wisconsin) · 1998
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 inputs and unknown or inputs is a specialized version of the program, in which that require only the static inputs are absent. 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 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 that use only static data). We argue that this is an appropriate termination guarantee for partial evaluation of imperative programs. Our BTA algorithms are able to provide a termination guarantee for partial evaluation, without compromising the ability of the partial evaluator to aggressively identify static code and execute it at compile time. We present experimental results to support this claim.