Idempotent Slices with Applications to Code-Size Reduction

Este artigo formaliza o conceito de fatias idempotentes e apresenta um algoritmo eficiente em GSA para extraí-las, permitindo uma otimização de redução de tamanho de código que funde instruções não contíguas, alcançando reduções de até 7,24% em benchmarks específicos do LLVM.

O essencial

Imagine que você está organizando uma cozinha gigante e muito bagunçada, onde vários chefs (o programa de computador) estão preparando pratos complexos. O objetivo deste artigo é encontrar uma maneira inteligente de economizar espaço nessa cozinha sem estragar a comida.

Aqui está a explicação do trabalho, traduzida para uma linguagem simples e cheia de analogias:

1. O Problema: A Cozinha Cheia de Repetições

Muitos programas de computador têm "receitas" repetidas. Às vezes, o mesmo pedaço de código (uma sequência de instruções) aparece em vários lugares diferentes, ou até mesmo dentro da mesma função, mas de forma desorganizada.

• O que os outros faziam: Técnicas anteriores tentavam encontrar repetições apenas olhando para sequências de instruções que estavam juntas (como pegar dois ingredientes que estão lado a lado na bancada). Se a receita fosse "cortada" por uma decisão (como "se o cliente quiser pimenta, adicione pimenta"), essas técnicas perdiam o fio da meada e não conseguiam juntar as partes.

2. A Solução: O "Fatia Mágica" (Idempotent Slices)

Os autores propõem uma nova ideia chamada Fatia Idempotente.

• A Analogia da Fatia: Imagine que você quer fazer um suco de laranja. Você pega a laranja, espreme, coa e serve. Se você fizer esse processo 10 vezes com a mesma laranja, o resultado é sempre o mesmo suco. Isso é "idempotente": o resultado não muda, não importa quantas vezes você repita o processo (desde que os ingredientes de entrada sejam os mesmos).
• A "Fatia": O algoritmo do artigo olha para o programa e diz: "Ei, essa parte aqui da receita (o suco) depende apenas dessas 3 laranjas e não mexe em nada fora dela. Posso cortar essa parte inteira, mesmo que ela esteja espalhada pela cozinha, e transformá-la em uma máquina de suco automática".

3. O Desafio Técnico: O Mapa da Cozinha (GSA)

Para fazer isso com segurança, eles precisavam de um mapa melhor.

• O Problema do Mapa Antigo: Os mapas antigos (chamados de SSA) eram bons, mas às vezes confundiam onde as decisões (como "se chover, pegue guarda-chuva") afetavam as ações. Isso fazia com que o algoritmo antigo cortasse a receita no lugar errado, estragando o prato.
• O Novo Mapa (GSA): Eles usaram uma versão aprimorada do mapa chamada GSA (Static Single Assignment com Portões). Pense no GSA como um mapa que não só mostra os ingredientes, mas também coloca portões e guardiões em cada decisão. Ele sabe exatamente qual caminho o ingrediente percorreu.
• A Vantagem: Com esse mapa detalhado, o algoritmo consegue encontrar "fatias" de código que estão espalhadas, misturadas com loops e decisões, e ainda garante que, se você extrair essa fatia, ela funcionará perfeitamente como uma função independente.

4. A Aplicação: Reduzindo o Tamanho do Código

O objetivo final é diminuir o tamanho do programa (o código).

1. Identificar: O algoritmo encontra todas as "fatias" repetidas (como a máquina de suco que aparece em 10 lugares diferentes).
2. Recortar (Outlining): Ele corta essas fatias do código principal e as coloca em uma função separada (uma "biblioteca de receitas").
3. Fundir (Merging): Se duas fatias são idênticas, ele as funde em uma só.
4. Substituir: No código original, onde antes havia 50 linhas de receita repetida, agora só existe uma linha: "Chame a máquina de suco".

5. Os Resultados: O Que Eles Descobriram?

Eles testaram isso em mais de 2.000 programas reais (o "LLVM Test Suite").

