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                 continue;
 228             } else if (fn1.kind()==FKind.FlatFlagActionNode) {
 229                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 230                 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
 231                     if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
 232                         throw new Error("PRE FlagActions not supported");
 233
 234                 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 235                     Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
 236                     Vector<FlagState> initFStates = ffan.getInitFStates(temp.getType().getClassDesc());
 237                     if(!initFStates.contains(fs)) {
 238                         initFStates.addElement(fs);
 239                     }
 240                     Vector<FlagState> targetFStates = ffan.getTargetFStates(fs);
 241                     for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
 242                         FlagState fs_taskexit=(FlagState)en.nextElement();
 243                         if (!sourcenodes.containsKey(fs_taskexit)) {
 244                             toprocess.add(fs_taskexit);
 245                         }
 246                         //seen this node already
 247                         fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
 248                         FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex);
 249                         ((Vector<FEdge>)tdToFEdges.get(td)).add(newedge);
 250                         fs.addEdge(newedge);
 251
 252                         if(!targetFStates.contains(fs_taskexit)) {
 253                             targetFStates.addElement(fs_taskexit);
 254                         }
 255                     }
 256                     continue;
 257                 }
 258             }
 259             /* Queue other nodes past this one */
 260             for(int i=0;i<fn1.numNext();i++) {
 261                 FlatNode fnext=fn1.getNext(i);
 262                 if (!discovered.contains(fnext)) {
 263                     discovered.add(fnext);
 264                     nodestack.push(fnext);
 265                 }
 266             }
 267         }
 268     }
 269 }
 270
 271
 272 /** Determines whether the given flagstate satisfies a
 273  *  single parameter in the given task.
 274  *  @param fen FlagExpressionNode
 275  *  @see FlagExpressionNode
 276  *  @param fs  FlagState
 277  *  @see FlagState
 278  *  @return <CODE>true</CODE> if fs satisfies the boolean expression
 279     denoted by fen else <CODE>false</CODE>.
 280  */
 281
 282
 283 public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
 284     if (fen==null)
 285         return true;
 286     else if (fen instanceof FlagNode)
 287         return fs.get(((FlagNode)fen).getFlag());
 288     else
 289         switch (((FlagOpNode)fen).getOp().getOp()) {
 290         case Operation.LOGIC_AND:
 291             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 292         case Operation.LOGIC_OR:
 293             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 294         case Operation.LOGIC_NOT:
 295             return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 296         default:
 297             return false;
 298         }
 299 }
 300
 301 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 302
 303         if (tel!=null){
 304         for (int i=0;i<tel.numTags() ; i++){
 305                 switch (fs.getTagCount(tel.getType(i))){
 306                         case FlagState.ONETAG:
 307                         case FlagState.MULTITAGS:
 308                                 break;
 309                         case FlagState.NOTAGS:
 310                                 return false;
 311                 }
 312         }
 313         }
 314         return true;
 315 }
 316
 317
 318     private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
 319         FlagState fstemp=fs;
 320         Vector<FlagState> processed=new Vector<FlagState>();
 321
 322         //Process the flag changes
 323
 324         for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
 325             TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 326             if (temp==tfp.getTemp())
 327                 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
 328         }
 329
 330         //Process the tag changes
 331
 332         processed.add(fstemp);
 333
 334         //Process clears first
 335         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
 336             TempTagPair ttp=(TempTagPair)it_ttp.next();
 337
 338             if (temp==ttp.getTemp()) {
 339                 Vector<FlagState> oldprocess=processed;
 340                 processed=new Vector<FlagState>();
 341
 342                 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
 343                     FlagState fsworking=(FlagState)en.nextElement();
 344                     if (!ffan.getTagChange(ttp)){
 345                         processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
 346                     } else processed.add(fsworking);
 347                 }
 348             }
 349         }
 350         //Process sets next
 351         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
 352             TempTagPair ttp=(TempTagPair)it_ttp.next();
 353
 354             if (temp==ttp.getTemp()) {
 355                 Vector<FlagState> oldprocess=processed;
 356                 processed=new Vector<FlagState>();
 357
 358                 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
 359                     FlagState fsworking=(FlagState)en.nextElement();
 360                     if (ffan.getTagChange(ttp)){
 361                         processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
 362                     } else processed.add(fsworking);
 363                 }
 364             }
 365         }
 366         return processed;
 367     }
 368
 369
 370     private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
 371         if (sourcenodes.containsKey(fs))
 372             return (FlagState)sourcenodes.get(fs);
 373         else{
 374             sourcenodes.put(fs,fs);
 375             return fs;
 376         }
 377     }
 378
 379    /** Creates a DOT file using the flagstates for a given class
 380     *  @param cd ClassDescriptor of the class
 381     *  @throws java.io.IOException
 382     *  @see ClassDescriptor
 383     */
 384
 385     public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 386         File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
 387         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
 388         FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 389     }
 390
 391     /** Returns the flag states for the class descriptor. */
 392     public Set<FlagState> getFlagStates(ClassDescriptor cd) {
 393         if (flagstates.containsKey(cd))
 394             return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
 395         else
 396             return new HashSet<FlagState>();
 397     }
 398
 399
 400     private void createPossibleRuntimeStates(FlagState fs) {
 401         ClassDescriptor cd = fs.getClassDescriptor();
 402         Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 403         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 404         int externs=((Integer)extern_flags.get(cd)).intValue();
 405
 406         if(externs==0)
 407             return;
 408
 409         int noOfIterations=(1<<externs) - 1;
 410         boolean BoolValTable[]=new boolean[externs];
 411
 412
 413         for(int i=0; i < externs ; i++) {
 414             BoolValTable[i]=fs.get(fd[i]);
 415         }
 416
 417         for(int k=0; k<noOfIterations; k++) {
 418             for(int j=0; j < externs ;j++) {
 419                 if ((k% (1<<j)) == 0)
 420                     BoolValTable[j]=(!BoolValTable[j]);
 421             }
 422
 423             FlagState fstemp=fs;
 424
 425             for(int i=0; i < externs;i++) {
 426                 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 427             }
 428             if (!sourcenodes.containsKey(fstemp))
 429                 toprocess.add(fstemp);
 430
 431             fstemp=canonicalizeFlagState(sourcenodes,fstemp);
 432             fs.addEdge(new FEdge(fstemp,"Runtime", null, -1));
 433         }
 434     }
 435
 436     public Vector getRootNodes(ClassDescriptor cd){
 437         return (Vector)cdtorootnodes.get(cd);
 438     }
 439
 440     public Vector getFEdgesFromTD(TaskDescriptor td) {
 441         return (Vector)tdToFEdges.get(td);
 442     }
 443 }
 444