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