Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.jikesrvm.compilers.opt.ssa
Class EnterSSA

java.lang.Object
  extended by org.jikesrvm.compilers.opt.driver.CompilerPhase
      extended by org.jikesrvm.compilers.opt.ssa.EnterSSA

public class EnterSSA
extends CompilerPhase

This compiler phase constructs SSA form.

This module constructs SSA according to the SSA properties defined in IR.desiredSSAOptions . See SSAOptions for more details on supported options for SSA construction.

The SSA construction algorithm is the classic dominance frontier based algorithm from Cytron et al.'s 1991 TOPLAS paper.

See our SAS 2000 paper Unified Analysis of Arrays and Object References in Strongly Typed Languages for an overview of Array SSA form. More implementation details are documented in SSA.java.

See Also:
SSA, SSAOptions, LTDominators

Field Summary
private static Constructor<CompilerPhase> constructor
          Constructor for this compiler phase
(package private) static boolean DEBUG
          flag to optionally print verbose debugging messages
private static int FOUND_NULL_TYPE
           
private  IR ir
          The governing IR
private  LiveAnalysis live
          Cached results of liveness analysis
private static int NO_NULL_TYPE
           
private  HashSet<Register> nonLocalRegisters
          A set of registers determined to span basic blocks
private  int[] numPredProcessed
          For each basic block, the number of predecessors that have been processed.
private  HashSet<Instruction> scalarPhis
          The set of scalar phi functions inserted
 
Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase
container
 
Constructor Summary
EnterSSA()
           
 
Method Summary
private  void computeNonLocals()
          Pass through the IR and calculate which registers are not local to a basic block.
private  void computeSSA(IR ir, boolean scalarsOnly, boolean backwards, Set<Object> heapTypes, boolean insertUsePhis, boolean insertPEIDeps, boolean excludeGuards)
          Calculate SSA form for an IR.
private  void copyHeapDefs(IR ir, HashMap<Instruction,HeapOperand<?>[]> store)
          Store a copy of the Heap variables each instruction defs.
private  TypeReference findParameterType(Register p)
          Find a parameter type.
 Constructor<CompilerPhase> getClassConstructor()
          Get a constructor object for this compiler phase
private  BitVector[] getDefSets()
          Calculate the set of blocks that contain defs for each symbolic register in an IR.
 String getName()
          Return a string identifying this compiler phase.
private  Register[] getSymbolicRegisters()
          Set up a mapping from symbolic register number to the register.
private  void insertHeapPhiFunctions(IR ir)
          Insert phi functions for heap array SSA heap variables.
private  void insertHeapVariables(IR ir, boolean backwards)
          Insert heap variables needed for Array SSA form.
private  void insertPhi(BasicBlock bb, Register r)
          Insert a phi function for a symbolic register at the head of a basic block.
private  void insertPhiFunctions(IR ir, BitVector[] defs, Register[] symbolics, boolean excludeGuards)
          Insert the necessary phi functions into an IR.
private  Instruction makePhiInstruction(Register r, BasicBlock bb)
          Create a phi-function instruction
private static TypeReference meetPhiType(Instruction s)
          Return the meet of the types on the rhs of a phi instruction SIDE EFFECT: bashes the Instruction scratch field.
private  void patchPEIgeneratedValues()
          Work around some problems with PEI-generated values and handlers.
 void perform(IR ir)
          Construct SSA form to satisfy the desired options in ir.desiredSSAOptions.
private  void prepare()
          Perform some calculations to prepare for SSA construction.
 boolean printingEnabled(OptOptions options, boolean before)
          Should the IR be printed either before or after performing this phase?
private  void rectifyPhiTypes()
           
private  void registerCalls(IR ir)
          Register every CALL instruction in this method with the implicit heap array SSA look aside structure.
private  void registerExits(IR ir)
          Register every instruction that can leave this method with the implicit heap array SSA look aside structure.
private  void registerHeapVariables(IR ir)
          Register every instruction in this method with the implicit heap array SSA lookaside structure.
private  void registerRenamedHeapPhis(IR ir)
          After performing renaming on heap phi functions, this routines notifies the SSA dictionary of the new names.
private  void removeAllUnreachablePhis(HashSet<Instruction> scalarPhis)
          Remove all phis that are unreachable
private  void removePhisThatDominateAllDefs(BitVector needsPhi, IR ir, BitVector defs)
          If node N dominates all defs of a register r, then N does not need a phi function for r; this function removes such nodes N from a Bit Set.
private  void removeUnreachableOperands(HashSet<Instruction> scalarPhis)
          Remove all unreachable operands from scalar phi functions NOT CURRENTLY USED
private  void renameHeapVariables(IR ir)
          Rename the implicit heap variables in the SSA form so that each heap variable has only one definition.
private  void renameSymbolicRegisters(Register[] symbolicRegisters)
          Rename the symbolic registers so that each register has only one definition.
private  void search(BasicBlock X, Stack<RegisterOperand>[] S)
          This routine is the guts of the SSA construction phase for scalars.
