avrora.stack
Class Analyzer

java.lang.Object
  avrora.stack.Analyzer

public class Analyzer

extends java.lang.Object

The Analyzer class implements the analysis phase that determines the transition relation between the states in the abstract state space. It is modelled on the simulator, but only does abstract interpretation rather than executing the entire program.

Nested Class Summary

class	Analyzer.ContextSensitivePolicy The ContextSensitive class implements the context-sensitive analysis similar to 1-CFA.
protected class	Analyzer.MonitorThread The MonitorThread class represents a thread instance that constantly monitors the progress of the stack analysis and reports on the number of states explored, edges inserted, states on the frontier, as well statistics about the propagation phase.

Field Summary

static int	CALL_EDGE
static int[]	EDGE_DELTA
static java.lang.String[]	EDGE_NAMES
protected StateTransitionGraph	graph
static int	INT_EDGE
static boolean	MONITOR_STATES
protected int	newEdgeCount
protected StateTransitionGraph.EdgeList	newEdges
protected int	newRetCount
protected StateTransitionGraph.StateList	newReturnStates
static int	NORMAL_EDGE
static int	NORMAL_STATE
static int	POP_EDGE
protected Verbose.Printer	printer
protected Program	program
static int	PUSH_EDGE
static byte[]	reserve
static int	RET_EDGE
static int	RET_STATE
protected int	retCount
static int	RETI_EDGE
static int	RETI_STATE
protected int	retiCount
static boolean	running
static boolean	SHOW_PATH
static int	SPECIAL_EDGE
static boolean	TRACE
static boolean	TRACE_SUMMARY
static boolean	USE_ISEA

Constructor Summary

Analyzer(Program p)

Method Summary

protected void	buildReachableStateSpace() The buildReachableStateSpace() method starts at the eden state of the analysis, maintaining a list of frontier states.
void	dump()
protected avrora.stack.Analyzer.Path	findMaximalPath(StateCache.State s, java.util.HashMap stack, int depth) The findMaximalPath() method is a recursive procedure that discovers the maximal weight path in the state graph.
protected void	processNewEdges()
protected void	processNewReturns() The processPropagationList() method walks through a list of target/caller state pairs, propagating callers to return states.
void	report() The report() method generates a textual report after the analysis has been completed.
void	run() The run() method begins the analysis.
static void	traceEdge(int type, StateCache.State s, StateCache.State t, int weight)

Methods inherited from class java.lang.Object

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

Field Detail

MONITOR_STATES

public static boolean MONITOR_STATES

TRACE_SUMMARY

public static boolean TRACE_SUMMARY

USE_ISEA

public static boolean USE_ISEA

SHOW_PATH

public static boolean SHOW_PATH

printer

protected final Verbose.Printer printer

program

protected final Program program

graph

protected final StateTransitionGraph graph

retCount

protected int retCount

retiCount

protected int retiCount

newRetCount

protected int newRetCount

newEdgeCount

protected int newEdgeCount

newReturnStates

protected StateTransitionGraph.StateList newReturnStates

newEdges

protected StateTransitionGraph.EdgeList newEdges

NORMAL_EDGE

public static final int NORMAL_EDGE

See Also:

Constant Field Values

PUSH_EDGE

public static final int PUSH_EDGE

See Also:

Constant Field Values

POP_EDGE

public static final int POP_EDGE

See Also:

Constant Field Values

CALL_EDGE

public static final int CALL_EDGE

See Also:

Constant Field Values

INT_EDGE

public static final int INT_EDGE

See Also:

Constant Field Values

RET_EDGE

public static final int RET_EDGE

See Also:

Constant Field Values

RETI_EDGE

public static final int RETI_EDGE

See Also:

Constant Field Values

SPECIAL_EDGE

public static final int SPECIAL_EDGE

See Also:

Constant Field Values

NORMAL_STATE

public static final int NORMAL_STATE

See Also:

Constant Field Values

RET_STATE

public static final int RET_STATE

See Also:

Constant Field Values

RETI_STATE

public static final int RETI_STATE

See Also:

Constant Field Values

EDGE_NAMES

public static final java.lang.String[] EDGE_NAMES

EDGE_DELTA

public static final int[] EDGE_DELTA

TRACE

public static boolean TRACE

running

public static boolean running

reserve

public static byte[] reserve

Constructor Detail

Analyzer

public Analyzer(Program p)

Method Detail

run

public void run()

The run() method begins the analysis. The entrypoint of the program with an initial default state serves as the first state to start exploring.

buildReachableStateSpace

protected void buildReachableStateSpace()

The buildReachableStateSpace() method starts at the eden state of the analysis, maintaining a list of frontier states. It then builds the state space using the frontier states as a work list. When the work list becomes null, it propagates calling states to their reachable return states and inserts return edges to (possibly unexplored) states. After the propagation phase, it processes any new frontier states. The analysis continues until there are no new frontier states and there are no new propagations to be performed.

processNewReturns

protected void processNewReturns()

The processPropagationList() method walks through a list of target/caller state pairs, propagating callers to return states. When return states are encountered, return edges between the caller and new return state are inserted and any new return states are pushed onto the frontier.

processNewEdges

protected void processNewEdges()

findMaximalPath

protected avrora.stack.Analyzer.Path findMaximalPath(StateCache.State s,
                                                     java.util.HashMap stack,
                                                     int depth)
                                              throws avrora.stack.Analyzer.UnboundedStackException

The findMaximalPath() method is a recursive procedure that discovers the maximal weight path in the state graph. If there is a non-zero weight cycle, this method will throw a UnboundedStackException which contains as a field the path leading out of the specified state back to a state on the stack.

Parameters:

s - the state to explore

stack - the states on the traversal stack

depth - the current stack depth

Returns:

a path leading out of the current state that adds the maximum height to the stack of any path leading out of this state

Throws:

UnboundedStackException - if a non-zero weight cycle exists in the graph

avrora.stack.Analyzer.UnboundedStackException

report

public void report()

The report() method generates a textual report after the analysis has been completed. It reports information about states, reachable states, time for analysis, and of course, the maximum stack size for the program.

dump

public void dump()

traceEdge

public static void traceEdge(int type,
                             StateCache.State s,
                             StateCache.State t,
                             int weight)