Adapting stochastic generation of energy-efficient optimization pipelines for modern LLVM via a pushdown automaton

Abstract

A demanda energética da computação cresce ano após ano, e o compilador, que medeia toda tradução do código-fonte para o executável, é um ponto estratégico único para lidar com isso. Níveis padrão de otimização, como -O3, aplicam uma sequência fixa e predefinida de passagens, mas a ordem em que as passagens são executadas afeta significativamente o programa final, e uma execução mais rápida não significa necessariamente uma execução mais ecológica. A busca por uma melhor ordenação das passagens, o problema da ordenação de fases, é NP-difícil, e as abordagens existentes normalmente exigem conhecimento especializado na área, treinamento dispendioso que não é generalizável ou oferecem pouca interpretabilidade. Uma alternativa leve e interpretável é um método baseado em grafos, que acumula conhecimento sobre transições úteis de passagens em uma Cadeia de Markov e amostra novas sequências por meio de um Passeio Aleatório. No entanto, desde 2021, o LLVM substituiu seu Legacy Pass Manager plano pelo New Pass Manager hierárquico, invalidando este e vários outros trabalhos de ajuste automático que visam versões agora obsoletas, enquanto as distribuições convencionais já fornecem as versões recentes. Este trabalho apresenta o MaCETA (Markov Chain Energy-aware Tool for Auto-tuning), uma adaptação do método baseado em grafos para o LLVM 20.1.8, decompondo a geração do pipeline em uma Cadeia de Markov que amostra passagens e um autômato de empilhamento que impõe a estrutura aninhada do New Pass Manager. Avaliado no PolyBench em comparação com a opção -O3, com a energia medida por meio do Intel RAPL, o MaCETA reduz o consumo de energia do pacote em cerca de 30% em média, superando os 24% relatados pelo método original, ao mesmo tempo em que se mantém simples, interpretável e fácil de adaptar a novas versões do compilador.

The energy demand of computing grows year over year, and the compiler, which mediates every translation from source code to executable, is a uniquely strategic place to address it. Standard optimization levels such as -O3 apply a fixed, predefined sequence of passes, yet the order in which passes run greatly affects the final program, and running faster is not necessarily running greener. Searching for a better pass ordering, the phase-ordering problem, is NP-hard, and existing approaches typically demand domain expertise, costly training that does not generalize, or offer little interpretability. A lightweight and interpretable alternative is a graph-based method, which accumulates knowledge of useful pass transitions in a Markov Chain and samples new sequences by a Random Walk. However, since 2021 LLVM replaced its flat Legacy Pass Manager with the hierarchical New Pass Manager, invalidating this and several other auto-tuning works that target now-obsolete versions, while mainstream distributions already ship recent ones. This work presents MaCETA (Markov Chain Energy-aware Tool for Auto-tuning), an adaptation of the graph-based method to LLVM 20.1.8, decomposing pipeline generation into a Markov Chain that samples passes and a Pushdown Automaton (PDA) that enforces the nested structure of the New Pass Manager. Evaluated on PolyBench against -O3 with energy measured through Intel RAPL, MaCETA reduces package energy by a mean of roughly 30%, exceeding the 24% reported by the original method, while remaining simple, interpretable, and trivial to re-target to new compiler versions.