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

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