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