1 package Analysis.TaskStateAnalysis;
7 import java.io.FileWriter;
8 import java.io.FileOutputStream;
10 public class TaskAnalysis {
14 Hashtable extern_flags;
15 Queue<FlagState> toprocess;
16 TagAnalysis taganalysis;
23 * @param state a flattened State object
26 public TaskAnalysis(State state, TagAnalysis taganalysis)
29 this.typeutil=new TypeUtil(state);
30 this.taganalysis=taganalysis;
34 /** Builds a table of flags for each class in the Bristlecone program.
35 * It creates two hashtables: one which holds the ClassDescriptors and arrays of
36 * FlagDescriptors as key-value pairs; the other holds the ClassDescriptor and the
37 * number of external flags for that specific class.
40 private void getFlagsfromClasses() {
41 flags=new Hashtable();
42 extern_flags = new Hashtable();
44 /** Iterate through the classes used in the program to build the table of flags
46 for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
48 ClassDescriptor cd = (ClassDescriptor)it_classes.next();
49 System.out.println(cd.getSymbol());
50 Vector vFlags=new Vector();
51 FlagDescriptor flag[];
55 /* Adding the flags of the super class */
56 if (cd.getSuper()!=null) {
57 ClassDescriptor superdesc=cd.getSuperDesc();
59 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
60 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
61 System.out.println(fd.toString());
66 for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
67 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
71 if (vFlags.size()!=0) {
72 flag=new FlagDescriptor[vFlags.size()];
74 for(int i=0;i < vFlags.size() ; i++) {
75 if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
76 flag[ctr]=(FlagDescriptor)vFlags.get(i);
77 vFlags.remove(flag[ctr]);
81 for(int i=0;i < vFlags.size() ; i++) {
82 flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
84 extern_flags.put(cd,new Integer(ctr));
90 /** Method which starts up the analysis
94 public void taskAnalysis() throws java.io.IOException {
95 flagstates=new Hashtable();
96 Hashtable<FlagState,FlagState> sourcenodes;
99 getFlagsfromClasses();
102 toprocess=new LinkedList<FlagState>();
104 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
105 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
106 externs=((Integer)extern_flags.get(cd)).intValue();
107 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
110 System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
111 System.out.println("No of externs " + externs);
112 System.out.println("No of flags: "+fd.length);
115 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
119 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
121 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
122 FlagState fsstartup=new FlagState(startupobject);
125 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
127 fsstartup=fsstartup.setFlag(fd[0],true);
128 fsstartup.setAsSourceNode();
130 sourcenodes.put(fsstartup,fsstartup);
131 toprocess.add(fsstartup);
133 /** Looping through the flagstates in the toprocess queue to perform the state analysis */
134 while (!toprocess.isEmpty()) {
135 FlagState trigger=toprocess.poll();
136 createPossibleRuntimeStates(trigger);
138 analyseTasks(trigger);
141 /** Creating DOT files */
142 Enumeration e=flagstates.keys();
144 while (e.hasMoreElements()) {
145 System.out.println("creating dot file");
146 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
147 System.out.println((cdtemp.getSymbol()));
148 createDOTfile(cdtemp);
153 /** Analyses the set of tasks based on the given flagstate, checking
154 * to see which tasks are triggered and what new flagstates are created
155 * from the base flagstate.
156 * @param fs A FlagState object which is used to analyse the task
160 private void analyseTasks(FlagState fs) {
161 ClassDescriptor cd=fs.getClassDescriptor();
162 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
164 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
165 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
166 String taskname=td.getSymbol();
169 System.out.println();
170 System.out.println(cd.getSymbol()+" : "+fs.getTextLabel());
171 System.out.println("Task: "+taskname);
174 /** counter to keep track of the number of parameters (of the task being analyzed) that
175 * are satisfied by the flagstate.
178 TempDescriptor temp=null;
179 FlatMethod fm = state.getMethodFlat(td);
181 for(int i=0; i < td.numParameters(); i++) {
182 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
183 TagExpressionList tel=td.getTag(td.getParameter(i));
185 /** Checking to see if the parameter is of the same type/class as the
186 * flagstate's and also if the flagstate fs triggers the given task*/
187 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
188 && isTaskTrigger_flag(fen,fs)
189 && isTaskTrigger_tag(tel,fs)) {
190 temp=fm.getParameter(i);
195 if (trigger_ctr==0) //Look at next task
199 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
203 System.out.println("Task:" + taskname +" is triggered");
206 Set newstates=taganalysis.getFlagStates(td);
207 for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
208 FlagState fsnew=(FlagState) fsit.next();
209 fsnew.setAsSourceNode();
211 if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
212 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
213 toprocess.add(fsnew);
217 Stack nodestack=new Stack();
218 HashSet discovered=new HashSet();
221 //Iterating through the nodes
223 while(!nodestack.isEmpty()) {
224 FlatNode fn1 = (FlatNode) nodestack.pop();
226 if (fn1.kind()==FKind.FlatReturnNode) {
228 FEdge newedge=new FEdge(fs, taskname);
231 } else if (fn1.kind()==FKind.FlatFlagActionNode) {
232 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
233 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
234 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
235 throw new Error("PRE FlagActions not supported");
237 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
239 System.out.println("TASKEXIT");
242 Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
244 for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
245 FlagState fs_taskexit=(FlagState)en.nextElement();
246 if (!sourcenodes.containsKey(fs_taskexit)) {
247 toprocess.add(fs_taskexit);
250 //seen this node already
251 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
252 FEdge newedge=new FEdge(fs_taskexit,taskname);
253 //FEdge newedge=new FEdge(fs_taskexit,td);
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);
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
278 * @return <CODE>true</CODE> if fs satisfies the boolean expression
279 denoted by fen else <CODE>false</CODE>.
283 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
286 else if (fen instanceof FlagNode)
287 return fs.get(((FlagNode)fen).getFlag());
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));
301 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
304 for (int i=0;i<tel.numTags() ; i++){
305 switch (fs.getTagCount(tel.getType(i))){
306 case FlagState.ONETAG:
307 case FlagState.MULTITAGS:
309 case FlagState.NOTAGS:
317 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
319 for(int i=0;i<tel.numTags() ; i++){
320 if (tel.getType(i).equals(tagtype))
326 /** Evaluates a NewObject Node and returns the newly created
327 * flagstate to add to the process queue.
334 private FlagState evalNewObjNode(FlatNode nn){
336 ClassDescriptor cd_new=((FlatNew)nn.getPrev(0)).getType().getClassDesc();
339 //TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
341 //if (tdArray.length==0)
344 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
345 //ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
347 FlagState fstemp=new FlagState(cd_new);
349 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
350 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
351 if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
353 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
359 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
360 TempTagPair ttp=(TempTagPair)it_ttp.next();
361 if (! (ttp.getTag()==null)){
362 fstemp=fstemp.setTag(ttp.getTag());
371 private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
373 //FlagState[] fstemparray=new FlagState[3];
374 Vector<FlagState> inprocess=new Vector<FlagState>();
375 Vector<FlagState> processed=new Vector<FlagState>();
377 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
378 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
379 if (temp==tfp.getTemp())
380 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
383 inprocess.add(fstemp);
384 processed.add(fstemp);
386 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
387 TempTagPair ttp=(TempTagPair)it_ttp.next();
389 if (temp==ttp.getTemp()){
390 processed=new Vector<FlagState>();
391 for (Enumeration en=inprocess.elements();en.hasMoreElements();){
392 FlagState fsworking=(FlagState)en.nextElement();
393 if (((FlatFlagActionNode)nn).getTagChange(ttp)){
394 fsworking=fsworking.setTag(ttp.getTag());
395 processed.add(fsworking);
399 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
410 private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
411 if (sourcenodes.containsKey(fs))
412 return (FlagState)sourcenodes.get(fs);
414 sourcenodes.put(fs,fs);
419 /** Creates a DOT file using the flagstates for a given class
420 * @param cd ClassDescriptor of the class
421 * @throws java.io.IOException
422 * @see ClassDescriptor
425 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
426 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
427 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
428 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
432 /** Returns the flag states for the class descriptor. */
433 public Set getFlagStates(ClassDescriptor cd) {
434 if (flagstates.containsKey(cd))
435 return ((Hashtable)flagstates.get(cd)).keySet();
441 private void createPossibleRuntimeStates(FlagState fs) {
442 ClassDescriptor cd = fs.getClassDescriptor();
443 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
444 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
445 int externs=((Integer)extern_flags.get(cd)).intValue();
450 int noOfIterations=(1<<externs) - 1;
451 boolean BoolValTable[]=new boolean[externs];
454 for(int i=0; i < externs ; i++) {
455 BoolValTable[i]=fs.get(fd[i]);
458 for(int k=0; k<noOfIterations; k++) {
459 for(int j=0; j < externs ;j++) {
460 if ((k% (1<<j)) == 0)
461 BoolValTable[j]=(!BoolValTable[j]);
466 for(int i=0; i < externs;i++) {
467 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
469 if (!sourcenodes.containsKey(fstemp))
470 toprocess.add(fstemp);
472 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
473 fs.addEdge(new FEdge(fstemp,"Runtime"));