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 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
93 public void taskAnalysis() throws java.io.IOException {
94 flagstates=new Hashtable();
95 Hashtable<FlagState,FlagState> sourcenodes;
96 cdtorootnodes=new Hashtable();
98 getFlagsfromClasses();
101 toprocess=new LinkedList<FlagState>();
103 for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
104 ClassDescriptor cd=(ClassDescriptor)it_classes.next();
105 externs=((Integer)extern_flags.get(cd)).intValue();
106 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
107 flagstates.put(cd,new Hashtable<FlagState,FlagState>());
108 cdtorootnodes.put(cd,new Vector());
112 ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
114 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
115 FlagState fsstartup=new FlagState(startupobject);
118 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
120 fsstartup=fsstartup.setFlag(fd[0],true);
121 fsstartup.setAsSourceNode();
122 ((Vector)cdtorootnodes.get(startupobject)).add(fsstartup);
124 sourcenodes.put(fsstartup,fsstartup);
125 toprocess.add(fsstartup);
127 /** Looping through the flagstates in the toprocess queue to 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 task being analyzed) that
161 * are satisfied by the flagstate.
164 TempDescriptor temp=null;
165 FlatMethod fm = state.getMethodFlat(td);
167 for(int i=0; i < td.numParameters(); i++) {
168 FlagExpressionNode fen=td.getFlag(td.getParameter(i));
169 TagExpressionList tel=td.getTag(td.getParameter(i));
171 /** Checking to see if the parameter is of the same type/class as the
172 * flagstate's and also if the flagstate fs triggers the given task*/
173 if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
174 && isTaskTrigger_flag(fen,fs)
175 && isTaskTrigger_tag(tel,fs)) {
176 temp=fm.getParameter(i);
181 if (trigger_ctr==0) //Look at next task
185 throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
188 Set newstates=taganalysis.getFlagStates(td);
189 for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
190 FlagState fsnew=(FlagState) fsit.next();
191 fsnew.setAsSourceNode();
192 fsnew.addAllocatingTask(td);
193 ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
195 if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
196 ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
197 toprocess.add(fsnew);
201 Stack nodestack=new Stack();
202 HashSet discovered=new HashSet();
205 //Iterating through the nodes
207 while(!nodestack.isEmpty()) {
208 FlatNode fn1 = (FlatNode) nodestack.pop();
210 if (fn1.kind()==FKind.FlatReturnNode) {
212 FEdge newedge=new FEdge(fs, taskname);
215 } else if (fn1.kind()==FKind.FlatFlagActionNode) {
216 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
217 if (ffan.getTaskType() == FlatFlagActionNode.PRE) {
218 if (ffan.getTempFlagPairs().hasNext()||ffan.getTempTagPairs().hasNext())
219 throw new Error("PRE FlagActions not supported");
221 } else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
222 Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
223 for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
224 FlagState fs_taskexit=(FlagState)en.nextElement();
225 if (!sourcenodes.containsKey(fs_taskexit)) {
226 toprocess.add(fs_taskexit);
228 //seen this node already
229 fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
230 FEdge newedge=new FEdge(fs_taskexit,taskname);
236 /* Queue other nodes past this one */
237 for(int i=0;i<fn1.numNext();i++) {
238 FlatNode fnext=fn1.getNext(i);
239 if (!discovered.contains(fnext)) {
240 discovered.add(fnext);
241 nodestack.push(fnext);
249 /** Determines whether the given flagstate satisfies a
250 * single parameter in the given task.
251 * @param fen FlagExpressionNode
252 * @see FlagExpressionNode
253 * @param fs FlagState
255 * @return <CODE>true</CODE> if fs satisfies the boolean expression
256 denoted by fen else <CODE>false</CODE>.
260 private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
263 else if (fen instanceof FlagNode)
264 return fs.get(((FlagNode)fen).getFlag());
266 switch (((FlagOpNode)fen).getOp().getOp()) {
267 case Operation.LOGIC_AND:
268 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
269 case Operation.LOGIC_OR:
270 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
271 case Operation.LOGIC_NOT:
272 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
278 private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
281 for (int i=0;i<tel.numTags() ; i++){
282 switch (fs.getTagCount(tel.getType(i))){
283 case FlagState.ONETAG:
284 case FlagState.MULTITAGS:
286 case FlagState.NOTAGS:
294 /*private int tagTypeCount(TagExpressionList tel, String tagtype){
296 for(int i=0;i<tel.numTags() ; i++){
297 if (tel.getType(i).equals(tagtype))
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,true);
373 FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
376 /** Returns the flag states for the class descriptor. */
377 public Set getFlagStates(ClassDescriptor cd) {
378 if (flagstates.containsKey(cd))
379 return ((Hashtable)flagstates.get(cd)).keySet();
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"));
421 public Vector getRootNodes(ClassDescriptor cd){
422 return (Vector)cdtorootnodes.get(cd);