Resumo Técnico: Algoritmos Eficientes para Problemas de Satisfação de Restrições Parciais sobre Grafos de Fluxo de Controle

Definição do Problema

Este trabalho aborda o Problema de Satisfação de Restrições Parciais (PCSP) sobre os Grafos de Fluxo de Controle (CFGs) de programas estruturados e sem goto. Enquanto o Problema de Satisfação de Restrições (CSP) padrão exige encontrar uma atribuição de valores a variáveis que satisfaça todas as restrições, os PCSPs permitem a violação de certas restrições a um custo especificado. O objetivo é encontrar uma atribuição que minimize o custo total das restrições violadas.

No contexto de otimização de compiladores, muitas tarefas podem ser modeladas como PCSPs onde:

• Variáveis correspondem a vértices (instruções ou blocos básicos) no CFG.
• Restrições correspondem a arestas entre vértices.
• Custos estão associados a violações de arestas (ex: spills de registradores, computações redundantes ou instruções de seleção de banco).

O artigo observa que os PCSPs são geralmente NP-difíceis, mesmo com tamanhos de domínio pequenos (ex: tamanho 3 ou até tamanho 2 sob reduções específicas). No entanto, os CFGs de programas estruturados possuem propriedades estruturais específicas — especificamente, eles são esparsos e decomponíveis — que podem ser exploradas para projetar algoritmos eficientes.

Metodologia

Os autores propõem um algoritmo geral que utiliza a decomposição Série-Paralelo-Loop (SPL) de CFGs, um conceito introduzido por Cai e Goharshady [7]. Diferente de abordagens anteriores que dependem de decomposições de árvore e parâmetros de treewidth, este método utiliza a gramática específica de programas estruturados para decompor o grafo em componentes atômicos e operações.

Decomposição SPL

O algoritmo opera em um grafo SPL $G = (V, E, S, T, B, C)$, que inclui quatro nós especiais: Início ($S$), Terminação ($T$), Break ($B$) e Continue ($C$). A decomposição é definida recursivamente via três operações:

1. Série ($G_1 \otimes G_2$): Representa execução sequencial ($P_1; P_2$). Os vértices $T_1$ e $S_2$ são fundidos, assim como os nós $B$ e $C$.
2. Paralelo ($G_1 \oplus G_2$): Representa ramificação condicional ($if \dots then \dots else \dots$). Os nós de Início, Terminação, Break e Continue são fundidos entre os dois subgrafos.
3. Loop ($G_1^\circledast$): Representa um laço ($while \dots do \dots$). Novos nós $S, T, B, C$ são adicionados, conectando-se aos nós internos do subgrafo para modelar caminhos de entrada, saída, break e continue do loop.

Algoritmo de Programação Dinâmica

A contribuição central é um algoritmo de programação dinâmica (DP) bottom-up que calcula o custo mínimo para uma decomposição SPL.

• Definição de Estado: Para cada nó $u$ na árvore de decomposição SPL, representando um subgrafo $G_u$, o algoritmo calcula uma tabela de DP $dp[u, X]$. Aqui, $X$ é uma atribuição de valores do domínio $D$ aos quatro vértices especiais de $G_u$ ($S_u, T_u, B_u, C_u$).
• Lógica de Transição:
  • Nós Atômicos: O custo é calculado diretamente com base na aresta única e nos valores atribuídos.
  • Nós de Série: O algoritmo minimiza a soma dos custos dos subgrafos filhos ($v$ e $w$) sujeito a restrições de compatibilidade (ex: $X_v(T_v) = X_w(S_w)$).
  • Nós de Paralelo: Semelhante aos nós de série, mas com restrições de igualdade mais estritas nos vértices fundidos. O algoritmo leva em conta potenciais arestas duplicadas introduzidas pela fusão.
  • Nós de Loop: O algoritmo calcula o custo das novas arestas introduzidas pela operação de loop e o adiciona ao custo do corpo do subgrafo.
