Definición de alcanzar

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

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

d1es una definición que alcanza el alcance de d2. En el siguiente ejemplo, sin embargo:

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

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

Como análisis

El operador de confluencia de flujo de datos, que tiene un nombre similar, es un análisis de flujo de datos que determina de forma estática qué definiciones pueden alcanzar un punto determinado en el código. Debido a su simplicidad, se utiliza a menudo como ejemplo canónico de un 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 el flujo hacia adelante. Las definiciones de alcance se utilizan para calcular cadenas de uso y definición .

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

• ${\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 son todas las definiciones de alcance de los predecesores de , . consta de todos los bloques básicos que vienen antes en el gráfico de flujo de control . Las definiciones de alcance que salen de son todas las definiciones de alcance de sus predecesores menos aquellas definiciones de alcance cuya variable es eliminada por más cualquier nueva definición generada dentro de . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle pred[S]}$ ${\displaystyle pred[S]}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

Para una instrucción genérica, definimos los conjuntos y de la siguiente manera: ${\displaystyle {\rm {GEN}}}$ ${\displaystyle {\rm {KILL}}}$

• ${\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, pero sí en el resto del programa) eliminadas por las definiciones en el bloque básico.

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

Algoritmo de lista de trabajo

La definición alcanzada generalmente se calcula utilizando un algoritmo de lista de trabajo iterativo.

Entrada: gráfico 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];          // coloca todos los nodos en el conjunto modificado // N son todos los nodos en el gráfico, Modificado = N ;  // Iterar mientras ( Cambiado != conjunto vacío ) { elige un nodo n en Cambiado ; // eliminarlo del conjunto cambiado Cambiado = Cambiado - { n };                 // init IN[n] para que esté vacío IN [ n ] = emptyset ;    // calcular IN[n] a partir de OUT[p] de los predecesores para todos los nodos p en predecesores ( n ) IN [ n ] = IN [ n ] Unión OUT [ p ];            oldout = OUT [ n ]; // guardar el antiguo 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] comparado con el valor anterior? if ( OUT [ n ] changed ) // comparar oldout vs. OUT[n] { // si es así, poner todos los sucesores de n en el conjunto cambiado para todos los nodos s en successors ( n ) Changed = Changed U { s }; } }                     

Véase también

• Eliminación de código muerto
• Movimiento de código invariante en bucle
• Usos alcanzables
• Formulario de asignación única estática

Lectura adicional

• 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). Implementación de compiladores modernos en aprendizaje automático . 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 de compiladores avanzados . 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.