Hydra: static detection of hottest blocks on control flow graphs
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Hydra: detecção estática de blocos mais frequentes em grafos de fluxo de controle
Primeiro orientador
Membros da banca
Mircea Trofin
Sergey Pupyrev
Sergey Pupyrev
Resumo
Profile-guided optimization (PGO) is a well-established technique for improving program performance, being integrated into major compilers such as GCC, LLVM/Clang, and Microsoft Visual C++. PGO collects information about a program’s execution and uses it to guide optimizations such as inlining, and code layout. However, these very transformations alter the program’s control flow, which may render the collected profiles stale or inaccurate. To deal with this problem, this work investigates how to maintain profile data after optimization without re-executing the program. We study two complementary strategies: prediction, which estimates likely hot code paths in the optimized program without any prior knowledge, and projection, which transfers profile information from the original control-flow graph to its transformed version. We evaluate several techniques for reconstructing profile data, including a large language model (LLM)–based approach using GPT-4o, and a lightweight method that compares opcode histograms of code regions recursively to identify structural similarities. Our results show that the histogram-based method is not only simpler but also consistently more accurate than both the LLM-based approach and prior prediction and projection techniques, including those implemented in LLVM and the BOLT binary optimizer.
Abstract
Profile-guided optimization (PGO) é uma técnica bem estabelecida para melhorar o desempenho dos programas, sendo adotada pelos principais compiladores, como GCC, LLVM/Clang e o Microsoft Visual C++. Nela, dados de execução de um programa (perfil) são coletados para orientar o compilador na tomada de decisões mais eficientes, como inlining de funções crı́ticas e organização de código. A coleta de perfil, no entanto, apresenta desafios: perfis estáticos podem não refletir o comportamento real do programa, enquanto perfis dinâmicos, obtidos por meio de execução instrumentada, têm alto custo computacional. Além disso, qualquer modificação no código-fonte — seja pelo programador ou pelas próprias otimizações do compilador — pode tornar o perfil coletado obsoleto, exigindo uma nova coleta. Para lidar com esse problema, este trabalho investiga a manutenção dos dados de perfil após uma sequência de otimizações, sem a necessidade de reexecutar o programa. Duas estratégias foram estudadas: o uso de perfis estáticos, e a projeção de perfis, que transfere informações de perfil de um programa original para sua versão transformada. Foram avaliadas diversas heurı́sticas para reconstruir os dados de perfil, incluindo uma abordagem baseada em um grande modelo de linguagem (LLM) com o GPT-4o e um método que compara, recursivamente, histogramas de operandos de blocos básicos e regiões de código para identificar similaridades estruturais. Os resultados demonstram que o método baseado em histogramas não só é mais simples, mas também supera em precisão as demais técnicas utilizadas em quase todos os cenários, incluindo as utilizadas pela LLVM e pelo otimizador de binários BOLT.
Assunto
Computação – Teses, Compiladores (Programas de computador) - Teses, Otimização de códigos (compiladores) – Teses, Análise estática – Teses
Palavras-chave
Static analysis, Profile projection