Robust/src/Analysis/Prefetch/PrefetchAnalysis.java

   1 package Analysis.Prefetch;
   2
   3 import java.util.*;
   4 import Analysis.CallGraph.CallGraph;
   5 import Analysis.Prefetch.PrefetchPair;
   6 import Analysis.Prefetch.IndexDescriptor;
   7 import IR.SymbolTable;
   8 import IR.State;
   9 import IR.TypeUtil;
  10 import IR.MethodDescriptor;
  11 import IR.Flat.*;
  12 import IR.*;
  13 import IR.ClassDescriptor;
  14
  15 public class PrefetchAnalysis {
  16     State state;
  17     CallGraph callgraph;
  18     TypeUtil typeutil;
  19     Set<FlatNode> tovisit;
  20     Hashtable<FlatNode, Hashtable<PrefetchPair, Float>> prefetch_hash;
  21     Hashtable<PrefetchPair, Float> branch_prefetch_set;
  22     public static final int ROUNDED_MODE = 30;
  23     public static final float THRESHOLD_PROB = (float)0.30;
  24     public static final float BRANCH_TRUE_EDGE_PROB = (float)0.5;
  25     public static final float BRANCH_FALSE_EDGE_PROB = (float)0.5;
  26
  27     /** This function finds if a tempdescriptor object is found in a given prefetch pair
  28      *  It returns true if found else returns false*/
  29     private boolean isTempDescFound(PrefetchPair pp, TempDescriptor td) {
  30             ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  31             ListIterator it = desc.listIterator();
  32             for(;it.hasNext();) {
  33                     Object o = it.next();
  34                     if(o instanceof IndexDescriptor) {
  35                             ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
  36                             if(tdarray.contains(td)) {
  37                                     return true;
  38                             }
  39                     }
  40             }
  41             return false;
  42     }
  43
  44     /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
  45      * tempdescriptors when there is a match for FlatOpNodes or FlatLiteralNodes */
  46
  47     private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor newtd) {
  48             ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  49             ListIterator it = desc.listIterator();
  50             for(;it.hasNext();) {
  51                     Object currdesc = it.next();
  52                     if(currdesc instanceof IndexDescriptor) {
  53                             ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
  54                             if(tdarray.contains(td)) {
  55                                     int index = tdarray.indexOf(td);
  56                                     tdarray.set(index, newtd);
  57                             }
  58                     }
  59             }
  60             return desc;
  61     }
  62
  63     /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
  64      * tempdescriptors when there is a match for FlatOpNodes i= i+j then replace i with i+j */
  65     private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor left, TempDescriptor right) {
  66             ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  67             ListIterator it = desc.listIterator();
  68             for(;it.hasNext();) {
  69                     Object currdesc = it.next();
  70                     if(currdesc instanceof IndexDescriptor) {
  71                             ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
  72                             if(tdarray.contains(td)) {
  73                                     int index = tdarray.indexOf(td);
  74                                     tdarray.set(index, left);
  75                                     tdarray.add(right);
  76                             }
  77                     }
  78             }
  79             return desc;
  80     }
  81
  82     public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
  83             this.typeutil=typeutil;
  84             this.state=state;
  85             this.callgraph=callgraph;
  86             prefetch_hash = new Hashtable<FlatNode, Hashtable<PrefetchPair,Float>>();
  87             DoPrefetch();
  88     }
  89
  90     /** This function starts the prefetch analysis */
  91     private void DoPrefetch() {
  92             Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
  93             while(classit.hasNext()) {
  94                     ClassDescriptor cn=(ClassDescriptor)classit.next();
  95                     doMethodAnalysis(cn);
  96             }
  97     }
  98
  99     /** This function calls analysis for every method in a class */
 100     private void doMethodAnalysis(ClassDescriptor cn) {
 101             Iterator methodit=cn.getMethods();
 102             while(methodit.hasNext()) {
 103                     /* Classify parameters */
 104                     MethodDescriptor md=(MethodDescriptor)methodit.next();
 105                     FlatMethod fm=state.getMethodFlat(md);
 106                     doFlatNodeAnalysis(fm);
 107             }
 108     }
 109
 110     /** This function calls analysis for every node in a method */
 111     private void doFlatNodeAnalysis(FlatMethod fm) {
 112             tovisit = fm.getNodeSet(); //Flat nodes to process
 113             Hashtable<PrefetchPair, Float> nodehash = new Hashtable<PrefetchPair, Float>();
 114             /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
 115             while(!tovisit.isEmpty()) {
 116                     FlatNode fn = (FlatNode)tovisit.iterator().next();
 117                     prefetch_hash.put(fn, nodehash);
 118                     tovisit.remove(fn);
 119             }
 120             tovisit = fm.getNodeSet(); //Flat nodes to process
 121             while(!tovisit.isEmpty()) {
 122                     FlatNode fn = (FlatNode)tovisit.iterator().next();
 123                     /* Generate prefetch pairs after the child node analysis */
 124                     doChildNodeAnalysis(fn);
 125                     tovisit.remove(fn);
 126             }
 127     }
 128
 129     /**
 130      * This function generates the prefetch sets for a given Flatnode considering the kind of node
 131      * It calls severals functions based on the kind of the node and
 132      * returns true: if the prefetch set has changed since last time the node was analysed
 133      * returns false : otherwise
 134      */
 135     private void doChildNodeAnalysis(FlatNode curr) {
 136             Hashtable<PrefetchPair, Float> child_hash = new Hashtable<PrefetchPair, Float>();
 137             if(curr.kind()==FKind.FlatCondBranch) {
 138                     branch_prefetch_set =  new Hashtable<PrefetchPair,Float>();
 139             }
 140             for (int i = 0; i < curr.numNext(); i++) {
 141                     FlatNode child_node = curr.getNext(i);
 142                     if (prefetch_hash.containsKey(child_node)) {
 143                             child_hash = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
 144                     }
 145                     switch(curr.kind()) {
 146                             case FKind.FlatBackEdge:
 147                                     processDefaultCase(curr,child_hash);
 148                                     break;
 149                             case FKind.FlatCall:
 150                                     //TODO change it to take care of FlatMethod, Flatcalls
 151                                     processFlatCall(curr, child_hash);
 152                                     break;
 153                             case FKind.FlatCheckNode:
 154                                     processDefaultCase(curr,child_hash);
 155                                     break;
 156                             case FKind.FlatMethod:
 157                                     //TODO change it to take care of FlatMethod, Flatcalls
 158                                     processFlatMethod(curr, child_hash);
 159                                     break;
 160                             case FKind.FlatNew:
 161                                     processFlatNewNode(curr, child_hash);
 162                                     break;
 163                             case FKind.FlatReturnNode:
 164                                     //TODO change it to take care of FlatMethod, Flatcalls
 165                                     processDefaultCase(curr,child_hash);
 166                                     break;
 167                             case FKind.FlatFieldNode:
 168                                     processFlatFieldNode(curr, child_hash);
 169                                     break;
 170                             case FKind.FlatElementNode:
 171                                     processFlatElementNode(curr, child_hash);
 172                                     break;
 173                             case FKind.FlatCondBranch:
 174                                     processFlatCondBranch(curr, child_hash, i, branch_prefetch_set);
 175                                     break;
 176                             case FKind.FlatOpNode:
 177                                     processFlatOpNode(curr, child_hash);
 178                                     break;
 179                             case FKind.FlatLiteralNode:
 180                                     processFlatLiteralNode(curr, child_hash);
 181                                     break;
 182                             case FKind.FlatSetElementNode:
 183                                     processFlatSetElementNode(curr, child_hash);
 184                                     break;
 185                             case FKind.FlatSetFieldNode:
 186                                     processFlatSetFieldNode(curr, child_hash);
 187                                     break;
 188                             case FKind.FlatAtomicEnterNode:
 189                                     processDefaultCase(curr,child_hash);
 190                                     break;
 191                             case FKind.FlatAtomicExitNode:
 192                                     processDefaultCase(curr,child_hash);
 193                                     break;
 194                             case FKind.FlatCastNode:
 195                                     processDefaultCase(curr,child_hash);
 196                                     break;
 197                             case FKind.FlatFlagActionNode:
 198                                     processDefaultCase(curr,child_hash);
 199                                     break;
 200                             case FKind.FlatGlobalConvNode:
 201                                     processDefaultCase(curr,child_hash);
 202                                     break;
 203                             case FKind.FlatNop:
 204                                     processDefaultCase(curr,child_hash);
 205                                     break;
 206                             case FKind.FlatTagDeclaration:
 207                                     processDefaultCase(curr,child_hash);
 208                                     break;
 209                             default:
 210                                     System.out.println("NO SUCH FLATNODE");
 211                                     break;
 212                     }
 213             }
 214     }
 215
 216     /**This function compares all the prefetch pairs in a Prefetch set hashtable and
 217      * returns: true if something has changed in the new Prefetch set else
 218      * returns: false
 219      */
 220     private boolean comparePrefetchSets(Hashtable<PrefetchPair, Float> oldPrefetchSet, Hashtable<PrefetchPair, Float>
 221                     newPrefetchSet) {
 222             boolean hasChanged = false;
 223             PrefetchPair oldpp = null;
 224             PrefetchPair newpp = null;
 225
 226             if(oldPrefetchSet.size() != newPrefetchSet.size()) {
 227                     return true;
 228             } else {
 229                     Enumeration e = newPrefetchSet.keys();
 230                     while(e.hasMoreElements()) {
 231                             newpp = (PrefetchPair) e.nextElement();
 232                             float newprob = newPrefetchSet.get(newpp);
 233                             for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) {
 234                                     oldpp = (PrefetchPair) elem.nextElement();
 235                                     if(oldpp.equals(newpp)) {
 236                                             /*Compare the difference in their probabilities */
 237                                             float oldprob = oldPrefetchSet.get(oldpp);
 238                                             int diff = (int) ((newprob - oldprob)/oldprob)*100;
 239                                             if(diff >= ROUNDED_MODE) {
 240                                                     return true;
 241                                             }else {
 242                                             }
 243                                             break;
 244                                     }
 245                             }
 246                     }
 247             }
 248             return hasChanged;
 249     }
 250
 251     /** This function processes the prefetch set of FlatFieldNode
 252      * It generates a new prefetch set after comparision with its children
 253      * Then compares it with its old prefetch set
 254      * If old prefetch set is not same as new prefetch set then enqueue the parents
 255      * of the current FlatFieldNode
 256      * */
 257     private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 258             boolean pSetHasChanged = false;
 259             Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
 260             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 261             FlatFieldNode currffn = (FlatFieldNode) curr;
 262
 263             /* Do Self analysis of the current node*/
 264             FieldDescriptor currffn_field =  currffn.getField();
 265             TempDescriptor currffn_src = currffn.getSrc();
 266             if (currffn_field.getType().isPtr()) {
 267                     PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
 268                     Float prob = new Float((float)1.0);
 269                     currcopy.put(pp, prob);
 270             }
 271
 272             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 273             Enumeration ecld = child_hash.keys();
 274             PrefetchPair currpp = null;
 275             PrefetchPair childpp = null;
 276             while (ecld.hasMoreElements()) {
 277                     childpp = (PrefetchPair) ecld.nextElement();
 278                     if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
 279                             if (currffn.getField().getType().isPtr()) {
 280                                     /* Create a new Prefetch set*/
 281                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 282                                     newdesc.add(currffn.getField());
 283                                     newdesc.addAll(childpp.desc);
 284                                     PrefetchPair newpp =  new PrefetchPair(currffn.getSrc(), newdesc);
 285                                     Float newprob = child_hash.get(childpp).floatValue();
 286                                     tocompare.put(newpp, newprob);
 287                                     child_hash.remove(childpp);
 288                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 289                                      * to compute new probability */
 290                                     if(child_hash.containsKey(newpp)) {
 291                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 292                                             if(newprob < THRESHOLD_PROB) {
 293                                                     tocompare.remove(newpp);
 294                                             } else {
 295                                                     tocompare.put(newpp, newprob);
 296                                             }
 297                                             child_hash.remove(newpp);
 298                                     }
 299                             }
 300                     } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
 301                             child_hash.remove(childpp);
 302                     } else {
 303                             continue;
 304                     }
 305             }
 306             /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 307              * if so calculate the new probability and then remove the common one from the child prefetch set */
 308             ecld = child_hash.keys();
 309             Enumeration e = null;
 310             while(ecld.hasMoreElements()) {
 311                     childpp = (PrefetchPair) ecld.nextElement();
 312                     for(e = currcopy.keys(); e.hasMoreElements();) {
 313                             currpp = (PrefetchPair) e.nextElement();
 314                             if(currpp.equals(childpp)) {
 315                                     /* Probability of the incoming edge for a FlatFieldNode is always 100% */
 316                                     Float prob = currcopy.get(currpp).floatValue();
 317                                     currcopy.put(currpp, prob);
 318                                     child_hash.remove(childpp);
 319                                     break;
 320                             }
 321                     }
 322             }
 323
 324             /* Merge child prefetch pairs */
 325             ecld = child_hash.keys();
 326             while(ecld.hasMoreElements()) {
 327                     childpp = (PrefetchPair) ecld.nextElement();
 328                     tocompare.put(childpp, child_hash.get(childpp));
 329                     child_hash.remove(childpp);
 330             }
 331
 332             /* Merge curr prefetch pairs */
 333             e = currcopy.keys();
 334             while(e.hasMoreElements()) {
 335                     currpp = (PrefetchPair) e.nextElement();
 336                     tocompare.put(currpp, currcopy.get(currpp));
 337                     currcopy.remove(currpp);
 338             }
 339
 340             /* Compare with the orginal prefetch pairs */
 341             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 342             /* Enqueue parent nodes */
 343             if(pSetHasChanged) {
 344                     for(int i=0; i<curr.numPrev(); i++) {
 345                             tovisit.add(curr.getPrev(i));
 346                     }
 347                     /* Overwrite the new prefetch set to the global hash table */
 348                     prefetch_hash.put(curr,tocompare);
 349             }
 350     }
 351
 352     /** This function processes the prefetch set of a FlatElementNode
 353      * It generates a new prefetch set after comparision with its children
 354      * It compares the old prefetch set with this new prefetch set and enqueues the parents
 355      * of the current node if change occurs and updates the global flatnode hash table
 356      * */
 357     private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 358
 359             boolean pSetHasChanged = false;
 360             Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
 361             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 362             FlatElementNode currfen = (FlatElementNode) curr;
 363
 364
 365             /* Do Self analysis of the current node*/
 366             TempDescriptor currfen_index = currfen.getIndex();
 367             IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
 368             TempDescriptor currfen_src = currfen.getSrc();
 369             if(currfen.getDst().getType().isPtr()) {
 370                     PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
 371                     Float prob = new Float((float)1.0);
 372                     currcopy.put(pp, prob);
 373             }
 374
 375             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 376             Enumeration ecld = child_hash.keys();
 377             PrefetchPair currpp = null;
 378             PrefetchPair childpp = null;
 379             while (ecld.hasMoreElements()) {
 380                     childpp = (PrefetchPair) ecld.nextElement();
 381                     if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
 382                             if (currfen.getDst().getType().isPtr()) {
 383                                     //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table
 384                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 385                                     newdesc.add((Descriptor)idesc);
 386                                     newdesc.addAll(childpp.desc);
 387                                     PrefetchPair newpp =  new PrefetchPair(currfen.getSrc(), newdesc);
 388                                     Float newprob = child_hash.get(childpp).floatValue();
 389                                     tocompare.put(newpp, newprob);
 390                                     child_hash.remove(childpp);
 391                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 392                                      * to compute new probability */
 393                                     if(child_hash.containsKey(newpp)) {
 394                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 395                                             if(newprob < THRESHOLD_PROB) {
 396                                                     tocompare.remove(newpp);
 397                                             } else {
 398                                                     tocompare.put(newpp, newprob);
 399                                             }
 400                                             child_hash.remove(newpp);
 401                                     }
 402                             }
 403                     } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
 404                             child_hash.remove(childpp);
 405                     }
 406             }
 407             /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 408              * if so calculate the new probability and then remove the common one from the child prefetch set */
 409             ecld = child_hash.keys();
 410             Enumeration e = null;
 411             while(ecld.hasMoreElements()) {
 412                     childpp = (PrefetchPair) ecld.nextElement();
 413                     for(e = currcopy.keys(); e.hasMoreElements();) {
 414                             currpp = (PrefetchPair) e.nextElement();
 415                             if(currpp.equals(childpp)) {
 416                                     /* Probability of the incoming edge for a FlatElementNode is always 100% */
 417                                     Float prob = currcopy.get(currpp).floatValue();
 418                                     currcopy.put(currpp, prob);
 419                                     child_hash.remove(childpp);
 420                                     break;
 421                             }
 422                     }
 423             }
 424
 425             /* Merge child prefetch pairs */
 426             ecld = child_hash.keys();
 427             while(ecld.hasMoreElements()) {
 428                     childpp = (PrefetchPair) ecld.nextElement();
 429                     tocompare.put(childpp, child_hash.get(childpp));
 430                     child_hash.remove(childpp);
 431             }
 432
 433             /* Merge curr prefetch pairs */
 434             e = currcopy.keys();
 435             while(e.hasMoreElements()) {
 436                     currpp = (PrefetchPair) e.nextElement();
 437                     tocompare.put(currpp, currcopy.get(currpp));
 438                     currcopy.remove(currpp);
 439             }
 440
 441             /* Compare with the orginal prefetch pairs */
 442             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 443             /* Enqueue parent nodes */
 444             if(pSetHasChanged) {
 445                     for(int i=0; i<curr.numPrev(); i++) {
 446                             tovisit.add(curr.getPrev(i));
 447                     }
 448                     /* Overwrite the new prefetch set to the global hash table */
 449                     prefetch_hash.put(curr,tocompare);
 450             }
 451     }
 452
 453     /** This function processes the prefetch set of a FlatSetFieldNode
 454      * It generates a new prefetch set after comparision with its children
 455      * It compares the old prefetch set with this new prefetch set and enqueues the parents
 456      * of the current node if change occurs and then updates the global flatnode hash table
 457      * */
 458     private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 459             boolean pSetHasChanged = false;
 460             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 461             FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
 462             PrefetchPair childpp = null;
 463
 464             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 465             Enumeration ecld = child_hash.keys();
 466             while (ecld.hasMoreElements()) {
 467                     childpp = (PrefetchPair) ecld.nextElement();
 468                     if(childpp.base == currfsfn.getDst()) {
 469                             int size = childpp.desc.size();
 470                             if(size >=2) {
 471                                     if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 472                                             ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 473                                             for(int i = 0;i<(childpp.desc.size()-1); i++) {
 474                                                     newdesc.add(i,childpp.desc.get(i+1));
 475                                             }
 476                                             PrefetchPair newpp =  new PrefetchPair(currfsfn.getSrc(), newdesc);
 477                                             Float newprob = child_hash.get(childpp).floatValue();
 478                                             tocompare.put(newpp, newprob);
 479                                             child_hash.remove(childpp);
 480                                             /* Check for independence of prefetch pairs in newly generated and child_hash prefetch pairs
 481                                              * to compute new probability */
 482                                             if(child_hash.containsKey(newpp)) {
 483                                                     newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 484                                                     if(newprob < THRESHOLD_PROB) {
 485                                                             tocompare.remove(newpp);
 486                                                     } else {
 487                                                             tocompare.put(newpp, newprob);
 488                                                     }
 489                                                     child_hash.remove(newpp);
 490                                             }
 491                                     }
 492                             } else if(size==1) {
 493                                     if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 494                                             child_hash.remove(childpp);
 495                                     }
 496                             } else {
 497                                     continue;
 498                             }
 499                     }
 500             }
 501
 502             /* Merge child prefetch pairs */
 503             ecld = child_hash.keys();
 504             while(ecld.hasMoreElements()) {
 505                     childpp = (PrefetchPair) ecld.nextElement();
 506                     tocompare.put(childpp, child_hash.get(childpp));
 507                     child_hash.remove(childpp);
 508             }
 509
 510             /* Compare with the orginal prefetch pairs */
 511             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 512             /* Enqueue parent nodes */
 513             if(pSetHasChanged) {
 514                     for(int i=0; i<curr.numPrev(); i++) {
 515                             tovisit.add(curr.getPrev(i));
 516                     }
 517                     /* Overwrite the new prefetch set to the global hash table */
 518                     prefetch_hash.put(curr,tocompare);
 519             }
 520     }
 521
 522     /** This function processes the prefetch set of a FlatSeElementNode
 523      * It generates a new prefetch set after comparision with its children
 524      * It compares the old prefetch set with this new prefetch set and enqueues the parents
 525      * of the current node if change occurs and then updates the global flatnode hash table
 526      * */
 527     private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 528             boolean pSetHasChanged = false;
 529             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 530             PrefetchPair childpp = null;
 531             FlatSetElementNode currfsen = (FlatSetElementNode) curr;
 532
 533             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 534             Enumeration ecld = child_hash.keys();
 535             while (ecld.hasMoreElements()) {
 536                     childpp = (PrefetchPair) ecld.nextElement();
 537                     if (childpp.base == currfsen.getDst()){
 538                             int sizedesc = childpp.desc.size();
 539                             if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
 540                                     int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
 541                                     if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizetempdesc==1) && (sizedesc>=2)) {
 542                                             //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table
 543                                             ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 544                                             for(int i = 0;i<(childpp.desc.size()-1); i++) {
 545                                                     newdesc.add(i,childpp.desc.get(i+1));
 546                                             }
 547                                             PrefetchPair newpp =  new PrefetchPair(currfsen.getSrc(), newdesc);
 548                                             Float newprob = child_hash.get(childpp).floatValue();
 549                                             tocompare.put(newpp, newprob);
 550                                             child_hash.remove(childpp);
 551                                             /* Check for independence of prefetch pairs if any in the child prefetch set
 552                                              * to compute new probability */
 553                                             if(child_hash.containsKey(newpp)) {
 554                                                     newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 555                                                     if(newprob < THRESHOLD_PROB) {
 556                                                             tocompare.remove(newpp);
 557                                                     } else {
 558                                                             tocompare.put(newpp, newprob);
 559                                                     }
 560                                                     child_hash.remove(newpp);
 561                                             }
 562                                     } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizetempdesc==1) && (sizedesc==1)) {
 563                                             child_hash.remove(childpp);
 564                                     } else {
 565                                             continue;
 566                                     }
 567                             }
 568                     }
 569             }
 570             /* Merge child prefetch pairs */
 571             ecld = child_hash.keys();
 572             while(ecld.hasMoreElements()) {
 573                     childpp = (PrefetchPair) ecld.nextElement();
 574                     tocompare.put(childpp, child_hash.get(childpp));
 575                     child_hash.remove(childpp);
 576             }
 577             /* Compare with the orginal prefetch pairs */
 578             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 579             /* Enqueue parent nodes */
 580             if(pSetHasChanged) {
 581                     for(int i=0; i<curr.numPrev(); i++) {
 582                             tovisit.add(curr.getPrev(i));
 583                     }
 584                     /* Overwrite the new prefetch set to the global hash table */
 585                     prefetch_hash.put(curr,tocompare);
 586             }
 587     }
 588
 589     /** This function applies rules and does analysis for a FlatOpNode
 590      *  And updates the global prefetch hashtable
 591      * */
 592     private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 593             boolean pSetHasChanged = false;
 594             int index;
 595             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 596             FlatOpNode currfopn = (FlatOpNode) curr;
 597             Enumeration ecld = null;
 598             PrefetchPair childpp = null;
 599
 600             /* Check the  Operation type of flatOpNode */
 601             if(currfopn.getOp().getOp()== Operation.ASSIGN) {
 602                     ecld = child_hash.keys();
 603                     while (ecld.hasMoreElements()) {
 604                             childpp = (PrefetchPair) ecld.nextElement();
 605                             PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 606
 607                             /* Base of child prefetch pair same as destination of the current FlatOpNode
 608                              * For cases like x=y followed by childnode t=x[i].z or t=x.g*/
 609                             if(childpp.base == currfopn.getDest()) {
 610                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 611                                     newdesc.addAll(childpp.desc);
 612                                     PrefetchPair newpp =  new PrefetchPair(currfopn.getLeft(), newdesc);
 613                                     Float newprob = child_hash.get(childpp).floatValue();
 614                                     tocompare.put(newpp, newprob);
 615                                     child_hash.remove(childpp);
 616                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 617                                      * to compute new probability */
 618                                     if(child_hash.containsKey(newpp)) {
 619                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 620                                             if(newprob < THRESHOLD_PROB) {
 621                                                     tocompare.remove(newpp);
 622                                             } else {
 623                                                     tocompare.put(newpp, newprob);
 624                                             }
 625                                             child_hash.remove(newpp);
 626                                     }
 627                                     /* Any member of the desc of child prefetch pair is same as destination of the current FlatOpNode
 628                                      * For cases like x=y followed by t = r[i].x or t =r[x].p or t = r[p+x].q*/
 629                             } else if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
 630                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 631                                     newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft()));
 632                                     PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 633                                     Float newprob = child_hash.get(childpp).floatValue();
 634                                     tocompare.put(newpp, newprob);
 635                                     child_hash.remove(childpp);
 636                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 637                                      * to compute new probability*/
 638                                     if(child_hash.containsKey(newpp)) {
 639                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 640                                             if(newprob < THRESHOLD_PROB) {
 641                                                     tocompare.remove(newpp);
 642                                             } else {
 643                                                     tocompare.put(newpp, newprob);
 644                                             }
 645                                             child_hash.remove(newpp);
 646                                     }
 647                             }else {
 648                                     continue;
 649                             }
 650                     }
 651             } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
 652                     //case i = i+z  followed by a[i].x
 653                     ecld = child_hash.keys();
 654                     while (ecld.hasMoreElements()) {
 655                             childpp = (PrefetchPair) ecld.nextElement();
 656                             PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 657
 658                             if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
 659                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 660                                     newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft(), currfopn.getRight()));
 661                                     PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 662                                     Float newprob = child_hash.get(childpp).floatValue();
 663                                     tocompare.put(newpp, newprob);
 664                                     child_hash.remove(childpp);
 665                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 666                                      * to compute new probability*/
 667                                     if(child_hash.containsKey(newpp)) {
 668                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 669                                             if(newprob < THRESHOLD_PROB) {
 670                                                     tocompare.remove(newpp);
 671                                             } else {
 672                                                     tocompare.put(newpp, newprob);
 673                                             }
 674                                             child_hash.remove(newpp);
 675                                     }
 676                             }else {
 677                                     continue;
 678                             }
 679                     }
 680             } else {
 681                     //FIXME Is not taken care of for cases like x = -y followed by a[x].i
 682             }
 683
 684             /* Merge child prefetch pairs */
 685             ecld = child_hash.keys();
 686             while(ecld.hasMoreElements()) {
 687                     childpp = (PrefetchPair) ecld.nextElement();
 688                     tocompare.put(childpp, child_hash.get(childpp));
 689                     child_hash.remove(childpp);
 690             }
 691
 692             /* Compare with the orginal prefetch pairs */
 693             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 694             /* Enqueue parent nodes */
 695             if(pSetHasChanged) {
 696                     for(int i=0; i<curr.numPrev(); i++) {
 697                             tovisit.add(curr.getPrev(i));
 698                     }
 699                     /* Overwrite the new prefetch set to the global hash table */
 700                     prefetch_hash.put(curr,tocompare);
 701             }
 702     }
 703
 704     private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 705             boolean pSetHasChanged = false;
 706             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 707             FlatLiteralNode currfln = (FlatLiteralNode) curr;
 708             Enumeration ecld = null;
 709             PrefetchPair childpp = null;
 710
 711             if(currfln.getType().isIntegerType()) {
 712                     ecld = child_hash.keys();
 713                     while (ecld.hasMoreElements()) {
 714                             childpp = (PrefetchPair) ecld.nextElement();
 715                             PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 716                             /* Check for same index in child prefetch pairs
 717                              * for cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r*/
 718                             if(isTempDescFound(copyofchildpp,currfln.getDst())) {
 719                                     ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
 720                                     ListIterator it = copychilddesc.listIterator();
 721                                     for(;it.hasNext();) {
 722                                             Object o = it.next();
 723                                             if(o instanceof IndexDescriptor) {
 724                                                     ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
 725                                                     if(td.contains(currfln.getDst())) {
 726                                                             int index = td.indexOf(currfln.getDst());
 727                                                             ((IndexDescriptor)o).offset = (Integer)currfln.getValue();
 728                                                             td.remove(index);
 729                                                     }
 730                                             }
 731                                     }
 732                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 733                                     newdesc.addAll(copychilddesc);
 734                                     PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 735                                     Float newprob = (child_hash.get(childpp)).floatValue();
 736                                     tocompare.put(newpp, newprob);
 737                                     child_hash.remove(childpp);
 738                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 739                                      * to compute new probability */
 740                                     if(child_hash.containsKey(newpp)) {
 741                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 742                                             if(newprob < THRESHOLD_PROB) {
 743                                                     tocompare.remove(newpp);
 744                                             } else {
 745                                                     tocompare.put(newpp, newprob);
 746                                             }
 747                                             child_hash.remove(newpp);
 748                                     }
 749                             }
 750                     }
 751             }
 752
 753             /* Merge child prefetch pairs */
 754             ecld = child_hash.keys();
 755             while(ecld.hasMoreElements()) {
 756                     childpp = (PrefetchPair) ecld.nextElement();
 757                     tocompare.put(childpp, child_hash.get(childpp));
 758                     child_hash.remove(childpp);
 759             }
 760
 761             /* Compare with the orginal prefetch pairs */
 762             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 763             /* Enqueue parent nodes */
 764             if(pSetHasChanged) {
 765                     for(int i=0; i<curr.numPrev(); i++) {
 766                             tovisit.add(curr.getPrev(i));
 767                     }
 768                     /* Overwrite the new prefetch set to the global hash table */
 769                     prefetch_hash.put(curr,tocompare);
 770             }
 771
 772     }
 773
 774     private void processFlatMethod(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 775             boolean pSetHasChanged = false;
 776             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 777             FlatMethod currfm = (FlatMethod) curr;
 778             Enumeration ecld = null;
 779             PrefetchPair childpp = null;
 780
 781             /* Merge child prefetch pairs */
 782             ecld = child_hash.keys();
 783             while(ecld.hasMoreElements()) {
 784                     childpp = (PrefetchPair) ecld.nextElement();
 785                     tocompare.put(childpp, child_hash.get(childpp));
 786                     child_hash.remove(childpp);
 787             }
 788
 789             /* Compare with the orginal prefetch pairs */
 790             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 791             /* Enqueue parent nodes */
 792             if(pSetHasChanged) {
 793                     /* Overwrite the new prefetch set to the global hash table */
 794                     prefetch_hash.put(curr,tocompare);
 795             }
 796     }
 797
 798     /** This Function processes the FlatCalls
 799      * It currently drops the propagation of those prefetchpairs that are passed as
 800      * arguments in the FlatCall
 801      */
 802
 803     private void processFlatCall(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 804             boolean pSetHasChanged = false;
 805             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 806             FlatCall currfcn = (FlatCall) curr;
 807             Enumeration ecld = null;
 808             PrefetchPair childpp = null;
 809             boolean isSameArg = false;
 810
 811             for(int i= 0; i<currfcn.numArgs(); i++) {
 812             }
 813
 814             ecld = child_hash.keys();
 815             while(ecld.hasMoreElements()) {
 816                     childpp = (PrefetchPair) ecld.nextElement();
 817                     PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 818                     int numargs = currfcn.numArgs();
 819                     for(int i= 0; i<currfcn.numArgs(); i++) {
 820                             if(currfcn.getArg(i) == childpp.base){
 821                                     isSameArg = true;
 822                             }
 823                     }
 824                     if(!(currfcn.getThis() == childpp.base) && !(isSameArg)) {
 825                             tocompare.put(childpp, child_hash.get(childpp));
 826                             child_hash.remove(childpp);
 827                     } else {
 828                             child_hash.remove(childpp);
 829                     }
 830             }
 831
 832             /* Compare with the orginal prefetch pairs */
 833             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 834             /* Enqueue parent nodes */
 835             if(pSetHasChanged) {
 836                     for(int i=0; i<curr.numPrev(); i++) {
 837                             tovisit.add(curr.getPrev(i));
 838                     }
 839                     /* Overwrite the new prefetch set to the global hash table */
 840                     prefetch_hash.put(curr,tocompare);
 841             }
 842     }
 843
 844     /** This function handles the processes the FlatNode of type FlatCondBranch
 845      * It combines prefetches of both child elements and create a new hash table called
 846      * branch_prefetch_set to contains the entries of both its children
 847      */
 848     private void processFlatCondBranch(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash, int index,
 849                     Hashtable<PrefetchPair,Float> branch_prefetch_set) {
 850             boolean pSetHasChanged = false;
 851             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 852             FlatCondBranch currfcb = (FlatCondBranch) curr;
 853             Float newprob = new Float((float)0.0);
 854             PrefetchPair childpp = null;
 855             PrefetchPair pp = null;
 856             Enumeration ecld = null;
 857
 858             ecld = child_hash.keys();
 859             while (ecld.hasMoreElements()) {
 860                     childpp = (PrefetchPair) ecld.nextElement();
 861                     /* Create a new Prefetch set*/
 862                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 863                     newdesc.addAll(childpp.desc);
 864                     PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 865                     /* True Edge */
 866                     if(index == 0) {
 867                             newprob = child_hash.get(childpp).floatValue() * BRANCH_TRUE_EDGE_PROB;
 868                             if(newprob >= THRESHOLD_PROB) {
 869                                     tocompare.put(newpp, newprob);
 870                                     child_hash.remove(newpp);
 871                             }
 872                     } else if(index == 1) { /* False Edge */
 873                             newprob = child_hash.get(childpp).floatValue() * BRANCH_FALSE_EDGE_PROB;
 874                             if(newprob >= THRESHOLD_PROB) {
 875                                     tocompare.put(newpp, newprob);
 876                                     child_hash.remove(newpp);
 877                             }
 878                     } else {
 879                             System.out.println("DEBUG-> No more children of the FlatCondBranchNode present");
 880                     }
 881             }
 882
 883             /* Merge child prefetch pairs */
 884             ecld = child_hash.keys();
 885             while(ecld.hasMoreElements()) {
 886                     childpp = (PrefetchPair) ecld.nextElement();
 887                     tocompare.put(childpp, child_hash.get(childpp));
 888                     child_hash.remove(childpp);
 889             }
 890
 891             /* Update the new branch_prefetch_hashtable to store all new prefetch pairs */
 892             if(!tocompare.isEmpty()) {
 893                     if(index == 0) {
 894                             branch_prefetch_set.putAll(tocompare);
 895                     }else if(index == 1) {
 896                             if(branch_prefetch_set.isEmpty()) {
 897                                     branch_prefetch_set.putAll(tocompare);
 898                             } else {
 899                                     Enumeration e = tocompare.keys();
 900                                     while(e.hasMoreElements()) {
 901                                             pp = (PrefetchPair) e.nextElement();
 902                                             if(branch_prefetch_set.containsKey(pp)) {
 903                                                     newprob = (float)(branch_prefetch_set.get(pp).floatValue() + tocompare.get(pp).floatValue());
 904                                                     if(newprob < THRESHOLD_PROB) {
 905                                                             branch_prefetch_set.remove(pp);
 906                                                     } else {
 907                                                             branch_prefetch_set.put(pp, newprob);
 908                                                     }
 909                                                     tocompare.remove(pp);
 910                                             }
 911                                     }
 912                                     e = tocompare.keys();
 913                                     while(e.hasMoreElements()) {
 914                                             pp = (PrefetchPair) e.nextElement();
 915                                             branch_prefetch_set.put(pp,tocompare.get(pp));
 916                                             tocompare.remove(pp);
 917                                     }
 918                             }
 919                     } else {
 920                             System.out.println("DEBUG-> No more children of the FlatCondBranchNode present");
 921                     }
 922             }
 923
 924             /* Enqueue parent nodes */
 925             if(index == 1) {
 926                     pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), branch_prefetch_set);
 927                     if(pSetHasChanged) {
 928                             for(int i=0; i<curr.numPrev(); i++) {
 929                                     tovisit.add(curr.getPrev(i));
 930                             }
 931                             /* Overwrite the new prefetch set to the global hash table */
 932                             prefetch_hash.put(curr,branch_prefetch_set);
 933                     }
 934
 935             }
 936     }
 937
 938
 939     /** If FlatNode is not concerned with the prefetch set of its Child then propagate
 940      * prefetches up the FlatNode*/
 941     private void processDefaultCase(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 942             boolean pSetHasChanged = false;
 943             Enumeration e = null;
 944             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 945
 946             for(e = child_hash.keys(); e.hasMoreElements();) {
 947                     PrefetchPair newpp = (PrefetchPair) e.nextElement();
 948                     tocompare.put(newpp, child_hash.get(newpp));
 949             }
 950
 951             /* Compare with old Prefetch sets */
 952             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 953             if(pSetHasChanged){
 954                     for(int i=0; i<curr.numPrev(); i++) {
 955                             tovisit.add(curr.getPrev(i));
 956                     }
 957                     /* Overwrite the new prefetch set to the global hash table */
 958                     prefetch_hash.put(curr,tocompare);
 959             }
 960     }
 961
 962     private void processFlatNewNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 963             boolean pSetHasChanged = false;
 964             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 965             FlatNew currfnn = (FlatNew) curr;
 966             Float newprob = new Float((float)0.0);
 967             PrefetchPair childpp = null;
 968             Enumeration ecld = null;
 969
 970             ecld = child_hash.keys();
 971             while (ecld.hasMoreElements()) {
 972                     childpp = (PrefetchPair) ecld.nextElement();
 973                     if(childpp.base == currfnn.getDst()){
 974                             child_hash.remove(childpp);
 975                     } else {
 976                             tocompare.put(childpp, child_hash.get(childpp));
 977                             child_hash.remove(childpp);
 978                     }
 979             }
 980
 981             /* Compare with the orginal prefetch pairs */
 982             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 983             /* Enqueue parent nodes */
 984             if(pSetHasChanged) {
 985                     for(int i=0; i<curr.numPrev(); i++) {
 986                             tovisit.add(curr.getPrev(i));
 987                     }
 988                     /* Overwrite the new prefetch set to the global hash table */
 989                     prefetch_hash.put(curr,tocompare);
 990             }
 991     }
 992
 993     /** This function prints the Prefetch pairs of a given flatnode */
 994     private void printPrefetchPairs(FlatNode fn) {
 995             if(prefetch_hash.containsKey(fn)) {
 996                     System.out.print("Prefetch" + "(");
 997                     Hashtable<PrefetchPair, Float> currhash = (Hashtable) prefetch_hash.get(fn);
 998                     for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
 999                             PrefetchPair pp = (PrefetchPair) pphash.nextElement();
1000                             System.out.print(pp.toString() + ", ");
1001                     }
1002                     System.out.println(")");
1003             } else {
1004                     System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
1005             }
1006     }
1007
1008     private void doAnalysis() {
1009         Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
1010         while(classit.hasNext()) {
1011             ClassDescriptor cn=(ClassDescriptor)classit.next();
1012             Iterator methodit=cn.getMethods();
1013             while(methodit.hasNext()) {
1014                 /* Classify parameters */
1015                 MethodDescriptor md=(MethodDescriptor)methodit.next();
1016                 FlatMethod fm=state.getMethodFlat(md);
1017                 printMethod(fm);
1018             }
1019         }
1020     }
1021
1022     private void printMethod(FlatMethod fm) {
1023         System.out.println(fm.getMethod()+" {");
1024         HashSet tovisit=new HashSet();
1025         HashSet visited=new HashSet();
1026         int labelindex=0;
1027         Hashtable nodetolabel=new Hashtable();
1028         tovisit.add(fm);
1029         FlatNode current_node=null;
1030         //Assign labels 1st
1031         //Node needs a label if it is
1032         while(!tovisit.isEmpty()) {
1033             FlatNode fn=(FlatNode)tovisit.iterator().next();
1034             tovisit.remove(fn);
1035             visited.add(fn);
1036
1037             for(int i=0;i<fn.numNext();i++) {
1038                 FlatNode nn=fn.getNext(i);
1039                 if(i>0) {
1040                     //1) Edge >1 of node
1041                     nodetolabel.put(nn,new Integer(labelindex++));
1042                 }
1043                 if (!visited.contains(nn)&&!tovisit.contains(nn)) {
1044                     tovisit.add(nn);
1045                 } else {
1046                     //2) Join point
1047                     nodetolabel.put(nn,new Integer(labelindex++));
1048                 }
1049             }
1050         }
1051         //Do the actual printing
1052         tovisit=new HashSet();
1053         visited=new HashSet();
1054         tovisit.add(fm);
1055         while(current_node!=null||!tovisit.isEmpty()) {
1056             if (current_node==null) {
1057                 current_node=(FlatNode)tovisit.iterator().next();
1058                 tovisit.remove(current_node);
1059             }
1060             visited.add(current_node);
1061             if (nodetolabel.containsKey(current_node))
1062                 System.out.println("L"+nodetolabel.get(current_node)+":");
1063             if (current_node.numNext()==0) {
1064                 System.out.println("   "+current_node.toString());
1065                 current_node=null;
1066             } else if(current_node.numNext()==1) {
1067                 System.out.println("   "+current_node.toString());
1068                 FlatNode nextnode=current_node.getNext(0);
1069                 if (visited.contains(nextnode)) {
1070                     System.out.println("goto L"+nodetolabel.get(nextnode));
1071                     current_node=null;
1072                 } else
1073                     current_node=nextnode;
1074             } else if (current_node.numNext()==2) {
1075                 /* Branch */
1076                 System.out.println("   "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1))));
1077                 if (!visited.contains(current_node.getNext(1)))
1078                     tovisit.add(current_node.getNext(1));
1079                 if (visited.contains(current_node.getNext(0))) {
1080                     System.out.println("goto L"+nodetolabel.get(current_node.getNext(0)));
1081                     current_node=null;
1082                 } else
1083                     current_node=current_node.getNext(0);
1084             } else throw new Error();
1085         }
1086         System.out.println("}");
1087     }
1088
1089 }