Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java

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