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;
33 /** Builds a table of flags for each class in the Bristlecone program.
34 * It creates two hashtables: one which holds the ClassDescriptors and arrays of
35 * FlagDescriptors as key-value pairs; the other holds the ClassDescriptor and the
36 * number of external flags for that specific class.
39 private void getFlagsfromClasses() {
40 flags=new Hashtable();
41 extern_flags = new Hashtable();
43 /** Iterate through the classes used in the program to build the table of flags
45 for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
47 ClassDescriptor cd = (ClassDescriptor)it_classes.next();
48 System.out.println(cd.getSymbol());
49 Vector vFlags=new Vector();
50 FlagDescriptor flag[];
54 /* Adding the flags of the super class */
55 if (cd.getSuper()!=null) {
56 ClassDescriptor superdesc=cd.getSuperDesc();
58 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
59 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
60 System.out.println(fd.toString());
65 for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
66 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
70 if (vFlags.size()!=0) {
71 flag=new FlagDescriptor[vFlags.size()];
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]);
80 for(int i=0;i < vFlags.size() ; i++) {
81 flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
83 extern_flags.put(cd,new Integer(ctr));
89 /** Method which starts up the analysis
93 public void taskAnalysis() throws java.io.IOException {
94 flagstates=new Hashtable();
95 Hashtable<FlagState,FlagState> sourcenodes;
98 getFlagsfromClasses();
101 toprocess=new LinkedList<FlagState>();
103 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
104 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
105 externs=((Integer)extern_flags.get(cd)).intValue();
106 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
109 System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
110 System.out.println("No of externs " + externs);
111 System.out.println("No of flags: "+fd.length);
114 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
118 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
120 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
122 FlagState fsstartup=new FlagState(startupobject);
123 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
125 fsstartup=fsstartup.setFlag(fd[0],true);
127 sourcenodes.put(fsstartup,fsstartup);
128 toprocess.add(fsstartup);
130 /** Looping through the flagstates in the toprocess queue to perform the state analysis */
131 while (!toprocess.isEmpty()) {
132 FlagState trigger=toprocess.poll();
133 createPossibleRuntimeStates(trigger);
135 analyseTasks(trigger);
138 /** Creating DOT files */
139 Enumeration e=flagstates.keys();
141 while (e.hasMoreElements()) {
142 System.out.println("creating dot file");
143 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
144 System.out.println((cdtemp.getSymbol()));
145 createDOTfile(cdtemp);
150 /** Analyses the set of tasks based on the given flagstate, checking
151 * to see which tasks are triggered and what new flagstates are created
152 * from the base flagstate.
153 * @param fs A FlagState object which is used to analyse the task
157 private void analyseTasks(FlagState fs) {
158 ClassDescriptor cd=fs.getClassDescriptor();
159 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
161 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
162 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
163 String taskname=td.getSymbol();
166 System.out.println();
167 System.out.println(cd.getSymbol()+" : "+fs.getTextLabel());
168 System.out.println("Task: "+taskname);
171 /** counter to keep track of the number of parameters (of the task being analyzed) that
172 * are satisfied by the flagstate.
175 TempDescriptor temp=null;
176 FlatMethod fm = state.getMethodFlat(td);
178 for(int i=0; i < td.numParameters(); i++) {
179 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
180 TagExpressionList tel=td.getTag(td.getParameter(i));
182 /** Checking to see if the parameter is of the same type/class as the
183 * flagstate's and also if the flagstate fs triggers the given task*/
184 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
185 && isTaskTrigger_flag(fen,fs)
186 && isTaskTrigger_tag(tel,fs)) {
187 temp=fm.getParameter(i);
192 if (trigger_ctr==0) //Look at next task
196 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
200 System.out.println("Task:" + taskname +" is triggered");
203 Set newstates=taganalysis.getFlagStates(td);
204 for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
205 FlagState fsnew=(FlagState) fsit.next();
206 if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
207 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
208 toprocess.add(fsnew);
212 //Iterating through the nodes
213 Set nodeset=fm.getNodeSet();
215 for(Iterator nodeit=nodeset.iterator();nodeit.hasNext();) {
216 FlatNode fn1 = (FlatNode) nodeit.next();
218 if (fn1.kind()==FKind.FlatFlagActionNode) {
219 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
220 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
221 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
222 throw new Error("PRE FlagActions not supported");
224 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
226 System.out.println("TASKEXIT");
229 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);
237 //seen this node already
238 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
239 FEdge newedge=new FEdge(fs_taskexit,taskname);
240 //FEdge newedge=new FEdge(fs_taskexit,td);
250 /** Determines whether the given flagstate satisfies a
251 * single parameter in the given task.
252 * @param fen FlagExpressionNode
253 * @see FlagExpressionNode
254 * @param fs FlagState
256 * @return <CODE>true</CODE> if fs satisfies the boolean expression
257 denoted by fen else <CODE>false</CODE>.
261 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
262 if (fen instanceof FlagNode)
263 return fs.get(((FlagNode)fen).getFlag());
265 switch (((FlagOpNode)fen).getOp().getOp()) {
266 case Operation.LOGIC_AND:
267 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
268 case Operation.LOGIC_OR:
269 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
270 case Operation.LOGIC_NOT:
271 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
277 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
280 for (int i=0;i<tel.numTags() ; i++){
281 switch (fs.getTagCount(tel.getType(i))){
282 case FlagState.ONETAG:
283 case FlagState.MULTITAGS:
285 case FlagState.NOTAGS:
293 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
295 for(int i=0;i<tel.numTags() ; i++){
296 if (tel.getType(i).equals(tagtype))
302 /** Evaluates a NewObject Node and returns the newly created
303 * flagstate to add to the process queue.
310 private FlagState evalNewObjNode(FlatNode nn){
312 ClassDescriptor cd_new=((FlatNew)nn.getPrev(0)).getType().getClassDesc();
315 //TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
317 //if (tdArray.length==0)
320 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
321 //ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
323 FlagState fstemp=new FlagState(cd_new);
325 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
326 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
327 if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
329 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
335 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
336 TempTagPair ttp=(TempTagPair)it_ttp.next();
337 if (! (ttp.getTag()==null)){
338 fstemp=fstemp.setTag(ttp.getTag());
347 private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
349 //FlagState[] fstemparray=new FlagState[3];
350 Vector<FlagState> inprocess=new Vector<FlagState>();
351 Vector<FlagState> processed=new Vector<FlagState>();
353 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
354 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
355 if (temp==tfp.getTemp())
356 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
359 inprocess.add(fstemp);
360 processed.add(fstemp);
362 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
363 TempTagPair ttp=(TempTagPair)it_ttp.next();
365 if (temp==ttp.getTemp()){
366 processed=new Vector<FlagState>();
367 for (Enumeration en=inprocess.elements();en.hasMoreElements();){
368 FlagState fsworking=(FlagState)en.nextElement();
369 if (((FlatFlagActionNode)nn).getTagChange(ttp)){
370 fsworking=fsworking.setTag(ttp.getTag());
371 processed.add(fsworking);
375 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
386 private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
387 if (sourcenodes.containsKey(fs))
388 return (FlagState)sourcenodes.get(fs);
390 sourcenodes.put(fs,fs);
395 /** Creates a DOT file using the flagstates for a given class
396 * @param cd ClassDescriptor of the class
397 * @throws java.io.IOException
398 * @see ClassDescriptor
401 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
402 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
403 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
404 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
408 /** Returns the flag states for the class descriptor. */
409 public Set getFlagStates(ClassDescriptor cd) {
410 if (flagstates.containsKey(cd))
411 return ((Hashtable)flagstates.get(cd)).keySet();
417 private void createPossibleRuntimeStates(FlagState fs) {
418 ClassDescriptor cd = fs.getClassDescriptor();
419 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
420 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
421 int externs=((Integer)extern_flags.get(cd)).intValue();
426 int noOfIterations=(1<<externs) - 1;
427 boolean BoolValTable[]=new boolean[externs];
430 for(int i=0; i < externs ; i++) {
431 BoolValTable[i]=fs.get(fd[i]);
434 for(int k=0; k<noOfIterations; k++) {
435 for(int j=0; j < externs ;j++) {
436 if ((k% (1<<j)) == 0)
437 BoolValTable[j]=(!BoolValTable[j]);
442 for(int i=0; i < externs;i++) {
443 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
445 if (!sourcenodes.containsKey(fstemp))
446 toprocess.add(fstemp);
448 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
449 fs.addEdge(new FEdge(fstemp,"Runtime"));