Planejei escrever um artigo sobre como o LLVM otimiza uma função, mas primeiro você precisa escrever como o Clang converte C ou C ++ em LLVM.
Considere os aspectos de alto nível sem mergulhar nas profundezas de Clang. Quero prestar atenção em como a saída do Clang está relacionada à entrada, enquanto não consideraremos os recursos não triviais do C ++. Usamos essa pequena função, que emprestei de excelentes
palestras sobre otimizações cíclicas :
bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; }
Como o Clang não faz nenhuma otimização e como o LLVM IR foi originalmente projetado para funcionar com C e C ++, a conversão é relativamente fácil. Usarei o Clang 6.0.1 (ou uma versão mais próxima, pois essa ainda não foi lançada) no x86-64.
A linha de comando é a seguinte:
clang++ is_sorted.cpp -O0 -S -emit-llvm
Em outras palavras: compilamos o arquivo is_sorted.cpp como C ++ e, em seguida, informamos ao conjunto de ferramentas do LLVM o seguinte: não otimize, produza o assembler como uma representação textual do LLVM IR. O LLVM IR é volumoso e não pode ser exibido ou analisado rapidamente; um formato de código de bit binário é sempre preferível se uma pessoa não precisar examinar esse código.
Aqui está o IR completo da LLVM, que será analisado em partes.
Vamos começar no topo do arquivo:
; ModuleID = 'is_sorted.cpp' source_filename = "is_sorted.cpp" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"
O texto inteiro entre o ponto e vírgula e o final da linha é um comentário, o que significa que a primeira linha não faz nada, mas, se você estiver interessado, no LLVM um "módulo" é uma unidade de compilação, um contêiner para código e dados. A segunda linha também não deve nos incomodar. A terceira linha descreve algumas suposições feitas pelo compilador, elas não desempenham um papel neste artigo, mas você pode ler mais
aqui .
O alvo três é o legado do gcc e não precisa mais de nós.
A função LLVM possui atributos opcionais:
; Function Attrs: noinline nounwind optnone uwtable
Alguns deles (como esses) são suportados pelo front-end, outros são adicionados posteriormente por passes de otimização. Esses atributos não têm nada a ver com o significado do código, não os discutirei aqui, mas você pode ler sobre eles
aqui se estiver interessado.
E, finalmente, nossa função:
define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n)
“Zeroext” significa que o valor de retorno da função (i1, um número inteiro de um bit) deve ser expandido com zeros no backend na largura que a ABI exige. Depois vem o nome da função "desconfigurada" e a lista de parâmetros, basicamente os mesmos do código C ++, exceto que o i32 define uma variável de 32 bits. # 0 conecta a função ao
grupo de atributos no final do arquivo.
Aqui está a primeira unidade base:
entry: %retval = alloca i1, align 1 %a.addr = alloca i32*, align 8 %n.addr = alloca i32, align 4 %i = alloca i32, align 4 store i32* %a, i32** %a.addr, align 8 store i32 %n, i32* %n.addr, align 4 store i32 0, i32* %i, align 4 br label %for.cond
Cada instrução LLVM deve estar localizada dentro da unidade base: um conjunto de instruções que possui uma entrada no início e uma saída no final. A última instrução da unidade base deve ser uma
instrução de término : "falha" na próxima unidade base é inaceitável. Cada função deve ter um bloco de entrada que não possui predecessores que executam a transição para esse bloco. Esta e
outras propriedades são verificadas ao analisar o IR; essas verificações também podem ser chamadas várias vezes durante o processo de compilação pelo "verificador de módulo". O verificador é útil para depuração quando um passe gera um IR inválido.
As quatro primeiras instruções neste bloco base são "alloca": alocação de memória da pilha. Os três primeiros criam variáveis criadas implicitamente durante a compilação, o quarto - uma variável de loop. As variáveis alocadas dessa maneira só podem ser acessadas através de instruções de carregamento e armazenamento. As três instruções a seguir inicializam os três slots de pilha, a.addr e n.addr são inicializados usando os valores passados para a função como parâmetros e i é inicializado com zero. O valor de retorno não precisa ser inicializado, qualquer código que não esteja indefinido em C e C ++ terá que cuidar disso. A última instrução é uma transição incondicional para a próxima unidade base (ainda não estamos preocupados com isso, a maioria das transições desnecessárias será excluída pelo back-end do LLVM).
Você pode perguntar: por que Clang aloca slots de pilha para a e n? Por que ele não usa esses valores diretamente? Nesta função, como a e n não mudam, essa estratégia funcionará, mas esse caso será levado em consideração pelo otimizador e está fora da competência de Calng. Se a e n puderem ser modificados, eles devem estar na memória e não devem ter valores SSA, que, por definição, só podem receber valor em um ponto do programa. As células de memória estão fora do mundo da SSA e podem ser modificadas a qualquer momento. Isso pode parecer estranho, mas essa solução permite organizar o trabalho de todas as partes do compilador de uma maneira natural e eficiente.
Penso em Clang como um gerador de código SSA degenerado que satisfaz todos os requisitos do SSA, mas apenas porque a troca de informações entre as unidades base ocorre através da memória. A geração de código não degenerado requer alguma atenção e algumas análises, e os desenvolvedores do Clang se recusaram a fazer isso para separar as responsabilidades de gerar e otimizar o código. Não vi os resultados da medição, mas, no meu entendimento, muitas operações de memória são geradas e, quase imediatamente, a maioria delas é excluída pelo otimizador, sem levar a grandes despesas gerais do tempo de compilação,
Considere como o loop for se traduz. Em termos gerais, fica assim:
for (initializer; condition; modifier) { body }
Isso se traduz em algo assim:
initializer goto COND COND: if (condition) goto BODY else goto EXIT BODY: body modifier goto COND EXIT:
Obviamente, essa tradução não é específica para Clang, qualquer compilador C e C ++ faz o mesmo.
No nosso exemplo, o inicializador de loop é recolhido no bloco base de entrada. A seguinte unidade base é uma verificação da condição do loop:
for.cond: ; preds = %for.inc, %entry %0 = load i32, i32* %i, align 4 %1 = load i32, i32* %n.addr, align 4 %sub = sub nsw i32 %1, 1 %cmp = icmp slt i32 %0, %sub br i1 %cmp, label %for.body, label %for.end
Clang também faz um comentário útil de que este bloco base pode ser alcançado a partir de for.inc ou do bloco base de entrada. Esse bloco carrega i e n da memória, reduz n (o sinalizador nsw reflete a propriedade da linguagem C que o excesso de sinal não está definido; sem esse sinalizador, o LLVM usa a semântica do código adicional), compara o valor reduzido com i usando o slt (assinado menos que, assine menos que) e, finalmente, ramifique na base para o bloco for.body ou for.end.
A entrada no corpo do loop é possível apenas no bloco for.cond:
for.body: %2 = load i32*, i32** %a.addr, align 8 %3 = load i32, i32* %i, align 4 %idxprom = sext i32 %3 to i64 %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom %4 = load i32, i32* %arrayidx, align 4 %5 = load i32*, i32** %a.addr, align 8 %6 = load i32, i32* %i, align 4 %add = add nsw i32 %6, 1 %idxprom1 = sext i32 %add to i64 %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1 %7 = load i32, i32* %arrayidx2, align 4 %cmp3 = icmp sgt i32 %4, %7 br i1 %cmp3, label %if.then, label %if.end
As duas primeiras linhas carregam a e i nos registros SSA; Em seguida, expanda para 64 bits e posso participar do cálculo do endereço. O comando
getelementptr (ou gep para abreviar) é o comando LLVM conhecido por sua pretensão, e até possui sua própria
seção de ajuda . Diferentemente da linguagem de máquina, o LLVM não trata os ponteiros como números inteiros. Isso facilita a análise de alias e outras otimizações de memória. Este código carrega um [i] e um [i + 1], compara-os e executa ramificações, dependendo do resultado.
O bloco if.then salva 0 no slot da pilha para o valor de retorno da função e pula incondicionalmente para o bloco de saída da função:
if.then: store i1 false, i1* %retval, align 1 br label %return
O bloco else é trivial:
if.end: br label %for.inc
E o bloco para adicionar um à variável de loop também é muito simples:
for.inc: %8 = load i32, i32* %i, align 4 %inc = add nsw i32 %8, 1 store i32 %inc, i32* %i, align 4 br label %for.cond
Esse código retorna para verificar as condições do loop.
Se o loop for concluído normalmente, retornamos true:
for.end: store i1 true, i1* %retval, align 1 br label %return
E, finalmente, o que carregamos no slot da pilha do valor de retorno é carregado e retornado:
return: %9 = load i1, i1* %retval, align 1 ret i1 %9
Não há nada de especial no final da função. O post acabou sendo mais longo do que eu pensava, no próximo post consideraremos otimizar o nível de IR para esta função.
(Obrigado a Xi Wang e Alex Rosenberg pelas correções enviadas)