Programming Languages Research Group: Git - IRC.git/blob

   1 package Analysis.TaskStateAnalysis;
   2
   3 import Analysis.TaskStateAnalysis.*;
   4 import IR.*;
   5 import IR.Tree.*;
   6 import IR.Flat.*;
   7 import java.util.*;
   8 import java.io.*;
   9 import Util.GraphNode;
  10
  11 /** This class is used to hold the flag states that a class in the Bristlecone
  12  *  program can exist in, during runtime.
  13  */
  14 public class FlagState extends GraphNode implements Cloneable {
  15     public static final int ONETAG=1;
  16     public static final int NOTAGS=0;
  17     public static final int MULTITAGS=-1;
  18
  19     private int uid;
  20     private static int nodeid=0;
  21
  22     private final HashSet flagstate;
  23     private final ClassDescriptor cd;
  24     private final Hashtable<TagDescriptor,Integer> tags;
  25     private boolean issourcenode;
  26     private Vector tasks;
  27     public static final int KLIMIT=2;
  28
  29     // jzhou
  30     private int executeTime;
  31     private int invokeNum;
  32
  33     /** Class constructor
  34      *  Creates a new flagstate with all flags set to false.
  35      *  @param cd ClassDescriptor
  36      */
  37     public FlagState(ClassDescriptor cd) {
  38         this.flagstate=new HashSet();
  39         this.cd=cd;
  40         this.tags=new Hashtable<TagDescriptor,Integer>();
  41         this.uid=FlagState.nodeid++;
  42         this.issourcenode=false;
  43         this.executeTime = -1;
  44         this.invokeNum = 0;
  45     }
  46
  47     /** Class constructor
  48      *  Creates a new flagstate with flags set according to the HashSet.
  49      *  If the flag exists in the hashset, it's set to true else set to false.
  50      *  @param cd ClassDescriptor
  51      *  @param flagstate a <CODE>HashSet</CODE> containing FlagDescriptors
  52      */
  53     private FlagState(HashSet flagstate, ClassDescriptor cd,Hashtable<TagDescriptor,Integer> tags) {
  54         this.flagstate=flagstate;
  55         this.cd=cd;
  56         this.tags=tags;
  57         this.uid=FlagState.nodeid++;
  58         this.issourcenode=false;
  59         this.executeTime = -1;
  60         this.invokeNum = 0;
  61     }
  62
  63     public int getuid() {
  64         return uid;
  65     }
  66
  67     /** Accessor method
  68       *  @param fd FlagDescriptor
  69       *  @return true if the flagstate contains fd else false.
  70       */
  71     public boolean get(FlagDescriptor fd) {
  72         return flagstate.contains(fd);
  73     }
  74
  75     /** Checks if the flagstate is a source node.
  76      *  @return true if the flagstate is a sourcenode(i.e. Is the product of an allocation site).
  77      */
  78
  79     public boolean isSourceNode(){
  80         return issourcenode;
  81     }
  82
  83     /**  Sets the flagstate as a source node.
  84      */
  85     public void setAsSourceNode(){
  86         if(!issourcenode){
  87             issourcenode=true;
  88             this.tasks=new Vector();
  89         }
  90     }
  91
  92     public void addAllocatingTask(TaskDescriptor task){
  93         tasks.add(task);
  94     }
  95
  96     public Vector getAllocatingTasks(){
  97         return tasks;
  98     }
  99
 100
 101     public String toString() {
 102         return cd.toString()+getTextLabel();
 103     }
 104
 105     /** @return Iterator over the flags in the flagstate.
 106      */
 107
 108     public Iterator getFlags() {
 109         return flagstate.iterator();
 110     }
 111
 112     public int numFlags(){
 113         return flagstate.size();
 114     }
 115
 116     public FlagState[] setTag(TagDescriptor tag, boolean set){
 117         HashSet newset1=(HashSet)flagstate.clone();
 118         Hashtable<TagDescriptor,Integer> newtags1=(Hashtable<TagDescriptor,Integer>)tags.clone();
 119
 120         if (set) {
 121             int count=0;
 122             if (tags.containsKey(tag))
 123                 count=tags.get(tag).intValue();
 124             if (count<KLIMIT)
 125                 count++;
 126             newtags1.put(tag, new Integer(count));
 127             return new FlagState[] {new FlagState(newset1, cd, newtags1)};
 128         } else {
 129             int count=1;
 130             if (tags.containsKey(tag))
 131                 count=tags.get(tag).intValue();
 132             newtags1.put(tag, new Integer(count));
 133             if ((count+1)==KLIMIT)
 134                 return new FlagState[] {this, new FlagState(newset1, cd, newtags1)};
 135             else
 136                 return new FlagState[] {new FlagState(newset1, cd, newtags1)};
 137         }
 138     }
 139
 140     public FlagState[] setTag(TagDescriptor tag){
 141         HashSet newset1=(HashSet)flagstate.clone();
 142         Hashtable<TagDescriptor,Integer> newtags1=(Hashtable<TagDescriptor,Integer>)tags.clone();
 143
 144         if (tags.containsKey(tag)){
 145             //Code could try to remove flag that doesn't exist
 146
 147             switch (tags.get(tag).intValue()){
 148             case ONETAG:
 149                 newtags1.put(tag,new Integer(MULTITAGS));
 150                 return new FlagState[] {this, new FlagState(newset1, cd, newtags1)};
 151             case MULTITAGS:
 152                 return new FlagState[] {this};
 153             default:
 154                 throw new Error();
 155             }
 156         } else {
 157             newtags1.put(tag,new Integer(ONETAG));
 158             return new FlagState[] {new FlagState(newset1,cd,newtags1)};
 159         }
 160     }
 161
 162     public int getTagCount(TagDescriptor tag) {
 163         if (tags.containsKey(tag))
 164             return tags.get(tag).intValue();
 165         else return 0;
 166     }
 167
 168     public int getTagCount(String tagtype){
 169         return getTagCount(new TagDescriptor(tagtype));
 170     }
 171
 172     public FlagState[] clearTag(TagDescriptor tag){
 173         if (tags.containsKey(tag)){
 174             switch(tags.get(tag).intValue()){
 175             case ONETAG:
 176                 HashSet newset=(HashSet)flagstate.clone();
 177                 Hashtable<TagDescriptor,Integer> newtags=(Hashtable<TagDescriptor,Integer>)tags.clone();
 178                 newtags.remove(tag);
 179                 return new FlagState[]{new FlagState(newset,cd,newtags)};
 180
 181             case MULTITAGS:
 182                 //two possibilities - count remains 2 or becomes 1
 183                 //2 case
 184                 HashSet newset1=(HashSet)flagstate.clone();
 185                 Hashtable<TagDescriptor,Integer> newtags1=(Hashtable<TagDescriptor,Integer>)tags.clone();
 186
 187                 //1 case
 188                 HashSet newset2=(HashSet)flagstate.clone();
 189                 Hashtable<TagDescriptor,Integer> newtags2=(Hashtable<TagDescriptor,Integer>)tags.clone();
 190                 newtags1.put(tag,new Integer(ONETAG));
 191                 return new FlagState[] {new FlagState(newset1, cd, newtags2),
 192                                         new FlagState(newset2, cd, newtags2)};
 193             default:
 194                 throw new Error();
 195             }
 196         } else {
 197             throw new Error("Invalid Operation: Can not clear a tag that doesn't exist.");
 198         }
 199     }
 200
 201     /** Creates a string description of the flagstate
 202      *  e.g.  a flagstate with five flags could look like 01001
 203      *  @param flags an array of flagdescriptors.
 204      *  @return string representation of the flagstate.
 205      */
 206     public String toString(FlagDescriptor[] flags)
 207     {
 208         StringBuffer sb = new StringBuffer(flagstate.size());
 209         for(int i=0;i < flags.length; i++)
 210             {
 211                 if (get(flags[i]))
 212                     sb.append(1);
 213                 else
 214                     sb.append(0);
 215             }
 216
 217         return new String(sb);
 218     }
 219
 220         /** Accessor method
 221          *  @return returns the classdescriptor of the flagstate.
 222          */
 223
 224     public ClassDescriptor getClassDescriptor(){
 225         return cd;
 226     }
 227
 228         /** Sets the status of a specific flag in a flagstate after cloning it.
 229          *  @param      fd FlagDescriptor of the flag whose status is being set.
 230          *  @param  status boolean value
 231          *  @return the new flagstate with <CODE>fd</CODE> set to <CODE>status</CODE>.
 232          */
 233
 234     public FlagState setFlag(FlagDescriptor fd, boolean status) {
 235         HashSet newset=(HashSet) flagstate.clone();
 236         Hashtable<TagDescriptor,Integer> newtags=(Hashtable<TagDescriptor,Integer>)tags.clone();
 237         if (status)
 238             newset.add(fd);
 239         else if (newset.contains(fd)){
 240             newset.remove(fd);
 241         }
 242
 243         return new FlagState(newset, cd, newtags);
 244     }
 245
 246     /** Tests for equality of two flagstate objects.
 247     */
 248
 249     public boolean equals(Object o) {
 250         if (o instanceof FlagState) {
 251             FlagState fs=(FlagState)o;
 252             if (fs.cd!=cd)
 253                 return false;
 254             return (fs.flagstate.equals(flagstate) & fs.tags.equals(tags));
 255         }
 256         return false;
 257     }
 258
 259     public int hashCode() {
 260         return cd.hashCode()^flagstate.hashCode()^tags.hashCode();
 261     }
 262
 263     public String getLabel() {
 264         return "N"+uid;
 265     }
 266
 267     public String getTextLabel() {
 268         String label=null;
 269         for(Iterator it=getFlags();it.hasNext();) {
 270             FlagDescriptor fd=(FlagDescriptor) it.next();
 271             if (label==null)
 272                 label=fd.toString();
 273             else
 274                 label+=", "+fd.toString();
 275         }
 276         for (Enumeration en_tags=getTags();en_tags.hasMoreElements();){
 277             TagDescriptor td=(TagDescriptor)en_tags.nextElement();
 278             switch (tags.get(td).intValue()){
 279             case ONETAG:
 280                 if (label==null)
 281                     label=td.toString()+"(1)";
 282                 else
 283                     label+=", "+td.toString()+"(1)";
 284                 break;
 285             case MULTITAGS:
 286                 if (label==null)
 287                     label=td.toString()+"(n)";
 288                 else
 289                     label+=", "+td.toString()+"(n)";
 290                 break;
 291             default:
 292                 break;
 293             }
 294         }
 295         if (label==null)
 296             return " ";
 297         return label;
 298     }
 299
 300     public Enumeration getTags(){
 301         return tags.keys();
 302     }
 303
 304     public int getExeTime() {
 305         try {
 306             if(this.executeTime == -1) {
 307                 calExeTime();
 308             }
 309         } catch (Exception e) {
 310             e.printStackTrace();
 311             System.exit(0);
 312         }
 313         return this.executeTime;
 314     }
 315
 316     public void setExeTime(int exeTime) {
 317         this.executeTime = exeTime;
 318     }
 319
 320     public void calExeTime() throws Exception {
 321         Iterator it = this.edges();
 322         if(it.hasNext()) {
 323             FEdge fe = (FEdge)it.next();
 324             if(fe.getExeTime() == -1) {
 325                 throw new Exception("Error: Uninitiate FEdge!");
 326             }
 327             this.executeTime = fe.getExeTime() + ((FlagState)fe.getTarget()).getExeTime();
 328         } else {
 329             this.executeTime = 0;
 330         }
 331         while(it.hasNext()) {
 332             FEdge fe = (FEdge)it.next();
 333             int temp = fe.getExeTime() + ((FlagState)fe.getTarget()).getExeTime();
 334             if(temp < this.executeTime) {
 335                 this.executeTime = temp;
 336             }
 337         }
 338     }
 339
 340     public Object clone() {
 341         FlagState o = null;
 342         try {
 343             o = (FlagState)super.clone();
 344         } catch(CloneNotSupportedException e){
 345             e.printStackTrace();
 346         }
 347         o.uid = FlagState.nodeid++;
 348         o.edges = new Vector();
 349         for(int i = 0; i < this.edges.size(); i++) {
 350             o.edges.addElement(this.edges.elementAt(i));
 351         }
 352         o.inedges = new Vector();
 353         for(int i = 0; i < this.inedges.size(); i++) {
 354             o.inedges.addElement(this.inedges.elementAt(i));
 355         }
 356         return o;
 357     }
 358
 359     public void init4Simulate() {
 360         this.invokeNum = 0;
 361     }
 362
 363     public FEdge process(TaskDescriptor td) {
 364         FEdge next = null;
 365         this.invokeNum++;
 366         // refresh all the expInvokeNum of each edge
 367         for(int i = 0; i < this.edges.size(); i++) {
 368             next = (FEdge)this.edges.elementAt(i);
 369             next.setExpInvokeNum((int)Math.round(this.invokeNum * (next.getProbability() / 100)));
 370         }
 371
 372         // find the one with the biggest gap between its actual invoke time and the expected invoke time
 373         // and associated with task td
 374         int index = 0;
 375         int gap = 0;
 376         for(int i = 0; i < this.edges.size(); i++) {
 377             int temp = ((FEdge)this.edges.elementAt(index)).getInvokeNumGap();
 378             if((temp > gap) && (next.getTask().equals(td))){
 379                 index = i;
 380                 gap = temp;
 381             }
 382         }
 383         next = (FEdge)this.edges.elementAt(index);
 384         next.process();
 385
 386         return next;
 387     }
 388 }