Rastreando a compilação just-in-time - Tracing just-in-time compilation

O rastreamento da compilação just-in-time é uma técnica usada por máquinas virtuais para otimizar a execução de um programa em tempo de execução . Isso é feito gravando uma sequência linear de operações executadas com frequência, compilando -as em código de máquina nativo e executando-as. Isso se opõe aos compiladores just-in-time (JIT) tradicionais que funcionam por método.

Visão geral

A compilação just-in-time é uma técnica para aumentar a velocidade de execução de programas, compilando partes de um programa em código de máquina em tempo de execução. Uma maneira de categorizar diferentes compiladores JIT é por seu escopo de compilação. Enquanto os compiladores JIT baseados em método traduzem um método por vez em código de máquina, os JITs de rastreamento usam loops executados com frequência como sua unidade de compilação. Os JITs de rastreamento são baseados nas suposições de que os programas passam a maior parte do tempo em alguns loops do programa ("hot loops") e as iterações de loop subsequentes geralmente seguem caminhos semelhantes. As máquinas virtuais que possuem um JIT de rastreamento geralmente são ambientes de execução de modo misto, o que significa que elas têm um interpretador ou um compilador de método, além do JIT de rastreamento.

Detalhes técnicos

Um compilador JIT de rastreamento passa por várias fases no tempo de execução. Primeiro, são coletadas informações de criação de perfil para loops. Depois que um loop quente foi identificado, uma fase de rastreamento especial é inserida, que registra todas as operações executadas desse loop. Essa sequência de operações é chamada de rastreamento. O rastreamento é então otimizado e compilado em código de máquina (rastreamento). Quando esse loop é executado novamente, o rastreamento compilado é chamado em vez da contraparte do programa.

Essas etapas são explicadas em detalhes a seguir:

Fase de criação de perfil

O objetivo da criação de perfil é identificar loops ativos. Isso geralmente é feito contando o número de iterações para cada loop. Depois que a contagem de um loop excede um certo limite, o loop é considerado quente e a fase de rastreamento é inserida.

Fase de rastreamento

Na fase de rastreamento, a execução do loop prossegue normalmente, mas, além disso, cada operação executada é registrada em um rastreamento. As operações gravadas são normalmente armazenadas na árvore de rastreamento , geralmente em uma representação intermediária (IR). O rastreamento segue as chamadas de função, o que faz com que sejam embutidas no rastreamento. O rastreamento continua até que o loop chegue ao fim e volte para o início.

Como o rastreamento é registrado seguindo um caminho de execução concreto do loop, as execuções posteriores desse rastreamento podem divergir desse caminho. Para identificar os locais onde isso pode acontecer, instruções especiais de proteção são inseridas no rastreamento. Um exemplo de tal lugar são as declarações if. O guarda é uma verificação rápida para determinar se a condição original ainda é verdadeira. Se um guarda falhar, a execução do rastreamento é abortada.

Como o rastreamento é feito durante a execução, o rastreamento pode ser feito para conter informações de tempo de execução (por exemplo, informações de tipo ). Essas informações podem ser usadas posteriormente na fase de otimização para aumentar a eficiência do código.

Fase de otimização e geração de código

Os rastreamentos são fáceis de otimizar, pois representam apenas um caminho de execução, o que significa que não existe fluxo de controle e não precisa ser manuseado. Otimizações típicas incluem a eliminação constante-subexpression , eliminação de código morto , registar alocação , movimento invariável-code , dobrar constante e análise de fuga .

Após a otimização, o trace é transformado em código de máquina. Da mesma forma que a otimização, isso é fácil devido à natureza linear dos traços.

Execução

Após o rastreamento ter sido compilado para o código de máquina, ele pode ser executado em iterações subsequentes do loop. A execução do rastreamento continua até que um guarda falhe.

História

Enquanto a ideia de JITs remonta à década de 1960, o rastreamento de JITs passou a ser usado com mais frequência apenas recentemente. A primeira menção de uma ideia que é semelhante à ideia de hoje de rastrear JITs foi em 1970. Foi observado que o código compilado pode ser derivado de um interpretador em tempo de execução simplesmente armazenando as ações realizadas durante a interpretação.

A primeira implementação de rastreamento é o Dynamo, "um sistema de otimização dinâmica de software que é capaz de melhorar de forma transparente o desempenho de um fluxo de instrução nativo conforme ele é executado no processador". Para fazer isso, o fluxo de instrução nativo é interpretado até que uma seqüência de instruções "quente" seja encontrada. Para esta sequência, uma versão otimizada é gerada, armazenada em cache e executada.

O Dínamo foi posteriormente estendido para o DínamoRIO . Um projeto baseado no DynamoRIO foi uma estrutura para construção de interpretador que combina rastreamento e avaliação parcial. Foi usado para "remover dinamicamente a sobrecarga do interpretador de implementações de linguagem".

Em 2006, foi desenvolvido o HotpathVM, o primeiro compilador JIT de rastreamento para uma linguagem de alto nível. Esta VM foi capaz de identificar dinamicamente instruções de bytecode executadas com frequência, que são rastreadas e então compiladas em código de máquina usando construção de atribuição única estática (SSA). A motivação para HotpathVM era ter uma JVM eficiente para dispositivos móveis com recursos limitados.

Outro exemplo de JIT de rastreamento é o TraceMonkey , uma das implementações de JavaScript da Mozilla para Firefox (2009). TraceMonkey compila traços de loop executados com freqüência na linguagem dinâmica JavaScript em tempo de execução e especializa o código gerado para os tipos dinâmicos reais que ocorrem em cada caminho.

Outro projeto que utiliza JITs de rastreamento é o PyPy . Ele permite o uso de JITs de rastreamento para implementações de linguagem que foram escritas com a cadeia de ferramentas de tradução do PyPy, melhorando assim o desempenho de qualquer programa executado usando esse interpretador. Isso é possível rastreando o próprio intérprete, em vez do programa executado por ele.

O rastreamento de JITs também foi explorado pela Microsoft no projeto SPUR para sua Common Intermediate Language (CIL). SPUR é um rastreador genérico para CIL, que também pode ser usado para rastrear por meio de uma implementação de JavaScript.

Exemplo de um traço

Considere o seguinte programa Python que calcula a soma dos quadrados de números inteiros sucessivos até que a soma exceda 100.000:

def square(x):
    return x * x

i = 0
y = 0
while True:
    y += square(i)
    if y > 100000:
        break
    i = i + 1

Um rastreamento para este programa pode ser parecido com isto:

 loopstart(i1, y1)
 i2 = int_mul(i1, i1)		# x*x
 y2 = int_add(y1, i2)		# y += i*i
 b1 = int_gt(y2, 100000)
 guard_false(b1)
 i3 = int_add(i1, 1)		# i = i+1
 jump(i3, y2)

Observe como a chamada de função para squareestá embutida no rastreamento e como a instrução if é transformada em a guard_false.

Veja também

• Geração de código
• Dalvik
• Ponto de acesso
• Intérprete
• Otimização guiada por perfil
• RPython
• Codificação de dicionário semântico

Referências

links externos

• Site oficial da LuaJIT