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