Queue<FlagState> toprocess;
TagAnalysis taganalysis;
Hashtable cdtorootnodes;
+ Hashtable tdToFEdges;
TypeUtil typeutil;
* @param state a flattened State object
* @see State
*/
- public TaskAnalysis(State state, TagAnalysis taganalysis)
- {
+ public TaskAnalysis(State state, TagAnalysis taganalysis) {
this.state=state;
this.typeutil=new TypeUtil(state);
this.taganalysis=taganalysis;
-
}
- /** Builds a table of flags for each class in the Bristlecone program.
- * It creates two hashtables: one which holds the ClassDescriptors and arrays of
- * FlagDescriptors as key-value pairs; the other holds the ClassDescriptor and the
- * number of external flags for that specific class.
+ /** Builds a table of flags for each class in the Bristlecone
+ * program. It creates two hashtables: one which holds the
+ * ClassDescriptors and arrays of * FlagDescriptors as key-value
+ * pairs; the other holds the ClassDescriptor and the * number of
+ * external flags for that specific class.
*/
private void getFlagsfromClasses() {
flags=new Hashtable();
extern_flags = new Hashtable();
- /** Iterate through the classes used in the program to build the table of flags
+ /** Iterate through the classes used in the program to build
+ * the table of flags
*/
for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
ClassDescriptor cd = (ClassDescriptor)it_classes.next();
- System.out.println(cd.getSymbol());
Vector vFlags=new Vector();
FlagDescriptor flag[];
int ctr=0;
/* Adding the flags of the super class */
- if (cd.getSuper()!=null) {
- ClassDescriptor superdesc=cd.getSuperDesc();
-
- for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
+ ClassDescriptor tmp=cd;
+ while(tmp!=null) {
+ for(Iterator it_cflags=tmp.getFlags();it_cflags.hasNext();) {
FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
- System.out.println(fd.toString());
vFlags.add(fd);
}
+ tmp=tmp.getSuperDesc();
}
- for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
- FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
- vFlags.add(fd);
- }
if (vFlags.size()!=0) {
flag=new FlagDescriptor[vFlags.size()];
}
}
}
- /** Method which starts up the analysis
- *
+ /** Method which starts up the analysis
*/
public void taskAnalysis() throws java.io.IOException {
flagstates=new Hashtable();
Hashtable<FlagState,FlagState> sourcenodes;
cdtorootnodes=new Hashtable();
+ tdToFEdges=new Hashtable();
getFlagsfromClasses();
ClassDescriptor cd=(ClassDescriptor)it_classes.next();
externs=((Integer)extern_flags.get(cd)).intValue();
FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
-
- //Debug block
- System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
- System.out.println("No of externs " + externs);
- System.out.println("No of flags: "+fd.length);
- //Debug block
-
flagstates.put(cd,new Hashtable<FlagState,FlagState>());
cdtorootnodes.put(cd,new Vector());
}
sourcenodes.put(fsstartup,fsstartup);
toprocess.add(fsstartup);
- /** Looping through the flagstates in the toprocess queue to perform the state analysis */
+ /** Looping through the flagstates in the toprocess queue to
+ * perform the state analysis */
while (!toprocess.isEmpty()) {
FlagState trigger=toprocess.poll();
createPossibleRuntimeStates(trigger);
Enumeration e=flagstates.keys();
while (e.hasMoreElements()) {
- System.out.println("creating dot file");
ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
- System.out.println((cdtemp.getSymbol()));
createDOTfile(cdtemp);
}
}
TaskDescriptor td = (TaskDescriptor)it_tasks.next();
String taskname=td.getSymbol();
- //**Debug***/
- System.out.println();
- System.out.println(cd.getSymbol()+" : "+fs.getTextLabel());
- System.out.println("Task: "+taskname);
- //***********
-
- /** counter to keep track of the number of parameters (of the task being analyzed) that
- * are satisfied by the flagstate.
+ if(!tdToFEdges.containsKey(td)) {
+ tdToFEdges.put(td, new Vector<FEdge>());
+ }
+
+ /** counter to keep track of the number of parameters (of the
+ * task being analyzed) that are satisfied by the flagstate.
*/
int trigger_ctr=0;
TempDescriptor temp=null;
FlatMethod fm = state.getMethodFlat(td);
-
+ int parameterindex=0;
+
for(int i=0; i < td.numParameters(); i++) {
FlagExpressionNode fen=td.getFlag(td.getParameter(i));
TagExpressionList tel=td.getTag(td.getParameter(i));
- /** Checking to see if the parameter is of the same type/class as the
- * flagstate's and also if the flagstate fs triggers the given task*/
+ /** Checking to see if the parameter is of the same
+ * type/class as the flagstate's and also if the
+ * flagstate fs triggers the given task*/
+
if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd)
&& isTaskTrigger_flag(fen,fs)
&& isTaskTrigger_tag(tel,fs)) {
temp=fm.getParameter(i);
+ parameterindex=i;
trigger_ctr++;
}
}
continue;
if (trigger_ctr>1)
- throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
-
-
- //** debug
- System.out.println("Task:" + taskname +" is triggered");
+ System.out.println("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task:"+fs + " in "+td);
Set newstates=taganalysis.getFlagStates(td);
for(Iterator fsit=newstates.iterator();fsit.hasNext();) {
FlagState fsnew=(FlagState) fsit.next();
- fsnew.setAsSourceNode();
- fsnew.addAllocatingTask(td);
- ((Vector)cdtorootnodes.get(cd)).add(fsnew);
+ System.out.println("SOURCE:"+fsnew);
if (! ((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).containsKey(fsnew)) {
((Hashtable<FlagState,FlagState>)flagstates.get(fsnew.getClassDescriptor())).put(fsnew, fsnew);
toprocess.add(fsnew);
+ } else {
+ fsnew=((Hashtable<FlagState, FlagState>)flagstates.get(fsnew.getClassDescriptor())).get(fsnew);
+ }
+ fsnew.setAsSourceNode();
+ fsnew.addAllocatingTask(td);
+
+ if(!((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).contains(fsnew)) {
+ ((Vector)cdtorootnodes.get(fsnew.getClassDescriptor())).add(fsnew);
}
}
if (fn1.kind()==FKind.FlatReturnNode) {
/* Self edge */
- FEdge newedge=new FEdge(fs, taskname);
+ FEdge newedge=new FEdge(fs, taskname, td, parameterindex);
+ ((Vector<FEdge>)tdToFEdges.get(td)).add(newedge);
fs.addEdge(newedge);
continue;
} else if (fn1.kind()==FKind.FlatFlagActionNode) {
throw new Error("PRE FlagActions not supported");
} else if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
- //***
- System.out.println("TASKEXIT");
- //***
-
Vector<FlagState> fsv_taskexit=evalTaskExitNode(ffan,cd,fs,temp);
-
+ Vector<FlagState> initFStates = ffan.getInitFStates(temp.getType().getClassDesc());
+ if(!initFStates.contains(fs)) {
+ initFStates.addElement(fs);
+ }
+ Vector<FlagState> targetFStates = ffan.getTargetFStates(fs);
for(Enumeration en=fsv_taskexit.elements();en.hasMoreElements();){
FlagState fs_taskexit=(FlagState)en.nextElement();
if (!sourcenodes.containsKey(fs_taskexit)) {
toprocess.add(fs_taskexit);
-
}
//seen this node already
fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit);
- FEdge newedge=new FEdge(fs_taskexit,taskname);
- //FEdge newedge=new FEdge(fs_taskexit,td);
+ FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex);
+ ((Vector<FEdge>)tdToFEdges.get(td)).add(newedge);
fs.addEdge(newedge);
+
+ if(!targetFStates.contains(fs_taskexit)) {
+ targetFStates.addElement(fs_taskexit);
+ }
}
continue;
}
*/
-private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
+public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
if (fen==null)
return true;
else if (fen instanceof FlagNode)
return true;
}
-/*private int tagTypeCount(TagExpressionList tel, String tagtype){
- int ctr=0;
- for(int i=0;i<tel.numTags() ; i++){
- if (tel.getType(i).equals(tagtype))
- ctr++;
- }
- return ctr;
-} */
-/** Evaluates a NewObject Node and returns the newly created
- * flagstate to add to the process queue.
- * @param nn FlatNode
- * @return FlagState
- * @see FlatNode
- * @see FlagState
- */
-
-private FlagState evalNewObjNode(FlatNode nn){
-
- ClassDescriptor cd_new=((FlatNew)nn.getPrev(0)).getType().getClassDesc();
-
-
- //TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
-
- //if (tdArray.length==0)
- // return null;
-
- //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
- //ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
-
- FlagState fstemp=new FlagState(cd_new);
-
- for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
- TempFlagPair tfp=(TempFlagPair)it_tfp.next();
- if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
- {
- fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
- }
+ private Vector<FlagState> evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
+ FlagState fstemp=fs;
+ Vector<FlagState> processed=new Vector<FlagState>();
+
+ //Process the flag changes
- else
- break;
- }
- for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
- TempTagPair ttp=(TempTagPair)it_ttp.next();
- if (! (ttp.getTag()==null)){
- fstemp=fstemp.setTag(ttp.getTag());
+ for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
+ TempFlagPair tfp=(TempFlagPair)it_tfp.next();
+ if (temp==tfp.getTemp())
+ fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
}
- else
- break;
- }
- return fstemp;
-}
+ //Process the tag changes
+
+ processed.add(fstemp);
- private Vector<FlagState> evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){
- FlagState fstemp=fs;
- //FlagState[] fstemparray=new FlagState[3];
- Vector<FlagState> inprocess=new Vector<FlagState>();
- Vector<FlagState> processed=new Vector<FlagState>();
-
- for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
- TempFlagPair tfp=(TempFlagPair)it_tfp.next();
- if (temp==tfp.getTemp())
- fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
- }
-
- inprocess.add(fstemp);
- processed.add(fstemp);
-
- for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) {
- TempTagPair ttp=(TempTagPair)it_ttp.next();
-
- if (temp==ttp.getTemp()){
- processed=new Vector<FlagState>();
- for (Enumeration en=inprocess.elements();en.hasMoreElements();){
- FlagState fsworking=(FlagState)en.nextElement();
- if (((FlatFlagActionNode)nn).getTagChange(ttp)){
- fsworking=fsworking.setTag(ttp.getTag());
- processed.add(fsworking);
- }
- else
- {
- processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
- }
- }
- inprocess=processed;
- }
+ //Process clears first
+ for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
+ TempTagPair ttp=(TempTagPair)it_ttp.next();
+
+ if (temp==ttp.getTemp()) {
+ Vector<FlagState> oldprocess=processed;
+ processed=new Vector<FlagState>();
+
+ for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
+ FlagState fsworking=(FlagState)en.nextElement();
+ if (!ffan.getTagChange(ttp)){
+ processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
+ } else processed.add(fsworking);
}
- return processed;
-
-}
+ }
+ }
+ //Process sets next
+ for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
+ TempTagPair ttp=(TempTagPair)it_ttp.next();
+ if (temp==ttp.getTemp()) {
+ Vector<FlagState> oldprocess=processed;
+ processed=new Vector<FlagState>();
+
+ for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
+ FlagState fsworking=(FlagState)en.nextElement();
+ if (ffan.getTagChange(ttp)){
+ processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
+ } else processed.add(fsworking);
+ }
+ }
+ }
+ return processed;
+ }
+
private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){
if (sourcenodes.containsKey(fs))
*/
public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
- File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
- FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
- FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
-
+ File dotfile_flagstates= new File("graph"+cd.getSymbol()+".dot");
+ FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
+ FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
}
-
+
/** Returns the flag states for the class descriptor. */
- public Set getFlagStates(ClassDescriptor cd) {
+ public Set<FlagState> getFlagStates(ClassDescriptor cd) {
if (flagstates.containsKey(cd))
- return ((Hashtable)flagstates.get(cd)).keySet();
+ return ((Hashtable<FlagState, FlagState>)flagstates.get(cd)).keySet();
else
- return null;
+ return new HashSet<FlagState>();
}
private void createPossibleRuntimeStates(FlagState fs) {
- ClassDescriptor cd = fs.getClassDescriptor();
- Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
- FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
- int externs=((Integer)extern_flags.get(cd)).intValue();
-
- if(externs==0)
- return;
-
- int noOfIterations=(1<<externs) - 1;
- boolean BoolValTable[]=new boolean[externs];
-
-
- for(int i=0; i < externs ; i++) {
- BoolValTable[i]=fs.get(fd[i]);
- }
-
- for(int k=0; k<noOfIterations; k++) {
- for(int j=0; j < externs ;j++) {
- if ((k% (1<<j)) == 0)
- BoolValTable[j]=(!BoolValTable[j]);
- }
+ ClassDescriptor cd = fs.getClassDescriptor();
+ Hashtable<FlagState,FlagState> sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
+ FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
+ int externs=((Integer)extern_flags.get(cd)).intValue();
- FlagState fstemp=fs;
+ if(externs==0)
+ return;
+
+ int noOfIterations=(1<<externs) - 1;
+ boolean BoolValTable[]=new boolean[externs];
- for(int i=0; i < externs;i++) {
- fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
- }
- if (!sourcenodes.containsKey(fstemp))
- toprocess.add(fstemp);
-
- fstemp=canonicalizeFlagState(sourcenodes,fstemp);
- fs.addEdge(new FEdge(fstemp,"Runtime"));
- }
- }
- public Vector getRootNodes(ClassDescriptor cd){
- return (Vector)cdtorootnodes.get(cd);
+ for(int i=0; i < externs ; i++) {
+ BoolValTable[i]=fs.get(fd[i]);
}
-
+ for(int k=0; k<noOfIterations; k++) {
+ for(int j=0; j < externs ;j++) {
+ if ((k% (1<<j)) == 0)
+ BoolValTable[j]=(!BoolValTable[j]);
+ }
+
+ FlagState fstemp=fs;
+
+ for(int i=0; i < externs;i++) {
+ fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
+ }
+ if (!sourcenodes.containsKey(fstemp))
+ toprocess.add(fstemp);
+
+ fstemp=canonicalizeFlagState(sourcenodes,fstemp);
+ fs.addEdge(new FEdge(fstemp,"Runtime", null, -1));
+ }
+ }
+
+ public Vector getRootNodes(ClassDescriptor cd){
+ return (Vector)cdtorootnodes.get(cd);
+ }
+
+ public Vector getFEdgesFromTD(TaskDescriptor td) {
+ return (Vector)tdToFEdges.get(td);
+ }
}