Explain Directed Acyclic Graph

  • DAG stands for  Directed Acyclic Graph.
  • Syntax tree and DAG both, are graphical representations. Syntax tree does not find the common sub expressions whereas DAG can
  • Another usage of DAG is the application of optimization technique in the basic block
  • To apply optimization technique on basic block, a DAG is a constructed three address code which is the output of an intermediate code generation.
  • Characteristics of DAG are:
  • All internal nodes store operator values
  • External or leaf nodes are identifiers or variable names or constants
  • Algorithm for Construction of DAG
    There are three possible cases to construct DAG on three address code:
    Case 1: x = y op z
    Case 2: x = op y
    Case 3: x = y
    DAG can be constructed as follows:
    STEP 1:
    If y is undefined then create a node with label y. Similarly create a node with label z.
    STEP 2:
    For case 1, create a node with label op whose left child is node y, and node z will be the right child. Also, check for any common sub expressions. For case 2, determine if a node is labelled op. such node will have a child node y. for case 3 node n will be node y.
    STEP 3:
    Delete x from list of identifiers for node x. append x to the list of attached identifiers for node n found in step 2.
Posted on by
Score
Views