O compilador Stalin otimiza brutalmente, mas como?

14

A declaração de pesquisa de JM Siskind afirma:

Stalin é um compilador de otimização para o Scheme que executa análise estática de todo o programa e usa os resultados dessa análise para gerar código extremamente eficiente. Stalin utiliza uma grande coleção de técnicas de análise estática. Ele executa uma nova forma de análise de fluxo polivariável que usa análise de fluxo monovariante iterada para executar a divisão direcionada por fluxo: clonagem de cópias especializadas de procedimentos e atribuição por local de chamada de destinos a esses clones. Ele usa os resultados da análise de fluxo para executar análises de tempo de vida, análise de escape, análise de pontos a análise e análise de alias obrigatório. Essas análises suportam uma nova forma de conversão de fechamento leve que elimina a maioria dos slots de fechamento, usando técnicas como globalização e localização variáveis, compacta a cadeia traseira estática e geralmente elimina a maioria dos fechamentos dos programas. Ele também usa as análises acima para dar suporte ao gerenciamento de armazenamento baseado em região direcionado por fluxo, onde a coleta de lixo em tempo de execução é substituída pela alocação e desalocação estática com base no valor abstrato e no ponto do programa. Ele também realiza a conversão CPS leve direcionada ao fluxo, usando extensões das técnicas pioneiras no Screamer, para oferecer suporte a continuações de primeira classe extremamente eficientes. Por fim, ele suporta inlining direcionado ao fluxo e seleção de representação de baixo nível para escolher a implementação (ou não implementação) de tags, verificação de tags e envio de tags com base no valor abstrato e no ponto por programa. Isso elimina a maioria das tags de tempo de execução, verificação e identificação de tags, remoção de tags, envio de tags, boxe e unboxing dos programas. onde a coleta de lixo em tempo de execução é substituída pela alocação e desalocação estática com base no valor abstrato e no ponto por programa. Ele também realiza a conversão CPS leve direcionada ao fluxo, usando extensões das técnicas pioneiras no Screamer, para oferecer suporte a continuações de primeira classe extremamente eficientes. Por fim, ele suporta inlining direcionado ao fluxo e seleção de representação de baixo nível para escolher a implementação (ou não implementação) de tags, verificação de tags e envio de tags com base no valor abstrato e no ponto por programa. Isso elimina a maioria das tags de tempo de execução, verificação e identificação de tags, remoção de tags, envio de tags, boxe e unboxing dos programas. onde a coleta de lixo em tempo de execução é substituída pela alocação e desalocação estática com base no valor abstrato e no ponto por programa. Ele também realiza a conversão CPS leve direcionada ao fluxo, usando extensões das técnicas pioneiras no Screamer, para oferecer suporte a continuações de primeira classe extremamente eficientes. Por fim, ele suporta inlining direcionado ao fluxo e seleção de representação de baixo nível para escolher a implementação (ou não implementação) de tags, verificação de tags e envio de tags com base no valor abstrato e no ponto por programa. Isso elimina a maioria das tags de tempo de execução, verificação e identificação de tags, remoção de tags, envio de tags, boxe e unboxing dos programas. usando extensões das técnicas pioneiras no Screamer, para oferecer suporte a continuações de primeira classe extremamente eficientes. Por fim, ele suporta inlining direcionado ao fluxo e seleção de representação de baixo nível para escolher a implementação (ou não implementação) de tags, verificação de tags e envio de tags com base no valor abstrato e no ponto por programa. Isso elimina a maioria das tags de tempo de execução, verificação e identificação de tags, remoção de tags, envio de tags, boxe e unboxing dos programas. usando extensões das técnicas pioneiras no Screamer, para oferecer suporte a continuações de primeira classe extremamente eficientes. Por fim, ele suporta inlining direcionado ao fluxo e seleção de representação de baixo nível para escolher a implementação (ou não implementação) de tags, verificação de tags e envio de tags com base no valor abstrato e no ponto por programa. Isso elimina a maioria das tags de tempo de execução, verificação e identificação de tags, remoção de tags, envio de tags, boxe e unboxing dos programas.Essas análises e otimizações permitem que Stalin gere códigos extremamente eficientes que superem todos os outros compiladores de Esquemas por fatores que variam entre duzentos e cem, principalmente para códigos numericamente intensivos. Stalin geralmente gera código que supera o código c escrito à mão e Fortran.

Pude encontrar o seguinte artigo muito interessante sobre a implementação de fechamentos / chamadas de função: Conversão de fechamento leve direcionada por fluxo . Também enviei um e-mail ao autor para perguntar sobre os trabalhos sobre outros tópicos, mencionados como escritos no documento de conversão de fechamento:

Siskind, JM 2000a. Conversão CPS leve direcionada por fluxo. Em preparação.

Siskind, JM 2000b. Polivariância direcionada ao fluxo. Em preparação.

Siskind, JM 2000c. Seleção de representação direcionada por fluxo. Em preparação.

Siskind, JM 2000d. Gerenciamento de armazenamento direcionado por fluxo. Em preparação

Infelizmente, ele nunca chegou a escrever esses papéis. Minha pergunta para você é: existem trabalhos alternativos ou relacionados que abordam esses tópicos? Estou muito interessado em aprender como Stalin (ou outros compiladores) podem compilar uma linguagem de alto nível, como o Scheme que é coletado de lixo, digitado dinamicamente, suporta funções de primeira classe e até continuações de primeira classe, pode ser estaticamente compilado para um código tão eficiente . Embora os trabalhos sobre análise de fluxo sejam bastante abundantes, os trabalhos sobre o uso dos resultados dessa análise para fazer as otimizações mencionadas acima não são.

Jules
fonte

Respostas:

11

A chave é provavelmente o fato de que ele usa análise de todo o programa e otimização de todo o programa. Quanto mais você souber sobre como um programa se comporta, mais você pode se especializar, alinhar e obter desempenho.

O compilador MLton para o ML padrão faz uma coisa semelhante ( http://mlton.org/ ). Há uma apresentação (pelo menos) sobre isso: http://mlton.org/pages/References/attachments/060916-mlton.pdf .

O trabalho anterior foi realizado por Craig Chambers e seu grupo na Universidade de Washington (por exemplo: http://www.cs.washington.edu/research/projects/cecil/www/pubs/jdean-thesis.html ). Isso foi feito no contexto do Self e mais tarde Cecil / Vortex.

Provavelmente há mais trabalho na comunidade Scheme / Lisp. Você provavelmente deseja considerar "otimização de programa inteiro" no Google.

Dave Clarke
fonte