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 public class TaskAnalysis {
  13     State state;
  14     Hashtable flagstates;
  15     Hashtable flags;
  16     Hashtable extern_flags;
  17     Queue<FlagState> toprocess;
  18     Hashtable map;
  19     TempDescriptor temp;
  20     TypeUtil typeutil;
  21
  22     /**
  23      * Class Constructor
  24      *
  25      * @param state a flattened State object
  26      * @see State
  27      * @param map Hashtable containing the temp to var mapping
  28      */
  29     public TaskAnalysis(State state,Hashtable map)
  30     {
  31         this.state=state;
  32         this.map=map;
  33         this.typeutil=new TypeUtil(state);
  34     }
  35
  36     /** This function builds a table of flags for each class **/
  37
  38     private void getFlagsfromClasses() {
  39         flags=new Hashtable();
  40         extern_flags = new Hashtable();
  41
  42         for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
  43
  44             ClassDescriptor cd = (ClassDescriptor)it_classes.next();
  45             System.out.println(cd.getSymbol());
  46             Vector vFlags=new Vector();
  47             FlagDescriptor flag[];
  48             int ctr=0;
  49
  50
  51             /* Adding the flags of the super class */
  52             if (cd.getSuper()!=null) {
  53                 ClassDescriptor superdesc=cd.getSuperDesc();
  54
  55                 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
  56                     FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
  57                     System.out.println(fd.toString());
  58                     vFlags.add(fd);
  59                 }
  60             }
  61
  62             for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
  63                 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
  64                 System.out.println(fd.toString());
  65                 vFlags.add(fd);
  66             }
  67
  68             if (vFlags.size()!=0) {
  69                 flag=new FlagDescriptor[vFlags.size()];
  70
  71                 for(int i=0;i < vFlags.size() ; i++) {
  72                     if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
  73                         flag[ctr]=(FlagDescriptor)vFlags.get(i);
  74                         vFlags.remove(flag[ctr]);
  75                         ctr++;
  76                     }
  77                 }
  78                 for(int i=0;i < vFlags.size() ; i++) {
  79                     flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
  80                 }
  81                 extern_flags.put(cd,new Integer(ctr));
  82                 flags.put(cd,flag);
  83
  84             }
  85         }
  86     }
  87
  88     public void taskAnalysis() throws java.io.IOException {
  89         flagstates=new Hashtable();
  90         Hashtable<FlagState,FlagState> sourcenodes;
  91
  92         getFlagsfromClasses();
  93
  94         int externs;
  95         toprocess=new LinkedList<FlagState>();
  96
  97         for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
  98             ClassDescriptor cd=(ClassDescriptor)it_classes.next();
  99             externs=((Integer)extern_flags.get(cd)).intValue();
 100             FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 101
 102             //Debug block
 103             System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
 104             System.out.println("No of externs " + externs);
 105             System.out.println("No of flags: "+fd.length);
 106             //Debug block
 107
 108             flagstates.put(cd,new Hashtable<FlagState,FlagState>());
 109         }
 110
 111
 112         ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 113
 114         sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
 115
 116         FlagState fsstartup=new FlagState(startupobject);
 117         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
 118
 119         fsstartup=fsstartup.setFlag(fd[0],true);
 120
 121         sourcenodes.put(fsstartup,fsstartup);
 122         toprocess.add(fsstartup);
 123
 124         while (!toprocess.isEmpty()) {
 125             FlagState trigger=toprocess.poll();
 126             createPossibleRuntimeStates(trigger);
 127             analyseTasks(trigger);
 128         }
 129
 130         //Creating DOT files
 131         Enumeration e=flagstates.keys();
 132
 133         while (e.hasMoreElements()) {
 134             System.out.println("creating dot file");
 135             ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
 136             System.out.println((cdtemp.getSymbol()));
 137             createDOTfile(cdtemp);
 138         }
 139     }
 140
 141
 142 private void analyseTasks(FlagState fs) {
 143     Hashtable<FlagState,FlagState> sourcenodes;
 144
 145     ClassDescriptor cd=fs.getClassDescriptor();
 146
 147     sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 148
 149     for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
 150         TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 151         String taskname=td.getSymbol();
 152         int trigger_ctr=0;
 153
 154         for(int i=0; i < td.numParameters(); i++) {
 155             FlagExpressionNode fen=td.getFlag(td.getParameter(i));
 156             if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
 157                 && isTaskTrigger(fen,fs)) {
 158                 temp=(TempDescriptor)map.get(td.getParameter(i));
 159                 trigger_ctr++;
 160             }
 161         }
 162
 163         if (trigger_ctr==0)
 164             return;
 165
 166         if (trigger_ctr>1)
 167             throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
 168
 169         //Iterating through the nodes
 170         FlatMethod fm = state.getMethodFlat(td);
 171         FlatNode fn=fm.methodEntryNode();
 172
 173         HashSet tovisit= new HashSet();
 174         HashSet visited= new HashSet();
 175
 176         tovisit.add(fn);
 177         while(!tovisit.isEmpty()) {
 178             FlatNode fn1 = (FlatNode)tovisit.iterator().next();
 179             tovisit.remove(fn1);
 180             visited.add(fn1);
 181             // Queue all of the next nodes
 182             for(int i = 0; i < fn1.numNext(); i++) {
 183                 FlatNode nn=fn1.getNext(i);
 184                 if (!visited.contains(nn))
 185                     tovisit.add(nn);
 186             }
 187
 188             if (fn.kind()==FKind.FlatFlagActionNode) {
 189                 if (((FlatFlagActionNode)fn).getTaskType() == FlatFlagActionNode.PRE) {
 190                     throw new Error("PRE FlagActions not supported");
 191
 192                 } else if (((FlatFlagActionNode)fn).getTaskType() == FlatFlagActionNode.NEWOBJECT) {
 193                     FlagState fsnew=evalNewObjNode(fn);
 194                     //Have we seen this node yet
 195                     if (!sourcenodes.containsKey(fsnew)) {
 196                         sourcenodes.put(fsnew, fsnew);
 197                         toprocess.add(fsnew);
 198                     }
 199                 } else if (((FlatFlagActionNode)fn).getTaskType() == FlatFlagActionNode.TASKEXIT) {
 200                     FlagState fs_taskexit=evalTaskExitNode(fn,cd,fs);
 201
 202                     if (!sourcenodes.containsKey(fs_taskexit)) {
 203                         toprocess.add(fs_taskexit);
 204                     }
 205                     //seen this node already
 206                     fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
 207                     Edge newedge=new Edge(fs_taskexit,taskname);
 208                     fs.addEdge(newedge);
 209                 }
 210             }
 211         }
 212     }
 213 }
 214
 215 private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) {
 216     if (fen instanceof FlagNode)
 217         return fs.get(((FlagNode)fen).getFlag());
 218     else
 219         switch (((FlagOpNode)fen).getOp().getOp()) {
 220         case Operation.LOGIC_AND:
 221             return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
 222         case Operation.LOGIC_OR:
 223             return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
 224         case Operation.LOGIC_NOT:
 225             return !(isTaskTrigger(((FlagOpNode)fen).getLeft(),fs));
 226         default:
 227             return false;
 228         }
 229 }
 230
 231     private FlagState evalNewObjNode(FlatNode nn){
 232             TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
 233
 234                 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
 235                 ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
 236
 237                 FlagState fstemp=new FlagState(cd_new);
 238
 239                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 240                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 241                         if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
 242                         {
 243                                 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 244                         }
 245                         else
 246                                 break;
 247                 }
 248                 return fstemp;
 249         }
 250
 251         private FlagState evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs){
 252                 FlagState fstemp=fs;
 253
 254                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 255                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 256                         if (temp.toString().equals(tfp.getTemp().toString()))
 257                                 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 258                 }
 259                 return fstemp;
 260         }
 261
 262
 263     private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
 264         if (sourcenodes.containsKey(fs))
 265             return (FlagState)sourcenodes.get(fs);
 266         else{
 267             sourcenodes.put(fs,fs);
 268             return fs;
 269         }
 270     }
 271
 272    public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 273         File dotfile= new File("graph"+cd.getSymbol()+".dot");
 274         FileOutputStream dotstream=new FileOutputStream(dotfile,true);
 275         FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 276    }
 277
 278
 279     private String getTaskName(TaskDescriptor td) {
 280         StringTokenizer st = new StringTokenizer(td.toString(),"(");
 281         return st.nextToken();
 282     }
 283
 284 private void createPossibleRuntimeStates(FlagState fs) {
 285     ClassDescriptor cd = fs.getClassDescriptor();
 286     Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 287     FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 288     int externs=((Integer)extern_flags.get(cd)).intValue();
 289     if(externs==0)
 290         return;
 291
 292     int noOfIterations=(1<<externs) - 1;
 293     boolean BoolValTable[]=new boolean[externs];
 294
 295
 296     for(int i=0; i < externs ; i++) {
 297         BoolValTable[i]=fs.get(fd[i]);
 298     }
 299
 300
 301     for(int k=0; k<noOfIterations; k++) {
 302         for(int j=0; j < externs ;j++) {
 303             if ((k% (1<<j)) == 0)
 304                 BoolValTable[j]=(!BoolValTable[j]);
 305         }
 306
 307         FlagState fstemp=fs;
 308
 309         for(int i=0; i < externs;i++) {
 310             fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 311         }
 312         if (!sourcenodes.containsKey(fstemp))
 313             toprocess.add(fstemp);
 314
 315         fstemp=canonicalizeFlagState(sourcenodes,fstemp);
 316         fs.addEdge(new Edge(fstemp,"Runtime"));
 317     }
 318 }
 319 }