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