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) {
29 this.typeutil=new TypeUtil(state);
30 this.taganalysis=taganalysis;
33 /** Builds a table of flags for each class in the Bristlecone
34 * program. It creates two hashtables: one which holds the
35 * ClassDescriptors and arrays of * FlagDescriptors as key-value
36 * pairs; the other holds the ClassDescriptor and the * number of
37 * external flags for that specific class.
40 private void getFlagsfromClasses() {
41 flags=new Hashtable();
42 extern_flags = new Hashtable();
44 /** Iterate through the classes used in the program to build
47 for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
49 ClassDescriptor cd = (ClassDescriptor)it_classes.next();
50 Vector vFlags=new Vector();
51 FlagDescriptor flag[];
55 /* Adding the flags of the super class */
56 if (cd.getSuper()!=null) {
57 ClassDescriptor superdesc=cd.getSuperDesc();
59 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
60 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
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
92 public void taskAnalysis() throws java.io.IOException {
93 flagstates=new Hashtable();
94 Hashtable<FlagState,FlagState> sourcenodes;
95 cdtorootnodes=new Hashtable();
97 getFlagsfromClasses();
100 toprocess=new LinkedList<FlagState>();
102 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
103 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
104 externs=((Integer)extern_flags.get(cd)).intValue();
105 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
106 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
107 cdtorootnodes.put(cd,new Vector());
111 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
113 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
114 FlagState fsstartup=new FlagState(startupobject);
117 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
119 fsstartup=fsstartup.setFlag(fd[0],true);
120 fsstartup.setAsSourceNode();
121 ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
123 sourcenodes.put(fsstartup,fsstartup);
124 toprocess.add(fsstartup);
126 /** Looping through the flagstates in the toprocess queue to
127 * perform the state analysis */
128 while (!toprocess.isEmpty()) {
129 FlagState trigger=toprocess.poll();
130 createPossibleRuntimeStates(trigger);
132 analyseTasks(trigger);
135 /** Creating DOT files */
136 Enumeration e=flagstates.keys();
138 while (e.hasMoreElements()) {
139 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
140 createDOTfile(cdtemp);
145 /** Analyses the set of tasks based on the given flagstate, checking
146 * to see which tasks are triggered and what new flagstates are created
147 * from the base flagstate.
148 * @param fs A FlagState object which is used to analyse the task
152 private void analyseTasks(FlagState fs) {
153 ClassDescriptor cd=fs.getClassDescriptor();
154 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
156 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
157 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
158 String taskname=td.getSymbol();
160 /** counter to keep track of the number of parameters (of the
161 * task being analyzed) that are satisfied by the flagstate.
164 TempDescriptor temp=null;
165 FlatMethod fm = state.getMethodFlat(td);
166 int parameterindex=0;
168 for(int i=0; i < td.numParameters(); i++) {
169 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
170 TagExpressionList tel=td.getTag(td.getParameter(i));
172 /** Checking to see if the parameter is of the same
173 * type/class as the flagstate's and also if the
174 * flagstate fs triggers the given task*/
176 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
177 && isTaskTrigger_flag(fen,fs)
178 && isTaskTrigger_tag(tel,fs)) {
179 temp=fm.getParameter(i);
185 if (trigger_ctr==0) //Look at next task
189 System.out.println("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task:"+fs + " in "+td);
192 Set newstates=taganalysis.getFlagStates(td);
193 for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
194 FlagState fsnew=(FlagState) fsit.next();
195 System.out.println("SOURCE:"+fsnew);
197 if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
198 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
199 toprocess.add(fsnew);
201 fsnew=((Hashtable<FlagState, FlagState>)flagstates.get(fsnew.getClassDescriptor())).get(fsnew);
203 fsnew.setAsSourceNode();
204 fsnew.addAllocatingTask(td);
206 ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
209 Stack nodestack=new Stack();
210 HashSet discovered=new HashSet();
213 //Iterating through the nodes
215 while(!nodestack.isEmpty()) {
216 FlatNode fn1 = (FlatNode) nodestack.pop();
218 if (fn1.kind()==FKind.FlatReturnNode) {
220 FEdge newedge=new FEdge(fs, taskname, td, parameterindex);
223 } else if (fn1.kind()==FKind.FlatFlagActionNode) {
224 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
225 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
226 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
227 throw new Error("PRE FlagActions not supported");
229 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
230 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);
236 //seen this node already
237 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
238 FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex);
244 /* Queue other nodes past this one */
245 for(int i=0;i<fn1.numNext();i++) {
246 FlatNode fnext=fn1.getNext(i);
247 if (!discovered.contains(fnext)) {
248 discovered.add(fnext);
249 nodestack.push(fnext);
257 /** Determines whether the given flagstate satisfies a
258 * single parameter in the given task.
259 * @param fen FlagExpressionNode
260 * @see FlagExpressionNode
261 * @param fs FlagState
263 * @return <CODE>true</CODE> if fs satisfies the boolean expression
264 denoted by fen else <CODE>false</CODE>.
268 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
271 else if (fen instanceof FlagNode)
272 return fs.get(((FlagNode)fen).getFlag());
274 switch (((FlagOpNode)fen).getOp().getOp()) {
275 case Operation.LOGIC_AND:
276 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
277 case Operation.LOGIC_OR:
278 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
279 case Operation.LOGIC_NOT:
280 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
286 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
289 for (int i=0;i<tel.numTags() ; i++){
290 switch (fs.getTagCount(tel.getType(i))){
291 case FlagState.ONETAG:
292 case FlagState.MULTITAGS:
294 case FlagState.NOTAGS:
303 private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
305 Vector<FlagState> processed=new Vector<FlagState>();
307 //Process the flag changes
309 for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
310 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
311 if (temp==tfp.getTemp())
312 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
315 //Process the tag changes
317 processed.add(fstemp);
319 //Process clears first
320 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
321 TempTagPair ttp=(TempTagPair)it_ttp.next();
323 if (temp==ttp.getTemp()) {
324 Vector<FlagState> oldprocess=processed;
325 processed=new Vector<FlagState>();
327 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
328 FlagState fsworking=(FlagState)en.nextElement();
329 if (!ffan.getTagChange(ttp)){
330 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
331 } else processed.add(fsworking);
336 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
337 TempTagPair ttp=(TempTagPair)it_ttp.next();
339 if (temp==ttp.getTemp()) {
340 Vector<FlagState> oldprocess=processed;
341 processed=new Vector<FlagState>();
343 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
344 FlagState fsworking=(FlagState)en.nextElement();
345 if (ffan.getTagChange(ttp)){
346 processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
347 } else processed.add(fsworking);
355 private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
356 if (sourcenodes.containsKey(fs))
357 return (FlagState)sourcenodes.get(fs);
359 sourcenodes.put(fs,fs);
364 /** Creates a DOT file using the flagstates for a given class
365 * @param cd ClassDescriptor of the class
366 * @throws java.io.IOException
367 * @see ClassDescriptor
370 public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
371 File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
372 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
373 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
376 /** Returns the flag states for the class descriptor. */
377 public Set<FlagState> getFlagStates(ClassDescriptor cd) {
378 if (flagstates.containsKey(cd))
379 return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
381 return new HashSet<FlagState>();
385 private void createPossibleRuntimeStates(FlagState fs) {
386 ClassDescriptor cd = fs.getClassDescriptor();
387 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
388 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
389 int externs=((Integer)extern_flags.get(cd)).intValue();
394 int noOfIterations=(1<<externs) - 1;
395 boolean BoolValTable[]=new boolean[externs];
398 for(int i=0; i < externs ; i++) {
399 BoolValTable[i]=fs.get(fd[i]);
402 for(int k=0; k<noOfIterations; k++) {
403 for(int j=0; j < externs ;j++) {
404 if ((k% (1<<j)) == 0)
405 BoolValTable[j]=(!BoolValTable[j]);
410 for(int i=0; i < externs;i++) {
411 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
413 if (!sourcenodes.containsKey(fstemp))
414 toprocess.add(fstemp);
416 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
417 fs.addEdge(new FEdge(fstemp,"Runtime", null, -1));
421 public Vector getRootNodes(ClassDescriptor cd){
422 return (Vector)cdtorootnodes.get(cd);