Defining Static Single Assignment


Most compilers convert the input source code into one or more intermediate representations (IRs) to make it easier and faster to analyze and optimize the code. Static single assignment (SSA) is a property of IRs that helps in not only simplifying the algorithms that analyze the code, but also improve their results at the same time, leading to more effective and efficient optimizations. The definition of SSA according to Wikipedia is currently as follows:

“In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable is assigned exactly once, and every variable is defined before it is used.”

If you are not familiar with SSA, then it’s better to read the whole Wikipedia article before continuing. This article is only about the definition of SSA and does not get into the benefits of that property.

This definition includes three pieces of information. First, it states that SSA is a property of IRs rather than an IR itself. This is an important part of the definition. Then it states two conditions for that property to hold. The first is that each variable is assigned exactly once. Perhaps, this explains the phrase “single assignment.” Hopefully, the second condition will tell us something about the “static” part of the term. The second condition is that every variable is defined before it is used. Is this why it’s called static? There is really no connection between the two.

The bigger issue with that definition is that it’s ambiguous. It says that every variable must be defined before it is used. But to define a variable, don’t we have to assign to it an initial value? But that has already been stated in the first condition. Perhaps, the term “defined” is used as a synonym to “declared.” But why is it important for each variable to be declared? Suppose there is an IR in which it’s OK to use a variable without declaring it first, in which case the variable gets some default value. The variable could be implicitly declared in the same scope in which it was first used. In fact, thew whole Wikipedia article does not explain why the second condition matters.

This got me suspicious that the definition given in Wikipedia is not very accurate. Therefore, I started looking into textbooks and other articles to find a better definition, but to no avail.

The best way to determine the exact definition of SSA is to check how it was defined in the document that first proposed this idea. To the best of my knowledge, Rosen, Wegman, and Zadeck are the authors who proposed this idea in their 1988 paper titled “Global value numbers and redundant computations.” In that paper, this is how they introduce SSA:

“The phrase single assignment is already in use for programs that assign to each variable only once when running. Dynamically, a program with loops may assign to the same variable many times, even if only one assignment appears in the program text. Our transformation puts the program into static single assignment form, which we will abbreviate to SSA form.”

The authors first mention that the term “single assignment” was used to refer to execution behavior in which a particular variable is assigned only once during the lifetime of the program. Then they give an example where even though there is a single assignment statement in the source code, that statement could be executed many times. This leads to the distinction between dynamic single assignment (which was called simply single assignment) and static single assignment (what the authors propose).

Now let’s get to the definition from Wikipedia and figure out what’s wrong with it. First, the first condition is slightly incorrect. It’s OK if there are some variables that are never assigned to any value (they get some garbage value at run-time). The SSA property would still hold and the algorithms the depend on it would work with little or no modifications. The first condition should be written as follows: each variable is assigned at most once in the source code.

The second condition is actually completely irrelevant to SSA. In that paper, the authors never mentioned any such condition. All algorithms that require the SSA property can be easily adjusted to handle IRs that allow variables to be used without first declaring them. Therefore, the second condition should be completely eliminated.

Overall, this is how the definition of SSA should read: In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable is assigned exactly once in the source code.

That said, the rest of the Wikipedia article is nicely written.

Later, in 2003, a variant of SSA was proposed and was called Weak Dynamic Single Assignment (Weak DSA). For more information refer to this paper. That paper also provides more discussion on DSA.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s