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     Hashtable<TaskDescriptor, TaskQueue> tasktable;
  17
  18
  19     /**
  20      * Class Constructor
  21      *
  22      */
  23     public TaskTagAnalysis(State state, TagAnalysis taganalysis) {
  24         this.state=state;
  25         this.typeutil=new TypeUtil(state);
  26         this.taganalysis=taganalysis;
  27         this.flaginfo=new FlagInfo(state);
  28         this.toprocess=new HashSet<TagState>();
  29         this.tasktable=new Hashtable<TaskDescriptor, TaskQueue>();
  30         for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
  31             TaskDescriptor td=(TaskDescriptor)taskit.next();
  32             tasktable.put(td, new TaskQueue(td));
  33         }
  34     }
  35
  36     private void doAnalysis() {
  37         toprocess.add(createInitialState());
  38         while(!toprocess.isEmpty()) {
  39             TagState ts=toprocess.iterator().next();
  40             toprocess.remove(ts);
  41             //Loop through each task
  42             for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
  43                 TaskDescriptor td=(TaskDescriptor)taskit.next();
  44                 TaskQueue tq=tasktable.get(td);
  45                 processTask(td, tq, ts);
  46             }
  47         }
  48     }
  49
  50     private void processTask(TaskDescriptor td, TaskQueue tq, TagState ts) {
  51         Set<FlagState> flagset=ts.getFS();
  52         for(Iterator<FlagState> fsit=flagset.iterator();fsit.hasNext();) {
  53             FlagState fs=fsit.next();
  54             FlagTagState fts=new FlagTagState(ts, fs);
  55             for(int i=0;i<td.numParameters();i++) {
  56                 if (canEnqueue(td, i, fs)) {
  57                     TaskQueueIterator tqi=tq.enqueue(i, fts);
  58                     while(tqi.hasNext()) {
  59                         processBinding(tqi);
  60                         tqi.next();
  61                     }
  62                 }
  63             }
  64         }
  65     }
  66
  67     private void processBinding(TaskQueueIterator tqi) {
  68         TaskBinding tb=new TaskBinding(tqi);
  69         while(tb.hasNext()) {
  70             doAnalysis(tb);
  71             tb.next();
  72         }
  73     }
  74
  75     private Hashtable<TempDescriptor, Wrapper> computeInitialState(Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> maintable, FlatNode fn) {
  76         Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
  77         Hashtable<TagWrapper,TagWrapper> tagtable=new Hashtable<TagWrapper, TagWrapper>();
  78         for(int i=0;i<fn.numPrev();i++) {
  79             FlatNode fnprev=fn.getPrev(i);
  80             Hashtable<TempDescriptor, Wrapper> prevtable=maintable.get(fn);
  81
  82             //Iterator through the Tags
  83             for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
  84                 TempDescriptor tmp=tmpit.next();
  85                 Wrapper prevtag=prevtable.get(tmp);
  86                 if (prevtag instanceof ObjWrapper)
  87                     continue;
  88                 if (table.containsKey(tmp)) {
  89                     //merge tag states
  90                     TagWrapper currtag=(TagWrapper) table.get(tmp);
  91                     tagtable.put((TagWrapper)prevtag, currtag);
  92                     assert(currtag.initts.equals(((TagWrapper)prevtag).initts));
  93                     for(Iterator<TagState> tagit=((TagWrapper)prevtag).ts.iterator();tagit.hasNext();) {
  94                         TagState tag=tagit.next();
  95                         if (!currtag.ts.contains(tag)) {
  96                             currtag.ts.add(tag);
  97                         }
  98                     }
  99                 } else {
 100                     TagWrapper clonetag=prevtag.clone();
 101                     tagtable.put(prevtag, clonetag);
 102                     table.put(tmp, clonetag);
 103                 }
 104             }
 105
 106             //Iterator through the Objects
 107             for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
 108                 TempDescriptor tmp=tmpit.next();
 109                 Wrapper obj=prevtable.get(tmp);
 110                 if (obj instanceof TagWrapper)
 111                     continue;
 112                 ObjWrapper prevobj=(ObjWrapper)obj;
 113                 if (!table.containsKey(tmp)) {
 114                     //merge tag states
 115                     ObjWrapper newobj=new ObjWrapper();
 116                     newobj.initfs=prevobj.initfs;
 117                     table.put(tmp, newobj);
 118                 }
 119                 ObjWrapper currobj=(ObjWrapper) table.get(tmp);
 120                 assert(currobj.initfs.equals(prevobj.initfs));
 121                 for(Iterator<TagWrapper> tagit=prevobj.tags.iterator();tagit.hasNext();) {
 122                     TagWrapper tprev=tagit.next();
 123                     TagWrapper t=tagtable.get(tprev);
 124                     currobj.tags.add(t);
 125                 }
 126                 for(Iterator<FlagState> flagit=prevobj.fs.iterator();flagit.hasNext();) {
 127                     FlagState fs=flagit.nexT();
 128                     currobj.fs.add(fs);
 129                 }
 130             }
 131         }
 132         return table;
 133     }
 134
 135     private void processFlatFlag(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table) {
 136         if (fn.getTaskType()==FlatFlagActionNode.PRE) {
 137             throw new Error("Unsupported");
 138         } else if (fn.getTaskType()==FlatFlagActionNode.TASKEXIT) {
 139             evalTaskExitNode(fn, table);
 140
 141         } else if (fn.getTaskType()==FlatFlagActionNode.NEW) {
 142         }
 143     }
 144
 145     private void setFlag(ObjWrapper ow, FlagDescriptor fd, boolean value) {
 146         HashSet<FlagState> newstate=new HashSet<FlagState>();
 147         Hastable<FlagState, FlagState> flagmap=new Hashtable<FlagState, FlagState>();
 148         for(Iterator<FlagState> flagit=ow.fs.iterator();flagit.hasNext();) {
 149             FlagState fs=flagit.next();
 150             FlagState fsnew=canonical(fs.setFlag(fd, value));
 151             newstate.add(fsnew);
 152             flagmap.put(fs, fsnew);
 153         }
 154
 155         for(Iterator<TagWrapper> tagit=ow.tags.iterator();tagit.hasNext();) {
 156             TagWrapper tw=tagit.next();
 157             HashSet<TagState> newstates=new HashSet<TagState>();
 158             for(Iterator<TagState> tgit=tw.ts.iterator();tgit.hasNext();) {
 159                 TagState ts=tgit.next();
 160                 for(Iterator<FlagState> flagit=ts.flags.keySet();flagit.hasNext();) {
 161                     FlagState fs=flagit.next();
 162                     if (flagmap.containsKey(fs)) {
 163                         if (flagmap.get(fs).equals(fs)) {
 164                             newstates.add(ts);
 165                         } else {
 166                             TagState tsarray[]=ts.clearFS(fs);
 167                             //Can do strong update here because these
 168                             //must be parameter objects...therefore
 169                             //all possible aliasing relationships are
 170                             //explored
 171                             for(int i=0;i<tsarray.length;i++) {
 172                                 newstates.addAll(Arrays.asList(tsarray[i].addnewFS(flagmap.get(fs))));
 173                             }
 174                         }
 175                     }
 176                 }
 177             }
 178             tw.ts=newstates;
 179         }
 180
 181     }
 182
 183     private void setTag(ObjWrapper ow, TagWrapper tw, boolean value) {
 184
 185
 186     }
 187
 188     private void evalTaskExitNode(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table) {
 189         //Process clears first
 190         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
 191             TempTagPair ttp=(TempTagPair)it_ttp.next();
 192             TempDescriptor tmp=ttp.getTemp();
 193             TempDescriptor tagtmp=ttp.getTagTemp();
 194             TagWrapper tagw=(TagWrapper)table.get(tagtmp)
 195             boolean newtagstate=fn.getTagChange(ttp);
 196             ObjWrapper ow=(ObjWrapper)table.get(tmp);
 197             if (!newtagstate)
 198                 setTag(ow, tagw, newtagstate);
 199         }
 200
 201         //Process sets next
 202         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
 203             TempTagPair ttp=(TempTagPair)it_ttp.next();
 204             TempDescriptor tmp=ttp.getTemp();
 205             TempDescriptor tagtmp=ttp.getTagTemp();
 206             TagWrapper tagw=(TagWrapper)table.get(tagtmp)
 207             boolean newtagstate=fn.getTagChange(ttp);
 208             ObjWrapper ow=(ObjWrapper)table.get(tmp);
 209             if (newtagstate)
 210                 setTag(ow, tagw, newtagstate);
 211         }
 212
 213         //Do the flags last
 214         for(Iterator<TempFlagPair> it_tfp=fn.getTempFlagPairs();it_tfp.hasNext();) {
 215             TempFlagPair tfp=it_tfp.next();
 216             TempDescriptor tmp=tfp.getTemp();
 217             FlagDescriptor fd=tfp.getFlag();
 218             boolean newflagstate=fn.getFlagChange(tfp);
 219             ObjWrapper ow=(ObjWrapper)table.get(tmp);
 220             setFlag(ow, fd, newflagstate);
 221         }
 222     }
 223
 224     private void processFlatTag(FlatTagDeclaration fn, Hashtable<TempDescriptor, Wrapper> table) {
 225         TempDescriptor tmp=fn.getDst();
 226         if (table.containsKey(tmp)) {
 227             recordtagchange(table.get(tmp));
 228         }
 229         TagDescriptor tag=fn.getTag();
 230         TagState ts=canonical(new TagState(tag));
 231         TagWrapper tw=new TagWrapper(ts);
 232         tw.initts=null;
 233         table.put(tmp, tw);
 234     }
 235
 236     private void processFlatCall(FlatCall fc, Hashtable<TempDescriptor, Wrapper> table) {
 237         //Do nothing for now
 238     }
 239
 240     private void processFlatReturnNode(FlatReturnNode fr, Hashtable<TempDescriptor, Wrapper> table) {
 241
 242     }
 243
 244     private boolean equivalent(Hashtable<TempDescriptor, Wrapper> table1, Hashtable<TempDescriptor, Wrapper> table2) {
 245         Hashtable<Wrapper, Wrapper> emap=new Hashtable<Wrapper, Wrapper>;
 246
 247         if (table1.keySet().size()!=table2.keySet().size())
 248             return false;
 249
 250         for(Iterator<TempDescriptor> tmpit=table1.keySet().iterator();tmpit.hasNext();) {
 251             TempDescriptor tmp=tmpit.next();
 252             if (table2.containsKey(tmp)) {
 253                 emap.put(table1.get(tmp), table2.get(tmp));
 254             } else return false;
 255         }
 256
 257         for(Iterator<TempDescriptor> tmpit=table1.keySet().iterator();tmpit.hasNext();) {
 258             TempDescriptor tmp=tmpit.next();
 259             Wrapper w1=table1.get(tmp);
 260             Wrapper w2=table2.get(tmp);
 261             if (w1 instanceof TagWrapper) {
 262                 TagWrapper t1=(TagWrapper)w1;
 263                 TagWrapper t2=(TagWrapper)w2;
 264                 if (!t1.ts.equals(t2.ts))
 265                     return false;
 266
 267             } else {
 268                 ObjWrapper t1=(ObjWrapper)w1;
 269                 ObjWrapper t2=(ObjWrapper)w2;
 270                 if (!t1.fs.equals(t2.fs))
 271                     return false;
 272                 if (t1.tags.size()!=t2.tags.size())
 273                     return false;
 274                 for(Iterator<TagWrapper> twit=t1.tags.iterator();twit.hasNext();) {
 275                     TagWrapper tw1=twit.next();
 276                     if (!t2.tags.contains(emap.get(tw1)))
 277                         return false;
 278                 }
 279             }
 280         }
 281         return true;
 282     }
 283
 284     private void doAnalysis(TaskBinding tb) {
 285         TaskDescriptor td=tb.tqi.tq.getTask();
 286         FlatMethod fm=state.getMethodFlat(td);
 287         Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> wtable=new Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>>();
 288         wtable.put(fm, buildinittable(tb));
 289         HashSet<FlatNode> visited=new HashSet<FlatNode>();
 290         HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 291         tovisit.add(fm.getNext(0));
 292         while(!tovisit.isEmpty()) {
 293             FlatNode fn=tovisit.iterator().next();
 294             tovisit.remove(fn);
 295             visited.add(fn);
 296             Hashtable<TempDescriptor, Wrapper> table=computeInitialState(wtable, fn);
 297             switch(fn.kind()) {
 298             case FKind.FlatFlagActionNode:
 299                 processFlatFlag((FlatFlagActionNode)fn, table);
 300                 break;
 301             case FKind.FlatTagDeclaration:
 302                 processFlatTag((FlatTagDeclaration)fn, table);
 303                 break;
 304             case FKind.FlatCall:
 305                 processFlatCall((FlatCall)fn, table);
 306                 break;
 307             case FKind.FlatReturnNode:
 308                 processFlatReturnNode((FlatReturn)fn, table);
 309                 break;
 310             default:
 311             }
 312
 313             if (!equivalent(table, wtable.get(fn))) {
 314                 wtable.put(fn, table);
 315                 for(int i=0;i<fn.numNext();i++) {
 316                     tovisit.add(fn.getNext(i));
 317                 }
 318             } else {
 319                 for(int i=0;i<fn.numNext();i++) {
 320                     if (!visited.contains(fn.getNext(i)))
 321                         tovisit.add(fn.getNext(i));
 322                 }
 323             }
 324         }
 325
 326     }
 327
 328     private Hashtable<TempDescriptor, Wrapper> buildinittable(TaskBinding tb, FlatMethod fm) {
 329         Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
 330         Vector<TempDescriptor> tagtmps=tb.tqi.tq.tags;
 331         for(int i=0;i<tagtmps.size();i++) {
 332             TempDescriptor tmp=tagtmps.get(i);
 333             table.put(tmp, tb.getTag(tmp));
 334         }
 335         for(int i=0;i<fm.numParameters();i++) {
 336             TempDescriptor tmp=fm.getParameter(i);
 337             table.put(tmp, tb.getParameter(i));
 338         }
 339         return table;
 340     }
 341
 342     /*
 343       method summary:
 344       new flag states created
 345       new tag states created
 346       flag states bound to tag parameters
 347     */
 348
 349     public boolean canEnqueue(TaskDescriptor td, int paramnum, FlagState fs) {
 350         return typeutil.isSuperorType(td.getParamType(paramnum).getClassDesc(),fs.getClassDescriptor())&&
 351             isTaskTrigger_flag(td.getFlag(td.getParameter(paramnum)),fs)&&
 352             isTaskTrigger_tag(td.getTag(td.getParameter(paramnum)),fs);
 353     }
 354
 355     private static boolean isTaskTrigger_flag(FlagExpressionNode fen, FlagState fs) {
 356         if (fen==null)
 357             return true;
 358         else if (fen instanceof FlagNode)
 359             return fs.get(((FlagNode)fen).getFlag());
 360         else
 361             switch (((FlagOpNode)fen).getOp().getOp()) {
 362             case Operation.LOGIC_AND:
 363                 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 364             case Operation.LOGIC_OR:
 365                 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 366             case Operation.LOGIC_NOT:
 367                 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 368             default:
 369                 return false;
 370             }
 371     }
 372
 373
 374     private static boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 375         if (tel!=null){
 376             for (int i=0;i<tel.numTags() ; i++){
 377                 switch (fs.getTagCount(tel.getType(i))){
 378                 case FlagState.ONETAG:
 379                 case FlagState.MULTITAGS:
 380                     break;
 381                 case FlagState.NOTAGS:
 382                     return false;
 383                 }
 384             }
 385         }
 386         return true;
 387     }
 388
 389     TagState createInitialState() {
 390         ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 391         FlagDescriptor fd=(FlagDescriptor)startupobject.getFlagTable().get(FlagDescriptor.InitialFlag);
 392         FlagState fsstartup=(new FlagState(startupobject)).setFlag(fd,true);
 393         fsstartup.setAsSourceNode();
 394         fsstartup=canonical(fsstartup);
 395         TagState ts=new TagState();
 396         TagState[] tsarray=ts.addFS(fsstartup);
 397         return canonical(tsarray[0]);
 398     }
 399
 400     FlagState canonical(FlagState fs) {
 401         return fs;
 402     }
 403
 404     TagState canonical(TagState ts) {
 405         return ts;
 406     }
 407
 408
 409 }
 410