Re: Partial evaluation vs flow-graph analysis

Christian Fabre <fabre@gr.osf.org> writes:


>Partial evaluation seems to be a hot topic in the compiler field
>nowaday. As far as we've understood, the basic idea is to partially
>evaluate (sic) a program based on the information we are able to
>gather about its arguments. This requires some sort of intrepreter
>(or is it a meta-interpreter?) to compute the simplified program.


>Did we miss something obvious so far?


I don't think so --- usually "the information we are able to gather
about its arguments" means the actual _values_ of some (static)
argument that are constant for a number of runs.


>This makes us think that the kind of tasks well suited for partial
>evaluation can also be done, for most of them, with "older" techniques
>such as flow-graph equations.


>So our question is what kind of optimisations will partial evaluation
>make possible that are out of reach of a classical optimizer (and
>vice-versa)?


Conceptually, a partial evaluator is nothing but a powerful
interprocedural constant propagation transformation (where the values
of the static parameters are inserted as constants in the program
text), which allows loop unrolling, call unfolding, context
propagation, procedure cloning.


On the other hand, most program optimizations can be seen as special
instances of partial evaluation...


>Is there some paper comparing the two techniques?


In chapter 17 of the book "Partial Evaluation and Automatic Program
Transformation" by Jones, Gomard and Sestoft there is some discussion
of the relation to Fold/Unfold and to deforestation.


>Also, most of the papers talk about PE in the context of functional
>languages like ML or Haskell. Is this technique also usefull/usable
>for imperative languages like C, C++, Java or Eiffel?


Look at


http://www.diku.dk/research-groups/topps/activities/cmix.html


for a partial evaluator for C. There is some research on PE of Java at
DIKU and (I believe) in France --- I wouldn't expect any conceptual
difficulties.


Cheerio,


Christian
--
Christian Mossin E-mail: mossin@diku.dk
DIKU, Department of Computer Science Phones: Off: +45 35 32 14 06
Universitetsparken 1, DK-2100 Copenhagen East, DENMARK Fax: +45 35 32 14 01
http://www.diku.dk/research-groups/topps/personal/mossin.html
--

Return to the comp.compilers page.
Search the comp.compilers archives again.