1 package Analysis.TaskStateAnalysis;
2 import Analysis.TaskStateAnalysis.*;
8 import java.io.FileWriter;
10 public class TaskAnalysis {
14 Hashtable extern_flags;
15 Queue<FlagState> q_main;
22 * @param state a flattened State object
24 * @param map Hashtable containing the temp to var mapping
26 public TaskAnalysis(State state,Hashtable map)
32 /** This function builds a table of flags for each class **/
34 private void getFlagsfromClasses() {
35 flags=new Hashtable();
36 extern_flags = new Hashtable();
38 for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
40 ClassDescriptor cd = (ClassDescriptor)it_classes.next();
41 System.out.println(cd.getSymbol());
42 Vector vFlags=new Vector();
43 FlagDescriptor flag[];
47 /* Adding the flags of the super class */
48 if (cd.getSuper()!=null) {
49 ClassDescriptor superdesc=cd.getSuperDesc();
51 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
52 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
53 System.out.println(fd.toString());
58 for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
59 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
60 System.out.println(fd.toString());
64 if (vFlags.size()!=0) {
65 flag=new FlagDescriptor[vFlags.size()];
67 for(int i=0;i < vFlags.size() ; i++) {
68 if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
69 flag[ctr]=(FlagDescriptor)vFlags.get(i);
70 vFlags.remove(flag[ctr]);
74 for(int i=0;i < vFlags.size() ; i++) {
75 flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
77 extern_flags.put(cd,new Integer(ctr));
84 public void taskAnalysis() throws java.io.IOException {
85 Adj_List=new Hashtable();
86 Hashtable<FlagState,Vector> Adj_List_temp;
88 getFlagsfromClasses();
91 q_main=new LinkedList<FlagState>();
93 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
94 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
95 externs=((Integer)extern_flags.get(cd)).intValue();
96 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
99 System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
100 System.out.println("No of externs " + externs);
101 System.out.println("No of flags: "+fd.length);
104 Adj_List.put(cd,new Hashtable<FlagState,Vector>());
107 TypeUtil typeutil=new TypeUtil(state);
108 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
109 Adj_List_temp=(Hashtable<FlagState,Vector>)Adj_List.get(startupobject);
111 FlagState fsstartup=new FlagState(startupobject);
112 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
114 FlagState fstemp=fsstartup.setFlag(fd[0],true);
115 Vector vtemp=new Vector();
116 Edge estartup=new Edge(fstemp,"Runtime");
119 Adj_List_temp.put(fsstartup,vtemp);
121 Queue<FlagState> q_temp=analyseTasks(fstemp);
123 if ( q_temp != null) {
124 q_main.addAll(q_temp);
127 while (q_main.size() > 0) {
128 // ****debug block********
130 System.out.println("/***********contents of main q before pop**********/");
131 for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
134 FlagState fs_qm=(FlagState)it_qm.next();
136 System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
138 System.out.println("/*********************************/");
139 // ****debug block********
140 FlagState trigger=q_main.poll();
143 q_temp=createPossibleRuntimeStates(trigger);
145 if ( q_temp != null){
146 q_main.addAll(q_temp);
148 // ****debug block********
150 System.out.println("/***********contents of main q**********/");
151 for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
154 FlagState fs_qm=(FlagState)it_qm.next();
156 System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
158 System.out.println("/*********************************/");
159 // ****debug block********
161 q_temp=analyseTasks(trigger);
164 q_main.addAll(q_temp);
166 // ****debug block********
168 System.out.println("/***********contents of main q after analyse tasks**********/");
169 for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
172 FlagState fs_qm=(FlagState)it_qm.next();
174 System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
176 System.out.println("/*********************************/");
177 // ****debug block********
183 Enumeration e=Adj_List.keys();
185 while (e.hasMoreElements()) {
186 System.out.println("creating dot file");
187 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
188 System.out.println((cdtemp.getSymbol()));
189 createDOTfile(cdtemp);
196 public Queue<FlagState> analyseTasks(FlagState fs) throws java.io.IOException {
199 Hashtable Adj_List_temp;
200 Queue<FlagState> q_retval;
204 ClassDescriptor cd=fs.getClassDescriptor();
206 Adj_List_temp=(Hashtable)Adj_List.get(cd);
208 int externs=((Integer)extern_flags.get(cd)).intValue();
209 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
211 q_retval=new LinkedList<FlagState>();
214 //while (q.size() != 0) {
215 System.out.println("inside while loop in analysetasks \n");
218 //FlagDescriptor[] ftemp=(FlagDescriptor[])flags.get(cd);
219 //System.out.println("Processing state: "+cd.getSymbol()+" " + fsworking.toString(ftemp));
223 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
224 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
225 boolean taskistriggered=false;
227 String taskname=getTaskName(td);
233 System.out.println("Method: AnalyseTasks");
234 System.out.println(taskname);
235 System.out.println();
241 for(int i=0; i < td.numParameters(); i++) {
242 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
243 //if ( (td.getParamType(i).equals(cd))&&(isTaskTrigger(fen,fs))){
244 if ((isParamOfSameClass(td.getParamType(i),cd)) && (isTaskTrigger(fen,fs))){
245 taskistriggered = true;
246 System.out.println(td.getParamType(i).toString()+" "+cd.toString());
247 temp=(TempDescriptor)map.get(td.getParameter(i));
253 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
255 if (taskistriggered) {
258 System.out.println("inside taskistriggered");
262 taskistriggered=false;
263 Adj_List_temp.put(fs,new Vector());
265 //Iterating through the nodes
266 FlatMethod fm = state.getMethodFlat(td);
267 FlatNode fn=fm.methodEntryNode();
269 HashSet tovisit= new HashSet();
270 HashSet visited= new HashSet();
273 while(!tovisit.isEmpty()) {
274 FlatNode fn1 = (FlatNode)tovisit.iterator().next();
277 for(int i = 0; i < fn1.numNext(); i++) {
278 FlatNode nn=fn1.getNext(i);
281 if (((FlatFlagActionNode)nn).getFFANType() == FlatFlagActionNode.PRE) {
282 throw new Error("PRE FlagActions not supported");
284 } else if (((FlatFlagActionNode)nn).getFFANType() == FlatFlagActionNode.NEWOBJECT) {
286 System.out.println("NEWObject");
289 q_retval.offer(evalNewObjNode(nn));
293 // ****debug block********
294 // System.out.println("/***********contents of q ret **********/");
295 /* for (Iterator it_qret=q_retval.iterator();it_qret.hasNext();) {
296 TriggerState ts_qret=(TriggerState)it_qret.next();
297 FlagState fs_qret=ts_qret.getState();
299 System.out.println("FS : "+fs_qret.toString((FlagDescriptor [])flags.get(ts_qret.getClassDescriptor())));
301 // ****debug block********
304 if (((FlatFlagActionNode)nn).getFFANType() == FlatFlagActionNode.TASKEXIT) {
307 System.out.println("TaskExit");
309 FlagState fs_taskexit=evalTaskExitNode(nn,cd,fs);
313 if (!edgeexists(Adj_List_temp,fs,fs_taskexit,taskname)) {
314 ((Vector)Adj_List_temp.get(fs)).add(new Edge(fs_taskexit,taskname));
316 if ((!wasFlagStateProcessed(Adj_List_temp,fs_taskexit)) && (!existsInQMain(fs_taskexit)) && (!existsInQ(q_retval,fs_taskexit))){
317 q_retval.offer(fs_taskexit);
322 if (!visited.contains(nn) && !tovisit.contains(nn)) {
330 if (q_retval.size()==0)
336 private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) {
337 if (fen instanceof FlagNode)
338 return fs.get(((FlagNode)fen).getFlag());
340 switch (((FlagOpNode)fen).getOp().getOp()) {
341 case Operation.LOGIC_AND:
342 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
343 case Operation.LOGIC_OR:
344 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
345 case Operation.LOGIC_NOT:
346 return !(isTaskTrigger(((FlagOpNode)fen).getLeft(),fs));
352 private boolean isParamOfSameClass(TypeDescriptor typedesc, ClassDescriptor classdesc){
353 if (typedesc.getSafeSymbol().equals(classdesc.getSafeSymbol()))
360 private FlagState evalNewObjNode(FlatNode nn){
361 TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
363 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
364 ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
366 FlagState fstemp=new FlagState(cd_new);
368 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
369 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
370 if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
372 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
380 private FlagState evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs){
383 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
384 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
385 if (temp.toString().equals(tfp.getTemp().toString()))
386 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
392 private boolean wasFlagStateProcessed(Hashtable Adj_List,FlagState fs) {
393 Enumeration e=Adj_List.keys();
395 while(e.hasMoreElements()) {
396 FlagState fsv = (FlagState)(e.nextElement());
404 /* private boolean existsInQueue(TriggerState ts) {
405 throw new Error("Use hashcode/contains of set method to find...no linear search allowed");
408 private boolean existsInQMain(FlagState fs) {
409 if (q_main.contains(fs))
415 private boolean existsInQ(Queue q,FlagState fs) {
423 public void printAdjList(ClassDescriptor cd) {
424 Enumeration e=((Hashtable)Adj_List.get(cd)).keys();
425 while(e.hasMoreElements()) {
426 FlagState fsv = (FlagState)(e.nextElement());
427 System.out.println(fsv.toString((FlagDescriptor [])flags.get(cd)));
431 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
432 File dotfile= new File("graph"+cd.getSymbol()+".dot");
434 FileWriter dotwriter=new FileWriter(dotfile,true);
436 dotwriter.write("digraph G{ \n");
437 dotwriter.write("center=true;\norientation=landscape;\n");
440 FlagDescriptor[] flg=(FlagDescriptor [])flags.get(cd);
441 for(int i = 0; i < flg.length ; i++)
443 dotwriter.write(flg[i].toString()+"\n");
447 Enumeration e=((Hashtable)Adj_List.get(cd)).keys();
448 while(e.hasMoreElements()) {
449 FlagState fsv = (FlagState)(e.nextElement());
450 System.out.println(fsv.toString());
451 Hashtable test=(Hashtable)Adj_List.get(cd);
452 Vector edges=(Vector)test.get(fsv);
453 for(int i=0;i < edges.size();i++) {
454 dotwriter.write(fsv.toString((FlagDescriptor [])flags.get(cd))+" -> "+((Edge)edges.get(i)).getTarget().toString((FlagDescriptor [])flags.get(cd))+"[label=\""+((Edge)edges.get(i)).getLabel()+"\"];\n");
458 dotwriter.write("}\n");
463 private String getTaskName(TaskDescriptor td) {
464 StringTokenizer st = new StringTokenizer(td.toString(),"(");
465 return st.nextToken();
468 private boolean edgeexists(Hashtable Adj_List_local,FlagState v1, FlagState v2,String label) {
469 Vector edges=(Vector)Adj_List_local.get(v1);
472 for(int i=0;i < edges.size();i++) {
473 FlagState fs=((Edge)edges.get(i)).getTarget();
474 if (fs.equals(v2) && (label.compareTo(((Edge)edges.get(i)).getLabel())==0))
481 private Queue createPossibleRuntimeStates(FlagState fs) throws java.io.IOException {
483 int noOfIterations, externs;
484 Hashtable Adj_List_temp, Adj_List_local;
487 System.out.println("Inside CreatePossible runtime states");
489 ClassDescriptor cd = fs.getClassDescriptor();
491 Adj_List_temp=(Hashtable)Adj_List.get(cd);
492 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
493 externs=((Integer)extern_flags.get(cd)).intValue();
494 //System.out.println("No of externs:"+externs);
497 Queue<FlagState> q_ret=new LinkedList<FlagState>();
500 noOfIterations=(1<<externs) - 1;
501 // System.out.println("No of iterations: "+noOfIterations);
502 boolean BoolValTable[]=new boolean[externs];
504 for(int i=0; i < externs ; i++) {
505 System.out.println(fd[i].getSymbol());
506 BoolValTable[i]=fs.get(fd[i]);
509 /* if (! wasFlagStateProcessed(Adj_List_temp,fs)) {
510 Adj_List_temp.put(fs,new Vector());
514 Adj_List_local=new Hashtable();
515 Adj_List_local.put(fs, new Vector());
518 for(int k=0; k<noOfIterations; k++) {
519 for(int j=0; j < externs ;j++) {
520 if ((k% (1<<j)) == 0)
521 BoolValTable[j]=(!BoolValTable[j]);
526 for(int i=0; i < externs;i++) {
527 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
529 Adj_List_local.put(fstemp,new Vector());
531 if (!existsInQMain(fstemp) && ! wasFlagStateProcessed(Adj_List_temp,fs)){
535 for (Enumeration en=Adj_List_local.keys();en.hasMoreElements();){
536 FlagState fs_local=(FlagState)en.nextElement();
537 System.out.println(fs_local.toString(fd)+" : "+fstemp.toString(fd));
538 if (fstemp.equals(fs_local))
540 System.out.print(" : equal");
544 //if (!edgeexists(Adj_List_local,fstemp,fs_local,"Runtime"))
545 ((Vector)Adj_List_local.get(fstemp)).add(new Edge(fs_local,"Runtime"));
546 //System.out.println(fstemp.toString(fd)+" : "+fs_local.toString(fd));
548 //if (!edgeexists(Adj_List_local,fs_local,fstemp,"Runtime"))
549 ((Vector)Adj_List_local.get(fs_local)).add(new Edge(fstemp,"Runtime"));
550 //System.out.println(fs_local.toString(fd)+" : "+fstemp.toString(fd));
558 for (Enumeration en=Adj_List_local.keys();en.hasMoreElements();){
559 FlagState fs_local=(FlagState)en.nextElement();
560 System.out.print("Source FS: "+fs_local.toString(fd)+" -> ");
561 Vector edges=(Vector)Adj_List_local.get(fs_local);
563 for(int i=0;i < edges.size();i++) {
564 Edge edge=(Edge)edges.get(i);
565 System.out.print("("+edge.getTarget().toString(fd)+" "+edge.getLabel()+")\n");
570 for (Enumeration en=Adj_List_local.keys();en.hasMoreElements();){
571 FlagState fs_local=(FlagState)en.nextElement();
572 if (wasFlagStateProcessed(Adj_List_temp,fs_local)){
573 System.out.println("FS: "+fs_local.toString(fd)+" processed already");
574 //Add edges that don't exist already.
575 Vector edges=(Vector)Adj_List_local.get(fs_local);
577 for(int i=0;i < edges.size();i++) {
578 Edge edge=(Edge)edges.get(i);
579 if (! ((Vector)Adj_List_temp.get(fs_local)).contains(edge))
580 ((Vector)Adj_List_temp.get(fs_local)).add(edge);
583 //((Vector)Adj_List_temp.get(fs_local)).addAll((Vector)Adj_List_local.get(fs_local));
586 System.out.println("FS: "+fs_local.toString(fd)+" not processed already");
587 Adj_List_temp.put(fs_local,(Vector)Adj_List_local.get(fs_local));
592 for (Enumeration en=Adj_List_temp.keys();en.hasMoreElements();){
593 FlagState fs_local=(FlagState)en.nextElement();
594 System.out.print("Source FS: "+fs_local.toString(fd)+" -> ");
595 Vector edges=(Vector)Adj_List_local.get(fs_local);
597 for(int i=0;i < edges.size();i++) {
598 Edge edge=(Edge)edges.get(i);
599 System.out.print("("+edge.getTarget().toString(fd)+" "+edge.getLabel()+")\n");
615 private void processTasksWithPost(ClassDescriptor cd, Hashtable pre) {
618 private ClassDescriptor processFlatNew(FlatNode fn) {
619 if (! (fn.getNext(0).kind() == 13)) {
620 return (((FlatNew)fn).getType().getClassDesc());