package Analysis.TaskStateAnalysis;
-import Analysis.TaskStateAnalysis.*;
import IR.*;
import IR.Tree.*;
import IR.Flat.*;
import java.io.FileWriter;
import java.io.FileOutputStream;
-
-
-
-
public class TaskAnalysis {
State state;
Hashtable flagstates;
Hashtable flags;
Hashtable extern_flags;
Queue<FlagState> toprocess;
+ TagAnalysis taganalysis;
+ Hashtable cdtorootnodes;
+
TypeUtil typeutil;
-
+
/**
* Class Constructor
*
* @param state a flattened State object
* @see State
*/
- public TaskAnalysis(State state)
+ public TaskAnalysis(State state, TagAnalysis taganalysis)
{
this.state=state;
this.typeutil=new TypeUtil(state);
+ this.taganalysis=taganalysis;
+
}
/** Builds a table of flags for each class in the Bristlecone program.
for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
ClassDescriptor cd = (ClassDescriptor)it_classes.next();
- System.out.println(cd.getSymbol());
Vector vFlags=new Vector();
FlagDescriptor flag[];
int ctr=0;
for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
- System.out.println(fd.toString());
vFlags.add(fd);
}
}
public void taskAnalysis() throws java.io.IOException {
flagstates=new Hashtable();
Hashtable<FlagState,FlagState> sourcenodes;
-
+ cdtorootnodes=new Hashtable();
getFlagsfromClasses();
ClassDescriptor cd=(ClassDescriptor)it_classes.next();
externs=((Integer)extern_flags.get(cd)).intValue();
FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
-
- //Debug block
- System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
- System.out.println("No of externs " + externs);
- System.out.println("No of flags: "+fd.length);
- //Debug block
-
flagstates.put(cd,new Hashtable<FlagState,FlagState>());
+ cdtorootnodes.put(cd,new Vector());
}
ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
-
FlagState fsstartup=new FlagState(startupobject);
+
+
FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
fsstartup=fsstartup.setFlag(fd[0],true);
-
+ fsstartup.setAsSourceNode();
+ ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
+
sourcenodes.put(fsstartup,fsstartup);
toprocess.add(fsstartup);
while (!toprocess.isEmpty()) {
FlagState trigger=toprocess.poll();
createPossibleRuntimeStates(trigger);
+
analyseTasks(trigger);
}
Enumeration e=flagstates.keys();
while (e.hasMoreElements()) {
- System.out.println("creating dot file");
ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
- System.out.println((cdtemp.getSymbol()));
createDOTfile(cdtemp);
}
}
* @see FlagState
*/
- private void analyseTasks(FlagState fs) {
+private void analyseTasks(FlagState fs) {
ClassDescriptor cd=fs.getClassDescriptor();
Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
TaskDescriptor td = (TaskDescriptor)it_tasks.next();
String taskname=td.getSymbol();
+
/** counter to keep track of the number of parameters (of the task being analyzed) that
* are satisfied by the flagstate.
*/
int trigger_ctr=0;
TempDescriptor temp=null;
FlatMethod fm = state.getMethodFlat(td);
-
+
for(int i=0; i < td.numParameters(); i++) {
FlagExpressionNode fen=td.getFlag(td.getParameter(i));
TagExpressionList tel=td.getTag(td.getParameter(i));
-
+
/** Checking to see if the parameter is of the same type/class as the
* flagstate's and also if the flagstate fs triggers the given task*/
if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
if (trigger_ctr>1)
throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
- //Iterating through the nodes
- FlatNode fn=fm.methodEntryNode();
-
- HashSet tovisit= new HashSet();
- HashSet visited= new HashSet();
- tovisit.add(fn);
- while(!tovisit.isEmpty()) {
- FlatNode fn1 = (FlatNode)tovisit.iterator().next();
- tovisit.remove(fn1);
- visited.add(fn1);
- // Queue all of the next nodes
- for(int i = 0; i < fn1.numNext(); i++) {
- FlatNode nn=fn1.getNext(i);
- if (!visited.contains(nn))
- tovisit.add(nn);
+ Set newstates=taganalysis.getFlagStates(td);
+ for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
+ FlagState fsnew=(FlagState) fsit.next();
+ fsnew.setAsSourceNode();
+ fsnew.addAllocatingTask(td);
+ ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
+
+ if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
+ ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
+ toprocess.add(fsnew);
}
- if (fn1.kind()==FKind.FlatFlagActionNode) {
+ }
+
+ Stack nodestack=new Stack();
+ HashSet discovered=new HashSet();
+ nodestack.push(fm);
+ discovered.add(fm);
+ //Iterating through the nodes
+
+ while(!nodestack.isEmpty()) {
+ FlatNode fn1 = (FlatNode) nodestack.pop();
+
+ if (fn1.kind()==FKind.FlatReturnNode) {
+ /* Self edge */
+ FEdge newedge=new FEdge(fs, taskname);
+ fs.addEdge(newedge);
+ continue;
+ } else if (fn1.kind()==FKind.FlatFlagActionNode) {
FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
throw new Error("PRE FlagActions not supported");
- } else if (ffan.getTaskType() == FlatFlagActionNode.NEWOBJECT) {
- FlagState fsnew=evalNewObjNode(ffan);
- //Have we seen this node yet
- if (!sourcenodes.containsKey(fsnew)) {
- sourcenodes.put(fsnew, fsnew);
- toprocess.add(fsnew);
- }
+
} else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
- FlagState fs_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
- if (!sourcenodes.containsKey(fs_taskexit)) {
- toprocess.add(fs_taskexit);
+ Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
+ for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
+ FlagState fs_taskexit=(FlagState)en.nextElement();
+ if (!sourcenodes.containsKey(fs_taskexit)) {
+ toprocess.add(fs_taskexit);
+ }
+ //seen this node already
+ fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
+ FEdge newedge=new FEdge(fs_taskexit,taskname);
+ fs.addEdge(newedge);
}
- //seen this node already
- fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
- Edge newedge=new Edge(fs_taskexit,taskname);
- fs.addEdge(newedge);
+ continue;
+ }
+ }
+ /* Queue other nodes past this one */
+ for(int i=0;i<fn1.numNext();i++) {
+ FlatNode fnext=fn1.getNext(i);
+ if (!discovered.contains(fnext)) {
+ discovered.add(fnext);
+ nodestack.push(fnext);
}
}
}
}
}
+
/** Determines whether the given flagstate satisfies a
* single parameter in the given task.
* @param fen FlagExpressionNode
private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
- if (fen instanceof FlagNode)
+ if (fen==null)
+ return true;
+ else if (fen instanceof FlagNode)
return fs.get(((FlagNode)fen).getFlag());
else
switch (((FlagOpNode)fen).getOp().getOp()) {
case Operation.LOGIC_AND:
- return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
+ return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
case Operation.LOGIC_OR:
- return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
+ return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
case Operation.LOGIC_NOT:
- return !(isTaskTrigger(((FlagOpNode)fen).getLeft(),fs));
+ return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
default:
return false;
}
private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
-
+ if (tel!=null){
for (int i=0;i<tel.numTags() ; i++){
switch (fs.getTagCount(tel.getType(i))){
case FlagState.ONETAG:
- case FlagState.MULTITAG:
- retval=true;
+ case FlagState.MULTITAGS:
break;
- case FlagState.NOTAG:
+ case FlagState.NOTAGS:
return false;
- break;
}
- return true;
}
+ }
+ return true;
}
/*private int tagTypeCount(TagExpressionList tel, String tagtype){
return ctr;
} */
-/** Evaluates a NewObject Node and returns the newly created
- * flagstate to add to the process queue.
- * @param nn FlatNode
- * @return FlagState
- * @see FlatNode
- * @see FlagState
- */
-
- private FlagState evalNewObjNode(FlatNode nn){
- TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
-
- //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
- ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
-
- FlagState fstemp=new FlagState(cd_new);
-
- for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
- TempFlagPair tfp=(TempFlagPair)it_tfp.next();
- if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
- {
- fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
- }
-
- else
- break;
- }
- for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
- TempTagPair ttp=(TempTagPair)it_ttp.next();
- if (! (ttp.getTag()==null)){
- fstemp=fstemp.setTag(ttp.getTag());
- }
- else
- break;
- return fstemp;
+ private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
+ FlagState fstemp=fs;
+ Vector<FlagState> processed=new Vector<FlagState>();
+
+ //Process the flag changes
+
+ for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
+ TempFlagPair tfp=(TempFlagPair)it_tfp.next();
+ if (temp==tfp.getTemp())
+ fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
}
- private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
- FlagState fstemp=fs;
- //FlagState[] fstemparray=new FlagState[3];
- Vector<FlagState> fsv=new Vector<FlagState>();
-
-
- for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
- TempFlagPair tfp=(TempFlagPair)it_tfp.next();
- if (temp==tfp.getTemp())
- fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
- }
-
- for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
- TempTagPair ttp=(TempTagPair)it_ttp.next();
- if (temp==ttp.getTemp()){
- if (((FlatFlagActionNode)nn).getTagChange(ttp)){
- fstemp=fstemp.setTag(ttp.getTag());
- fstemp
- else
- fstemparray
+ //Process the tag changes
+
+ processed.add(fstemp);
+
+ //Process clears first
+ for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
+ TempTagPair ttp=(TempTagPair)it_ttp.next();
+
+ if (temp==ttp.getTemp()) {
+ Vector<FlagState> oldprocess=processed;
+ processed=new Vector<FlagState>();
+
+ for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
+ FlagState fsworking=(FlagState)en.nextElement();
+ if (!ffan.getTagChange(ttp)){
+ processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
+ } else processed.add(fsworking);
}
-
- return fstemp;
- }
+ }
+ }
+ //Process sets next
+ for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
+ TempTagPair ttp=(TempTagPair)it_ttp.next();
+ if (temp==ttp.getTemp()) {
+ Vector<FlagState> oldprocess=processed;
+ processed=new Vector<FlagState>();
+
+ for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
+ FlagState fsworking=(FlagState)en.nextElement();
+ if (ffan.getTagChange(ttp)){
+ processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
+ } else processed.add(fsworking);
+ }
+ }
+ }
+ return processed;
+ }
+
private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
if (sourcenodes.containsKey(fs))
* @see ClassDescriptor
*/
- public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
- File dotfile= new File("graph"+cd.getSymbol()+".dot");
- FileOutputStream dotstream=new FileOutputStream(dotfile,true);
+ public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
+ File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
+ FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
- }
-
+ }
- private String getTaskName(TaskDescriptor td) {
- StringTokenizer st = new StringTokenizer(td.toString(),"(");
- return st.nextToken();
+ /** Returns the flag states for the class descriptor. */
+ public Set getFlagStates(ClassDescriptor cd) {
+ if (flagstates.containsKey(cd))
+ return ((Hashtable)flagstates.get(cd)).keySet();
+ else
+ return null;
}
- private void createPossibleRuntimeStates(FlagState fs) {
+
+ private void createPossibleRuntimeStates(FlagState fs) {
ClassDescriptor cd = fs.getClassDescriptor();
Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
int externs=((Integer)extern_flags.get(cd)).intValue();
+
if(externs==0)
return;
toprocess.add(fstemp);
fstemp=canonicalizeFlagState(sourcenodes,fstemp);
- fs.addEdge(new Edge(fstemp,"Runtime"));
+ fs.addEdge(new FEdge(fstemp,"Runtime"));
}
+ }
+
+ public Vector getRootNodes(ClassDescriptor cd){
+ return (Vector)cdtorootnodes.get(cd);
+ }
+
+
+
}
-}
+
projects / IRC.git / blobdiff