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.

DEBUG

static final boolean DEBUG

See Also:

Constant Field Values

round

private final int round

which round of load elimination is this?

LoadElimination

public LoadElimination(int round)

Parameters:

round - which round of load elimination is this?

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)

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

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

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

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:

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 an instruction after a store instruction that caches value in register r.

findOrCreateRegister

static Register findOrCreateRegister(Object heapType,
                                     int valueNumber,
                                     HashMap<LoadElimination.UseRecord,Register> registers,
                                     ArchitectureSpecificOpt.RegisterPool 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 -

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

findOrCreateRegister

static Register findOrCreateRegister(Object heapType,
                                     int v1,
                                     int v2,
                                     HashMap<LoadElimination.UseRecord,Register> registers,
                                     ArchitectureSpecificOpt.RegisterPool 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

findOrCreateIndexSet

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

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.