Directed Acyclic Graph-
Directed Acyclic Graph (DAG) is a special kind of Abstract Syntax Tree.
- Each node of it contains a unique value.
- It does not contain any cycles in it, hence called Acyclic.
Optimization Of Basic Blocks-
DAG is a very useful data structure for implementing transformations on Basic Blocks.
- A DAG is constructed for optimizing the basic block.
- A DAG is usually constructed using Three Address Code.
- Transformations such as dead code elimination and common sub expression elimination are then applied.
Properties-
- Reachability relation forms a partial order in DAGs.
- Both transitive closure & transitive reduction are uniquely defined for DAGs.
- Topological Orderings are defined for DAGs.
Applications-
DAGs are used for the following purposes-
- To determine the expressions which have been computed more than once (called common sub-expressions).
- To determine the names whose computation has been done outside the block butused inside the block.
- To determine the statements of the block whose computed value can be made available outside the block.
- To simplify the list of Quadruples by not executing the assignment instructions x:=y unless they are necessary and eliminating the common sub-expressions.
Construction of DAGs-
Following rules are used for the construction of DAGs-
Rule-01:
In a DAG,
- Interior nodes always represent the operators.
- Exterior nodes (leaf nodes) always represent the names, identifiers or constants.
Rule-02:
While constructing a DAG,
- A check is made to find if there exists any node with the same value.
- A new node is created only when there does not exist any node with the same value.
- This action helps in detecting the common sub-expressions and avoiding the re-computation of the same.
Rule-03:
The assignment instructions of the form x:=y are not performed unless they are necessary.
Also Read- Code Optimization
PRACTICE PROBLEMS BASED ON DIRECTED ACYCLIC GRAPHS-
Problem-01:
Consider the following expression and construct a DAG for it-
( a + b ) x ( a + b + c )
Solution-
Three Address Code for the given expression is-
T1 = a + b
T2 = T1 + c
T3 = T1 x T2
Now, Directed Acyclic Graph is-
NOTE
From the constructed DAG, we observe-
- The common sub-expression (a+b) has been expressed into a single node in the DAG.
- The computation is carried out only once and stored in the identifier T1 and reused later.
This illustrates how the construction scheme of a DAG identifies the common sub-expression and helps in eliminating its re-computation later.
Problem-02:
Consider the following expression and construct a DAG for it-
( ( ( a + a ) + ( a + a ) ) + ( ( a + a ) + ( a + a ) ) )
Solution-
Directed Acyclic Graph for the given expression is-
Problem-03:
Consider the following block and construct a DAG for it-
(1) a = b x c
(2) d = b
(3) e = d x c
(4) b = e
(5) f = b + c
(6) g = f + d
Solution-
Directed Acyclic Graph for the given block is-
Problem-04:
Optimize the block in the Problem-03.
Solution-
Step-01:
Firstly, construct a DAG for the given block (already done above).
Step-02:
Now, the optimized block can be generated by traversing the DAG.
- The common sub-expression e = d x c which is actually b x c (since d = b) is eliminated.
- The dead code b = e is eliminated.
The optimized block is-
(1) a = b x c
(2) d = b
(3) f = a + c
(4) g = f + d
Problem-05:
Consider the following basic block-
B10:
S1 = 4 x I
S2 = addr(A) – 4
S3 = S2[S1]
S4 = 4 x I
S5 = addr(B) – 4
S6 = S5[S4]
S7 = S3 x S6
S8 = PROD + S7
PROD = S8
S9 = I + 1
I = S9
If I <= 20 goto L10
- Draw a directed acyclic graph and identify local common sub-expressions.
- After eliminating the common sub-expressions, re-write the basic block.
Solution-
Directed Acyclic Graph for the given basic block is-
In this code fragment,
- 4 x I is a common sub-expression. Hence, we can eliminate because S1 = S4.
- We can optimize S8 = PROD + S7 and PROD = S8 as PROD = PROD + S7.
- We can optimize S9 = I + 1 and I = S9 as I = I + 1.
After eliminating S4, S8 and S9, we get the following basic block-
B10:
S1 = 4 x I
S2 = addr(A) – 4
S3 = S2[S1]
S5 = addr(B) – 4
S6 = S5[S1]
S7 = S3 x S6
PROD = PROD + S7
I = I + 1
If I <= 20 goto L10
To gain better understanding about Directed Acyclic Graphs,
Watch this Video Lecture
Download Handwritten Notes Here-
Next Article- Misc Problems On Directed Acyclic Graphs
Get more notes and other study material of Compiler Design.
Watch video lectures by visiting our YouTube channel LearnVidFun.
Summary
Article Name
Directed Acyclic Graphs | DAGs | Examples
Description
In Compiler design, Directed Acyclic Graph is a directed graph that does not contain any cycles in it. Directed Acyclic Graph Examples. Properties and Applications. Problems On Directed Acyclic Graphs.
Author
Akshay Singhal
Publisher Name
Gate Vidyalay
Publisher Logo
FAQs
A directed acyclic graph is a directed graph that has no cycles. A vertex v of a directed graph is said to be reachable from another vertex u when there exists a path that starts at u and ends at v. As a special case, every vertex is considered to be reachable from itself (by a path with zero edges).
What is DAG used for? ›
A DAG is a Directed Acyclic Graph, a type of graph whose nodes are directionally related to each other and don't form a directional closed loop. In the practice of analytics engineering, DAGs are often used to visually represent the relationships between your data models.
How does DAGs work? ›
A directed acyclic graph (DAG) is a conceptual representation of a series of activities. The order of the activities is depicted by a graph, which is visually presented as a set of circles, each representing an activity, some of which are connected by lines, representing the flow from one activity to another.
What is a DAG in Python? ›
A DAG (Directed Acyclic Graph) is the core concept of Airflow, collecting Tasks together, organized with dependencies and relationships to say how they should run.
How do you know if a graph is a DAG? ›
Directed Acyclic Graph (DAG)
A directed graph is acyclic if it contains no cycles. That is, starting at any node in the graph, no sequence of edges exists that can be followed to loop back to that starting node. As a result, directed acyclic graphs do not contain any self-loops.
What are the advantages of directed acyclic graph? ›
Directed Acyclic Graphs (DAGs) find extensive utility across diverse fields like computer science, data analysis, and machine learning. In computer science, DAGs serve as fundamental structures for tasks like scheduling and optimizing computations .
Why are DAGs useful? ›
What are DAGs good for? They provide a simple visual representation of causal relationships among a set of variables. If these causal relationships are know to be true, then great. But if not, then they make it explicit what assumptions are being made.
What are the limitations of DAGs? ›
Limitations of DAGs
Second, DAGs do not convey information about magnitude or functional form of causal relationships and therefore are not ideal tools to definitively represent effect-measure modification or moderators. For example, in Figure 1, J causes D.
Why Airflow uses DAG? ›
In Airflow, a DAG represents a data pipeline or workflow with a start and an end. The mathematical properties of DAGs make them useful for building data pipelines: Directed: There is a clear direction of flow between tasks. A task can be either upstream, downstream, or parallel to another task.
Is DAG an algorithm? ›
Directed Acyclic Graphs (DAGs) are directed graphs that do not contain cycles. These kind of graphs are commonly used to model dependencies between entities. The canonical algorithm that goes hand in hand with DAGs is topological sort, for which GDS provides an efficient parallel implementation.
A Tree is just a restricted form of a Graph. Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.
How to write a Python DAG? ›
The following are the steps by step to write an Airflow DAG or workflow:
- Creating a python file.
- Importing the modules.
- Default Arguments for the DAG.
- Instantiate a DAG.
- Creating a callable function.
- Creating Tasks.
- Setting up Dependencies.
- Verifying the final Dag code.
A cycle, in the context of a graph, occurs when some number of vertices are connected to one another in a closed chain of edges. A graph that contains at least one cycle is known as a cyclic graph. Conversely, a graph that contains zero cycles is known as an acyclic graph.
What is the difference between a tree and a directed acyclic graph? ›
A Tree is just a restricted form of a Graph. Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.
What is the difference between directed acyclic and undirected graphs? ›
A graph is acyclic if it does not contain a cycle. With that said, a directed graph is one where the edges are all endowed with a direction. Associated with every digraph is its underlying graph which is an undirected graph with the same vertex and edge set but "ignoring" the direction.
What is the difference between directed acyclic graph and Blockchain? ›
Unlike blockchains, DAGs do not organize data in blocks but in a graph structure where various types of transactions directly reference one another. No Need for Blocks or Miners: This structure eliminates the need for blocks and miners, potentially increasing transaction speeds and reducing costs.
