From 5d1179f4e81ba944d52b6e5ceb096a79cf874e74 Mon Sep 17 00:00:00 2001 From: sivaji Date: Fri, 18 May 2007 02:38:20 +0000 Subject: [PATCH] Added tag support to TaskAnalysis, FlagState. --- .../Analysis/TaskStateAnalysis/FlagState.java | 173 +++++++++++++++--- .../TaskStateAnalysis/TaskAnalysis.java | 123 +++++++++++-- .../TaskStateAnalysis/TaskAnalysisAlgorithm | 2 + 3 files changed, 263 insertions(+), 35 deletions(-) diff --git a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java index b7921443..44c82747 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java @@ -6,14 +6,22 @@ import IR.Flat.*; import java.util.*; import java.io.*; - +/** This class is used to hold the flag states that a class in the Bristlecone + * program can exist in, during runtime. + */ public class FlagState { /* NodeStatus enumeration pattern ***********/ public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED"); public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING"); public static final NodeStatus FINISHED = new NodeStatus("FINISHED"); + public static final int ONETAG=1; + public static final int NOTAGS=0; + public static final int MULTITAGS=-1; + + + public static class NodeStatus { private static String name; private NodeStatus(String name) { this.name = name; } @@ -24,6 +32,7 @@ public class FlagState { int discoverytime = -1; int finishingtime = -1; /* used for searches */ + //Hashtable tags=new Hashtable(); Vector edges = new Vector(); Vector inedges = new Vector(); NodeStatus status = UNVISITED; @@ -35,6 +44,7 @@ public class FlagState { private final HashSet flagstate; private final ClassDescriptor cd; + private final Hashtable tags; public void setOption(String option) { this.nodeoption=","+option; @@ -43,31 +53,120 @@ public class FlagState { public void setMerge() { merge=true; } - + /** Class constructor + * Creates a new flagstate with all flags set to false. + * @param cd ClassDescriptor + */ public FlagState(ClassDescriptor cd) { this.flagstate=new HashSet(); this.cd=cd; + this.tags=new Hashtable(); this.uid=FlagState.nodeid++; } - private FlagState(HashSet flagstate, ClassDescriptor cd) { + /** Class constructor + * Creates a new flagstate with flags set according to the HashSet. + * If the flag exists in the hashset, it's set to true else set to false. + * @param cd ClassDescriptor + * @param flagstate a HashSet containing FlagDescriptors + */ + private FlagState(HashSet flagstate, ClassDescriptor cd,Hashtable tags) { this.flagstate=flagstate; this.cd=cd; + this.tags=tags; this.uid=FlagState.nodeid++; + } + /** Accessor method + * @param fd FlagDescriptor + * @return true if the flagstate contains fd else false. + */ public boolean get(FlagDescriptor fd) { return flagstate.contains(fd); } + public String toString() { return cd.toString()+getTextLabel(); } + /** @return Iterator over the flags in the flagstate. + */ + public Iterator getFlags() { return flagstate.iterator(); } + public FlagState setTag(TagDescriptor tag){ + + HashSet newset=flagstate.clone(); + Hashtable newtags=tags.clone(); + + if (newtags.containsKey(tag)){ + switch (newtags.get(tag).intValue()){ + case ONETAG: + newtags.put(tag,new Integer(MULTITAG)); + break; + case MULTITAG: + newtags.put(tag,new Integer(MULTITAG)); + break; + } + } + else{ + newtags.put(tag,new Integer(ONETAG)); + } + + return new FlagState(newset,cd,newtags); + + } + public int getTagCount(String tagtype){ + for (Enumeration en=getTags();en.hasMoreElements();){ + TagDescriptor td=(TagDescriptor)en.nextElement(); + if (tagtype.equals(td.getSymbol())) + return tags.get(td).intValue(); //returns either ONETAG or MULTITAG + } + return NOTAG; + + } + + + + public FlagState[] clearTag(TagDescriptor tag){ + + if (tags.containsKey(tag)){ + switch(tags.get(tag).intValue()){ + case ONETAG: + HashSet newset=flagstate.clone(); + Hashtable newtags=tags.clone(); + newtags.remove(tag); + return new FlagState(newset,cd,newtags); + break; + case MULTITAG: + //when tagcount is more than 2, COUNT stays at MULTITAG + FlagState[] retstates=new FlagState[2]; + HashSet newset1=flagstate.clone(); + Hashtable newtags1=tags.clone(); + retstates[1]=new FlagState(newset1,cd,newtags1); + //when tagcount is 2, COUNT changes to ONETAG + HashSet newset2=flagstate.clone(); + Hashtable newtags2=tags.clone(); + newtags1.put(tag,new Integer(ONETAG)); + retstates[1]=new FlagState(newset2,cd,newtags2); + return retstates; + break; + } + }else{ + throw new Error("Invalid Operation: Can not clear a tag that doesn't exist."); + } + + } + + /** Creates a string description of the flagstate + * e.g. a flagstate with five flags could look like 01001 + * @param flags an array of flagdescriptors. + * @return string representation of the flagstate. + */ public String toString(FlagDescriptor[] flags) { StringBuffer sb = new StringBuffer(flagstate.size()); @@ -82,11 +181,20 @@ public class FlagState { return new String(sb); } - + /** Accessor method + * @return returns the classdescriptor of the flagstate. + */ + public ClassDescriptor getClassDescriptor(){ return cd; } + /** Sets the status of a specific flag in a flagstate after cloning it. + * @param fd FlagDescriptor of the flag whose status is being set. + * @param status boolean value + * @return the new flagstate with fd set to status. + */ + public FlagState setFlag(FlagDescriptor fd, boolean status) { HashSet newset=(HashSet) flagstate.clone(); if (status) @@ -97,18 +205,21 @@ public class FlagState { return new FlagState(newset, cd); } + /** Tests for equality of two flagstate objects. + */ + public boolean equals(Object o) { if (o instanceof FlagState) { FlagState fs=(FlagState)o; if (fs.cd!=cd) return false; - return fs.flagstate.equals(flagstate); + return (fs.flagstate.equals(flagstate) & fs.tags.equals(tags)); } return false; } public int hashCode() { - return cd.hashCode()^flagstate.hashCode(); + return cd.hashCode()^flagstate.hashCode()^tags.hashCode(); } public static void computeclosure(Collection nodes, Collection removed) { @@ -185,8 +296,25 @@ public class FlagState { else label+=", "+fd.toString(); } + for (Enumeration en_tags=getTags();en_tags.hasMoreElements();){ + TagDescriptor td=(TagDescriptor)en_tags.nextElement(); + switch (tags.get(td).intValue()){ + case ONETAG: + label+=", "+td.toString()+"(1)"; + break; + case MULTITAG: + label+=", "+td.toString()+"(n)"; + break; + default: + break; + } + } return label; } + + public Enumeration getTags(){ + return tags.keys(); + } public NodeStatus getStatus() { return this.status; @@ -286,24 +414,23 @@ public class FlagState { FlagState gn = (FlagState) i.next(); Iterator edges = gn.edges(); String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];"; - String option=gn.nodeoption; - if (special!=null&&special.contains(gn)) - option+=",shape=box"; - if (!gn.merge) + String option=gn.nodeoption; + if (special!=null&&special.contains(gn)) + option+=",shape=box"; + if (!gn.merge) output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];"); - - if (!gn.merge) - while (edges.hasNext()) { - Edge edge = (Edge) edges.next(); - FlagState node = edge.getTarget(); - if (nodes.contains(node)) { - for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) { - FlagState node2=(FlagState)nodeit.next(); - String edgelabel = "label=\"" + edge.getLabel() + "\""; - output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];"); - } - } - } + if (!gn.merge) + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + FlagState node = edge.getTarget(); + if (nodes.contains(node)) { + for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) { + FlagState node2=(FlagState)nodeit.next(); + String edgelabel = "label=\"" + edge.getLabel() + "\""; + output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];"); + } + } + } } } diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java index 23474145..441de09e 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java @@ -9,6 +9,9 @@ import java.io.FileWriter; import java.io.FileOutputStream; + + + public class TaskAnalysis { State state; Hashtable flagstates; @@ -29,12 +32,18 @@ public class TaskAnalysis { this.typeutil=new TypeUtil(state); } - /** This function builds a table of flags for each 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 + */ for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) { ClassDescriptor cd = (ClassDescriptor)it_classes.next(); @@ -57,7 +66,6 @@ public class TaskAnalysis { for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) { FlagDescriptor fd = (FlagDescriptor)it_cflags.next(); - System.out.println(fd.toString()); vFlags.add(fd); } @@ -80,11 +88,15 @@ public class TaskAnalysis { } } } + /** Method which starts up the analysis + * + */ public void taskAnalysis() throws java.io.IOException { flagstates=new Hashtable(); Hashtable sourcenodes; + getFlagsfromClasses(); int externs; @@ -117,13 +129,14 @@ public class TaskAnalysis { sourcenodes.put(fsstartup,fsstartup); toprocess.add(fsstartup); + /** Looping through the flagstates in the toprocess queue to perform the state analysis */ while (!toprocess.isEmpty()) { FlagState trigger=toprocess.poll(); createPossibleRuntimeStates(trigger); analyseTasks(trigger); } - //Creating DOT files + /** Creating DOT files */ Enumeration e=flagstates.keys(); while (e.hasMoreElements()) { @@ -133,24 +146,38 @@ public class TaskAnalysis { createDOTfile(cdtemp); } } + + + /** Analyses the set of tasks based on the given flagstate, checking + * to see which tasks are triggered and what new flagstates are created + * from the base flagstate. + * @param fs A FlagState object which is used to analyse the task + * @see FlagState + */ - -private void analyseTasks(FlagState fs) { + private void analyseTasks(FlagState fs) { ClassDescriptor cd=fs.getClassDescriptor(); Hashtable sourcenodes=(Hashtable)flagstates.get(cd); for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) { TaskDescriptor td = (TaskDescriptor)it_tasks.next(); String taskname=td.getSymbol(); + /** 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); 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*/ if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd) - && isTaskTrigger(fen,fs)) { + && isTaskTrigger_flag(fen,fs) + && isTaskTrigger_tag(tel,fs)) { temp=fm.getParameter(i); trigger_ctr++; } @@ -206,7 +233,18 @@ private void analyseTasks(FlagState fs) { } } -private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) { +/** Determines whether the given flagstate satisfies a + * single parameter in the given task. + * @param fen FlagExpressionNode + * @see FlagExpressionNode + * @param fs FlagState + * @see FlagState + * @return true if fs satisfies the boolean expression + denoted by fen else false. + */ + + +private boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) { if (fen instanceof FlagNode) return fs.get(((FlagNode)fen).getFlag()); else @@ -221,6 +259,40 @@ private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) { return false; } } + +private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){ + + + for (int i=0;i evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){ FlagState fstemp=fs; + //FlagState[] fstemparray=new FlagState[3]; + Vector fsv=new Vector(); + 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)); } + + for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + if (temp==ttp.getTemp()){ + if (((FlatFlagActionNode)nn).getTagChange(ttp)){ + fstemp=fstemp.setTag(ttp.getTag()); + fstemp + else + fstemparray + } + return fstemp; } @@ -263,6 +357,12 @@ private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) { } } + /** Creates a DOT file using the flagstates for a given class + * @param cd ClassDescriptor of the class + * @throws java.io.IOException + * @see ClassDescriptor + */ + public void createDOTfile(ClassDescriptor cd) throws java.io.IOException { File dotfile= new File("graph"+cd.getSymbol()+".dot"); FileOutputStream dotstream=new FileOutputStream(dotfile,true); @@ -275,7 +375,7 @@ private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) { return st.nextToken(); } -private void createPossibleRuntimeStates(FlagState fs) { + private void createPossibleRuntimeStates(FlagState fs) { ClassDescriptor cd = fs.getClassDescriptor(); Hashtable sourcenodes=(Hashtable)flagstates.get(cd); FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd); @@ -291,8 +391,7 @@ private void createPossibleRuntimeStates(FlagState fs) { BoolValTable[i]=fs.get(fd[i]); } - - for(int k=0; k