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 ClassDescriptor tmp=cd;
58 for(Iterator it_cflags=tmp.getFlags();it_cflags.hasNext();) {
59 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
62 tmp=tmp.getSuperDesc();
66 if (vFlags.size()!=0) {
67 flag=new FlagDescriptor[vFlags.size()];
69 for(int i=0;i < vFlags.size() ; i++) {
70 if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
71 flag[ctr]=(FlagDescriptor)vFlags.get(i);
72 vFlags.remove(flag[ctr]);
76 for(int i=0;i < vFlags.size() ; i++) {
77 flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
79 extern_flags.put(cd,new Integer(ctr));
85 /** Method which starts up the analysis
88 public void taskAnalysis() throws java.io.IOException {
89 flagstates=new Hashtable();
90 Hashtable<FlagState,FlagState> sourcenodes;
91 cdtorootnodes=new Hashtable();
93 getFlagsfromClasses();
96 toprocess=new LinkedList<FlagState>();
98 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
99 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
100 externs=((Integer)extern_flags.get(cd)).intValue();
101 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
102 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
103 cdtorootnodes.put(cd,new Vector());
107 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
109 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
110 FlagState fsstartup=new FlagState(startupobject);
113 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
115 fsstartup=fsstartup.setFlag(fd[0],true);
116 fsstartup.setAsSourceNode();
117 ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
119 sourcenodes.put(fsstartup,fsstartup);
120 toprocess.add(fsstartup);
122 /** Looping through the flagstates in the toprocess queue to
123 * perform the state analysis */
124 while (!toprocess.isEmpty()) {
125 FlagState trigger=toprocess.poll();
126 createPossibleRuntimeStates(trigger);
128 analyseTasks(trigger);
131 /** Creating DOT files */
132 Enumeration e=flagstates.keys();
134 while (e.hasMoreElements()) {
135 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
136 createDOTfile(cdtemp);
141 /** Analyses the set of tasks based on the given flagstate, checking
142 * to see which tasks are triggered and what new flagstates are created
143 * from the base flagstate.
144 * @param fs A FlagState object which is used to analyse the task
148 private void analyseTasks(FlagState fs) {
149 ClassDescriptor cd=fs.getClassDescriptor();
150 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
152 for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
153 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
154 String taskname=td.getSymbol();
156 /** counter to keep track of the number of parameters (of the
157 * task being analyzed) that are satisfied by the flagstate.
160 TempDescriptor temp=null;
161 FlatMethod fm = state.getMethodFlat(td);
162 int parameterindex=0;
164 for(int i=0; i < td.numParameters(); i++) {
165 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
166 TagExpressionList tel=td.getTag(td.getParameter(i));
168 /** Checking to see if the parameter is of the same
169 * type/class as the flagstate's and also if the
170 * flagstate fs triggers the given task*/
172 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
173 && isTaskTrigger_flag(fen,fs)
174 && isTaskTrigger_tag(tel,fs)) {
175 temp=fm.getParameter(i);
181 if (trigger_ctr==0) //Look at next task
185 System.out.println("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task:"+fs + " in "+td);
188 Set newstates=taganalysis.getFlagStates(td);
189 for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
190 FlagState fsnew=(FlagState) fsit.next();
191 System.out.println("SOURCE:"+fsnew);
193 if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
194 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
195 toprocess.add(fsnew);
197 fsnew=((Hashtable<FlagState, FlagState>)flagstates.get(fsnew.getClassDescriptor())).get(fsnew);
199 fsnew.setAsSourceNode();
200 fsnew.addAllocatingTask(td);
202 ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
205 Stack nodestack=new Stack();
206 HashSet discovered=new HashSet();
209 //Iterating through the nodes
211 while(!nodestack.isEmpty()) {
212 FlatNode fn1 = (FlatNode) nodestack.pop();
214 if (fn1.kind()==FKind.FlatReturnNode) {
216 FEdge newedge=new FEdge(fs, taskname, td, parameterindex);
219 } else if (fn1.kind()==FKind.FlatFlagActionNode) {
220 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
221 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
222 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
223 throw new Error("PRE FlagActions not supported");
225 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
226 Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
227 for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
228 FlagState fs_taskexit=(FlagState)en.nextElement();
229 if (!sourcenodes.containsKey(fs_taskexit)) {
230 toprocess.add(fs_taskexit);
232 //seen this node already
233 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
234 FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex);
240 /* Queue other nodes past this one */
241 for(int i=0;i<fn1.numNext();i++) {
242 FlatNode fnext=fn1.getNext(i);
243 if (!discovered.contains(fnext)) {
244 discovered.add(fnext);
245 nodestack.push(fnext);
253 /** Determines whether the given flagstate satisfies a
254 * single parameter in the given task.
255 * @param fen FlagExpressionNode
256 * @see FlagExpressionNode
257 * @param fs FlagState
259 * @return <CODE>true</CODE> if fs satisfies the boolean expression
260 denoted by fen else <CODE>false</CODE>.
264 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
267 else if (fen instanceof FlagNode)
268 return fs.get(((FlagNode)fen).getFlag());
270 switch (((FlagOpNode)fen).getOp().getOp()) {
271 case Operation.LOGIC_AND:
272 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
273 case Operation.LOGIC_OR:
274 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
275 case Operation.LOGIC_NOT:
276 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
282 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
285 for (int i=0;i<tel.numTags() ; i++){
286 switch (fs.getTagCount(tel.getType(i))){
287 case FlagState.ONETAG:
288 case FlagState.MULTITAGS:
290 case FlagState.NOTAGS:
299 private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
301 Vector<FlagState> processed=new Vector<FlagState>();
303 //Process the flag changes
305 for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
306 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
307 if (temp==tfp.getTemp())
308 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
311 //Process the tag changes
313 processed.add(fstemp);
315 //Process clears first
316 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
317 TempTagPair ttp=(TempTagPair)it_ttp.next();
319 if (temp==ttp.getTemp()) {
320 Vector<FlagState> oldprocess=processed;
321 processed=new Vector<FlagState>();
323 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
324 FlagState fsworking=(FlagState)en.nextElement();
325 if (!ffan.getTagChange(ttp)){
326 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
327 } else processed.add(fsworking);
332 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
333 TempTagPair ttp=(TempTagPair)it_ttp.next();
335 if (temp==ttp.getTemp()) {
336 Vector<FlagState> oldprocess=processed;
337 processed=new Vector<FlagState>();
339 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
340 FlagState fsworking=(FlagState)en.nextElement();
341 if (ffan.getTagChange(ttp)){
342 processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
343 } else processed.add(fsworking);
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_flagstates= new File("graph"+cd.getSymbol()+".dot");
368 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
369 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
372 /** Returns the flag states for the class descriptor. */
373 public Set<FlagState> getFlagStates(ClassDescriptor cd) {
374 if (flagstates.containsKey(cd))
375 return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
377 return new HashSet<FlagState>();
381 private void createPossibleRuntimeStates(FlagState fs) {
382 ClassDescriptor cd = fs.getClassDescriptor();
383 Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
384 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
385 int externs=((Integer)extern_flags.get(cd)).intValue();
390 int noOfIterations=(1<<externs) - 1;
391 boolean BoolValTable[]=new boolean[externs];
394 for(int i=0; i < externs ; i++) {
395 BoolValTable[i]=fs.get(fd[i]);
398 for(int k=0; k<noOfIterations; k++) {
399 for(int j=0; j < externs ;j++) {
400 if ((k% (1<<j)) == 0)
401 BoolValTable[j]=(!BoolValTable[j]);
406 for(int i=0; i < externs;i++) {
407 fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
409 if (!sourcenodes.containsKey(fstemp))
410 toprocess.add(fstemp);
412 fstemp=canonicalizeFlagState(sourcenodes,fstemp);
413 fs.addEdge(new FEdge(fstemp,"Runtime", null, -1));
417 public Vector getRootNodes(ClassDescriptor cd){
418 return (Vector)cdtorootnodes.get(cd);