private  void search2(BasicBlock X, HashMap<Object,Stack<HeapOperand<Object>>> stacks)
          This routine is the guts of the SSA construction phase for heap array SSA.
 boolean shouldPerform(OptOptions options)
          Should this phase be performed under a guiding set of compiler options?
 
Methods inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase
dumpIR, dumpIR, getCompilerPhaseConstructor, getCompilerPhaseConstructor, newExecution, performPhase, reportAdditionalStats, setContainer, verify
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEBUG

static final boolean DEBUG
flag to optionally print verbose debugging messages

See Also:
Constant Field Values

ir

private IR ir
The governing IR

live

private LiveAnalysis live
Cached results of liveness analysis

nonLocalRegisters

private HashSet<Register> nonLocalRegisters
A set of registers determined to span basic blocks

scalarPhis

private final HashSet<Instruction> scalarPhis
The set of scalar phi functions inserted

numPredProcessed

private int[] numPredProcessed
For each basic block, the number of predecessors that have been processed.

constructor

private static final Constructor<CompilerPhase> constructor
Constructor for this compiler phase

NO_NULL_TYPE

private static final int NO_NULL_TYPE
See Also:
Constant Field Values

FOUND_NULL_TYPE

private static final int FOUND_NULL_TYPE
See Also:
Constant Field Values
Constructor Detail

EnterSSA

public EnterSSA()
Method Detail

shouldPerform

public final boolean shouldPerform(OptOptions options)
Should this phase be performed under a guiding set of compiler options?

Overrides:
shouldPerform in class CompilerPhase
Parameters:
options - the controlling compiler options
Returns:
true iff SSA is enabled under the options

getClassConstructor

public Constructor<CompilerPhase> getClassConstructor()
Get a constructor object for this compiler phase

Overrides:
getClassConstructor in class CompilerPhase
Returns:
compiler phase constructor

getName

public final String getName()
Return a string identifying this compiler phase.

Specified by:
getName in class CompilerPhase
Returns:
"Enter SSA"

printingEnabled

public final boolean printingEnabled(OptOptions options,
                                     boolean before)
Should the IR be printed either before or after performing this phase?

Overrides:
printingEnabled in class CompilerPhase
Parameters:
options - controlling compiler options
before - true iff querying before the phase
Returns:
true or false

perform

public final void perform(IR ir)
Construct SSA form to satisfy the desired options in ir.desiredSSAOptions. This module is lazy; if the actual SSA options satisfy the desired options, then do nothing.

Specified by:
perform in class CompilerPhase
Parameters:
ir - the IR on which to apply the phase

prepare

private void prepare()
Perform some calculations to prepare for SSA construction.

computeNonLocals

private void computeNonLocals()
Pass through the IR and calculate which registers are not local to a basic block. Store the result in the nonLocalRegisters field.

patchPEIgeneratedValues

private void patchPEIgeneratedValues()
Work around some problems with PEI-generated values and handlers. Namely, if a PEI has a return value, rename the result register before and after the PEI in order to reflect the fact that the PEI may not actually assign the result register.

computeSSA

private void computeSSA(IR ir,
                        boolean scalarsOnly,
                        boolean backwards,
                        Set<Object> heapTypes,
                        boolean insertUsePhis,
                        boolean insertPEIDeps,
                        boolean excludeGuards)
Calculate SSA form for an IR. This routine holds the guts of the transformation.

Parameters:
ir - the governing IR
scalarsOnly - should we compute SSA only for scalar variables?
backwards - If this is true, then every statement that can leave the procedure is considered to use every heap variable. This option is useful for backwards analyses such as dead store elimination.
heapTypes - If this variable is non-null, then heap array SSA form will restrict itself to this set of types. If this is null, build heap array SSA for all types.
insertUsePhis - Should we insert uphi functions for heap array SSA? ie., should we create a new name for each heap array at every use of the heap array? This option is useful for some analyses, such as our redundant load elimination algorithm.
insertPEIDeps - Should we model exceptions with an explicit heap variable for exception state? This option is useful for global code placement algorithms.
excludeGuards - Should we exclude guard registers from SSA?

insertHeapVariables

private void insertHeapVariables(IR ir,
                                 boolean backwards)
Insert heap variables needed for Array SSA form.

Parameters:
ir - the governing IR
backwards - if this is true, every statement that can leave the procedure uses every heap variable. This option is useful for backwards analyses

registerExits

private void registerExits(IR ir)
Register every instruction that can leave this method with the implicit heap array SSA look aside structure.

Parameters:
ir - the governing IR

registerCalls

private void registerCalls(IR ir)
Register every CALL instruction in this method with the implicit heap array SSA look aside structure. Namely, mark that this instruction defs and uses every type of heap variable in the IR's SSA dictionary.

Parameters:
ir - the governing IR

registerHeapVariables

private void registerHeapVariables(IR ir)
Register every instruction in this method with the implicit heap array SSA lookaside structure.

Parameters:
ir - the governing IR

insertHeapPhiFunctions

private void insertHeapPhiFunctions(IR ir)
Insert phi functions for heap array SSA heap variables.

Parameters:
ir - the governing IR

getDefSets

private BitVector[] getDefSets()
Calculate the set of blocks that contain defs for each symbolic register in an IR. Note: This routine skips registers marked already having a single static definition, physical registers, and guard registeres.

