org.jikesrvm.compilers.opt.liveness

Class LiveAnalysis

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

org.jikesrvm.compilers.opt.liveness.LiveAnalysis

public final class LiveAnalysis
extends CompilerPhase

This class performs a flow-sensitive iterative live variable analysis. The result of this analysis is live ranges for each basic block. (@see BasicBlock)

This class can also optionally construct GC maps. These GC maps are later used to create the final gc map (see OptReferenceMap.java).

Previously we used to be concerned that we didn't lose any precision due to imprecise modeling of exceptions. However, the troublesome situation cannot occur in Java. The rest of the comment for this class explains why that situation cannot occur.

The Java SPEC forces the compiler to declare a variable as uninitialized in those case that would be problematic. Consider the following ***ILLEGAL*** example:

 static void main(String arg[]) {
   Object x;

   try {
     foo();
     x = null;
     bar();
   }
   catch (FooException e) {
   }

   catch (BarException e) {
     Object a = x;
   }
 }
 

Here x is live in the Bar catch block, but not above the assignment in the try block. We only kill off values coming from catch blocks if they are in the first PEI region (above the call to foo). Thus, our analysis will conservatively record that x is live above the assignment.

However, the Java SPEC requires compilers to state that x is uninitialized here, even though it isn't. Thus, this scenario cannot occur. Basically, every variable used in a catch block needs to be defined before the TRY statement. (The SPEC doesn't explicitly state this, but on page 398 (Sec 16.2.13) it says that every variable used in a *finally* block needs to be defined before the TRY statement, which is even more restrictive.

Bottomline: losing precision is not a concern!

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	LiveAnalysis.BBLiveElement
(package private) static class	LiveAnalysis.MapElement A simple class used just in this file when creating GC maps

Field Summary

Fields

Modifier and Type	Field and Description
private LiveAnalysis.BBLiveElement[]	bbLiveInfo Temporary live information associated with each basic block
private static Constructor<CompilerPhase>	constructor Constructor for this compiler phase
private boolean	createGCMaps Should we also create GC maps while we are computing liveness
private LiveSet	currentSet The current LiveSet that we will carry around
private static boolean	DEBUG Debugging info
private LiveInterval	liveIntervals
private GCIRMap	map The GC map associated with the IR, optionally filled by this class
private VariableMap	osrMap
private ArrayList<LiveIntervalElement>[]	registerMap For each register, the set of live interval elements describing the register.
private boolean	skipGuards Should we skip guard registers?
private boolean	skipLocal Should we skip the (final) local propagation phase?
private boolean	storeLiveAtHandlers Should we store liveness information at the top of each handler block?
private static boolean	VERBOSE Even more debugging info

Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

container

Constructor Summary

Constructors

Constructor and Description
LiveAnalysis() By default we don't create GC maps and do perform the local prop phase
LiveAnalysis(boolean createGCMaps, boolean skipLocal) The constructor is used to specify whether GC maps should be computed along with live analysis.
LiveAnalysis(boolean createGCMaps, boolean skipLocal, boolean storeLiveAtHandlers) The constructor is used to specify whether GC maps should be computed along with live analysis.
LiveAnalysis(boolean createGCMaps, boolean skipLocal, boolean storeLiveAtHandlers, boolean skipGuards) The constructor is used to specify whether GC maps should be computed along with live analysis.

Method Summary

Modifier and Type	Method and Description
private void	addToRegisterMap(Register r, LiveIntervalElement i)
private void	collectOsrInfo(Instruction inst, LiveSet lives)
private void	computeBlockGenAndKill(BasicBlock bblock, IR ir) Compute summary (local) live variable analysis for a basic block, which is basically Gen and Kill information.
private void	computeRegisterMap(IR ir) Sets up a mapping from each register to the set of live intervals for the register.
private void	debugBegining(IR ir, boolean createGCMaps, boolean dumpFixedPointResults, boolean dumpFinalMaps, boolean dumpFinalLiveIntervals) Just a helper method to encapsulate the optional debugging info that is performed at the beginning of the perform method
private void	debugPostGlobal(IR ir, boolean dumpFixedPointResults, boolean dumpFinalMaps, boolean dumpFinalLiveIntervals) Just a helper method to encapsulate the optional debugging info that is performed after the global propagation step of "perform"
Constructor<CompilerPhase>	getClassConstructor() Get a constructor object for this compiler phase
LiveAnalysis.BBLiveElement	getLiveInfo(BasicBlock bb) REturns the live information for a particular block
HashSet<Register>	getLiveRegistersOnEdge(BasicBlock bb1, BasicBlock bb2) Return the set of registers that are live on the control-flow edge basic block bb1 to basic block bb2
(package private) HashSet<Register>	getLiveRegistersOnEntry(BasicBlock bb)
(package private) HashSet<Register>	getLiveRegistersOnExit(BasicBlock bb)
String	getName()
private void	getUsesFromPhis(BasicBlock bblock) The rvals of phi nodes are logically uses in the phi's predecessor blocks, so here we collect phi rvals from the current block's successors into the gen set for this block, being careful to collect only the appropriate rval
private boolean	isSkippableReg(RegisterOperand regOp, IR ir) Should this register be included in the liveness solution?
Iterator<LiveIntervalElement>	iterateLiveIntervals(Register r)
void	merge(Register r1, Register r2) Update the data structures to reflect that all live intervals for r2 are now intervals for r1.
void	perform(IR ir) The entry point into this class Perform live variable analysis on this IR, constructing live range info and (optionally) GC map info as we go.
private void	performLocalPropagation(IR ir, boolean createGCMaps) This method performs the last phase of the analysis, local propagation.
private void	printFinalLiveIntervals(IR ir) Prints the Final Live Intervals
private void	printFinalMaps(IR ir)
private void	printFixedPointResults(IR ir) Prints the results of the fixed point computation.
private boolean	processBlock(BasicBlock block, boolean reuseCurrentSet, IR ir) Computes the in set for this block given the out, gen, and kill set

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

