scale.score
Class SSA

java.lang.Object
  scale.score.SSA

public class SSA
extends java.lang.Object

This class converts a Scribble CFG into the SSA form of the CFG.

$Id: SSA.java,v 1.191 2007-10-04 19:58:19 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

See page 447 in Modern Compiler Implementation in Java by Appel, Cambridge, 1998 or Kathryn S. McKinley's CS 710 lecture notes.

The algorithm creates new Clef variable declarations for the renamed variables generated for the SSA form. The new variable declarations are named by appending the original name with a '#' followed by a sequence of digits. Phi operations are inserted into the CFG and reference the renamed variables.

Our baseline technique for including alias information in SSA form is described in the paper by Chow et. al. It helps to understand this paper to understand our extensions.

The main contribution by Chow et. al. is the use of virtual variables to represent indirect operations which unifies the treatment of indirect and scalar variables for SSA analyses and optimizations. The treatment of aliases is based upon the work by Choi et. al. which distinguishes between MayDefs (preserving definitions or weak updates), MustDefs, and MayUses. Chow et. al. add Chi and Mu operators to model MayDef and MayUse effects, respectively. The Chi and Mu operators work on virtual variables rather than scalar variables. Thus, a definition (Chi) of a virtual variable is a definition of a group of actual variables that share similar alias characteristics. Correspondingly, a Mu operator represents a use.

A virtual variable represents a group of program, or user, variables that have similar alias characteristics. We originally used Steensgaard's alias analysis algorithm to create these groups which we also call abstract locations (abstract location and virtual variable can be used interchangeably). For example, in the sequence, "p = &a; p = &b", a virtual variable is created to represent "a", "b", and "*p". This means that, conservatively, any use of "*p" may use "a" or "b". A very conservative approach may create one virtual variable for every user variable.

Our basic algorithm works as follows:

1. Perform alias analysis to identify the virtual variables
2. Perform a pass over the program and insert Chi and Mu nodes for the virtual variables.
3. Convert to SSA with the virtual variables

In step 2, we insert a Mu node for each use of an aliased user variable. We insert a Chi node for each definition of an aliased user variable. We also insert a Chi at function calls for each actual aliased actual parameter. Using our small example from above, if we create a virtual variable, _v, to represent "a", "b", and "*p" then we add a Mu(_v)/Chi(_v) to each use/definition of "a", "b", or "*p". Note - the Chi(_v) is actually an assignment of the form _v = Chi(_v).

When the program is translated in SSA form, the virtual variables as as well as the user variables are renamed. This means that Phi nodes are created for the virtual variables and the virtual variables obey the single assignment rule of SSA form.

The scheme as described above works because each indirect variable (e.g., *p) represents at most one virtual variable (i.e., p points to at most one abstract location). Unfortunately, the scheme does not work when p may point to multiple locations. In the Shapiro/Horwitz algorithm, p may point to multiple locations. We need to extend our alias SSA representation to handle the Shapiro analysis.

Again, using the example from above, let's say the Shapiro algorithm partitions the user variables such that "p"->{"a"} or "p"->{"b"} (i.e., "p" points to "a" or to "b", but "a" and "b" are not aliases). This is different from the Steensgaard algorithm in which "p"->{"a", "b"} (i.e., "a" and "b" are aliases). To incorporate the Shapiro results into SSA form, we need a different scheme to represent the MayUse and MayDefs. For example, a use/def of "a" is not a use/def of "b", but a use/def of "*p" may be a use/def of "a" or "b".

We extend the basic scheme for including alias information by changing the meaning of a virtual variable. In our new scheme, a virtual variable represents multiple locations and we attach information to the variable to distinguish between the locations. We assign a superset and subset name to the virtual variable (yes, we need better names). Essentially, the superset name represents indirect variables (e.g., *p), and the subset name represents user variables. In our example, we can represent the relations among the variables using set notation, where a virtual variable represents the set {*p, {"a"}, {"b"}}. This means, "a" and "b" belong to distinct subsets but they are members of the same enclosing set which includes "*p".

In theory, our extended algorithm for adding alias information to SSA isn't much different that the original.

1. Perform alias analysis to identify the virtual variables
2. Perform a pass over the program and insert Chi and Mu nodes for the virtual variables.
3. Convert to SSA with the virtual variables