• Complexidade: A complexidade de tempo para processar cada nó na decomposição é $O(|D|^6)$, onde $|D|$ é o tamanho do domínio. Como o tamanho da decomposição SPL é linear no tamanho do CFG ($|G|$), o tempo de execução total é $O(|G| \cdot |D|^6)$. Para qualquer tamanho de domínio fixo, isso resulta em uma solução de tempo linear.

Principais Contribuições

1. Generalização de PCSP: O artigo apresenta um framework unificado para resolver PCSPs sobre CFGs, generalizando algoritmos especializados anteriores para Alocação de Registradores [7] e Eliminação de Redundância Parcial Especulativa de Tempo de Vida Ótimo (LOSPRE) [6].
2. Eficiência Baseada em SPL: Ao utilizar decomposições SPL em vez de decomposições de árvore, os autores evitam a dependência de parâmetros de treewidth. Isso resulta em um algoritmo mais simples que explora diretamente a estrutura de programas estruturados.
3. Seleção de Banco Ótima: Os autores aplicam este framework geral à Colocação Ótima de Instruções de Seleção de Banco, um problema anteriormente resolvido usando métodos baseados em treewidth [32].
4. Validação Experimental: A implementação demonstra que a abordagem baseada em SPL supera significativamente a abordagem de estado da arte baseada em treewidth para seleção de banco, alcançando tempos de execução aproximadamente quatro vezes mais rápidos.

Resultados Experimentais

Os autores implementaram o algoritmo em C++ e o integraram ao Small Device C Compiler (SDCC). Experimentos foram conduzidos no conjunto de testes de regressão do SDCC cobrindo três arquiteturas: HC08, Z80 e MCS51.

• Desempenho vs. Estado da Arte: Comparado à abordagem baseada em treewidth de [32] (que possui um tempo de execução de $O(|G| \cdot tw(G) \cdot |D|^{tw(G)+1})$), o algoritmo proposto alcançou tempos de execução médios aproximadamente 4 vezes mais rápidos em todas as arquiteturas testadas.
  • Exemplo (HC08): 1.998,3 ns (proposto) vs. 8.558,8 ns (base).
• Comparação com SAT/ILP: O método também foi comparado com solvers SAT (Kissat) e Programação Linear Inteira (Gurobi). O algoritmo proposto mostrou-se quase 10 vezes mais rápido que a abordagem ILP e aproximadamente 1.000 vezes mais rápido que o solver SAT.
• Otimalidade: Tanto o método proposto quanto o método base [32] produzem soluções ótimas idênticas para seleção de banco; a melhoria é estritamente em eficiência computacional.

Significância e Alegações

O artigo alega que o algoritmo proposto fornece uma solução de tempo linear para uma ampla classe de problemas de otimização de compiladores modelados como PCSPs sobre CFGs de programas estruturados, desde que o tamanho do domínio seja fixo.

A significância reside em:

• Unificação: Consolida tarefas de otimização distintas (Alocação de Registradores, LOSPRE, Seleção de Banco) sob um único framework algorítmico geral.
• Aceleração Prática: A remoção da dependência do parâmetro de treewidth e o uso de decomposições SPL resultam em um fator constante significativamente menor na prática, levando a acelerações substanciais em cenários reais de compiladores.
• Escalabilidade: A dependência linear do tamanho do grafo ($|G|$) torna a abordagem altamente escalável para grandes bases de código, superando tanto métodos parametrizados de decomposição de árvore quanto solvers gerais de problemas NP-difíceis (SAT/ILP).

Os autores enfatizam que, embora a complexidade teórica dependa de $|D|^6$, em aplicações práticas de compiladores (como seleção de banco, onde $|D|$ é pequeno e constante), o algoritmo se comporta como um solver de tempo linear real, oferecendo uma alternativa superior a heurísticas existentes e algoritmos parametrizados.