The Static Single Assignment Form (SSA) is an intermediate form which allows various optimizations and facilitates register allocation. The main point of the SSA is that each variable is assigned a value only once. Each new assignment leads to a new instance of this variable (indicated by i₁ and i₂). When optimizing, subsequent instuctions can simply use the definition and the value of these variables (e.g. for constant folding). The register allocation can be made more efficient as the living ranges of the instances are generally very short. More information about the creation and usage of the SSA can be found in H. Mössenböck.

The SSA is stored into nodes similar to the CFG nodes. For this purpose we define SSANode as an extension of CFGNode.

Structure of an SSANode

When generating the CFG we already create instances of type SSANode.

All Bytecode instructions of all nodes are translated into SSA instructions. The SSA instructions can be categorized as follows:

Classes for SSA Instructions

As the figure shows, the following types are available

• NoOpnd: no operands, pushes the result to the stack
• NoOpndRef: no operands, get reference from constant pool, pushes the result to the stack
• Monadic: fetches one operand from the stack, pushes the result to the stack
• MonadicRef: fetches one operand from the stack, get reference from constant pool, pushes the result to the stack
• Dyadic: fetches two operands from the stack, pushes the result to the stack
• DyadicRef: fetches two operands from the stack, get reference from constant pool, pushes the result to the stack
• Triadic: fetches three operands from the stack, pushes the result to the stack
• Branch
• Call
• PhiFunction

Each instruction has an opcode (ssaOpcode). This can be of

• sCloadConst:
• sCloadLocal:
• sCloadFromField, sCstoreToField: accessing class and instance fields
• sCloadFromArray, sCstoreToArray: accessing array elements
• sCadd, sCsub, sCmul, sCdiv, sCrem, sCneg: arithmetic operations
• sCshl, sCshr, sCushr: shift operations
• sCand, sCor, sCxor: logical operations
• sCconvInt, sCconvLong, sCconvFloat, sCconvDouble: type conversions
• sCcmpl, sCcmpg: comparing long, float and double
• sCinstanceof, sCcheckcast, sCthrow: checking
• sCalength: array length
• sCbranch, sCswitch, sCcall, sCnew, sCreturn: branching and method calls
• sCregMove, sCPhiFunc: phi functions

Storing to fields (sCstoreToField) can be of type MonadicRef or DiadicRef. MonadicRef is used when accessing class fields. Here the reference is the field whereas the operand is the value to store. DyadicRef is used when accessing instance fields. Here the reference is the field whereas the first operand contains the reference to the object and the second operand is the value to store. The reference to the field is used to hold information about the type of the field and the offset within the object. A similar case is sCloadFromField.
Some SSA instructions don't produce a result, such as sCstoreToField. In this case, the SSA instruction allocates a result of type void.

All operands and results of the SSA instructions are of type SSAValue.

For each SSANode a state array is carried along with information about local variables and the operand stack. The state of this array at the beginning of a node is the entrySet, at the end of a node the exitSet. The state array holds references to SSAValues. This values are results of previous SSA instructions. The state array shows the state of the operand stack and indicates which instruction created a certain local variable. When generating SSA instructions the following rules apply:

• Loading of a constant: Create new SSA instruction, result is this constant value, locals is not modified, constant is put on the operand stack.
• Loading of a local variable with index i: Creates no SSA instruction, locals is not modified, the value in locals with index i is put onto the operand stack.
• Loading of a local variable which is not yet initialized: Create new SSA instruction, result is value of local variable, locals is modified.
• Arithmetic operation (as example of general instruction): Create new SSA instruction, fetch 2 values from operand stack, locals is not modified, push result onto operand stack.
• Storing of a local variable: Creates no SSA instruction, fetch value from operand stack and store it in locals.

Sind eine Erweiterung der SSAInstruction und werden benötigt, wenn ein Knoten 2 oder mehr direkte Vorgänger hat. Mittels der Phi Funktion werden die Locals in den ExitSets der Vorgänger Zusammengeführt. Das Resultat wird dann im EntrySet des aktuellen Knotens abgelegt.

Spezialfall Loopheader:
Beim der ersten maTraversierung werden alle Phi-Funktionen angelegt, wobei noch nicht alle Parameter bekannt sind. Diese werden bei der zweiten Traversierung dann hinzugefügt.

Eliminieren von redundanten Phi-Funktionen:
Gemäss {Moessenboeck00} gibt es 2 Fälle von redundanten Phi Funktionen. Fall 1:

  x = [y,x,x,...,x]

hier sind alle bis auf einen Operand gleich wie auf der linke Seite des Gleichheitszeichen. Diese Phi-Funktionen können in Loopheaders auftreten wenn eine Variable in der Schleife nicht verändert wird. Somit kann diese mit y ersetzt werden.

Fall 2:

 x = [x,x,...,x]