• Economia Real: Em alguns programas, eles conseguiram reduzir o tamanho do código em até 12,5%. Isso é muito espaço economizado!
• Não é Mágica (Tudo tem um preço):
  • Tempo de Compilação: O processo de encontrar essas fatias demora um pouco mais (cerca de 4% a mais de tempo para compilar), mas é aceitável.
  • Velocidade: O programa final roda quase na mesma velocidade. Às vezes fica até mais rápido porque o computador precisa carregar menos código na memória (como ter uma cozinha menor e mais organizada).
  • O "Efeito Colateral": Em alguns casos raros, se a "fatia" for muito pequena e complexa, criar a função separada pode até aumentar um pouquinho o tamanho. Por isso, eles criaram um "filtro de custo" para só fazer a troca se valer a pena.

6. Conclusão: Por que isso é importante?

Este trabalho é como descobrir que você não precisa ter 10 facas iguais na gaveta. Você pode ter uma única faca de alta qualidade e usar sempre que precisar.

• Eles mostraram que é possível encontrar repetições de código que estavam "escondidas" dentro de loops e decisões complexas, algo que as técnicas antigas não conseguiam ver.
• Eles provaram que essa técnica é segura (não quebra o programa) e eficiente.
• E o melhor: essa técnica funciona bem junto com outras técnicas de otimização. É como se você pudesse usar a "máquina de suco" junto com um "moedor de carne" e um "liquidificador" para deixar a cozinha ainda mais eficiente.

Em resumo: O artigo ensina como usar um mapa super detalhado para encontrar pedaços de código repetidos e espalhados, transformá-los em funções únicas e economizar espaço no computador, tudo isso garantindo que o programa continue funcionando perfeitamente.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Idempotent Slices with Applications to Code-Size Reduction", apresentado em português:

Título: Fatias Idempotentes com Aplicações à Redução de Tamanho de Código

Autores: Rafael Alvarenga de Azevedo, Daniel Augusto Costa de Sa, Rodrigo Caetano Rocha e Fernando Magno Quintão Pereira.
Instituição: UFMG (Brasil) e Huawei (Reino Unido).

---

1. O Problema

O artigo aborda a necessidade de reduzir o tamanho do código binário (especificamente a seção .text) em compiladores modernos, uma métrica crucial para dispositivos com memória limitada e para melhorar a localidade do cache de instruções.

O problema central identificado é a insuficiência das técnicas existentes de "fatias" (slices) de código para otimização de tamanho. Especificamente:

• Limitações de Algoritmos Anteriores: Um algoritmo proposto anteriormente por Guimarães et al. (2023) para transformar avaliação ansiosa em preguiçosa (lazy evaluation) falha em cenários comuns de grafos de fluxo de controle (CFG). Ele não lida corretamente com programas que não satisfazem a propriedade "Conventional SSA" (CSSA) e falha em estruturas de controle que não possuem a forma de "hammock" (regiões de entrada única e saída única).
• Ineficiência na Identificação de Redundâncias: Técnicas atuais de fusão de funções (como IROutliner do LLVM ou FMSA) geralmente focam em sequências contíguas de instruções ou não conseguem fundir código redundante não contíguo dentro da mesma função.

2. Metodologia

Os autores propõem uma nova abordagem baseada em Fatias Traseiras Idempotentes (Idempotent Backward Slices) extraídas a partir da forma Gated Static Single Assignment (GSA).

Conceitos Fundamentais:

• Execução Idempotente: Uma sequência de instruções é idempotente se, para as mesmas entradas, executá-la múltiplas vezes produz o mesmo resultado e não altera o estado observável do programa (sem efeitos colaterais, exceções ou escritas em memória mutável).
• Fatia Traseira Idempotente: É um subprograma máximo que computa um valor específico (critério da fatia), garantindo que seja uma função referencialmente transparente. Diferente de fatias densas clássicas, esta fatia é restrita ao loop onde o critério é definido para evitar computar múltiplos valores.

Algoritmo Proposto:

1. Conversão para GSA: O programa é convertido da forma SSA (Static Single Assignment) para GSA (Gated SSA). A forma GSA utiliza instruções de "portão" ($\gamma$, $\mu$, $\eta$) para explicitar as dependências de controle e dados, substituindo as funções $\phi$ tradicionais. Isso resolve as ambiguidades de dependência que falhavam nos algoritmos anteriores.
2. Identificação de Fatias: Um algoritmo de travessia traseira (backward traversal) no grafo de dependências explícito da GSA identifica as instruções que compõem a fatia idempotente. O algoritmo para a travessia ao encontrar:
   • Parâmetros de função (limites intra-procedurais).
   • Instruções $\mu$ (cabeças de loop) que definem variáveis no mesmo nível de aninhamento do critério (garantindo que a fatia não "escapa" do loop).
