Robust/src/Analysis/Prefetch/PrefetchAnalysis.java

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