Gráfico acíclico dirigido:
el gráfico acíclico dirigido (DAG) se utiliza para representar la estructura de bloques básicos , para visualizar el flujo de valores entre bloques básicos y para proporcionar técnicas de optimización en el bloque básico. Para aplicar una técnica de optimización a un bloque básico, un DAG es un código de tres direcciones que se genera como resultado de una generación de código intermedio.
- Los gráficos acíclicos dirigidos son un tipo de estructura de datos y se utilizan para aplicar transformaciones a bloques básicos.
- El gráfico acíclico dirigido (DAG) facilita la transformación de bloques básicos.
- DAG es un método eficiente para identificar subexpresiones comunes.
- Demuestra cómo se utiliza el valor calculado de la declaración en declaraciones posteriores.
Ejemplos de gráfico acíclico dirigido:
Características del gráfico acíclico dirigido:
un gráfico acíclico dirigido para bloque básico es un gráfico acíclico dirigido con las siguientes etiquetas en los Nodes.
- Cada una de las hojas del gráfico tiene un identificador único, que puede ser nombres de variables o constantes.
- Los Nodes interiores del gráfico están etiquetados con un símbolo de operador.
- Además, los Nodes reciben una string de identificadores para usar como etiquetas para almacenar el valor calculado.
- Los gráficos acíclicos dirigidos tienen sus propias definiciones de cierre transitivo y reducción transitiva.
- Los gráficos acíclicos dirigidos tienen órdenes topológicos definidos.
Algoritmo para la construcción de gráficos acíclicos dirigidos:
hay tres escenarios posibles para construir un DAG en tres códigos de dirección:
Caso 1 – x = y op z
Caso 2 – x = op y
Caso 3 – x = y
El gráfico acíclico dirigido para los casos anteriores se puede construir de la siguiente manera:
Paso 1 –
- Si el operando y no está definido, cree un Node (y).
- Si el operando z no está definido, cree un Node para el caso (1) como Node (z).
Paso 2 –
- Cree el Node (OP) para el caso (1), con el Node (z) como su hijo derecho y el Node (OP) como su hijo izquierdo (y).
- Para el caso (2), vea si hay un operador de Node (OP) con un Node hijo (y).
- El Node n será el Node (y) en el caso (3).
Paso 3:
elimine x de la lista de identificadores de Node. Paso 2: agregue x a la lista de identificadores adjuntos para el Node n.
Ejemplo :
T 0 = a + b —Expresión 1
T 1 = T 0 + c —-Expresión 2
d = T 0 + T 1 —–Expresión 3
Expresión 1 : T 0 = a + b
Expresión 2: T 1 = T 0 + c
Expresión 3: d = T 0 + T 1
Gráfico acíclico dirigido final
Ejemplo :
T 1 = un + segundo
T 2 = T1 + c
T 3 = T1 x T2
Ejemplo :
T 1 = un + segundo
T 2 = un – segundo
T 3 = T 1 * T 2
T 4 = T 1 – T 3
T 5 = T 4 + T 3
Gráfico acíclico dirigido final
Ejemplo :
una = bxc
re =
segundo mi = dxc segundo = mi
f = segundo
+ c
gramo = f + re
Gráfico acíclico dirigido final
Ejemplo :
T 1 := 4*I 0
T 2 := un[T 1 ]
T 3 := 4*I 0
T 4 := b[T 3 ]
T 5 := T 2 * T 4
T 6 := prod + T 5
producción:= T 6
T 7 := yo 0 + 1
yo 0 := T 7
si yo 0 <= 20 pasa a 1
Gráfico acíclico dirigido final
Aplicación del gráfico acíclico dirigido:
- El gráfico acíclico dirigido determina las subexpresiones que se usan comúnmente.
- El gráfico acíclico dirigido determina los nombres utilizados dentro del bloque, así como los nombres calculados fuera del bloque.
- Determina qué declaraciones en el bloque pueden tener su valor calculado fuera del bloque.
- El código se puede representar mediante un gráfico acíclico dirigido que describe las entradas y salidas de cada una de las operaciones aritméticas realizadas dentro del código; esta representación permite que el compilador realice la eliminación de subexpresiones comunes de manera eficiente.
- Varios lenguajes de programación describen sistemas de valores que están vinculados entre sí por un gráfico acíclico dirigido. Cuando cambia un valor, se recalculan sus sucesores; cada valor en el DAG se evalúa como una función de sus predecesores.
Publicación traducida automáticamente
Artículo escrito por naimishsahu08 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA