org.jikesrvm.compilers.opt.ssa

Class LoadElimination

java.lang.Object

org.jikesrvm.compilers.opt.driver.OptimizationPlanElement

org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement

org.jikesrvm.compilers.opt.ssa.LoadElimination

public final class LoadElimination
extends OptimizationPlanCompositeElement

This class implements the redundant load elimination by Fink, Knobe & Sarkar. See SAS 2000 paper for details.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	LoadElimination.GVNPreparation This class sets up the IR state prior to entering SSA for GVN.
static class	LoadElimination.LoadEliminationPreparation This class sets up the IR state prior to entering SSA for load elimination
(package private) static class	LoadElimination.LoadEliminator
(package private) static class	LoadElimination.UseRecord
(package private) static class	LoadElimination.UseRecordSet

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static boolean	DEBUG
private int	round which round of load elimination is this?

Constructor Summary

Constructors

Constructor and Description
LoadElimination(int round)

Method Summary

Modifier and Type	Method and Description
(package private) static void	appendMove(Register r, Operand src, Instruction store) Append a move instruction after a store instruction that caches value in register r.
(package private) static boolean	eliminateLoads(IR ir, DF_Solution available) Eliminates redundant loads with respect to prior defs and prior uses.
private static <T> HashSet<T>	findOrCreateIndexSet(HashMap<Object,HashSet<T>> map, Object key)
(package private) static Register	findOrCreateRegister(Object heapType, int valueNumber, HashMap<LoadElimination.UseRecord,Register> registers, GenericRegisterPool pool, TypeReference type) Given a value number, return the temporary register allocated for that value number.
(package private) static Register	findOrCreateRegister(Object heapType, int v1, int v2, HashMap<LoadElimination.UseRecord,Register> registers, GenericRegisterPool pool, TypeReference type) Given a pair of value numbers, return the temporary register allocated for that pair.
static HashSet<Object>	getCandidates(IR ir) Do a quick pass over the IR, and return types that are candidates for redundant load elimination.
String	getName()
(package private) static void	replaceDefs(IR ir, LoadElimination.UseRecordSet UseRepSet, HashMap<LoadElimination.UseRecord,Register> registers) Perform scalar replacement actions for a Def of a heap variable.
(package private) static LoadElimination.UseRecordSet	replaceLoads(IR ir, DF_Solution available, HashMap<LoadElimination.UseRecord,Register> registers) Walk over each instruction.
(package private) static void	replaceLoadWithMove(Register r, Instruction load) Replace a Load instruction s with a load from a scalar register r TODO: factor this functionality out elsewhere
boolean	shouldPerform(OptOptions options) Determine, possibly by consulting the passed options object, if this optimization plan element should be performed.

Methods inherited from class org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement

compose, elapsedTime, initializeForMeasureCompilation, perform, printingEnabled, reportStats

Methods inherited from class org.jikesrvm.compilers.opt.driver.OptimizationPlanElement

prettyPrintTime

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

See Also:

Constant Field Values

round

private final int round

which round of load elimination is this?

Constructor Detail

LoadElimination

public LoadElimination(int round)

Parameters:

round - which round of load elimination is this?

Method Detail

shouldPerform

public boolean shouldPerform(OptOptions options)

Description copied from class: OptimizationPlanElement

Determine, possibly by consulting the passed options object, if this optimization plan element should be performed.

Overrides:

shouldPerform in class OptimizationPlanCompositeElement

Parameters:

options - The Options object for the current compilation.

Returns:

true if the plan element should be performed.

getName

public String getName()

Overrides:

getName in class OptimizationPlanCompositeElement

Returns:

a String which is the name of the phase.

eliminateLoads

static boolean eliminateLoads(IR ir,
                              DF_Solution available)

Eliminates redundant loads with respect to prior defs and prior uses.

Parameters:

ir - the governing IR

available - results of index propagation analysis

Returns:

true if any load is eliminated.

replaceLoads

static LoadElimination.UseRecordSet replaceLoads(IR ir,
                                                 DF_Solution available,
                                                 HashMap<LoadElimination.UseRecord,Register> registers)

Walk over each instruction. If its a USE (load) of a heap variable and the value is available, then replace the load with a move from a register.

POSTCONDITION: sets up the mapping 'registers' from value number to temporary register

Parameters:

ir - the IR

available - information on which values are available

registers - a place to store information about temp registers

Returns:

mapping from heap variables to value numbers

replaceLoadWithMove

static void replaceLoadWithMove(Register r,
                                Instruction load)

Replace a Load instruction s with a load from a scalar register r

TODO: factor this functionality out elsewhere

Parameters:

r - the register to load from

load - the load instruction

replaceDefs

static void replaceDefs(IR ir,
                        LoadElimination.UseRecordSet UseRepSet,
                        HashMap<LoadElimination.UseRecord,Register> registers)

Perform scalar replacement actions for a Def of a heap variable.

NOTE: Even loads can def a heap variable.

Parameters:

ir - the governing IR

UseRepSet - stores the uses(loads) that have been eliminated

registers - mapping from valueNumber -> temporary register

appendMove

static void appendMove(Register r,
                       Operand src,
                       Instruction store)

Append a move instruction after a store instruction that caches value in register r.

Parameters:

r - move target

src - move source

store - the instruction after which the move will be inserted

findOrCreateRegister

static Register findOrCreateRegister(Object heapType,
                                     int valueNumber,
                                     HashMap<LoadElimination.UseRecord,Register> registers,
                                     GenericRegisterPool pool,
                                     TypeReference type)

Given a value number, return the temporary register allocated for that value number. Create one if necessary.

Parameters:

heapType - a TypeReference or RVMField identifying the array SSA heap type

valueNumber - the value number

registers - a mapping from value number to temporary register

pool - register pool to allocate new temporaries from

type - the type to store in the new register

Returns:

the temporary register allocated for the value number

findOrCreateRegister

static Register findOrCreateRegister(Object heapType,
                                     int v1,
                                     int v2,
                                     HashMap<LoadElimination.UseRecord,Register> registers,
                                     GenericRegisterPool pool,
                                     TypeReference type)

Given a pair of value numbers, return the temporary register allocated for that pair. Create one if necessary.

Parameters:

heapType - a TypeReference identifying the array SSA heap type

v1 - first value number

v2 - second value number

registers - a mapping from value number to temporary register

pool - register pool to allocate new temporaries from

type - the type to store in the new register

Returns:

the temporary register allocated for the pair

findOrCreateIndexSet

private static <T> HashSet<T> findOrCreateIndexSet(HashMap<Object,HashSet<T>> map,
                                                   Object key)

Type Parameters:

T - the type for the collection returned as value in the mapping

Parameters:

map - a mapping from key to HashSet

key - a key into the map

Returns:

the set map(key). create one if none exists.

getCandidates

public static HashSet<Object> getCandidates(IR ir)

Do a quick pass over the IR, and return types that are candidates for redundant load elimination.

Algorithm: return those types T where

• there's a load L(i) of type T
• there's another load or store M(j) of type T, M!=L and V(i) == V(j)

The result contains objects of type RVMField and TypeReference, whose narrowest common ancestor is Object.

Parameters:

ir - the governing IR

Returns:

the types that are candidates for redundant load elimination