¿Alguien sabe de alguna discusión de documentos algoritmos de alineación? Y muy relacionado, la relación de gráfico padre-hijo para llamar al gráfico.Algoritmo de alineación
Antecedentes: tengo un compilador escrito en Ocaml cuales inlines agresiva funciones, principalmente como resultado de esto y algunas otras optimizaciones que genera código más rápido para mi lenguaje de programación que la mayoría de los demás en muchas circunstancias (incluyendo incluso C).
Problema n. ° 1: El algoritmo tiene problemas con la recursión. Para esto, mi regla es solo para poner en línea a los niños en los padres, para evitar la recursión infinita, pero esto impide que las funciones hermanas se alineen una con la otra.
Problema n. ° 2: No conozco una forma sencilla de optimizar las operaciones de alineación. Mi algoritmo es imprescindible con la representación mutable de los cuerpos de función porque no parece remotamente posible hacer un algoritmo de alineación funcional eficiente. Si el gráfico de llamadas es un árbol, es claro que una alineación ascendente es óptima.
Información técnica: La alineación consiste en una serie de pasos de alineación. El problema es ordenar los pasos.
Cada paso funciona de la siguiente manera:
- hacemos una copia de la función a ser inline y beta- reducir a la sustitución de los parámetros tipo y parámetros de valores de argumentos.
- Reemplazamos declaración de retorno con una asignación a una nueva variable seguido de un salto al final del cuerpo de la función.
- La llamada original a la función es reemplazada por este cuerpo.
- Sin embargo, no hemos terminado. También debemos clonar todos los hijos de la función, reduciéndolos en beta también, y reparent los clones a la función de llamada.
La operación de clonación hace que sea extremadamente difícil para alinear las funciones recursivas. El truco habitual de mantener una lista de lo que ya está en progreso y simplemente verificar si ya estamos procesando esta llamada no funciona de forma ingenua porque la llamada recursiva ahora se mueve al código reducido en beta que se rellena en la llamada. función, y el objetivo de recursión puede haber cambiado a un hijo clonado. Sin embargo, ese niño, al llamar al padre, sigue llamando al padre original que llama a su hijo, y ahora el desenrollamiento de la recursión no se detendrá. Como mencioné, rompí esta regresión al permitir que se incluyera una llamada recursiva a un niño, lo que impidió que las repeticiones entre hermanos estuvieran en línea.
El costo de alineación se complica aún más por la necesidad de garbage collect funciones no utilizadas. Como la línea entrante es potencialmente exponencial, esto es esencial. Si todas las llamadas a una función están en línea, deberíamos deshacernos de la función si todavía no se ha introducido, de lo contrario perderemos tiempo en una función que ya no se usa. En realidad, hacer un seguimiento de quién llama es extremadamente difícil, porque al enderezar no estamos trabajando con una representación de función real, sino una función "desentrañada": por ejemplo, la lista de instrucciones se procesa secuencialmente y se crea una nueva lista, y en cualquier punto en el tiempo puede no haber una lista de instrucciones coherente.
En sus ML compilador Semanas Steven optó por utilizar una serie de pequeñas optimizaciones aplicadas en varias ocasiones, ya que esto hizo que las optimizaciones fácil de escribir y fácil de controlar, pero por desgracia esto no encuentra una gran cantidad de oportunidades de optimización en comparación con un algoritmo recursivo .
Problema n. ° 3: ¿Cuándo es seguro realizar una llamada a función?
Explicar este problema genéricamente: en un lenguaje funcional vago, los argumentos se envuelven en cierres y luego podemos alinear una aplicación; este es el modelo estándar para Haskell. Sin embargo, también explica por qué Haskell es tan lento. Los cierres no son necesarios si se conoce el argumento, entonces el parámetro se puede reemplazar directamente con su argumento donde se produce (este es el orden normal beta-reduction).
Sin embargo, si se sabe que la evaluación del argumento no es no terminante, se puede usar una evaluación entusiasta: el parámetro se le asigna el valor de la expresión una vez y luego se reutiliza. Un híbrido de estas dos técnicas es usar un cierre pero almacenar en caché el resultado dentro del objeto de cierre. Aún así, GHC no ha logrado producir código muy eficiente: es claramente muy difícil, especialmente si tiene una compilación por separado.
En Felix, tomé el enfoque opuesto. En lugar de exigir corrección y mejorar gradualmente la eficacia probando la semántica optimizada, confirmo que la optimización define la semántica. Esto garantiza el correcto funcionamiento del optimizador a expensas de la incertidumbre sobre cómo se comportará determinado código. La idea es proporcionar formas para que el programador obligue al optimizador a cumplir con la semántica deseada si la estrategia de optimización predeterminada es demasiado agresiva.
Por ejemplo, el modo de paso de parámetros predeterminado permite al compilador elegir si envolver el argumento en un cierre, reemplazar el parámetro con el argumento o asignar el argumento al parámetro. Si el programador quiere forzar un cierre, simplemente pueden pasar un cierre. Si el programador quiere forzar una evaluación entusiasta, marcan el parámetro var.
La complejidad aquí es mucho mayor que un lenguaje de programación funcional: Felix es un lenguaje de procedimientos con variables y punteros. También tiene clases de estilo Haskell. Esto hace que la rutina de entrada sea extremadamente compleja, por ejemplo, las instancias de clase de tipo reemplazan las funciones abstractas siempre que sea posible (debido a la especialización de tipo al llamar a una función polimórfica, puede ser posible encontrar una instancia mientras está en línea, entonces ahora tenemos una nueva función puede en línea).
Para que quede claro, tengo que agregar algunas notas más.
La alineación y otras optimizaciones tales como reducciones de términos definidas por el usuario, instancias de clases de tipos, comprobaciones de flujo de datos lineales para la eliminación de variables, optimización de compilación de cola, se realizan de una vez en una función determinada.
El problema de ordenar no es el orden para aplicar diferentes optimizaciones, el problema es ordenar las funciones.
Uso un algoritmo de muerte cerebral para detectar la recursión: construyo una lista de todo lo que usa directamente cada función, encuentro el cierre y luego verifico si la función está en el resultado. Tenga en cuenta que el conjunto de uso se acumula muchas veces durante la optimización, y esto es un serio cuello de botella.
Si una función es recursiva o no puede cambiar desafortunadamente. Una función recursiva puede volverse no recursiva después de la optimización de cola rec.Pero hay un caso mucho más difícil: crear una instancia "virtual" de una clase de tipo puede hacer que lo que parecía ser recursivo no recursivo.
En cuanto a las llamadas entre hermanos, el problema es que, dado f y g, donde f llama g y g llamadas f, realmente quiero alinear f en g, yg en f ... una vez. Mi regla de detención de regresión infinita es permitir solo la alineación de f en g si son recursivas recíprocas si f es un hijo de g, lo que excluye a los hermanos en línea.
Básicamente quiero "aplanar" todo el código "tanto como sea posible".
Voy a consultar la Wiki de GHC. También vale la pena leer sobre MlTon. Sin embargo, pude haber sido un poco confuso: mi compilador no hace la mayoría de las optimizaciones en los pases: ya terminaron todos a la vez. – Yttrill
gracias por el enlace Compilación por Igualdad de Saturación: ¡este es un enfoque muy agradable! – Yttrill
Creo que es realmente importante alinear en el idioma de origen o equivalente, ya que hay mucho más margen para la optimización. Punto importante de @gasche anterior. –