Peter Bernard Kessler

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-84-213
December 1984

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-213.pdf

Retargetable compilers generate code using machine-independent algorithms guided by the results of an analysis of the target machine. The analysis may be performed either by the compiler writer or by a compiler phase construction program. An implementation must be found for each operation of the source language.

Additional analysis may reveal special features of the target architecture that may be exploited to generate efficient code. Such analysis is optional; it affects only the quality of the code produced. This dissertation examines one method of automating the examination of a machine description to discover machine-specific idioms for inefficient instruction sequences.

Previous techniques discovered idioms by composing instructions into sequences and searching for more efficient implementations of those sequences. Analysis by composition takes time exponential in the length of the sequences examined. Practical considerations limit such analysis to sequences composed of pairs of instructions. The thesis of this dissertation is that an interesting class of idioms can be discovered by decomposing instructions into inefficient sequences to be avoided during compilation. Decomposition is shown to take no more time than composition in the worst case, and is shown to take less time on the average. Analysis by decomposition naturally discovers idioms for sequences longer than pairs of instructions.

Idioms on a target machine and predicates for their applicability are discovered during compiler construction. Consequently, alternative instruction sequences must be identified without knowledge of the particulars of individual programs, such as instances of instruction sequences, operands, or data flow contexts. These program-dependent properties can be exploited by recording the conditions under which one instruction sequence is equivalent to another. Program-independent predicates on instruction equivalence are evaluated during compiler construction, leaving only program-dependent predicates to be evaluated during compilation.

The design of an idiom discoverer is discussed and a prototype implementation is examined. One application of idioms is demonstrated with a prototype retargetable transformer of assembler source code. This transformer can be used to replace hand-written case analysis routines in a retargetable code generator. Other applications of idioms are suggested.

Advisor: Susan L. Graham

BibTeX citation:

@phdthesis{Kessler:CSD-84-213,
    Author = {Kessler, Peter Bernard},
    Title = {Automated Discovery of Machine-Specific Code Improvements},
    School = {EECS Department, University of California, Berkeley},
    Year = {1984},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5739.html},
    Number = {UCB/CSD-84-213},
    Abstract = {Retargetable compilers generate code using machine-independent algorithms guided by the results of an analysis of the target machine. The analysis may be performed either by the compiler writer or by a compiler phase construction program. An implementation must be found for each operation of the source language.  <p>  Additional analysis may reveal special features of the target architecture that may be exploited to generate efficient code. Such analysis is optional; it affects only the quality of the code produced. This dissertation examines one method of automating the examination of a machine description to discover machine-specific idioms for inefficient instruction sequences.  <p>  Previous techniques discovered idioms by composing instructions into sequences and searching for more efficient implementations of those sequences. Analysis by composition takes time exponential in the length of the sequences examined. Practical considerations limit such analysis to sequences composed of pairs of instructions. The thesis of this dissertation is that an interesting class of idioms can be discovered by decomposing instructions into inefficient sequences to be avoided during compilation. Decomposition is shown to take no more time than composition in the worst case, and is shown to take less time on the average. Analysis by decomposition naturally discovers idioms for sequences longer than pairs of instructions.  <p>  Idioms on a target machine and predicates for their applicability are discovered during compiler construction. Consequently, alternative instruction sequences must be identified without knowledge of the particulars of individual programs, such as instances of instruction sequences, operands, or data flow contexts. These program-dependent properties can be exploited by recording the conditions under which one instruction sequence is equivalent to another. Program-independent predicates on instruction equivalence are evaluated during compiler construction, leaving only program-dependent predicates to be evaluated during compilation.  <p>  The design of an idiom discoverer is discussed and a prototype implementation is examined. One application of idioms is demonstrated with a prototype retargetable transformer of assembler source code. This transformer can be used to replace hand-written case analysis routines in a retargetable code generator. Other applications of idioms are suggested.}
}

EndNote citation:

%0 Thesis
%A Kessler, Peter Bernard
%T Automated Discovery of Machine-Specific Code Improvements
%I EECS Department, University of California, Berkeley
%D 1984
%@ UCB/CSD-84-213
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5739.html
%F Kessler:CSD-84-213