BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-98-1608
       ENTRY:: June 12, 1998
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A New Perspective on Partial Evaluation and Use Analysis
        TYPE:: Thesis
        TYPE:: Technical Report
      AUTHOR:: Katz, Morris J.
        DATE:: June 1998
       PAGES:: 224
    ABSTRACT:: Partial evaluators are compile time optimizers achieving
               performance improvements through a program modification
               technique called specialization. Partial evaluators produce
               one or more copies, or specializations, of each procedure in
               a source program in the output program. Specializations are
               distinguished by being optimized for invocation from call
               sites with different characteristics, for example, placing
               certain constraints on argument values. Specializations are
               created by partially executing procedures, leaving only
               unexecutable portions as residual code. Symbolic execution
               can replace variable references by the referenced values,
               executed primitives by their computed results, and function
               applications by the bodies of the applied functions, yielding
               inlining. One core challenge of partial evaluation is
               selecting what specializations to create. Attempting to
               produce an infinite number of specializations results in
               divergence. The termination mechanism of a partial evaluator
               decides whether or not to symbolically execute a procedure in
               order to create a new specialization. Creating a termination
               mechanism that precludes divergence is not difficult.
               However, crafting a termination mechanism resulting in the
               production of a sufficient number of appropriate
               specializations to produce high quality residual code while
               still terminating all, or most, of the time is quite
               challenging. This dissertation presents a new type of
               analysis, called use analysis, forming the basis of a
               termination mechanism designed to yield a better combination
               of residual code quality and frequent termination than the
               current state-of-the-art.
       NOTES:: [Adminitrivia V1/Prg/19980612]
         END:: STAN//CS-TR-98-1608