[<<][meta][>>][..]

DAG Representations

                  flatten           schedule
MEMO-EXPR (dag)  --------->  SSA  <----------  DFN (dag)


1. Starting from expressions and variables.

The memo-expr is the basic form of functional code: value reuse
through function abstraction or let-binding.  Adding variables allows
one to move from trees to directed acyclic graphs (value reuse).

SSA is a MEMO-EXPR without expression nesting, i.e. all bindings are
primitive operations.


2. Starting from dataflow notation (input/output variables).

A dataflow network consists of:

  - a set of nodes
  - a set of input-output relations between nodes
  - a constraint: each node is the output node of exactly one relation

Node that the difference with expressions is that a DFN has _explicit_
output node naming, while for expressions this is _mostly_ implicit,
except for memoized expressions, and of course for SSA, which can be
interpreted as a DFN.  A memo-expression has _explicit_ dependency
order (lexical scope), but implicit data allocation.

                     MEX          DFN
    dependency order explicit     implicit
    output alloc     implicit     explicit          

An SSA expression is _both_ a MEX and a DFN.




[Reply][About]
[<<][meta][>>][..]