hier sind alle Operanden gleich wie auf der Linken Seite des Gleichheitszeichen. Diese Phi Funktionen können durch das Eliminieren von Phi- Funktionen entstehen. Diese könne direkt mit x ersetzt werden.

Die Phi-Funktion selbst kann aber nur als gelöscht markiert werden. Da sie bei der Registerreservierung dennoch gebraucht werden.

Jede lokale Variable muss zugewiesen sein, bevor sie verwendet werden kann. Ein Parameter wird jedoch beim Aufruf der Methode übergeben, somit existiert in der SSA keine Zuweisung. Daher muss direkt vor dem ersten Gebrauch des Parameters eine SSAInstruction „loadLoacal“ eingefügt werden. Diese sorgt dann bei der Codegenerierung, dass die Variable geladen wird.

Spezialfall Phi-Funktion:
Benutzt diese einen Parameter welcher noch nicht geladen ist, so wird die SSAInstruction „loadLocal“ am Ende des zugehörigen direkten Vorgängers eingefügt. Existiert dieser nicht (z.B. bei einem nicht implementiertem else-Block einer if-Anweisung), so muss dieser Knoten erzeugt und eingefügt werden.

1. Bestimmen des EntrySet
   • Knoten hat kein Vorgänger → neues EntrySet erzeugen
   • Knoten hat einen Vorgänger → ExitSet des Vorgängers kopieren
     • Einzige Ausnahme ist, wenn der Knoten selbst ein Loopheader ist. Dann muss obwohl es nichts zum zusammenführen gibt für jeden Local eine PhiFunktion erzeugt werden. Diese werden dann für die Registerreservierung benötigt.
   • Knoten hat mehrere Vorgänger → ExitSets mittels Phi Funktionen zusammenführen.
     • Wenn Loopheader und erster Besuch → für alle Locals jeweils eine PhiFunktion erzeugen.
     • Wenn Loopheader und zweiter Besuch → alle ExitsSets der Predecessoren werden zusammengeführt, wobei Parameter speziell berücksichtigt werden müssen und gegebenen falls muss eine loadParameter Instruktion beim Dominator eingefügt werden.
     • Wenn kein Loopheader → Werden nur PhiFunktionen erzeugt, wenn ein Local in mehreren Predecessoren gesetzt wurden und diese auch vom selben Typ sind.
       • Wobei für Parameter immer eine PhiFunktion erzeugt wird. Unter Berücksichtigung ob eine LoadParamter Instruktion erzeugt werden muss.
       • Ist der Local bereits eine PhiFunktion so muss bestimmt werden, ob diese in diesem Knoten erzeugt wurde. Ist dies nicht der Fall so wird eine neue PhiFunktion erzeugt und die bestehende wird als Parameter übergeben.
2. Redundante PhiFunktionen löschen.
3. Bytecode traversieren und jeweilige SSAInstruction erzeugen. Gleichzeitig auch locals nachführen.
4. Locals dem ExitSet zuweisen.

Beim Bilden der SSA ist die Reihenfolge, in der die Knoten traversiert werden, zu berücksichtigen. Dabei gilt:

• Ein Knoten darf nur traversiert werden, wenn alle seine direkten Vorgänger bereits traversiert worden sind. (Ausnahme Loopheaders)
• Loopheaders müssen 2-mal traversiert werden, da beim ersten mal noch nicht alle direkten Vorgänger traversiert worden sind.

Die Phi-Funktionen müssen aufgelöst werden. Das heisst, alle ihre Operanden und ihr Resultat erhalten das gleiche Register zugewiesen. Dazu wird der Index in den locals verwendet.
Üblicherweise haben die Operanden und das Resultat auch den gleichen Index. Es gibt aber zwei Fälle, wo das nicht zutrifft. Für diese Fälle muss in allen Vorgängerknotens des Knotens mit der phi-Funktion ein Registermoves eingefügt werden. Ebenso müssen die Exit-Sets dieser Vorgängerknoten angepasst werden.

  boolean a = i > 10? b : c;

Hier belegen alle drei Variablen vom Typ Boolean (a,b,c) je einen anderen Index im Exit-Set.

  if (condition)
    a = 1;
  else 
    a = 2;
  b = a;

Hier hat a z.B. den Index 0 und b den Index 1. Die SSA-Form von a = 1 lädt die Konstante 1. b = a taucht in der SSA-Form nicht auf, resp. b ist das Resultat der phi-Funktion mit den Konstanten 1 und 2 als Operanden.

Für das Source-Lookup des Debuggers muss nachher bekannt sein, welche Instruktion zu welcher Sourcezeile gehört. Diese Information findet sich im Bytecode in der LineNumberTable. Diese Information muss auch in die SSA übernommen werden. Achtung: gelöschte oder neu eingefügte Knoten müssen speziell behandelt werden.