1 package Analysis.TaskStateAnalysis;
7 import java.io.FileWriter;
8 import java.io.FileOutputStream;
10 public class TaskTagAnalysis {
12 TagAnalysis taganalysis;
15 HashSet<TagState> toprocess;
16 HashSet<TagState> discovered;
17 Hashtable<TaskDescriptor, TaskQueue> tasktable;
18 Hashtable<TagDescriptor, Set<TagState>> tsresults;
19 Hashtable<ClassDescriptor, Set<TagState>> fsresults;
26 public TaskTagAnalysis(State state, TagAnalysis taganalysis) {
28 this.typeutil=new TypeUtil(state);
29 this.taganalysis=taganalysis;
30 this.flaginfo=new FlagInfo(state);
31 this.toprocess=new HashSet<TagState>();
32 this.discovered=new HashSet<TagState>();
33 this.tasktable=new Hashtable<TaskDescriptor, TaskQueue>();
34 this.tsresults=new Hashtable<TagDescriptor, Set<TagState>>();
35 this.fsresults=new Hashtable<ClassDescriptor, Set<TagState>>();
38 for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
39 TaskDescriptor td=(TaskDescriptor)taskit.next();
40 tasktable.put(td, new TaskQueue(td));
46 private void doOutput() {
48 for(Iterator<TagDescriptor> tagit=tsresults.keySet().iterator();tagit.hasNext();) {
49 TagDescriptor tag=tagit.next();
50 Set<TagState> set=tsresults.get(tag);
51 File dotfile_flagstates= new File("tag"+tag.getSymbol()+".dot");
52 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
53 TagState.DOTVisitor.visit(dotstream,set);
55 for(Iterator<ClassDescriptor> cdit=fsresults.keySet().iterator();cdit.hasNext();) {
56 ClassDescriptor cd=cdit.next();
57 Set<TagState> set=fsresults.get(cd);
58 File dotfile_flagstates= new File("class"+cd.getSymbol()+".dot");
59 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
60 TagState.DOTVisitor.visit(dotstream,set);
62 } catch (Exception e) {
67 private void doAnalysis() {
68 toprocess.add(createInitialState());
69 while(!toprocess.isEmpty()) {
70 TagState ts=toprocess.iterator().next();
72 //Loop through each task
73 for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
74 TaskDescriptor td=(TaskDescriptor)taskit.next();
75 TaskQueue tq=tasktable.get(td);
76 processTask(td, tq, ts);
81 private void processTask(TaskDescriptor td, TaskQueue tq, TagState ts) {
82 Set<FlagState> flagset=ts.getFS();
83 for(Iterator<FlagState> fsit=flagset.iterator();fsit.hasNext();) {
84 FlagState fs=fsit.next();
85 FlagTagState fts=new FlagTagState(ts, fs);
86 for(int i=0;i<td.numParameters();i++) {
87 System.out.println("Trying to enqueue "+td);
88 if (canEnqueue(td, i, fs)) {
89 System.out.println("Enqueued");
90 TaskQueueIterator tqi=tq.enqueue(i, fts);
91 while(tqi.hasNext()) {
92 System.out.println("binding");
101 private void processBinding(TaskQueueIterator tqi) {
102 TaskBinding tb=new TaskBinding(tqi);
103 while(tb.hasNext()) {
109 private Hashtable<TempDescriptor, Wrapper> computeInitialState(Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> maintable, FlatNode fn) {
110 Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
111 Hashtable<TagWrapper,TagWrapper> tagtable=new Hashtable<TagWrapper, TagWrapper>();
112 for(int i=0;i<fn.numPrev();i++) {
113 FlatNode fnprev=fn.getPrev(i);
114 Hashtable<TempDescriptor, Wrapper> prevtable=maintable.get(fn);
116 //Iterator through the Tags
117 for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
118 TempDescriptor tmp=tmpit.next();
119 Wrapper prevtag=prevtable.get(tmp);
120 if (prevtag instanceof ObjWrapper)
122 if (table.containsKey(tmp)) {
124 TagWrapper currtag=(TagWrapper) table.get(tmp);
125 tagtable.put((TagWrapper)prevtag, currtag);
126 assert(currtag.initts.equals(((TagWrapper)prevtag).initts));
127 for(Iterator<TagState> tagit=((TagWrapper)prevtag).ts.iterator();tagit.hasNext();) {
128 TagState tag=tagit.next();
129 if (!currtag.ts.contains(tag)) {
134 TagWrapper clonetag=((TagWrapper)prevtag).clone();
135 tagtable.put((TagWrapper)prevtag, clonetag);
136 table.put(tmp, clonetag);
140 //Iterator through the Objects
141 for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
142 TempDescriptor tmp=tmpit.next();
143 Wrapper obj=prevtable.get(tmp);
144 if (obj instanceof TagWrapper)
146 ObjWrapper prevobj=(ObjWrapper)obj;
147 if (!table.containsKey(tmp)) {
149 ObjWrapper newobj=new ObjWrapper();
150 newobj.initfs=prevobj.initfs;
151 table.put(tmp, newobj);
153 ObjWrapper currobj=(ObjWrapper) table.get(tmp);
154 assert(currobj.initfs.equals(prevobj.initfs));
155 for(Iterator<TagWrapper> tagit=prevobj.tags.iterator();tagit.hasNext();) {
156 TagWrapper tprev=tagit.next();
157 TagWrapper t=tagtable.get(tprev);
160 for(Iterator<FlagState> flagit=prevobj.fs.iterator();flagit.hasNext();) {
161 FlagState fs=flagit.next();
169 private void processFlatFlag(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
170 if (fn.getTaskType()==FlatFlagActionNode.PRE) {
171 throw new Error("Unsupported");
172 } else if (fn.getTaskType()==FlatFlagActionNode.TASKEXIT) {
173 evalTaskExitNode(fn, table);
174 } else if (fn.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
175 evalNewNode(fn, table, td);
179 private void setFlag(ObjWrapper ow, FlagDescriptor fd, boolean value) {
180 HashSet<FlagState> newstate=new HashSet<FlagState>();
181 Hashtable<FlagState, FlagState> flagmap=new Hashtable<FlagState, FlagState>();
182 for(Iterator<FlagState> flagit=ow.fs.iterator();flagit.hasNext();) {
183 FlagState fs=flagit.next();
184 FlagState fsnew=canonical(fs.setFlag(fd, value));
186 flagmap.put(fs, fsnew);
189 for(Iterator<TagWrapper> tagit=ow.tags.iterator();tagit.hasNext();) {
190 TagWrapper tw=tagit.next();
191 HashSet<TagState> newstates=new HashSet<TagState>();
192 for(Iterator<TagState> tgit=tw.ts.iterator();tgit.hasNext();) {
193 TagState ts=tgit.next();
194 for(Iterator<FlagState> flagit=ts.getFS().iterator();flagit.hasNext();) {
195 FlagState fs=flagit.next();
196 if (flagmap.containsKey(fs)) {
197 if (flagmap.get(fs).equals(fs)) {
200 TagState tsarray[]=ts.clearFS(fs);
201 //Can do strong update here because these
202 //must be parameter objects...therefore
203 //all possible aliasing relationships are
205 for(int i=0;i<tsarray.length;i++) {
206 TagState ts2=canonical(tsarray[i]);
207 TagState tsarray2[]=ts2.addnewFS(flagmap.get(fs));
208 for(int j=0;j<tsarray2.length;j++)
209 newstates.add(canonical(tsarray2[j]));
219 private void setTag(ObjWrapper ow, TagWrapper twnew, TagDescriptor tag, boolean value) {
221 if (ow.tags.contains(twnew)) {
222 System.out.println("Tag already bound to object.");
226 if (!ow.tags.contains(twnew)) {
227 System.out.println("Tag not bound to object.");
231 HashSet<FlagState> newfsstates=new HashSet<FlagState>();
232 Hashtable<FlagState, FlagState[]> flagmap=new Hashtable<FlagState, FlagState[]>();
233 //Change the flag states
234 for(Iterator<FlagState> fsit=ow.fs.iterator();fsit.hasNext();) {
235 FlagState fs=fsit.next();
236 FlagState[] fsnew=canonical(fs.setTag(tag, value));
237 flagmap.put(fs, fsnew);
238 newfsstates.addAll(Arrays.asList(fsnew));
240 for(Iterator<TagWrapper> tagit=ow.tags.iterator();tagit.hasNext();) {
241 TagWrapper tw=tagit.next();
242 HashSet<TagState> newstates=new HashSet<TagState>();
243 for(Iterator<TagState> tgit=tw.ts.iterator();tgit.hasNext();) {
244 TagState ts=tgit.next();
245 for(Iterator<FlagState> flagit=ts.getFS().iterator();flagit.hasNext();) {
246 FlagState fs=flagit.next();
247 if (flagmap.containsKey(fs)) {
248 FlagState[] fmap=flagmap.get(fs);
249 for(int i=0;i<fmap.length;i++) {
250 FlagState fsnew=fmap[i];
251 if (fsnew.equals(fs)) {
254 TagState tsarray[]=ts.clearFS(fs);
255 //Can do strong update here because
256 //these must be parameter
257 //objects...therefore all possible
258 //aliasing relationships are explored
259 for(int j=0;j<tsarray.length;j++) {
260 TagState ts2=canonical(tsarray[j]);
261 TagState tsarray2[]=ts2.addnewFS(fsnew);
262 for(int k=0;k<tsarray2.length;k++)
263 newstates.add(canonical(tsarray2[k]));
274 HashSet<TagState> newstates=new HashSet<TagState>();
275 for(Iterator<TagState> tgit=twnew.ts.iterator();tgit.hasNext();) {
276 TagState ts=tgit.next();
277 for(Iterator<FlagState> flagit=newfsstates.iterator();flagit.hasNext();) {
278 FlagState fsnew=flagit.next();
279 //Can do strong update here because these must
280 //be parameter objects...therefore all
281 //possible aliasing relationships are explored
284 tsarray2=ts.addnewFS(fsnew);
286 tsarray2=ts.clearFS(fsnew);
287 for(int j=0;j<tsarray2.length;j++)
288 newstates.add(canonical(tsarray2[j]));
297 ow.tags.remove(twnew);
301 private void evalTaskExitNode(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table) {
302 //Process clears first
303 for(Iterator<TempTagPair> it_ttp=fn.getTempTagPairs();it_ttp.hasNext();) {
304 TempTagPair ttp=it_ttp.next();
305 TempDescriptor tmp=ttp.getTemp();
306 TagDescriptor tag=ttp.getTag();
307 TempDescriptor tagtmp=ttp.getTagTemp();
308 TagWrapper tagw=(TagWrapper)table.get(tagtmp);
309 boolean newtagstate=fn.getTagChange(ttp);
310 ObjWrapper ow=(ObjWrapper)table.get(tmp);
312 setTag(ow, tagw, tag, newtagstate);
316 for(Iterator<TempFlagPair> it_tfp=fn.getTempFlagPairs();it_tfp.hasNext();) {
317 TempFlagPair tfp=it_tfp.next();
318 TempDescriptor tmp=tfp.getTemp();
319 FlagDescriptor fd=tfp.getFlag();
320 boolean newflagstate=fn.getFlagChange(tfp);
321 ObjWrapper ow=(ObjWrapper)table.get(tmp);
322 setFlag(ow, fd, newflagstate);
326 for(Iterator it_ttp=fn.getTempTagPairs();it_ttp.hasNext();) {
327 TempTagPair ttp=(TempTagPair)it_ttp.next();
328 TempDescriptor tmp=ttp.getTemp();
329 TagDescriptor tag=ttp.getTag();
330 TempDescriptor tagtmp=ttp.getTagTemp();
331 TagWrapper tagw=(TagWrapper)table.get(tagtmp);
332 boolean newtagstate=fn.getTagChange(ttp);
333 ObjWrapper ow=(ObjWrapper)table.get(tmp);
335 setTag(ow, tagw, tag, newtagstate);
339 private void evalNewNode(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
340 TempDescriptor fntemp=null;
343 Iterator it=fn.getTempFlagPairs();
345 TempFlagPair tfp=(TempFlagPair)it.next();
346 fntemp=tfp.getTemp();
348 it=fn.getTempTagPairs();
351 TempTagPair ttp=(TempTagPair)it.next();
352 fntemp=ttp.getTemp();
355 FlagState fs=canonical(new FlagState(fntemp.getType().getClassDesc()));
356 ObjWrapper ow=new ObjWrapper();
358 table.put(fntemp, ow);
360 for(Iterator<TempFlagPair> it_tfp=fn.getTempFlagPairs();it_tfp.hasNext();) {
361 TempFlagPair tfp=it_tfp.next();
362 TempDescriptor tmp=tfp.getTemp();
363 FlagDescriptor fd=tfp.getFlag();
364 boolean newflagstate=fn.getFlagChange(tfp);
365 assert(ow==table.get(tmp));
366 setFlag(ow, fd, newflagstate);
369 for(Iterator it_ttp=fn.getTempTagPairs();it_ttp.hasNext();) {
370 TempTagPair ttp=(TempTagPair)it_ttp.next();
371 TempDescriptor tmp=ttp.getTemp();
372 TagDescriptor tag=ttp.getTag();
373 TempDescriptor tagtmp=ttp.getTagTemp();
374 TagWrapper tagw=(TagWrapper)table.get(tagtmp);
375 boolean newtagstate=fn.getTagChange(ttp);
376 assert(ow==table.get(tmp));
378 setTag(ow, tagw, tag, newtagstate);
380 throw new Error("Can't clear tag in newly allocated object");
382 for(Iterator<FlagState> fsit=ow.fs.iterator();fsit.hasNext();) {
383 FlagState fs2=fsit.next();
384 fs2.addAllocatingTask(td);
385 TagState ts2=new TagState(fs2.getClassDescriptor());
389 addresult(fs2.getClassDescriptor(), ts2);
390 if (!discovered.contains(ts2)) {
397 private void processFlatTag(FlatTagDeclaration fn, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
398 TempDescriptor tmp=fn.getDst();
399 if (table.containsKey(tmp)) {
400 recordtagchange((TagWrapper)table.get(tmp), td);
402 TagDescriptor tag=fn.getType();
403 TagState ts=canonical(new TagState(tag));
404 TagWrapper tw=new TagWrapper(ts);
409 private void addresult(TagDescriptor td, TagState ts) {
410 if (!tsresults.containsKey(td))
411 tsresults.put(td, new HashSet<TagState>());
412 tsresults.get(td).add(ts);
415 private void addresult(ClassDescriptor cd, TagState ts) {
416 if (!fsresults.containsKey(cd))
417 fsresults.put(cd, new HashSet<TagState>());
418 fsresults.get(cd).add(ts);
421 public void recordtagchange(TagWrapper tw, TaskDescriptor td) {
422 TagState init=tw.initts;
423 for(Iterator<TagState> tsit=tw.ts.iterator(); tsit.hasNext();) {
424 TagState ts=tsit.next();
428 TagEdge te=new TagEdge(ts, td);
429 if (!init.containsEdge(te)) {
433 if (ts.getTag()!=null)
434 addresult(ts.getTag(), ts);
436 addresult(ts.getClassDesc(), ts);
437 if (!discovered.contains(ts)) {
444 private void recordobj(ObjWrapper ow, TaskDescriptor td) {
445 for(Iterator<TagWrapper> twit=ow.tags.iterator();twit.hasNext();) {
446 TagWrapper tw=twit.next();
447 recordtagchange(tw, td);
451 private void processFlatCall(FlatCall fc, Hashtable<TempDescriptor, Wrapper> table) {
455 private void processFlatReturnNode(FlatReturnNode fr, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
456 for(Iterator<TempDescriptor> tmpit=table.keySet().iterator();tmpit.hasNext();) {
457 TempDescriptor tmp=tmpit.next();
458 Wrapper w=table.get(tmp);
459 if (w instanceof TagWrapper) {
460 TagWrapper tw=(TagWrapper)w;
461 recordtagchange(tw, td);
463 ObjWrapper ow=(ObjWrapper)w;
469 private boolean equivalent(Hashtable<TempDescriptor, Wrapper> table1, Hashtable<TempDescriptor, Wrapper> table2) {
470 Hashtable<Wrapper, Wrapper> emap=new Hashtable<Wrapper, Wrapper>();
472 if (table1.keySet().size()!=table2.keySet().size())
475 for(Iterator<TempDescriptor> tmpit=table1.keySet().iterator();tmpit.hasNext();) {
476 TempDescriptor tmp=tmpit.next();
477 if (table2.containsKey(tmp)) {
478 emap.put(table1.get(tmp), table2.get(tmp));
482 for(Iterator<TempDescriptor> tmpit=table1.keySet().iterator();tmpit.hasNext();) {
483 TempDescriptor tmp=tmpit.next();
484 Wrapper w1=table1.get(tmp);
485 Wrapper w2=table2.get(tmp);
486 if (w1 instanceof TagWrapper) {
487 TagWrapper t1=(TagWrapper)w1;
488 TagWrapper t2=(TagWrapper)w2;
489 if (!t1.ts.equals(t2.ts))
493 ObjWrapper t1=(ObjWrapper)w1;
494 ObjWrapper t2=(ObjWrapper)w2;
495 if (!t1.fs.equals(t2.fs))
497 if (t1.tags.size()!=t2.tags.size())
499 for(Iterator<TagWrapper> twit=t1.tags.iterator();twit.hasNext();) {
500 TagWrapper tw1=twit.next();
501 if (!t2.tags.contains(emap.get(tw1)))
509 private void doAnalysis(TaskBinding tb) {
510 TaskDescriptor td=tb.tqi.tq.getTask();
511 FlatMethod fm=state.getMethodFlat(td);
512 Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> wtable=new Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>>();
513 wtable.put(fm, buildinittable(tb, fm));
514 HashSet<FlatNode> visited=new HashSet<FlatNode>();
515 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
516 tovisit.add(fm.getNext(0));
517 while(!tovisit.isEmpty()) {
518 FlatNode fn=tovisit.iterator().next();
521 Hashtable<TempDescriptor, Wrapper> table=computeInitialState(wtable, fn);
523 case FKind.FlatFlagActionNode:
524 processFlatFlag((FlatFlagActionNode)fn, table, td);
526 case FKind.FlatTagDeclaration:
527 processFlatTag((FlatTagDeclaration)fn, table, td);
530 processFlatCall((FlatCall)fn, table);
532 case FKind.FlatReturnNode:
533 processFlatReturnNode((FlatReturnNode)fn, table, td);
538 if (!equivalent(table, wtable.get(fn))) {
539 wtable.put(fn, table);
540 for(int i=0;i<fn.numNext();i++) {
541 tovisit.add(fn.getNext(i));
544 for(int i=0;i<fn.numNext();i++) {
545 if (!visited.contains(fn.getNext(i)))
546 tovisit.add(fn.getNext(i));
553 private Hashtable<TempDescriptor, Wrapper> buildinittable(TaskBinding tb, FlatMethod fm) {
554 Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
555 Vector<TempDescriptor> tagtmps=tb.tqi.tq.tags;
556 for(int i=0;i<tagtmps.size();i++) {
557 TempDescriptor tmp=tagtmps.get(i);
558 table.put(tmp, tb.getTag(tmp));
560 for(int i=0;i<fm.numParameters();i++) {
561 TempDescriptor tmp=fm.getParameter(i);
562 table.put(tmp, tb.getParameter(i));
569 new flag states created
570 new tag states created
571 flag states bound to tag parameters
574 public boolean canEnqueue(TaskDescriptor td, int paramnum, FlagState fs) {
575 return typeutil.isSuperorType(td.getParamType(paramnum).getClassDesc(),fs.getClassDescriptor())&&
576 isTaskTrigger_flag(td.getFlag(td.getParameter(paramnum)),fs)&&
577 isTaskTrigger_tag(td.getTag(td.getParameter(paramnum)),fs);
580 private static boolean isTaskTrigger_flag(FlagExpressionNode fen, FlagState fs) {
583 else if (fen instanceof FlagNode)
584 return fs.get(((FlagNode)fen).getFlag());
586 switch (((FlagOpNode)fen).getOp().getOp()) {
587 case Operation.LOGIC_AND:
588 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
589 case Operation.LOGIC_OR:
590 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
591 case Operation.LOGIC_NOT:
592 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
599 private static boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
601 for (int i=0;i<tel.numTags() ; i++){
602 switch (fs.getTagCount(tel.getType(i))){
603 case FlagState.ONETAG:
604 case FlagState.MULTITAGS:
606 case FlagState.NOTAGS:
614 TagState createInitialState() {
615 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
616 FlagDescriptor fd=(FlagDescriptor)startupobject.getFlagTable().get(FlagDescriptor.InitialFlag);
617 FlagState fsstartup=(new FlagState(startupobject)).setFlag(fd,true);
618 fsstartup.setAsSourceNode();
619 fsstartup=canonical(fsstartup);
620 TagState ts=new TagState(startupobject);
621 TagState[] tsarray=ts.addFS(fsstartup);
622 return canonical(tsarray[0]);
625 FlagState[] canonical(FlagState[] fs) {
626 FlagState[] fsarray=new FlagState[fs.length];
627 for(int i=0;i<fs.length;i++)
628 fsarray[i]=canonical(fs[i]);
632 FlagState canonical(FlagState fs) {
636 TagState canonical(TagState ts) {