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;
25 * @param state a flattened State object
28 public TaskAnalysis(State state, TagAnalysis taganalysis, TypeUtil typeutil) {
30 this.typeutil=typeutil;
31 this.taganalysis=taganalysis;
34 /** Builds a table of flags for each class in the Bristlecone
35 * program. It creates two hashtables: one which holds the
36 * ClassDescriptors and arrays of * FlagDescriptors as key-value
37 * pairs; the other holds the ClassDescriptor and the * number of
38 * 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
48 for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext(); ) {
50 ClassDescriptor cd = (ClassDescriptor)it_classes.next();
51 Vector vFlags=new Vector();
52 FlagDescriptor flag[];
56 /* Adding the flags of the super class */
57 ClassDescriptor tmp=cd;
59 for(Iterator it_cflags=tmp.getFlags(); it_cflags.hasNext(); ) {
60 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
63 tmp=tmp.getSuperDesc();
67 if (vFlags.size()!=0) {
68 flag=new FlagDescriptor[vFlags.size()];
70 for(int i=0; i < vFlags.size(); i++) {
71 if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
72 flag[ctr]=(FlagDescriptor)vFlags.get(i);
73 vFlags.remove(flag[ctr]);
77 for(int i=0; i < vFlags.size(); i++) {
78 flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
80 extern_flags.put(cd,new Integer(ctr));
86 /** Method which starts up the analysis
89 public void taskAnalysis() throws java.io.IOException {
90 flagstates=new Hashtable();
91 Hashtable<FlagState,FlagState> sourcenodes;
92 cdtorootnodes=new Hashtable();
93 tdToFEdges=new Hashtable();
95 getFlagsfromClasses();
98 toprocess=new LinkedList<FlagState>();
100 for(Iterator it_classes=(Iterator)flags.keys(); it_classes.hasNext(); ) {
101 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
102 externs=((Integer)extern_flags.get(cd)).intValue();
103 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
104 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
105 cdtorootnodes.put(cd,new Vector());
109 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
111 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
112 FlagState fsstartup=new FlagState(startupobject);
115 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
117 fsstartup=fsstartup.setFlag(fd[0],true);
118 fsstartup.setAsSourceNode();
119 ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
121 sourcenodes.put(fsstartup,fsstartup);
122 toprocess.add(fsstartup);
124 /** Looping through the flagstates in the toprocess queue to
125 * perform the state analysis */
126 while (!toprocess.isEmpty()) {
127 FlagState trigger=toprocess.poll();
128 createPossibleRuntimeStates(trigger);
130 analyseTasks(trigger);
133 /** Creating DOT files */
134 Enumeration e=flagstates.keys();
136 while (e.hasMoreElements()) {
137 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
138 createDOTfile(cdtemp);
143 /** Analyses the set of tasks based on the given flagstate, checking
144 * to see which tasks are triggered and what new flagstates are created
145 * from the base flagstate.
146 * @param fs A FlagState object which is used to analyse the task
150 private void analyseTasks(FlagState fs) {
151 ClassDescriptor cd=fs.getClassDescriptor();
152 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
154 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator(); it_tasks.hasNext(); ) {
155 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
156 String taskname=td.getSymbol();
158 if(!tdToFEdges.containsKey(td)) {
159 tdToFEdges.put(td, new Vector<FEdge>());
162 /** counter to keep track of the number of parameters (of the
163 * task being analyzed) that are satisfied by the flagstate.
166 TempDescriptor temp=null;
167 FlatMethod fm = state.getMethodFlat(td);
168 int parameterindex=0;
170 for(int i=0; i < td.numParameters(); i++) {
171 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
172 TagExpressionList tel=td.getTag(td.getParameter(i));
174 /** Checking to see if the parameter is of the same
175 * type/class as the flagstate's and also if the
176 * 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);
187 if (trigger_ctr==0) //Look at next task
191 System.out.println("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task:"+fs + " in "+td);
194 Set newstates=taganalysis.getFlagStates(td);
195 for(Iterator fsit=newstates.iterator(); fsit.hasNext(); ) {
196 FlagState fsnew=(FlagState) fsit.next();
197 System.out.println("SOURCE:"+fsnew);
199 if (!((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
200 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
201 toprocess.add(fsnew);
203 fsnew=((Hashtable<FlagState, FlagState>)flagstates.get(fsnew.getClassDescriptor())).get(fsnew);
205 fsnew.setAsSourceNode();
206 fsnew.addAllocatingTask(td);
208 if(!((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).contains(fsnew)) {
209 ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
213 Stack nodestack=new Stack();
214 HashSet discovered=new HashSet();
217 //Iterating through the nodes
219 while(!nodestack.isEmpty()) {
220 FlatNode fn1 = (FlatNode) nodestack.pop();
222 if (fn1.kind()==FKind.FlatReturnNode) {
224 FEdge newedge=new FEdge(fs, taskname, td, parameterindex);
225 ((Vector<FEdge>)tdToFEdges.get(td)).add(newedge);
227 newedge.setisbackedge(true);
229 } else if (fn1.kind()==FKind.FlatFlagActionNode) {
230 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
231 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
232 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
233 throw new Error("PRE FlagActions not supported");
235 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
236 Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
237 Vector<FlagState> initFStates = ffan.getInitFStates(temp.getType().getClassDesc());
238 if(!initFStates.contains(fs)) {
239 initFStates.addElement(fs);
241 Vector<FlagState> targetFStates = ffan.getTargetFStates(fs);
242 for(Enumeration en=fsv_taskexit.elements(); en.hasMoreElements(); ) {
243 FlagState fs_taskexit=(FlagState)en.nextElement();
244 if (!sourcenodes.containsKey(fs_taskexit)) {
245 toprocess.add(fs_taskexit);
247 //seen this node already
248 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
249 FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex);
250 newedge.setTaskExitIndex(ffan.getTaskExitIndex());
251 ((Vector<FEdge>)tdToFEdges.get(td)).add(newedge);
254 if(!targetFStates.contains(fs_taskexit)) {
255 targetFStates.addElement(fs_taskexit);
261 /* Queue other nodes past this one */
262 for(int i=0; i<fn1.numNext(); i++) {
263 FlatNode fnext=fn1.getNext(i);
264 if (!discovered.contains(fnext)) {
265 discovered.add(fnext);
266 nodestack.push(fnext);
274 /** Determines whether the given flagstate satisfies a
275 * single parameter in the given task.
276 * @param fen FlagExpressionNode
277 * @see FlagExpressionNode
278 * @param fs FlagState
280 * @return <CODE>true</CODE> if fs satisfies the boolean expression
281 denoted by fen else <CODE>false</CODE>.
285 public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
288 else if (fen instanceof FlagNode)
289 return fs.get(((FlagNode)fen).getFlag());
291 switch (((FlagOpNode)fen).getOp().getOp()) {
292 case Operation.LOGIC_AND:
293 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
295 case Operation.LOGIC_OR:
296 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
298 case Operation.LOGIC_NOT:
299 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:
315 case FlagState.NOTAGS:
324 private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp) {
326 Vector<FlagState> processed=new Vector<FlagState>();
328 //Process the flag changes
330 for(Iterator it_tfp=ffan.getTempFlagPairs(); it_tfp.hasNext(); ) {
331 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
332 if (temp==tfp.getTemp())
333 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
336 //Process the tag changes
338 processed.add(fstemp);
340 //Process clears first
341 for(Iterator it_ttp=ffan.getTempTagPairs(); it_ttp.hasNext(); ) {
342 TempTagPair ttp=(TempTagPair)it_ttp.next();
344 if (temp==ttp.getTemp()) {
345 Vector<FlagState> oldprocess=processed;
346 processed=new Vector<FlagState>();
348 for (Enumeration en=oldprocess.elements(); en.hasMoreElements(); ) {
349 FlagState fsworking=(FlagState)en.nextElement();
350 if (!ffan.getTagChange(ttp)) {
351 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
352 } else processed.add(fsworking);
357 for(Iterator it_ttp=ffan.getTempTagPairs(); it_ttp.hasNext(); ) {
358 TempTagPair ttp=(TempTagPair)it_ttp.next();
360 if (temp==ttp.getTemp()) {
361 Vector<FlagState> oldprocess=processed;
362 processed=new Vector<FlagState>();
364 for (Enumeration en=oldprocess.elements(); en.hasMoreElements(); ) {
365 FlagState fsworking=(FlagState)en.nextElement();
366 if (ffan.getTagChange(ttp)) {
367 processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
368 } else processed.add(fsworking);
376 private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs) {
377 if (sourcenodes.containsKey(fs))
378 return (FlagState)sourcenodes.get(fs);
380 sourcenodes.put(fs,fs);
385 /** Creates a DOT file using the flagstates for a given class
386 * @param cd ClassDescriptor of the class
387 * @throws java.io.IOException
388 * @see ClassDescriptor
391 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
392 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
393 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
394 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
397 /** Returns the flag states for the class descriptor. */
398 public Set<FlagState> getFlagStates(ClassDescriptor cd) {
399 if (flagstates.containsKey(cd))
400 return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
402 return new HashSet<FlagState>();
406 private void createPossibleRuntimeStates(FlagState fs) {
407 ClassDescriptor cd = fs.getClassDescriptor();
408 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
409 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
410 int externs=((Integer)extern_flags.get(cd)).intValue();
415 int noOfIterations=(1<<externs) - 1;
416 boolean BoolValTable[]=new boolean[externs];
419 for(int i=0; i < externs; i++) {
420 BoolValTable[i]=fs.get(fd[i]);
423 for(int k=0; k<noOfIterations; k++) {
424 for(int j=0; j < externs; j++) {
425 if ((k% (1<<j)) == 0)
426 BoolValTable[j]=(!BoolValTable[j]);
431 for(int i=0; i < externs; i++) {
432 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
434 if (!sourcenodes.containsKey(fstemp))
435 toprocess.add(fstemp);
437 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
438 fs.addEdge(new FEdge(fstemp,"Runtime", null, -1));
442 public Vector getRootNodes(ClassDescriptor cd) {
443 return (Vector)cdtorootnodes.get(cd);
446 public Vector<FEdge> getFEdgesFromTD(TaskDescriptor td) {
447 return (Vector<FEdge>)tdToFEdges.get(td);