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
  13
  14
  15 public class TaskAnalysis {
  16     State state;
  17     Hashtable flagstates;
  18     Hashtable flags;
  19     Hashtable extern_flags;
  20     Queue<FlagState> toprocess;
  21     TypeUtil typeutil;
  22
  23     /**
  24      * Class Constructor
  25      *
  26      * @param state a flattened State object
  27      * @see State
  28      */
  29     public TaskAnalysis(State state)
  30     {
  31         this.state=state;
  32         this.typeutil=new TypeUtil(state);
  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
  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         }
 118
 119
 120         ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 121
 122         sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
 123
 124         FlagState fsstartup=new FlagState(startupobject);
 125         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
 126
 127         fsstartup=fsstartup.setFlag(fd[0],true);
 128
 129         sourcenodes.put(fsstartup,fsstartup);
 130         toprocess.add(fsstartup);
 131
 132         /** Looping through the flagstates in the toprocess queue to perform the state analysis */
 133         while (!toprocess.isEmpty()) {
 134             FlagState trigger=toprocess.poll();
 135             createPossibleRuntimeStates(trigger);
 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         /** counter to keep track of the number of parameters (of the task being analyzed) that
 166          *  are satisfied by the flagstate.
 167          */
 168         int trigger_ctr=0;
 169         TempDescriptor temp=null;
 170         FlatMethod fm = state.getMethodFlat(td);
 171
 172         for(int i=0; i < td.numParameters(); i++) {
 173             FlagExpressionNode fen=td.getFlag(td.getParameter(i));
 174             TagExpressionList tel=td.getTag(td.getParameter(i));
 175
 176             /** Checking to see if the parameter is of the same type/class as the
 177              *  flagstate's and also if the flagstate fs triggers the given task*/
 178             if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
 179                 && isTaskTrigger_flag(fen,fs)
 180                 && isTaskTrigger_tag(tel,fs)) {
 181                 temp=fm.getParameter(i);
 182                 trigger_ctr++;
 183             }
 184         }
 185
 186         if (trigger_ctr==0) //Look at next task
 187             continue;
 188
 189         if (trigger_ctr>1)
 190             throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
 191
 192         //Iterating through the nodes
 193         FlatNode fn=fm.methodEntryNode();
 194
 195         HashSet tovisit= new HashSet();
 196         HashSet visited= new HashSet();
 197
 198         tovisit.add(fn);
 199         while(!tovisit.isEmpty()) {
 200             FlatNode fn1 = (FlatNode)tovisit.iterator().next();
 201             tovisit.remove(fn1);
 202             visited.add(fn1);
 203             // Queue all of the next nodes
 204             for(int i = 0; i < fn1.numNext(); i++) {
 205                 FlatNode nn=fn1.getNext(i);
 206                 if (!visited.contains(nn))
 207                     tovisit.add(nn);
 208             }
 209             if (fn1.kind()==FKind.FlatFlagActionNode) {
 210                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 211                 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
 212                     if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
 213                         throw new Error("PRE FlagActions not supported");
 214                 } else if (ffan.getTaskType() == FlatFlagActionNode.NEWOBJECT) {
 215                     FlagState fsnew=evalNewObjNode(ffan);
 216                     //Have we seen this node yet
 217                     if (!sourcenodes.containsKey(fsnew)) {
 218                         sourcenodes.put(fsnew, fsnew);
 219                         toprocess.add(fsnew);
 220                     }
 221                 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 222                     Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
 223
 224                     for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
 225                             FlagState fs_taskexit=(FlagState)en.nextElement();
 226                         if (!sourcenodes.containsKey(fs_taskexit)) {
 227                                         toprocess.add(fs_taskexit);
 228                         }
 229                         //seen this node already
 230                         fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
 231                         FEdge newedge=new FEdge(fs_taskexit,taskname);
 232                         fs.addEdge(newedge);
 233                 }
 234                 }
 235             }
 236         }
 237     }
 238 }
 239
 240 /** Determines whether the given flagstate satisfies a
 241  *  single parameter in the given task.
 242  *  @param fen FlagExpressionNode
 243  *  @see FlagExpressionNode
 244  *  @param fs  FlagState
 245  *  @see FlagState
 246  *  @return <CODE>true</CODE> if fs satisfies the boolean expression
 247     denoted by fen else <CODE>false</CODE>.
 248  */
 249
 250
 251 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
 252     if (fen instanceof FlagNode)
 253         return fs.get(((FlagNode)fen).getFlag());
 254     else
 255         switch (((FlagOpNode)fen).getOp().getOp()) {
 256         case Operation.LOGIC_AND:
 257             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 258         case Operation.LOGIC_OR:
 259             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 260         case Operation.LOGIC_NOT:
 261             return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 262         default:
 263             return false;
 264         }
 265 }
 266
 267 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 268
 269
 270         for (int i=0;i<tel.numTags() ; i++){
 271                 switch (fs.getTagCount(tel.getType(i))){
 272                         case FlagState.ONETAG:
 273                         case FlagState.MULTITAGS:
 274                                 break;
 275                         case FlagState.NOTAGS:
 276                                 return false;
 277                 }
 278
 279         }
 280         return true;
 281 }
 282
 283 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
 284         int ctr=0;
 285         for(int i=0;i<tel.numTags() ; i++){
 286                 if (tel.getType(i).equals(tagtype))
 287                         ctr++;
 288         }
 289         return ctr;
 290 } */
 291
 292 /** Evaluates a NewObject Node and returns the newly created
 293  *  flagstate to add to the process queue.
 294  *      @param nn FlatNode
 295  *  @return FlagState
 296  *  @see FlatNode
 297  *  @see FlagState
 298  */
 299
 300     private FlagState evalNewObjNode(FlatNode nn){
 301             TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
 302
 303                 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
 304                 ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
 305
 306                 FlagState fstemp=new FlagState(cd_new);
 307
 308                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 309                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 310                         if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
 311                         {
 312                                 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 313                         }
 314
 315                         else
 316                                 break;
 317                 }
 318                 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
 319                         TempTagPair ttp=(TempTagPair)it_ttp.next();
 320                         if (! (ttp.getTag()==null)){
 321                                 fstemp=fstemp.setTag(ttp.getTag());
 322                         }
 323                         else
 324                                 break;
 325
 326                 }
 327                 return fstemp;
 328 }
 329
 330         private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
 331                 FlagState fstemp=fs;
 332                 //FlagState[] fstemparray=new FlagState[3];
 333                 Vector<FlagState> inprocess=new Vector<FlagState>();
 334                 Vector<FlagState> processed=new Vector<FlagState>();
 335
 336                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 337                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 338                         if (temp==tfp.getTemp())
 339                             fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 340                 }
 341
 342                 inprocess.add(fstemp);
 343                 processed.add(fstemp);
 344
 345                 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
 346                         TempTagPair ttp=(TempTagPair)it_ttp.next();
 347
 348                         if (temp==ttp.getTemp()){
 349                                 processed=new Vector<FlagState>();
 350                                 for (Enumeration en=inprocess.elements();en.hasMoreElements();){
 351                                         FlagState fsworking=(FlagState)en.nextElement();
 352                                         if (((FlatFlagActionNode)nn).getTagChange(ttp)){
 353                                                 fsworking=fsworking.setTag(ttp.getTag());
 354                                                 processed.add(fsworking);
 355                                         }
 356                                         else
 357                                         {
 358                                                 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
 359                                         }
 360                                 }
 361                                 inprocess=processed;
 362                 }
 363                 }
 364                 return processed;
 365
 366 }
 367
 368
 369     private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
 370         if (sourcenodes.containsKey(fs))
 371             return (FlagState)sourcenodes.get(fs);
 372         else{
 373             sourcenodes.put(fs,fs);
 374             return fs;
 375         }
 376     }
 377
 378    /** Creates a DOT file using the flagstates for a given class
 379     *  @param cd ClassDescriptor of the class
 380     *  @throws java.io.IOException
 381     *  @see ClassDescriptor
 382     */
 383
 384    public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 385         File dotfile= new File("graph"+cd.getSymbol()+".dot");
 386         FileOutputStream dotstream=new FileOutputStream(dotfile,true);
 387         FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 388    }
 389
 390
 391     private String getTaskName(TaskDescriptor td) {
 392         StringTokenizer st = new StringTokenizer(td.toString(),"(");
 393         return st.nextToken();
 394     }
 395
 396         private void createPossibleRuntimeStates(FlagState fs) {
 397     ClassDescriptor cd = fs.getClassDescriptor();
 398     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 399     FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 400     int externs=((Integer)extern_flags.get(cd)).intValue();
 401     if(externs==0)
 402         return;
 403
 404     int noOfIterations=(1<<externs) - 1;
 405     boolean BoolValTable[]=new boolean[externs];
 406
 407
 408     for(int i=0; i < externs ; i++) {
 409         BoolValTable[i]=fs.get(fd[i]);
 410     }
 411
 412         for(int k=0; k<noOfIterations; k++) {
 413         for(int j=0; j < externs ;j++) {
 414             if ((k% (1<<j)) == 0)
 415                 BoolValTable[j]=(!BoolValTable[j]);
 416         }
 417
 418         FlagState fstemp=fs;
 419
 420         for(int i=0; i < externs;i++) {
 421             fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 422         }
 423         if (!sourcenodes.containsKey(fstemp))
 424             toprocess.add(fstemp);
 425
 426         fstemp=canonicalizeFlagState(sourcenodes,fstemp);
 427         fs.addEdge(new FEdge(fstemp,"Runtime"));
 428     }
 429         }
 430 }
 431