--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+import java.io.File;
+import java.io.FileWriter;
+import java.io.FileOutputStream;
+
+
+public class FlagInfo {
+ private Hashtable<ClassDescriptor, FlagDescriptor[]> flags;
+ private State state;
+
+ public FlagInfo(State state) {
+ this.state=state;
+ flags=new Hashtable<ClassDescriptor, FlagDescriptor[]>();
+ getFlagsfromClasses();
+ }
+
+ public FlagDescriptor[] getFlags(ClassDescriptor cd) {
+ return flags.get(cd);
+ }
+
+ /** Builds a table of flags for each class in the Bristlecone
+ * program. It creates one hashtables: one which holds the
+ * ClassDescriptors and arrays of * FlagDescriptors as key-value
+ * pairs. */
+
+ private void getFlagsfromClasses() {
+ for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
+ ClassDescriptor cd = (ClassDescriptor)it_classes.next();
+ Vector vFlags=new Vector();
+ FlagDescriptor flag[];
+ int ctr=0;
+
+ /* Adding the flags of the super class */
+ ClassDescriptor tmp=cd;
+ while(tmp!=null) {
+ for(Iterator it_cflags=tmp.getFlags();it_cflags.hasNext();) {
+ FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
+ vFlags.add(fd);
+ }
+ tmp=tmp.getSuperDesc();
+ }
+
+ flag=new FlagDescriptor[vFlags.size()];
+
+ flags.put(cd,flag);
+ }
+ }
+}
\ No newline at end of file
}
}
+ public int getTagCount(TagDescriptor tag) {
+ if (tags.containsKey(tag))
+ return tags.get(tag).intValue();
+ else return 0;
+ }
+
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 NOTAGS;
+ return getTagCount(new TagDescriptor(tagtype));
}
public FlagState[] clearTag(TagDescriptor tag){
return "N"+uid;
}
-
-
-
public String getTextLabel() {
String label=null;
for(Iterator it=getFlags();it.hasNext();) {
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+
+public class FlagTagState {
+ TagState ts;
+ FlagState fs;
+
+ public FlagTagState(TagState ts, FlagState fs) {
+ this.ts=ts;
+ this.fs=fs;
+ }
+
+ public boolean equals(Object o) {
+ if (o instanceof FlagTagState) {
+ FlagTagState fts=(FlagTagState) o;
+ return ts.equals(fts.ts)&&fs.equals(fts.fs);
+ }
+ return false;
+ }
+
+ public int hashCode() {
+ return ts.hashCode()^fs.hashCode();
+ }
+}
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+
+public class ObjWrapper {
+ FlagState fs;
+ Vector<TagWrapper> tags;
+
+ public ObjWrapper(FlagState fs) {
+ this.fs=fs;
+ tags=new Vector<TagWrapper>();
+ }
+
+}
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import Analysis.TaskStateAnalysis.*;
+import IR.*;
+import IR.Flat.*;
+import java.util.*;
+import Util.GraphNode;
+
+
+public class TagState extends GraphNode {
+ private TagDescriptor tag;
+ private Hashtable<FlagState, Integer> flags;
+ public static final int KLIMIT=2;
+
+ public TagState() {
+ this(null);
+ }
+
+ public TagState(TagDescriptor tag) {
+ this.tag=tag;
+ this.flags=new Hashtable<FlagState, Integer>();
+ }
+
+ public TagDescriptor getTag() {
+ return tag;
+ }
+
+ public TagState[] addnewFS(FlagState fs) {
+ int num=0;
+ if (flags.containsKey(fs))
+ num=flags.get(fs).intValue();
+ if (num<KLIMIT)
+ num++;
+
+ TagState ts=new TagState(tag);
+ ts.flags.putAll(flags);
+ ts.flags.put(fs, new Integer(num));
+ return new TagState[] {ts};
+ }
+
+ public TagState[] addFS(FlagState fs) {
+ int num=0;
+ if (flags.containsKey(fs))
+ num=flags.get(fs).intValue();
+ if (num<KLIMIT)
+ num++;
+
+ TagState ts=new TagState(tag);
+ ts.flags.putAll(flags);
+ ts.flags.put(fs, new Integer(num));
+ if (num==1)
+ return new TagState[] {ts};
+ else
+ return new TagState[] {this, ts};
+ }
+
+ public boolean containsFS(FlagState fs) {
+ return flags.containsKey(fs);
+ }
+
+ public Set<FlagState> getFS() {
+ return flags.keySet();
+ }
+
+ public int hashCode() {
+ int hashcode=flags.hashCode();
+ if (tag!=null)
+ hashcode^=tag.hashCode();
+ return hashcode;
+ }
+
+ public boolean equals(Object o) {
+ if (o instanceof TagState) {
+ TagState t=(TagState)o;
+ if ((tag==null&&t.tag==null)||
+ (tag!=null&&t.tag!=null&&tag.equals(t.tag))) {
+ return flags.equals(t.flags);
+ }
+ }
+ return false;
+ }
+}
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+
+public class TagWrapper {
+ TagState initts;
+ Vector<TagState> ts;
+
+ public TagWrapper(TagState ts) {
+ this.initts=ts;
+ this.ts=new Vector<TagState>();
+ this.ts.addAll(ts);
+ }
+
+ public TagWrapper clone() {
+ TagWrapper tw=new TagWrapper();
+ tw.initts=initts;
+ tw.ts=ts.clone();
+ return tw;
+ }
+}
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+
+public class TaskBinding {
+ TaskQueueIterator tqi;
+ Vector<Integer> decisions;
+ Hashtable<TempDescriptor, TagWrapper> temptotag;
+ ObjWrapper[] parameterbindings;
+ boolean increment;
+
+ public TaskBinding(TaskQueueIterator tqi) {
+ this.tqi=tqi;
+ this.decisions=new Vector<Integer>();
+ int numobjs=tqi.ftsarray.length;
+ int numtags=tqi.tq.tags.size();
+ this.parameterbindings=new ObjWrapper[numobjs];
+ for(int i=0;i<(numtags+numobjs);i++) {
+ decisions.add(new Integer(0));
+ }
+ }
+
+ public ObjWrapper getParameter(int i) {
+ return parameterbindings[i];
+ }
+
+ public TagWrapper getTag(TempDescriptor tmp) {
+ return temptotag.get(tmp);
+ }
+
+ public void next() {
+ increment=true;
+ }
+
+ public boolean hasNext() {
+ Vector<TempDescriptor> tagv=tqi.tq.tags;
+ int numtags=tagv.size();
+ int numobjs=tqi.ftsarray.length;
+ int incrementlevel=numtags+numobjs;
+ if (increment) {
+ //actually do increment
+ incrementlevel--;
+ increment=false;
+ }
+
+ mainloop:
+ while(true) {
+ Hashtable<TagState, Vector<TagWrapper>> ttable=new Hashtable<TagState, Vector<TagWrapper>>();
+ temptotag=new Hashtable<TempDescriptor, TagWrapper>();
+ //build current state
+ for(int i=0;i<(numtags+numobjs);i++) {
+ TagState tag=null;
+ TagWrapper tw=null;
+ if (i>=numtags) {
+ int objindex=i-numtags;
+ tag=tqi.ftsarray[objindex].ts;
+ } else {
+ TempDescriptor tmp=tagv.get(i);
+ tag=tqi.getTS(tmp);
+ }
+ int index=decisions.get(i).intValue();
+ int currentsize=ttable.get(tag).size();
+ if (i==incrementlevel) {
+ if (index==currentsize) {
+ if (incrementlevel==0)
+ return false;
+ incrementlevel--;
+ continue mainloop;
+ } else {
+ index++;
+ decisions.set(i, new Integer(index));
+ }
+ } else if (i>incrementlevel) {
+ index=0;
+ decisions.set(i, new Integer(index));
+ }
+ if (index>currentsize) {
+ tw=new TagWrapper(tag);
+ if (!ttable.containsKey(tag)) {
+ ttable.put(tag, new Vector<TagWrapper>());
+ }
+ ttable.get(tag).add(tw);
+ } else {
+ //use old instance
+ tw=ttable.get(tag).get(index);
+ }
+ if (i>=numtags) {
+ int objindex=i-numtags;
+ FlagTagState fts=tqi.ftsarray[objindex];
+ ObjWrapper ow=new ObjWrapper(fts.fs);
+ Hashtable <TagState,Set<TagWrapper>> ctable=new Hashtable<TagState, Set<TagWrapper>>();
+ ctable.put(tw.ts, new HashSet<TagWrapper>());
+ ctable.get(tw.ts).add(tw);
+ ow.tags.add(tw);
+ TagExpressionList tel=tqi.tq.task.getTag(tqi.tq.task.getParameter(i));
+ for(int j=0;j<tel.numTags();j++) {
+ TempDescriptor tagtmp=tel.getTemp(j);
+ TagWrapper twtmp=temptotag.get(tagtmp);
+ if (!ctable.containsKey(twtmp.ts))
+ ctable.put(twtmp.ts, new HashSet<TagWrapper>());
+ ctable.get(twtmp.ts).add(twtmp);
+ ow.tags.add(twtmp);
+ int tagcount=ctable.get(twtmp.ts).size();
+ int fstagcount=fts.fs.getTagCount(twtmp.ts.getTag());
+ if (fstagcount>=0&&(tagcount>fstagcount)) {
+ //Too many unique tags of this type bound to object wrapper
+ incrementlevel=i;
+ continue mainloop;
+ }
+ }
+ parameterbindings[objindex]=ow;
+ } else {
+ TempDescriptor tmp=tagv.get(i);
+ temptotag.put(tmp, tw);
+ }
+ }
+ return true;
+ }
+ }
+}
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+
+public class TaskQueue {
+ protected TaskDescriptor task;
+ protected HashSet<FlagTagState> []parameterset;
+ protected Vector<TempDescriptor> tags;
+ protected Hashtable <FlagState, Vector<FlagTagState>> map;
+
+ public int numParameters() {
+ return parameterset.length;
+ }
+
+ public TaskDescriptor getTask() {
+ return task;
+ }
+
+ public TaskQueue(TaskDescriptor td) {
+ this.task=td;
+ this.parameterset=(HashSet<FlagTagState>[])new HashSet[task.numParameters()];
+ this.map=new Hashtable<FlagState, Vector<FlagTagState>>();
+ for(int i=0;i<task.numParameters();i++) {
+ this.parameterset[i]=new HashSet<FlagTagState>();
+ TagExpressionList tel=td.getTag(td.getParameter(i));
+ for(int j=0;j<tel.numTags();j++) {
+ TempDescriptor tagtmp=tel.getTemp(j);
+ if (!tags.contains(tagtmp))
+ tags.add(tagtmp);
+ }
+ }
+ }
+
+ public TaskQueueIterator enqueue(int index, FlagTagState fts) {
+ parameterset[index].add(fts);
+ if (!map.containsKey(fts.fs)) {
+ map.put(fts.fs, new Vector<FlagTagState>());
+ }
+ map.get(fts.fs).add(fts);
+ return new TaskQueueIterator(this, index, fts);
+ }
+}
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+
+public class TaskQueueIterator {
+ TaskQueue tq;
+ int index;
+ FlagTagState fts;
+ FlagTagState ftsarray[];
+ Hashtable<TempDescriptor, TagState> tsarray;
+ Hashtable<TempDescriptor, Integer> tsindexarray;
+ Iterator<FlagTagState> itarray[];
+ boolean needit;
+ boolean needinit;
+
+ public TaskQueueIterator(TaskQueue tq, int index, FlagTagState fts) {
+ this.tq=tq;
+ this.index=index;
+ this.fts=fts;
+ this.ftsarray=new FlagTagState[tq.numParameters()];
+ this.ftsarray[index]=fts;
+ this.tsarray=new Hashtable<TempDescriptor, TagState>();
+ this.tsindexarray=new Hashtable<TempDescriptor, Integer>();
+ this.itarray=(Iterator<FlagTagState>[]) new Iterator[tq.numParameters()];
+ needit=false;
+ needinit=true;
+ init();
+ }
+
+ private void init() {
+ for(int i=ftsarray.length-1;i>=0;i--) {
+ if (i!=index)
+ itarray[i]=tq.parameterset[i].iterator();
+ VarDescriptor vd=tq.task.getParameter(i);
+ TagExpressionList tel=tq.task.getTag(vd);
+ for(int j=0;j<tel.numTags();j++) {
+ TempDescriptor tmp=tel.getTemp(j);
+ if (!tsindexarray.containsKey(tmp)) {
+ tsindexarray.put(tmp, new Integer(i));
+ }
+ }
+ }
+ }
+
+ public boolean hasNext() {
+ TaskDescriptor td=tq.task;
+ int i;
+ if (needinit) {
+ i=ftsarray.length-1;
+ if (i!=index)
+ ftsarray[i]=itarray[i].next();
+ } else {
+ i=0;
+ }
+
+ objloop:
+ for(;i<ftsarray.length;i++) {
+ FlagState currfs=ftsarray[i].fs;
+ VarDescriptor vd=td.getParameter(i);
+ TagExpressionList tel=td.getTag(vd);
+ int j;
+ if (needinit) {
+ j=tel.numTags()>0?tel.numTags()-1:0;
+ needinit=false;
+ } else
+ j=0;
+ tagloop:
+ for(;j<tel.numTags();j++) {
+ TempDescriptor tmp=tel.getTemp(j);
+ TagState currtag=tsarray.get(tmp);
+ String type=tel.getType(j);
+
+ if (tsindexarray.get(tmp).intValue()==i) {
+ //doing the assignment right here!!!
+ Vector<FlagTagState> possts=tq.map.get(currfs);
+ int index=0;
+ if (currtag!=null)
+ index=possts.indexOf(new FlagTagState(currtag,currfs));
+ if (needit) {
+ index++;
+ needit=false;
+ }
+ for(int k=index;k<possts.size();k++) {
+ FlagTagState posstag=possts.get(k);
+ if (posstag.ts.getTag().getSymbol().equals(type)) {
+ tsarray.put(tmp, posstag.ts);
+ if (j==0) {
+ if (i==0) {
+ //We are done!
+ return true;
+ } else {
+ //Backtrack on objects
+ i-=2;
+ continue objloop;
+ }
+ } else {
+ //Backtrack on tags
+ j-=2;
+ continue tagloop;
+ }
+ }
+ }
+ //couldn't find a tag
+ tsarray.put(tmp, null);
+ needit=true;
+ } else {
+ //check tag compatibility
+ if (!currtag.containsFS(currfs)) {
+ //incompatible tag set by previous level
+ //need to increment object state
+ needit=true;
+ break;
+ }
+ }
+ }
+ if (index==i) {
+ continue;
+ }
+ if (needit) {
+ if (itarray[i].hasNext()) {
+ ftsarray[i]=itarray[i].next();
+ needit=false;
+ i-=1;
+ continue objloop; //backtrack and fix up everything
+ } else {
+ itarray[i]=tq.parameterset[i].iterator();//keep going backwards
+ }
+ } else {
+ throw new Error();
+ }
+ }
+ return false;
+ }
+
+ public FlagTagState getFTS(int index) {
+ return ftsarray[index];
+ }
+
+ public TagState getTS(TempDescriptor tmp) {
+ return tsarray.get(tmp);
+ }
+
+ public void next() {
+ needit=true;
+ }
+}
--- /dev/null
+package Analysis.TaskStateAnalysis;
+import IR.*;
+import IR.Tree.*;
+import IR.Flat.*;
+import java.util.*;
+import java.io.File;
+import java.io.FileWriter;
+import java.io.FileOutputStream;
+
+public class TaskTagAnalysis {
+ State state;
+ TagAnalysis taganalysis;
+ TypeUtil typeutil;
+ FlagInfo flaginfo;
+ HashSet<TagState> toprocess;
+ Hashtable<TaskDescriptor, TaskQueue> tasktable;
+
+
+ /**
+ * Class Constructor
+ *
+ */
+ public TaskTagAnalysis(State state, TagAnalysis taganalysis) {
+ this.state=state;
+ this.typeutil=new TypeUtil(state);
+ this.taganalysis=taganalysis;
+ this.flaginfo=new FlagInfo(state);
+ this.toprocess=new HashSet<TagState>();
+ this.tasktable=new Hashtable<TaskDescriptor, TaskQueue>();
+ for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
+ TaskDescriptor td=(TaskDescriptor)taskit.next();
+ tasktable.put(td, new TaskQueue(td));
+ }
+ }
+
+ private void doAnalysis() {
+ toprocess.add(createInitialState());
+
+ while(!toprocess.isEmpty()) {
+ TagState ts=toprocess.iterator().next();
+ toprocess.remove(ts);
+ //Loop through each task
+ for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
+ TaskDescriptor td=(TaskDescriptor)taskit.next();
+ TaskQueue tq=tasktable.get(td);
+ processTask(td, tq, ts);
+ }
+ }
+ }
+
+ private void processTask(TaskDescriptor td, TaskQueue tq, TagState ts) {
+ Set<FlagState> flagset=ts.getFS();
+ for(Iterator<FlagState> fsit=flagset.iterator();fsit.hasNext();) {
+ FlagState fs=fsit.next();
+ FlagTagState fts=new FlagTagState(ts, fs);
+ for(int i=0;i<td.numParameters();i++) {
+ if (canEnqueue(td, i, fs)) {
+ TaskQueueIterator tqi=tq.enqueue(i, fts);
+ while(tqi.hasNext()) {
+ processBinding(tqi);
+ tqi.next();
+ }
+ }
+ }
+ }
+ }
+
+ private void processBinding(TaskQueueIterator tqi) {
+ TaskBinding tb=new TaskBinding(tqi);
+ while(tb.hasNext()) {
+ doAnalysis(tb);
+
+ tb.next();
+ }
+ }
+
+ private Hashtable<TempDescriptor, TagWrapper> computeInitialState(Hashtable<FlatNode, Hashtable<TempDescriptor, TagWrapper>> table, FlatNode fn) {
+ Hashtable<TempDescriptor, TagWrapper> table=new Hashtable<TempDescriptor, TagWrapper>();
+ for(int i=0;i<fn.numPrev();i++) {
+ FlatNode fnprev=fn.getPrev(i);
+ Hashtable<TempDescriptor, TagWrapper> prevtable=table.get(fn);
+ for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
+ TempDescriptor tmp=tmpit.next();
+ TagWrapper prevtag=prevtable.get(tmp);
+ if (table.containsKey(tmp)) {
+ TagWrapper currtag=table.get(tmp);
+ } else {
+ table.put(tmp, prevtag.clone());
+ }
+
+ }
+ }
+
+ return table;
+ }
+
+ private void doAnalysis(TaskBinding tb) {
+ TaskDescriptor td=tb.tqi.tq.getTask();
+ FlatMethod fm=state.getMethodFlat(td);
+ Hashtable<FlatNode, Hashtable<TempDescriptor, TagWrapper>> table=new Hashtable<FlatNode, Hashtable<TempDescriptor, TagWrapper>>();
+ table.put(fm, buildinittable(tb));
+ HashSet<FlatNode> visited=new HashSet<FlatNode>();
+ HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
+ tovisit.add(fm.getNext(0));
+ while(!tovisit.isEmpty()) {
+ FlatNode fn=tovisit.iterator().next();
+ tovisit.remove(fn);
+ visited.add(fn);
+
+
+ for(int i=0;i<fn.numNext();i++) {
+ if (!visited.contains(fn.getNext(i)))
+ tovisit.add(fn.getNext(i));
+ }
+ }
+
+ }
+
+ private Hashtable<TempDescriptor, Set<TagWrapper>> buildinittable(TaskBinding tb) {
+ Hashtable<TempDescriptor, Set<TagWrapper>> table=new Hashtable<TempDescriptor, Set<TagWrapper>>();
+ Vector<TempDescriptor> tagtmps=tb.tqi.tq.tags;
+ for(int i=0;i<tagtmps.size();i++) {
+ TempDescriptor tmp=tagtmps.get(i);
+ HashSet<TagWrapper> tset=new HashSet<TagWrapper>();
+ tset.add(tb.getTag(tmp));
+ table.put(tmp, tset);
+ }
+ return table;
+ }
+
+ /*
+ method summary:
+ new flag states created
+ new tag states created
+ flag states bound to tag parameters
+ */
+
+ public boolean canEnqueue(TaskDescriptor td, int paramnum, FlagState fs) {
+ return typeutil.isSuperorType(td.getParamType(paramnum).getClassDesc(),fs.getClassDescriptor())&&
+ isTaskTrigger_flag(td.getFlag(td.getParameter(paramnum)),fs)&&
+ isTaskTrigger_tag(td.getTag(td.getParameter(paramnum)),fs);
+ }
+
+ private static boolean isTaskTrigger_flag(FlagExpressionNode fen, FlagState fs) {
+ if (fen==null)
+ return true;
+ else if (fen instanceof FlagNode)
+ return fs.get(((FlagNode)fen).getFlag());
+ else
+ switch (((FlagOpNode)fen).getOp().getOp()) {
+ case Operation.LOGIC_AND:
+ return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
+ case Operation.LOGIC_OR:
+ return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
+ case Operation.LOGIC_NOT:
+ return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
+ default:
+ return false;
+ }
+ }
+
+
+ private static boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
+ if (tel!=null){
+ for (int i=0;i<tel.numTags() ; i++){
+ switch (fs.getTagCount(tel.getType(i))){
+ case FlagState.ONETAG:
+ case FlagState.MULTITAGS:
+ break;
+ case FlagState.NOTAGS:
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ TagState createInitialState() {
+ ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
+ FlagDescriptor fd=(FlagDescriptor)startupobject.getFlagTable().get(FlagDescriptor.InitialFlag);
+ FlagState fsstartup=(new FlagState(startupobject)).setFlag(fd,true);
+ fsstartup.setAsSourceNode();
+ fsstartup=canonical(fsstartup);
+ TagState ts=new TagState();
+ TagState[] tsarray=ts.addFS(fsstartup);
+ return canonical(tsarray[0]);
+ }
+
+ FlagState canonical(FlagState fs) {
+ return fs;
+ }
+
+ TagState canonical(TagState ts) {
+ return ts;
+ }
+
+
+}
+
projects / IRC.git / commitdiff