org.jikesrvm.compilers.opt.dfsolver
Class DF_System

java.lang.Object
  org.jikesrvm.compilers.opt.dfsolver.DF_System

Direct Known Subclasses:

DominatorSystem, IndexPropagationSystem

public abstract class DF_System
extends Object

Represents a system of Data Flow equations

Implementation Note: The set of equations is internally represented as a graph (actually a SpaceEffGraph). Each dataflow equation is a node in the graph. If a dataflow equation produces a lattice cell value that is used by another equation, the graph has a directed edge from the producer to the consumer. Fixed-point iteration proceeds in a topological order according to these edges.

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

EAGER

private final boolean EAGER

equations

private final Graph equations

The equations that comprise this dataflow system.

workList

protected final TreeSet<DF_Equation> workList

Set of equations pending evaluation

newEquations

private final HashSet<DF_Equation> newEquations

Set of equations considered "new"

cells

protected final DF_Solution cells

The lattice cells of the system: Mapping from Object to DF_LatticeCell

dfComparator

private static final Comparator<DF_Equation> dfComparator

DF_System

public DF_System()

DF_System

public DF_System(boolean eager)

solve

public void solve()

Solve the set of dataflow equations.

PRECONDITION: equations are set up

getSolution

public DF_Solution getSolution()

Return the solution of the dataflow equation system. This is only valid after calling solve()

Returns:

the solution

toString

public String toString()

Return a string representation of the system

Overrides:

toString in class Object

Returns:

a string representation of the system

getEquations

public Enumeration<DF_Equation> getEquations()

Return an Enumeration over the equations in this system.

Returns:

an Enumeration over the equations in this system

getNumberOfEquations

public int getNumberOfEquations()

Get the number of equations in this system

Returns:

the number of equations in this system

addToWorkList

public void addToWorkList(DF_Equation eq)

Add an equation to the work list.

Parameters:

eq - the equation to add

addNewEquationsToWorkList

public void addNewEquationsToWorkList()

Add all new equations to the work list.

addAllEquationsToWorkList

public void addAllEquationsToWorkList()

Add all equations to the work list.

changedCell

public void changedCell(DF_LatticeCell cell)

Call this method when the contents of a lattice cell changes. This routine adds all equations using this cell to the set of new equations.

Parameters:

cell - the lattice cell that has changed

findOrCreateCell

protected DF_LatticeCell findOrCreateCell(Object key)

Find the cell matching this key. If none found, create one.

Parameters:

key - the key for the lattice cell.

newEquation

protected void newEquation(DF_LatticeCell lhs,
                           DF_Operator operator,
                           DF_LatticeCell op1)

Add an equation with one operand on the right-hand side.

Parameters:

lhs - the lattice cell set by this equation

operator - the equation operator

op1 - first operand on the rhs

newEquation

void newEquation(DF_LatticeCell lhs,
                 DF_Operator operator,
                 DF_LatticeCell op1,
                 DF_LatticeCell op2)

Add an equation with two operands on the right-hand side.

Parameters:

lhs - the lattice cell set by this equation

operator - the equation operator

op1 - first operand on the rhs

op2 - second operand on the rhs

newEquation

void newEquation(DF_LatticeCell lhs,
                 DF_Operator operator,
                 DF_LatticeCell op1,
                 DF_LatticeCell op2,
                 DF_LatticeCell op3)

Add an equation with three operands on the right-hand side.

Parameters:

lhs - the lattice cell set by this equation

operator - the equation operator

op1 - first operand on the rhs

op2 - second operand on the rhs

op3 - third operand on the rhs

newEquation

protected void newEquation(DF_LatticeCell lhs,
                           DF_Operator operator,
                           DF_LatticeCell[] rhs)

Add an equation to the system with an arbitrary number of operands on the right-hand side.

Parameters:

lhs - lattice cell set by this equation

operator - the equation operator

rhs - the operands on the rhs

addEquation

void addEquation(DF_Equation eq)

Add an existing equation to the system

Parameters:

eq - the equation

getCell

public DF_LatticeCell getCell(Object key)

Return the DF_LatticeCell corresponding to a key.

Parameters:

key - the key

Returns:

the LatticeCell if found. null otherwise

addCellAppearancesToWorkList

public void addCellAppearancesToWorkList(DF_LatticeCell cell)

Add all equations which contain a given cell to the work list.

Parameters:

cell - the cell in question

initializeLatticeCells

protected abstract void initializeLatticeCells()

Initialize all lattice cells in the system.

initializeWorkList

protected abstract void initializeWorkList()

Initialize the work list for iteration.j

makeCell

protected abstract DF_LatticeCell makeCell(Object key)

Create a new lattice cell, referenced by a given key

Parameters:

key - key to look up the new cell with

Returns:

the newly created lattice cell

updateWorkList

protected void updateWorkList(DF_Equation eq)

Update the worklist, assuming that a particular equation has been re-evaluated

Parameters:

eq - the equation that has been re-evaluated.

numberEquationsTopological

private void numberEquationsTopological()

Number the equations in topological order.

PRECONDITION: Already called addGraphEdges()

Algorithm:

• 1. create a DAG of SCCs
• 2. number this DAG topologically
• 3. walk through the DAG and number nodes as they are encountered

showGraphStats

void showGraphStats()

Debugging aid: print statistics about the dataflow system.