The Task of Automatic Generation of Peephole-Optimizations: Approaches Overview, Solution of the Optimal Expansion of Managed Instructions Set Architecture

Abstract

This article discusses the problem of automatic generation of peephole-optimization of the static bytecode optimizer of a virtual machine (VM) concerning the task of improving the instruction set architecture (ISA) of the VM. Peephole optimization is one of the stages of the optimizing compiler. It applies to the code of the original input program in an intermediate representation (IR or LLIR) and resides in finding sequences of instructions that match known templates and replacing them with shorter or faster semantically equivalent sequences. The current peephole optimization approaches assume some limited set of templates or functions that are manually encoded while relying on the engineers' in-depth knowledge of the corresponding IR and the structure of the compiler output programs. Also, for various IRs you must re-encode similar peephole optimizations, which entails additional monetary and time costs. An alternative approach is superoptimization, which consists of the automatic generation of templates and their matching rules. Among the main parts of the superoptimizer there are the search algorithm, the cost function, and the equivalence verifier. In the article algorithm for solving a more specialized subtask was implemented and tested. It consists in finding and counting the most frequent instruction templates, which can later be replaced with one new instruction to optimize execution time and/or bytecode size or be analyzed by a programmer to investigate the weaknesses of the existing ISA and obtain information about the specifics of the source data.

Keywords

• automatic generation of peephole optimizations
• compilers
• peephole optimizations
• superoptimizers
• instruction set architecture
• bytecode
• virtual machines