Returns:
an array of BitVectors, where element i represents the basic blocks that contain defs for symbolic register i

insertPhiFunctions

private void insertPhiFunctions(IR ir,
                                BitVector[] defs,
                                Register[] symbolics,
                                boolean excludeGuards)
Insert the necessary phi functions into an IR.

Algorithm:

For register r, let S be the set of all blocks that contain defs of r. Let D be the iterated dominance frontier of S. Each block in D needs a phi-function for r.

Special Java case: if node N dominates all defs of r, then N does not need a phi-function for r

Parameters:
ir - the governing IR
defs - defs[i] represents the basic blocks that define symbolic register i.
symbolics - symbolics[i] is symbolic register number i

removePhisThatDominateAllDefs

private void removePhisThatDominateAllDefs(BitVector needsPhi,
                                           IR ir,
                                           BitVector defs)
If node N dominates all defs of a register r, then N does not need a phi function for r; this function removes such nodes N from a Bit Set.

Parameters:
needsPhi - representation of set of nodes that need phi functions for a register r
ir - the governing IR
defs - set of nodes that define register r

insertPhi

private void insertPhi(BasicBlock bb,
                       Register r)
Insert a phi function for a symbolic register at the head of a basic block.

Parameters:
bb - the basic block
r - the symbolic register that needs a phi function

makePhiInstruction

private Instruction makePhiInstruction(Register r,
                                       BasicBlock bb)
Create a phi-function instruction

Parameters:
r - the symbolic register
bb - the basic block holding the new phi function
Returns:
the instruction r = PHI null,null,..,null

getSymbolicRegisters

private Register[] getSymbolicRegisters()
Set up a mapping from symbolic register number to the register.

TODO: put this functionality elsewhere.

Returns:
a mapping

renameSymbolicRegisters

private void renameSymbolicRegisters(Register[] symbolicRegisters)
Rename the symbolic registers so that each register has only one definition.

Note : call this after phi functions have been inserted.

Algorithm: from Cytron et. al 91 

  call search(entry)

  search(X):
  for each statement A in X do
     if A is not-phi
       for each r in RHS(A) do
            if !r.isSSA, replace r with TOP(S(r))
       done
     fi
    for each r in LHS(A) do
            if !r.isSSA
                r2 = new temp register
                push r2 onto S(r)
                replace r in A by r2
            fi
    done
  done (end of first loop)
  for each Y in succ(X) do
      j <- whichPred(Y,X)
      for each phi-function F in Y do
       replace the j-th operand (r) in RHS(F) with TOP(S(r))
     done
  done (end of second loop)
  for each Y in Children(X) do
    call search(Y)
  done (end of third loop)
  for each assignment A in X do
     for each r in LHS(A) do
      pop(S(r))
   done
  done (end of fourth loop)
  end
 




Parameters:
symbolicRegisters - mapping from integer to symbolic registers

search

private void search(BasicBlock X,
                    Stack<RegisterOperand>[] S)
This routine is the guts of the SSA construction phase for scalars. See renameSymbolicRegisters for more details.

Parameters:
X - basic block to search dominator tree from
S - stack of names for each register

renameHeapVariables

private void renameHeapVariables(IR ir)
Rename the implicit heap variables in the SSA form so that each heap variable has only one definition.

Algorithm: Cytron et. al 91 (see renameSymbolicRegisters)

Parameters:
ir - the governing IR

search2

private void search2(BasicBlock X,
                     HashMap<Object,Stack<HeapOperand<Object>>> stacks)
This routine is the guts of the SSA construction phase for heap array SSA. The renaming algorithm is analagous to the algorithm for scalars See renameSymbolicRegisters for more details.

Parameters:
X - the current basic block being traversed
stacks - a structure holding the current names for each heap variable used and defined by each instruction.

registerRenamedHeapPhis

private void registerRenamedHeapPhis(IR ir)
After performing renaming on heap phi functions, this routines notifies the SSA dictionary of the new names.

FIXME - this was commented out: delete it ?? RJG

Parameters:
ir - the governing IR

copyHeapDefs

private void copyHeapDefs(IR ir,
                          HashMap<Instruction,HeapOperand<?>[]> store)
Store a copy of the Heap variables each instruction defs.

Parameters:
ir - governing IR
store - place to store copies

rectifyPhiTypes

private void rectifyPhiTypes()

removeAllUnreachablePhis

private void removeAllUnreachablePhis(HashSet<Instruction> scalarPhis)
Remove all phis that are unreachable

removeUnreachableOperands

private void removeUnreachableOperands(HashSet<Instruction> scalarPhis)
Remove all unreachable operands from scalar phi functions

NOT CURRENTLY USED

meetPhiType

private static TypeReference meetPhiType(Instruction s)
Return the meet of the types on the rhs of a phi instruction

SIDE EFFECT: bashes the Instruction scratch field.

Parameters:
s - phi instruction

findParameterType

private TypeReference findParameterType(Register p)
Find a parameter type.

Given a register that holds a parameter, look at the register's use chain to find the type of the parameter

Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD