Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java

   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
  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         this.state=state;
  29         this.typeutil=new TypeUtil(state);
  30         this.taganalysis=taganalysis;
  31     }
  32
  33     /** Builds a table of flags for each class in the Bristlecone
  34      *  program.  It creates two hashtables: one which holds the
  35      *  ClassDescriptors and arrays of * FlagDescriptors as key-value
  36      *  pairs; the other holds the ClassDescriptor and the * number of
  37      *  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
  45          * 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             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                     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     public void taskAnalysis() throws java.io.IOException {
  93         flagstates=new Hashtable();
  94         Hashtable<FlagState,FlagState> sourcenodes;
  95         cdtorootnodes=new Hashtable();
  96
  97         getFlagsfromClasses();
  98
  99         int externs;
 100         toprocess=new LinkedList<FlagState>();
 101
 102         for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
 103             ClassDescriptor cd=(ClassDescriptor)it_classes.next();
 104             externs=((Integer)extern_flags.get(cd)).intValue();
 105             FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 106             flagstates.put(cd,new Hashtable<FlagState,FlagState>());
 107             cdtorootnodes.put(cd,new Vector());
 108         }
 109
 110
 111         ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 112
 113         sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
 114         FlagState fsstartup=new FlagState(startupobject);
 115
 116
 117         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
 118
 119         fsstartup=fsstartup.setFlag(fd[0],true);
 120         fsstartup.setAsSourceNode();
 121         ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
 122
 123         sourcenodes.put(fsstartup,fsstartup);
 124         toprocess.add(fsstartup);
 125
 126         /** Looping through the flagstates in the toprocess queue to
 127          * perform the state analysis */
 128         while (!toprocess.isEmpty()) {
 129             FlagState trigger=toprocess.poll();
 130             createPossibleRuntimeStates(trigger);
 131
 132             analyseTasks(trigger);
 133         }
 134
 135         /** Creating DOT files */
 136         Enumeration e=flagstates.keys();
 137
 138         while (e.hasMoreElements()) {
 139             ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
 140             createDOTfile(cdtemp);
 141         }
 142     }
 143
 144
 145     /** Analyses the set of tasks based on the given flagstate, checking
 146      *  to see which tasks are triggered and what new flagstates are created
 147      *  from the base flagstate.
 148      *  @param fs A FlagState object which is used to analyse the task
 149      *  @see FlagState
 150      */
 151
 152 private void analyseTasks(FlagState fs) {
 153     ClassDescriptor cd=fs.getClassDescriptor();
 154     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 155
 156     for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
 157         TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 158         String taskname=td.getSymbol();
 159
 160         /** counter to keep track of the number of parameters (of the
 161          *  task being analyzed) that are satisfied by the flagstate.
 162          */
 163         int trigger_ctr=0;
 164         TempDescriptor temp=null;
 165         FlatMethod fm = state.getMethodFlat(td);
 166
 167         for(int i=0; i < td.numParameters(); i++) {
 168             FlagExpressionNode fen=td.getFlag(td.getParameter(i));
 169             TagExpressionList tel=td.getTag(td.getParameter(i));
 170
 171             /** Checking to see if the parameter is of the same
 172              *  type/class as the flagstate's and also if the
 173              *  flagstate fs triggers the given task*/
 174
 175             if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
 176                 && isTaskTrigger_flag(fen,fs)
 177                 && isTaskTrigger_tag(tel,fs)) {
 178                 temp=fm.getParameter(i);
 179                 trigger_ctr++;
 180             }
 181         }
 182
 183         if (trigger_ctr==0) //Look at next task
 184             continue;
 185
 186         if (trigger_ctr>1)
 187             throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
 188
 189
 190         Set newstates=taganalysis.getFlagStates(td);
 191         for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
 192             FlagState fsnew=(FlagState) fsit.next();
 193             fsnew.setAsSourceNode();
 194             fsnew.addAllocatingTask(td);
 195             ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
 196
 197             if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
 198                 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
 199                 toprocess.add(fsnew);
 200             }
 201         }
 202
 203         Stack nodestack=new Stack();
 204         HashSet discovered=new HashSet();
 205         nodestack.push(fm);
 206         discovered.add(fm);
 207         //Iterating through the nodes
 208
 209         while(!nodestack.isEmpty()) {
 210             FlatNode fn1 = (FlatNode) nodestack.pop();
 211
 212             if (fn1.kind()==FKind.FlatReturnNode) {
 213                 /* Self edge */
 214                 FEdge newedge=new FEdge(fs, taskname, td);
 215                 fs.addEdge(newedge);
 216                 continue;
 217             } else if (fn1.kind()==FKind.FlatFlagActionNode) {
 218                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 219                 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
 220                     if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
 221                         throw new Error("PRE FlagActions not supported");
 222
 223                 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 224                     Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
 225                     for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
 226                         FlagState fs_taskexit=(FlagState)en.nextElement();
 227                         if (!sourcenodes.containsKey(fs_taskexit)) {
 228                             toprocess.add(fs_taskexit);
 229                         }
 230                         //seen this node already
 231                         fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
 232                         FEdge newedge=new FEdge(fs_taskexit,taskname, td);
 233                         fs.addEdge(newedge);
 234                     }
 235                     continue;
 236                 }
 237             }
 238             /* Queue other nodes past this one */
 239             for(int i=0;i<fn1.numNext();i++) {
 240                 FlatNode fnext=fn1.getNext(i);
 241                 if (!discovered.contains(fnext)) {
 242                     discovered.add(fnext);
 243                     nodestack.push(fnext);
 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==null)
 264         return true;
 265     else if (fen instanceof FlagNode)
 266         return fs.get(((FlagNode)fen).getFlag());
 267     else
 268         switch (((FlagOpNode)fen).getOp().getOp()) {
 269         case Operation.LOGIC_AND:
 270             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 271         case Operation.LOGIC_OR:
 272             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 273         case Operation.LOGIC_NOT:
 274             return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 275         default:
 276             return false;
 277         }
 278 }
 279
 280 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 281
 282         if (tel!=null){
 283         for (int i=0;i<tel.numTags() ; i++){
 284                 switch (fs.getTagCount(tel.getType(i))){
 285                         case FlagState.ONETAG:
 286                         case FlagState.MULTITAGS:
 287                                 break;
 288                         case FlagState.NOTAGS:
 289                                 return false;
 290                 }
 291         }
 292         }
 293         return true;
 294 }
 295
 296 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
 297         int ctr=0;
 298         for(int i=0;i<tel.numTags() ; i++){
 299                 if (tel.getType(i).equals(tagtype))
 300                         ctr++;
 301         }
 302         return ctr;
 303 } */
 304
 305     private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
 306         FlagState fstemp=fs;
 307         Vector<FlagState> processed=new Vector<FlagState>();
 308
 309         //Process the flag changes
 310
 311         for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
 312             TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 313             if (temp==tfp.getTemp())
 314                 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
 315         }
 316
 317         //Process the tag changes
 318
 319         processed.add(fstemp);
 320
 321         //Process clears first
 322         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
 323             TempTagPair ttp=(TempTagPair)it_ttp.next();
 324
 325             if (temp==ttp.getTemp()) {
 326                 Vector<FlagState> oldprocess=processed;
 327                 processed=new Vector<FlagState>();
 328
 329                 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
 330                     FlagState fsworking=(FlagState)en.nextElement();
 331                     if (!ffan.getTagChange(ttp)){
 332                         processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
 333                     } else processed.add(fsworking);
 334                 }
 335             }
 336         }
 337         //Process sets next
 338         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
 339             TempTagPair ttp=(TempTagPair)it_ttp.next();
 340
 341             if (temp==ttp.getTemp()) {
 342                 Vector<FlagState> oldprocess=processed;
 343                 processed=new Vector<FlagState>();
 344
 345                 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
 346                     FlagState fsworking=(FlagState)en.nextElement();
 347                     if (ffan.getTagChange(ttp)){
 348                         processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
 349                     } else processed.add(fsworking);
 350                 }
 351             }
 352         }
 353         return processed;
 354     }
 355
 356
 357     private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
 358         if (sourcenodes.containsKey(fs))
 359             return (FlagState)sourcenodes.get(fs);
 360         else{
 361             sourcenodes.put(fs,fs);
 362             return fs;
 363         }
 364     }
 365
 366    /** Creates a DOT file using the flagstates for a given class
 367     *  @param cd ClassDescriptor of the class
 368     *  @throws java.io.IOException
 369     *  @see ClassDescriptor
 370     */
 371
 372     public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 373         File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
 374         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
 375         FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 376     }
 377
 378     /** Returns the flag states for the class descriptor. */
 379     public Set<FlagState> getFlagStates(ClassDescriptor cd) {
 380         if (flagstates.containsKey(cd))
 381             return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
 382         else
 383             return null;
 384     }
 385
 386
 387     private void createPossibleRuntimeStates(FlagState fs) {
 388         ClassDescriptor cd = fs.getClassDescriptor();
 389         Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 390         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 391         int externs=((Integer)extern_flags.get(cd)).intValue();
 392
 393         if(externs==0)
 394             return;
 395
 396         int noOfIterations=(1<<externs) - 1;
 397         boolean BoolValTable[]=new boolean[externs];
 398
 399
 400         for(int i=0; i < externs ; i++) {
 401             BoolValTable[i]=fs.get(fd[i]);
 402         }
 403
 404         for(int k=0; k<noOfIterations; k++) {
 405             for(int j=0; j < externs ;j++) {
 406                 if ((k% (1<<j)) == 0)
 407                     BoolValTable[j]=(!BoolValTable[j]);
 408             }
 409
 410             FlagState fstemp=fs;
 411
 412             for(int i=0; i < externs;i++) {
 413                 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 414             }
 415             if (!sourcenodes.containsKey(fstemp))
 416                 toprocess.add(fstemp);
 417
 418             fstemp=canonicalizeFlagState(sourcenodes,fstemp);
 419             fs.addEdge(new FEdge(fstemp,"Runtime", null));
 420         }
 421     }
 422
 423     public Vector getRootNodes(ClassDescriptor cd){
 424         return (Vector)cdtorootnodes.get(cd);
 425     }
 426 }
 427