Superoptimization of stack-based bytecode

Abstract

Program optimization represents an important discipline within programming languages, particularly in compiler design. These techniques aim to enhance a program's performance and efficiency across various aspects such as the program's execution time, memory utilization or code size. Despite their ability to generate highly efficient code, it is unusual that the produced code is truly optimal.Superoptimization is a compilation technique that addresses these inefficiencies by exploring all sequences that are equivalent to an initial sequence, searching for the one with the minimum cost. This approach enables optimizations that are often impossible to achieve using traditional optimization techniques. Howeves, exploring the entire solution space is extremely costly, making it very hard to adopt in prractice. nevertheless, superoptimization techniques can be used to identify potential inefficiencies in optimizers and develop new optimization techniques. Stack-based languages are ideal for studying these techniques, given their (generally) simple instruction set, and given that an optimal management of the stack is difficult...

Las técnicas de optimización de código constituyen un campo de estudio importante dentro de los lenguajes de programación, particularmente en el desarrollo de compiladores. El objetivo de estas técnicas es mejorar el rendimiento y la eficiencia de programas en función de distintos aspectos (tiempo de ejecución, memoria, tamaño del código...). A pesar de que estas técnicas producen código muy eficiente, rara vez este código es totalmente óptimo.La superoptimización es una técnica de compilación que aborda estas ineficiencias. Esta técnica consiste en explorar todas las secuencias equivalentes a una de partida, buscando aquella que sea de coste mínimo. Esto nos permite obtener optimizaciones que son a menudo imposibles de conseguir aplicando técnicas tradicionales de optimización. Sin embargo, explorar todo el espacio de soluciones es muy costoso y esto hace que generalmente no sea viable aplicarlas en la práctica. Aun así, las técnicas de superoptimización siguen siendo útiles porque permiten identificar posibles ineficiencias en optimizadores y nos permiten desarrollar nuevas técnicas de optimización para mejorarlos. Las máquinas de pilas son un entrono ideal para el estudio de estas técnicas, al tener un repertorio de instrucciones sencillo y, a la vez, ser muy complicado manejar la pila de forma óptima...