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