Record Details

An Environment for Automatic Generation of Code Optimizers

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title An Environment for Automatic Generation of Code Optimizers
 
Creator Paleri, Vineeth Kumar
 
Subject Computer and Information Science
Compiler optimization
Automatic Generation
Code transformation
 
Description Code optimization or code transformation is a complex function of a compiler involving analyses and modifications with the entire program as its scope. In spite of its complexity, hardly any tools exist to support this function of the
compiler. This thesis presents the development of a code transformation system, specifically for scalar transformations, which can be used either as a tool to assist the generation of code transformers or as an environment for experimentation with code transformations.

The development of the code transformation system involves the formal specification of code transformations using dependence relations. We have written formal specifications for the whole class of traditional scalar transformations, including induction variable elimination - a complex transformation - for which no formal specifications are available in the literature. All transformations considered in this thesis are global.
Most of the specifications given here, for
which specifications are already available in the literature, are improved versions, in terms of conservativeness.The study of algorithms for code transformations, in the context of their
formal specification, lead us to the development of a new algorithm for partial redundancy elimination. The basic idea behind the algorithm is the new concepts of safe partial availability and safe partial anticipability. Our algorithm is computationally and lifetime optimal. It
works on flow graphs whose nodes are basic blocks, which makes it practical.In comparison with existing algorithms the new algorithm also requires four unidirectional analyses, but saves some preprocessing time. The main advantage of the algorithm is its conceptual simplicity.
The code transformation system provides an environment in which one can specify a transformation using dependence relations (in
the specification language we have designed), generate code for a transformer from its specification,and experiment with the generated transformers on real-world programs.
The system takes a program to be transformed, in C or FORTRAN, as input,translates it into intermediate code, interacts with the user to decide the transformation to be performed, computes the necessary dependence relations
using the dependence analyzer, applies the specified transformer on the intermediate code, and converts the transformed intermediate code back to high-level. The system is unique of its kind,providing a complete environment for the generation of code transformers, and allowing experimentations with them using real-world programs.
 
Publisher Indian Institute of Science
 
Contributor Srikant, Y N
Shankar, Priti
 
Date 2005-03-11T06:21:10Z
2005-03-11T06:21:10Z
2005-03-11T06:21:10Z
1999-07
 
Type Electronic Thesis and Dissertation
 
Format 797639 bytes
application/pdf
 
Identifier http://etd.iisc.ernet.in/handle/2005/82
null
 
Language en
 
Rights I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertation.