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 public class TaskAnalysis {
  12     State state;
  13     Hashtable flagstates;
  14     Hashtable flags;
  15     Hashtable extern_flags;
  16     Queue<FlagState> toprocess;
  17     TagAnalysis taganalysis;
  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     /** 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
 123         FlagState fsstartup=new FlagState(startupobject);
 124         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
 125
 126         fsstartup=fsstartup.setFlag(fd[0],true);
 127
 128         sourcenodes.put(fsstartup,fsstartup);
 129         toprocess.add(fsstartup);
 130
 131         /** Looping through the flagstates in the toprocess queue to perform the state analysis */
 132         while (!toprocess.isEmpty()) {
 133             FlagState trigger=toprocess.poll();
 134             createPossibleRuntimeStates(trigger);
 135
 136             analyseTasks(trigger);
 137         }
 138
 139         /** Creating DOT files */
 140         Enumeration e=flagstates.keys();
 141
 142         while (e.hasMoreElements()) {
 143             System.out.println("creating dot file");
 144             ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
 145             System.out.println((cdtemp.getSymbol()));
 146             createDOTfile(cdtemp);
 147         }
 148     }
 149
 150
 151     /** Analyses the set of tasks based on the given flagstate, checking
 152      *  to see which tasks are triggered and what new flagstates are created
 153      *  from the base flagstate.
 154      *  @param fs A FlagState object which is used to analyse the task
 155      *  @see FlagState
 156      */
 157
 158 private void analyseTasks(FlagState fs) {
 159     ClassDescriptor cd=fs.getClassDescriptor();
 160     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 161
 162     for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
 163         TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 164         String taskname=td.getSymbol();
 165
 166         //**Debug***/
 167         System.out.println();
 168         System.out.println(cd.getSymbol()+" : "+fs.getTextLabel());
 169         System.out.println("Task: "+taskname);
 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         Set newstates=taganalysis.getFlagStates(td);
 205         for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
 206             FlagState fsnew=(FlagState) fsit.next();
 207             if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
 208                 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
 209                 toprocess.add(fsnew);
 210             }
 211         }
 212
 213         //Iterating through the nodes
 214         Set nodeset=fm.getNodeSet();
 215
 216         for(Iterator nodeit=nodeset.iterator();nodeit.hasNext();) {
 217             FlatNode fn1 = (FlatNode) nodeit.next();
 218
 219             if (fn1.kind()==FKind.FlatFlagActionNode) {
 220                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 221                 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
 222                     if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
 223                         throw new Error("PRE FlagActions not supported");
 224
 225                 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 226                     //***
 227                     System.out.println("TASKEXIT");
 228                     //***
 229
 230                     Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
 231
 232                     for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
 233                         FlagState fs_taskexit=(FlagState)en.nextElement();
 234                         if (!sourcenodes.containsKey(fs_taskexit)) {
 235                             toprocess.add(fs_taskexit);
 236
 237                         }
 238                         //seen this node already
 239                         fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
 240                         FEdge newedge=new FEdge(fs_taskexit,taskname);
 241                         //FEdge newedge=new FEdge(fs_taskexit,td);
 242                         fs.addEdge(newedge);
 243                     }
 244                 }
 245             }
 246         }
 247     }
 248 }
 249
 250
 251 /** Determines whether the given flagstate satisfies a
 252  *  single parameter in the given task.
 253  *  @param fen FlagExpressionNode
 254  *  @see FlagExpressionNode
 255  *  @param fs  FlagState
 256  *  @see FlagState
 257  *  @return <CODE>true</CODE> if fs satisfies the boolean expression
 258     denoted by fen else <CODE>false</CODE>.
 259  */
 260
 261
 262 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
 263     if (fen instanceof FlagNode)
 264         return fs.get(((FlagNode)fen).getFlag());
 265     else
 266         switch (((FlagOpNode)fen).getOp().getOp()) {
 267         case Operation.LOGIC_AND:
 268             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 269         case Operation.LOGIC_OR:
 270             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 271         case Operation.LOGIC_NOT:
 272             return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 273         default:
 274             return false;
 275         }
 276 }
 277
 278 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 279
 280         if (tel!=null){
 281         for (int i=0;i<tel.numTags() ; i++){
 282                 switch (fs.getTagCount(tel.getType(i))){
 283                         case FlagState.ONETAG:
 284                         case FlagState.MULTITAGS:
 285                                 break;
 286                         case FlagState.NOTAGS:
 287                                 return false;
 288                 }
 289         }
 290         }
 291         return true;
 292 }
 293
 294 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
 295         int ctr=0;
 296         for(int i=0;i<tel.numTags() ; i++){
 297                 if (tel.getType(i).equals(tagtype))
 298                         ctr++;
 299         }
 300         return ctr;
 301 } */
 302
 303 /** Evaluates a NewObject Node and returns the newly created
 304  *  flagstate to add to the process queue.
 305  *      @param nn FlatNode
 306  *  @return FlagState
 307  *  @see FlatNode
 308  *  @see FlagState
 309  */
 310
 311 private FlagState evalNewObjNode(FlatNode nn){
 312
 313     ClassDescriptor cd_new=((FlatNew)nn.getPrev(0)).getType().getClassDesc();
 314
 315
 316     //TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
 317
 318     //if (tdArray.length==0)
 319     //  return null;
 320
 321     //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
 322     //ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
 323
 324     FlagState fstemp=new FlagState(cd_new);
 325
 326     for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 327         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 328         if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
 329             {
 330                 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 331             }
 332
 333         else
 334             break;
 335     }
 336     for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
 337         TempTagPair ttp=(TempTagPair)it_ttp.next();
 338         if (! (ttp.getTag()==null)){
 339             fstemp=fstemp.setTag(ttp.getTag());
 340         }
 341         else
 342             break;
 343
 344     }
 345     return fstemp;
 346 }
 347
 348         private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
 349                 FlagState fstemp=fs;
 350                 //FlagState[] fstemparray=new FlagState[3];
 351                 Vector<FlagState> inprocess=new Vector<FlagState>();
 352                 Vector<FlagState> processed=new Vector<FlagState>();
 353
 354                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 355                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 356                         if (temp==tfp.getTemp())
 357                             fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 358                 }
 359
 360                 inprocess.add(fstemp);
 361                 processed.add(fstemp);
 362
 363                 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
 364                         TempTagPair ttp=(TempTagPair)it_ttp.next();
 365
 366                         if (temp==ttp.getTemp()){
 367                                 processed=new Vector<FlagState>();
 368                                 for (Enumeration en=inprocess.elements();en.hasMoreElements();){
 369                                         FlagState fsworking=(FlagState)en.nextElement();
 370                                         if (((FlatFlagActionNode)nn).getTagChange(ttp)){
 371                                                 fsworking=fsworking.setTag(ttp.getTag());
 372                                                 processed.add(fsworking);
 373                                         }
 374                                         else
 375                                         {
 376                                                 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
 377                                         }
 378                                 }
 379                                 inprocess=processed;
 380                 }
 381                 }
 382                 return processed;
 383
 384 }
 385
 386
 387     private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
 388         if (sourcenodes.containsKey(fs))
 389             return (FlagState)sourcenodes.get(fs);
 390         else{
 391             sourcenodes.put(fs,fs);
 392             return fs;
 393         }
 394     }
 395
 396    /** Creates a DOT file using the flagstates for a given class
 397     *  @param cd ClassDescriptor of the class
 398     *  @throws java.io.IOException
 399     *  @see ClassDescriptor
 400     */
 401
 402     public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 403                 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
 404                 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
 405                 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 406
 407                 File dotfile_tasknodes=new File("graph"+cd.getSymbol()+"_task.dot");
 408                 dotstream=new FileOutputStream(dotfile_tasknodes,true);
 409                 TaskNode.DOTVisitor.visit(dotstream,(produceTaskNodes((Hashtable)flagstates.get(cd))).values());
 410     }
 411
 412
 413     private void createPossibleRuntimeStates(FlagState fs) {
 414     ClassDescriptor cd = fs.getClassDescriptor();
 415     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 416     FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 417     int externs=((Integer)extern_flags.get(cd)).intValue();
 418
 419     if(externs==0)
 420         return;
 421
 422     int noOfIterations=(1<<externs) - 1;
 423     boolean BoolValTable[]=new boolean[externs];
 424
 425
 426     for(int i=0; i < externs ; i++) {
 427         BoolValTable[i]=fs.get(fd[i]);
 428     }
 429
 430         for(int k=0; k<noOfIterations; k++) {
 431         for(int j=0; j < externs ;j++) {
 432             if ((k% (1<<j)) == 0)
 433                 BoolValTable[j]=(!BoolValTable[j]);
 434         }
 435
 436         FlagState fstemp=fs;
 437
 438         for(int i=0; i < externs;i++) {
 439             fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 440         }
 441         if (!sourcenodes.containsKey(fstemp))
 442             toprocess.add(fstemp);
 443
 444         fstemp=canonicalizeFlagState(sourcenodes,fstemp);
 445         fs.addEdge(new FEdge(fstemp,"Runtime"));
 446     }
 447         }
 448
 449         private TaskNode canonicalizeTaskNode(Hashtable nodes, TaskNode node){
 450         if (nodes.containsKey(node))
 451             return (TaskNode)nodes.get(node);
 452         else{
 453             nodes.put(node,node);
 454             return (TaskNode)node;
 455         }
 456     }
 457
 458         public Hashtable produceTaskNodes(Hashtable<FlagState,FlagState> fsnodes){
 459
 460                 Hashtable<TaskNode,TaskNode> tasknodes=new Hashtable<TaskNode,TaskNode>();
 461                 for(Enumeration en=fsnodes.keys();en.hasMoreElements();){
 462                         FlagState fs=(FlagState)en.nextElement();
 463
 464                         Iterator it_inedges=fs.inedges();
 465                         TaskNode tn;
 466                         do{
 467                                 if (!fs.inedges().hasNext()){
 468                                         tn=new TaskNode("Start Node");
 469                                 }else{
 470                                         FEdge inedge=(FEdge)it_inedges.next();
 471                                         tn=new TaskNode(inedge.getLabel());
 472                                 }
 473                                 if(fs.edges().hasNext()){
 474                                         tn=(TaskNode)canonicalizeTaskNode(tasknodes, tn);
 475                                         for (Iterator it_edges=fs.edges();it_edges.hasNext();){
 476                                                 TaskNode target=new TaskNode(((FEdge)it_edges.next()).getLabel());
 477                                                 target=(TaskNode)canonicalizeTaskNode(tasknodes,target);
 478                                                 tn.addEdge(new TEdge(target));
 479                                         }
 480                                 }
 481                         }while(it_inedges.hasNext());
 482                 }
 483                 return tasknodes;
 484         }
 485
 486 }
 487