Criação de perfil de código com LLVM

A maldição do não-determinismo

Minha primeira tentativa de escrever uma passagem LLVM - eu amo essas segfolty

Recentemente, deparei com um problema interessante - eu precisava de uma maneira determinística e de plataforma cruzada para determinar o tempo de execução do código C ++. Com a palavra "determinista", quero dizer que o mesmo código será executado pelo mesmo número de unidades de tempo. Por plataforma cruzada, entendo que o mesmo código no Windows e no Ubuntu será executado pelo mesmo número de unidades de tempo.

Naturalmente, medir o tempo na CPU não atende a essas condições. O código da máquina varia de acordo com a arquitetura e o sistema operacional, e o mesmo código levará um tempo diferente para ser executado. Mesmo na mesma máquina, fatores como falhas de cache terão um grande papel - o suficiente para distorcer os resultados da medição do tempo de execução do mesmo código. Eu precisava de algo mais inteligente ...

Motivação

Eu me deparei com esse problema quando estava trabalhando no meu projeto, Code Character. Code Character é uma competição de IA on-line na qual os participantes escrevem bots para controlar um exército em uma estratégia baseada em turnos. Eu queria limitar a quantidade de código que um participante pode executar de uma só vez.

Meu primeiro pensamento foi simplesmente medir o tempo de execução do código, mas, como vemos, essa estratégia não é determinística, e o participante que enviou o mesmo código duas vezes obterá resultados completamente diferentes. De fato, tentamos implementar essa solução, e os resultados mudam tanto que um participante pode ganhar ou perder com o mesmo código. O resultado será completamente aleatório e descartamos a ideia de medir o tempo.

Bytecode do LLVM

Como não podemos medir o tempo, decidimos medir o número de instruções executadas. Portanto, precisamos instrumentar o código do participante. Se você não está familiarizado com este termo, isso inclui alguns códigos no aplicativo, a fim de monitorar alguns parâmetros, por exemplo, uso ou tempo de execução da CPU. Naturalmente, não esperamos que os participantes façam isso eles mesmos, devemos automatizar o processo.

Queríamos evitar custos indiretos para ferramentas de tempo de execução ao trabalhar em nosso servidor e, portanto, algo como uma ferramenta de PIN não é adequado para nossos propósitos. Em vez disso, decidimos instruir diretamente o código dos participantes para contar o número de instruções que seriam executadas. Em vez de instrumentar binários (código de máquina), decidimos usar o Clang para compilar o código e o bytecode do instrumento LLVM.

Se você é novo no LLVM, é uma coleção de tecnologias modulares e reutilizáveis ​​de compilador e cadeia de ferramentas. Um dos principais projetos é o LLVM RI e back-end. Em termos simples, uma Representação Intermediária foi desenvolvida na qual um front-end compilado compila código. Esse código, LLVM IR, é compilado no código da máquina pelo back-end do LLVM. Portanto, se você estiver criando um novo idioma, poderá permitir que o LLVM ofereça suporte à geração e otimização de código de máquina e escreva um front-end para converter seu idioma em LLVM IR.


Clang converte o código C ++ em LLVM IR, que é convertido em código de máquina pelo back-end do LLVM.

Clang é o frontend do LLVM. Como precisamos de um método de plataforma cruzada para medir código, não podemos instrumentar código binário. O LLVM IR, no entanto, é independente da plataforma, pois é apenas uma representação intermediária do código. A instrumentação do código IR com bibliotecas LLVM é uma solução simples de plataforma cruzada.

Solução

Obviamente, uma contagem simples de instruções LLVM IR não é adequada, pois precisamos do número de instruções que realmente serão executadas e não apenas do número de instruções no código. No final, desenvolvemos um algoritmo simples baseado no conceito de blocos básicos de código.

Uma unidade base é um conjunto de instruções em que apenas a primeira instrução pode ser o ponto de entrada e apenas a última instrução pode ser o ponto de saída. ( Qualquer transição dentro do bloco base também é proibida - aprox. Transl. ) Para entender isso, tente dividir o código em partes nas quais as instruções de ramificação (transições, loops e retornos) só podem ser as últimas do conjunto e a entrada para o bloco (primeira instrução em função, loop ou bloco if / else) só é possível na primeira instrução. O resultado é um conjunto de blocos básicos - blocos de código seqüencial que simplesmente são executados sequencialmente, sem decidir qual instrução executar a seguir.

