A technique for recursive invariance detection and selective program specialization

Giannotti, Fosca and Hermenegildo, Manuel V. (1991). A technique for recursive invariance detection and selective program specialization. In: "3rd International Symposium, PLILP '91", August 26-28, 1991, Passau, Germany. ISBN 9783540544449.

Description

Title: A technique for recursive invariance detection and selective program specialization
Author/s:
  • Giannotti, Fosca
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 3rd International Symposium, PLILP '91
Event Dates: August 26-28, 1991
Event Location: Passau, Germany
Title of Book: Programming Language Implementation and Logic Programming
Date: August 1991
ISBN: 9783540544449
Volume: 528
Subjects:
Freetext Keywords: Logic programming, Abstract interpretation, Program transformation, Program specialization, Parallel logic programming, Cycle invariant detection, Compile-time optimization, Programación lógica, Interpretación de resúmenes, Transformación de programas, Especialización de programas, Programación lógica paralela, Detección de circuitos invariables.
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (942kB) | Preview

Abstract

This paper presents a technique for achieving a class of optimizations related to the reduction of checks within cycles. The technique uses both Program Transformation and Abstract Interpretation. After a ñrst pass of an abstract interpreter which detects simple invariants, program transformation is used to build a hypothetical situation that simpliñes some predicates that should be executed within the cycle. This transformation implements the heuristic hypothesis that once conditional tests hold they may continué doing so recursively. Specialized versions of predicates are generated to detect and exploit those cases in which the invariance may hold. Abstract interpretation is then used again to verify the truth of such hypotheses and conñrm the proposed simpliñcation. This allows optimizations that go beyond those possible with only one pass of the abstract interpreter over the original program, as is normally the case. It also allows selective program specialization using a standard abstract interpreter not speciñcally designed for this purpose, thus simplifying the design of this already complex module of the compiler. In the paper, a class of programs amenable to such optimization is presented, along with some examples and an evaluation of the proposed techniques in some application áreas such as floundering detection and reducing run-time tests in automatic logic program parallelization. The analysis of the examples presented has been performed automatically by an implementation of the technique using existing abstract interpretation and program transformation tools.

More information

Item ID: 14485
DC Identifier: http://oa.upm.es/14485/
OAI Identifier: oai:oa.upm.es:14485
Official URL: http://link.springer.com/chapter/10.1007%2F3-540-54444-5_109
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 14 Feb 2013 07:34
Last Modified: 21 Apr 2016 14:11
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM