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);
144 /** Creating DOT files */
145 Enumeration e=flagstates.keys();
147 while (e.hasMoreElements()) {
148 System.out.println("creating dot file");
149 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
150 System.out.println((cdtemp.getSymbol()));
151 createDOTfile(cdtemp);
156 /** Analyses the set of tasks based on the given flagstate, checking
157 * to see which tasks are triggered and what new flagstates are created
158 * from the base flagstate.
159 * @param fs A FlagState object which is used to analyse the task
163 private void analyseTasks(FlagState fs) {
164 ClassDescriptor cd=fs.getClassDescriptor();
165 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
167 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
168 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
169 String taskname=td.getSymbol();
172 System.out.println();
173 System.out.println(cd.getSymbol()+" : "+fs.getTextLabel());
174 System.out.println("Task: "+taskname);
177 /** counter to keep track of the number of parameters (of the task being analyzed) that
178 * are satisfied by the flagstate.
181 TempDescriptor temp=null;
182 FlatMethod fm = state.getMethodFlat(td);
184 for(int i=0; i < td.numParameters(); i++) {
185 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
186 TagExpressionList tel=td.getTag(td.getParameter(i));
188 /** Checking to see if the parameter is of the same type/class as the
189 * flagstate's and also if the flagstate fs triggers the given task*/
190 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
191 && isTaskTrigger_flag(fen,fs)
192 && isTaskTrigger_tag(tel,fs)) {
193 temp=fm.getParameter(i);
198 if (trigger_ctr==0) //Look at next task
202 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
206 System.out.println("Task:" + taskname +" is triggered");
209 Set newstates=taganalysis.getFlagStates(td);
210 for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
211 FlagState fsnew=(FlagState) fsit.next();
212 fsnew.setAsSourceNode();
213 fsnew.addAllocatingTask(td);
214 ((Vector)cdtorootnodes.get(cd)).add(fsnew);
216 if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
217 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
218 toprocess.add(fsnew);
222 Stack nodestack=new Stack();
223 HashSet discovered=new HashSet();
226 //Iterating through the nodes
228 while(!nodestack.isEmpty()) {
229 FlatNode fn1 = (FlatNode) nodestack.pop();
231 if (fn1.kind()==FKind.FlatReturnNode) {
233 FEdge newedge=new FEdge(fs, taskname);
236 } else if (fn1.kind()==FKind.FlatFlagActionNode) {
237 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
238 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
239 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
240 throw new Error("PRE FlagActions not supported");
242 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
244 System.out.println("TASKEXIT");
247 Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
249 for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
250 FlagState fs_taskexit=(FlagState)en.nextElement();
251 if (!sourcenodes.containsKey(fs_taskexit)) {
252 toprocess.add(fs_taskexit);
255 //seen this node already
256 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
257 FEdge newedge=new FEdge(fs_taskexit,taskname);
258 //FEdge newedge=new FEdge(fs_taskexit,td);
264 /* Queue other nodes past this one */
265 for(int i=0;i<fn1.numNext();i++) {
266 FlatNode fnext=fn1.getNext(i);
267 if (!discovered.contains(fnext)) {
268 discovered.add(fnext);
269 nodestack.push(fnext);
277 /** Determines whether the given flagstate satisfies a
278 * single parameter in the given task.
279 * @param fen FlagExpressionNode
280 * @see FlagExpressionNode
281 * @param fs FlagState
283 * @return <CODE>true</CODE> if fs satisfies the boolean expression
284 denoted by fen else <CODE>false</CODE>.
288 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
291 else if (fen instanceof FlagNode)
292 return fs.get(((FlagNode)fen).getFlag());
294 switch (((FlagOpNode)fen).getOp().getOp()) {
295 case Operation.LOGIC_AND:
296 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
297 case Operation.LOGIC_OR:
298 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
299 case Operation.LOGIC_NOT:
300 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
306 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
309 for (int i=0;i<tel.numTags() ; i++){
310 switch (fs.getTagCount(tel.getType(i))){
311 case FlagState.ONETAG:
312 case FlagState.MULTITAGS:
314 case FlagState.NOTAGS:
322 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
324 for(int i=0;i<tel.numTags() ; i++){
325 if (tel.getType(i).equals(tagtype))
331 /** Evaluates a NewObject Node and returns the newly created
332 * flagstate to add to the process queue.
339 private FlagState evalNewObjNode(FlatNode nn){
341 ClassDescriptor cd_new=((FlatNew)nn.getPrev(0)).getType().getClassDesc();
344 //TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
346 //if (tdArray.length==0)
349 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
350 //ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
352 FlagState fstemp=new FlagState(cd_new);
354 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
355 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
356 if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
358 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
364 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
365 TempTagPair ttp=(TempTagPair)it_ttp.next();
366 if (! (ttp.getTag()==null)){
367 fstemp=fstemp.setTag(ttp.getTag());
376 private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
378 //FlagState[] fstemparray=new FlagState[3];
379 Vector<FlagState> inprocess=new Vector<FlagState>();
380 Vector<FlagState> processed=new Vector<FlagState>();
382 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
383 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
384 if (temp==tfp.getTemp())
385 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
388 inprocess.add(fstemp);
389 processed.add(fstemp);
391 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
392 TempTagPair ttp=(TempTagPair)it_ttp.next();
394 if (temp==ttp.getTemp()){
395 processed=new Vector<FlagState>();
396 for (Enumeration en=inprocess.elements();en.hasMoreElements();){
397 FlagState fsworking=(FlagState)en.nextElement();
398 if (((FlatFlagActionNode)nn).getTagChange(ttp)){
399 fsworking=fsworking.setTag(ttp.getTag());
400 processed.add(fsworking);
404 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
415 private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
416 if (sourcenodes.containsKey(fs))
417 return (FlagState)sourcenodes.get(fs);
419 sourcenodes.put(fs,fs);
424 /** Creates a DOT file using the flagstates for a given class
425 * @param cd ClassDescriptor of the class
426 * @throws java.io.IOException
427 * @see ClassDescriptor
430 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
431 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
432 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
433 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
437 /** Returns the flag states for the class descriptor. */
438 public Set getFlagStates(ClassDescriptor cd) {
439 if (flagstates.containsKey(cd))
440 return ((Hashtable)flagstates.get(cd)).keySet();
446 private void createPossibleRuntimeStates(FlagState fs) {
447 ClassDescriptor cd = fs.getClassDescriptor();
448 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
449 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
450 int externs=((Integer)extern_flags.get(cd)).intValue();
455 int noOfIterations=(1<<externs) - 1;
456 boolean BoolValTable[]=new boolean[externs];
459 for(int i=0; i < externs ; i++) {
460 BoolValTable[i]=fs.get(fd[i]);
463 for(int k=0; k<noOfIterations; k++) {
464 for(int j=0; j < externs ;j++) {
465 if ((k% (1<<j)) == 0)
466 BoolValTable[j]=(!BoolValTable[j]);
471 for(int i=0; i < externs;i++) {
472 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
474 if (!sourcenodes.containsKey(fstemp))
475 toprocess.add(fstemp);
477 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
478 fs.addEdge(new FEdge(fstemp,"Runtime"));
482 public Vector getRootNodes(ClassDescriptor cd){
483 return (Vector)cdtorootnodes.get(cd);