Robust/src/Analysis/TaskStateAnalysis/TaskTagAnalysis.java

   1 package Analysis.TaskStateAnalysis;
   2 import IR.*;
   3 import IR.Tree.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.File;
   7 import java.io.FileWriter;
   8 import java.io.FileOutputStream;
   9
  10 public class TaskTagAnalysis {
  11     State state;
  12     TagAnalysis taganalysis;
  13     TypeUtil typeutil;
  14     FlagInfo flaginfo;
  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;
  20
  21
  22     /**
  23      * Class Constructor
  24      *
  25      */
  26     public TaskTagAnalysis(State state, TagAnalysis taganalysis) {
  27         this.state=state;
  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>>();
  36
  37
  38         for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
  39             TaskDescriptor td=(TaskDescriptor)taskit.next();
  40             tasktable.put(td, new TaskQueue(td));
  41         }
  42         doAnalysis();
  43         doOutput();
  44     }
  45
  46     private void doOutput() {
  47         try {
  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);
  54         }
  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);
  61         }
  62         } catch (Exception e) {
  63             e.printStackTrace();
  64         }
  65     }
  66
  67     private void doAnalysis() {
  68         toprocess.add(createInitialState());
  69         while(!toprocess.isEmpty()) {
  70             TagState ts=toprocess.iterator().next();
  71             toprocess.remove(ts);
  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);
  77             }
  78         }
  79     }
  80
  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");
  93                         processBinding(tqi);
  94                         tqi.next();
  95                     }
  96                 }
  97             }
  98         }
  99     }
 100
 101     private void processBinding(TaskQueueIterator tqi) {
 102         TaskBinding tb=new TaskBinding(tqi);
 103         while(tb.hasNext()) {
 104             doAnalysis(tb);
 105             tb.next();
 106         }
 107     }
 108
 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);
 115
 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)
 121                     continue;
 122                 if (table.containsKey(tmp)) {
 123                     //merge tag states
 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)) {
 130                             currtag.ts.add(tag);
 131                         }
 132                     }
 133                 } else {
 134                     TagWrapper clonetag=((TagWrapper)prevtag).clone();
 135                     tagtable.put((TagWrapper)prevtag, clonetag);
 136                     table.put(tmp, clonetag);
 137                 }
 138             }
 139
 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)
 145                     continue;
 146                 ObjWrapper prevobj=(ObjWrapper)obj;
 147                 if (!table.containsKey(tmp)) {
 148                     //merge tag states
 149                     ObjWrapper newobj=new ObjWrapper();
 150                     newobj.initfs=prevobj.initfs;
 151                     table.put(tmp, newobj);
 152                 }
 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);
 158                     currobj.tags.add(t);
 159                 }
 160                 for(Iterator<FlagState> flagit=prevobj.fs.iterator();flagit.hasNext();) {
 161                     FlagState fs=flagit.next();
 162                     currobj.fs.add(fs);
 163                 }
 164             }
 165         }
 166         return table;
 167     }
 168
 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);
 176         }
 177     }
 178
 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));
 185             newstate.add(fsnew);
 186             flagmap.put(fs, fsnew);
 187         }
 188
 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)) {
 198                             newstates.add(ts);
 199                         } else {
 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
 204                             //explored
 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]));
 210                             }
 211                         }
 212                     }
 213                 }
 214             }
 215             tw.ts=newstates;
 216         }
 217     }
 218
 219     private void setTag(ObjWrapper ow, TagWrapper twnew, TagDescriptor tag, boolean value) {
 220         if (value) {
 221             if (ow.tags.contains(twnew)) {
 222                 System.out.println("Tag already bound to object.");
 223                 return;
 224             }
 225         } else {
 226             if (!ow.tags.contains(twnew)) {
 227                 System.out.println("Tag not bound to object.");
 228                 return;
 229             }
 230         }
 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));
 239         }
 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)) {
 252                                 newstates.add(ts);
 253                             } else {
 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]));
 264                                 }
 265                             }
 266                         }
 267                     }
 268                 }
 269             }
 270             tw.ts=newstates;
 271         }
 272
 273         {
 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
 282                     TagState tsarray2[];
 283                     if (value)
 284                         tsarray2=ts.addnewFS(fsnew);
 285                     else
 286                         tsarray2=ts.clearFS(fsnew);
 287                     for(int j=0;j<tsarray2.length;j++)
 288                         newstates.add(canonical(tsarray2[j]));
 289                 }
 290             }
 291             twnew.ts=newstates;
 292         }
 293
 294         if (value)
 295             ow.tags.add(twnew);
 296         else
 297             ow.tags.remove(twnew);
 298         ow.fs=newfsstates;
 299     }
 300
 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);
 311             if (!newtagstate)
 312                 setTag(ow, tagw, tag, newtagstate);
 313         }
 314
 315         //Do the flags next
 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);
 323         }
 324
 325         //Process sets last
 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);
 334             if (newtagstate)
 335                 setTag(ow, tagw, tag, newtagstate);
 336         }
 337     }
 338
 339     private void evalNewNode(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
 340         TempDescriptor fntemp=null;
 341         {
 342             /* Compute type */
 343             Iterator it=fn.getTempFlagPairs();
 344             if (it.hasNext()) {
 345                 TempFlagPair tfp=(TempFlagPair)it.next();
 346                 fntemp=tfp.getTemp();
 347             } else {
 348                 it=fn.getTempTagPairs();
 349                 if (!it.hasNext())
 350                     throw new Error();
 351                 TempTagPair ttp=(TempTagPair)it.next();
 352                 fntemp=ttp.getTemp();
 353             }
 354         }
 355         FlagState fs=canonical(new FlagState(fntemp.getType().getClassDesc()));
 356         ObjWrapper ow=new ObjWrapper();
 357         ow.fs.add(fs);
 358         table.put(fntemp, ow);
 359         //Do the flags first
 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);
 367         }
 368         //Process sets next
 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));
 377             if (newtagstate)
 378                 setTag(ow, tagw, tag, newtagstate);
 379             else
 380                 throw new Error("Can't clear tag in newly allocated object");
 381         }
 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());
 386             ts2.addFS(fs2);
 387             ts2=canonical(ts2);
 388             ts2.addSource(td);
 389             addresult(fs2.getClassDescriptor(), ts2);
 390             if (!discovered.contains(ts2)) {
 391                 discovered.add(ts2);
 392                 toprocess.add(ts2);
 393             }
 394         }
 395     }
 396
 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);
 401         }
 402         TagDescriptor tag=fn.getType();
 403         TagState ts=canonical(new TagState(tag));
 404         TagWrapper tw=new TagWrapper(ts);
 405         tw.initts=null;
 406         table.put(tmp, tw);
 407     }
 408
 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);
 413     }
 414
 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);
 419     }
 420
 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();
 425             if (init==null) {
 426                 ts.addSource(td);
 427             } else {
 428                 TagEdge te=new TagEdge(ts, td);
 429                 if (!init.containsEdge(te)) {
 430                     init.addEdge(te);
 431                 }
 432             }
 433             if (ts.getTag()!=null)
 434                 addresult(ts.getTag(), ts);
 435             else
 436                 addresult(ts.getClassDesc(), ts);
 437             if (!discovered.contains(ts)) {
 438                 discovered.add(ts);
 439                 toprocess.add(ts);
 440             }
 441         }
 442     }
 443
 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);
 448         }
 449     }
 450
 451     private void processFlatCall(FlatCall fc, Hashtable<TempDescriptor, Wrapper> table) {
 452         //Do nothing for now
 453     }
 454
 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);
 462             } else {
 463                 ObjWrapper ow=(ObjWrapper)w;
 464                 recordobj(ow, td);
 465             }
 466         }
 467     }
 468
 469     private boolean equivalent(Hashtable<TempDescriptor, Wrapper> table1, Hashtable<TempDescriptor, Wrapper> table2) {
 470         Hashtable<Wrapper, Wrapper> emap=new Hashtable<Wrapper, Wrapper>();
 471
 472         if (table1.keySet().size()!=table2.keySet().size())
 473             return false;
 474
 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));
 479             } else return false;
 480         }
 481
 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))
 490                     return false;
 491
 492             } else {
 493                 ObjWrapper t1=(ObjWrapper)w1;
 494                 ObjWrapper t2=(ObjWrapper)w2;
 495                 if (!t1.fs.equals(t2.fs))
 496                     return false;
 497                 if (t1.tags.size()!=t2.tags.size())
 498                     return false;
 499                 for(Iterator<TagWrapper> twit=t1.tags.iterator();twit.hasNext();) {
 500                     TagWrapper tw1=twit.next();
 501                     if (!t2.tags.contains(emap.get(tw1)))
 502                         return false;
 503                 }
 504             }
 505         }
 506         return true;
 507     }
 508
 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();
 519             tovisit.remove(fn);
 520             visited.add(fn);
 521             Hashtable<TempDescriptor, Wrapper> table=computeInitialState(wtable, fn);
 522             switch(fn.kind()) {
 523             case FKind.FlatFlagActionNode:
 524                 processFlatFlag((FlatFlagActionNode)fn, table, td);
 525                 break;
 526             case FKind.FlatTagDeclaration:
 527                 processFlatTag((FlatTagDeclaration)fn, table, td);
 528                 break;
 529             case FKind.FlatCall:
 530                 processFlatCall((FlatCall)fn, table);
 531                 break;
 532             case FKind.FlatReturnNode:
 533                 processFlatReturnNode((FlatReturnNode)fn, table, td);
 534                 break;
 535             default:
 536             }
 537
 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));
 542                 }
 543             } else {
 544                 for(int i=0;i<fn.numNext();i++) {
 545                     if (!visited.contains(fn.getNext(i)))
 546                         tovisit.add(fn.getNext(i));
 547                 }
 548             }
 549         }
 550
 551     }
 552
 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));
 559         }
 560         for(int i=0;i<fm.numParameters();i++) {
 561             TempDescriptor tmp=fm.getParameter(i);
 562             table.put(tmp, tb.getParameter(i));
 563         }
 564         return table;
 565     }
 566
 567     /*
 568       method summary:
 569       new flag states created
 570       new tag states created
 571       flag states bound to tag parameters
 572     */
 573
 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);
 578     }
 579
 580     private static boolean isTaskTrigger_flag(FlagExpressionNode fen, FlagState fs) {
 581         if (fen==null)
 582             return true;
 583         else if (fen instanceof FlagNode)
 584             return fs.get(((FlagNode)fen).getFlag());
 585         else
 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));
 593             default:
 594                 return false;
 595             }
 596     }
 597
 598
 599     private static boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 600         if (tel!=null){
 601             for (int i=0;i<tel.numTags() ; i++){
 602                 switch (fs.getTagCount(tel.getType(i))){
 603                 case FlagState.ONETAG:
 604                 case FlagState.MULTITAGS:
 605                     break;
 606                 case FlagState.NOTAGS:
 607                     return false;
 608                 }
 609             }
 610         }
 611         return true;
 612     }
 613
 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]);
 623     }
 624
 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]);
 629         return fsarray;
 630     }
 631
 632     FlagState canonical(FlagState fs) {
 633         return fs;
 634     }
 635
 636     TagState canonical(TagState ts) {
 637         return ts;
 638     }
 639
 640
 641 }
 642