Repositorio Institucional de Documentos

Proyecto Fin de Carrera de Ingenier´ıa en Inform´atica DESARROLLO DE FASES DE COMPILACI ´ ON PARA DESCUBRIR EL TIEMPO DE EJECUCI ´ ON DE PEOR CASO Marta L´opez Ara Director: Juan Segarra Flor ´ Area de Arquitectura y Tecnolog´ıa de Computadores Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza Septiembre 2011 Curso 2010 / 2011 Agradecimientos Una vez llegado al final de este proyecto, me gustar´ıa expresar mi agradecimiento a todas aquellas personas que de una manera u otra han contribuido a su realizaci´on. En primer lugar a mi director de proyecto, Juan Segarra Flor, por conseguir que llegara hasta aqu´ı gracias a sus continuas explicaciones, su apoyo y su confianza depositada en m´ı. A Ra´ul por su inestimable ayuda, paciencia, tranquilidad, por estar ah´ı cuando las fuerzas empiezan a flaquear y por infundir el color necesario para seguir trabajando cuando se ve todo de negro. A mi padre y mi madre, por el apoyo, cari˜no y comprensi´on que me han dado durante todos estos a˜nos. A mis abuelos, por su amor incondicional. A todos mis amigos de la universidad, por todos estos a˜nos compartidos juntos que nunca olvidar´e. A mis amigos: compa˜neros de la escuela de idiomas, postgrado, monitores de tiempo libre y alguno m´as que me puedo dejar en el tintero, porque gracias a su amistad me han aportado algo m´as que buenos momentos. ¡¡Muchas gracias a todos!! Desarrollo de fases de compilaci´on para descubrir el tiempo de ejecuci´on de peor caso RESUMEN Los dispositivos con requisitos de tiempo real son cada vez m´as utilizados, por ejemplo en autom´oviles (e.g. ABS), aeron´autica, electrodom´esticos, etc. Para poder planificar los requisitos temporales de cualquier tarea, el primer paso es conocer (una cota superior de) su tiempo de ejecuci´on en el peor caso (worst case execution time o WCET). Este c´alculo depende de factores hardware y software, como por ejemplo de las memorias cache y del compilador utilizado, y debe conocerse previamente a su ejecuci´on. Adem´as, requiere informaci´on que maneja internamente el compilador pero no queda expl´ıcita en el ejecutable final, con lo que recuperarla es muy complejo. Cuanto m´as ajustada sea la cota superior obtenida, mejor se aprovechar´an los recursos del sistema, aumentando as´ı la planificabilidad del mismo. Por todo lo anterior, se ha realizado este proyecto de fin de carrera, cuyo objetivo principal ha sido la implementaci´on de una serie de pasos (fases en la terminolog´ıa usual de compiladores) que obtengan la informaci´on necesaria directamente en el proceso de compilaci´on: re´usos de bloques de memoria y n´umero m´aximo de iteraciones en bucles. Para ello se ha utilizado la infraestructura de compilaci´on Low Level Virtual Machine (LLVM). Se han creado dos bibliotecas para ayudar al c´alculo de la cota superior de los procesos. Estas bibliotecas van a sacar a relucir los accesos a memoria que existen, pudiendo as´ı saber el re´uso de variables y constantes, tanto temporal como espacial, y el n´umero de veces que se ejecuta cada bucle de instrucciones como m´aximo. En particular: La biblioteca libmarcarLoadsStores localiza en el c´odigo intermedio de LLVM los accesos a memoria que existen (loads y stores) a˜nadi´endoles los metadatas de depuraci´on para su posterior reconocimiento con sus correspondientes instrucciones en el fichero que contiene el c´odigo ensamblador ARM. La biblioteca libbuclesReusos analiza en profundidad el c´odigo LLVM Intermediate Repesentation (IR) en busca de iteraciones y subiteraciones, indicando en fichero ARM el m´aximo n´umero de veces que se puede ejecutar un bloque b´asico de instrucciones, siempre que se sepa este dato en tiempo de compilaci´on. Adem´as, recoge los datos de los accesos a memoria, para poder identificar el re´uso espacial y temporal, la variable o constante a la cual se refiere, y el desplazamiento que existe. ´ Indice general 1. Introducci´on 1 1.1. Motivaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Contexto de realizaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4. Herramientas utilizadas . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.5. Fases del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.6. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Planificaci´on 6 2.1. Ciclo de vida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2. Planificaci´on del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Conceptos 8 3.1. Funcionamiento del compilador LLVM . . . . . . . . . . . . . . . . . 8 3.2. Bucles y re´usos en c´odigo ARM . . . . . . . . . . . . . . . . . . . . . 10 4. Desarrollo 13 4.1. An´alisis y dise˜no . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1.1. Alcance del proyecto . . . . . . . . . . . . . . . . . . . . . . . 13 4.1.2. An´alisis del proyecto . . . . . . . . . . . . . . . . . . . . . . . 14 4.1.3. Dise˜no del proyecto . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2. Implementaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.1. Cuenta de iteraciones . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.2. Marcaci´on de loads y stores . . . . . . . . . . . . . . . . . . . 16 4.2.3. Localizaci´on de re´usos espaciales . . . . . . . . . . . . . . . . . 17 4.2.4. Localizaci´on de re´usos temporales . . . . . . . . . . . . . . . . 20 4.3. Pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5. Conclusiones 22 5.1. Dificultades encontradas . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.2. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.3. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.4. Valoraci´on personal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 ´ INDICE GENERAL iv A. LLVM Intermediate Representation 26 A.1. Visi´on general del juego de instrucciones . . . . . . . . . . . . . . . . 26 A.2. Tipos primarios y derivados . . . . . . . . . . . . . . . . . . . . . . . 27 A.3. SSA form (PHINODE) . . . . . . . . . . . . . . . . . . . . . . . . . . 28 A.4. Acceso a direcciones de memoria . . . . . . . . . . . . . . . . . . . . . 29 A.5. Lectura y escritura en memoria . . . . . . . . . . . . . . . . . . . . . 30 A.6. Ejemplo completo comentado . . . . . . . . . . . . . . . . . . . . . . 31 B. Gu´ıa de comandos LLVM 32 C. Pruebas 35 C.1. Cuenta de iteraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 C.2. Marcaci´on de loads y stores . . . . . . . . . . . . . . . . . . . . . . . 47 C.3. Localizaci´on de re´usos temporales y espaciales . . . . . . . . . . . . . 51 D. Manual de Uso 69 D.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 D.2. Requerimientos Software . . . . . . . . . . . . . . . . . . . . . . . . . 69 D.3. Compilaci´on de las bibliotecas . . . . . . . . . . . . . . . . . . . . . . 70 D.4. Compilaci´on de los ficheros a analizar . . . . . . . . . . . . . . . . . . 71 D.5. Ficheros Resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Bibliograf´ıa 76 ´ Indice de figuras 2.1. Ciclo de vida incremental. . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2. Diagrama de Gantt correspondiente a las fases de desarrollo . . . . . 7 3.1. Arquitectura y m´odulos LLVM . . . . . . . . . . . . . . . . . . . . . 9 3.2. C´odigo C de stores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3. C´odigo LLVM de stores . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4. C´odigo ARM de stores . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.5. C´odigo ejemplo en C . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.6. C´odigo ejemplo en ARM . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.7. C´odigo ejemplo final ARM . . . . . . . . . . . . . . . . . . . . . . . . 12 4.1. Optimizaci´on indvars ........................... 16 4.2. Ejemplo de cuenta de iteraciones . . . . . . . . . . . . . . . . . . . . 16 4.3. Ejemplo de debug en loads y stores . . . . . . . . . . . . . . . . . . . 17 4.4. Ejemplo de metadatas . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.5. Ejemplo de puntero con varios par´ametros . . . . . . . . . . . . . . . 18 4.6. Ejemplo de load con m´ultiples variables . . . . . . . . . . . . . . . . . 18 4.7. Ejemplo de store con una variable . . . . . . . . . . . . . . . . . . . . 18 4.8. Ejemplo de incremento constante . . . . . . . . . . . . . . . . . . . . 19 4.9. Ejemplo de incremento variable . . . . . . . . . . . . . . . . . . . . . 19 4.10. Ejemplo de re´uso temporal . . . . . . . . . . . . . . . . . . . . . . . . 20 4.11. Ejemplo de store de pila . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.12. Ejemplo de load de constante . . . . . . . . . . . . . . . . . . . . . . 20 A.1. C´odigo ejemplo en C . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A.2. C´odigo ejemplo comentado en LLVM IR . . . . . . . . . . . . . . . . 31 C.1. C´odigo del fichero bucle.c . . . . . . . . . . . . . . . . . . . . . . . . 36 C.2. Bucle anidado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 C.3. Bucles con incremento constante . . . . . . . . . . . . . . . . . . . . . 37 C.4. Bucle con incremento variable . . . . . . . . . . . . . . . . . . . . . . 37 C.5. Bucles con decremento constante . . . . . . . . . . . . . . . . . . . . 37 C.6. Fichero bucle.ll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 C.7. Salida por pantalla al compilar bucle.c . . . . . . . . . . . . . . . . . 41 C.8. Parte del fichero bucle.arm.opt.s que nos muestra la salida para los bucles anidados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 ´ INDICE DE FIGURAS vi C.9. Parte del fichero bucle.arm.opt.s que nos muestra la salida para distintos bucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 C.10.Parte del fichero bucle2.c . . . . . . . . . . . . . . . . . . . . . . . . . 44 C.11.Parte del fichero bucle2.arm.opt.s . . . . . . . . . . . . . . . . . . . . 44 C.12.Parte del fichero bucle3.c . . . . . . . . . . . . . . . . . . . . . . . . . 45 C.13.Parte del fichero bucle3.arm.opt.s . . . . . . . . . . . . . . . . . . . . 45 C.14.Ejemplo de bucle con instrucci´on do . . . . . . . . . . . . . . . . . . . 45 C.15.Tranformaci´on de bucle con instrucci´on do en lenguaje ARM . . . . . 46 C.16.Ejemplo de prueba para marcaci´on de loads y stores . . . . . . . . . . 47 C.17.Salida por pantalla al compilar el fichero stores.c . . . . . . . . . . . . 48 C.18.Fichero storesMarcado.ll . . . . . . . . . . . . . . . . . . . . . . . . . 49 C.19.Fichero stores.ll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 C.20.Parte del fichero stores.arm.opt.s . . . . . . . . . . . . . . . . . . . . 51 C.21.Fichero pruebaStores.c . . . . . . . . . . . . . . . . . . . . . . . . . . 52 C.22.Fichero pruebaStores.arm.opt.s . . . . . . . . . . . . . . . . . . . . . 55 C.23.Fichero jfdctint.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 C.24.Fichero jfdctint.arm.opt.s . . . . . . . . . . . . . . . . . . . . . . . . . 68 D.1. Ejemplo de compilaci´on de bibliotecas . . . . . . . . . . . . . . . . . 70 D.2. Comandos para compilar las bibliotecas . . . . . . . . . . . . . . . . . 70 D.3. Contenido de la carpeta . . . . . . . . . . . . . . . . . . . . . . . . . 71 D.4. C´odigo ejemplo de Makefile . . . . . . . . . . . . . . . . . . . . . . . 73 D.5. Makefile de ”Prueba1” . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Cap´ıtulo 1 Introducci´on En este cap´ıtulo se comentar´an los aspectos m´as generales del presente Proyecto Fin de Carrera, entre los que se encuentran: la motivaci´on para la consecuci´on del mismo, su contexto de realizaci´on, los objetivos definidos en la propuesta, las herramientas que se han utilizado durante su elaboraci´on, las fases en las que se ha dividido el trabajo y, por ´ultimo, una breve explicaci´on de la estructura del documento. 1.1. Motivaci´on A la hora de elegir un proyecto, fueron varios los motivos que me hicieron decantarme por ´este. Para empezar, el hecho de contribuir a la utilizaci´on de herramientas de software libre, en particular el proyecto Low Level Virtual Machine (LLVM). Otro aspecto interesante fue la posibilidad de ampliar mis conocimientos de ingenier´ıa del software, as´ı como de los lenguajes ensamblador y C++. Tambi´en consider´e interesante para completar mi formaci´on el hecho de incorporarme a un proyecto de investigaci´on y tener que adaptarme a ´el y a las necesidades del mismo, puesto que en mi futura vida laboral es una situaci´on m´as que probable. Y, por supuesto, el poner en pr´actica los conocimientos adquiridos durante la carrera, que considero debe ser el principal objetivo de cualquier PFC. 1.2. Contexto de realizaci´on El presente proyecto de fin de carrera se enmarca en temas de investigaci´on llevados a cabo dentro del grupo de Arquitectura de Computadores (gaZ) de la Universidad de Zaragoza. Parte de dicha investigaci´on consiste en desarrollar metodologias para analizar el tiempo de ejecuci´on en el peor caso (WCET) y proponer componentes hardware alternativos a los existentes cuyo an´alisis sea factible. Para analizar el WCET en un sistema de tiempo real son necesarios par´ametros como el m´aximo n´umero de iteraciones de cada bucle. En caso de que el sistema 1.3 Objetivos 2 final disponga de cache de datos, tambi´en resulta imprescindible conocer el re´uso de datos del programa a analizar. En este PFC se obtienen dichos par´ametros desde dentro del compilador, lo cual facilita el posterior an´alisis y proporciona mayor independencia respecto al repertorio de instrucciones final. 1.3. Objetivos Los objetivos principales del proyecto son los siguientes: 1. Estudio del funcionamiento interno del compilador LLVM [1] 2. Localizaci´on de bucles y variables de iteraci´on en c´odigo LLVM 3. Backtracking de variables de iteraci´on para obtener el m´aximo n´umero de iteraciones en bucles cuando sea posible 4. Identificaci´on de re´uso espacial y temporal b´asico en accesos a memoria en c´odigo LLVM 5. Generaci´on de ensamblador ARM etiquetado con la informaci´on anterior (m´aximo n´umero de iteraciones en bucles e informaci´on de re´uso en accesos a memoria) 1.4. Herramientas utilizadas Para realizar el desarrollo software habr´ıa bastado simplemente con un editor de texto y el entorno de desarrollo implementado por LLVM. Sin embargo, ha habido muchas otras herramientas que han sido muy ´utiles durante todo el desarrollo. ´ Estas han sido las herramientas utilizadas: Gedit 2.30.4 [2]:´ Este fue el editor elegido para codificar y manejar los diferentes tipos de archivos. Destaca por su simpleza y rapidez, y por sus m´ultiples funciones y plugins que ofrece a la hora de desarrollar. Y, sobre todo, por poder manejar a la vez m´ultiples tipos de archivos (C, C++, ensamblador ARM, LLVM IR) con facilidad. GCC 4.5 [3]: Compilador de C/C++ del proyecto GNU/Linux. Usado para compilar las bibliotecas. LLVM 2.8 [1]: Infraestructura de compilaci´on, junto con todas sus herramientas llvm-gcc, llvm-dis, llc, opt. Estas herramientas permiten compilar programas, pasar de un c´odigo a otro y hacer pasadas de an´alisis y compilaci´on sobre el c´odigo. 3.1 Funcionamiento del compilador LLVM 9 Figura 3.1: Arquitectura y m´odulos LLVM En este proyecto nos vamos a basar principalmente en este lenguaje para analizar los diferentes tipos de instrucciones, para calcular el n´umero de iteraciones en los bucles y los re´usos tanto temporales como espaciales. Una vez calculados y localizados se escribir´an en el c´odigo ARM correspondiente. Para entenderlo mejor, se va a mostrar el mismo c´odigo de un bucle con dos stores, tanto en lenguaje C como su transformaci´on en lenguaje LLVM IR. En la Figura 3.2 vemos c´omo ser´ıa el c´odigo en lenguaje C, en la Figura 3.3 vemos c´omo ser´ıa el mismo c´odigo en lenguaje LLVM IR, y para terminar en la Figura 3.4 vemos su transformaci´on en lenguaje ensamblador ARM. for (varBucle=0;varBucle<Tam;varBucle++) { Vector1[varBucle]=varBucle*5; Vector2[varBucle]=varBucle*5; } Figura 3.2: C´odigo C de stores En el c´odigo representado en la Figura 3.3, bb indica la etiqueta de un bloque b´asico que contiene todas las intrucciones siguientes del ejemplo. La instrucci´on getelementptr devuelve un puntero con la direcci´on de memoria. Las instrucciones add ymul son la suma y la multiplicaci´on en c´odigo LLVM, mientras que br es el salto. La instrucci´on store es la instrucci´on str en c´odigo ensamblador ARM. 3.2 Bucles y re´ usos en c´ odigo ARM 10 bb: ; preds = %bb, %bb.nph9 %varBucle.08 = phi i32 [ 0, %bb.nph9 ], [ %tmp1, %bb ] %scevgep12 = getelementptr [5000 x i32]* %Vector1, i32 0, i32 %varBucle.08 %scevgep13 = getelementptr [5000 x i32]* %Vector2, i32 0, i32 %varBucle.08 %tmp = mul i32 %varBucle.08, 5 store i32 %tmp, i32* %scevgep12, align 4 store i32 %tmp, i32* %scevgep13, align 4 %tmp1 = add nsw i32 %varBucle.08, 1 %exitcond11 = icmp eq i32 %tmp1, 5000 br i1 %exitcond11, label %bb3, label %bb Figura 3.3: C´odigo LLVM de stores .LBB0_1: @ %bb @ =>This Inner Loop Header: Depth=1 str r0, [r2], #4 str r0, [r1], #4 add r0, r0, #5 cmp r0, r3 bne .LBB0_1 @ BB#2: @ %bb.bb3_crit_edge add lr, sp, #1, 18 @ 16384 mov r4, #226, 30 @ 904 orr r4, r4, #1, 20 @ 4096 mov r5, sp add r6, lr, #226, 28 @ 3616 ldr r7, .LCPI0_0 Figura 3.4: C´odigo ARM de stores 3.2. Bucles y re´usos en c´odigo ARM El c´odigo ARM es el lenguaje ensamblador propio de la arquitectura ARM. El c´odigo escrito en lenguaje ensamblador es complejo ya que es una reprensentaci´on del lenguaje m´aquina, con instrucciones, registros y posiciones de memoria del procesador. Al tratarse de un nivel tan bajo y tratar con registros de la m´aquina es muy dif´ıcil poder ver con claridad las iteraciones de los bucles y re´usos mirando directamente el c´odigo ARM. El siguiente sencillo ejemplo en lenguaje C, Figura 3.5, nos permitir´a explicar a que nos referimos, mostrando bucles y re´usos espaciales. En el programa de ejemplo podemos ver que hay dos vectores y un bucle que se va incrementando de uno en uno. Dentro del bucle vemos que se produce una escritura en cada vector en la posici´on “i” que es la variable de iteraci´on. Tambi´en vemos que el bucle se repetir´a cinco mil veces. Sabemos, por tanto, que se van a producir re´usos espaciales en los dos vectores ya que se accede a una posici´on del vector que se va incrementando de manera constante a lo largo del bucle. 3.2 Bucles y re´ usos en c´ odigo ARM 11 #include <stdio.h> #define Tam 5000 int main() { int i=0; int A[Tam]; int B[Tam]; for (i=0;i<Tam;i++) { A[i]=i*5; B[i]=i*5; } } Figura 3.5: C´odigo ejemplo en C Sin embargo al compilarlo a c´odigo ARM, esa informaci´on es muy dif´ıcil de ver, como se puede observar en la Figura 3.6. @ BB#0: @ %bb.nph9 stmdb sp!, {r4, r5, r6, r7, r8, lr} sub sp, sp, #113, 26 @ 7232 sub sp, sp, #2, 18 @ 32768 add lr, sp, #1, 18 @ 16384 mov r0, #0 mov r1, sp add r2, lr, #226, 28 @ 3616 mov r3, #106, 30 @ 424 orr r3, r3, #6, 20 @ 24576 .LBB0_1: @ %bb @ =>This Inner Loop Header: Depth=1 str r0, [r2], #4 str r0, [r1], #4 add r0, r0, #5 cmp r0, r3 bne .LBB0_1 @ BB#2: @ %bb.bb3_crit_edge add lr, sp, #1, 18 @ 16384 mov r4, #226, 30 @ 904 orr r4, r4, #1, 20 @ 4096 mov r5, sp add r6, lr, #226, 28 @ 3616 ldr r7, .LCPI0_0 Figura 3.6: C´odigo ejemplo en ARM 3.2 Bucles y re´ usos en c´ odigo ARM 12 Podemos ver que hay dos stores (instrucciones str) dentro de un bloque que se repite (.LBB0 1), con un salto (bne) con comparaci´on (cmp). El bloque pertenece a un bucle, pero no podemos conocer f´acilmente los re´usos de esos stores ni las repeticiones que har´a dicho bloque. El objetivo del proyecto es precisamente mostrar claramente en el c´odigo ARM este tipo de informaci´on de forma clara y transparente. La siguiente figura muestra el resultado final en c´odigo ARM despu´es de pasar las bibliotecas. .LBB0_1: @ %bb @ Numero de vueltas=5000 @ =>This Inner Loop Header: Depth=1 str r0, [r2], #4 @ Store var "A". Reuso espacial. Var iteracion "i". Desplazamiento con "stride" 1 str r0, [r1], #4 @ Store var "B". Reuso espacial. Var iteracion "i". Desplazamiento con "stride" 1 add r0, r0, #5 cmp r0, r3 bne .LBB0_1 @ BB#2: @ %bb.bb3_crit_edge add lr, sp, #1, 18 @ 16384 mov r4, #226, 30 @ 904 orr r4, r4, #1, 20 @ 4096 mov r5, sp add r6, lr, #226, 28 @ 3616 ldr r7, .LCPI0_0 @ Load Constante .LCPI0_0 Figura 3.7: C´odigo ejemplo final ARM Cap´ıtulo 4 Desarrollo Este cap´ıtulo describe c´omo se llev´o a cabo el desarrollo del proyecto y las decisiones m´as importantes tomadas durante el mismo. 4.1. An´alisis y dise˜no Durante toda la fase de an´alisis y dise˜no, se trabaj´o estrechamente con el profesor Juan Segarra Flor para definir bien los siguientes puntos: Alcance del Proyecto: Se defini´o, describi´o y prepar´o el escenario de implementaci´on. An´alisis del Proyecto: Se especificaron las necesidades actuales del proyecto, y el encaminamiento para el futuro de la aplicaci´on. Dise˜no del Proyecto: Se describi´o su soluci´on y las actividades de implementaci´on y testeo que se iban a hacer. El objetivo de esta fase era poner en firme cu´ales eran exactamente las especificaciones del proyecto, la entrega y la preparaci´on de la implementaci´on. 4.1.1. Alcance del proyecto Se empez´o a trabajar para determinar el alcance de la implementaci´on del proyecto. En este paso, se determin´o lo que cubrir´ıa el proyecto, y c´omo se gestionar´ıa el tiempo para ello. El resultado final de esta fase, fue la generaci´on de dos documentos: La propuesta del proyecto, que contiene el alcance descrito para el mismo. Una primera planificaci´on de la distribuci´on del proyecto. 4.1 An´ alisis y dise˜ no 14 4.1.2. An´alisis del proyecto En la fase del an´alisis se recogieron los requisitos necesarios. Para esto, se qued´o varios d´ıas con el profesor Juan Segarra Flor, y as´ı se delimitaron las necesidades halladas hasta el momento, las cuales cambiar´ıan muy poco en todo el proceso. Los requerimientos m´as importantes fueron: Localizar los bucles dentro de un c´odigo fuente. Calcular el n´umero de iteraciones m´aximo, en tiempo de compilaci´on, de cada bloque de instrucciones. Hallar el re´uso espacial. Encontrar el re´uso temporal. Mostrar todo lo anterior en el fichero ensamblador de ARM. 4.1.3. Dise˜no del proyecto Posteriormente, una vez establecidos los requisitos y hecha la propuesta, se dise˜n´o la biblioteca y sus dependencias. Se llev´o a cabo un mapeo de las tecnolog´ıas disponibles para su ejecuci´on y un profundo estudio de la herramienta LLVM. Se siguieron haciendo reuniones para asegurar si el camino llevado hasta el momento era el correcto y para resolver dudas. Se fij´o que hab´ıa que realizar una biblioteca que leyera el c´odigo intermedio LLVM IR y que us´andola mediante una pasada de an´alisis sobre un programa pudi´eramos leer los datos de sus instrucciones. As´ı se tendr´ıa acceso a la secuencia de instrucciones y podr´ıamos analizarlas en profundidad. Se estableci´o como hab´ıa que realizar dicha biblioteca y las opciones del makefile. Se describieron los archivos makefile, tanto de la biblioteca como de los programas a analizar. Se establecieron tambi´en los comandos para poder realizar una pasada de an´alisis-optimizaci´on usando la biblioteca sobre el c´odigo LLVM IR. Se estudiaron todos los par´ametros de optimizaci´on de LLVM y los diferentes niveles de optimizaci´on a la hora de compilar. Se realizaron varios ejemplos b´asicos de bibliotecas que realizaban un recorrido b´asico sobre las instrucciones LLVM IR. Se comprob´o as´ı que ten´ıamos acceso a dichas instrucciones y sus par´ametros. Se fijaron tambi´en los diferentes tipos de programas-pruebas en C que habr´ıa que realizar para probar nuestra biblioteca: diferentes tipos de bucles (while, for, etc), acceso a vectores sobre la variable de iteraci´on en los bucles y varios programas completos de prueba. 4.2 Implementaci´ on 15 Es gracias a esta fase y a la de an´alisis, que la fase de implementaci´on ha sido m´as corta de lo que se esperaba, teniendo una duraci´on final esta ´ultima de dos meses a tiempo parcial, como se puede ver en la Secci´on 2.2. 4.2. Implementaci´on Fue requisito del proyecto que el lenguaje de desarrollo fuese C++, ya que es el lenguaje del c´odigo fuente de las bibliotecas de LLVM. Para poder entender bien la implementaci´on, se va a dividir esta secci´on en tres partes. En la primera, se va a explicar c´omo se construy´o la biblioteca para la cuenta de iteraciones de bloques. En la segunda, se mostrar´a c´omo se cre´o la biblioteca libMarcarLoadsStores. Para finalizar, se detallar´a c´omo se pasaron los re´usos temporales y espaciales marcados en el c´odigo LLVM IR al fichero ensamblador ARM, y varios detalles adicionales que se hicieron para complementar el trabajo realizado. 4.2.1. Cuenta de iteraciones Despu´es de estudiar el funcionamiento de LLVM y su API se decidi´o realizar primero el conteo de iteraci´on de los bucles. Para ello, hubo que realizar una biblioteca, ya que se ´esta se puede cargar en una pasada de an´alisis. Por consiguiente, se cre´o la biblioteca libcuentaBucles, que despu´es se pasar´ıa a llamar libbuclesReusos. Para poder utilizarla, hubo que usar la herramienta “opt” que realiza pasadas de an´alisis y optimizaci´on sobre c´odigo LLVM IR, y a la que se le pueden a˜nadir muchos par´ametros seg´un la necesidad que se tenga. Para hallar el n´umero de veces que se pasa por un bloque de instrucciones, fue de gran ayuda la clase “LoopInfo” de la API. Gracias a ella, se pod´ıa acceder a la informaci´on de cada bucle. Dentro de esa informaci´on, destacan los siguientes datos: Etiqueta del bloque de instrucciones N´umero de vueltas Variable de iteraci´on Adem´as de cada una de las instrucciones incluidas en cada bloque. De gran importancia, fue la optimizaci´on “indvars”. Gracias a esto se pudieron convertir todos los bucles en bucles naturales con variable de iteraci´on can´onica, es decir, que todos empezaran en cero y fueran increment´andose de uno en uno, como se muestra en la siguiente figura. 4.2 Implementaci´ on 16 for (i = 10; i < 5000; i+=2) => for (i = 0; i < 2495; i++) for (i = 7; i*i < 1000; i++) => for (i = 0; i != 25; i++) Figura 4.1: Optimizaci´on indvars Con esto, ya se pod´ıa saber las iteraciones que se producir´ıan en cada bucle y su etiqueta. El nombre de las etiquetas en c´odigo LLVM IR y en c´odigo ARM son id´enticos, por lo cual, se pod´ıa escribir en el fichero ARM el n´umero de vueltas calculado. En la siguiente figura podemos ver un ejemplo de bucles anidados: .LBB0_1: @ %bb2.preheader @ Numero de vueltas=5000 @ =>This Loop Header: Depth=1 @ Child Loop BB0_2 Depth 2 mov r7, #0 .LBB0_2: @ %bb1 @ Numero de vueltas=3000 @ Parent Loop BB0_1 Depth=1 @ => This Inner Loop Header: Depth=2 mov r1, r7 mov r0, r5 add r7, r7, #1 bl printf cmp r7, r6 bne .LBB0_2 Figura 4.2: Ejemplo de cuenta de iteraciones 4.2.2. Marcaci´on de loads y stores El siguiente paso fue localizar los re´usos, tanto temporales como espaciales, en el c´odigo LLVM IR. Gracias a la biblioteca creada se pod´ıa acceder a las instrucciones y comprobar si ´estas eran loads o stores. Tambi´en, se pod´ıa saber cu´al era la variable que se cargaba en cada momento, siempre hablando en tiempo de compilaci´on, y si ´esta se incrementaba con la variable de iteraci´on. Pero como el objetivo del proyecto era localizarlos en el ARM aqu´ı estuvo el primer gran problema. El c´odigo LLVM IR usa nombres para variables mientras que el c´odigo ARM s´olo usa los registros (r1, r2, r3, etc). Por este motivo, no se pod´ıa saber qu´e instrucci´on ARM correspond´ıa con cada load o store localizado en el c´odigo LLVM IR. Primero se pens´o en a˜nadir anotaciones o comentarios en las instrucciones del c´odigo LLVM para que al compilarlo a c´odigo ARM estuvieran all´ı en las 4.2 Implementaci´ on 17 instrucciones correspondientes, pero los comentarios se eliminaban en el proceso de traducci´on. Despu´es de mucho investigar, se comprob´o que la informaci´on del tipo “metadata” de LLVM (Figura 4.3) dise˜nada para DEBUG, y disponible desde la versi´on 2.7 de LLVM, se transformaba en comentarios en el c´odigo ARM (Figura 4.4) a la hora de compilar. Escribiendo un metadata en una instrucci´on LLVM se pod´ıa saber con qu´e instrucci´on o instrucciones se correspond´ıa en el c´odigo ARM. %tmp2 = load i32* %scevgep, align 4, !dbg !7 %tmp4 = load i32* %scevgep10, align 4, !dbg !8 Figura 4.3: Ejemplo de debug en loads y stores declare i32 @printf(i8* nocapture, ...) nounwind !1 = metadata !{i32 524329, metadata !"load", null, null} !2 = metadata !{i32 524329, metadata !"store", null, null} !3 = metadata !{i32 524299, null, i32 6, i32 0, metadata !1, i32 0} !4 = metadata !{i32 524299, null, i32 6, i32 0, metadata !2, i32 0} !5= metadata !{i32 0, i32 0, metadata !4, null} !6= metadata !{i32 1, i32 0, metadata !4, null} !7= metadata !{i32 0, i32 0, metadata !3, null} !8= metadata !{i32 1, i32 0, metadata !3, null} Figura 4.4: Ejemplo de metadatas As´ı pues, hab´ıa que escribir los metadatas en los loads y stores del c´odigo LLVM IR y despu´es compilarlo para acceder a dicha informaci´on en el ARM. Como hab´ıa que marcar los loads y stores, y despu´es, compilar para obtener el ARM con la informaci´on necesaria para poder relacionar las instrucciones, se opt´o por crear dos bibliotecas en vez de una. Por este motivo, se desarroll´o una nueva biblioteca llamada libmarcarLoadsStores que se encargar´ıa de escribir los metadatas correspondientes en los loads y stores del c´odigo LLVM. As´ı, cuando se compilara el c´odigo pas´andole esta biblioteca, ya tendr´ıamos el c´odigo LLVM con metadatas y faltar´ıa pasarlo a c´odigo ARM. Es entonces, cuando se decidi´o que la biblioteca llamada libcuentaBucles, mencionada anteriormente, tambi´en fuera la encargada de realizar todo el proceso de comprobar los diferentes re´usos de los loads y stores (temporal y espacial), y pas´o a llamarse libbuclesReusos. 4.2.3. Localizaci´on de re´usos espaciales El re´uso espacial que se ha calculado en este proyecto se centra en el acceso a diferentes posiciones de vectores, matrices o estructuras, en especial, cuando estas posiciones dependen directa o indirectamente de la variable de iteraci´on de los bucles. 4.2 Implementaci´ on 18 Ya que se hab´ıa calculado el n´umero de iteraciones en los bucles y se ten´ıa la variable de iteraci´on, se opt´o por continuar con la localizaci´on de re´usos espaciales. Para continuar, lo primero que hab´ıa que entender era lo que significaba cada par´ametro de las instrucciones, en particular las de loads y stores. Estas instrucciones tienen dos par´ametros. Uno es la variable o el valor de lectura, o de escritura, dependiendo de si es un load o un store. El otro par´ametro es, en el caso de los re´usos espaciales, un puntero a una posici´on de un vector. Dicho puntero es el que nos interesaba analizar con profundidad. Los punteros tambi´en tienen varios par´ametros (ver Figura 4.5). El primero es el vector al que se quiere acceder, y los dem´as par´ametros son variables, instrucciones o valores que nos indican los ´ındices de desplazamiento sobre ´este. Nos interesaba saber el nombre de la variable del vector y los par´ametros de desplazamiento. El principal objetivo aqu´ı era saber cu´antos par´ametros ten´ıa cada puntero de los loads y stores. Si ten´ıa m´as de un par´ametro, est´abamos ante un vector multidimensional o una estructura. %scevgep = getelementptr [100 x [100 x i32]]* @A, i32 0, i32 %i.119, i32 %k.016 %scevgep25 = getelementptr [100 x [100 x i32]]* @B, i32 0, i32 %k.016, i32 %j.117 Figura 4.5: Ejemplo de puntero con varios par´ametros Aunque no fue un requisito inicial, se prefiri´o dar una explicaci´on m´as detallada de la instrucci´on a analizar. Por lo cual, adem´as de avisar que hab´ıa re´uso espacial, a partir de ahora, tambi´en se indicar´ıa si era de una o m´ultiples variables, y el nombre de las mismas o el valor, seg´un el caso, como se muestra en la figura Figura 4.6. ldr r6, [r4, -r12] @ Load var "A". Reuso espacial. Multiples variables "i" "k" ldr r7, [r2], #400 @ Load var "B". Reuso espacial. Multiples variables "k" "j" Figura 4.6: Ejemplo de load con m´ultiples variables En el caso de que fuera una sola variable la del desplazamiento sobre el puntero, se acord´o que se mostrar´ıa el “stride”, es decir, la separaci´on entre una posici´on y la siguiente a la que se accediera, siempre expresado en elementos del tipo declarado en el vector. str r0, [r2], #4 @ Store var "A". Reuso espacial. Var iteracion "i". Desplazamiento con "stride" 1 str r0, [r1], #4 @ Store var "B". Reuso espacial. Var iteracion "i". Desplazamiento con "stride" 1 Figura 4.7: Ejemplo de store con una variable