SSA Form

Most optimizations are performed on a static single assignment representation of the Scribble CFG. The compiler is able to transform a CFG into and out of SSA form as required.

When a variable is in static single assignment form it has only one definition. That is, there is only one production that sets the value of the variable. To accompish this, new versions of a variable are created. For example, in

int ftn(int x, int y)
{
   if (x < 0) {
     x = y - x;
   } else {
     x = y + x;
   }
   return x;
}

variable x is renamed as shown in

int ftn(int x, int y)
{
   x_0 = x;
   if (x_0 < 0) {
     x_1 = y - x_0;
   } else {
     x_2 = y + x_0;
   }
   x_3 = PHI(x_1, x_2);
   return x_3;
}

Now, there is only one definition for each variable. This allows simple (use-def) links to be created from the use of a variable to its definition. These simple links simplify many optimizations. The PHI function is removed prior to generating the result program as shown in

int ftn(int x, int y)
{
   x_0 = x;
   if (x_0 < 0) {
     x_1 = y - x_0;
     x_3 = x_1;
   } else {
     x_2 = y + x_0;
     x_3 = x_2;
   }
   return x_3;
}

Scale is able to utilize surrogates for global variables and place them in SSA form. These surrogates are Local copies of the global variables. The "Global Variable Replacement" optimization creates the surrogates. (The original global variable is not in SSA form.)

Return to Scale dataflow diagram.
Return to Scale home page.
(Last changed: March 21, 2007.)