Por que não tentamos agora? Este é um trecho de código fornecido por um contribuidor de Caractere de código:

// Make the soldiers who aren't patrolling attack the enemy for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { auto &soldier = state.soldiers[i]; if (soldier.hp == 0) // If this soldier is dead, skip it continue; for (auto enemy_soldier : state.enemy_soldiers) { if (enemy_soldier.hp != 0) { // Ensure your prospective target has // not already been slain soldier.soldier_target = enemy_soldier.id; break; } } } 

Link do Github: https://gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp

Usando o fato de a unidade base ter apenas um ponto de entrada (a primeira instrução), podemos dividir esse fragmento nas seguintes unidades base:

 //-------------------------------- BB 1 ---------------------------------- for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { //-------------------------------- BB 2 ---------------------------------- auto &soldier = state.soldiers[i]; if (soldier.hp == 0) //-------------------------------- BB 3 ---------------------------------- continue; //-------------------------------- BB 4 ---------------------------------- for (auto enemy_soldier : state.enemy_soldiers) { //-------------------------------- BB 5 ---------------------------------- if (enemy_soldier.hp != 0) { //-------------------------------- BB 6 ---------------------------------- soldier.soldier_target = enemy_soldier.id; break; //-------------------------------- BB 7 ---------------------------------- } } } 

Link do Github
Isso nos ajudou a entender como os blocos básicos funcionam, agora vamos ver esse algoritmo no LLVM IR:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 br label %181 

Link do Github

Se você observar com atenção, notará que o fragmento de código acima é os três primeiros blocos do fragmento de código C ++ compilado no LLVM IR (cada linha é o início do bloco base).

O LLVM possui bibliotecas que nos permitem escrever “passes” - código que pode transformar o LLVM IR. A API do LLVM nos permite ler e analisar com facilidade o LLVM IR, iterando através de módulos, funções e blocos básicos, e modificando o LLVM IR antes de ser compilado no código da máquina.

Agora que temos os blocos básicos e a API LLVM, está se tornando uma questão simples calcular o número de instruções a serem executadas usando um algoritmo tão simples:

1. Escrevemos a função IncrementCount, que pega um número inteiro e incrementa um número inteiro estático com esse valor, cada vez que é chamado. Ele precisa estar vinculado ao código do membro.
2. Fazemos iterações em todos os blocos de base. Para cada unidade base, execute as etapas 3 e 4.
3. Encontramos n - o número de instruções nesta unidade base.
4. Nós inserimos a chamada na função IncrementCount antes da última instrução da unidade base, com o argumento n.
5. O número inteiro estático com o qual IncrementCount trabalha será o contador de instruções após a execução do código. Ele pode ser salvo em algum lugar e depois verificado.

Nosso RI instrumentado funciona assim:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 call void @_Z14IncrementCountm(i32 4) br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 call void @_Z14IncrementCountm(i32 10) br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 call void @_Z14IncrementCountm(i32 1) br label %181 

Link do Github

Como podemos ver, uma chamada IncrementCount é feita no final de cada bloco base, logo antes da última instrução. Usando o int estático com o qual IncrementCount trabalha, podemos obter o número de instruções no final da movimentação de cada participante. Este método é determinístico e multiplataforma, como é garantido que o mesmo código fonte gere o mesmo IR LLVM se usarmos a mesma versão do compilador e os mesmos sinalizadores.

Conclusão

A criação de perfil de código não é uma coisa tão simples como eu pensava. No processo de trabalhar em uma tarefa relativamente simples, eu me familiarizei com o funcionamento do compilador e como escrever passes LLVM. Se você está interessado em gerar código e deseja escrever suas próprias passagens, o LLVM possui um guia para iniciantes . há também um ótimo artigo de blog que costumava escrever minha própria passagem. Como a API do LLVM não é compatível com versões anteriores entre as principais versões, preste atenção na versão do LLVM que você está usando.

Você pode obter o código fonte do passe aqui .