sandmark.watermark.potkonjak
Class livenessAnalysis

java.lang.Object
  |
  +--sandmark.watermark.potkonjak.livenessAnalysis

public class livenessAnalysis

extends java.lang.Object

Liveness represents the interference graph of the local variables contained in a control flow graph. When the liveness of two variables overlap each other, the two variables are said to interfere with each other. The interference graph represents this relationship between variables. There is an (un-directed) edge between variables a and b in the interference graph if variable a interferes with variable b.

Nested Class Summary

(package private) class	livenessAnalysis.IGNode Represents a node in the interference graph.
(package private) class	livenessAnalysis.Key
(package private) class	livenessAnalysis.NodeInfo Stores information about each Node in an expression tree (!)
(package private) class	livenessAnalysis.Pos A Pos is an element in the worklist used to determine the live out set of a given LocalExpr.

Field Summary

static boolean	AFTER
static boolean	BEFORE
(package private) EDU.purdue.cs.bloat.cfg.FlowGraph	cfg
static boolean	DEBUG
(package private) EDU.purdue.cs.bloat.util.Graph	ig
static boolean	UNIQUE

Constructor Summary

livenessAnalysis(EDU.purdue.cs.bloat.cfg.FlowGraph cfg)
Constructor.

Method Summary

java.util.Collection	defs() Returns the LocalExprs (variables) that occur in the CFG.
EDU.purdue.cs.bloat.util.Graph	getIG() Returns the interference graph.
java.util.Iterator	intersections(EDU.purdue.cs.bloat.tree.VarExpr a) Returns an Iterator of LocalExprs that interfere with a given VarExpr.
boolean	liveAtEndOfBlock(EDU.purdue.cs.bloat.tree.VarExpr isLive, EDU.purdue.cs.bloat.cfg.Block block) Should not be called.
boolean	liveAtStartOfBlock(EDU.purdue.cs.bloat.tree.VarExpr isLive, EDU.purdue.cs.bloat.cfg.Block block) Should not be called.
boolean	liveAtUse(EDU.purdue.cs.bloat.tree.VarExpr isLive, EDU.purdue.cs.bloat.tree.VarExpr at, boolean after) Should not be called.
(package private) void	liveOut(java.util.BitSet m, java.util.List[] nodes, EDU.purdue.cs.bloat.cfg.Block block, int nodeIndex, livenessAnalysis.IGNode defNode, java.util.Collection phiCatchNodes) Computes (a portion of) the "live out" set for a given local variable.
boolean	liveRangesIntersect(EDU.purdue.cs.bloat.tree.VarExpr a, EDU.purdue.cs.bloat.tree.VarExpr b) Determines whether or not two variables interfere with one another.
void	putIG(EDU.purdue.cs.bloat.util.Graph ig) Assignment of an interference graph to the field ig
void	removeVar(EDU.purdue.cs.bloat.tree.LocalExpr expr) Removes a local expression from the interference graph.

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

public static boolean DEBUG

UNIQUE

public static boolean UNIQUE

BEFORE

public static final boolean BEFORE

See Also:

Constant Field Values

AFTER

public static final boolean AFTER

See Also:

Constant Field Values

cfg

EDU.purdue.cs.bloat.cfg.FlowGraph cfg

ig

EDU.purdue.cs.bloat.util.Graph ig

Constructor Detail

livenessAnalysis

public livenessAnalysis(EDU.purdue.cs.bloat.cfg.FlowGraph cfg)

Constructor.

Parameters:

cfg - Control flow graph on which to perform liveness analysis.

Method Detail

removeVar

public void removeVar(EDU.purdue.cs.bloat.tree.LocalExpr expr)

Removes a local expression from the interference graph.

liveAtUse

public boolean liveAtUse(EDU.purdue.cs.bloat.tree.VarExpr isLive,
                         EDU.purdue.cs.bloat.tree.VarExpr at,
                         boolean after)

Should not be called.

liveAtStartOfBlock

public boolean liveAtStartOfBlock(EDU.purdue.cs.bloat.tree.VarExpr isLive,
                                  EDU.purdue.cs.bloat.cfg.Block block)

Should not be called.

liveAtEndOfBlock

public boolean liveAtEndOfBlock(EDU.purdue.cs.bloat.tree.VarExpr isLive,
                                EDU.purdue.cs.bloat.cfg.Block block)

Should not be called.

defs

public java.util.Collection defs()

Returns the LocalExprs (variables) that occur in the CFG. They correspond to nodes in the interference graph.

intersections

public java.util.Iterator intersections(EDU.purdue.cs.bloat.tree.VarExpr a)

Returns an Iterator of LocalExprs that interfere with a given VarExpr.

liveRangesIntersect

public boolean liveRangesIntersect(EDU.purdue.cs.bloat.tree.VarExpr a,
                                   EDU.purdue.cs.bloat.tree.VarExpr b)

Determines whether or not two variables interfere with one another.

getIG

public EDU.purdue.cs.bloat.util.Graph getIG()

Returns the interference graph.

putIG

public void putIG(EDU.purdue.cs.bloat.util.Graph ig)

Assignment of an interference graph to the field ig

liveOut

void liveOut(java.util.BitSet m,
             java.util.List[] nodes,
             EDU.purdue.cs.bloat.cfg.Block block,
             int nodeIndex,
             livenessAnalysis.IGNode defNode,
             java.util.Collection phiCatchNodes)

Computes (a portion of) the "live out" set for a given local variable. If a variable is live on a block's outgoing edge in the CFG, then it is "live out" at that block.

Parameters:

m - Bit vector that indicates the block for which block the defNode is live out

nodes - The NodeInfo for the local variables used or defined in each block

block - The block in which the LocalExpr of interest is defined

nodeIndex - Which number definition in the defining block

defNode - The node in the IG whose live out set we are interested in