Alcanzando la definición

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

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

d1es una definición de alcance 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.

Como análisis

Las definiciones de alcance con nombres similares son un análisis de flujo de datos que determina estáticamente qué definiciones pueden llegar a un punto dado en el código. Debido a su simplicidad, a menudo se usa como el 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 unión de conjuntos y el análisis es flujo directo. Las definiciones de alcance se utilizan para calcular cadenas de definición de uso .

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}$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}$ todos alcanzan definiciones de sus predecesores menos aquellos que alcanzan definiciones cuya variable es eliminada por ${\displaystyle S}$ más cualquier nueva definición generada dentro ${\displaystyle S}$.

Para una instrucción genérica, definimos el ${\displaystyle {\rm {GEN}}}$ y ${\displaystyle {\rm {KILL}}}$ 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, pero en el resto del programa) eliminadas por definiciones en el bloque básico.

donde ${\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 tanto, el dominio de los valores para llegar a las definiciones son estas etiquetas de instrucción.

Algoritmo de lista de trabajo

La definición de alcance generalmente se calcula mediante un algoritmo de lista de trabajo iterativo.

Entrada: gráfico de flujo de control CFG = (Nodos, Bordes, Entrada, Salida)

// Inicializar para  todos los  nodos CFG  n en N , OUT [ n ] = emptyset ; // puede optimizar por OUT [n] = GEN [n];       // poner todos los nodos en el conjunto modificado // N son todos los nodos del gráfico, Cambiado  =  N ;// Iterar mientras  ( ¡ Cambiado  ! =  Conjunto vacío ) {  elige  un  nodo  n  en  Cambiado ;  // eliminarlo del conjunto modificado  Cambiado  =  Cambiado  - {  n  }; // init IN [n] para estar vacío  IN [ n ]  =  emptyset ; // calcular IN [n] de los predecesores 'OUT [p]  para  todos los  nodos  p  en  predecesores ( n )  IN [ n ]  =  IN [ n ]  Union  OUT [ p ]; oldout  =  OUT [ n ];  // guarda el antiguo OUT [n] // actualiza 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 ]  cambiado )  // comparar oldout con OUT [n]  {  // si es así, poner todos los sucesores de n en el conjunto modificado  para  todos los  nodos  s  en  sucesores ( n )  Cambiado  =  Cambiado  U  {  s  };  } }

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 del compilador moderno en ML . Prensa de la Universidad de Cambridge. 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 . Saltador. ISBN 3-540-65410-0.

Ver también

• Formulario estático de asignación única
• Usos accesibles