org.jikesrvm.compilers.opt.ssa

Class EnterSSA

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

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.

See Also:

SSA, SSAOptions, LTDominators

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	EnterSSA.PhiTypeInformation

Field Summary

Fields

Modifier and Type	Field and Description
private static Constructor<CompilerPhase>	constructor Constructor for this compiler phase
(package private) static boolean	DEBUG flag to optionally print verbose debugging messages
private IR	ir The governing IR
private LiveAnalysis	live Cached results of liveness analysis
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

Constructors

Constructor and Description
EnterSSA()

Method Summary

Modifier and Type	Method and Description
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)
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, Map<Instruction,EnterSSA.PhiTypeInformation> phiTypes) Return the meet of the types on the rhs of a phi instruction
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)
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)
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

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.

• If using pruned SSA, compute liveness.
• If using semi-pruned SSA, compute non-local registers

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

excludeGuards - whether guard registers should be excluded from SSA

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)

removeUnreachableOperands

private void removeUnreachableOperands(HashSet<Instruction> scalarPhis)

meetPhiType

private static TypeReference meetPhiType(Instruction s,
                                         Map<Instruction,EnterSSA.PhiTypeInformation> phiTypes)

Return the meet of the types on the rhs of a phi instruction

Parameters:

s - phi instruction

phiTypes - TODO

Returns:

the meet of the types

findParameterType

private TypeReference findParameterType(Register p)