In Step 1, we create virtual variables using the new name scheme. The number of subset names depends upon the number of categories used in the Shapiro pointer analysis. In Step 2, inserting the Chi and Mu nodes is slightly different. We insert a Chi/Mu for a superset virtual variable for a definition/use of an indirect variable. We insert a Chi/Mu for a subset virtual variable for a definition/use of a user variable. In Step 3, we also convert a program to SSA, but we ignore the subset names for the purposes of creating the the MayDef/Use links. The subset names must be preserved for the optimizations to make use of the more precise alias information.

Note that the MayDef/Use links (and SSA numbers) ignore the subset name. But, the optimizations must check for the subset names when propagating information. Analysis information should only be propagated when the virtual variables are equivalent. Two virtual variables are equivalent under the following conditions: 1) The subset and superset names are the same, 2) One virtual variable only contains a superset name and both the superset names are the same.

The superset and subset distinctions are intended to help the optimization phases. We only want to propagate information for equivalent virtual variables. That is, when propagation information associated with subset name, we ignore different subset names but we must perform an appropriate action for a virtual variable with the same subset name or superset name. This is the main difference between the old scheme and the new scheme. In the old scheme, analysis information is always propagated down may def/use links. But, in the new scheme, we selectively propagate analysis information down the may def/use links.

Using our example, we create 3 virtual variables, _v#p, _v#p.a, and _v#p.b (our implementation actually uses numbers, so it's _v#0.0, _v#0.1 and _v#0.2, but here letters are used to hopefully make things clearer. The description of constant propagation (CP) below is not meant to match the algorithm in Scale. Instead, it is an attempt to illustrate how an optimization phase should use our SSA extensions.

We use the following program to illustrate the extensions (given that "p"->{"a"}, or "p"->{"b"}).

 a = 1;
 b = 2;
   = *p;
   = b;
   = a;
 

Using Steensgaard analysis (or Shapiro's analysis with 1 category), we cannot propagate 1 to the use of "a" or 2 to the use of "b". But, with Shapiro's analysis with multiple categories we can. After converting to SSA form:

 a = 1;  _v#p.a_1 = Chi(_v#p.a)
 b = 2;  _v#p.b_2 = Chi(_v#p.b_1)
   = *p; Mu(_v#p_2)
   = b;  Mu(_v#p.b_2)
   = a;  Mu(_v#p.a_2)
 

In the example, CP associates 1 with _v#p.a_1 and _v#p.b_1 after statement 1. The may def-use link for _v#p.a_1 points to the use of _v#p.b_1 at statement 2. Since the virtual variable at statement 2 is not equivalent to the virtual variable at statement 1, CP does not propagate the value 1 to _v#p.b_1. Instead, CP associates 2 with _v#p.b_2 and _v#p_2. Then, CP follows the may def-use links to the Mu nodes at statements 3, 4, 5. At statement 3, _v#p_2 is 2 so the use of "*p" can be replaced by 2. The same action occurs at statement 4 for "b". At statement 4, "a" can be replaced by 1.

If there is control flow:

 if ()
   a = 1; _v#p.a_1 = Chi(_v#p.a)
 else
   b = 2; _v#p.b_2 = Chi(_v#p.b_1)
       _v#p_3 = Phi(_v#p_1,_v#p_2)
  = *p;   Mu(_v#p_3)
  = b;    Mu(_v#p.b_3)
  = a;    Mu(_v#p.a_3)
 

In this case, CP associates not a constant with _v#p_3, _v#p.a_3, and _v#p.b_3 at the Phi node. Then, none of the uses can be replaced by a constant.

Note - in the presence of control flow, we only need to add Phi functions for superset names because the definition of a superset is equivalent to definitions for each of the subsets.

Fred Chow, Sun Chan, Shin-Ming Liu, Raymond Lo and Mark Streich. Effective Representation of Aliases and Indirect Memory Operations in SSA Form, In Compiler Construction, 6th International Conference, CC'96, Linkoping, Sweden, Apr 1996.

Field Summary

static boolean	classTrace True if traces are to be performed.
static boolean	doBackPropagation Set true to run special back propagation algorithm.
static boolean	inhibitCoalescing Set true to inhibit variable coalescing.
static boolean	onlyBPtoPhis Control back propagation.
static int	rpCase Specify the level of "extra branch" elimination to apply when removing phi functions.

Constructor Summary

SSA(Scribble scribble, PlaceIndirectOps pio)
Compute the dominance frontier for each node in a CFG.

Method Summary

static int	acnbbCnt() Return the count of the number of times we avoided creating a new basic block when exiting SSA form.
static int	acnbbfCnt() Return the count of the number of times we failed to avoid creating a new basic block because of variable coalescing.
void	addNewLoad(LoadDeclValueExpr load) Do any additional processing required when a load of a value is added to the CFG while it is in SSA form.
void	addNewNode(Chord s) Do any additional processing required when a node is added to the CFG while it is in SSA form.
void	addNewNodes(Vector<Chord> chords) Do any additional processing required when nodes are added to the CFG while it is in SSA form.
void	buildSSA() Build the SSA form with alias information.
static int	callSites() Return the number of call sites.
static int	coalesced() Return the count of the number of times a renamed variable was coalsced.
void	coalesceVariables() Coalesce variables, created by going into SSA form, into the original variable if there is no interference in the live ranges.
protected MayDef	createMayDefInfo(Expr expr, VirtualVar v) Create a may definition expression to repesent the aliasing characteristics of an expression.
protected MayUse	createMayUseInfo(Expr expr, VirtualVar v) Create a may use expression to repesent the aliasing characteristics of an expression.
VariableDecl	createRenamedVariable(VariableDecl original, boolean addOrig) Return a new RenamedVariableDecl.
static int	deadCFGNodes() Return the number of dead nodes removed.
static int	deadVariables() Return the count of variables removed because they were coalesced.
static int	newCFGNodes() Return the number of new nodes created.
static int	newVariableDecls() Return the current number of new variable declarations created.
static int	notCoalesced() Return the count of the number of times a renamed variable was not coalsced.
void	removePhis() Remove any PhiExprs still in the Scribble graph.
static int	vars() Return the number of variables processed.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

classTrace

public static boolean classTrace

True if traces are to be performed.

rpCase

public static int rpCase

Specify the level of "extra branch" elimination to apply when removing phi functions.

inhibitCoalescing

public static boolean inhibitCoalescing

Set true to inhibit variable coalescing. This is provided for debugging the compiler and it is desireable to see the generated code without coalescing.

doBackPropagation

public static boolean doBackPropagation

Set true to run special back propagation algorithm.

onlyBPtoPhis

public static boolean onlyBPtoPhis

Control back propagation.

Constructor Detail

SSA

public SSA(Scribble scribble,
           PlaceIndirectOps pio)

Compute the dominance frontier for each node in a CFG.

Parameters:

scribble - is the Scribble graph to be transformed

pio - is null or the class to use to process new CFG nodes added

See Also:

DominanceFrontier

Method Detail

newVariableDecls

public static int newVariableDecls()

Return the current number of new variable declarations created.

deadVariables

public static int deadVariables()

Return the count of variables removed because they were coalesced.

newCFGNodes

public static int newCFGNodes()

Return the number of new nodes created.

deadCFGNodes

public static int deadCFGNodes()

Return the number of dead nodes removed.

vars

public static int vars()

Return the number of variables processed.

callSites

public static int callSites()

Return the number of call sites.

acnbbCnt

public static int acnbbCnt()

Return the count of the number of times we avoided creating a new basic block when exiting SSA form.

acnbbfCnt

public static int acnbbfCnt()

Return the count of the number of times we failed to avoid creating a new basic block because of variable coalescing.

coalesced

public static int coalesced()

Return the count of the number of times a renamed variable was coalsced.

notCoalesced

public static int notCoalesced()

Return the count of the number of times a renamed variable was not coalsced.

addNewNode

public void addNewNode(Chord s)

Do any additional processing required when a node is added to the CFG while it is in SSA form. This method does not add use-def links.

addNewLoad

public void addNewLoad(LoadDeclValueExpr load)

Do any additional processing required when a load of a value is added to the CFG while it is in SSA form. This method does not add use-def links.

addNewNodes

public void addNewNodes(Vector<Chord> chords)

Do any additional processing required when nodes are added to the CFG while it is in SSA form. This method does not add use-def links.

buildSSA

public final void buildSSA()

Build the SSA form with alias information. Creating SSA form involves several steps. We assume that alias analysis has been performed and that alias groups have been created.

1. Assign virtual variables to indirect variables
2. Insert Mu and Chi annotations for all variables
3. Insert phi functions at merge points (the dominance frontier)
4. Rename scalar and virtual variables.
5. Compute zero version (TBD).

The actual implementation determines where to place the phi functions, then renames, and then actually inserts the phi functions.

createRenamedVariable

public final VariableDecl createRenamedVariable(VariableDecl original,
                                                boolean addOrig)

Return a new RenamedVariableDecl.

createMayDefInfo

protected MayDef createMayDefInfo(Expr expr,
                                  VirtualVar v)

Create a may definition expression to repesent the aliasing characteristics of an expression.

Parameters:

expr - the expression that the information is added to

v - the virtual variable that the may def is associated with

Returns:

the may definition expression

createMayUseInfo

protected MayUse createMayUseInfo(Expr expr,
                                  VirtualVar v)

Create a may use expression to repesent the aliasing characteristics of an expression.

Parameters:

expr - the expression that the information is added to

v - the virtual variable that the may def is associated with

Returns:

the may use expression

removePhis

public final void removePhis()

Remove any PhiExprs still in the Scribble graph.

This uses a different algorithm from the Briggs algorithm to handle both the "Lost Copy" and "Swap" problem when removing Phi functions from SSA form.

This is my algoritm for removing phi functions from a CFG in SSA form It is cheaper than the algorithm in Briggs, et al for our representation of basic blocks. The Briggs algorithm stops at each basic block and looks for phi functions in each of the block's successors. It then inserts copies at the end of the block for each phi function in each of the block's successors. For our representation, this means that a particular block is scanned from beginning to end once per in-coming CFG edge.

In my algorithm, I do the insert of the copy statements in the predecessors of the block as in the naive algorithm used by Cytron. This eliminates the multiple scan of each basic block for its phi functions.

Before the inserts are done, I order the copy statements to eliminate the "Lost Copy" problem. Then, to eliminate the "Swap" problem, when the destination of one phi function is used as the source of another phi function and that second phi function's destination is also used by another phi function, I insert copies to temporaries and copies from temporaries.

For example, consider the phi functions

   a1 <- phi(a2, b1)
   c1 <- phi(c2, c3)
   b1 <- phi(b2, a1)
   x1 <- phi(x2, a1)
 

These are ordered first for the second in-coming CFG edge as

   c1 <- phi(c2, c3)
   x1 <- phi(x2, a1)
   a1 <- phi(a2, b1)
   b1 <- phi(b2, a1)
 

because the x1 and c1 phi function destinations are not used by another phi function. Then, copies are inserted along the two in-coming CFG edges as

   left edge          right edge
 ----------------------------------
   a1 <- a2            c1 <- c3
   c1 <- c2            x1 <- a1
   b1 <- b2         a_t_1 <- b1        
   x1 <- x2         b_t_1 <- a1      
                       a1 <- a_t_1      
                       b1 <- b_t_1       
 

This algorithm is more conservative than necessary because it assumes that if a phi function has a destination that is used by another phi function whose destination is used by ..., then the two phi functions MAY exhibit the "Swap" problem. It would be possible, with more effort, to order these phi functions to eliminate the need to use some of the additional temporaries in some cases. For example, in the case

   x1 <- phi(x2, x3)
   y1 <- phi(y2, x1)
   z1 <- phi(z2, y1)
 

the copies for the second edge would be

      z1 <- y1
   x_t_0 <- x3
   y_t_0 <- x1
      x1 <- x_t_0
      y1 <- y_t_0
 

This could be reduced to

      z1 <- y1
   x_t_0 <- x3
      y1 <- x1
      x1 <- x_t_0
 

I believe that this case will be rare enough that the cost of detecting it is not warranted and that the extra copies will not be a problem.
James H. Burrill, February 3, 1999

coalesceVariables

public final void coalesceVariables()

Coalesce variables, created by going into SSA form, into the original variable if there is no interference in the live ranges. See Algorithm 19.17 in "Modern Compiler Implementation in Java" by Appel.

In the interest of execution speed, this algorithm does not preserve the may-def information.