Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.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 TaskAnalysis {
  11   State state;
  12   Hashtable flagstates;
  13   Hashtable flags;
  14   Hashtable extern_flags;
  15   Queue<FlagState> toprocess;
  16   TagAnalysis taganalysis;
  17   Hashtable cdtorootnodes;
  18   Hashtable tdToFEdges;
  19
  20   TypeUtil typeutil;
  21
  22   /**
  23    * Class Constructor
  24    *
  25    * @param state a flattened State object
  26    * @see State
  27    */
  28   public TaskAnalysis(State state, TagAnalysis taganalysis) {
  29     this.state=state;
  30     this.typeutil=new TypeUtil(state);
  31     this.taganalysis=taganalysis;
  32   }
  33
  34   /** Builds a table of flags for each class in the Bristlecone
  35    *    program.  It creates two hashtables: one which holds the
  36    *    ClassDescriptors and arrays of * FlagDescriptors as key-value
  37    *    pairs; the other holds the ClassDescriptor and the * number of
  38    *    external flags for that specific class.
  39    */
  40
  41   private void getFlagsfromClasses() {
  42     flags=new Hashtable();
  43     extern_flags = new Hashtable();
  44
  45     /** Iterate through the classes used in the program to build
  46      * the table of flags
  47      */
  48     for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) {
  49
  50       ClassDescriptor cd = (ClassDescriptor)it_classes.next();
  51       Vector vFlags=new Vector();
  52       FlagDescriptor flag[];
  53       int ctr=0;
  54
  55
  56       /* Adding the flags of the super class */
  57       ClassDescriptor tmp=cd;
  58       while(tmp!=null) {
  59         for(Iterator it_cflags=tmp.getFlags(); it_cflags.hasNext();) {
  60           FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
  61           vFlags.add(fd);
  62         }
  63         tmp=tmp.getSuperDesc();
  64       }
  65
  66
  67       if (vFlags.size()!=0) {
  68         flag=new FlagDescriptor[vFlags.size()];
  69
  70         for(int i=0; i < vFlags.size() ; i++) {
  71           if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
  72             flag[ctr]=(FlagDescriptor)vFlags.get(i);
  73             vFlags.remove(flag[ctr]);
  74             ctr++;
  75           }
  76         }
  77         for(int i=0; i < vFlags.size() ; i++) {
  78           flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
  79         }
  80         extern_flags.put(cd,new Integer(ctr));
  81         flags.put(cd,flag);
  82
  83       }
  84     }
  85   }
  86   /** Method which starts up the analysis
  87    */
  88
  89   public void taskAnalysis() throws java.io.IOException {
  90     flagstates=new Hashtable();
  91     Hashtable<FlagState,FlagState> sourcenodes;
  92     cdtorootnodes=new Hashtable();
  93     tdToFEdges=new Hashtable();
  94
  95     getFlagsfromClasses();
  96
  97     int externs;
  98     toprocess=new LinkedList<FlagState>();
  99
 100     for(Iterator it_classes=(Iterator)flags.keys(); it_classes.hasNext();) {
 101       ClassDescriptor cd=(ClassDescriptor)it_classes.next();
 102       externs=((Integer)extern_flags.get(cd)).intValue();
 103       FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 104       flagstates.put(cd,new Hashtable<FlagState,FlagState>());
 105       cdtorootnodes.put(cd,new Vector());
 106     }
 107
 108
 109     ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 110
 111     sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
 112     FlagState fsstartup=new FlagState(startupobject);
 113
 114
 115     FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
 116
 117     fsstartup=fsstartup.setFlag(fd[0],true);
 118     fsstartup.setAsSourceNode();
 119     ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
 120
 121     sourcenodes.put(fsstartup,fsstartup);
 122     toprocess.add(fsstartup);
 123
 124     /** Looping through the flagstates in the toprocess queue to
 125      * perform the state analysis */
 126     while (!toprocess.isEmpty()) {
 127       FlagState trigger=toprocess.poll();
 128       createPossibleRuntimeStates(trigger);
 129
 130       analyseTasks(trigger);
 131     }
 132
 133     /** Creating DOT files */
 134     Enumeration e=flagstates.keys();
 135
 136     while (e.hasMoreElements()) {
 137       ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
 138       createDOTfile(cdtemp);
 139     }
 140   }
 141
 142
 143   /** Analyses the set of tasks based on the given flagstate, checking
 144    *  to see which tasks are triggered and what new flagstates are created
 145    *  from the base flagstate.
 146    *  @param fs A FlagState object which is used to analyse the task
 147    *  @see FlagState
 148    */
 149
 150   private void analyseTasks(FlagState fs) {
 151     ClassDescriptor cd=fs.getClassDescriptor();
 152     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 153
 154     for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator(); it_tasks.hasNext();) {
 155       TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 156       String taskname=td.getSymbol();
 157
 158       if(!tdToFEdges.containsKey(td)) {
 159         tdToFEdges.put(td, new Vector<FEdge>());
 160       }
 161
 162       /** counter to keep track of the number of parameters (of the
 163        *  task being analyzed) that are satisfied by the flagstate.
 164        */
 165       int trigger_ctr=0;
 166       TempDescriptor temp=null;
 167       FlatMethod fm = state.getMethodFlat(td);
 168       int parameterindex=0;
 169
 170       for(int i=0; i < td.numParameters(); i++) {
 171         FlagExpressionNode fen=td.getFlag(td.getParameter(i));
 172         TagExpressionList tel=td.getTag(td.getParameter(i));
 173
 174         /** Checking to see if the parameter is of the same
 175          *  type/class as the flagstate's and also if the
 176          *  flagstate fs triggers the given task*/
 177
 178         if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
 179             && isTaskTrigger_flag(fen,fs)
 180             && isTaskTrigger_tag(tel,fs)) {
 181           temp=fm.getParameter(i);
 182           parameterindex=i;
 183           trigger_ctr++;
 184         }
 185       }
 186
 187       if (trigger_ctr==0)   //Look at next task
 188         continue;
 189
 190       if (trigger_ctr>1)
 191         System.out.println("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task:"+fs + " in "+td);
 192
 193
 194       Set newstates=taganalysis.getFlagStates(td);
 195       for(Iterator fsit=newstates.iterator(); fsit.hasNext();) {
 196         FlagState fsnew=(FlagState) fsit.next();
 197         System.out.println("SOURCE:"+fsnew);
 198
 199         if (!((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
 200           ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
 201           toprocess.add(fsnew);
 202         } else {
 203           fsnew=((Hashtable<FlagState, FlagState>)flagstates.get(fsnew.getClassDescriptor())).get(fsnew);
 204         }
 205         fsnew.setAsSourceNode();
 206         fsnew.addAllocatingTask(td);
 207
 208         if(!((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).contains(fsnew)) {
 209           ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
 210         }
 211       }
 212
 213       Stack nodestack=new Stack();
 214       HashSet discovered=new HashSet();
 215       nodestack.push(fm);
 216       discovered.add(fm);
 217       //Iterating through the nodes
 218
 219       while(!nodestack.isEmpty()) {
 220         FlatNode fn1 = (FlatNode) nodestack.pop();
 221
 222         if (fn1.kind()==FKind.FlatReturnNode) {
 223           /* Self edge */
 224           FEdge newedge=new FEdge(fs, taskname, td, parameterindex);
 225           ((Vector<FEdge>)tdToFEdges.get(td)).add(newedge);
 226           fs.addEdge(newedge);
 227           continue;
 228         } else if (fn1.kind()==FKind.FlatFlagActionNode) {
 229           FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 230           if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
 231             if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
 232               throw new Error("PRE FlagActions not supported");
 233
 234           } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 235             Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
 236             Vector<FlagState> initFStates = ffan.getInitFStates(temp.getType().getClassDesc());
 237             if(!initFStates.contains(fs)) {
 238               initFStates.addElement(fs);
 239             }
 240             Vector<FlagState> targetFStates = ffan.getTargetFStates(fs);
 241             for(Enumeration en=fsv_taskexit.elements(); en.hasMoreElements();){
 242               FlagState fs_taskexit=(FlagState)en.nextElement();
 243               if (!sourcenodes.containsKey(fs_taskexit)) {
 244                 toprocess.add(fs_taskexit);
 245               }
 246               //seen this node already
 247               fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
 248               FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex);
 249               ((Vector<FEdge>)tdToFEdges.get(td)).add(newedge);
 250               fs.addEdge(newedge);
 251
 252               if(!targetFStates.contains(fs_taskexit)) {
 253                 targetFStates.addElement(fs_taskexit);
 254               }
 255             }
 256             continue;
 257           }
 258         }
 259         /* Queue other nodes past this one */
 260         for(int i=0; i<fn1.numNext(); i++) {
 261           FlatNode fnext=fn1.getNext(i);
 262           if (!discovered.contains(fnext)) {
 263             discovered.add(fnext);
 264             nodestack.push(fnext);
 265           }
 266         }
 267       }
 268     }
 269   }
 270
 271
 272 /** Determines whether the given flagstate satisfies a
 273  *  single parameter in the given task.
 274  *  @param fen FlagExpressionNode
 275  *  @see FlagExpressionNode
 276  *  @param fs  FlagState
 277  *  @see FlagState
 278  *  @return <CODE>true</CODE> if fs satisfies the boolean expression
 279     denoted by fen else <CODE>false</CODE>.
 280  */
 281
 282
 283   public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
 284     if (fen==null)
 285       return true;
 286     else if (fen instanceof FlagNode)
 287       return fs.get(((FlagNode)fen).getFlag());
 288     else
 289       switch (((FlagOpNode)fen).getOp().getOp()) {
 290       case Operation.LOGIC_AND:
 291         return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 292
 293       case Operation.LOGIC_OR:
 294         return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 295
 296       case Operation.LOGIC_NOT:
 297         return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 298
 299       default:
 300         return false;
 301       }
 302   }
 303
 304   private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs) {
 305
 306     if (tel!=null){
 307       for (int i=0; i<tel.numTags() ; i++){
 308         switch (fs.getTagCount(tel.getType(i))){
 309         case FlagState.ONETAG:
 310         case FlagState.MULTITAGS:
 311           break;
 312
 313         case FlagState.NOTAGS:
 314           return false;
 315         }
 316       }
 317     }
 318     return true;
 319   }
 320
 321
 322   private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp) {
 323     FlagState fstemp=fs;
 324     Vector<FlagState> processed=new Vector<FlagState>();
 325
 326     //Process the flag changes
 327
 328     for(Iterator it_tfp=ffan.getTempFlagPairs(); it_tfp.hasNext();) {
 329       TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 330       if (temp==tfp.getTemp())
 331         fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
 332     }
 333
 334     //Process the tag changes
 335
 336     processed.add(fstemp);
 337
 338     //Process clears first
 339     for(Iterator it_ttp=ffan.getTempTagPairs(); it_ttp.hasNext();) {
 340       TempTagPair ttp=(TempTagPair)it_ttp.next();
 341
 342       if (temp==ttp.getTemp()) {
 343         Vector<FlagState> oldprocess=processed;
 344         processed=new Vector<FlagState>();
 345
 346         for (Enumeration en=oldprocess.elements(); en.hasMoreElements();){
 347           FlagState fsworking=(FlagState)en.nextElement();
 348           if (!ffan.getTagChange(ttp)){
 349             processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
 350           } else processed.add(fsworking);
 351         }
 352       }
 353     }
 354     //Process sets next
 355     for(Iterator it_ttp=ffan.getTempTagPairs(); it_ttp.hasNext();) {
 356       TempTagPair ttp=(TempTagPair)it_ttp.next();
 357
 358       if (temp==ttp.getTemp()) {
 359         Vector<FlagState> oldprocess=processed;
 360         processed=new Vector<FlagState>();
 361
 362         for (Enumeration en=oldprocess.elements(); en.hasMoreElements();){
 363           FlagState fsworking=(FlagState)en.nextElement();
 364           if (ffan.getTagChange(ttp)){
 365             processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
 366           } else processed.add(fsworking);
 367         }
 368       }
 369     }
 370     return processed;
 371   }
 372
 373
 374   private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs) {
 375     if (sourcenodes.containsKey(fs))
 376       return (FlagState)sourcenodes.get(fs);
 377     else{
 378       sourcenodes.put(fs,fs);
 379       return fs;
 380     }
 381   }
 382
 383   /** Creates a DOT file using the flagstates for a given class
 384    *  @param cd ClassDescriptor of the class
 385    *  @throws java.io.IOException
 386    *  @see ClassDescriptor
 387    */
 388
 389   public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 390     File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
 391     FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
 392     FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 393   }
 394
 395   /** Returns the flag states for the class descriptor. */
 396   public Set<FlagState> getFlagStates(ClassDescriptor cd) {
 397     if (flagstates.containsKey(cd))
 398       return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
 399     else
 400       return new HashSet<FlagState>();
 401   }
 402
 403
 404   private void createPossibleRuntimeStates(FlagState fs) {
 405     ClassDescriptor cd = fs.getClassDescriptor();
 406     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 407     FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 408     int externs=((Integer)extern_flags.get(cd)).intValue();
 409
 410     if(externs==0)
 411       return;
 412
 413     int noOfIterations=(1<<externs) - 1;
 414     boolean BoolValTable[]=new boolean[externs];
 415
 416
 417     for(int i=0; i < externs ; i++) {
 418       BoolValTable[i]=fs.get(fd[i]);
 419     }
 420
 421     for(int k=0; k<noOfIterations; k++) {
 422       for(int j=0; j < externs ; j++) {
 423         if ((k% (1<<j)) == 0)
 424           BoolValTable[j]=(!BoolValTable[j]);
 425       }
 426
 427       FlagState fstemp=fs;
 428
 429       for(int i=0; i < externs; i++) {
 430         fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 431       }
 432       if (!sourcenodes.containsKey(fstemp))
 433         toprocess.add(fstemp);
 434
 435       fstemp=canonicalizeFlagState(sourcenodes,fstemp);
 436       fs.addEdge(new FEdge(fstemp,"Runtime", null, -1));
 437     }
 438   }
 439
 440   public Vector getRootNodes(ClassDescriptor cd) {
 441     return (Vector)cdtorootnodes.get(cd);
 442   }
 443
 444   public Vector getFEdgesFromTD(TaskDescriptor td) {
 445     return (Vector)tdToFEdges.get(td);
 446   }
 447 }
 448