Quando o compilador surpreende você

 (xania.org)
1 pontos por GN⁺ 2025-12-26 | 1 comentários | Compartilhar no WhatsApp
  • Um caso em que foram observadas as diferenças de otimização entre GCC e Clang ao compilar uma função simples de soma de inteiros
  • O GCC faz uma otimização de loop no formato x*2 + 1, somando dois números de uma vez dentro do loop
  • O Clang remove completamente o loop e substitui o cálculo por uma fórmula fechada v(v - 1)/2
  • Com essa transformação, o código passa de O(n) para O(1), com simplificação matemática feita automaticamente
  • Um exemplo que mostra o nível de otimização inteligente dos compiladores, a ponto de surpreender até um autor com mais de 20 anos de experiência com compiladores

Otimização de loop no GCC

  • Ao escrever uma função simples de soma de inteiros, o GCC gera um código de soma eficiente baseado em loop
    • Dentro do loop, ele usa a instrução lea edx, [rdx+1+rax*2] para somar dois números ao mesmo tempo
    • Isso corresponde a transformar a operação de somar x e x+1 em x*2 + 1
  • Ao elevar o nível de otimização para -O3, ele processa o loop mais rapidamente por meio de soma paralela (vectorization)
  • Essa abordagem é uma forma tradicional de otimização que mantém o loop enquanto maximiza a eficiência das operações

Otimização matemática no Clang

  • Ao compilar o mesmo código com Clang, o loop desaparece completamente
    • O Clang verifica se o valor de entrada é positivo e então realiza o cálculo com uma sequência de instruções lea, imul e shr
    • Como resultado, ele converte o cálculo em (v² - v)/2, isto é, uma fórmula fechada para a soma de inteiros
  • Essa transformação elimina o loop e o substitui por um cálculo em tempo constante (O(1))
  • O autor descreve esse resultado como “ter encontrado por conta própria a solução matemática para a soma de inteiros”

Processo de desenvolvimento da fórmula

  • Ao rastrear matematicamente, em sentido inverso, o código assembly gerado pelo Clang, obtém-se a seguinte transformação
    • v + ((v - 1)(v - 2) / 2) - 1
    • Ao expandir e simplificar, isso se reduz a (v² - v)/2
  • No fim, chega-se à forma v(v - 1)/2, que coincide com a fórmula da soma de 1 até v
  • Esse processo é apresentado como um caso em que o compilador reconheceu um padrão matemático e o otimizou

O comportamento inteligente do compilador

  • Explica-se que o motivo de o Clang usar essa sequência específica de instruções está ligado à prevenção de overflow e à forma de rastrear variáveis de indução
  • Embora a causa exata do funcionamento interno não esteja totalmente clara, o texto menciona que isso é resultado da ação combinada da lógica interna de otimização do Clang
  • O autor descreve esse resultado como “uma experiência humilde e inspiradora”

Encerramento e contexto da série

  • Este texto é o 24º artigo da série ‘Advent of Compiler Optimisations 2025’
  • Ele explora como os compiladores alcançam simplificação matemática e ganho de desempenho por meio de transformações de código
  • O autor enfatiza que, “os compiladores ainda me surpreendem”, destacando o encantamento técnico contínuo mesmo após muitos anos de experiência

Leituras relacionadas

1 comentários

 
GN⁺ 2025-12-26
Comentários no Hacker News

  • O código que implementa esse recurso está em ScalarEvolution.cpp e IndVarSimplify.cpp

    • É impressionante e ao mesmo tempo um pouco inquietante que um único arquivo tenha quase 16.000 linhas de código

  • Esse tipo de otimização é realmente interessante
    As otimizações de compilador se dividem em duas grandes categorias — análise de fluxo de dados e reconhecimento e substituição de padrões
    A primeira funciona bem para a maioria dos programas, e a segunda é um trabalho de acumular padrões com retorno cada vez menor
    O exemplo do link é inteligente e divertido, mas na prática não tem muito valor. Em 45 anos eu nunca escrevi um loop desses
    Claro, esse tipo de substituição de padrão ainda importa porque é gerado automaticamente a partir de código de alto nível
    Para ser sincero, pode ser só eu resmungando porque meu optimizer não consegue fazer esse tipo de otimização

    • Na prática, isso pode ser mais valioso do que parece. O SCEV (Scalar Evolution) do LLVM é usado principalmente para análise e também viabiliza outras otimizações além de loops matemáticos
    • Não está claro que otimização foi feita. Quando eu fazia compiladores de nicho no passado, lembro de me surpreender ao ver o compilador lidar com isso melhor do que as otimizações que eu mesmo escrevi

  • Isso é um recurso chamado Scalar Evolution (SCEV), e no LLVM ele é implementado de forma bem complexa

  • Há um caso de otimização parecido no artigo “Do not optimize away”

    • A explicação no começo do texto está um pouco errada. O código soma de 0 até N, mas exclui N, então o correto é N(N-1)/2. Matematicamente, a soma de 1 até N é N(N+1)/2, então, para excluir o limite superior, é preciso trocar N por (N-1)
    • Acho que o compilador ainda poderia otimizar isso. Talvez desse para criar separadamente uma versão com constant folding e outra sem, e então desviar em runtime

  • O realmente incrível dessa otimização é que ela é genérica (generic)
    Não é apenas um reconhecimento do padrão “soma de sequência finita de inteiros”; é impressionante que isso seja aplicado de forma geral

  • Parece que o compilador poderia adicionar mais closed forms. Fico curioso se isso valeria a pena
    Um conceito relacionado é o Wilf–Zeilberger pair

  • Mais uma vez me surpreendi com o resultado de que o GCC é mais lento que o Clang
    Mesmo com o GCC tendo 20 anos de vantagem, ainda há casos em que o Clang gera código mais rápido
    No passado, ao fazer extração de bits, o Clang resolveu com dois shifts, enquanto o GCC fez três

    • Existe uma grande diferença geracional em tecnologia de compiladores entre GCC e LLVM/Clang. O GCC continua sendo um projeto impressionante, mas ouvi dizer que, estruturalmente, é difícil aplicar nele técnicas modernas de otimização
    • O desempenho real dos dois compiladores é parecido. Eles têm passes de otimização diferentes, então o resultado varia conforme a situação
    • No começo, o GCC tinha uma arquitetura idealista centrada em licenças, o que reduzia sua extensibilidade. Isso foi bastante amenizado hoje, mas o gerador de código ainda é complexo. Já o Clang tem uma estrutura mais simples, o que facilita implementar otimizações. Pessoalmente, acho a saída do MSVC e do ICC bem boa também
    • Será que era código relacionado a bitfield? O GCC é especialmente fraco nessa parte

  • Fico curioso se alguém já tentou uma otimização que substitui o problema de coloração de grafos (graph coloring) por uma constante

    • Coloração de grafos é um problema NP-hard, então é difícil transformar isso em O(1). Se o grafo for planar, o teorema das quatro cores se aplica, mas isso não produz sempre a mesma resposta. Eu só queria falar de teoria dos grafos

  • Este é um exemplo que embaralha a fronteira entre implementação e especificação
    Achamos que estamos escrevendo uma implementação, mas na prática estamos escrevendo um proxy da especificação
    Em outras palavras, o compilador está criando a ilusão de uma máquina imperativa

  • No começo, achei surpreendente que o Matt não soubesse desse comportamento
    Eu também fiquei chocado quando, na época da faculdade, brinquei com LLVM IR e vi recursão ser simplificada em multiplicação
    O fato de o Matt não saber pode significar que essa otimização só se aplica a casos simples com os quais ele não lida