Robust/src/Analysis/Prefetch/PrefetchAnalysis.java

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