Cadena de definición de uso

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

Dentro de la informática , una cadena de definición de uso (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 a partir de esa definición sin ninguna otra definición intermedia. ^[3]

Tanto las cadenas UD como DU se crean mediante una forma 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 , incluida la propagación constante y la eliminación de subexpresiones comunes .

Objetivo

Hacer las cadenas usar-definir o definir-usar es un paso en el análisis de vida , 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 */                

Observe 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 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 use-def 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, xpodría ser como allí habrá una variable diferente; En la práctica, 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 separadas se llama división de rango en vivo. Véase también formulario estático de asignación única .

Configuración

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

• Las declaraciones se etiquetan utilizando las siguientes convenciones: , donde i es un número entero en ; y n es el número de declaraciones en el bloque básico ${\displaystyle s(i)}$ ${\displaystyle [1,n]}$
• Las variables se identifican en cursiva (p. ej., v , u y t ).
• Se supone que cada variable tiene una definición en el contexto o alcance. (En forma de asignación única estática , las cadenas de uso-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 en cursiva) y, para abreviar, su declaración se identifica como . En general, una declaración de una variable puede estar en un ámbito externo (por ejemplo, una variable global ). ${\displaystyle s(0)}$

Definición de una variable

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

Uso de una variable

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

Ejecución

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

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

Ejemplo de ejecución de def-use-chain

Este ejemplo se basa en un algoritmo de Java para encontrar el mcd . (No es importante entender 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 ) {       int c = a ;    int re = b ;     si ( c == 0 )    regresar d ;  mientras ( d ! = 0 ) {      si ( c > d )    c = c - d ;     demás re = re - c ;     }  devolver c ;  }

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

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

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

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

   En este caso lo 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 de definición, el acceso de escritura concreto, el acceso de lectura concreto]

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

Repita estos pasos con 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 ( d ! = 0 )]    [ d , d = b , si ( c > d )]    [ re , re = segundo , c = c - re ]    [ re , re = segundo , re = re - c ]   [ d , d = d - c , mientras ( d ! = 0 )]    [ d , d = d - c , si ( c > d )]    [ re , re = re - c , c = c - re ]    [ re , re = re - c , re = re - c ]  

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

Por ejemplo: desde la línea 7 hasta la línea 13 en el código fuente, d no se redefine ni cambia. En la línea 14, d podría redefinirse. Es por eso que debe recombinar este acceso de escritura en d con todos los accesos de lectura posibles que se puedan alcanzar. En este caso, sólo el código más allá de la línea 10 es relevante. Por ejemplo, ya no se puede llegar a la línea 7. Para su comprensión, puede imaginar 2 variables diferentes d :

 [ d1 , d1 = b , devuelve d1 ]     [ d1 , d1 = b , mientras ( d1 ! = 0 )]    [ d1 , d1 = b , si ( c > d1 )]    [ d1 , d1 = segundo , 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ía 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 ) {      int c = a ;    int d ;   si ( c == 0 )    devolver b ;  si ( b ! = 0 ) {     si ( c > b ) {     c = c - b ;     re = segundo ;   } demás re = b - c ;     mientras ( d ! = 0 ) {      si ( c > d )    c = c - d ;     demás re = re - c ;     } }  devolver c ;  }

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

1. Establecer definiciones en la declaración ${\displaystyle s(0)}$
2. Para cada i en , busque definiciones activas que se utilicen en la declaración ${\displaystyle [1,n]}$ ${\displaystyle s(i)}$
3. Hacer un vínculo entre definiciones y usos.
4. Establecer la declaración , como declaración de definición ${\displaystyle s(i)}$
5. Matar definiciones anteriores

Con este algoritmo se consiguen dos cosas:

1. Se crea un gráfico acíclico dirigido (DAG) sobre los usos y definiciones de las variables. El DAG especifica una dependencia de datos entre declaraciones de asignación, así como un orden parcial (por lo tanto, paralelismo entre declaraciones).
2. Cuando se llega a la declaración, 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 . ${\displaystyle s(i)}$

Referencias

1. Kennedy, Ken (enero de 1978). "Cadenas de definición de uso con aplicaciones". Lenguajes informáticos . 3 (3): 163–179. doi :10.1016/0096-0551(78)90009-7.
2. Searle, Aarón; Gough, John; Abramson, David (2003). "DUCT: una herramienta interactiva de navegación en cadena de uso definido para depuración relativa". arXiv : cs/0311037 .
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.