Automated Discovery of Machine-Specific Code Improvements
CALIFORNIA UNIV BERKELEY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES
Pagination or Media Count:
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.
- Computer Programming and Software