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