Consider the following basic block: $a = b + c$ $c = a + d$ $d = b + c$ $e = d - b$ $a = e + b$ The minimum number of nodes and edges present in the DAG representation of the above basic block, respectively, are

Question

Accepted Answer

6 and 6. In a DAG for a basic block, identical expressions are represented once and variable names are attached to nodes. Here, the computations can be organized with minimal sharing so that the representation uses 6 nodes and 6 edges. This is the standard DAG optimization idea used in compiler design.

Consider the following basic block: $a = b + c$ $c = a + d$ $d = b + c$ $e = d - b$ $a = e + b$ The minimum number of nodes and edges present in the DAG representation of the above basic block, respectively, are

Solution

Related GATE Technical questions