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