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
  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)
  28     {
  29         this.state=state;
  30         this.typeutil=new TypeUtil(state);
  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
 172
 173         /** counter to keep track of the number of parameters (of the task being analyzed) that
 174          *  are satisfied by the flagstate.
 175          */
 176         int trigger_ctr=0;
 177         TempDescriptor temp=null;
 178         FlatMethod fm = state.getMethodFlat(td);
 179
 180         for(int i=0; i < td.numParameters(); i++) {
 181             FlagExpressionNode fen=td.getFlag(td.getParameter(i));
 182             TagExpressionList tel=td.getTag(td.getParameter(i));
 183
 184             /** Checking to see if the parameter is of the same type/class as the
 185              *  flagstate's and also if the flagstate fs triggers the given task*/
 186             if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
 187                 && isTaskTrigger_flag(fen,fs)
 188                 && isTaskTrigger_tag(tel,fs)) {
 189                 temp=fm.getParameter(i);
 190                 trigger_ctr++;
 191             }
 192         }
 193
 194         if (trigger_ctr==0) //Look at next task
 195             continue;
 196
 197         if (trigger_ctr>1)
 198             throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
 199
 200
 201         //** debug
 202         System.out.println("Task:" + taskname +" is triggered");
 203
 204
 205         //Iterating through the nodes
 206         FlatNode fn=fm.methodEntryNode();
 207
 208         HashSet tovisit= new HashSet();
 209         HashSet visited= new HashSet();
 210
 211         tovisit.add(fn);
 212         while(!tovisit.isEmpty()) {
 213             FlatNode fn1 = (FlatNode)tovisit.iterator().next();
 214             tovisit.remove(fn1);
 215             visited.add(fn1);
 216             // Queue all of the next nodes
 217             for(int i = 0; i < fn1.numNext(); i++) {
 218                 FlatNode nn=fn1.getNext(i);
 219                 if (!visited.contains(nn))
 220                     tovisit.add(nn);
 221             }
 222             if (fn1.kind()==FKind.FlatFlagActionNode) {
 223                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 224                 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
 225                     if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
 226                         throw new Error("PRE FlagActions not supported");
 227                 } else if (ffan.getTaskType() == FlatFlagActionNode.NEWOBJECT) {
 228                         //***
 229                         System.out.println("NEWOBJ");
 230                         //***
 231                     FlagState fsnew=evalNewObjNode(ffan);
 232                     //Have we seen this node yet
 233                     if(fsnew!=null){
 234                     if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
 235                         ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
 236                         toprocess.add(fsnew);
 237                     }
 238                 }
 239                 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 240                     //***
 241                     System.out.println("TASKEXIT");
 242                     //***
 243
 244                         Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
 245
 246                     for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
 247                             FlagState fs_taskexit=(FlagState)en.nextElement();
 248                         if (!sourcenodes.containsKey(fs_taskexit)) {
 249                                         toprocess.add(fs_taskexit);
 250
 251                         }
 252                         //seen this node already
 253                         fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
 254                         FEdge newedge=new FEdge(fs_taskexit,taskname);
 255                         //FEdge newedge=new FEdge(fs_taskexit,td);
 256                         fs.addEdge(newedge);
 257                 }
 258                 }
 259             }
 260         }
 261     }
 262 }
 263
 264 /** Determines whether the given flagstate satisfies a
 265  *  single parameter in the given task.
 266  *  @param fen FlagExpressionNode
 267  *  @see FlagExpressionNode
 268  *  @param fs  FlagState
 269  *  @see FlagState
 270  *  @return <CODE>true</CODE> if fs satisfies the boolean expression
 271     denoted by fen else <CODE>false</CODE>.
 272  */
 273
 274
 275 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
 276     if (fen instanceof FlagNode)
 277         return fs.get(((FlagNode)fen).getFlag());
 278     else
 279         switch (((FlagOpNode)fen).getOp().getOp()) {
 280         case Operation.LOGIC_AND:
 281             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 282         case Operation.LOGIC_OR:
 283             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 284         case Operation.LOGIC_NOT:
 285             return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 286         default:
 287             return false;
 288         }
 289 }
 290
 291 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 292
 293         if (tel!=null){
 294         for (int i=0;i<tel.numTags() ; i++){
 295                 switch (fs.getTagCount(tel.getType(i))){
 296                         case FlagState.ONETAG:
 297                         case FlagState.MULTITAGS:
 298                                 break;
 299                         case FlagState.NOTAGS:
 300                                 return false;
 301                 }
 302         }
 303         }
 304         return true;
 305 }
 306
 307 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
 308         int ctr=0;
 309         for(int i=0;i<tel.numTags() ; i++){
 310                 if (tel.getType(i).equals(tagtype))
 311                         ctr++;
 312         }
 313         return ctr;
 314 } */
 315
 316 /** Evaluates a NewObject Node and returns the newly created
 317  *  flagstate to add to the process queue.
 318  *      @param nn FlatNode
 319  *  @return FlagState
 320  *  @see FlatNode
 321  *  @see FlagState
 322  */
 323
 324     private FlagState evalNewObjNode(FlatNode nn){
 325
 326             ClassDescriptor cd_new=((FlatNew)nn.getPrev(0)).getType().getClassDesc();
 327
 328
 329             //TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
 330
 331             //if (tdArray.length==0)
 332             //  return null;
 333
 334                 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
 335                 //ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
 336
 337                 FlagState fstemp=new FlagState(cd_new);
 338
 339                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 340                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 341                         if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
 342                         {
 343                                 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 344                         }
 345
 346                         else
 347                                 break;
 348                 }
 349                 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
 350                         TempTagPair ttp=(TempTagPair)it_ttp.next();
 351                         if (! (ttp.getTag()==null)){
 352                                 fstemp=fstemp.setTag(ttp.getTag());
 353                         }
 354                         else
 355                                 break;
 356
 357                 }
 358                 return fstemp;
 359 }
 360
 361         private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
 362                 FlagState fstemp=fs;
 363                 //FlagState[] fstemparray=new FlagState[3];
 364                 Vector<FlagState> inprocess=new Vector<FlagState>();
 365                 Vector<FlagState> processed=new Vector<FlagState>();
 366
 367                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 368                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 369                         if (temp==tfp.getTemp())
 370                             fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 371                 }
 372
 373                 inprocess.add(fstemp);
 374                 processed.add(fstemp);
 375
 376                 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
 377                         TempTagPair ttp=(TempTagPair)it_ttp.next();
 378
 379                         if (temp==ttp.getTemp()){
 380                                 processed=new Vector<FlagState>();
 381                                 for (Enumeration en=inprocess.elements();en.hasMoreElements();){
 382                                         FlagState fsworking=(FlagState)en.nextElement();
 383                                         if (((FlatFlagActionNode)nn).getTagChange(ttp)){
 384                                                 fsworking=fsworking.setTag(ttp.getTag());
 385                                                 processed.add(fsworking);
 386                                         }
 387                                         else
 388                                         {
 389                                                 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
 390                                         }
 391                                 }
 392                                 inprocess=processed;
 393                 }
 394                 }
 395                 return processed;
 396
 397 }
 398
 399
 400     private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
 401         if (sourcenodes.containsKey(fs))
 402             return (FlagState)sourcenodes.get(fs);
 403         else{
 404             sourcenodes.put(fs,fs);
 405             return fs;
 406         }
 407     }
 408
 409    /** Creates a DOT file using the flagstates for a given class
 410     *  @param cd ClassDescriptor of the class
 411     *  @throws java.io.IOException
 412     *  @see ClassDescriptor
 413     */
 414
 415     public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 416                 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
 417                 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
 418                 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 419
 420                 File dotfile_tasknodes=new File("graph"+cd.getSymbol()+"_task.dot");
 421                 dotstream=new FileOutputStream(dotfile_tasknodes,true);
 422                 TaskNode.DOTVisitor.visit(dotstream,(produceTaskNodes((Hashtable)flagstates.get(cd))).values());
 423     }
 424
 425
 426     private void createPossibleRuntimeStates(FlagState fs) {
 427     ClassDescriptor cd = fs.getClassDescriptor();
 428     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 429     FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 430     int externs=((Integer)extern_flags.get(cd)).intValue();
 431
 432     if(externs==0)
 433         return;
 434
 435     int noOfIterations=(1<<externs) - 1;
 436     boolean BoolValTable[]=new boolean[externs];
 437
 438
 439     for(int i=0; i < externs ; i++) {
 440         BoolValTable[i]=fs.get(fd[i]);
 441     }
 442
 443         for(int k=0; k<noOfIterations; k++) {
 444         for(int j=0; j < externs ;j++) {
 445             if ((k% (1<<j)) == 0)
 446                 BoolValTable[j]=(!BoolValTable[j]);
 447         }
 448
 449         FlagState fstemp=fs;
 450
 451         for(int i=0; i < externs;i++) {
 452             fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 453         }
 454         if (!sourcenodes.containsKey(fstemp))
 455             toprocess.add(fstemp);
 456
 457         fstemp=canonicalizeFlagState(sourcenodes,fstemp);
 458         fs.addEdge(new FEdge(fstemp,"Runtime"));
 459     }
 460         }
 461
 462         private TaskNode canonicalizeTaskNode(Hashtable nodes, TaskNode node){
 463         if (nodes.containsKey(node))
 464             return (TaskNode)nodes.get(node);
 465         else{
 466             nodes.put(node,node);
 467             return (TaskNode)node;
 468         }
 469     }
 470
 471         public Hashtable produceTaskNodes(Hashtable<FlagState,FlagState> fsnodes){
 472
 473                 Hashtable<TaskNode,TaskNode> tasknodes=new Hashtable<TaskNode,TaskNode>();
 474                 for(Enumeration en=fsnodes.keys();en.hasMoreElements();){
 475                         FlagState fs=(FlagState)en.nextElement();
 476
 477                         Iterator it_inedges=fs.inedges();
 478                         TaskNode tn;
 479                         do{
 480                                 if (!fs.inedges().hasNext()){
 481                                         tn=new TaskNode("Start Node");
 482                                 }else{
 483                                         FEdge inedge=(FEdge)it_inedges.next();
 484                                         tn=new TaskNode(inedge.getLabel());
 485                                 }
 486                                 if(fs.edges().hasNext()){
 487                                         tn=(TaskNode)canonicalizeTaskNode(tasknodes, tn);
 488                                         for (Iterator it_edges=fs.edges();it_edges.hasNext();){
 489                                                 TaskNode target=new TaskNode(((FEdge)it_edges.next()).getLabel());
 490                                                 target=(TaskNode)canonicalizeTaskNode(tasknodes,target);
 491                                                 tn.addEdge(new TEdge(target));
 492                                         }
 493                                 }
 494                         }while(it_inedges.hasNext());
 495                 }
 496                 return tasknodes;
 497         }
 498
 499 }
 500