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