APT Wiki | Jamaica / DynamicSingleAssignmentForm

Dynamic single assignment form (DSA) is an extension of the popular static single assignment form (SSA) intermediate representation. Both DSA and SSA are intraprocedural representations, so the terms program/procedure generally refer to the same monolithic source code unit in both DSA and SSA descriptions.

Definition

In SSA, each variable is a destination operand (hence assignment) exactly once (hence single) in the program source code (hence static). In DSA, each variable is a destination operand at most once during any run of the program (hence dynamic).

Transformation Process

Assignment statements that are not enclosed in loops can be easily transformed to DSA, using the same variable renaming mechanisms as for SSA. However, assignment statements within loops are more tricky. Generally, the DSA conversion algorithm increases the dimensionality of the variable so that it is equal to the loop nesting depth. A couple of examples follow.

Example 1.

Program before DSA conversion:

    x = 0;
    for (int i = 0; i < 10; i++) {
        x = x + i;
    }
    return x;

Program after DSA conversion:

    x[0] = 0;
    for (int i = 0; i < 10; i++) {
        x[i+1] = x[i] + i;
    }
    return x[10];

Note that the scalar variable x has been transformed into a 1-dimensional array. In the transformed program, for the ith loop iteration, array element x[i] has the same value as scalar x from the original program. Yes, I know you are thinking, "There are multiple assignments to variable i in the for statement!" For some reason the DSA inventors seem to overlook this. It makes things simpler, even if it appears to break the rules.

Example 2.

Program before DSA conversion:

    int i, j, k;
    for (k = 0; k <= 10; k++) {
        c[k] = k;
    }
    for (i = 0; i <=4; i++) {
        for (j = 0; j <= 6; j++) {
            c[i+j] = c[i+j]+a[i]*b[j]
        }
    }

Program after DSA conversion:

    int i, j, k;
    for (k = 0; k <= 10; k++) {
        c1[k] = k;
    }
    for (i = 0; i <=4; i++) {
        for (j = 0; j <= 6; j++) {
            c2[i][j] = (i==0 || j==6 ? c1[i+j] : c2[i-1][j+1]) + a[i] * b[j]
        }
    }

(This more complicated example comes from a DSA paper, see Papers.)

Uses of DSA.

Each array element should be assigned at most once dynamically. Thus it makes data dependence calculation straightforward. Parallelization should be easy from DSA, since all non-flow dependence should be entirely eliminated.

Caveats

DSA construction algorithms only work for simple programs. Generally only works on for loops with constant bounds and constant loop iterators. Also, DSA - very inefficient. Uses lots more space, more indirection... Hopefully only an analysis tool, optimize away inefficiencies during final code generation.

Papers about DSA

 @article{feautrier91dataflow,
  author   = "Paul Feautrier",
  title    = "Dataflow analysis of array and scalar references",
  journal  = "International Journal of Parallel Programming",
  volume   = "20",
  number   = "1",
  pages    = "23--51",
  month    = "Feb",
  year     = "1991",
  url      = "http://citeseer.ist.psu.edu/feautrier91dataflow.html",
  abstract = "Original paper introducing dynamic single assignment form (DSA).
              With an extremely simple syntax-directed transformation algorithm,
              for a simple subset of Fortran.",
  }

 @techreport{offner03weak,
  author      = "Carl Offner and Kathleen Knobe",
  title       = "Weak Dynamic Single Assignment Form",
  month       = "Nov",
  year        = "2003",
  number      = "TR-HPL-2003-169",
  institution = "HP Labs",
  url         = "http://www.hpl.hp.com/techreports/2003/HPL-2003-169.html",
  abstract    = "reviews array SSA, goes onto develop dynamic single assignment form.
                 Works by adding extra dimensions to arrays to cope with repeated assignments to
                 same elements (due to loops). Little related work, seems to be unaware of 
                 previous formulations and transformation algorithms.",
 }

 @article{rau96iterative,
  author   =  "B. Ramakrishna Rau",
  title    = "Iterative modulo scheduling",
  journal  = "International Journal of Parallel Processing",
  volume   = "24",
  number   = "1",
  pages    = "3--64",
  month    = "Feb",
  year     = "1996",
  url      = "http://www.hpl.hp.com/techreports/94/HPL-94-115.html"
  abstract = "also available as a HP Labs technical report. Describes DSA and expanded
              virtual registers, the cloning support required for DSA. Basically converts each
              scalar into an array",
 }

 @techreport{vanbroekhoven03step,
  author      = "Peter Vanbroekhoven and Gerda Janssens and Maurice Bruynooghe and Henk Corporaal and Francky Catthoor",
  title       = "A Step towards a Scalable Dynamic Single Assignment Conversion",
  institution = "Department of Computer Science, Katholieke Universiteit Leuven",
  number      = "CW 360",
  month       = "Apr",
  year        = "2003",
  url         = "http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW360.abs.html",
  abstract    = "gives some motivation for DSA in terms of memory hierarchy design for embedded systems.
                 Then gives two different methods for transforming to DSA, one from 
                 SSA, one from CFG. Plenty of discussion, no results and not much analysis.
                 This technical report has the distinct flavour of a rejected paper.",
 }