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.FlatExit:
 113       case FKind.FlatNew:
 114       case FKind.FlatCastNode:
 115       case FKind.FlatTagDeclaration:
 116       case FKind.FlatInstanceOfNode:
 117         processDefaultCase(curr,child_prefetch_set_copy);
 118         break;
 119
 120       case FKind.FlatMethod:
 121         //TODO change it to take care of FlatMethod, Flatcalls
 122         processFlatMethod(curr, child_prefetch_set_copy);
 123         break;
 124
 125       case FKind.FlatFieldNode:
 126         processFlatFieldNode(curr, child_prefetch_set_copy);
 127         break;
 128
 129       case FKind.FlatElementNode:
 130         processFlatElementNode(curr, child_prefetch_set_copy);
 131         break;
 132
 133       case FKind.FlatOpNode:
 134         processFlatOpNode(curr, child_prefetch_set_copy);
 135         break;
 136
 137       case FKind.FlatLiteralNode:
 138         processFlatLiteralNode(curr, child_prefetch_set_copy);
 139         break;
 140
 141       case FKind.FlatSetElementNode:
 142         processFlatSetElementNode(curr, child_prefetch_set_copy);
 143         break;
 144
 145       case FKind.FlatSetFieldNode:
 146         processFlatSetFieldNode(curr, child_prefetch_set_copy);
 147         break;
 148
 149       case FKind.FlatOffsetNode:
 150         processDefaultCase(curr,child_prefetch_set_copy);
 151         break;
 152
 153       default:
 154         throw new Error("No such Flatnode kind");
 155       }
 156     }
 157   }
 158
 159   /**This function compares all the prefetch pairs in a Prefetch set hashtable and
 160    * returns: true if something has changed in the new Prefetch set else
 161    * returns: false
 162    */
 163   private boolean comparePrefetchSets(Hashtable<PrefetchPair, Double> oldPrefetchSet, Hashtable<PrefetchPair, Double> newPrefetchSet) {
 164     if (oldPrefetchSet.size()!=newPrefetchSet.size())
 165       return true;
 166
 167     for(Enumeration e = newPrefetchSet.keys(); e.hasMoreElements();) {
 168       PrefetchPair pp = (PrefetchPair) e.nextElement();
 169       double newprob = newPrefetchSet.get(pp).doubleValue();
 170       if (!oldPrefetchSet.containsKey(pp))
 171         return true;
 172       double oldprob = oldPrefetchSet.get(pp).doubleValue();
 173
 174       if((newprob - oldprob) > PROB_DIFF) {
 175         return true;
 176       }
 177       if (newprob >= PREFETCH_THRESHOLD_PROB && oldprob < PREFETCH_THRESHOLD_PROB) {
 178         return true;
 179       }
 180       if (oldprob>newprob) {
 181         System.out.println("ERROR:" + pp);
 182         System.out.println(oldprob + " -> "+ newprob);
 183       }
 184     }
 185     return false;
 186   }
 187
 188   private void updatePairMap(FlatNode curr, PairMap pm, int index) {
 189     if (index>=curr.numNext())
 190       return;
 191     if (!pmap_hash.containsKey(curr.getNext(index))) {
 192       pmap_hash.put(curr.getNext(index), new Hashtable<FlatNode, PairMap>());
 193     }
 194     pmap_hash.get(curr.getNext(index)).put(curr, pm);
 195   }
 196
 197   private void updatePrefetchSet(FlatNode curr, Hashtable<PrefetchPair, Double> newset) {
 198     Hashtable<PrefetchPair, Double>oldset=prefetch_hash.get(curr);
 199     if (comparePrefetchSets(oldset, newset)) {
 200       for(int i=0; i<curr.numPrev(); i++) {
 201         tovisit.add(curr.getPrev(i));
 202       }
 203       prefetch_hash.put(curr, newset);
 204     }
 205   }
 206
 207
 208   /** This function processes the prefetch set of FlatFieldNode
 209    * It generates a new prefetch set after comparision with its children
 210    * Then compares it with its old prefetch set
 211    * If old prefetch set is not same as new prefetch set then enqueue the parents
 212    * of the current FlatFieldNode
 213    * */
 214   private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
 215     Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
 216     Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 217     FlatFieldNode currffn = (FlatFieldNode) curr;
 218     PairMap pm = new PairMap();
 219
 220     /* Do Self analysis of the current node*/
 221     FieldDescriptor currffn_field =  currffn.getField();
 222     TempDescriptor currffn_src = currffn.getSrc();
 223     if (currffn_field.getType().isPtr()) {
 224       PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
 225       Double prob = new Double(1.0);
 226       tocompare.put(pp, prob);
 227     }
 228
 229     /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 230
 231     for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 232       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 233       if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
 234         if (currffn.getField().getType().isPtr()) {
 235           ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 236           newdesc.add(currffn.getField());
 237           newdesc.addAll(childpp.desc);
 238           PrefetchPair newpp =  new PrefetchPair(currffn.getSrc(), newdesc);
 239           Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 240           if (tocompare.containsKey(newpp)) {
 241             Double oldprob=tocompare.get(newpp);
 242             newprob=1.0-(1.0-oldprob)*(1.0-newprob);
 243           }
 244           tocompare.put(newpp, newprob);
 245           pm.addPair(childpp, newpp);
 246         }
 247         //drop if not ptr
 248       } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
 249         //covered by current prefetch
 250         child_prefetch_set_copy.remove(childpp);
 251       } else if(childpp.containsTemp(currffn.getDst())) {
 252         child_prefetch_set_copy.remove(childpp);
 253       } else {
 254         Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 255         if (tocompare.containsKey(childpp)) {
 256           Double oldprob=tocompare.get(childpp);
 257           newprob=1.0-(1.0-oldprob)*(1.0-newprob);
 258         }
 259         tocompare.put(childpp, newprob);
 260         pm.addPair(childpp, childpp);
 261       }
 262     }
 263
 264     for(Iterator<PrefetchPair> it=tocompare.keySet().iterator(); it.hasNext();) {
 265       PrefetchPair pp=it.next();
 266       if (tocompare.get(pp)<ANALYSIS_THRESHOLD_PROB)
 267         it.remove();
 268
 269     }
 270
 271     updatePairMap(curr, pm, 0);
 272     updatePrefetchSet(curr, tocompare);
 273   }
 274
 275   /** This function processes the prefetch set of a FlatElementNode
 276    * It generates a new prefetch set after comparision with its children
 277    * It compares the old prefetch set with this new prefetch set and enqueues the parents
 278    * of the current node if change occurs and updates the global flatnode hash table
 279    * */
 280   private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
 281
 282     Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
 283     Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 284     FlatElementNode currfen = (FlatElementNode) curr;
 285     PairMap pm = new PairMap();
 286
 287
 288     /* Do Self analysis of the current node*/
 289     TempDescriptor currfen_index = currfen.getIndex();
 290     IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
 291     TempDescriptor currfen_src = currfen.getSrc();
 292     if(currfen.getDst().getType().isPtr()) {
 293       PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
 294       Double prob = new Double(1.0);
 295       currcopy.put(pp, prob);
 296     }
 297
 298     /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 299     PrefetchPair currpp = null;
 300     for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 301       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 302       if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
 303         if (currfen.getDst().getType().isPtr()) {
 304           ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 305           newdesc.add((Descriptor)idesc);
 306           newdesc.addAll(childpp.desc);
 307           PrefetchPair newpp =  new PrefetchPair(currfen.getSrc(), newdesc);
 308           Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 309           tocompare.put(newpp, newprob);
 310           pm.addPair(childpp, newpp);
 311           child_prefetch_set_copy.remove(childpp);
 312           /* Check for independence of prefetch pairs to compute new probability */
 313           if(child_prefetch_set_copy.containsKey(newpp)) {
 314             newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 315             if(newprob < ANALYSIS_THRESHOLD_PROB) {
 316               tocompare.remove(newpp);
 317             } else {
 318               tocompare.put(newpp, newprob);
 319               pm.addPair(newpp, newpp);
 320             }
 321             child_prefetch_set_copy.remove(newpp);
 322           }
 323         }
 324       } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
 325         child_prefetch_set_copy.remove(childpp);
 326       } else if(childpp.containsTemp(currfen.getDst())) {
 327         child_prefetch_set_copy.remove(childpp);
 328       } else {
 329         continue;
 330       }
 331     }
 332     /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 333      * if so calculate the new probability */
 334     for(Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 335       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 336       for(Enumeration e = currcopy.keys(); e.hasMoreElements();) {
 337         currpp = (PrefetchPair) e.nextElement();
 338         if(currpp.equals(childpp)) {
 339           pm.addPair(childpp, currpp);
 340           child_prefetch_set_copy.remove(childpp);
 341           break;
 342         }
 343       }
 344     }
 345
 346     /* Merge child prefetch pairs */
 347     for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 348       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 349       tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 350       pm.addPair(childpp, childpp);
 351       child_prefetch_set_copy.remove(childpp);
 352     }
 353
 354     /* Merge curr prefetch pairs */
 355     for (Enumeration e = currcopy.keys(); e.hasMoreElements();) {
 356       currpp = (PrefetchPair) e.nextElement();
 357       tocompare.put(currpp, currcopy.get(currpp).doubleValue());
 358       currcopy.remove(currpp);
 359     }
 360
 361     updatePairMap(curr, pm, 0);
 362     updatePrefetchSet(curr, tocompare);
 363   }
 364
 365   /** This function processes the prefetch set of a FlatSetFieldNode
 366    * It generates a new prefetch set after comparision with its children
 367    * It compares the old prefetch set with this new prefetch set and enqueues the parents
 368    * of the current node if change occurs and then updates the global flatnode hash table
 369    * */
 370   private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
 371     Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 372     FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
 373     PairMap pm = new PairMap();
 374
 375     for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 376       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 377       if(childpp.base == currfsfn.getDst()) {
 378         int size = childpp.desc.size();
 379         if(size >=2) {         /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */
 380           if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 381             ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 382             for(int i = 0; i<(childpp.desc.size()-1); i++) {
 383               newdesc.add(i,childpp.desc.get(i+1));
 384             }
 385             PrefetchPair newpp =  new PrefetchPair(currfsfn.getSrc(), newdesc);
 386             Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 387             tocompare.put(newpp, newprob);
 388             pm.addPair(childpp, newpp);
 389             child_prefetch_set_copy.remove(childpp);
 390             /* Check for independence of prefetch pairs in newly generated prefetch pair
 391              * to compute new probability */
 392             if(child_prefetch_set_copy.containsKey(newpp)) {
 393               newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 394               if(newprob < ANALYSIS_THRESHOLD_PROB) {
 395                 tocompare.remove(newpp);
 396               } else {
 397                 tocompare.put(newpp, newprob);
 398                 pm.addPair(newpp, newpp);
 399               }
 400               child_prefetch_set_copy.remove(newpp);
 401             }
 402           }
 403         } else if(size==1) {         /* e.g x.f = g (with child prefetch x.f) */
 404           if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 405             child_prefetch_set_copy.remove(childpp);
 406           }
 407         } else {
 408           continue;
 409         }
 410       }
 411     }
 412
 413     /* Merge child prefetch pairs */
 414     for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 415       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 416       tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 417       pm.addPair(childpp, childpp);
 418       child_prefetch_set_copy.remove(childpp);
 419     }
 420
 421     updatePairMap(curr, pm, 0);
 422     updatePrefetchSet(curr, tocompare);
 423   }
 424
 425   /** This function processes the prefetch set of a FlatSetElementNode
 426    * It generates a new prefetch set after comparision with its children
 427    * It compares the old prefetch set with this new prefetch set and enqueues the parents
 428    * of the current node if change occurs and then updates the global flatnode hash table
 429    * */
 430   private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
 431     Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 432     FlatSetElementNode currfsen = (FlatSetElementNode) curr;
 433     PairMap pm = new PairMap();
 434
 435     for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 436       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 437       if (childpp.base == currfsen.getDst()) {
 438         int sizedesc = childpp.desc.size();
 439         if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
 440           int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
 441           if(sizetempdesc == 1) {
 442             if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
 443               /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */
 444               ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 445               for(int i = 0; i<(childpp.desc.size()-1); i++) {
 446                 newdesc.add(i,childpp.desc.get(i+1));
 447               }
 448               PrefetchPair newpp =  new PrefetchPair(currfsen.getSrc(), newdesc);
 449               Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 450               tocompare.put(newpp, newprob);
 451               pm.addPair(childpp, newpp);
 452               child_prefetch_set_copy.remove(childpp);
 453               /* Check for independence of prefetch pairs to compute new probability */
 454               if(child_prefetch_set_copy.containsKey(newpp)) {
 455                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 456                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 457                   tocompare.remove(newpp);
 458                 } else {
 459                   tocompare.put(newpp, newprob);
 460                   pm.addPair(newpp, newpp);
 461                 }
 462                 child_prefetch_set_copy.remove(newpp);
 463               }
 464             } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1))
 465               /* For e.g. a[i] = g with child prefetch set a[i] */
 466               child_prefetch_set_copy.remove(childpp);
 467           } else {
 468             continue;
 469           }
 470         }
 471       }
 472     }
 473     /* Merge child prefetch pairs */
 474     for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 475       PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 476       tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 477       pm.addPair(childpp, childpp);
 478       child_prefetch_set_copy.remove(childpp);
 479     }
 480
 481     updatePairMap(curr, pm, 0);
 482     updatePrefetchSet(curr, tocompare);
 483   }
 484
 485   /** This function applies rules and does analysis for a FlatOpNode
 486    *  And updates the global prefetch hashtable
 487    * */
 488   private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
 489     int index;
 490     Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 491     FlatOpNode currfopn = (FlatOpNode) curr;
 492     PairMap pm = new PairMap();
 493
 494     if(currfopn.getOp().getOp() == Operation.ASSIGN) {
 495       for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 496         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 497         PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 498
 499         /* For cases like x=y  with child prefetch set x[i].z,x.g*/
 500         if(childpp.base == currfopn.getDest()) {
 501           ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 502           newdesc.addAll(childpp.desc);
 503           PrefetchPair newpp =  new PrefetchPair(currfopn.getLeft(), newdesc);
 504           Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 505           tocompare.put(newpp, newprob);
 506           pm.addPair(childpp, newpp);
 507           child_prefetch_set_copy.remove(childpp);
 508           /* Check for independence of prefetch pairs to compute new probability */
 509           if(child_prefetch_set_copy.containsKey(newpp)) {
 510             newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 511             if(newprob < ANALYSIS_THRESHOLD_PROB) {
 512               tocompare.remove(newpp);
 513             } else {
 514               tocompare.put(newpp, newprob);
 515               pm.addPair(newpp, newpp);
 516             }
 517             child_prefetch_set_copy.remove(newpp);
 518           }
 519           /* For cases like x=y  with child prefetch set r[x].p, r[p+x].q where x is a  tempdescriptor*/
 520         } else if(copyofchildpp.containsTemp(currfopn.getDest())) {
 521           PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft()});
 522           Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 523           tocompare.put(newpp, newprob);
 524           pm.addPair(childpp, newpp);
 525           child_prefetch_set_copy.remove(childpp);
 526           /* Check for independence of prefetch pairs to compute new probability*/
 527           if(child_prefetch_set_copy.containsKey(newpp)) {
 528             newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 529             if(newprob < ANALYSIS_THRESHOLD_PROB) {
 530               tocompare.remove(newpp);
 531             } else {
 532               tocompare.put(newpp, newprob);
 533               pm.addPair(newpp, newpp);
 534             }
 535             child_prefetch_set_copy.remove(newpp);
 536           }
 537           newpp = null;
 538         } else {
 539           continue;
 540         }
 541       }
 542       //case i = i+z with child prefetch set a[i].x
 543     } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
 544       for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 545         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 546         PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 547
 548         if(copyofchildpp.containsTemp(currfopn.getDest())) {
 549           PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft(), currfopn.getRight()});
 550           Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 551           tocompare.put(newpp, newprob);
 552           pm.addPair(childpp, newpp);
 553           child_prefetch_set_copy.remove(childpp);
 554           /* Check for independence of prefetch pairs to compute new probability*/
 555           if(child_prefetch_set_copy.containsKey(newpp)) {
 556             newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 557             if(newprob < ANALYSIS_THRESHOLD_PROB) {
 558               tocompare.remove(newpp);
 559             } else {
 560               tocompare.put(newpp, newprob);
 561               pm.addPair(newpp, newpp);
 562             }
 563             child_prefetch_set_copy.remove(newpp);
 564           }
 565         } else {
 566           continue;
 567         }
 568       }
 569     } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.SUB)) {
 570       for(Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
 571         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 572         if(childpp.containsTemp(currfopn.getDest())) {
 573           child_prefetch_set_copy.remove(childpp);
 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   /** If FlatNode is not concerned with the prefetch set of its Child then propagate
 743    * prefetches up the FlatNode*/
 744   private void processCall(FlatCall curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
 745     PairMap pm = new PairMap();
 746     Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 747
 748     /* Don't propagate prefetches across cache clear */
 749     if (!(curr.getMethod().getClassMethodName().equals("System.clearPrefetchCache")||
 750           curr.getMethod().getClassMethodName().equals("Barrier.enterBarrier"))) {
 751       /* Propagate all child nodes */
 752 nexttemp:
 753       for(Enumeration e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
 754         PrefetchPair childpp = (PrefetchPair) e.nextElement();
 755         TempDescriptor[] writearray=curr.writesTemps();
 756         for(int i=0; i<writearray.length; i++) {
 757           TempDescriptor wtd=writearray[i];
 758           if(childpp.base == wtd||
 759              childpp.containsTemp(wtd))
 760             continue nexttemp;
 761         }
 762         tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
 763         pm.addPair(childpp, childpp);
 764       }
 765
 766     }
 767     updatePairMap(curr, pm, 0);
 768     updatePrefetchSet(curr, tocompare);
 769   }
 770
 771   /** This function prints the Prefetch pairs of a given flatnode */
 772   private void printPrefetchPairs(FlatNode fn) {
 773     System.out.println(fn);
 774     if(prefetch_hash.containsKey(fn)) {
 775       System.out.print("Prefetch" + "(");
 776       Hashtable<PrefetchPair, Double> currhash = (Hashtable) prefetch_hash.get(fn);
 777       for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
 778         PrefetchPair pp = (PrefetchPair) pphash.nextElement();
 779         System.out.print(pp.toString() + ", ");
 780       }
 781       System.out.println(")");
 782     } else {
 783       System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
 784     }
 785   }
 786
 787   private void doInsPrefetchAnalysis(FlatMethod fm, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
 788     Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
 789     HashSet<PrefetchPair> pset1_init = new HashSet<PrefetchPair>();
 790     LinkedList<FlatNode> newtovisit = new LinkedList<FlatNode>();
 791     LinkedList<FlatNode> newvisited = new LinkedList<FlatNode>();
 792
 793     newtovisit.addLast((FlatNode)fm);
 794     while(!newtovisit.isEmpty()) {
 795       FlatNode fn = (FlatNode) newtovisit.iterator().next();
 796       newtovisit.remove(0);
 797       pset1_hash.put(fn, pset1_init);       //Initialize pset1_hash
 798       newvisited.addLast(fn);
 799       for(int i=0; i<fn.numNext(); i++) {
 800         FlatNode nn = fn.getNext(i);
 801         if(!newtovisit.contains(nn) && !newvisited.contains(nn)) {
 802           newtovisit.addLast(nn);
 803         }
 804       }
 805     }
 806
 807     /* Start with a top down sorted order of nodes */
 808     while(!newvisited.isEmpty()) {
 809       applyPrefetchInsertRules((FlatNode) newvisited.getFirst(), newvisited, pset1_hash, newprefetchset);
 810       newvisited.remove(0);
 811     }
 812     delSubsetPPairs(newprefetchset);
 813   }
 814
 815   /** This function deletes the smaller prefetch pair subset from a list of prefetch pairs
 816    * for e.g. if there are 2 prefetch pairs a.b.c.d and a.b.c for a given flatnode
 817    * then this function drops a.b.c from the prefetch set of the flatnode */
 818   private void delSubsetPPairs(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
 819     for (Enumeration e = newprefetchset.keys(); e.hasMoreElements();) {
 820       FlatNode fn = (FlatNode) e.nextElement();
 821       Set<PrefetchPair> ppairs = newprefetchset.get(fn);
 822       Set<PrefetchPair> toremove=new HashSet<PrefetchPair>();
 823
 824       for(Iterator<PrefetchPair> it1=ppairs.iterator(); it1.hasNext();) {
 825         PrefetchPair pp1=it1.next();
 826         if (toremove.contains(pp1))
 827           continue;
 828         int l1=pp1.desc.size()+1;
 829         for(Iterator<PrefetchPair> it2=ppairs.iterator(); it2.hasNext();) {
 830           PrefetchPair pp2=it2.next();
 831           int l2=pp2.desc.size()+1;
 832
 833           if (l1<l2&&isSubSet(pp1,pp2))
 834             toremove.add(pp1);
 835           else
 836           if (l2>l1&&isSubSet(pp2,pp1))
 837             toremove.add(pp2);
 838         }
 839       }
 840
 841       ppairs.removeAll(toremove);
 842     }
 843   }
 844
 845   /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch
 846    * pair else it returns: false */
 847   private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) {
 848     if (shrt.base != lng.base) {
 849       return false;
 850     }
 851     for (int j = 0; j < shrt.desc.size(); j++) {
 852       if(shrt.getDescAt(j) instanceof IndexDescriptor) {
 853         IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j);
 854         if(lng.getDescAt(j) instanceof IndexDescriptor) {
 855           IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j);
 856           if(shrtid.equals(lngid)) {
 857             continue;
 858           } else {
 859             return false;
 860           }
 861         } else {
 862           return false;
 863         }
 864       } else  {
 865         if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)) {
 866           return false;
 867         }
 868       }
 869     }
 870     return true;
 871   }
 872
 873   /**This function compares all the prefetch pairs in a Prefetch set hashtable and
 874    * returns: true if something has changed in the new Prefetch set else
 875    * returns: false
 876    */
 877   private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
 878     if(oldPSet.size() != newPSet.size()) {
 879       return true;
 880     } else {
 881       for(Iterator it = newPSet.iterator(); it.hasNext();) {
 882         if(!oldPSet.contains((PrefetchPair)it.next())) {
 883           return true;
 884         }
 885       }
 886     }
 887     return false;
 888   }
 889
 890   /** This function creates a set called pset1 that contains prefetch pairs that have already
 891    * been prefetched. While traversing the graph of a flat representation in a top down fashion,
 892    * this function creates pset1 such that it contains prefetch pairs that have been prefetched at
 893    * the previous nodes */
 894
 895   private void applyPrefetchInsertRules(FlatNode fn, LinkedList<FlatNode> newvisited, Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
 896     if(fn.kind() == FKind.FlatMethod) {
 897       HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
 898       Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
 899       for(Enumeration e = prefetchset.keys(); e.hasMoreElements();) {
 900         PrefetchPair pp = (PrefetchPair) e.nextElement();
 901         /* Apply initial rule */
 902         if(prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB) {
 903           pset1.add(pp);
 904         }
 905       }
 906       /* Enqueue child node if Pset1 has changed */
 907       if (comparePSet1(pset1_hash.get(fn), pset1)) {
 908         for(int j=0; j<fn.numNext(); j++) {
 909           FlatNode nn = fn.getNext(j);
 910           newvisited.addLast((FlatNode)nn);
 911         }
 912         pset1_hash.put(fn, pset1);
 913       }
 914       newprefetchset.put(fn, pset1);
 915     } else {     /* Nodes other than Flat Method Node */
 916       HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
 917       HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
 918       Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
 919       Hashtable<FlatNode, PairMap> ppairmaphash = pmap_hash.get(fn);
 920       for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
 921         PrefetchPair pp = (PrefetchPair) epset.nextElement();
 922         boolean pprobIsGreater = (prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB);
 923         boolean mapprobIsLess=false;
 924         boolean mapIsPresent=true;
 925         for(int i=0; i<fn.numPrev(); i++) {
 926           FlatNode parentnode=fn.getPrev(i);
 927           PairMap pm = (PairMap) ppairmaphash.get(parentnode);
 928           //Find if probability is less for previous node
 929           if(pm!=null&&pm.getPair(pp) != null) {
 930             PrefetchPair mappedpp = pm.getPair(pp);
 931             if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
 932               double prob = prefetch_hash.get(parentnode).get(mappedpp).doubleValue();
 933               if(prob < PREFETCH_THRESHOLD_PROB)
 934                 mapprobIsLess = true;
 935             } else
 936               mapprobIsLess = true;
 937           } else {
 938             mapprobIsLess = true;
 939           }
 940           /* Build pset2 */
 941           if(pm !=null) {
 942             HashSet pset = pset1_hash.get(parentnode);
 943             if(pset.isEmpty()||!pset.contains((PrefetchPair) pm.getPair(pp)))
 944               mapIsPresent = false;
 945           } else
 946             mapIsPresent=false;
 947         }
 948
 949         if(mapIsPresent)
 950           pset2.add(pp);
 951
 952         if(pprobIsGreater && mapprobIsLess)
 953           newpset.add(pp);
 954       }
 955
 956       HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
 957       pset1.addAll(pset2);
 958       pset1.addAll(newpset);
 959       /* Enqueue child node if Pset1 has changed */
 960       if (comparePSet1(pset1_hash.get(fn), pset1)) {
 961         for(int i=0; i<fn.numNext(); i++) {
 962           FlatNode nn = fn.getNext(i);
 963           newvisited.addLast((FlatNode)nn);
 964         }
 965         pset1_hash.put(fn, pset1);
 966       }
 967
 968       /* To insert prefetch, apply rule: if the newpset minus pset2 is nonempty
 969        * then insert a new prefetch node here*/
 970
 971       HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
 972       s.addAll(newpset);
 973       s.removeAll(pset2);
 974       newprefetchset.put(fn, s);
 975     }
 976   }
 977
 978   private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
 979     boolean isFNPresent = false;     /* Detects presence of FlatNew node */
 980     /* This modifies the Flat representation graph */
 981     for(Enumeration e = newprefetchset.keys(); e.hasMoreElements();) {
 982       FlatNode fn = (FlatNode) e.nextElement();
 983       FlatPrefetchNode fpn = new FlatPrefetchNode();
 984       if(newprefetchset.get(fn).size() > 0) {
 985         fpn.insAllpp((HashSet)newprefetchset.get(fn));
 986         if(fn.kind() == FKind.FlatMethod) {
 987           FlatNode nn = fn.getNext(0);
 988           fn.setNext(0, fpn);
 989           fpn.addNext(nn);
 990           fpn.siteid = prefetchsiteid++;
 991         } else {
 992           /* Check if previous node of this FlatNode is a NEW node
 993            * If yes, delete this flatnode and its prefetch set from hash table
 994            * This eliminates prefetches for NULL ptrs*/
 995           for(int i = 0; i< fn.numPrev(); i++) {
 996             FlatNode nn = fn.getPrev(i);
 997             if(nn.kind() == FKind.FlatNew) {
 998               isFNPresent = true;
 999             }
1000           }
1001           if(!isFNPresent) {
1002             while(fn.numPrev() > 0) {
1003               FlatNode nn = fn.getPrev(0);
1004               for(int j = 0; j<nn.numNext(); j++) {
1005                 if(nn.getNext(j) == fn) {
1006                   nn.setNext(j, fpn);
1007                 }
1008               }
1009             }
1010             fpn.addNext(fn);
1011             fpn.siteid = prefetchsiteid++;
1012           }
1013         }   //end of else
1014       }       //End of if
1015     }     //end of for
1016   }
1017 }