Robust/src/Analysis/TaskStateAnalysis/FlagState.java

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