1 package Analysis.TaskStateAnalysis;
2 import Analysis.TaskStateAnalysis.*;
8 import java.io.FileWriter;
9 import java.io.FileOutputStream;
15 public class TaskAnalysis {
19 Hashtable extern_flags;
20 Queue<FlagState> toprocess;
26 * @param state a flattened State object
29 public TaskAnalysis(State state)
32 this.typeutil=new TypeUtil(state);
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;
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>());
120 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
122 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
124 FlagState fsstartup=new FlagState(startupobject);
125 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
127 fsstartup=fsstartup.setFlag(fd[0],true);
129 sourcenodes.put(fsstartup,fsstartup);
130 toprocess.add(fsstartup);
132 /** Looping through the flagstates in the toprocess queue to perform the state analysis */
133 while (!toprocess.isEmpty()) {
134 FlagState trigger=toprocess.poll();
135 createPossibleRuntimeStates(trigger);
136 analyseTasks(trigger);
139 /** Creating DOT files */
140 Enumeration e=flagstates.keys();
142 while (e.hasMoreElements()) {
143 System.out.println("creating dot file");
144 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
145 System.out.println((cdtemp.getSymbol()));
146 createDOTfile(cdtemp);
151 /** Analyses the set of tasks based on the given flagstate, checking
152 * to see which tasks are triggered and what new flagstates are created
153 * from the base flagstate.
154 * @param fs A FlagState object which is used to analyse the task
158 private void analyseTasks(FlagState fs) {
159 ClassDescriptor cd=fs.getClassDescriptor();
160 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
162 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
163 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
164 String taskname=td.getSymbol();
165 /** counter to keep track of the number of parameters (of the task being analyzed) that
166 * are satisfied by the flagstate.
169 TempDescriptor temp=null;
170 FlatMethod fm = state.getMethodFlat(td);
172 for(int i=0; i < td.numParameters(); i++) {
173 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
174 TagExpressionList tel=td.getTag(td.getParameter(i));
176 /** Checking to see if the parameter is of the same type/class as the
177 * flagstate's and also if the flagstate fs triggers the given task*/
178 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
179 && isTaskTrigger_flag(fen,fs)
180 && isTaskTrigger_tag(tel,fs)) {
181 temp=fm.getParameter(i);
186 if (trigger_ctr==0) //Look at next task
190 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
192 //Iterating through the nodes
193 FlatNode fn=fm.methodEntryNode();
195 HashSet tovisit= new HashSet();
196 HashSet visited= new HashSet();
199 while(!tovisit.isEmpty()) {
200 FlatNode fn1 = (FlatNode)tovisit.iterator().next();
203 // Queue all of the next nodes
204 for(int i = 0; i < fn1.numNext(); i++) {
205 FlatNode nn=fn1.getNext(i);
206 if (!visited.contains(nn))
209 if (fn1.kind()==FKind.FlatFlagActionNode) {
210 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
211 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
212 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
213 throw new Error("PRE FlagActions not supported");
214 } else if (ffan.getTaskType() == FlatFlagActionNode.NEWOBJECT) {
215 FlagState fsnew=evalNewObjNode(ffan);
216 //Have we seen this node yet
217 if (!sourcenodes.containsKey(fsnew)) {
218 sourcenodes.put(fsnew, fsnew);
219 toprocess.add(fsnew);
221 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
222 FlagState fs_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
223 if (!sourcenodes.containsKey(fs_taskexit)) {
224 toprocess.add(fs_taskexit);
226 //seen this node already
227 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
228 Edge newedge=new Edge(fs_taskexit,taskname);
236 /** Determines whether the given flagstate satisfies a
237 * single parameter in the given task.
238 * @param fen FlagExpressionNode
239 * @see FlagExpressionNode
240 * @param fs FlagState
242 * @return <CODE>true</CODE> if fs satisfies the boolean expression
243 denoted by fen else <CODE>false</CODE>.
247 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
248 if (fen instanceof FlagNode)
249 return fs.get(((FlagNode)fen).getFlag());
251 switch (((FlagOpNode)fen).getOp().getOp()) {
252 case Operation.LOGIC_AND:
253 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
254 case Operation.LOGIC_OR:
255 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
256 case Operation.LOGIC_NOT:
257 return !(isTaskTrigger(((FlagOpNode)fen).getLeft(),fs));
263 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
266 for (int i=0;i<tel.numTags() ; i++){
267 switch (fs.getTagCount(tel.getType(i))){
268 case FlagState.ONETAG:
269 case FlagState.MULTITAG:
272 case FlagState.NOTAG:
280 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
282 for(int i=0;i<tel.numTags() ; i++){
283 if (tel.getType(i).equals(tagtype))
289 /** Evaluates a NewObject Node and returns the newly created
290 * flagstate to add to the process queue.
297 private FlagState evalNewObjNode(FlatNode nn){
298 TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
300 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
301 ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
303 FlagState fstemp=new FlagState(cd_new);
305 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
306 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
307 if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
309 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
315 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
316 TempTagPair ttp=(TempTagPair)it_ttp.next();
317 if (! (ttp.getTag()==null)){
318 fstemp=fstemp.setTag(ttp.getTag());
325 private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
327 //FlagState[] fstemparray=new FlagState[3];
328 Vector<FlagState> fsv=new Vector<FlagState>();
331 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
332 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
333 if (temp==tfp.getTemp())
334 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
337 for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
338 TempTagPair ttp=(TempTagPair)it_ttp.next();
339 if (temp==ttp.getTemp()){
340 if (((FlatFlagActionNode)nn).getTagChange(ttp)){
341 fstemp=fstemp.setTag(ttp.getTag());
351 private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
352 if (sourcenodes.containsKey(fs))
353 return (FlagState)sourcenodes.get(fs);
355 sourcenodes.put(fs,fs);
360 /** Creates a DOT file using the flagstates for a given class
361 * @param cd ClassDescriptor of the class
362 * @throws java.io.IOException
363 * @see ClassDescriptor
366 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
367 File dotfile= new File("graph"+cd.getSymbol()+".dot");
368 FileOutputStream dotstream=new FileOutputStream(dotfile,true);
369 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
373 private String getTaskName(TaskDescriptor td) {
374 StringTokenizer st = new StringTokenizer(td.toString(),"(");
375 return st.nextToken();
378 private void createPossibleRuntimeStates(FlagState fs) {
379 ClassDescriptor cd = fs.getClassDescriptor();
380 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
381 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
382 int externs=((Integer)extern_flags.get(cd)).intValue();
386 int noOfIterations=(1<<externs) - 1;
387 boolean BoolValTable[]=new boolean[externs];
390 for(int i=0; i < externs ; i++) {
391 BoolValTable[i]=fs.get(fd[i]);
394 for(int k=0; k<noOfIterations; k++) {
395 for(int j=0; j < externs ;j++) {
396 if ((k% (1<<j)) == 0)
397 BoolValTable[j]=(!BoolValTable[j]);
402 for(int i=0; i < externs;i++) {
403 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
405 if (!sourcenodes.containsKey(fstemp))
406 toprocess.add(fstemp);
408 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
409 fs.addEdge(new Edge(fstemp,"Runtime"));