Program-optimizing transformations

Controlled transformations of a program, represented in one of its intermediate forms, that can be used during compilation (translation or program generation) with the purpose of improving the working characteristics of the program. These working characteristics are related with the use of computer resources by the program, the principal resources being the execution time and the amount of memory used.

Usually, every application of a program-optimizing transformation changes the local semantics of fragments of the program, but preserves the semantics of the program as a whole — the resulting program is either equivalent to the initial one or is an extension of it to a larger set of data.

One distinguishes machine-dependent program-optimizing transformations, which are defined by peculiarities of the machine language or other concrete characteristics of a concrete computer, and universal program-optimizing transformations (such are, e.g., removal of operators not accessible from the beginning of the program), which are defined only by the semantics included in the initial description of the algorithm, and are applicable to a large class of computers.

The usual means of improving a machine program using program-optimizing transformations are the removal of computations or objects from the process of executing the program or the substitution of simple computations for complicated ones (on the basis of a priori bounds on the computational complexity). This requires that the control, information and frequency relations arising in these processes between statements and objects of the program be taken into account. A program-optimizing transformation consists of: searching for relations of the types indicated that are necessary for it by means of local semantics of statements of the program (so-called flow analysis of the program); checking certain properties of the information collected (so-called context conditions); and transforming fragments of the program in case these conditions are satisfied (proper transformation by the given program-optimizing transformation).

According to the size of that part of the program (the so-called economy part) that is processed by a program-optimizing transformation independent of the environment, the program-optimizing transformations are divided into local, the economy part is not larger than a statement; global, the economy part is the entire program; and quasi-local, for which the economy part is a fragment of the program having a fixed intrinsic structure — e.g. a ray (a linear sequence of statements); a zone (a non-trivial strongly-connected subgraph of the control flow graph of the program) not containing other zones, or a hammock (a subgraph connected with the other part of the control flow graph at precisely two vertices — the input and output; the input vertex belongs to the hammock, the output vertex does not) not containing other hammocks or zones.

In order to diminish the time and volume complexity of a global program-optimizing transformation one often uses factorization — replacement of the global transformation by a series of quasi-local ones, applicable to fragments of the program in relation to their complexities.

Only for narrow classes of programs, such as, e.g., the class of linear programs, is it possible to construct a finite complete set of program-optimizing transformations. Therefore, in modern compilers a set of program-optimizing transformations is, to a large extent, constructed on heuristic grounds and essentially depends on the class of problems for which the compiler (translator or program generator) is intended. The choice of the sequence of application of program-optimizing transformations is important, since, as a rule, sets of program-optimizing transformations are not Church–Rosser systems, in which the result does not depend on the order of application of the transformations.

The set of program-optimizing transformations for compilers (translators) for the most widespread problem-oriented languages (cf. Problem-oriented language), such as, e.g. Algol; Fortran; PL/I, has been sufficiently well-studied and machine programs can be obtained that are comparable in quality with hand-written programs. The transformation consists of removal of repeated computations with identical results, partial execution of the program when translating, clearing the program from useless objects and computations, replacement of compound computations by simpler ones, diminishing the total amount of simultaneously existing objects, and contraction of the dimensions of the program.

References

[1]	A.V. Aho, J.D. Ullman, "The theory of parsing, translation and compiling" , 2 , Prentice-Hall (1973)
[2]	A.P. Ershov (ed.) , The ALPHA automatic programming system , Acad. Press (1971) (Translated from Russian)
[3]	V.N. Kas'yanov, I.V. Pottosin, "The technology of translation" , Novosibirsk (1979) (In Russian)
[4]	V.N. Kas'yanov, "Optimizing program transformations" , Moscow (1988) (In Russian)