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!

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.

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

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

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)

Return an iterator over all the live interval elements for a given register.

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.

computeRegisterMap

private void computeRegisterMap(IR ir)

Set 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.

addToRegisterMap

private void addToRegisterMap(Register r,
                              LiveIntervalElement i)

Add the live interval element i to the map for register r.

removeFromRegisterMap

private void removeFromRegisterMap(Register r,
                                   LiveIntervalElement i)

Remove the live interval element i from the map for register r.

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.

Parameters:

bblock - the basic block

ir - the governing if

See Also:

"Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs" by Choi, Grove, Hind, Sarkar in ACM PASTE99 workshop (available at www.research.ibm.com/jalapeno)"

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)

Compute 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

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

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)

Prints the final maps

Parameters:

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

getLiveRegistersOnExit

HashSet<Register> getLiveRegistersOnExit(BasicBlock bb)

Return 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)

Return 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)