dumpIR, dumpIR, getCompilerPhaseConstructor, getCompilerPhaseConstructor, newExecution, performPhase, printingEnabled, reportAdditionalStats, setContainer, shouldPerform, verify

Methods inherited from class java.lang.Object

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

Field Detail

createGCMaps

private final boolean createGCMaps

Should we also create GC maps while we are computing liveness

storeLiveAtHandlers

private final boolean storeLiveAtHandlers

Should we store liveness information at the top of each handler block?

skipGuards

private final boolean skipGuards

Should we skip guard registers?

skipLocal

private final boolean skipLocal

Should we skip the (final) local propagation phase?

currentSet

private LiveSet currentSet

The current LiveSet that we will carry around

bbLiveInfo

private LiveAnalysis.BBLiveElement[] bbLiveInfo

Temporary live information associated with each basic block

map

private final GCIRMap map

The GC map associated with the IR, optionally filled by this class

osrMap

private final VariableMap osrMap

registerMap

private ArrayList<LiveIntervalElement>[] registerMap

For each register, the set of live interval elements describing the register.

liveIntervals

private LiveInterval liveIntervals

DEBUG

private static final boolean DEBUG

Debugging info

See Also:

Constant Field Values

VERBOSE

private static final boolean VERBOSE

Even more debugging info

See Also:

Constant Field Values

constructor

private static final Constructor<CompilerPhase> constructor

Constructor for this compiler phase

Constructor Detail

LiveAnalysis

public LiveAnalysis(boolean createGCMaps,
                    boolean skipLocal)

The constructor is used to specify whether GC maps should be computed along with live analysis.

Parameters:

createGCMaps - should we create GC maps?

skipLocal - should we skip the (final) local propagation phase?

LiveAnalysis

public LiveAnalysis(boolean createGCMaps,
                    boolean skipLocal,
                    boolean storeLiveAtHandlers)

The constructor is used to specify whether GC maps should be computed along with live analysis.

Parameters:

createGCMaps - should we create GC maps?

skipLocal - should we skip the (final) local propagation phase?

storeLiveAtHandlers - should we store liveness info at the top of each handler block?

LiveAnalysis

public LiveAnalysis(boolean createGCMaps,
                    boolean skipLocal,
                    boolean storeLiveAtHandlers,
                    boolean skipGuards)

The constructor is used to specify whether GC maps should be computed along with live analysis.

Parameters:

createGCMaps - should we create GC maps?

skipLocal - should we skip the (final) local propagation phase?

storeLiveAtHandlers - should we store liveness info at the top of each handler block?

skipGuards - should we ignore validation registers?

LiveAnalysis

public LiveAnalysis()

By default we don't create GC maps and do perform the local prop phase

Method Detail

getName

public String getName()

Specified by:

getName in class CompilerPhase

Returns:

a String which is the name of the phase.

getClassConstructor

public Constructor<CompilerPhase> getClassConstructor()

Get a constructor object for this compiler phase

Overrides:

getClassConstructor in class CompilerPhase

Returns:

compiler phase constructor

perform

public void perform(IR ir)

The entry point into this class Perform live variable analysis on this IR, constructing live range info and (optionally) GC map info as we go.

Specified by:

perform in class CompilerPhase

Parameters:

ir - the ir

iterateLiveIntervals

public Iterator<LiveIntervalElement> iterateLiveIntervals(Register r)

merge

public void merge(Register r1,
                  Register r2)

Update the data structures to reflect that all live intervals for r2 are now intervals for r1.

Parameters:

r1 - old register

r2 - new register

