Is superoptimization viable for VM instruction sets?. (21st November 2013)

• Record Type: Journal Article
• Authors: Hume, Tom; Watson, Des
• Is Part Of: Software, practice & experience. Volume 45:Number 4(2015)
• Page Start: 571
• Page End: 579
• Publication Date: 2013-11-21
• Subjects: Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2240
• Languages: English
• ISSNs: 0038-0644

Abstract

<abstract abstract-type="main" id="spe2240-abs-0001"> <title>Summary</title> <p id="spe2240-para-0001">The technique of superoptimization attempts to ensure true optimality of a code (according to predefined criteria) through an exhaustive search of all potentially viable programs. Implementations have demonstrated that superoptimizers are capable of finding shorter programs than those hand optimized for size by experts or produced by conventional compilers. Superoptimizers have been developed for many machine architectures and used for diverse purposes including automating peephole optimization and binary translation of instruction sets. The output of superoptimizers is frequently surprising to human experts and often takes advantage of side effects or obscure characteristics of the targeted hardware. Virtual machines (VMs) are increasingly popular in implementations of programming languages, because they can provide a common platform across heterogeneous hardware architectures. This paper examines whether superoptimization could be a viable technique for VMs. A superoptimizer for the Java VM (JVM) has been developed and used to generate demonstrably size‐optimized versions of some simple mathematical functions, implemented in a Java bytecode. We have shown that these versions are shorter than both implementations shipped with the Java software development kit and those generated by the Java compiler. We also have some useful observations concerning techniques to allow larger programs to be optimized in a reasonable time by this approach. Copyright © 2013 John Wiley & Sons, Ltd.</p> </abstract>