====== Static Single Assignment Form ====== 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 i1 and i2). 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 [[http://wiki.bu.ost.ch/infoportal/literatur/moessenboeck|Hanspeter 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. [{{ .:ssanode.png?150&direct | //Structure of an SSANode//}}] When generating the CFG we already create instances of type SSANode. ===== SSA Instructions ===== All Bytecode instructions of all nodes are translated into SSA instructions. The SSA instructions can be categorized as follows: [{{ ssainstructions.png?770&direct | //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 IMPORTANT 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//. ===== SSA Value ===== All operands and results of the SSA instructions are of type SSAValue. [{{ .:ssavalue.png?150&direct | //Structure of a SSAValue// }}] ===== State Array ===== 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. [{{ .:statearray.png?150&direct | //State array with operand stack and locals// }}] 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. ===== Phi-Functions ===== We use phi-functions whenever a node has more than one predecessors. A phi-function combines a local variable from the exit sets of these predecessors. The resulting value (result of the phi-function) goes into the entry set of the actual node. Such phi-functions serve the following purpose: all the combined locals (operands of a phi-function) should be assigned the same register. ===Special case: loop header=== During the first traverse all necessary phi-functions will be generated. At this stage, not all parameters are known. Such parameters are added during the second traverse. ===Elimination of redundant phi-functions=== Two cases have to be considered: Case 1: x = [y,x,x,...,x] here, all operands except one are the same as the assigned value. Such phi-function can occur in loop headers, if the value of a variable does not change in the loop. The value can be replaced by y. Case 2: x = [x,x,...,x] here, all operands are the same as the assigned value. such phi-functions can occur when other phi-functions are eliminated. Simply replace with the value x. Phi-functions are never really deleted. They are marked as deletet, because even deleted phi-functions are used for register allocation. ===== Loading of Parameters ===== Every local variable must be assigned before it can be used. However, a parameter has no assignment instruction in the SSA. Therefore, before the first use of a parameter a SSA-instruction //loadLocal// must be inserted. ===Special case: phi-function=== If a phi-function uses a parameter which is not yet loaded, the SSA-instruction //loadLocal// must be inserted at the end of the appropriate predecessors. If these do not exist (e.g. if an //else// block is not present) a node must be created and inserted. ===== Traversing a Node ===== - Determine the entry set * Node has no predecessor -> create new entry set * Node has one predecessor -> copy exit set of predecessor. Single exception to this rule is when the node itself is a loop header. In that case a phi-function has to be created for each local, as these locals could have been set in the node. * Node has several predecessors -> merge exit sets with the aid of phi-functions. - If loop header and first visit -> create phi-functions for all locals. - If loop header and second visit -> the exit sets of all predecessor are merged while parameters need special care. If necessary, a load parameter instruction must be inserted in the dominator of the node. - If no loop header -> create phi-functions if a local is set in several predecessors while their types are the same (if the types differ, different locals occupy the same slot in the state array). For parameters a phi function has to be created in any case. Is a local itself a phi-function, you have to determine whether it was created within this node. If not, create a new phi-function with the existing one as a parameter to it. - Delete redundant phi-functions. - Traverse Bytecode and create ssa instructions, track locals. - Assign locals to exit set. ===== Building the SSA ===== When building the SSA the nodes must be traversed as follows: * A node may only be traversed after all its predecessors have been traversed. (with the exception of loop headers) * Loop headers must be traversed twice, because when they are traversed for the first time not all its predecessors have been traversed. ===== Insertion of Register Moves ===== The phi-functions will be resolved when register allocation takes places. That means its operands and its result are assigned the same register. For this, the index into //locals// is used. \\ Generally the operands and the result have the same index. However, there are two cases, where this is not true. ===Conditional Operator=== boolean a = i > 10? b : c; In that case all three variables of type boolean occupy another index in the exit-set. === Assignment after Branch === if (condition) a = 1; else a = 2; b = a; Let's assume that //a// has index 0 and //b// has index 1. The ssa instruction for //a = 1// loads the constant 1. //b = a// does not create any ssa instruction, though //b// is the result of the phi-function with constants 1 and 2 as operands. For these two cases a new ssa instruction //regMove// has to be inserted into all predecessors of the node with the phi-function. It simply copies the ssa value into a new value. The exit-sets of the predecessors have to be updated as well. ===== Handling Exceptions ===== Catch clauses of exceptions need special treatment. The exception is put on the stack by the JVM. try { ... } catch (Exception e) {...} The first Bytecode instruction in a catch clause is a //astore// instruction. As we have no JVM, we will pass the exception like a parameter in a prefixed register. However, we must make sure, that when the variable //e// is used in the catch node, we must introduce a //loadLocal// instruction. This instruction is marked with the boolean //firstInCatch// in order to assign the right register later. Special care must be paid to the fact, that //e// might occupy the same index in the state array as a variable of the try block. For this purpose a SSA-Node has the fields //excVarIndex//, //loadLocalExc// and //excVarLoaded//. ===== Handling iinc Instructions in Loops ===== The java virtual machine relies heavily on its operand stack. All operands of any instruction is first loaded onto this stack. However, there is one exception to this rule. The //iinc//-instruction modifies the local variable in the local variable frame directly. This allows for implementing pre- and postincrement operators as given in the following example: a[i++] = 10; The corresponding Bytecode is aload [a] iload [i] iinc i,1 bipush 10 iastore //i// is first loaded onto the operand stack, afterwards the local variable //i// is incremented and finally, the array field is stored. Please note, that the value of //i// which is used for //iastore// is the unincremented value! This poses a problem if the code is placed in a loop. In such a case, a phi-function is necessary for the variable //i//. As we replace the local variable frame and the operand stack with our entry and exit sets, the phi-function simply merges every instance of //i// into the same SSAValue (with the same index and ultimately the same register). When this happens, the order of incrementation and use of //i// might be wrong. A similar example is: a[i] = i++; with the Bytecode aload [a] iload [i] iload [i] iinc i,1 iastore Or still another example: a[i] = ++i; with the Bytecode aload [a] iload [i] iinc i,1 iload [i] iastore If the operand stack is not empty at the occurence of an //iinc//-instruction we must do the following: - insert a register move instruction before the //iinc//-instruction - the result of this register move instruction becomes an operand of the //iinc//-instruction - as soon as the operand stack becomes empty, another register move instruction with the result of the //iinc//-instruction has to be inserted - the result of this second register move instruction has to be added as operand to the corresponding phi-function. ===== Creating the Line Number Table ===== For the source lookup the debugger needs information about which SSA instruction belongs to which line number in the source. The information about line numbers and Bytecode instruction can be found in the //LineNumberTable//. This table must be extended to include ssa information as well. Care must be given to cases where SSA nodes are deleted or new nodes inserted.