1. Todd L. Veldhuizen and Jeremy Siek. Combining Optimizations, Combining Theories. Technical report 582, Indiana University, May 2003.

   Annotation:

   We consider the problem of how best to combine optimizations in imperative compilers. It is known that combined optimizations (or ``super-analyses'') can be strictly better than iterating separate improvement passes. We propose an explanation of why this is so by drawing connections between program analysis and the algebraic and coalgebraic views of programs and processes. We argue that ``optimistic'' analyses decide coinductively-defined relations and are based on bisimilarity. We relate combining program improvements to the problem of deciding combinations of theories. Iterating program improvements is similar to the Nelson-Oppen method of deciding combined theories: in Nelson-Oppen decision procedures communicate equalities, and iterated improvement passes implicitly communicate equalities via term replacements. To decide combined theories of bisimilarity, some ``co-Nelson-Oppen'' procedure is needed that propagates \e mph{inequalities} amongst decision procedures. Hence, iterating optimistic analyses fails to be effective because inequalities cannot be communicated by semantics-preserving rewrites. Superanalysis is conjectured to overcome this failing by behaving like a ``co-Nelson-Oppen'' decision procedure.

   [bibtex-entry]

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.

This document was translated from BibT_EX by bibtex2html