Cadena de uso y definición

Estructura de datos que rastrea el uso y las definiciones de las variables

Dentro de la informática , una cadena de uso-definición (o cadena UD ) es una estructura de datos que consta de un uso U , de una variable y de todas las definiciones D de esa variable que pueden llegar a ese uso sin ninguna otra definición intermedia. ^{[1] [2]} Una cadena UD generalmente significa la asignación de algún valor a una variable.

Una contraparte de una cadena UD es una cadena de definición-uso (o cadena DU ), que consiste en una definición D de una variable y todos los usos U alcanzables desde esa definición sin ninguna otra definición intermedia. ^[3]

Tanto las cadenas UD como las DU se crean mediante una forma de análisis de código estático conocida como análisis de flujo de datos . Conocer las cadenas use-def y def-use de un programa o subprograma es un requisito previo para muchas optimizaciones del compilador , incluidas la propagación constante y la eliminación de subexpresiones comunes .

Objetivo

Realizar las cadenas de uso-definición o definición-uso es un paso en el análisis de vitalidad , de modo que se puedan identificar y rastrear representaciones lógicas de todas las variables a través del código.

Considere el siguiente fragmento de código:

 int x = 0 ; /* A */ x = x + y ; /* B */ /* 1, algunos usos de x */ x = 35 ; /* C */ /* 2, algunos usos más de x */                

Observe que xse le asigna un valor en tres puntos (marcados A, B y C). Sin embargo, en el punto marcado "1", la cadena de definición de uso para xdebe indicar que su valor actual debe haber venido de la línea B (y su valor en la línea B debe haber venido de la línea A). Por el contrario, en el punto marcado "2", la cadena de definición de uso para xindica que su valor actual debe haber venido de la línea C. Dado que el valor de xen el bloque 2 no depende de ninguna definición en el bloque 1 o anterior, xbien podría ser una variable diferente allí; prácticamente hablando, es una variable diferente - llámela x2.

 int x = 0 ; /* A */ x = x + y ; /* B */ /* 1, algunos usos de x */ int x2 = 35 ; /* C */ /* 2, algunos usos de x2 */                 

El proceso de división xen dos variables independientes se denomina división de rango en vivo. Véase también formulario de asignación única estática .

Configuración

La lista de declaraciones determina un orden fuerte entre las declaraciones.

• Las declaraciones se etiquetan utilizando las siguientes convenciones: ⁠ ⁠ ${\displaystyle s(i)}$ , donde i es un entero en ⁠ ⁠ ${\displaystyle [1,n]}$ ; y n es el número de declaraciones en el bloque básico
• Las variables se identifican en cursiva (por ejemplo, v , u y t ).
• Se supone que cada variable tiene una definición en el contexto o ámbito. (En la forma de asignación única estática , las cadenas de uso y definición son explícitas porque cada cadena contiene un solo elemento).

Para una variable, como v , su declaración se identifica como V (letra mayúscula cursiva) y, para abreviar, su declaración se identifica como ⁠ ⁠ ${\displaystyle s(0)}$ . En general, una declaración de una variable puede estar en un ámbito externo (por ejemplo, una variable global ).

Definición de una variable

Cuando una variable, v , está en el lado izquierdo de una declaración de asignación, como ⁠ ⁠ ${\displaystyle s(j)}$ , entonces ⁠ ⁠ ${\displaystyle s(j)}$ es una definición de v . Cada variable ( v ) tiene al menos una definición por su declaración ( V ) (o inicialización).

Uso de una variable

Si la variable, v , está en el lado derecho del enunciado ⁠ ⁠ ${\displaystyle s(j)}$ , hay un enunciado, ⁠ ⁠ ${\displaystyle s(i)}$ con i < j y ⁠ ⁠ ${\displaystyle \min(j-i)}$ , que es una definición de v y tiene un uso en ⁠ ⁠ ${\displaystyle s(j)}$ (o, en resumen, cuando una variable, v , está en el lado derecho de un enunciado ⁠ ⁠ ${\displaystyle s(j)}$ , entonces v tiene un uso en el enunciado ⁠ ⁠ ${\displaystyle s(j)}$ ).

Ejecución

Consideremos la ejecución secuencial de la lista de declaraciones, ⁠ ⁠ ${\displaystyle s(i)}$ , y lo que ahora se puede observar como el cálculo en la declaración, j :

• Una definición en la declaración ⁠ ⁠ ${\displaystyle s(i)}$ con i < j está activa en j , si tiene un uso en una declaración ⁠ ⁠ ${\displaystyle s(k)}$ con k ≥ j . El conjunto de definiciones activas en la declaración i se denota como ⁠ ⁠ ${\displaystyle A(i)}$ y el número de definiciones activas como . ( ⁠ ⁠ es un concepto simple pero poderoso: los resultados teóricos y prácticos en la teoría de la complejidad espacial , la complejidad de acceso (complejidad de E/S), la asignación de registros y la explotación de la localidad de caché se basan en ⁠ ⁠ .) ${\displaystyle |A(i)|}$ ${\displaystyle A(i)}$ ${\displaystyle A(i)}$
• Una definición en la declaración ⁠ ⁠ ${\displaystyle s(i)}$ elimina todas las definiciones anteriores ( ⁠ ⁠ ${\displaystyle s(k)}$ con k < i ) para las mismas variables.

