Programming Languages Research Group: Git - IRC.git/blob

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