Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 int` | `SPECIAL_EDGE`
`static boolean` | `TRACE`
`static boolean` | `TRACE_SUMMARY`

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

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

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD