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