computeRegisterMap

private void computeRegisterMap(IR ir)

Sets up a mapping from each register to the set of live intervals for the register.

Side effect: map each live interval element to its basic block.

Parameters:

ir - the governing IR

addToRegisterMap

private void addToRegisterMap(Register r,
                              LiveIntervalElement i)

computeBlockGenAndKill

private void computeBlockGenAndKill(BasicBlock bblock,
                                    IR ir)

Compute summary (local) live variable analysis for a basic block, which is basically Gen and Kill information.

For more details, see the paper "Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs" by Choi, Grove, Hind and Sarkar in ACM PASTE99 workshop.

Parameters:

bblock - the basic block

ir - the governing IR

getUsesFromPhis

private void getUsesFromPhis(BasicBlock bblock)

The rvals of phi nodes are logically uses in the phi's predecessor blocks, so here we collect phi rvals from the current block's successors into the gen set for this block, being careful to collect only the appropriate rval

Parameters:

bblock - the basic block of interest pre: Assumes the liveInfo array is allocated for this block post: May add to liveInfo for this block

processBlock

private boolean processBlock(BasicBlock block,
                             boolean reuseCurrentSet,
                             IR ir)

Computes the in set for this block given the out, gen, and kill set

Parameters:

block - the block of interest

reuseCurrentSet - whether we can reuse the "currentSet" or else clear it out and recompute the meet of our succs

ir - the governing ir

Returns:

true if something changed

performLocalPropagation

private void performLocalPropagation(IR ir,
                                     boolean createGCMaps)

This method performs the last phase of the analysis, local propagation. It uses the results from the fixed point analysis to determine the local live information within a basic block.

It walks the IR and, using the live information computed for each basic block, i.e., the results of the iterative solution, makes a single pass backward walk through the basic block, GENing and KILLing local information. This produces the set of live variables at each instruction.

This information is saved into two data structures:

• at all GC points, live references are recorded
• at all instructions, live range information is recorded

Parameters:

ir - the IR

createGCMaps - whether GC maps need to be created

isSkippableReg

private boolean isSkippableReg(RegisterOperand regOp,
                               IR ir)

Should this register be included in the liveness solution?

Parameters:

regOp - the register operand to consider skipping

ir - the governing ir

Returns:

whether the register should be skipped, i.e., not be present in the liveness solution

debugBegining

private void debugBegining(IR ir,
                           boolean createGCMaps,
                           boolean dumpFixedPointResults,
                           boolean dumpFinalMaps,
                           boolean dumpFinalLiveIntervals)

Just a helper method to encapsulate the optional debugging info that is performed at the beginning of the perform method

Parameters:

ir - the IR

createGCMaps - are we creating GC maps?

dumpFixedPointResults - debug info

dumpFinalMaps - debug info

dumpFinalLiveIntervals - debug info

debugPostGlobal

private void debugPostGlobal(IR ir,
                             boolean dumpFixedPointResults,
                             boolean dumpFinalMaps,
                             boolean dumpFinalLiveIntervals)

Just a helper method to encapsulate the optional debugging info that is performed after the global propagation step of "perform"

Parameters:

ir - the IR

dumpFixedPointResults - debug info

dumpFinalMaps - debug info

dumpFinalLiveIntervals - debug info

printFixedPointResults

private void printFixedPointResults(IR ir)

Prints the results of the fixed point computation. (Use printFinalMaps for the final GC map)

Parameters:

ir - the IR

printFinalMaps

private void printFinalMaps(IR ir)

printFinalLiveIntervals

private void printFinalLiveIntervals(IR ir)

Prints the Final Live Intervals

Parameters:

ir - the IR

getLiveInfo

public LiveAnalysis.BBLiveElement getLiveInfo(BasicBlock bb)

REturns the live information for a particular block

Parameters:

bb - the basic block of interest

Returns:

the live information for the block

getLiveRegistersOnEdge

public HashSet<Register> getLiveRegistersOnEdge(BasicBlock bb1,
                                                BasicBlock bb2)

Return the set of registers that are live on the control-flow edge basic block bb1 to basic block bb2

Parameters:

bb1 - start block of the edge

bb2 - end block of the edge

Returns:

live registers on the edge

getLiveRegistersOnExit

HashSet<Register> getLiveRegistersOnExit(BasicBlock bb)

Parameters:

bb - the basic block we're interested in

Returns:

the set of registers that are live across a basic block, and who are live after the basic block exit.

getLiveRegistersOnEntry

HashSet<Register> getLiveRegistersOnEntry(BasicBlock bb)

Parameters:

bb - the basic block we're interested in

Returns:

the set of registers that are live across a basic block, and who are live before the basic block entry.

collectOsrInfo

private void collectOsrInfo(Instruction inst,
                            LiveSet lives)