Computer Science › Software + Computação Distribuída
Linguagens de Programação construiu um interpretador que percorre a árvore, fazendo scan, parse e avaliando um AST diretamente em tempo de execução. Um compilador real reaproveita exatamente esses mesmos estágios de front end, esta disciplina retoma logo depois de o AST existir, perguntando o que acontece quando um programa é traduzido antecipadamente para outra linguagem em vez de rodado nó por nó.
Um interpretador resolve o escopo de uma variável operacionalmente, percorrendo uma cadeia viva de ambientes enquanto o programa roda. Um compilador tem de responder à exata mesma pergunta, a qual declaração este nome se refere?, como uma computação estática, de uma passagem sobre o AST, antes de uma única instrução ser jamais gerada, usando uma tabela de símbolos em vez de um ambiente de tempo de execução.
Progresso e preservação, como cobertos em Linguagens de Programação, foram provados sobre um pequeno cálculo um passo de avaliação por vez. Um compilador precisa da mesma garantia entregue de forma diferente: uma única passagem em lote sobre o AST inteiro que ou faz a checagem de tipos completamente antes de qualquer código existir, ou rejeita o programa de uma vez, o ponto de vantagem estático e antecipado sobre o exato mesmo trade-off de tipagem estática.
Uma gramática livre de contexto já foi mostrada gerando uma árvore de derivação, sem semântica atrelada. As gramáticas de atributos atrelam uma ação semântica a cada produção, atributos herdados e sintetizados fluindo para cima e para baixo na mesma árvore de análise, que é exatamente o mecanismo que um analisador semântico e um gerador de código reais rodam para transformar sintaxe em significado.
Traduzir um AST diretamente para código de máquina amarraria toda otimização e todo gerador de código a uma linguagem-fonte específica e a uma arquitetura-alvo específica. Uma representação intermediária (IR) é a camada deliberada no meio, escreva N front ends e M back ends em vez de N×M, e rode toda passagem de otimização uma vez, sobre o IR, independentemente da linguagem-fonte ou da máquina-alvo.
O código de três endereços é o IR linear que a maioria dos compiladores de livro-texto escolhe: toda instrução tem no máximo um operador e no máximo três operandos (duas fontes, um destino), de modo que uma árvore de expressão de AST é achatada numa sequência que uma passagem posterior pode varrer, reordenar e reescrever uma instrução por vez.
Um bloco básico é uma sequência maximal de instruções de três endereços com uma entrada e uma saída, sem saltos no meio, sem saltos para o meio. Ligar blocos básicos com arestas para todo salto possível produz o grafo de fluxo de controle, a estrutura sobre a qual toda análise de fluxo de dados e toda passagem de otimização nesta disciplina é de fato definida.
A forma SSA renomeia toda variável para que ela seja atribuída exatamente uma vez no texto do programa, inserindo uma função Φ (phi) onde quer que dois caminhos de fluxo de controle se juntem com definições diferentes ainda vivas. Essa única reestruturação é por que quase todo compilador otimizador moderno, LLVM à frente, constrói o seu middle end sobre SSA: muitos fatos de fluxo de dados colapsam em propriedades simples das próprias variáveis renomeadas.
Toda análise clássica de fluxo de dados, definições que alcançam, variáveis vivas, expressões disponíveis, é uma instância da mesma receita geral: um reticulado de fatos possíveis, uma função de transferência por bloco básico, e um algoritmo iterativo que roda até um ponto fixo sobre o grafo de fluxo de controle. Aprender a receita uma vez significa que toda análise específica depois desta é só uma escolha de reticulado e função de transferência.
As definições que alcançam perguntam, para cada ponto do programa, quais atribuições poderiam possivelmente ter produzido o valor que está atualmente numa variável, a primeira instância concreta do arcabouço geral, e a análise de que a propagação de constantes precisa para saber que é sequer seguro substituir um valor.
Uma variável está viva num ponto se algum caminho a partir dali ainda lê o seu valor atual antes de sobrescrevê-lo. A análise de variáveis vivas roda para trás, em vez de para frente, pelo grafo de fluxo de controle, a inversão de direção que a torna a única análise sem a qual a alocação de registradores e a eliminação de código morto não conseguem passar.
Uma expressão está disponível num ponto se todo caminho que leva até lá já a computou, e nenhum dos seus operandos foi reatribuído desde então. Expressões disponíveis é a análise de fluxo direto, do tipo must, que diz à eliminação de subexpressões comuns exatamente quais recomputações são seguras de deletar.
A dobra de constantes avalia uma expressão puramente constante uma vez, em tempo de compilação, em vez de a cada execução; a propagação de constantes é o que a alimenta com entradas reais para dobrar, substituindo o valor constante conhecido de uma variável (justificado pelas definições que alcançam) onde quer que ela seja usada, muitas vezes expondo mais dobras numa única passagem.
Quando a análise de expressões disponíveis reporta que uma expressão já foi computada em todo caminho que alcança este ponto, recomputá-la é puro desperdício, a eliminação de subexpressões comuns substitui a segunda computação por uma referência ao primeiro resultado, o retorno direto de otimização da análise do conceito anterior.
Uma atribuição cujo alvo nunca está vivo depois, reportada diretamente pela análise de variáveis vivas, computa um valor que nada jamais lerá; a eliminação de código morto a deleta de uma vez, e muitas vezes descobre uma nova rodada de código morto quando os seus próprios operandos perdem o seu último uso.
Um laço roda o seu corpo muito mais vezes do que qualquer outro código num programa típico, então mover uma computação invariante do laço para antes dele (movimentação de código invariante) e substituir uma operação cara por uma mais barata que rende a mesma sequência de valores (redução de força, uma multiplicação-pelo-contador-do-laço virando uma adição corrente) compensam desproporcionalmente para uma pequena reescrita local.
\"Este ramo é jamais tomado?\", \"este ponteiro jamais faz alias com aquele?\", \"este laço sempre termina?\" são todas genuinamente indecidíveis em geral, instâncias diretas do teorema de Rice, já que cada uma faz uma pergunta semântica não trivial sobre o comportamento de um programa. Toda análise de fluxo de dados nesta disciplina é, portanto, uma APROXIMAÇÃO deliberadamente conservadora, segura de usar precisamente porque só responde \"talvez, então não otimize\" em vez de chutar errado.
IR otimizado ainda não é código de máquina, a seleção de instruções é a passagem que cobre uma árvore de expressão de IR com um conjunto de ladrilhos, cada ladrilho um modelo para uma instrução real do alvo (já coberta concretamente nos registradores e instruções aritméticas de `c-and-assembly`), escolhendo o ladrilhamento que cobre a árvore ao menor custo total, exatamente o tipo de casamento de padrões em árvore que os algoritmos de maximal munch automatizam.
A seleção de instruções assume um suprimento ilimitado de registradores virtuais; o hardware real tem um punhado. A alocação de registradores constrói um grafo de interferência a partir da análise de variáveis vivas (dois valores que estão simultaneamente vivos não podem compartilhar um registrador), o colore com K cores para K registradores reais, e, quando nenhuma coloração válida existe, faz spill de um valor para a pilha ou coalesce registradores tornados redundantes por um move, o algoritmo no estilo de Chaitin que compiladores reais ainda usam.
O risco de uso-de-carga já mostrou que uma CPU com pipeline trava quando uma instrução precisa de um valor que o seu predecessor imediato ainda não produziu. O escalonamento de instruções é a resposta do lado do compilador: reordenar instruções independentes (a alocação de registradores já fixou QUAIS registradores, esta passagem só muda QUANDO cada instrução roda) para pôr trabalho não relacionado entre uma carga e o seu primeiro uso, escondendo a trava sem mudar o que o programa computa.
Todo prólogo/epílogo e toda regra de passagem de argumentos na convenção de chamada System V AMD64, já coberta concretamente em `c-and-assembly`, é um ALVO que um gerador de código tem de atingir, não um fato sobre assembly escrito à mão apenas, este conceito é a lógica de geração do lado do compilador que decide o tamanho do quadro a partir da contagem de spills do alocador de registradores e emite exatamente o prólogo/epílogo que a convenção exige, para toda função, automaticamente.
Toda passagem nesta disciplina pode rodar uma vez, antecipadamente, produzindo um binário estático (AOT), ou as exatas mesmas passagens podem rodar em tempo de execução, sobre um programa em execução, com a opção adicional de especializar código para valores só observados enquanto ele executa (JIT) ao custo de pagar o tempo de compilação com o próprio orçamento de execução do programa; sistemas reais (a JVM, o V8, o PyPy) rotineiramente misturam ambos, rodando um interpretador primeiro e promovendo só o código quente que um perfil de fato identifica.
Cada estágio construído nesta disciplina, aplicado em ordem a uma pequena expressão real dentro de um laço: analisada sintaticamente num AST já coberto em `programming-languages`, checada e resolvida por uma tabela de símbolos, rebaixada a código de três endereços e a um grafo de fluxo de controle, apertada pelas definições que alcançam numa dobra de constante, com registradores alocados por coloração de grafo, e por fim emitida como as instruções x86-64 reais e o quadro da convenção de chamada que `c-and-assembly` já cobre isoladamente, o pipeline completo da frente ao fim, nomeado estágio por estágio.
Part of the Computer Science curriculum.
Linguagens de Programação construiu um interpretador que percorre a árvore, fazendo scan, parse e avaliando um AST diretamente em tempo de execução. Um compilador real reaproveita exatamente esses mesmos estágios de front end, esta disciplina retoma logo depois de o AST existir, perguntando o que acontece quando um programa é traduzido antecipadamente para outra linguagem em vez de rodado nó por nó.
Um interpretador resolve o escopo de uma variável operacionalmente, percorrendo uma cadeia viva de ambientes enquanto o programa roda. Um compilador tem de responder à exata mesma pergunta, a qual declaração este nome se refere?, como uma computação estática, de uma passagem sobre o AST, antes de uma única instrução ser jamais gerada, usando uma tabela de símbolos em vez de um ambiente de tempo de execução.
Progresso e preservação, como cobertos em Linguagens de Programação, foram provados sobre um pequeno cálculo um passo de avaliação por vez. Um compilador precisa da mesma garantia entregue de forma diferente: uma única passagem em lote sobre o AST inteiro que ou faz a checagem de tipos completamente antes de qualquer código existir, ou rejeita o programa de uma vez, o ponto de vantagem estático e antecipado sobre o exato mesmo trade-off de tipagem estática.
Uma gramática livre de contexto já foi mostrada gerando uma árvore de derivação, sem semântica atrelada. As gramáticas de atributos atrelam uma ação semântica a cada produção, atributos herdados e sintetizados fluindo para cima e para baixo na mesma árvore de análise, que é exatamente o mecanismo que um analisador semântico e um gerador de código reais rodam para transformar sintaxe em significado.
Traduzir um AST diretamente para código de máquina amarraria toda otimização e todo gerador de código a uma linguagem-fonte específica e a uma arquitetura-alvo específica. Uma representação intermediária (IR) é a camada deliberada no meio, escreva N front ends e M back ends em vez de N×M, e rode toda passagem de otimização uma vez, sobre o IR, independentemente da linguagem-fonte ou da máquina-alvo.
O código de três endereços é o IR linear que a maioria dos compiladores de livro-texto escolhe: toda instrução tem no máximo um operador e no máximo três operandos (duas fontes, um destino), de modo que uma árvore de expressão de AST é achatada numa sequência que uma passagem posterior pode varrer, reordenar e reescrever uma instrução por vez.
Um bloco básico é uma sequência maximal de instruções de três endereços com uma entrada e uma saída, sem saltos no meio, sem saltos para o meio. Ligar blocos básicos com arestas para todo salto possível produz o grafo de fluxo de controle, a estrutura sobre a qual toda análise de fluxo de dados e toda passagem de otimização nesta disciplina é de fato definida.
A forma SSA renomeia toda variável para que ela seja atribuída exatamente uma vez no texto do programa, inserindo uma função Φ (phi) onde quer que dois caminhos de fluxo de controle se juntem com definições diferentes ainda vivas. Essa única reestruturação é por que quase todo compilador otimizador moderno, LLVM à frente, constrói o seu middle end sobre SSA: muitos fatos de fluxo de dados colapsam em propriedades simples das próprias variáveis renomeadas.
Toda análise clássica de fluxo de dados, definições que alcançam, variáveis vivas, expressões disponíveis, é uma instância da mesma receita geral: um reticulado de fatos possíveis, uma função de transferência por bloco básico, e um algoritmo iterativo que roda até um ponto fixo sobre o grafo de fluxo de controle. Aprender a receita uma vez significa que toda análise específica depois desta é só uma escolha de reticulado e função de transferência.
As definições que alcançam perguntam, para cada ponto do programa, quais atribuições poderiam possivelmente ter produzido o valor que está atualmente numa variável, a primeira instância concreta do arcabouço geral, e a análise de que a propagação de constantes precisa para saber que é sequer seguro substituir um valor.
Uma variável está viva num ponto se algum caminho a partir dali ainda lê o seu valor atual antes de sobrescrevê-lo. A análise de variáveis vivas roda para trás, em vez de para frente, pelo grafo de fluxo de controle, a inversão de direção que a torna a única análise sem a qual a alocação de registradores e a eliminação de código morto não conseguem passar.
Uma expressão está disponível num ponto se todo caminho que leva até lá já a computou, e nenhum dos seus operandos foi reatribuído desde então. Expressões disponíveis é a análise de fluxo direto, do tipo must, que diz à eliminação de subexpressões comuns exatamente quais recomputações são seguras de deletar.
A dobra de constantes avalia uma expressão puramente constante uma vez, em tempo de compilação, em vez de a cada execução; a propagação de constantes é o que a alimenta com entradas reais para dobrar, substituindo o valor constante conhecido de uma variável (justificado pelas definições que alcançam) onde quer que ela seja usada, muitas vezes expondo mais dobras numa única passagem.
Quando a análise de expressões disponíveis reporta que uma expressão já foi computada em todo caminho que alcança este ponto, recomputá-la é puro desperdício, a eliminação de subexpressões comuns substitui a segunda computação por uma referência ao primeiro resultado, o retorno direto de otimização da análise do conceito anterior.
Uma atribuição cujo alvo nunca está vivo depois, reportada diretamente pela análise de variáveis vivas, computa um valor que nada jamais lerá; a eliminação de código morto a deleta de uma vez, e muitas vezes descobre uma nova rodada de código morto quando os seus próprios operandos perdem o seu último uso.
Um laço roda o seu corpo muito mais vezes do que qualquer outro código num programa típico, então mover uma computação invariante do laço para antes dele (movimentação de código invariante) e substituir uma operação cara por uma mais barata que rende a mesma sequência de valores (redução de força, uma multiplicação-pelo-contador-do-laço virando uma adição corrente) compensam desproporcionalmente para uma pequena reescrita local.
\"Este ramo é jamais tomado?\", \"este ponteiro jamais faz alias com aquele?\", \"este laço sempre termina?\" são todas genuinamente indecidíveis em geral, instâncias diretas do teorema de Rice, já que cada uma faz uma pergunta semântica não trivial sobre o comportamento de um programa. Toda análise de fluxo de dados nesta disciplina é, portanto, uma APROXIMAÇÃO deliberadamente conservadora, segura de usar precisamente porque só responde \"talvez, então não otimize\" em vez de chutar errado.
IR otimizado ainda não é código de máquina, a seleção de instruções é a passagem que cobre uma árvore de expressão de IR com um conjunto de ladrilhos, cada ladrilho um modelo para uma instrução real do alvo (já coberta concretamente nos registradores e instruções aritméticas de `c-and-assembly`), escolhendo o ladrilhamento que cobre a árvore ao menor custo total, exatamente o tipo de casamento de padrões em árvore que os algoritmos de maximal munch automatizam.
A seleção de instruções assume um suprimento ilimitado de registradores virtuais; o hardware real tem um punhado. A alocação de registradores constrói um grafo de interferência a partir da análise de variáveis vivas (dois valores que estão simultaneamente vivos não podem compartilhar um registrador), o colore com K cores para K registradores reais, e, quando nenhuma coloração válida existe, faz spill de um valor para a pilha ou coalesce registradores tornados redundantes por um move, o algoritmo no estilo de Chaitin que compiladores reais ainda usam.
O risco de uso-de-carga já mostrou que uma CPU com pipeline trava quando uma instrução precisa de um valor que o seu predecessor imediato ainda não produziu. O escalonamento de instruções é a resposta do lado do compilador: reordenar instruções independentes (a alocação de registradores já fixou QUAIS registradores, esta passagem só muda QUANDO cada instrução roda) para pôr trabalho não relacionado entre uma carga e o seu primeiro uso, escondendo a trava sem mudar o que o programa computa.
Todo prólogo/epílogo e toda regra de passagem de argumentos na convenção de chamada System V AMD64, já coberta concretamente em `c-and-assembly`, é um ALVO que um gerador de código tem de atingir, não um fato sobre assembly escrito à mão apenas, este conceito é a lógica de geração do lado do compilador que decide o tamanho do quadro a partir da contagem de spills do alocador de registradores e emite exatamente o prólogo/epílogo que a convenção exige, para toda função, automaticamente.
Toda passagem nesta disciplina pode rodar uma vez, antecipadamente, produzindo um binário estático (AOT), ou as exatas mesmas passagens podem rodar em tempo de execução, sobre um programa em execução, com a opção adicional de especializar código para valores só observados enquanto ele executa (JIT) ao custo de pagar o tempo de compilação com o próprio orçamento de execução do programa; sistemas reais (a JVM, o V8, o PyPy) rotineiramente misturam ambos, rodando um interpretador primeiro e promovendo só o código quente que um perfil de fato identifica.
Cada estágio construído nesta disciplina, aplicado em ordem a uma pequena expressão real dentro de um laço: analisada sintaticamente num AST já coberto em `programming-languages`, checada e resolvida por uma tabela de símbolos, rebaixada a código de três endereços e a um grafo de fluxo de controle, apertada pelas definições que alcançam numa dobra de constante, com registradores alocados por coloração de grafo, e por fim emitida como as instruções x86-64 reais e o quadro da convenção de chamada que `c-and-assembly` já cobre isoladamente, o pipeline completo da frente ao fim, nomeado estágio por estágio.