1 package Analysis.TaskStateAnalysis;
2 import Analysis.TaskStateAnalysis.*;
8 import java.io.FileWriter;
9 import java.io.FileOutputStream;
12 public class TaskAnalysis {
16 Hashtable extern_flags;
17 Queue<FlagState> q_main;
25 * @param state a flattened State object
27 * @param map Hashtable containing the temp to var mapping
29 public TaskAnalysis(State state,Hashtable map)
33 this.typeutil=new TypeUtil(state);
36 /** This function builds a table of flags for each class **/
38 private void getFlagsfromClasses() {
39 flags=new Hashtable();
40 extern_flags = new Hashtable();
42 for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
44 ClassDescriptor cd = (ClassDescriptor)it_classes.next();
45 System.out.println(cd.getSymbol());
46 Vector vFlags=new Vector();
47 FlagDescriptor flag[];
51 /* Adding the flags of the super class */
52 if (cd.getSuper()!=null) {
53 ClassDescriptor superdesc=cd.getSuperDesc();
55 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
56 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
57 System.out.println(fd.toString());
62 for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
63 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
64 System.out.println(fd.toString());
68 if (vFlags.size()!=0) {
69 flag=new FlagDescriptor[vFlags.size()];
71 for(int i=0;i < vFlags.size() ; i++) {
72 if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
73 flag[ctr]=(FlagDescriptor)vFlags.get(i);
74 vFlags.remove(flag[ctr]);
78 for(int i=0;i < vFlags.size() ; i++) {
79 flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
81 extern_flags.put(cd,new Integer(ctr));
88 public void taskAnalysis() throws java.io.IOException {
89 flagstates=new Hashtable();
90 Hashtable<FlagState,FlagState> sourcenodes;
92 getFlagsfromClasses();
95 q_main=new LinkedList<FlagState>();
97 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
98 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
99 externs=((Integer)extern_flags.get(cd)).intValue();
100 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
103 System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
104 System.out.println("No of externs " + externs);
105 System.out.println("No of flags: "+fd.length);
108 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
112 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
114 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
116 FlagState fsstartup=new FlagState(startupobject);
117 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
119 fsstartup=fsstartup.setFlag(fd[0],true);
121 sourcenodes.put(fsstartup,fsstartup);
123 Queue<FlagState> q_temp=analyseTasks(fsstartup);
125 if ( q_temp != null) {
126 q_main.addAll(q_temp);
129 while (q_main.size() > 0) {
130 // ****debug block********
132 System.out.println("/***********contents of main q before pop**********/");
133 for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
136 FlagState fs_qm=(FlagState)it_qm.next();
138 System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
140 System.out.println("/*********************************/");
141 // ****debug block********
142 FlagState trigger=q_main.poll();
145 q_temp=createPossibleRuntimeStates(trigger);
147 if ( q_temp != null){
148 q_main.addAll(q_temp);
150 // ****debug block********
152 System.out.println("/***********contents of main q**********/");
153 for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
156 FlagState fs_qm=(FlagState)it_qm.next();
158 System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
160 System.out.println("/*********************************/");
161 // ****debug block********
163 q_temp=analyseTasks(trigger);
166 q_main.addAll(q_temp);
168 // ****debug block********
170 System.out.println("/***********contents of main q after analyse tasks**********/");
171 for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
174 FlagState fs_qm=(FlagState)it_qm.next();
176 System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
178 System.out.println("/*********************************/");
179 // ****debug block********
185 Enumeration e=flagstates.keys();
187 while (e.hasMoreElements()) {
188 System.out.println("creating dot file");
189 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
190 System.out.println((cdtemp.getSymbol()));
191 createDOTfile(cdtemp);
198 public Queue<FlagState> analyseTasks(FlagState fs) throws java.io.IOException {
201 Hashtable<FlagState,FlagState> sourcenodes;
202 Queue<FlagState> q_retval;
206 ClassDescriptor cd=fs.getClassDescriptor();
208 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
210 int externs=((Integer)extern_flags.get(cd)).intValue();
211 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
213 q_retval=new LinkedList<FlagState>();
216 //while (q.size() != 0) {
217 System.out.println("inside while loop in analysetasks \n");
220 //FlagDescriptor[] ftemp=(FlagDescriptor[])flags.get(cd);
221 //System.out.println("Processing state: "+cd.getSymbol()+" " + fsworking.toString(ftemp));
225 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
226 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
227 boolean taskistriggered=false;
229 String taskname=getTaskName(td);
235 System.out.println("Method: AnalyseTasks");
236 System.out.println(taskname);
237 System.out.println();
243 for(int i=0; i < td.numParameters(); i++) {
244 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
245 //if ( (td.getParamType(i).equals(cd))&&(isTaskTrigger(fen,fs))){
246 if ((isParamOfSameClass(td.getParamType(i),cd)) && (isTaskTrigger(fen,fs))){
247 taskistriggered = true;
248 System.out.println(td.getParamType(i).toString()+" "+cd.toString());
249 temp=(TempDescriptor)map.get(td.getParameter(i));
255 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
257 if (taskistriggered) {
260 System.out.println("inside taskistriggered");
264 taskistriggered=false;
265 if (!wasFlagStateProcessed(sourcenodes,fs)){
266 sourcenodes.put(fs,fs);
269 fs=sourcenodes.get(fs);
272 //Iterating through the nodes
273 FlatMethod fm = state.getMethodFlat(td);
274 FlatNode fn=fm.methodEntryNode();
276 HashSet tovisit= new HashSet();
277 HashSet visited= new HashSet();
280 while(!tovisit.isEmpty()) {
281 FlatNode fn1 = (FlatNode)tovisit.iterator().next();
284 for(int i = 0; i < fn1.numNext(); i++) {
285 FlatNode nn=fn1.getNext(i);
286 if (nn.kind()==FKind.FlatFlagActionNode) {
288 if (((FlatFlagActionNode)nn).getTaskType() == FlatFlagActionNode.PRE) {
289 throw new Error("PRE FlagActions not supported");
291 } else if (((FlatFlagActionNode)nn).getTaskType() == FlatFlagActionNode.NEWOBJECT) {
293 System.out.println("NEWObject");
296 q_retval.offer(evalNewObjNode(nn));
298 if (((FlatFlagActionNode)nn).getTaskType() == FlatFlagActionNode.TASKEXIT) {
300 System.out.println("TaskExit");
302 FlagState fs_taskexit=evalTaskExitNode(nn,cd,fs);
304 Edge newedge=new Edge(fs_taskexit,taskname);
305 if (!edgeexists(fs,newedge)) {
308 if ((!wasFlagStateProcessed(sourcenodes,fs_taskexit)) && (!existsInQMain(fs_taskexit)) && (!existsInQ(q_retval,fs_taskexit))){
309 q_retval.offer(fs_taskexit);
314 if (!visited.contains(nn) && !tovisit.contains(nn)) {
322 if (q_retval.size()==0)
328 private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) {
329 if (fen instanceof FlagNode)
330 return fs.get(((FlagNode)fen).getFlag());
332 switch (((FlagOpNode)fen).getOp().getOp()) {
333 case Operation.LOGIC_AND:
334 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
335 case Operation.LOGIC_OR:
336 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
337 case Operation.LOGIC_NOT:
338 return !(isTaskTrigger(((FlagOpNode)fen).getLeft(),fs));
344 private boolean isParamOfSameClass(TypeDescriptor typedesc, ClassDescriptor classdesc){
345 /* Set subclasses=typeutil.getSubClasses(classdesc);
346 if (subclasses!=null){
347 if (subclasses.contains(typedesc.getClassDesc()) || typedesc.getClassDesc().equals(classdesc))
353 if (typedesc.getClassDesc().equals(classdesc))
359 return typeutil.isSuperorType(classdesc,typedesc.getClassDesc());
365 private FlagState evalNewObjNode(FlatNode nn){
366 TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
368 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
369 ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
371 FlagState fstemp=new FlagState(cd_new);
373 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
374 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
375 if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
377 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
385 private FlagState evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs){
388 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
389 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
390 if (temp.toString().equals(tfp.getTemp().toString()))
391 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
397 private boolean wasFlagStateProcessed(Hashtable sourcenodes,FlagState fs) {
398 if (sourcenodes.containsKey(fs))
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 {
433 File dotfile= new File("graph"+cd.getSymbol()+".dot");
435 /*FileOutputStream dotstream=new FileOutputStream(dotfile,true);
437 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
440 FileWriter dotwriter=new FileWriter(dotfile,true);
442 dotwriter.write("digraph G{ \n");
443 dotwriter.write("center=true;\norientation=landscape;\n");
446 FlagDescriptor[] flg=(FlagDescriptor [])flags.get(cd);
447 for(int i = 0; i < flg.length ; i++)
449 dotwriter.write(flg[i].toString()+"\n");
453 Iterator it_sourcenodes=((Hashtable)flagstates.get(cd)).values().iterator();
454 while(it_sourcenodes.hasNext()) {
455 FlagState fsv = (FlagState)(it_sourcenodes.next());
456 System.out.println(fsv.toString());
458 for(Iterator it_edges=fsv.edges();it_edges.hasNext();) {
459 Edge tonode=(Edge)it_edges.next();
460 dotwriter.write(fsv.toString(flg)+" -> "+tonode.getTarget().toString(flg)+"[label=\""+tonode.getLabel()+"\"];\n");
464 dotwriter.write("}\n");
470 private String getTaskName(TaskDescriptor td) {
471 StringTokenizer st = new StringTokenizer(td.toString(),"(");
472 return st.nextToken();
475 /* private boolean edgeexists(Hashtable Adj_List_local,FlagState v1, FlagState v2,String label) {
476 Vector edges=(Vector)Adj_List_local.get(v1);
479 for(int i=0;i < edges.size();i++) {
480 FlagState fs=((Edge)edges.get(i)).getTarget();
481 if (fs.equals(v2) && (label.compareTo(((Edge)edges.get(i)).getLabel())==0))
488 private boolean edgeexists(FlagState fs, Edge newedge){
489 for(Iterator it_edges=fs.edges();it_edges.hasNext();){
490 Edge e=(Edge)it_edges.next();
491 if (newedge.equals(e))
497 private Queue createPossibleRuntimeStates(FlagState fs) throws java.io.IOException {
499 int noOfIterations, externs;
500 Hashtable<FlagState,FlagState> sourcenodes;
503 System.out.println("Inside CreatePossible runtime states");
505 ClassDescriptor cd = fs.getClassDescriptor();
507 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
508 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
509 externs=((Integer)extern_flags.get(cd)).intValue();
510 //System.out.println("No of externs:"+externs);
513 Queue<FlagState> q_ret=new LinkedList<FlagState>();
516 noOfIterations=(1<<externs) - 1;
517 // System.out.println("No of iterations: "+noOfIterations);
518 boolean BoolValTable[]=new boolean[externs];
520 for(int i=0; i < externs ; i++) {
521 System.out.println(fd[i].getSymbol());
522 BoolValTable[i]=fs.get(fd[i]);
525 /* if (! wasFlagStateProcessed(Adj_List_temp,fs)) {
526 Adj_List_temp.put(fs,new Vector());
530 sourcenodes.put(fs,fs);
532 for(int k=0; k<noOfIterations; k++) {
533 for(int j=0; j < externs ;j++) {
534 if ((k% (1<<j)) == 0)
535 BoolValTable[j]=(!BoolValTable[j]);
540 for(int i=0; i < externs;i++) {
541 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
543 fs.addEdge(new Edge(fstemp,"Runtime"));
545 if (!existsInQMain(fstemp) && ! wasFlagStateProcessed(sourcenodes,fstemp)){
557 private void processTasksWithPost(ClassDescriptor cd, Hashtable pre) {
560 private ClassDescriptor processFlatNew(FlatNode fn) {
561 if (! (fn.getNext(0).kind() == 13)) {
562 return (((FlatNew)fn).getType().getClassDesc());