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.

Field Summary

Fields

Modifier and Type	Field and Description
protected DF_Solution	cells The lattice cells of the system: Mapping from Object to DF_LatticeCell
private static boolean	DEBUG
private static Comparator<DF_Equation>	dfComparator
private boolean	EAGER
private Graph	equations The equations that comprise this dataflow system.
private HashSet<DF_Equation>	newEquations Set of equations considered "new"
protected TreeSet<DF_Equation>	workList Set of equations pending evaluation

Constructor Summary

Constructors

Constructor and Description
DF_System()
DF_System(boolean eager)

Method Summary

Modifier and Type	Method and Description
void	addAllEquationsToWorkList() Add all equations to the work list.
void	addCellAppearancesToWorkList(DF_LatticeCell cell) Add all equations which contain a given cell to the work list.
(package private) void	addEquation(DF_Equation eq) Add an existing equation to the system
void	addNewEquationsToWorkList() Add all new equations to the work list.
void	addToWorkList(DF_Equation eq) Add an equation to the work list.
void	changedCell(DF_LatticeCell cell) Call this method when the contents of a lattice cell changes.
protected DF_LatticeCell	findOrCreateCell(Object key) Finds the cell matching this key.
DF_LatticeCell	getCell(Object key) Return the DF_LatticeCell corresponding to a key.
Enumeration<DF_Equation>	getEquations() Return an Enumeration over the equations in this system.
int	getNumberOfEquations() Get the number of equations in this system
DF_Solution	getSolution() Return the solution of the dataflow equation system.
protected abstract void	initializeLatticeCells() Initialize all lattice cells in the system.
protected abstract void	initializeWorkList() Initialize the work list for iteration.j
protected abstract DF_LatticeCell	makeCell(Object key) Create a new lattice cell, referenced by a given key
protected void	newEquation(DF_LatticeCell lhs, DF_Operator operator, DF_LatticeCell op1) Add an equation with one operand on the right-hand side.
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.
(package private) 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.
(package private) 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.
private void	numberEquationsTopological() Number the equations in topological order.
(package private) void	showGraphStats() Debugging aid: print statistics about the dataflow system.
void	solve() Solve the set of dataflow equations.
String	toString() Return a string representation of the system
protected void	updateWorkList(DF_Equation eq) Update the worklist, assuming that a particular equation has been re-evaluated

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

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

Constructor Detail

DF_System

public DF_System()

DF_System

public DF_System(boolean eager)

Method Detail

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)

Finds the cell matching this key. If none found, creates one.

Parameters:

key - the key for the lattice cell

Returns:

a suitable 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.