Ejemplo de ejecución de def-use-chain

Este ejemplo se basa en un algoritmo Java para encontrar el mcd . (No es importante entender lo que hace esta función).

/*** @param(a, b) Los valores utilizados para calcular el divisor.* @return El máximo común divisor de a y b.*/int mcd ( int a , int b ) {       int c = a ;    int d = b ;     si ( c == 0 )    devuelve d ;  mientras ( d != 0 ) {      si ( c > d )    c = c - d ;     demás d = d - c ;     }  devuelve c ;  }

Para conocer todas las cadenas de uso definido para la variable d, realice los siguientes pasos:

1. Buscar por primera vez que se define la variable (acceso de escritura).

   En este caso es " d=b" (l.7)

2. Busca la primera vez que se lee la variable.

   En este caso es " return d"

3. Escriba esta información en el siguiente estilo: [nombre de la variable para la que está creando una cadena de uso definido, el acceso de escritura concreto, el acceso de lectura concreto]

   En este caso es:[d, d=b, return d]

Repita estos pasos en el siguiente estilo: combine cada acceso de escritura con cada acceso de lectura (pero NO al revés).

El resultado debería ser:

 [ d , d = b , devuelve d ]     [ d , d = b , mientras que ( d != 0 )]    [ d , d = b , si ( c > d )]    [ d , d = b , c = c - d ]    [ d , d = b , d = d - c ]   [ d , d = d - c , mientras que ( d != 0 )]    [ d , d = d - c , si ( c > d )]    [ d , d = d - c , c = c - d ]    [ d , d = d - c , d = d - c ]  

Hay que tener cuidado si la variable cambia con el tiempo.

Por ejemplo: desde la línea 7 hasta la línea 13 del código fuente, d no se redefine ni se modifica. En la línea 14, d podría redefinirse. Por eso, hay que volver a combinar este acceso de escritura en d con todos los posibles accesos de lectura a los que se pueda acceder. En este caso, solo es relevante el código que se encuentra más allá de la línea 10. Por ejemplo, no se puede acceder de nuevo a la línea 7. Para que lo entiendas, puedes imaginar dos variables diferentes d :

 [ d1 , d1 = b , devuelve d1 ]     [ d1 , d1 = b , mientras que ( d1 != 0 )]    [ d1 , d1 = b , si ( c > d1 )]    [ d1 , d1 = b , c = c - d1 ]    [ d1 , d1 = b , d1 = d1 - c ]   [ d2 , d2 = d2 - c , mientras que ( d2 != 0 )]    [ d2 , d2 = d2 - c , si ( c > d2 )]    [ d2 , d2 = d2 - c , c = c - d2 ]    [ d2 , d2 = d2 - c , d2 = d2 - c ]  

Como resultado, se podría obtener algo como esto. La variable d1 se reemplazaría por b .

/*** @param(a, b) Los valores utilizados para calcular el divisor.* @return El máximo común divisor de a y b.**/int mcd ( int a , int b ) {      int c = a ;    entero d ;   si ( c == 0 )    devolver b ;  si ( b != 0 ) {     si ( c > b ) {     c = c - b ;     d = b ;   } demás d = b - c ;     mientras ( d != 0 ) {      si ( c > d )    c = c - d ;     demás d = d - c ;     } }  devuelve c ;  }

Método de construcción de unauso-def(otú) cadena

1. Establecer definiciones en la declaración ${\displaystyle s(0)}$
2. Para cada i en ⁠ ⁠ ${\displaystyle [1,n]}$ , encuentre definiciones vivas que tengan uso en la declaración ⁠ ⁠ ${\displaystyle s(i)}$
3. Establecer un vínculo entre definiciones y usos
4. Establezca la declaración ⁠ ⁠ ${\displaystyle s(i)}$ , como declaración de definición
5. Matar definiciones anteriores

Con este algoritmo se consiguen dos cosas:

1. Se crea un gráfico acíclico dirigido (DAG) a partir de los usos y definiciones de las variables. El DAG especifica una dependencia de datos entre las instrucciones de asignación, así como un orden parcial (por lo tanto, paralelismo entre instrucciones).
2. Cuando se llega a la instrucción ⁠ ⁠ ${\displaystyle s(i)}$ , hay una lista de asignaciones de variables activas . Si solo hay una asignación activa, por ejemplo, se podría utilizar la propagación constante .

Referencias

1. Kennedy, Ken (enero de 1978). "Cadenas de uso y definición con aplicaciones". Lenguajes informáticos . 3 (3): 163–179. doi :10.1016/0096-0551(78)90009-7.
2. Searle, Aaron; Gough, John; Abramson, David (2003). "DUCT: una herramienta interactiva de navegación por cadenas de definición y uso para la depuración relativa". arXiv : cs/0311037 .
3. Leiss, Ernst L. (26 de septiembre de 2006). A Programmer's Companion to Algorithm Analysis (Compendio de análisis de algoritmos para programadores ). CRC Press. ISBN 978-1-4200-1170-8.