Q8Compiler Design
Question
Define DAG (Directed Acyclic Graph).
Answer
A DAG (Directed Acyclic Graph) is a directed graph with no cycles, used in compilers to represent the structure of basic blocks and to identify common subexpressions.
A Directed Acyclic Graph (DAG) is a directed graph in which there are no cycles — following directed edges from any node will never lead back to that same node. In the context of compilers, DAGs are used as an intermediate representation for basic blocks.
In a DAG for a basic block: leaf nodes represent identifiers (variables) or constants; interior nodes represent operators; a node represents the result of the operation — if the same subexpression appears multiple times, only one node is created (shared). This sharing naturally identifies common subexpressions that need to be computed only once. DAGs are also used to represent data dependencies and for register allocation. Example: for t1 = a+b; t2 = a+b; both t1 and t2 point to the same '+' node with children a and b.