Una Cadena de Definición de Uso ( Cadena UD ) es una estructura de datos que consiste en un uso, U, de una variable , y todas las definiciones, D, de esa variable que pueden alcanzar ese uso sin ninguna otra definición que intervenga. Una Cadena UD generalmente significa la asignación de algún valor a una variable.
Una contraparte de una Cadena UD es una Cadena Definición-Uso ( DU Chain ), que consiste en una definición, D, de una variable y todos los usos, U, accesibles desde esa definición sin ninguna otra definición que intervenga.
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 para 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 .
Propósito
Hacer las cadenas de uso-definir o definir-uso es un paso en el análisis de vida , de modo que las representaciones lógicas de todas las variables se pueden identificar y rastrear 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 x
se le asigna un valor en tres puntos (marcados con A, B y C). Sin embargo, en el punto marcado con "1", la cadena use-def para x
debe 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 x
indica que su valor actual debe provenir de la línea C. Dado que el valor de x
en el bloque 2 no depende de ninguna definición en el bloque 1 o antes, x
podría como habrá una variable diferente allí; prácticamente hablando, es una variable diferente - llámala 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 x
en dos variables separadas se denomina división de rango en vivo . Consulte también el formulario de asignación única estática .
Configuración
La lista de declaraciones determina un orden fuerte entre 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
- 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 la forma de asignación única estática , las cadenas definidas por el uso son explícitas porque cada cadena contiene un solo elemento).
Para una variable, como v , su declaración se identifica como V (letra cursiva mayúscula) 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 ).
Definición de una variable
Cuando una variable, v , está en el lado izquierdo de una instrucción de asignación, como, luego 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, 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 una instrucción at).
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 :
- Una definición en la declaración con i < j está vivo en j , si tiene un uso en una declaracióncon k ≥ j . El conjunto de definiciones vivas en el enunciado 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.)
- Una definición en la declaración mata todas las definiciones anteriores (con k < i ) para las mismas variables.
Ejemplo de ejecución para def-use-chain
Este ejemplo se basa en un algoritmo de Java para encontrar el gcd . (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 ay b. * /int gcd ( int a , int b ) { int c = a ; int d = b ; si ( c == 0 ) return d ; while ( d ! = 0 ) { si ( c > d ) c = c - d ; demás d = d - c ; } return c ; }
Para averiguar todas las cadenas de uso de def para la variable d, siga los siguientes pasos:
- Buscar por primera vez que se defina la variable (acceso de escritura).
- En este caso es "
d=b
" (l.7)
- En este caso es "
- Busque la primera vez que se lea la variable.
- En este caso es "
return d
"
- En este caso es "
- Escriba esta información en el siguiente estilo: [nombre de la variable para la que está creando una cadena de def-use-chain, el acceso de escritura concreto, el acceso de lectura concreto]
- En este caso lo es:
[d, d=b, return d]
- En este caso lo es:
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 , return d ] [ d , d = b , mientras que ( d ! = 0 )] [ d , d = b , si ( c > d )] [ d , d = b , c = c - d ] [ d , d = segundo , 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 ]
Tienes que tener cuidado, si la variable se cambia por el tiempo.
Por ejemplo: desde la línea 7 hasta la línea 13 en el código fuente, d no se redefine / cambia. En la línea 14, d podría redefinirse, es por eso que tiene 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 el código más allá de la línea 10 es relevante. Por ejemplo, no se puede volver a alcanzar la línea 7. Para su comprensión, puede imaginar 2 variables diferentes d :
[ d1 , d1 = b , return 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, podría obtener algo como esto. La variable d1 sería reemplazado por B
/ ** * @param (a, b) Los valores utilizados para calcular el divisor. * @return El máximo común divisor de ay b. ** /int gcd ( int a , int b ) { int c = a ; int d ; si ( c == 0 ) volver b ; si ( b ! = 0 ) { si ( c > b ) { c = c - b ; d = b ; } demás d = b - c ; while ( d ! = 0 ) { si ( c > d ) c = c - d ; demás d = d - c ; } } return c ; }
Método de construcción de una cadena use-def (o ud )
- Establecer definiciones en una declaración
- Por cada yo en, encuentre definiciones en vivo que tengan uso en la declaración
- Establezca un vínculo entre definiciones y usos.
- Establecer la declaración , como declaración de definición
- Mata las definiciones anteriores
Con este algoritmo, se logran dos cosas:
- 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).
- Cuando declaración se alcanza, hay una lista de los vivos asignaciones de variables. Si solo una asignación está activa, por ejemplo, se puede utilizar la propagación constante .