more bugs
[IRC.git] / 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         int parameterindex=0;
167
168         for(int i=0; i < td.numParameters(); i++) {
169             FlagExpressionNode fen=td.getFlag(td.getParameter(i));
170             TagExpressionList tel=td.getTag(td.getParameter(i));
171             
172             /** Checking to see if the parameter is of the same
173              *  type/class as the flagstate's and also if the
174              *  flagstate fs triggers the given task*/
175
176             if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
177                 && isTaskTrigger_flag(fen,fs)
178                 && isTaskTrigger_tag(tel,fs)) {
179                 temp=fm.getParameter(i);
180                 parameterindex=i;
181                 trigger_ctr++;
182             }
183         }
184         
185         if (trigger_ctr==0) //Look at next task
186             continue;
187         
188         if (trigger_ctr>1)
189             System.out.println("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task:"+fs + " in "+td);
190         
191         
192         Set newstates=taganalysis.getFlagStates(td);
193         for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
194             FlagState fsnew=(FlagState) fsit.next();
195             System.out.println("SOURCE:"+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             } else {
201                 fsnew=((Hashtable<FlagState, FlagState>)flagstates.get(fsnew.getClassDescriptor())).get(fsnew);
202             }
203             fsnew.setAsSourceNode();
204             fsnew.addAllocatingTask(td);
205
206             ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
207         }
208         
209         Stack nodestack=new Stack();
210         HashSet discovered=new HashSet();
211         nodestack.push(fm);
212         discovered.add(fm);
213         //Iterating through the nodes
214         
215         while(!nodestack.isEmpty()) {
216             FlatNode fn1 = (FlatNode) nodestack.pop();
217             
218             if (fn1.kind()==FKind.FlatReturnNode) {
219                 /* Self edge */
220                 FEdge newedge=new FEdge(fs, taskname, td, parameterindex);
221                 fs.addEdge(newedge);
222                 continue;
223             } else if (fn1.kind()==FKind.FlatFlagActionNode) {
224                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
225                 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
226                     if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
227                         throw new Error("PRE FlagActions not supported");
228                     
229                 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
230                     Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
231                     for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
232                         FlagState fs_taskexit=(FlagState)en.nextElement();
233                         if (!sourcenodes.containsKey(fs_taskexit)) {
234                             toprocess.add(fs_taskexit);
235                         }
236                         //seen this node already
237                         fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
238                         FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex);
239                         fs.addEdge(newedge);
240                     }
241                     continue;
242                 }
243             }
244             /* Queue other nodes past this one */
245             for(int i=0;i<fn1.numNext();i++) {
246                 FlatNode fnext=fn1.getNext(i);
247                 if (!discovered.contains(fnext)) {
248                     discovered.add(fnext);
249                     nodestack.push(fnext);
250                 }
251             }
252         }
253     }
254 }
255
256
257 /** Determines whether the given flagstate satisfies a 
258  *  single parameter in the given task.
259  *  @param fen FlagExpressionNode
260  *  @see FlagExpressionNode
261  *  @param fs  FlagState
262  *  @see FlagState
263  *  @return <CODE>true</CODE> if fs satisfies the boolean expression
264     denoted by fen else <CODE>false</CODE>.
265  */
266
267
268 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
269     if (fen==null)
270         return true;
271     else if (fen instanceof FlagNode)
272         return fs.get(((FlagNode)fen).getFlag());
273     else
274         switch (((FlagOpNode)fen).getOp().getOp()) {
275         case Operation.LOGIC_AND:
276             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
277         case Operation.LOGIC_OR:
278             return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
279         case Operation.LOGIC_NOT:
280             return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
281         default:
282             return false;
283         }
284 }
285
286 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
287         
288         if (tel!=null){
289         for (int i=0;i<tel.numTags() ; i++){
290                 switch (fs.getTagCount(tel.getType(i))){
291                         case FlagState.ONETAG:
292                         case FlagState.MULTITAGS:
293                                 break;
294                         case FlagState.NOTAGS:
295                                 return false;
296                 }
297         }
298         }
299         return true;
300 }
301
302
303     private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
304         FlagState fstemp=fs;
305         Vector<FlagState> processed=new Vector<FlagState>();
306
307         //Process the flag changes
308         
309         for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
310             TempFlagPair tfp=(TempFlagPair)it_tfp.next();
311             if (temp==tfp.getTemp())
312                 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
313         }
314         
315         //Process the tag changes
316
317         processed.add(fstemp);
318         
319         //Process clears first
320         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
321             TempTagPair ttp=(TempTagPair)it_ttp.next();
322             
323             if (temp==ttp.getTemp()) {
324                 Vector<FlagState> oldprocess=processed;
325                 processed=new Vector<FlagState>();
326
327                 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
328                     FlagState fsworking=(FlagState)en.nextElement();
329                     if (!ffan.getTagChange(ttp)){
330                         processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
331                     } else processed.add(fsworking);
332                 }
333             }
334         }
335         //Process sets next
336         for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
337             TempTagPair ttp=(TempTagPair)it_ttp.next();
338             
339             if (temp==ttp.getTemp()) {
340                 Vector<FlagState> oldprocess=processed;
341                 processed=new Vector<FlagState>();
342
343                 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
344                     FlagState fsworking=(FlagState)en.nextElement();
345                     if (ffan.getTagChange(ttp)){
346                         processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
347                     } else processed.add(fsworking);
348                 }
349             }
350         }
351         return processed;
352     }           
353     
354
355     private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
356         if (sourcenodes.containsKey(fs))
357             return (FlagState)sourcenodes.get(fs);
358         else{
359             sourcenodes.put(fs,fs);
360             return fs;
361         }
362     }
363
364    /** Creates a DOT file using the flagstates for a given class
365     *  @param cd ClassDescriptor of the class
366     *  @throws java.io.IOException
367     *  @see ClassDescriptor
368     */
369     
370     public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
371         File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
372         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
373         FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
374     }
375
376     /** Returns the flag states for the class descriptor. */
377     public Set<FlagState> getFlagStates(ClassDescriptor cd) {
378         if (flagstates.containsKey(cd))
379             return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
380         else
381             return new HashSet<FlagState>();
382     }
383
384
385     private void createPossibleRuntimeStates(FlagState fs) {
386         ClassDescriptor cd = fs.getClassDescriptor();
387         Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
388         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);    
389         int externs=((Integer)extern_flags.get(cd)).intValue();
390         
391         if(externs==0)
392             return;
393         
394         int noOfIterations=(1<<externs) - 1;
395         boolean BoolValTable[]=new boolean[externs];
396         
397         
398         for(int i=0; i < externs ; i++) {
399             BoolValTable[i]=fs.get(fd[i]);
400         }
401         
402         for(int k=0; k<noOfIterations; k++) {
403             for(int j=0; j < externs ;j++) {
404                 if ((k% (1<<j)) == 0)
405                     BoolValTable[j]=(!BoolValTable[j]);
406             }
407         
408             FlagState fstemp=fs;
409             
410             for(int i=0; i < externs;i++) {
411                 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
412             }
413             if (!sourcenodes.containsKey(fstemp))
414                 toprocess.add(fstemp);
415
416             fstemp=canonicalizeFlagState(sourcenodes,fstemp);
417             fs.addEdge(new FEdge(fstemp,"Runtime", null, -1));
418         }
419     }
420     
421     public Vector getRootNodes(ClassDescriptor cd){
422         return (Vector)cdtorootnodes.get(cd);
423     }
424
425