Cadena de definición de uso

En 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 todas las definiciones D de esa variable que pueden alcanzar 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 ]}

Las cadenas UD y DU se crean mediante un tipo de análisis de código estático conocido 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 , incluyendo la propagación de constantes y la eliminación de subexpresiones comunes .

Objetivo

La creación de las cadenas use-define o define-use es un paso en el análisis de vivacidad , de modo que las representaciones lógicas de todas las variables puedan identificarse y rastrearse 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 */

Nótese que xse le asigna un valor en tres puntos (marcados A, B y C). Sin embargo, en el punto marcado "1", la cadena use-def para xdebería indicar que su valor actual debe provenir de la línea B (y su valor en la línea B debe provenir de la línea A). Por el contrario, en el punto marcado "2", la cadena use-def para xindica que su valor actual debe provenir 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í; en la práctica, es una variable diferente : llamémosla 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 dividir xen dos variables separadas se denomina división de rango dinámico . Véase también la forma de asignación única estática .

Configuración

La lista de afirmaciones determina un orden estricto entre ellas.

Las declaraciones se etiquetan utilizando las siguientes convenciones : $s(i)$ , donde i es un número entero en $[1,n]$ ; y n es el número de instrucciones en el bloque básico.
Las variables se identifican en cursiva (por ejemplo, v , u y t ).
Se presupone 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-definición son explícitas porque cada cadena contiene un único elemento).

Para una variable, como v , su declaración se identifica como V (letra mayúscula en cursiva), y para abreviar, su declaración se identifica como ⁠ $s(0)$ ⁠ . En general, la 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 instrucción de asignación, como por ejemplo : $s(j)$ ⁠ , entonces ⁠ $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 de la instrucción ⁠ $s(j)$ ⁠ , hay una declaración, ⁠ $s(i)$ con i < j y $\min(ji)$ ⁠ , que es una definición de v y tiene un uso en ⁠ $s(j)$ ( o, en resumen, cuando una variable, v , está en el lado derecho de una instrucción ) $s(j)$ ⁠ , entonces v tiene un uso en la declaración ⁠ $s(j)$ ⁠ ).

Ejecución

Consideremos la ejecución secuencial de la lista de instrucciones , $s(i)$ ⁠ , y lo que ahora se puede observar como el cálculo en la instrucción j :

Una definición en la declaración $s(i)$ ⁠ con i < j está vivo en j , si tiene un uso en una instrucción ⁠ $s(k)$ con k ≥ j . El conjunto de definiciones vivas en la declaracióni se denota como $A(i)$ y el número de definiciones vivas como $|A(i)|$ . ( ⁠ $A(i)$ 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 él . $A(i)$ . )
Una definición en la declaración $s(i)$ ⁠ elimina todas las definiciones anteriores ( ⁠ $s(k)$ con k < i ) paralas mismas variables.

Ejemplo de ejecución para def-use-chain

Este ejemplo se basa en un algoritmo de Java para hallar el máximo común divisor (MCD ). (No es importante comprender qué 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 ) {entero c = a ;entero d = b ;si ( c == 0 )devolver d ;mientras ( d != 0 ) {si ( c > d )c = c - d ;demásd = d - c ;}devolver c ;}

Para averiguar todas las cadenas de definición-uso para la variable d, siga los siguientes pasos:

Buscar la primera vez que se define la variable (acceso de escritura).
En este caso es " d=b" (l.7)
Buscar la primera vez que se lee la variable.
En este caso es " return d"
Escriba esta información con el siguiente formato: [nombre de la variable para la que está creando una cadena de uso-definición, el acceso de escritura concreto, el acceso de lectura concreto]
En este caso es:[d, d=b, return d]

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

El resultado debería ser:

[ d , d = b , devolver d ][ d , d = b , mientras ( 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 ( 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 es necesario recombinar este acceso de escritura en d con todos los posibles accesos de lectura que se puedan alcanzar. En este caso, solo es relevante el código posterior a la línea 10. La línea 7, por ejemplo, ya no se puede alcanzar. Para que lo entienda mejor, puede imaginar dos variables d diferentes :

[ d1 , d1 = b , devolver d1 ][ d1 , d1 = b , mientras ( 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 ( 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, podrías obtener algo como esto. La variable d1 sería reemplazada 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 ) {entero c = a ;int d ;si ( c == 0 )devolver b ;si ( b != 0 ) {si ( c > b ) {c = c - b ;d = b ;}demásd = b - c ;mientras ( d != 0 ) {si ( c > d )c = c - d ;demásd = d - c ;}}devolver c ;}

Método para construir una cadena use-def (o ud )

Definiciones de configuración en la declaración $s(0)$ ⁠
Para cada $i$ en ⁠ $[1,n]$ ⁠ , encuentra definiciones en vivo que tengan utilidad en la declaración ⁠ $s(i)$ ⁠
Establecer una relación entre definiciones y usos
Establecer la declaración $s(i)$ ⁠ , como declaración de definición
Eliminar definiciones anteriores

Con este algoritmo se consiguen dos cosas:

Se crea un grafo acíclico dirigido (DAG) a partir de los usos y definiciones de las variables. El DAG especifica una dependencia de datos entre las sentencias de asignación, así como un orden parcial (y, por lo tanto, paralelismo entre las sentencias).
Cuando se declara $s(i)$ Cuando se alcanza, hay una lista de asignaciones de variables activas . Si solo una asignación está activa, por ejemplo,se podría utilizar la propagación de constantes .

Referencias

↑ Kennedy, Ken (enero de 1978). "Cadenas de definición de uso con aplicaciones". Computer Languages . 3 (3): 163– 179. doi : 10.1016/0096-0551(78)90009-7 .
↑ Searle, Aaron; Gough, John; Abramson, David (2003). "DUCT: Una herramienta interactiva de navegación de cadenas de definición-uso para depuración relativa". arXiv : cs/0311037 .
^ Leiss, Ernst L. (26 de septiembre de 2006). Un compañero del programador para el análisis de algoritmos . Prensa CRC. ISBN 978-1-4200-1170-8.

[kennedy-1] Kennedy, Ken (enero de 1978). "Cadenas de definición de uso con aplicaciones". Computer Languages . 3 (3): 163– 179. doi : 10.1016/0096-0551(78)90009-7 .

[duct-2] Searle, Aaron; Gough, John; Abramson, David (2003). "DUCT: Una herramienta interactiva de navegación de cadenas de definición-uso para depuración relativa". arXiv : cs/0311037 .

[leiss-3] Leiss, Ernst L. (26 de septiembre de 2006). Un compañero del programador para el análisis de algoritmos . Prensa CRC. ISBN 978-1-4200-1170-8.

[ 1 ]

[ 2 ]

[ 3 ]