Eu não ligo para o que seu dragão disse, é uma mentira. Os dragões mentem. Você não sabe o que está esperando por você do outro lado.
Michael Swanwick, a filha do dragão de ferro
Este artigo é baseado na postagem no blog de Krister Walfridsson,
"Por que um comportamento indefinido pode chamar uma função nunca chamada?" .
O artigo tira uma conclusão simples: o comportamento indefinido em um compilador pode fazer qualquer coisa, mesmo algo absolutamente inesperado. Neste artigo, examino o mecanismo interno dessa otimização.
Para recapitular brevemente a postagem de Waldfridsson, no código-fonte abaixo, a função EraseAll não deve ser chamada de main, e não é realmente chamada quando compilada com -O0, mas de repente é chamada com a otimização -O1 e superior.
#include <cstdlib> typedef int (*Function)(); static Function Do; static int EraseAll() { return system(“rm -rf /”); } void NeverCalled() { Do = EraseAll; } int main() { return Do(); }
Como um compilador o otimiza? No início, Do, o ponteiro para uma função é nulo, porque, de acordo com o padrão C, todas as variáveis globais têm valores zero quando um programa é iniciado.
O programa tentará desreferenciar o ponteiro Do e chamar a função atribuída. Mas se tentarmos desreferenciar um ponteiro nulo, o padrão diz que é UB, comportamento indefinido. Normalmente, se compilarmos sem otimizações, com a opção -O0, obteremos uma falha de segmentação (no Linux). Mas o Standard diz que, no caso do UB, um programa pode fazer qualquer coisa.
Um compilador usa esse recurso do padrão para remover operações desnecessárias. Se um compilador vê que Do está atribuído em qualquer lugar do programa, ele pode atribuir esse valor no tempo de inicialização e não em tempo de execução. Na realidade, existem duas possibilidades:
1. Se um ponteiro for desreferenciado após ser atribuído, vencemos, porque um compilador pode remover uma atribuição desnecessária.
2. Se um ponteiro é desreferenciado antes de ser atribuído, o padrão diz que ele é UB e o comportamento pode ser qualquer, incluindo a chamada de uma função arbitrária. Ou seja, chamar a função PrintHello () não contradiz o padrão.
Ou seja, em qualquer caso, podemos atribuir algum valor não nulo a um ponteiro não inicializado e obter comportamento, de acordo com o padrão.
Quais são as condições que tornam essa otimização possível? Inicialmente, um programa deve conter um ponteiro global sem nenhum valor inicial ou com valor nulo (que é o mesmo). Em seguida, o programa deve conter uma atribuição de um valor para esse ponteiro, em qualquer lugar, não importa, antes da referência ao ponteiro ou depois dele. No exemplo acima, uma atribuição ainda não ocorreu, mas um compilador vê que a atribuição existe.
Se essas condições forem atendidas, um compilador pode remover a atribuição e alterá-la para o valor inicial do ponteiro.
No código fornecido, a variável Do é um ponteiro para uma função e possui o valor inicial nulo. Quando tentamos chamar uma função no ponteiro nulo, o comportamento do programa é indefinido (comportamento indefinido, UB) e o compilador tem o direito de otimizar o UB conforme desejado. Nesse caso, o compilador executou imediatamente a atribuição Do = EraseAll.
Por que isso acontece? No restante do texto, LLVM e Clang versão 5.0.0 são usados como compilador. Exemplos de código são executáveis para você praticar.
Para começar, vejamos o código IR ao otimizar com -O0 e -O1. Vamos mudar um pouco o código fonte para torná-lo menos dramático:
#include <cstdlib> typedef int (*Function)(); static Function Do; static int PrintHello() { return printf("hello world\n"); } void NeverCalled() { Do = PrintHello; } int main() { return Do(); }
E compilamos o código IR com -O0 (as informações de depuração são omitidas para maior clareza):
; ModuleID = 'test.c' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @Do = internal global i32 (...)* null, align 8 @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() #0 { entry: store i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*), i32 (...)** @Do, align 8 ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %0 = load i32 (...)*, i32 (...)** @Do, align 8 %call = call i32 (...) %0() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) #1 And with -O1: ; ModuleID = 'test.ll' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() local_unnamed_addr #0 { entry: ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() local_unnamed_addr #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %call = call i32 (...) bitcast (i32 ()* @PrintHello to i32 (...)*)() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() unnamed_addr #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) local_unnamed_addr #1
Se você compilar os executáveis, confirmará que, no primeiro caso, ocorre um erro de segmentação e, no segundo caso, “hello world” é exibido. Com outras opções de otimização, o resultado é o mesmo que para -O1.
Agora encontre a parte do código do compilador que executa essa otimização. A arquitetura do LLVM, o front-end, não lida com otimizações em si, ou seja, o cfe (Clang Frontend) sempre gera o código sem otimizações, que vemos na versão para -O0, e todas as otimizações são executadas pelo utilitário opt:
Com -O1, são executados 186 passes de otimização.
Desligando os passes um após o outro, encontramos o que estamos procurando: o passe
globalopt . Podemos deixar apenas esse passo de otimização e garantir que ele e mais ninguém gere o código de que precisamos. A fonte está no arquivo /lib/Transforms/IPO/GlobalOpt.cpp. Você pode ver o código-fonte no repositório LLVM. Por uma questão de brevidade, forneci apenas funções importantes para entender como ele funciona.
Esta imagem representa uma estrutura da representação IR. Um código na representação LLVM IR possui níveis hierárquicos: um módulo representa o nível mais alto de uma hierarquia e inclui todas as funções e objetos globais, como variáveis globais. Uma função é o nível mais importante de representação de RI e a maioria das passagens funciona nesse nível. Um bloco básico é aquele que é o conceito mais importante de uma teoria de compilador. Um bloco básico consiste em instruções, que não podem saltar do meio de um bloco básico ou dentro de um bloco básico. Todas as transições entre blocos básicos são possíveis apenas a partir do final de um bloco básico e do início de um bloco básico, e quaisquer saltos de ou para o meio de um bloco básico nunca são possíveis. Um nível de instrução representa uma instrução de código IR LLVM. Não é uma instrução de processador, é uma instrução de uma máquina virtual muito generalizada com um número infinito de registros.
Esta imagem mostra uma hierarquia de passes do LLVM. Nos passes à esquerda, trabalhando no código IR LLVM, são mostrados os passes à direita, trabalhando com as instruções do alvo.
Inicialmente, implementa o método runOnModule, ou seja, ao trabalhar, ele vê e otimiza todo o módulo (o que, é claro, é razoável nesse caso). A função que executa a otimização é optimizeGlobalsInModule:
static bool optimizeGlobalsInModule( Module &M, const DataLayout &DL, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { SmallSet<const comdat="Comdat" 8="8"> NotDiscardableComdats; bool Changed = false; bool LocalChange = true; while (LocalChange) { LocalChange = false; NotDiscardableComdats.clear(); for (const GlobalVariable &GV : M.globals()) if (const Comdat *C = GV.getComdat()) if (!GV.isDiscardableIfUnused() || !GV.use_empty()) NotDiscardableComdats.insert(C); for (Function &F : M) if (const Comdat *C = F.getComdat()) if (!F.isDefTriviallyDead()) NotDiscardableComdats.insert(C); for (GlobalAlias &GA : M.aliases()) if (const Comdat *C = GA.getComdat()) if (!GA.isDiscardableIfUnused() || !GA.use_empty()) NotDiscardableComdats.insert(C);
Vamos tentar descrever em palavras o que essa função faz. Para cada variável global no módulo, ele solicita um objeto Comdat.
O que é um objeto Comdat?
Uma seção Comdat é uma seção no arquivo de objeto, na qual os objetos são colocados, que podem ser duplicados em outros arquivos de objeto. Cada objeto possui informações para o vinculador, indicando o que ele deve fazer quando são detectadas duplicatas. As opções podem ser: Qualquer um - faça qualquer coisa, ExactMatch - duplicatas devem corresponder completamente, caso contrário, ocorre um erro, Maior - pegue o objeto com o maior valor, NoDublicates - não deve haver uma duplicata, SameSize - as duplicatas devem ter o mesmo tamanho, caso contrário, ocorrerá um erro.
No LLVM, os dados do Comdat são representados por uma enumeração:
enum SelectionKind { Any,
e a classe Comdat realmente representa um par (Nome, SelectionKind). (De fato, tudo é mais complicado.) Todas as variáveis que por algum motivo não podem ser excluídas são colocadas em um conjunto de NotDiscardableComdats. Com funções e aliases globais, fazemos o mesmo - algo que não pode ser excluído é colocado em NotDiscardableComdats. Em seguida, são chamadas funções de otimização separadas para construtores globais, funções globais, variáveis globais, aliases globais e destruidores globais. As otimizações continuam no loop até que nenhuma otimização seja executada. A cada iteração do loop, o conjunto de NotDiscardableComdats é definido como zero.
Vamos ver quais objetos do listado nossa fonte de teste contém.
Variáveis globais:
1. @Do = internal global i32 (...)* null, align 8 2. @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1
(um pouco mais adiante, posso dizer que a primeira variável será excluída pelo otimizador na primeira iteração).
Funções:
define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...)
Observe que printf é declarado apenas, mas não definido.
Não há aliases globais.
Vamos dar uma olhada no exemplo desse passo de otimização e considerar como esse resultado foi gerado. Obviamente, analisar todas as opções de otimização mesmo em uma passagem é uma tarefa muito grande, pois envolve muitos casos especiais diferentes de otimizações. Vamos nos concentrar em nosso exemplo, considerando as funções e estruturas de dados que são importantes para entender o trabalho dessa passagem de otimização.
Inicialmente, o otimizador faz várias verificações desinteressantes nesse caso e chama a função processInternalGlobal, que tenta otimizar variáveis globais. Essa função também é bastante complexa e faz muitas coisas diferentes, mas estamos interessados em uma coisa:
if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ...
As informações às quais a variável global é atribuída ao valor um e apenas uma vez são extraídas da estrutura GS (GlobalStatus). Essa estrutura é preenchida na função de chamada:
static bool processGlobal(GlobalValue &GV, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { if (GV.getName().startswith("llvm.")) return false; GlobalStatus GS; if (GlobalStatus::analyzeGlobal(&GV, GS)) return false; ...
Aqui vemos mais um fato interessante: objetos cujos nomes começam com "llvm". não estão sujeitos à otimização (pois são chamadas do sistema para o llvm runtime). E, apenas no caso, os nomes das variáveis no LLVM IR podem conter pontos (e até mesmo consistir em um ponto com o prefixo @ ou%). A função analyGlobal é uma chamada para a API LLVM e não consideraremos seu trabalho interno. A estrutura do GlobalStatus deve ser exibida em detalhes, pois contém informações muito importantes para passes de otimização.
Vale a pena explicar por que "Se descobrirmos que o endereço do global é usado, nenhuma dessas informações será precisa". De fato, se pegarmos o endereço de uma variável global e depois escrevermos algo nesse endereço, não pelo nome, será extremamente difícil rastrear isso, e é melhor deixar as variáveis como estão, sem tentar otimizar .
Assim, entramos na função optimizeOnceStoredGlobal, para a qual a variável (GV) e o valor armazenado (StoredOnceVal) são transmitidos. Aqui estão elas:
@Do = internal unnamed_addr global i32 (...)* null, align 8
Em seguida, para o valor, o bitcast insignificante é excluído e para a variável a seguinte condição é verificada:
if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ...
isto é, a variável deve ser inicializada com um ponteiro nulo. Se for esse o caso, criamos uma nova variável SOVC correspondente ao valor da conversão StoredOnceVal para o tipo GV:
if (Constant *SOVC = dyn_cast<constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
Aqui, getBitCast é o método que retorna o comando bitcast, que digita os tipos na linguagem LLVM IR.
Depois disso, a função OptimizeAwayTrappingUsesOfLoads é chamada. Transfere a variável global GV e a constante LV.
A otimização direta é realizada pela função OptimizeAwayTrappingUsesOfValue (Valor * V, Constante * NovoV).
Para cada uso de uma variável:
for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<instruction>(*UI++);
se este for um comando Load, substitua seu operando por um novo valor:
if (LoadInst *LI = dyn_cast<loadinst>(I)) { LI->setOperand(0, NewV); Changed = true; }
Se a variável for usada na chamada ou invocação da função (que é exatamente o que acontece em nosso exemplo), crie uma nova função, substituindo seu argumento por um novo valor:
if (isa<callinst>(I) || isa<invokeinst>(I)) { CallSite CS(I); if (CS.getCalledValue() == V) {
Todos os outros argumentos para a função são simplesmente copiados.
Além disso, algoritmos de substituição semelhantes são fornecidos para as instruções de transmissão e GEP, mas, no nosso caso, isso não acontece.
As ações adicionais são as seguintes: examinamos todos os usos de uma variável global, tentando excluir tudo, exceto a atribuição de valor. Se isso der certo, podemos excluir a variável Do.
Assim, revisamos brevemente o trabalho do passe de otimização LLVM em um exemplo específico. Em princípio, nada de super complicado está aqui, mas é necessária uma programação mais cuidadosa para fornecer todas as combinações possíveis de comandos e tipos de variáveis. Obviamente, tudo isso deve ser coberto por testes. Aprender o código fonte dos otimizadores LLVM ajudará você a escrever suas otimizações, permitindo melhorar o código para alguns casos específicos.