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