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