edu.ksu.cis.projects.bogor.analyses
Class IntraFSMAnalysis<L>

java.lang.Object
  edu.ksu.cis.projects.bogor.analyses.IntraFSMAnalysis<L>

Direct Known Subclasses:

LiveVariableAnalysis

public abstract class IntraFSMAnalysis<L>
extends Object

An implemenation of the Monotone Data-flow Framework.

Version:

CVS $Revision: 1.4 $ $Date: 2005/01/14 15:48:14 $

Author:

Robby , Matt Hoosier

Nested Class Summary

protected static interface	IntraFSMAnalysis.SetContainmentOperator<T>
protected static interface	IntraFSMAnalysis.SetFactory<T>
protected static interface	IntraFSMAnalysis.SetMergeOperator<T>
protected static class	IntraFSMAnalysis.WorkListEntry

Field Summary

protected IntObjectTable<Set<L>>	analysisTable Mapping of a label (CFG location) to the working set of the "thing" being calculated (live variables, available expressions, etc).
protected Set<L>	bottom First working set to give to labels which are not in the "extremal" labels set, E .
protected CFG	cfg Flow graph.
protected IntraFSMAnalysis.SetContainmentOperator<L>	containmentTest Abstract set containment operator used in MDF algorithm.
protected Set<L>	init First working set to give to labels which are in the "extremal" labels set, E .
protected boolean	isForwardAnalysis Flag to indicate whether transitions in cfg should be read in reverse or forwards.
protected IntraFSMAnalysis.SetMergeOperator<L>	mergeOperation Abstract set combination operator used in MDF algorithm.
protected IntraFSMAnalysis.SetFactory<L>	setFactory Factory object to create set implementations appropriate for the particular analysis "plugged into" the MDF.
protected LinkedList<IntraFSMAnalysis.WorkListEntry>	workList Pending-work queue.

Constructor Summary

IntraFSMAnalysis(CFG cfg, boolean isForwardAnalysis, IntraFSMAnalysis.SetContainmentOperator<L> subsetTest, IntraFSMAnalysis.SetMergeOperator<L> mergeOp, IntraFSMAnalysis.SetFactory<L> setFactory, Set<L> init, Set<L> bottom)
Build an instance of the Monotone Data-flow Framework.

Method Summary

protected void	addToWorkList(IntraFSMAnalysis.WorkListEntry newEntry)
protected void	analyze() Perform Phase II of the MDF algorithm.
protected abstract Set<L>	analyzeLocation(int locDesc, Set<L> s) Compute an analysis-specific "active" set of variables given a known active input set and a program location.
void	dispose()
protected Set<L>	getEntry(int locDesc) Find the working set for a location.
protected void	init() Perform Phase I of the MDF algorithm.
protected IntraFSMAnalysis.WorkListEntry	removeNextInWorkList()
protected void	setEntry(int locDesc, Set<L> entry) Update working set for a location.

Methods inherited from class java.lang.Object

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

Field Detail

cfg

protected CFG cfg

Flow graph.

isForwardAnalysis

protected boolean isForwardAnalysis

Flag to indicate whether transitions in cfg should be read in reverse or forwards.

containmentTest

protected IntraFSMAnalysis.SetContainmentOperator<L> containmentTest

Abstract set containment operator used in MDF algorithm. In practice, this is a containment or superset test.

mergeOperation

protected IntraFSMAnalysis.SetMergeOperator<L> mergeOperation

Abstract set combination operator used in MDF algorithm. In practice, this is a union or intersection.

setFactory

protected IntraFSMAnalysis.SetFactory<L> setFactory

Factory object to create set implementations appropriate for the particular analysis "plugged into" the MDF.

init

protected Set<L> init

First working set to give to labels which are in the "extremal" labels set, E .

bottom

protected Set<L> bottom

First working set to give to labels which are not in the "extremal" labels set, E .

workList

protected LinkedList<IntraFSMAnalysis.WorkListEntry> workList

Pending-work queue.

analysisTable

protected IntObjectTable<Set<L>> analysisTable

Mapping of a label (CFG location) to the working set of the "thing" being calculated (live variables, available expressions, etc).

Constructor Detail

IntraFSMAnalysis

public IntraFSMAnalysis(CFG cfg,
                        boolean isForwardAnalysis,
                        IntraFSMAnalysis.SetContainmentOperator<L> subsetTest,
                        IntraFSMAnalysis.SetMergeOperator<L> mergeOp,
                        IntraFSMAnalysis.SetFactory<L> setFactory,
                        Set<L> init,
                        Set<L> bottom)

Build an instance of the Monotone Data-flow Framework.

Parameters:

cfg - program control flow graph giving predecessor, successors, and entry/exit points

isForwardAnalysis - whether the MDF should use flow or reverse(flow) for the next-states relation

subsetTest - set relation tester functor

mergeOp - set combinator functor

setFactory - source of new set implementations compatible with the specific MDF being used. For instance, some may use TreeSet, others HashSet.

init - the initial working set to assign to labels which are in the extremal set, E .

bottom - the initial working set to assign to labels not in the extermal set, E

Method Detail

dispose

public void dispose()

setEntry

protected void setEntry(int locDesc,
                        Set<L> entry)

Update working set for a location.

getEntry

protected Set<L> getEntry(int locDesc)

Find the working set for a location.

addToWorkList

protected void addToWorkList(IntraFSMAnalysis.WorkListEntry newEntry)

analyze

protected void analyze()

Perform Phase II of the MDF algorithm. Computes a fixed-point for the working sets on each location.

analyzeLocation

protected abstract Set<L> analyzeLocation(int locDesc,
                                          Set<L> s)

Compute an analysis-specific "active" set of variables given a known active input set and a program location.

init

protected void init()

Perform Phase I of the MDF algorithm. Enqueues a work item for every (pred, succ) pair in the flow graph and sets initial working sets for each program label.

removeNextInWorkList

protected IntraFSMAnalysis.WorkListEntry removeNextInWorkList()