El uso del modelo poliédrico (también llamado modelo politopo ) dentro de un compilador requiere software para representar los objetos de este marco (conjuntos de puntos con valores enteros en regiones de varios espacios) y realizar operaciones sobre ellos (por ejemplo, probar si el conjunto es vacío).
Para obtener más detalles sobre los objetos y las operaciones en este modelo, y un ejemplo que relaciona el modelo con los programas que se están compilando, consulte la página del modelo poliédrico.
Hay muchos marcos que apoyan el modelo poliédrico . Algunos de estos marcos utilizan una o más bibliotecas para realizar operaciones poliédricas. Otros, en particular Omega, combinan todo en un solo paquete. Algunas bibliotecas de uso común son Omega Library [1] (y una bifurcación más reciente), [2] piplib, [3] [4] PolyLib, [5] [6] PPL, [7] isl , [8] the Cloog generador de código poliédrico, [9] [10] y la biblioteca barvinok para contar soluciones enteras. [11]De estas bibliotecas, PolyLib y PPL se centran principalmente en valores racionales, mientras que las otras bibliotecas se centran en valores enteros. El marco poliédrico de gcc se llama Grafito. [12] Polly [13] proporciona optimizaciones poliédricas para LLVM , y R-Stream [14] ha tenido un mapeador poliédrico desde ca. 2006.
Los marcos poliédricos están diseñados para admitir técnicas de compiladores para el análisis y transformación de códigos con bucles anidados, produciendo resultados exactos para nidos de bucles con subíndices y límites de bucle afines ("Partes de control estático" de los programas). Se pueden usar para representar y razonar sobre ejecuciones (iteraciones) de declaraciones, en lugar de tratar una declaración como un solo objeto que representa las propiedades de todas las ejecuciones de esa declaración. Los marcos poliédricos normalmente también permiten el uso de expresiones simbólicas.
Los marcos poliédricos se pueden utilizar para el análisis de dependencia de matrices, incluido el análisis de alias tradicional y técnicas más avanzadas como el análisis del flujo de datos en matrices o la identificación de dependencias condicionales. También se pueden utilizar para representar la transformación de código y proporcionar funciones para generar el código transformado en un lenguaje de alto nivel. Los sistemas de transformación y generación normalmente pueden manejar bucles anidados imperfectamente.
Para comparar el modelo poliédrico basado en restricciones con enfoques anteriores, como las transformaciones de bucle individual y el enfoque unimodular , considere la cuestión de si podemos paralelizar (ejecutar simultáneamente) las iteraciones del siguiente bucle artificial pero simple: