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