3. Outlining (Extração de Função): As fatias identificadas são extraídas para funções separadas. O algoritmo reconstrói o fluxo de controle da fatia usando regras de "Transposição" e "Atração" (baseadas no conceito de First Dominator) para garantir que a nova função tenha uma única entrada e preserve a semântica original.
4. Fusão e Redução de Código (SBCR):
   • O sistema identifica fatias isomórficas (que computam o mesmo valor com a mesma lógica).
   • Um modelo de custo (baseado no número de instruções, parâmetros e ocorrências) decide se vale a pena substituir as fatias originais por chamadas a uma única função fundida.
   • Funções duplicadas são fundidas, reduzindo a replicação de código.

3. Principais Contribuições

• Formalização Rigorosa: Definição formal de fatias traseiras idempotentes e um algoritmo correto e eficiente para sua extração em GSA, superando as limitações de algoritmos baseados em CSSA.
• Algoritmo de Extração Linear: A identificação de uma única fatia ocorre em tempo linear em relação às arestas do CFG, não exigindo estruturas de "hammock".
• Otimização SBCR (Slice-Based Code-Size Reduction): Uma nova técnica de otimização que pode fundir instruções não contíguas e não ordenadas dentro da mesma função ou entre funções, algo que técnicas anteriores não conseguiam fazer de forma segura e expressiva.
• Implementação no LLVM: O algoritmo foi implementado como um pass no compilador LLVM (versão 17.0.6) e testado em toda a suíte de testes do LLVM (2.007 programas).

4. Resultados Experimentais

Os experimentos foram realizados na suíte de testes do LLVM (2.007 programas) usando o compilador Clang 17 com otimizações -Os.

• Redução de Tamanho de Código:
  • Em benchmarks altamente otimizados onde a técnica é benéfica, o SBCR alcançou reduções de até -12,49% (ex: benchmark AMGmk) e uma média geométrica de -7,24% em um subconjunto de 29 programas.
  • O SBCR complementa outras técnicas: ele encontra redundâncias que o IROutliner e a fusão por alinhamento de sequência (FMSA) não detectam, e vice-versa.
• Composição de Técnicas: A combinação de IROutliner + SBCR + FMSA resultou em reduções ainda maiores (média de -14,43% no número de instruções em casos específicos), demonstrando que as técnicas são ortogonais.
• Desempenho de Execução: Não houve impacto estatisticamente significativo no tempo de execução na maioria dos casos. Em alguns benchmarks, houve melhoria devido à melhor localidade do cache de instruções (redução de misses no L1).
• Overhead de Compilação: O tempo de compilação aumentou em média 4,22%. O componente mais custoso foi a fase de identificação de fatias e construção da GSA.
• Escalabilidade: Embora a complexidade teórica seja $O(N^2)$, na prática o comportamento é quase linear devido ao pequeno tamanho das fatias identificadas e ao baixo número de fatias que atendem ao modelo de custo.

5. Significado e Conclusão

Este trabalho estabelece as fatias idempotentes como uma nova unidade fundamental para eliminação de redundância em compiladores. Ao utilizar a forma GSA, os autores conseguem lidar com estruturas de controle complexas que frustravam abordagens anteriores.

A técnica SBCR é significativa porque:

1. Oferece uma redução de código competitiva e complementar às melhores técnicas existentes.
2. Permite a extração de padrões de redundância semântica que não são apenas sequências de bytes, mas blocos de lógica computacional coerentes, mesmo que dispersos no fluxo de controle.
3. Demonstra que é possível realizar otimizações agressivas de tamanho de código sem sacrificar a correção semântica ou o desempenho de execução, desde que um modelo de custo adequado seja aplicado.

O código-fonte da implementação e os dados experimentais foram disponibilizados publicamente, permitindo a reprodução e extensão do trabalho.