X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FTaskStateAnalysis%2FTaskAnalysis.java;h=bba02a6edb955f4bcfa990bb7ff06f95ed6e9105;hb=4cb63e913202459da4fe9d01feb7c02f1b98dd6f;hp=6c3f8d0bce1d3c0c2d7059f91b03049850748c2d;hpb=948d94811000033c44a3ee0393ea8d152e72dd91;p=IRC.git diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java index 6c3f8d0b..bba02a6e 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java @@ -1,5 +1,4 @@ package Analysis.TaskStateAnalysis; -import Analysis.TaskStateAnalysis.*; import IR.*; import IR.Tree.*; import IR.Flat.*; @@ -8,64 +7,62 @@ import java.io.File; import java.io.FileWriter; import java.io.FileOutputStream; - public class TaskAnalysis { State state; Hashtable flagstates; Hashtable flags; Hashtable extern_flags; Queue toprocess; - + TagAnalysis taganalysis; + Hashtable cdtorootnodes; + Hashtable tdToFEdges; + 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. - * It creates two hashtables: one which holds the ClassDescriptors and arrays of - * FlagDescriptors as key-value pairs; the other holds the ClassDescriptor and the - * number of external flags for that specific class. + /** Builds a table of flags for each class in the Bristlecone + * program. It creates two hashtables: one which holds the + * ClassDescriptors and arrays of * FlagDescriptors as key-value + * pairs; the other holds the ClassDescriptor and the * number of + * external flags for that specific class. */ private void getFlagsfromClasses() { flags=new Hashtable(); extern_flags = new Hashtable(); - /** Iterate through the classes used in the program to build the table of flags + /** Iterate through the classes used in the program to build + * the table of flags */ 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; /* Adding the flags of the super class */ - if (cd.getSuper()!=null) { - ClassDescriptor superdesc=cd.getSuperDesc(); - - for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) { + ClassDescriptor tmp=cd; + while(tmp!=null) { + for(Iterator it_cflags=tmp.getFlags();it_cflags.hasNext();) { FlagDescriptor fd = (FlagDescriptor)it_cflags.next(); - System.out.println(fd.toString()); vFlags.add(fd); } + tmp=tmp.getSuperDesc(); } - for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) { - FlagDescriptor fd = (FlagDescriptor)it_cflags.next(); - vFlags.add(fd); - } if (vFlags.size()!=0) { flag=new FlagDescriptor[vFlags.size()]; @@ -86,14 +83,14 @@ public class TaskAnalysis { } } } - /** Method which starts up the analysis - * + /** Method which starts up the analysis */ public void taskAnalysis() throws java.io.IOException { flagstates=new Hashtable(); Hashtable sourcenodes; - + cdtorootnodes=new Hashtable(); + tdToFEdges=new Hashtable(); getFlagsfromClasses(); @@ -104,30 +101,28 @@ public class TaskAnalysis { 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()); + cdtorootnodes.put(cd,new Vector()); } ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass); sourcenodes=(Hashtable)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); - /** Looping through the flagstates in the toprocess queue to perform the state analysis */ + /** Looping through the flagstates in the toprocess queue to + * perform the state analysis */ while (!toprocess.isEmpty()) { FlagState trigger=toprocess.poll(); createPossibleRuntimeStates(trigger); @@ -139,9 +134,7 @@ public class TaskAnalysis { 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); } } @@ -154,7 +147,7 @@ public class TaskAnalysis { * @see FlagState */ - private void analyseTasks(FlagState fs) { +private void analyseTasks(FlagState fs) { ClassDescriptor cd=fs.getClassDescriptor(); Hashtable sourcenodes=(Hashtable)flagstates.get(cd); @@ -162,31 +155,31 @@ public class TaskAnalysis { TaskDescriptor td = (TaskDescriptor)it_tasks.next(); String taskname=td.getSymbol(); - //**Debug***/ - System.out.println(); - System.out.println(cd.getSymbol()+" : "+fs.getTextLabel()); - System.out.println("Task: "+taskname); - //*********** - - - - /** counter to keep track of the number of parameters (of the task being analyzed) that - * are satisfied by the flagstate. + if(!tdToFEdges.containsKey(td)) { + tdToFEdges.put(td, new Vector()); + } + + /** 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); + int parameterindex=0; 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*/ - /** 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) && isTaskTrigger_flag(fen,fs) && isTaskTrigger_tag(tel,fs)) { temp=fm.getParameter(i); + parameterindex=i; trigger_ctr++; } } @@ -195,72 +188,87 @@ public class TaskAnalysis { continue; if (trigger_ctr>1) - throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task."); + System.out.println("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task:"+fs + " in "+td); + + Set newstates=taganalysis.getFlagStates(td); + for(Iterator fsit=newstates.iterator();fsit.hasNext();) { + FlagState fsnew=(FlagState) fsit.next(); + System.out.println("SOURCE:"+fsnew); - //** debug - System.out.println("Task:" + taskname +" is triggered"); - - - //Iterating through the nodes - FlatNode fn=fm.methodEntryNode(); + if (! ((Hashtable)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) { + ((Hashtable)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew); + toprocess.add(fsnew); + } else { + fsnew=((Hashtable)flagstates.get(fsnew.getClassDescriptor())).get(fsnew); + } + fsnew.setAsSourceNode(); + fsnew.addAllocatingTask(td); + + if(!((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).contains(fsnew)) { + ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew); + } + } - HashSet tovisit= new HashSet(); - HashSet visited= new HashSet(); + Stack nodestack=new Stack(); + HashSet discovered=new HashSet(); + nodestack.push(fm); + discovered.add(fm); + //Iterating through the nodes - 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); - } - if (fn1.kind()==FKind.FlatFlagActionNode) { + while(!nodestack.isEmpty()) { + FlatNode fn1 = (FlatNode) nodestack.pop(); + + if (fn1.kind()==FKind.FlatReturnNode) { + /* Self edge */ + FEdge newedge=new FEdge(fs, taskname, td, parameterindex); + ((Vector)tdToFEdges.get(td)).add(newedge); + 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) { - //*** - System.out.println("NEWOBJ"); - //*** - FlagState fsnew=evalNewObjNode(ffan); - //Have we seen this node yet - if(fsnew!=null){ - if (! ((Hashtable)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) { - ((Hashtable)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew); - toprocess.add(fsnew); - } - } - } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { - //*** - System.out.println("TASKEXIT"); - //*** - - Vector fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp); + } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { + Vector fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp); + Vector initFStates = ffan.getInitFStates(temp.getType().getClassDesc()); + if(!initFStates.contains(fs)) { + initFStates.addElement(fs); + } + Vector targetFStates = ffan.getTargetFStates(fs); 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); - //FEdge newedge=new FEdge(fs_taskexit,td); - fs.addEdge(newedge); - } + 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, td, parameterindex); + ((Vector)tdToFEdges.get(td)).add(newedge); + fs.addEdge(newedge); + + if(!targetFStates.contains(fs_taskexit)) { + targetFStates.addElement(fs_taskexit); + } + } + continue; + } + } + /* Queue other nodes past this one */ + for(int i=0;i evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){ + FlagState fstemp=fs; + Vector processed=new Vector(); + + //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)); } - return ctr; -} */ + + //Process the tag changes -/** 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){ - - ClassDescriptor cd_new=((FlatNew)nn.getPrev(0)).getType().getClassDesc(); - - - //TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps(); - - //if (tdArray.length==0) - // return null; - - //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; -} + processed.add(fstemp); - private Vector evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){ - FlagState fstemp=fs; - //FlagState[] fstemparray=new FlagState[3]; - Vector inprocess=new Vector(); - Vector processed=new Vector(); - - 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)); - } - - inprocess.add(fstemp); - processed.add(fstemp); - - for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) { - TempTagPair ttp=(TempTagPair)it_ttp.next(); - - if (temp==ttp.getTemp()){ - processed=new Vector(); - for (Enumeration en=inprocess.elements();en.hasMoreElements();){ - FlagState fsworking=(FlagState)en.nextElement(); - if (((FlatFlagActionNode)nn).getTagChange(ttp)){ - fsworking=fsworking.setTag(ttp.getTag()); - processed.add(fsworking); - } - else - { - processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag()))); - } - } - inprocess=processed; - } + //Process clears first + for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + + if (temp==ttp.getTemp()) { + Vector oldprocess=processed; + processed=new Vector(); + + 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 processed; - -} + } + } + //Process sets next + for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + if (temp==ttp.getTemp()) { + Vector oldprocess=processed; + processed=new Vector(); + + 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)) @@ -413,88 +383,62 @@ private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){ */ 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()); - - File dotfile_tasknodes=new File("graph"+cd.getSymbol()+"_task.dot"); - dotstream=new FileOutputStream(dotfile_tasknodes,true); - TaskNode.DOTVisitor.visit(dotstream,(produceTaskNodes((Hashtable)flagstates.get(cd))).values()); + File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot"); + FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false); + FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values()); } - - - private void createPossibleRuntimeStates(FlagState fs) { - ClassDescriptor cd = fs.getClassDescriptor(); - Hashtable sourcenodes=(Hashtable)flagstates.get(cd); - FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd); - int externs=((Integer)extern_flags.get(cd)).intValue(); - - if(externs==0) - return; - int noOfIterations=(1< getFlagStates(ClassDescriptor cd) { + if (flagstates.containsKey(cd)) + return ((Hashtable)flagstates.get(cd)).keySet(); + else + return new HashSet(); } - for(int k=0; k sourcenodes=(Hashtable)flagstates.get(cd); + FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd); + int externs=((Integer)extern_flags.get(cd)).intValue(); - FlagState fstemp=fs; + if(externs==0) + return; - for(int i=0; i < externs;i++) { - fstemp=fstemp.setFlag(fd[i],BoolValTable[i]); - } - if (!sourcenodes.containsKey(fstemp)) - toprocess.add(fstemp); - - fstemp=canonicalizeFlagState(sourcenodes,fstemp); - fs.addEdge(new FEdge(fstemp,"Runtime")); - } - } + int noOfIterations=(1< fsnodes){ - - Hashtable tasknodes=new Hashtable(); - for(Enumeration en=fsnodes.keys();en.hasMoreElements();){ - FlagState fs=(FlagState)en.nextElement(); - - Iterator it_inedges=fs.inedges(); - TaskNode tn; - do{ - if (!fs.inedges().hasNext()){ - tn=new TaskNode("Start Node"); - }else{ - FEdge inedge=(FEdge)it_inedges.next(); - tn=new TaskNode(inedge.getLabel()); - } - if(fs.edges().hasNext()){ - tn=(TaskNode)canonicalizeTaskNode(tasknodes, tn); - for (Iterator it_edges=fs.edges();it_edges.hasNext();){ - TaskNode target=new TaskNode(((FEdge)it_edges.next()).getLabel()); - target=(TaskNode)canonicalizeTaskNode(tasknodes,target); - tn.addEdge(new TEdge(target)); - } - } - }while(it_inedges.hasNext()); - } - return tasknodes; + for(int i=0; i < externs ; i++) { + BoolValTable[i]=fs.get(fd[i]); } + for(int k=0; k