Robust/src/Analysis/Prefetch/PrefetchAnalysis.java

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