De Alto Nivel / optimización semántica

Question

Estoy escribiendo un compilador, y estoy en busca de recursos en la optimización. Estoy compilando en código máquina, así que cualquier cosa en tiempo de ejecución está fuera de la cuestión.

Lo que he estado buscando últimamente es menos optimización de código y optimización de alto nivel más semántica /. Por ejemplo:

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

Aunque estas funciones fueron completamente entre líneas, que eventualmente podrían llamar a las funciones de memoria del sistema operativo que nunca puede ser inline. Me encantaría ser capaz de eliminar por completo esa declaración sin la construcción de normas de casos especiales en que el compilador (después de todo, malloc es más que otra función).

Otro ejemplo:

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

En esta situación me gustaría ser capaz de inicializar la capacidad de b a str.Length + 2 (exactamente lo suficiente para aguantar el resultado, sin perder la memoria).

Para ser completamente honesto, no tengo idea de por dónde empezar para hacer frente a este problema, así que estaba esperando un lugar para empezar. ¿Ha habido algún trabajo realizado en áreas similares? ¿Hay compiladores que han implementado nada como esto en un sentido general?

Answer 1

Para hacer una optimización a través de 2 o más operaciones, hay que entender la relación algebraica de estas dos operaciones. Si ve las operaciones en su dominio del problema, que a menudo tienen este tipo de relaciones.

Su libre (malloc (400)) es posible porque libre y malloc son inversas en el dominio de la asignación de almacenamiento. Una gran cantidad de operaciones tienen inversos y enseñar el compilador que son inversas, y demostrando que los resultados de un flujo de datos sin condiciones en la otra, es lo que se necesita. Usted tiene que asegurarse de que sus inversas realmente son inversas y no es una sorpresa en alguna parte; a / x * x parece que sólo el valor de una, pero si x es cero se obtiene una trampa. Si no se preocupan por la trampa, es una inversa; si se preocupan por la trampa entonces la optimización es más compleja:       (Si (x == 0), entonces trampa () else a) que sigue siendo una buena optimización si usted piensa brecha es caro.

Otras relaciones "algebraicas" son posibles. Por ejemplo, hay puede idempotente operaciones: puesta a cero una variable de nada (ajuste a la misma valor en varias ocasiones), etc. Hay operaciones en las que actúa un operando como un elemento de identidad; X + 0 ==> X para cualquier 0. Si X y 0 son matrices, esto sigue siendo cierto y un ahorro de tiempo grande.

Otras optimizaciones pueden ocurrir cuando se puede razonar de manera abstracta acerca de lo que el código está haciendo. "Interpretación abstracta" es un conjunto de técnicas para razonar acerca valores de la clasificación de resultados en varios contenedores de interés (por ejemplo, este entero es desconocido, cero, negativo o positivo). Para ello, tiene que decidir qué bins son útiles y, a continuación calculan el valor abstracto en cada punto. Esto es útil cuando hay pruebas en categorías (por ejemplo, "si (x <0) {..." y que conoces abstractamente que x es menor que cero; se les puede optimizar la distancia condicional.

Otra forma es definir lo que es un cálculo está haciendo simbólicamente, y simular el cálculo para ver el resultado. Así es como se calculó el tamaño efectivo de la memoria intermedia requerida; se calculó el tamaño del búfer simbólicamente antes del inicio del bucle, y simulado el efecto de la ejecución del bucle para todas las iteraciones. Para ello, tiene que ser capaz de construir fórmulas simbólicas que representa propiedades de programas, componer tales fórmulas, y, a menudo simplificar tales fórmulas cuando llegan unusably complejos (tipos de fundidos en el resumen esquema de interpretación). También desea que ese cálculo simbólico para tener en cuenta las propiedades algebraicas he descrito anteriormente. Herramientas que hacen esto también son buenos en la construcción de fórmulas y sistemas de transformación de programas a menudo son buenas bases para ello. Un sistema de transformación de programas de fuente a fuente que se puede utilizar para hacer esto es la software DMS Reingeniería Toolkit .

Lo difícil es decidir qué optimizaciones son vale la pena hacerlo, porque se puede terminar de hacer el seguimiento de grandes cantidades de material, que pueden no dar sus frutos. ciclos de computación son cada vez más barato, y lo que tiene sentido para hacer un seguimiento más propiedades del código en el compilador.

Answer 2

El marco Broadway podría estar en la línea de Que estas buscando. Los documentos sobre la "transformación de fuente a fuente" probablemente también ser esclarecedor.