Задача автоматической генерации peephole-оптимизаций: обзор подходов, решение проблемы оптимального расширения архитектуры набора managed инструкций
Authors: Антипина А.В. 
Published: December 2024

В данной статье рассматривается проблема автоматической генерации peephole-оптимизаций статического оптимизатора байт-кода виртуальной машины (ВМ) применительно к задаче усовершенствования архитектуры набора инструкций (ISA) ВМ. Peephole-оптимизация является одним из этапов работы оптимизирующего компилятора, применяющаяся к коду исходной входной программы в промежуточном представлении (IR или LLIR) и заключающаяся в поиске последовательностей инструкций, совпадающих с известными шаблономи, и замене их на более короткие или более быстрые семантически эквивалентные наборы. Существующие подходы peephole-оптимизаций предполагают наличие некоторого ограниченного набора шаблонов или функций, которые закодированы вручную, полагаясь при этом на глубокие знания инженеров соответствующего IR и структуры выходных программ данного компилятора. Также для различных IR необходимо заново кодировать аналогичные peephole-оптимизации, что влечет дополнительные денежные и временные расходы. Альтернативным подходом является супероптимизация, заключающаяся в автоматической генерации шаблонов и правил их сопоставления. Среди основных частей супероптимизатора присутствуют алгоритм поиска, функция затрат и верификатор эквивалентности. В статье реализован и протестирован метод решения более специализированной подзадачи, заключающейся в поиске и подсчете наиболее частых шаблонов инструкций, которые в дальнейшем могут быть заменены на одну новую инструкцию для оптимизации времени выполнения и/или размера байт-кода и быть проанализированы программистом для получения информации о специфике исходных данных. Данный алгоритм может быть использован как инструмент проектирования managed ISA.

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.