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;
17 Hashtable cdtorootnodes;
24 * @param state a flattened State object
27 public TaskAnalysis(State state, TagAnalysis taganalysis)
30 this.typeutil=new TypeUtil(state);
31 this.taganalysis=taganalysis;
35 /** Builds a table of flags for each class in the Bristlecone program.
36 * It creates two hashtables: one which holds the ClassDescriptors and arrays of
37 * FlagDescriptors as key-value pairs; the other holds the ClassDescriptor and the
38 * number of external flags for that specific class.
41 private void getFlagsfromClasses() {
42 flags=new Hashtable();
43 extern_flags = new Hashtable();
45 /** Iterate through the classes used in the program to build the table of flags
47 for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
49 ClassDescriptor cd = (ClassDescriptor)it_classes.next();
50 System.out.println(cd.getSymbol());
51 Vector vFlags=new Vector();
52 FlagDescriptor flag[];
56 /* Adding the flags of the super class */
57 if (cd.getSuper()!=null) {
58 ClassDescriptor superdesc=cd.getSuperDesc();
60 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
61 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
62 System.out.println(fd.toString());
67 for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
68 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
72 if (vFlags.size()!=0) {
73 flag=new FlagDescriptor[vFlags.size()];
75 for(int i=0;i < vFlags.size() ; i++) {
76 if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
77 flag[ctr]=(FlagDescriptor)vFlags.get(i);
78 vFlags.remove(flag[ctr]);
82 for(int i=0;i < vFlags.size() ; i++) {
83 flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
85 extern_flags.put(cd,new Integer(ctr));
91 /** Method which starts up the analysis
95 public void taskAnalysis() throws java.io.IOException {
96 flagstates=new Hashtable();
97 Hashtable<FlagState,FlagState> sourcenodes;
98 cdtorootnodes=new Hashtable();
100 getFlagsfromClasses();
103 toprocess=new LinkedList<FlagState>();
105 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
106 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
107 externs=((Integer)extern_flags.get(cd)).intValue();
108 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
111 System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
112 System.out.println("No of externs " + externs);
113 System.out.println("No of flags: "+fd.length);
116 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
117 cdtorootnodes.put(cd,new Vector());
121 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
123 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
124 FlagState fsstartup=new FlagState(startupobject);
127 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
129 fsstartup=fsstartup.setFlag(fd[0],true);
130 fsstartup.setAsSourceNode();
131 ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
133 sourcenodes.put(fsstartup,fsstartup);
134 toprocess.add(fsstartup);
136 /** Looping through the flagstates in the toprocess queue to perform the state analysis */
137 while (!toprocess.isEmpty()) {
138 FlagState trigger=toprocess.poll();
139 createPossibleRuntimeStates(trigger);
141 analyseTasks(trigger);
146 /** Creating DOT files */
147 Enumeration e=flagstates.keys();
149 while (e.hasMoreElements()) {
150 System.out.println("creating dot file");
151 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
152 System.out.println((cdtemp.getSymbol()));
155 createDOTfile(cdtemp);
160 /** Analyses the set of tasks based on the given flagstate, checking
161 * to see which tasks are triggered and what new flagstates are created
162 * from the base flagstate.
163 * @param fs A FlagState object which is used to analyse the task
167 private void analyseTasks(FlagState fs) {
168 ClassDescriptor cd=fs.getClassDescriptor();
169 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
171 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
172 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
173 String taskname=td.getSymbol();
176 System.out.println();
177 System.out.println(cd.getSymbol()+" : "+fs.getTextLabel());
178 System.out.println("Task: "+taskname);
181 /** counter to keep track of the number of parameters (of the task being analyzed) that
182 * are satisfied by the flagstate.
185 TempDescriptor temp=null;
186 FlatMethod fm = state.getMethodFlat(td);
188 for(int i=0; i < td.numParameters(); i++) {
189 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
190 TagExpressionList tel=td.getTag(td.getParameter(i));
192 /** Checking to see if the parameter is of the same type/class as the
193 * flagstate's and also if the flagstate fs triggers the given task*/
194 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
195 && isTaskTrigger_flag(fen,fs)
196 && isTaskTrigger_tag(tel,fs)) {
197 temp=fm.getParameter(i);
202 if (trigger_ctr==0) //Look at next task
206 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
210 System.out.println("Task:" + taskname +" is triggered");
213 Set newstates=taganalysis.getFlagStates(td);
214 for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
215 FlagState fsnew=(FlagState) fsit.next();
216 fsnew.setAsSourceNode();
217 fsnew.addAllocatingTask(td);
218 ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
220 if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
221 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
222 toprocess.add(fsnew);
226 Stack nodestack=new Stack();
227 HashSet discovered=new HashSet();
230 //Iterating through the nodes
232 while(!nodestack.isEmpty()) {
233 FlatNode fn1 = (FlatNode) nodestack.pop();
235 if (fn1.kind()==FKind.FlatReturnNode) {
237 FEdge newedge=new FEdge(fs, taskname);
240 } else if (fn1.kind()==FKind.FlatFlagActionNode) {
241 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
242 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
243 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
244 throw new Error("PRE FlagActions not supported");
246 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
248 System.out.println("TASKEXIT");
251 Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
253 for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
254 FlagState fs_taskexit=(FlagState)en.nextElement();
255 if (!sourcenodes.containsKey(fs_taskexit)) {
256 toprocess.add(fs_taskexit);
259 //seen this node already
260 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
261 FEdge newedge=new FEdge(fs_taskexit,taskname);
262 //FEdge newedge=new FEdge(fs_taskexit,td);
268 /* Queue other nodes past this one */
269 for(int i=0;i<fn1.numNext();i++) {
270 FlatNode fnext=fn1.getNext(i);
271 if (!discovered.contains(fnext)) {
272 discovered.add(fnext);
273 nodestack.push(fnext);
281 /** Determines whether the given flagstate satisfies a
282 * single parameter in the given task.
283 * @param fen FlagExpressionNode
284 * @see FlagExpressionNode
285 * @param fs FlagState
287 * @return <CODE>true</CODE> if fs satisfies the boolean expression
288 denoted by fen else <CODE>false</CODE>.
292 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
295 else if (fen instanceof FlagNode)
296 return fs.get(((FlagNode)fen).getFlag());
298 switch (((FlagOpNode)fen).getOp().getOp()) {
299 case Operation.LOGIC_AND:
300 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
301 case Operation.LOGIC_OR:
302 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
303 case Operation.LOGIC_NOT:
304 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
310 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
313 for (int i=0;i<tel.numTags() ; i++){
314 switch (fs.getTagCount(tel.getType(i))){
315 case FlagState.ONETAG:
316 case FlagState.MULTITAGS:
318 case FlagState.NOTAGS:
326 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
328 for(int i=0;i<tel.numTags() ; i++){
329 if (tel.getType(i).equals(tagtype))
335 private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
337 Vector<FlagState> processed=new Vector<FlagState>();
339 //Process the flag changes
341 for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
342 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
343 if (temp==tfp.getTemp())
344 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
347 //Process the tag changes
349 processed.add(fstemp);
351 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
352 TempTagPair ttp=(TempTagPair)it_ttp.next();
354 if (temp==ttp.getTemp()) {
355 Vector<FlagState> oldprocess=processed;
356 processed=new Vector<FlagState>();
358 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
359 FlagState fsworking=(FlagState)en.nextElement();
360 if (ffan.getTagChange(ttp)){
361 processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
363 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
373 private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
374 if (sourcenodes.containsKey(fs))
375 return (FlagState)sourcenodes.get(fs);
377 sourcenodes.put(fs,fs);
382 /** Creates a DOT file using the flagstates for a given class
383 * @param cd ClassDescriptor of the class
384 * @throws java.io.IOException
385 * @see ClassDescriptor
388 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
389 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
390 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
391 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
395 /** Returns the flag states for the class descriptor. */
396 public Set getFlagStates(ClassDescriptor cd) {
397 if (flagstates.containsKey(cd))
398 return ((Hashtable)flagstates.get(cd)).keySet();
404 private void createPossibleRuntimeStates(FlagState fs) {
405 ClassDescriptor cd = fs.getClassDescriptor();
406 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
407 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
408 int externs=((Integer)extern_flags.get(cd)).intValue();
413 int noOfIterations=(1<<externs) - 1;
414 boolean BoolValTable[]=new boolean[externs];
417 for(int i=0; i < externs ; i++) {
418 BoolValTable[i]=fs.get(fd[i]);
421 for(int k=0; k<noOfIterations; k++) {
422 for(int j=0; j < externs ;j++) {
423 if ((k% (1<<j)) == 0)
424 BoolValTable[j]=(!BoolValTable[j]);
429 for(int i=0; i < externs;i++) {
430 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
432 if (!sourcenodes.containsKey(fstemp))
433 toprocess.add(fstemp);
435 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
436 fs.addEdge(new FEdge(fstemp,"Runtime"));
440 public Vector getRootNodes(ClassDescriptor cd){
441 return (Vector)cdtorootnodes.get(cd);