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 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
 183       case MULTITAGS:
 184         return new FlagState[] {this};
 185
 186       default:
 187         throw new Error();
 188       }
 189     } else {
 190       newtags1.put(tag,new Integer(ONETAG));
 191       return new FlagState[] {new FlagState(newset1,cd,newtags1)};
 192     }
 193   }
 194
 195   public int getTagCount(TagDescriptor tag) {
 196     if (tags.containsKey(tag))
 197       return tags.get(tag).intValue();
 198     else return 0;
 199   }
 200
 201   public int getTagCount(String tagtype) {
 202     return getTagCount(new TagDescriptor(tagtype));
 203   }
 204
 205   public FlagState[] clearTag(TagDescriptor tag) {
 206     if (tags.containsKey(tag)){
 207       switch(tags.get(tag).intValue()){
 208       case ONETAG:
 209         HashSet newset=(HashSet)flagstate.clone();
 210         Hashtable<TagDescriptor,Integer> newtags=(Hashtable<TagDescriptor,Integer>)tags.clone();
 211         newtags.remove(tag);
 212         return new FlagState[] {new FlagState(newset,cd,newtags)};
 213
 214       case MULTITAGS:
 215         //two possibilities - count remains 2 or becomes 1
 216         //2 case
 217         HashSet newset1=(HashSet)flagstate.clone();
 218         Hashtable<TagDescriptor,Integer> newtags1=(Hashtable<TagDescriptor,Integer>)tags.clone();
 219
 220         //1 case
 221         HashSet newset2=(HashSet)flagstate.clone();
 222         Hashtable<TagDescriptor,Integer> newtags2=(Hashtable<TagDescriptor,Integer>)tags.clone();
 223         newtags1.put(tag,new Integer(ONETAG));
 224         return new FlagState[] {new FlagState(newset1, cd, newtags2),
 225                                 new FlagState(newset2, cd, newtags2)};
 226
 227       default:
 228         throw new Error();
 229       }
 230     } else {
 231       throw new Error("Invalid Operation: Can not clear a tag that doesn't exist.");
 232     }
 233   }
 234
 235   /** Creates a string description of the flagstate
 236    *  e.g.  a flagstate with five flags could look like 01001
 237    *  @param flags an array of flagdescriptors.
 238    *  @return string representation of the flagstate.
 239    */
 240   public String toString(FlagDescriptor[] flags) {
 241     StringBuffer sb = new StringBuffer(flagstate.size());
 242     for(int i=0; i < flags.length; i++)
 243     {
 244       if (get(flags[i]))
 245         sb.append(1);
 246       else
 247         sb.append(0);
 248     }
 249
 250     return new String(sb);
 251   }
 252
 253   /** Accessor method
 254    *  @return returns the classdescriptor of the flagstate.
 255    */
 256
 257   public ClassDescriptor getClassDescriptor() {
 258     return cd;
 259   }
 260
 261   /** Sets the status of a specific flag in a flagstate after cloning it.
 262    *  @param    fd FlagDescriptor of the flag whose status is being set.
 263    *  @param  status boolean value
 264    *  @return the new flagstate with <CODE>fd</CODE> set to <CODE>status</CODE>.
 265    */
 266
 267   public FlagState setFlag(FlagDescriptor fd, boolean status) {
 268     HashSet newset=(HashSet) flagstate.clone();
 269     Hashtable<TagDescriptor,Integer> newtags=(Hashtable<TagDescriptor,Integer>)tags.clone();
 270     if (status)
 271       newset.add(fd);
 272     else if (newset.contains(fd)){
 273       newset.remove(fd);
 274     }
 275
 276     return new FlagState(newset, cd, newtags);
 277   }
 278
 279   /** Tests for equality of two flagstate objects.
 280    */
 281
 282   public boolean equals(Object o) {
 283     if (o instanceof FlagState) {
 284       FlagState fs=(FlagState)o;
 285       if (fs.cd!=cd)
 286         return false;
 287       return (fs.flagstate.equals(flagstate) & fs.tags.equals(tags));
 288     }
 289     return false;
 290   }
 291
 292   public int hashCode() {
 293     return cd.hashCode()^flagstate.hashCode()^tags.hashCode();
 294   }
 295
 296   public String getLabel() {
 297     return "N"+uid;
 298   }
 299
 300   public String getTextLabel() {
 301     String label=null;
 302     for(Iterator it=getFlags(); it.hasNext();) {
 303       FlagDescriptor fd=(FlagDescriptor) it.next();
 304       if (label==null)
 305         label=fd.toString();
 306       else
 307         label+=", "+fd.toString();
 308     }
 309     for (Enumeration en_tags=getTags(); en_tags.hasMoreElements();){
 310       TagDescriptor td=(TagDescriptor)en_tags.nextElement();
 311       switch (tags.get(td).intValue()){
 312       case ONETAG:
 313         if (label==null)
 314           label=td.toString()+"(1)";
 315         else
 316           label+=", "+td.toString()+"(1)";
 317         break;
 318
 319       case MULTITAGS:
 320         if (label==null)
 321           label=td.toString()+"(n)";
 322         else
 323           label+=", "+td.toString()+"(n)";
 324         break;
 325
 326       default:
 327         break;
 328       }
 329     }
 330     if (label==null)
 331       return " ";
 332     return label;
 333   }
 334
 335   public Enumeration getTags() {
 336     return tags.keys();
 337   }
 338
 339   public int getExeTime() {
 340     try {
 341       if(this.executeTime == -1) {
 342         if(this.visited4time == -1) {
 343           this.visited4time = 0;
 344           calExeTime();
 345         } else {
 346           // visited, this node is in a loop
 347           // TODO
 348           // currently set 10 as the largest time
 349           this.executeTime = FlagState.MAXTIME;
 350         }
 351       }
 352     } catch (Exception e) {
 353       e.printStackTrace();
 354       System.exit(0);
 355     }
 356     return this.executeTime;
 357   }
 358
 359   public void setExeTime(int exeTime) {
 360     this.executeTime = exeTime;
 361   }
 362
 363   public int getAndmask() {
 364     return andmask;
 365   }
 366
 367   public void setAndmask(int andmask) {
 368     this.andmask = andmask;
 369   }
 370
 371   public int getCheckmask() {
 372     return checkmask;
 373   }
 374
 375   public void setCheckmask(int checkmask) {
 376     this.checkmask = checkmask;
 377   }
 378
 379   public void calExeTime() throws Exception {
 380     Iterator it = this.edges();
 381     if(it.hasNext()) {
 382       FEdge fe = (FEdge)it.next();
 383       while((fe != null) && (fe.getTarget().equals(this))) {
 384         if(it.hasNext()) {
 385           fe = (FEdge)it.next();
 386         } else {
 387           fe = null;
 388         }
 389       }
 390       if(fe == null) {
 391         this.executeTime = 0;
 392       } else {
 393         if(fe.getExeTime() == -1) {
 394           throw new Exception("Error: Uninitiate FEdge!");
 395         }
 396         this.executeTime = fe.getExeTime() + ((FlagState)fe.getTarget()).getExeTime();
 397       }
 398     } else {
 399       this.executeTime = 0;
 400     }
 401     while(it.hasNext()) {
 402       FEdge fe = (FEdge)it.next();
 403       int temp = fe.getExeTime() + ((FlagState)fe.getTarget()).getExeTime();
 404       if(temp < this.executeTime) {
 405         this.executeTime = temp;
 406       }
 407     }
 408   }
 409
 410   public Object clone() {
 411     FlagState o = null;
 412     try {
 413       o = (FlagState) super.clone();
 414     } catch(CloneNotSupportedException e){
 415       e.printStackTrace();
 416     }
 417     o.uid = FlagState.nodeid++;
 418     o.edges = new Vector();
 419     for(int i = 0; i < this.edges.size(); i++) {
 420       o.edges.addElement(this.edges.elementAt(i));
 421     }
 422     o.inedges = new Vector();
 423     for(int i = 0; i < this.inedges.size(); i++) {
 424       o.inedges.addElement(this.inedges.elementAt(i));
 425     }
 426     return o;
 427   }
 428
 429   public void init4Simulate() {
 430     this.invokeNum = 0;
 431   }
 432
 433   public FEdge process(TaskDescriptor td) {
 434     FEdge next = null;
 435     this.invokeNum++;
 436     // refresh all the expInvokeNum of each edge
 437     for(int i = 0; i < this.edges.size(); i++) {
 438       next = (FEdge) this.edges.elementAt(i);
 439       next.setExpInvokeNum((int)Math.round(this.invokeNum * (next.getProbability() / 100)));
 440     }
 441
 442     // find the one with the biggest gap between its actual invoke time and the expected invoke time
 443     // and associated with task td
 444     int index = 0;
 445     int gap = 0;
 446     for(int i = 0; i < this.edges.size(); i++) {
 447       int temp = ((FEdge) this.edges.elementAt(index)).getInvokeNumGap();
 448       if((temp > gap) && (next.getTask().equals(td))){
 449         index = i;
 450         gap = temp;
 451       }
 452     }
 453     next = (FEdge) this.edges.elementAt(index);
 454     next.process();
 455
 456     return next;
 457   }
 458
 459   /*public Vector<ScheduleEdge> getAllys() {
 460       return allys;
 461      }
 462
 463      public void addAlly(ScheduleEdge se) {
 464       if(this.allys == null) {
 465           assert(this.isolate == true);
 466           this.isolate = false;
 467           this.allys = new Vector<ScheduleEdge>();
 468       }
 469       this.allys.addElement(se);
 470      }
 471
 472      public boolean isIsolate() {
 473       return isolate;
 474      }*/
 475
 476 }