DAG - Directed Acyclic Graph

Directed Acyclic Graph (DAG) is a tool that depicts the structure of basic blocks, helps to see the flow of values flowing among the basic blocks, and offers optimizatino too. 1

A directed acyclic graph (DAG) for a basic block:

  • Leaf nodes represent identifiers, names or constants.
  • Interior nodes are labeled by an operator symbol.
  • Nodes are also given a sequence of identifiers for labels to store the computed value.

DAG provides easy transformation on basic blocks.

Peephole Optimizations: works locally to transform the input code into an optimized code. By locally, we mean a small portion of the code block at hand. These methods can be applied on intermediate codes as well as on target codes. Possible optimizations are: redundant instruction elimination; unreachable code; flow of control optimization; algebraic expression simplification; strength reduction, replace operations that consume more time and space with other operations that consume less time and space, but produce the same result (x * 2 –> x << 1); access machine instructions, leverage target machine’s sophisticated instructions.

More at Compiler Design - Code Generation

To construct the DAG

Input: a basic block

Output: a DAG, where:

  • each node contains a label. For leaves, the label is an identifier.
  • each node contains a list of attached identifiers to hold the computed values.

More at DAG representation for basic blocks see

  1. Compiler Design - Code Generation ↩
Created Jul 13, 2020 // Last Updated Jul 14, 2020

If you could revise
the fundmental principles of
computer system design
to improve security...

... what would you change?