Alcanzando la definición

En teoría de compiladores , una definición de alcance para una instrucción dada es una instrucción anterior cuya variable objetivo puede alcanzar (ser asignada a) la instrucción dada sin una asignación intermedia. Por ejemplo, en el siguiente código:

d1 : y := 3 d2 : x := y

d1es una definición amplia para d2. Sin embargo, en el siguiente ejemplo:

d1 : y := 3 d2 : y := 4 d3 : x := y

d1ya no es una definición de alcance para d3, porque d2mata su alcance: el valor definido en d1ya no está disponible y no puede alcanzar d3.

El análisis de definiciones de alcance, de nombre similar, es un análisis de flujo de datos que determina estáticamente qué definiciones pueden llegar a un punto determinado del código. Debido a su simplicidad, se utiliza a menudo como ejemplo canónico de análisis de flujo de datos en los libros de texto. El operador de confluencia de flujo de datos utilizado es la unión de conjuntos, y el análisis es de flujo hacia adelante. Las definiciones de alcance se utilizan para calcular cadenas de uso-definición .

Las ecuaciones de flujo de datos utilizadas para un bloque básico dado${\displaystyle S}$para llegar a las definiciones son:

• ${\displaystyle {\rm {REACH}}_{\rm {in}}[S]=\bigcup _{p\in pred[S]}{\rm {REACH}}_{\rm {out}}[p]}$
• ${\displaystyle {\rm {REACH}}_{\rm {out}}[S]={\rm {GEN}}[S]\cup ({\rm {REACH}}_{\rm {in}}[S]-{\rm {KILL}}[S])}$

En otras palabras, el conjunto de definiciones de alcance que entran en${\displaystyle S}$son todas las definiciones de alcance de${\displaystyle S}$los predecesores,${\displaystyle pred[S]}$. ${\displaystyle pred[S]}$consta de todos los bloques básicos que vienen antes${\displaystyle S}$en el gráfico de flujo de control . Las definiciones de alcance que salen de${\displaystyle S}$son todas definiciones de alcance de sus predecesores menos aquellas definiciones de alcance cuya variable es eliminada por${\displaystyle S}$más cualquier nueva definición generada dentro${\displaystyle S}$.

Para una instrucción genérica, definimos la${\displaystyle {\rm {GEN}}}$y${\displaystyle {\rm {MATAR}}}$Se establece de la siguiente manera:

• ${\displaystyle {\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}}$, un conjunto de definiciones disponibles localmente en un bloque básico
• ${\displaystyle {\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}}$, un conjunto de definiciones (no disponibles localmente, sino en el resto del programa) eliminadas por definiciones en el bloque básico.

dónde${\displaystyle {\rm {DEFS}}[y]}$es el conjunto de todas las definiciones que se asignan a la variable${\displaystyle y}$. Aquí${\displaystyle d}$es una etiqueta única adjunta a la instrucción de asignación; por lo tanto, el dominio de valores para alcanzar definiciones son estas etiquetas de instrucción.

El cumplimiento de la definición se suele calcular mediante un algoritmo iterativo de lista de tareas.

Entrada: grafo de flujo de control CFG = (Nodos, Aristas, Entrada, Salida)

// Inicializar para todos los nodos CFG n en N , OUT [ n ] = emptyset ; // se puede optimizar mediante OUT[n] = GEN[n];// agregar todos los nodos al conjunto cambiado // N son todos los nodos en el grafo, Cambiado = N ;// Iterar mientras ( Changed != emptyset ) { elegir un nodo n en Changed ; // eliminarlo del conjunto cambiado Changed = Changed - { n };// inicializar IN[n] como vacío IN [ n ] = emptyset ;// calcular IN[n] a partir de OUT[p] de los predecesores para todos los nodos p en los predecesores ( n ) IN [ n ] = IN [ n ] Unión OUT [ p ];oldout = OUT [ n ]; // guardar old OUT[n] // actualizar OUT[n] usando la función de transferencia f_n () OUT [ n ] = GEN [ n ] Union ( IN [ n ] - KILL [ n ]);// ¿Algún cambio en OUT[n] en comparación con el valor anterior? if ( OUT [ n ] changed ) // comparar oldout vs. OUT[n] { // si es así, agregar todos los sucesores de n al conjunto cambiado para todos los nodos s en successors ( n ) Changed = Changed U { s }; } }

• eliminación de código muerto
• Movimiento de código invariante de bucle
• Usos accesibles
• Formulario de asignación única estática

• Aho, Alfred V.; Sethi, Ravi y Ullman, Jeffrey D. (1986). Compiladores: Principios, técnicas y herramientas . Addison Wesley. ISBN 0-201-10088-6.
• Appel, Andrew W. (1999). Modern Compiler Implementation in ML . Cambridge University Press. ISBN 0-521-58274-1.
• Cooper, Keith D. y Torczon, Linda. (2005). Ingeniería de un compilador . Morgan Kaufmann. ISBN 1-55860-698-X.
• Muchnick, Steven S. (1997). Diseño e implementación avanzados de compiladores . Morgan Kaufmann. ISBN 1-55860-320-4.
• Nielson F., HR Nielson; , C. Hankin (2005). Principios del análisis de programas . Springer. ISBN 3-540-65410-0.