org.jikesrvm.compilers.opt.ssa

Class IndexPropagationSystem

java.lang.Object

org.jikesrvm.compilers.opt.dfsolver.DF_System

org.jikesrvm.compilers.opt.ssa.IndexPropagationSystem

class IndexPropagationSystem
extends DF_System

Represents a set of dataflow equations used to solve the index propagation problem.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static class	IndexPropagationSystem.MeetOperator Represents a MEET function (intersection) over Cells.
(package private) class	IndexPropagationSystem.UpdateDefArrayOperator Represents an UPDATE_DEF function over two ArrayCells.
(package private) class	IndexPropagationSystem.UpdateDefObjectOperator Represents an UPDATE_DEF function over two ObjectCells.
(package private) static class	IndexPropagationSystem.UpdateUseArrayOperator Represents an UPDATE_USE function over two ArrayCells.
(package private) static class	IndexPropagationSystem.UpdateUseObjectOperator Represents an UPDATE_USE function over two ObjectCells.

Field Summary

Fields

Modifier and Type	Field and Description
private IR	ir The governing IR.
private static IndexPropagationSystem.MeetOperator	MEET object representing the MEET operator
private SSADictionary	ssa Heap Array SSA lookaside information for the IR.
private GlobalValueNumberState	valueNumbers Results of global value numbering

Fields inherited from class org.jikesrvm.compilers.opt.dfsolver.DF_System

cells, workList

Constructor Summary

Constructors

Constructor and Description
IndexPropagationSystem(IR _ir) Set up the system of dataflow equations.

Method Summary

Modifier and Type	Method and Description
(package private) void	addUpdateArrayDefEquation(HeapVariable<?> A1, HeapVariable<?> A2, Object array, Object index) Add an equation to the system of the form L(A1) = updateDef(L(A2), <VALNUM(array),VALNUM(index)>)
(package private) void	addUpdateArrayUseEquation(HeapVariable<?> A1, HeapVariable<?> A2, Object array, Object index) Add an equation to the system of the form L(A1) = updateUse(L(A2), <VALNUM(array),VALNUM(index)>)
(package private) void	addUpdateObjectDefEquation(HeapVariable<?> A1, HeapVariable<?> A2, int valueNumber) Add an equation to the system of the form L(A1) = updateDef(L(A2), VALNUM(address))
(package private) void	addUpdateObjectUseEquation(HeapVariable<?> A1, HeapVariable<?> A2, int valueNumber) Add an equation to the system of the form L(A1) = updateUse(L(A2), VALNUM(address))
protected void	initializeLatticeCells() Initialize the lattice variables.
protected void	initializeWorkList() Initialize the work list for the dataflow equation system.
protected DF_LatticeCell	makeCell(Object o) Create an DF_LatticeCell corresponding to an HeapVariable
(package private) void	processALoad(Instruction s) Update the set of dataflow equations to account for the actions of ALoad instruction s The load is of the form x = A[k].
(package private) void	processAStore(Instruction s) Update the set of dataflow equations to account for the actions of AStore instruction s The store is of the form A[k] = val.
(package private) void	processCall(Instruction s) Update the set of dataflow equations to account for the actions of CALL instruction.
(package private) void	processLoad(Instruction s) Update the set of dataflow equations to account for the actions of a Load instruction The load is of the form x = A[k].
(package private) void	processNew(Instruction s) Update the set of dataflow equations to account for the actions of allocation instruction s
(package private) void	processPhi(Instruction s) Update the set of dataflow equations to account for the actions of Phi instruction.
(package private) void	processStore(Instruction s) Update the set of dataflow equations to account for the actions of a Store instruction.
(package private) void	setupEquations() Walk through the IR and add dataflow equations for each instruction that affects the values of Array SSA variables.

Methods inherited from class org.jikesrvm.compilers.opt.dfsolver.DF_System

addAllEquationsToWorkList, addCellAppearancesToWorkList, addNewEquationsToWorkList, addToWorkList, changedCell, findOrCreateCell, getCell, getEquations, getNumberOfEquations, getSolution, newEquation, newEquation, solve, toString, updateWorkList

Methods inherited from class java.lang.Object

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

Field Detail

ir

private final IR ir

The governing IR.

ssa

private final SSADictionary ssa

Heap Array SSA lookaside information for the IR.

valueNumbers

private final GlobalValueNumberState valueNumbers

Results of global value numbering

MEET

private static final IndexPropagationSystem.MeetOperator MEET

object representing the MEET operator

Constructor Detail

IndexPropagationSystem

IndexPropagationSystem(IR _ir)

Set up the system of dataflow equations.

Parameters:

_ir - the IR

Method Detail

makeCell

protected DF_LatticeCell makeCell(Object o)

Create an DF_LatticeCell corresponding to an HeapVariable

Specified by:

makeCell in class DF_System

Parameters:

o - the heap variable

Returns:

a new lattice cell corresponding to this heap variable

initializeLatticeCells

protected void initializeLatticeCells()

Initialize the lattice variables.

Specified by:

initializeLatticeCells in class DF_System

initializeWorkList

protected void initializeWorkList()

Initialize the work list for the dataflow equation system.

Specified by:

initializeWorkList in class DF_System

setupEquations

void setupEquations()

Walk through the IR and add dataflow equations for each instruction that affects the values of Array SSA variables.

processLoad

void processLoad(Instruction s)

Update the set of dataflow equations to account for the actions of a Load instruction

The load is of the form x = A[k]. let A_1 be the array SSA variable before the load, and A_2 the array SSA variable after the store. Then we add the dataflow equation L(A_2) = updateUse(L(A_1), VALNUM(k))

Intuitively, this equation represents the fact that A[k] is available after the store

Parameters:

s - the Load instruction

processStore

void processStore(Instruction s)

Update the set of dataflow equations to account for the actions of a Store instruction.

The store is of the form A[k] = val. let A_1 be the array SSA variable before the store, and A_2 the array SSA variable after the store. Then we add the dataflow equation L(A_2) = updateDef(L(A_1), VALNUM(k))

Intuitively, this equation represents the fact that A[k] is available after the store

Parameters:

s - the Store instruction

processALoad

void processALoad(Instruction s)

Update the set of dataflow equations to account for the actions of ALoad instruction s

The load is of the form x = A[k]. let A_1 be the array SSA variable before the load, and A_2 the array SSA variable after the load. Then we add the dataflow equation L(A_2) = updateUse(L(A_1), VALNUM(k))

Intuitively, this equation represents the fact that A[k] is available after the store

Parameters:

s - the Aload instruction

processAStore

void processAStore(Instruction s)

Update the set of dataflow equations to account for the actions of AStore instruction s

The store is of the form A[k] = val. let A_1 be the array SSA variable before the store, and A_2 the array SSA variable after the store. Then we add the dataflow equation L(A_2) = update(L(A_1), VALNUM(k))

Intuitively, this equation represents the fact that A[k] is available after the store

Parameters:

s - the Astore instruction

processNew

void processNew(Instruction s)

Update the set of dataflow equations to account for the actions of allocation instruction s

Parameters:

s - the New instruction

processCall

void processCall(Instruction s)

Update the set of dataflow equations to account for the actions of CALL instruction.

Parameters:

s - the Call instruction

processPhi

void processPhi(Instruction s)

Update the set of dataflow equations to account for the actions of Phi instruction.

The instruction has the form A1 = PHI (A2, A3, A4); We add the dataflow equation L(A1) = MEET(L(A2), L(A3), L(A4))

Parameters:

s - the Phi instruction

addUpdateObjectDefEquation

void addUpdateObjectDefEquation(HeapVariable<?> A1,
                                HeapVariable<?> A2,
                                int valueNumber)

Add an equation to the system of the form L(A1) = updateDef(L(A2), VALNUM(address))

Parameters:

A1 - variable in the equation

A2 - variable in the equation

valueNumber - value number of the address

addUpdateObjectUseEquation

void addUpdateObjectUseEquation(HeapVariable<?> A1,
                                HeapVariable<?> A2,
                                int valueNumber)

Add an equation to the system of the form

 L(A1) = updateUse(L(A2), VALNUM(address))
 

Parameters:

A1 - variable in the equation

A2 - variable in the equation

valueNumber - value number of address

addUpdateArrayDefEquation

void addUpdateArrayDefEquation(HeapVariable<?> A1,
                               HeapVariable<?> A2,
                               Object array,
                               Object index)

Add an equation to the system of the form

 L(A1) = updateDef(L(A2), <VALNUM(array),VALNUM(index)>)
 

Parameters:

A1 - variable in the equation

A2 - variable in the equation

array - variable in the equation

index - variable in the equation

addUpdateArrayUseEquation

void addUpdateArrayUseEquation(HeapVariable<?> A1,
                               HeapVariable<?> A2,
                               Object array,
                               Object index)

Add an equation to the system of the form

 L(A1) = updateUse(L(A2), <VALNUM(array),VALNUM(index)>)
 

Parameters:

A1 - variable in the equation

A2 - variable in the equation

array - variable in the equation

index - variable in the equation