Otimização de alto nível/semântico

Question

Estou escrevendo um compilador e estou procurando recursos sobre otimização. Estou compilando o código da máquina, então qualquer coisa no tempo de execução está fora de questão.

O que estou procurando ultimamente é menos otimização de código e mais otimização semântica/de alto nível. Por exemplo:

free(malloc(400)); // should be completely optimized away

Mesmo que essas funções estivessem completamente inlinadas, elas poderiam eventualmente chamar as funções de memória do OS que nunca podem ser inlinhadas. Eu adoraria poder eliminar completamente essa afirmação sem construir regras de caso especial no compilador (afinal, malloc é apenas mais uma função).

Outro exemplo:

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

Nesta situação, eu adoraria poder inicializar bcapacidade de str.Length + 2 (o suficiente para manter exatamente o resultado, sem desperdiçar memória).

Para ser completamente honesto, não tenho idéia de por onde começar a enfrentar esse problema, então esperava que um lugar para começar. Houve algum trabalho realizado em áreas semelhantes? Existem compiladores que implementaram algo assim em um sentido geral?

Answer 1

Para fazer uma otimização em duas ou mais operações, você deve entender o relacionamento algébrico dessas duas operações. Se você visualizar as operações em seu domínio de problemas, elas geralmente têm esses relacionamentos.

Seu grátis (Malloc (400)) é possível porque o Free e o Malloc são inversos no domínio de alocação de armazenamento. Muitas operações têm inversas e ensinando ao compilador que são inversas, e demonstrando que os resultados de um fluxo de dados incondicionalmente no outro é o que é necessário. Você precisa garantir que seus inversos sejam realmente inversos e não haja uma surpresa em algum lugar; A/x*x parece apenas o valor A, mas se x é zero, você recebe uma armadilha. Se você não se importa com a armadilha, é um inverso; Se você se preocupa com a armadilha, a otimização será mais complexa: (se (x == 0), então trap () else a), que ainda é uma boa otimização se você acha que a divisão é cara.

Outros relacionamentos "algébricos" são possíveis. Por exemplo, existem operações idempotentes: zero uma variável (definindo qualquer coisa no mesmo valor repetidamente), etc. Existem operações em que um operando age como um elemento de identidade; X+0 ==> x para qualquer 0. Se x e 0 forem matrizes, isso ainda é verdadeiro e uma grande economia de tempo.

Outras otimizações podem ocorrer quando você pode raciocinar abstrair sobre o que o código está fazendo. "Interpretação abstrata" é um conjunto de técnicas para o raciocínio sobre valores, classificando os resultados em várias caixas interessantes (por exemplo, esse número inteiro é desconhecido, zero, negativo ou positivo). Para fazer isso, você precisa decidir quais caixas são úteis e calcular o valor abstrato em cada ponto. Isso é útil quando existem testes nas categorias (por exemplo, "se (x <0) {..." e você sabe abstrata que x é menor que zero; você pode otimizar o condicional.

Outra maneira é definir o que uma computação está fazendo simbolicamente e simular o cálculo para ver o resultado. Foi assim que você calculou o tamanho efetivo do buffer necessário; Você calculou o tamanho do buffer simbolicamente antes do início do loop e simulou o efeito de executar o loop para todas as iterações. Para isso, você precisa ser capaz de construir fórmulas simbólicas que representam propriedades do programa, compor tais fórmulas e geralmente simplificam essas fórmulas quando elas ficam incomumente complexas (tipos de desaparecimentos no esquema de interpretação abstrato). Você também deseja que esse cálculo simbólico leve em consideração as propriedades algébricas que descrevi acima. As ferramentas que fazem isso bem são boas na construção de fórmulas, e os sistemas de transformação de programas geralmente são bons fundamentos para isso. Um sistema de transformação de programas de origem a fonte que pode ser usado para fazer isso é o DMS Software Reengeneering Toolkit.

O que é difícil é decidir quais otimizações valem a pena fazer, porque você pode acabar com o controle de grandes quantidades de coisas, o que pode não pagar. Os ciclos de computador estão ficando mais baratos e, portanto, faz sentido rastrear mais propriedades do código no compilador.

Answer 2

o Broadway A estrutura pode estar na veia do que você está procurando. Os artigos sobre "transformação de origem a fonte" provavelmente também serão esclarecedores.