Evaluación parcial/especialización con LLVM-gcc o gcc

Question

Estoy interesado en la evaluación (parcial) en tiempo de compilación para c/C++ (no con parámetros de plantilla como en C++). Vamos a considerar el caso siguiente (tomado de [1]):

double mypower(double x, int n) { 
    int i; 
    double ret = x; 
    for (i = 1; i < n; i++) { 
    ret *= x; 
    } 
    return ret; 
} 

Luego llama a esta función en alguna parte del código con:

mypower(x,3); // y varies all the time, 

A continuación, el compilador puede optimizar este (por ejemplo desenrollado del bucle). Algunas de las funciones de uso frecuente que utilizo podrían beneficiarse realmente de esa optimización (probada manualmente por la función especializada creadora). La presentación [1] describe un proceso en el que se busca la función y se reemplaza por una versión especializada de la función. Esto parece funcionar Pero no parece ser muy universal, el código debe escribirse para las funciones que deben reemplazarse.

La presentación parece ser de 2008, no pude encontrar nada sustancial más información que en esta fuente. Entonces, ¿ha mejorado algo desde entonces? Preferiría algún tipo de automatismo, que hace lo mismo para todas las funciones posiblemente controladas por sintaxis de atributo (por ejemplo, __attribute__(peval) ...). Además, me gustaría que lo mismo funcione para código orientado a objetos, creando clases especializadas para diferentes objetos ([2] parece sugerir que esto no es posible).

Además, me gustaría que esta especialización no solo funcione para las constantes que se encuentran en el código. Estoy pensando en un programa compilado a LLVM IR (código de bytes) podría hacer lo siguiente:

1. Ejecución de la Programm durante una fase de inicialización de un intérprete, durante esa fase de inicialización del programa podría leer algunos de configuración desde un archivo. Después de la inicialización, el intérprete se detiene.

2. Algunas variables (incluidas las variables miembro) se corrigen a partir de ese momento. Extraiga estas variables (por ejemplo, marcado por atributo durante la compilación).

3. Crea funciones y clases especializadas. Clonar estos en el bytecode.

4. Ejecute el JIT para crear código de máquina nativo.

Esto es mucho lo que pido y pocos programas intensivos en computación se beneficiarían de tal optimización. Pero algunas personas deben estar trabajando en eso. Probablemente no conozco los términos de búsqueda correctos para alimentar a google.

Nota: No sugiero clases de plantilla con parámetros sin tipo o especialización manual, ya lo hago. Solo preferiría que el compilador hiciera el trabajo por mí.

Enlaces:

[1] Presentation how to partial evaluate in LLVM

[2] Forum message about partial evaluation

Answer 1

Esto es en gran parte en la arena de optimizaciones interprocedurales. llvm tiene algunos de ellos, en particular la propagación constante de IP, lo que solo ayudaría si usa mypower (x, 3) en todos los sitios de llamadas en una unidad de traducción. Lo que describes es posible, pero aún no se ha hecho. Mejorar el pase IPCP es lo que le gustaría hacer: clonar y especializar una función en un sitio de llamadas en particular.Esto podría, si tienes suficientes unidades de traducción, causar una gran cantidad de código grande, por lo que la gente realmente no ha buscado hacerlo.

Esto probablemente tendría más uso en el nivel de LTO cuando puede ver todas las llamadas en un programa.

Answer 2

Puede hacerlo utilizando transformaciones de fuente a fuente.

Nuestra DMS Software Reengineering Toolkit podría utilizarse para implementar esto. DMS usa definiciones de lenguaje explícitas para analizar el código fuente de los AST, imprime muy bien los AST al código fuente, proporciona varios tipos de tabla de símbolos, capacidades de control/flujo de datos y proporciona la capacidad de transformación para permitir que uno construya transformadores de código fuente personalizados. DMS tiene many front ends for differenct languages incluyendo C y C++ con preprocesadores completos.

Para realizar su tarea con DMS, usaría el analizador C para analizar todo el código de su sistema (porque debe inspeccionar todos los sitios de llamadas para ver si hay alguna especialización parcial). Debería definir una forma de especificar la evaluación parcial que desea; una forma, como ha sugerido, es escribir una llamada a función con argumentos vinculados a constantes, pero podría generalizar esto a argumentos vinculados a expresiones arbitrarias. Dicha especificación puede analizarse mediante el analizador sintáctico de patrones de DMS, que puede procesar arbitrariamente palabras terminales no legibles, por ejemplo, una llamada a una función: -} Debe aparcar estas especificaciones en algún lugar; quizás como un archivo externo adicional, o como comentarios en o cerca de los sitios de llamadas en cuestión.

Con un análisis de la especificación partial-eval, debe buscar el nombre de la llamada a la función para determinar la función real de interés; está en algún lugar de esa pila de fuentes y la tabla de símbolos lo hará fácil de encontrar. Dado un sitio de llamada con una especialización, la AST para la función identificada se puede replicar y los argumentos pueden sustituirse; utilizando probablemente solo un pequeño número de transformaciones, pero hay que tener cuidado con la captura de un argumento mediante un alcance léxico dentro de la función que se está especializando. Desplazarse puede requerir transformaciones adicionales. Después de gensymming un nuevo nombre y una lista de argumentos abreviados para la función especificada, volvería a insertar su AST cerca del sitio de definición de función original, modificaría el sitio de llamadas de manera adecuada y escupiría los AST modificados. Si desea agregar transformaciones adicionales para desenrollar bucles para casos especiales, o lo que sea que le interese, también es práctico.

DMS se ha utilizado para llevar a cabo transformaciones masivas en C y C++; esto parece "técnicamente" fácil. Existe la pequeña cuestión de familiarizarse con una herramienta como DMS; hay una buena curva de aprendizaje allí.