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         Set<FlatNode> tovisit;
  21         public Hashtable<FlatNode, Hashtable<PrefetchPair, Double>> prefetch_hash;//holds all flatnodes and corresponding prefetch set
  22         public Hashtable<FlatNode, Hashtable<FlatNode, PairMap>> pmap_hash;//holds all flatnodes and mappings between child prefetch pair and parent prefetch pair
  23         public static final double PROB_DIFF = 0.05;    //threshold for difference in probabilities during first phase of analysis
  24         public static final double ANALYSIS_THRESHOLD_PROB = 0.10; //threshold for prefetches to stop propagating during first phase of analysis
  25         public static final double PREFETCH_THRESHOLD_PROB = 0.30;//threshold for prefetches to stop propagating while applying prefetch rules during second phase of analysis
  26         public static final double BRANCH_TRUE_EDGE_PROB = 0.5;
  27         public static final double BRANCH_FALSE_EDGE_PROB = 0.5;
  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                 DoPrefetch();
  36                 prefetch_hash = null;
  37                 pmap_hash = null;
  38         }
  39
  40         /** This function returns true if a tempdescriptor object is found in the array of descriptors
  41          *  for a given prefetch pair else returns false*/
  42         private boolean isTempDescFound(PrefetchPair pp, TempDescriptor td) {
  43                 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  44                 ListIterator it = desc.listIterator();
  45                 for(;it.hasNext();) {
  46                         Object o = it.next();
  47                         if(o instanceof IndexDescriptor) {
  48                                 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
  49                                 if(tdarray.contains(td)) {
  50                                         return true;
  51                                 }
  52                         }
  53                 }
  54                 return false;
  55         }
  56
  57         /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
  58          * tempdescriptors when there is a match */
  59         private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor newtd) {
  60                 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  61                 ListIterator it = desc.listIterator();
  62                 for(;it.hasNext();) {
  63                         Object currdesc = it.next();
  64                         if(currdesc instanceof IndexDescriptor) {
  65                                 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
  66                                 if(tdarray.contains(td)) {
  67                                         int index = tdarray.indexOf(td);
  68                                         tdarray.set(index, newtd);
  69                                 }
  70                         }
  71                 }
  72                 return desc;
  73         }
  74
  75         /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
  76          * tempdescriptors when there is a match for e.g FlatOpNodes if i= i+j then replace i with i+j */
  77         private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor left, TempDescriptor right) {
  78                 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  79                 ListIterator it = desc.listIterator();
  80                 for(;it.hasNext();) {
  81                         Object currdesc = it.next();
  82                         if(currdesc instanceof IndexDescriptor) {
  83                                 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
  84                                 if(tdarray.contains(td)) {
  85                                         int index = tdarray.indexOf(td);
  86                                         tdarray.set(index, left);
  87                                         tdarray.add(right);
  88                                 }
  89                         }
  90                 }
  91                 return desc;
  92         }
  93
  94         /** This function starts the prefetch analysis */
  95         private void DoPrefetch() {
  96                 Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
  97                 while(classit.hasNext()) {
  98                         ClassDescriptor cn=(ClassDescriptor)classit.next();
  99                         doMethodAnalysis(cn);
 100                 }
 101         }
 102
 103         /** This function calls analysis for every method in a class */
 104         private void doMethodAnalysis(ClassDescriptor cn) {
 105             for (Iterator methodit=cn.getMethods();methodit.hasNext();) {
 106                 MethodDescriptor md=(MethodDescriptor)methodit.next();
 107                 if (state.excprefetch.contains(md.getClassMethodName()))
 108                     continue; //Skip this method
 109                 Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
 110                 FlatMethod fm=state.getMethodFlat(md);
 111                 doFlatNodeAnalysis(fm);
 112                 doInsPrefetchAnalysis(fm, newprefetchset);
 113                 if(newprefetchset.size() > 0) {
 114                     addFlatPrefetchNode(newprefetchset);
 115                 }
 116                 newprefetchset = null;
 117             }
 118         }
 119
 120         /** This function calls analysis for every node in a method */
 121         private void doFlatNodeAnalysis(FlatMethod fm) {
 122                 tovisit = fm.getNodeSet();
 123                 Hashtable<PrefetchPair, Double> nodehash = new Hashtable<PrefetchPair, Double>();
 124                 /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
 125                 while(!tovisit.isEmpty()) {
 126                         FlatNode fn = (FlatNode)tovisit.iterator().next();
 127                         prefetch_hash.put(fn, nodehash);
 128                         tovisit.remove(fn);
 129                 }
 130                 nodehash = null;
 131                 /* Visit and process nodes */
 132                 tovisit = fm.getNodeSet();
 133                 while(!tovisit.isEmpty()) {
 134                         FlatNode fn = (FlatNode)tovisit.iterator().next();
 135                         doChildNodeAnalysis(fn);
 136                         tovisit.remove(fn);
 137                 }
 138         }
 139
 140         /**
 141          * This function generates the prefetch sets for a given Flatnode considering the kind of node
 142          * It calls severals functions based on the kind of the node and
 143          * returns true: if the prefetch set has changed since last time the node was analysed
 144          * returns false : otherwise
 145          */
 146         private void doChildNodeAnalysis(FlatNode curr) {
 147                 Hashtable<PrefetchPair, Double> child_prefetch_set_copy = new Hashtable<PrefetchPair, Double>();
 148                 Hashtable<FlatNode, PairMap> parentpmap = new Hashtable<FlatNode, PairMap>();
 149                 FlatNode child_node = null;
 150                 if(curr.numNext() != 0) {
 151                         child_node = curr.getNext(0);
 152                         if(prefetch_hash.containsKey(child_node)) {
 153                                 child_prefetch_set_copy = (Hashtable<PrefetchPair,Double>) prefetch_hash.get(child_node).clone();
 154                         }
 155                 }
 156
 157                 switch(curr.kind()) {
 158                         case FKind.FlatBackEdge:
 159                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 160                                 break;
 161                         case FKind.FlatCall:
 162                                 //TODO change it to take care of FlatMethod, Flatcalls
 163                                 processFlatCall(curr, child_prefetch_set_copy, parentpmap);
 164                                 break;
 165                         case FKind.FlatCheckNode:
 166                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 167                                 break;
 168                         case FKind.FlatMethod:
 169                                 //TODO change it to take care of FlatMethod, Flatcalls
 170                                 processFlatMethod(curr, child_prefetch_set_copy, parentpmap);
 171                                 break;
 172                         case FKind.FlatNew:
 173                                 processFlatNewNode(curr, child_prefetch_set_copy, parentpmap);
 174                                 break;
 175                         case FKind.FlatReturnNode:
 176                                 //TODO change it to take care of FlatMethod, Flatcalls
 177                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 178                                 break;
 179                         case FKind.FlatFieldNode:
 180                                 processFlatFieldNode(curr, child_prefetch_set_copy, parentpmap);
 181                                 break;
 182                         case FKind.FlatElementNode:
 183                                 processFlatElementNode(curr, child_prefetch_set_copy, parentpmap);
 184                                 break;
 185                         case FKind.FlatCondBranch:
 186                                 Hashtable<PrefetchPair, Double> branch_prefetch_set =  new Hashtable<PrefetchPair,Double>();
 187                                 for (int i = 0; i < curr.numNext(); i++) {
 188                                         Hashtable<FlatNode, PairMap> branchparentpmap = new Hashtable<FlatNode, PairMap>();
 189                                         child_node = curr.getNext(i);
 190                                         if (prefetch_hash.containsKey(child_node)) {
 191                                                 child_prefetch_set_copy = (Hashtable<PrefetchPair,Double>) prefetch_hash.get(child_node).clone();
 192                                         }
 193                                         processFlatCondBranch(curr, child_prefetch_set_copy, i, branch_prefetch_set, branchparentpmap);
 194                                 }
 195                                 break;
 196                         case FKind.FlatOpNode:
 197                                 processFlatOpNode(curr, child_prefetch_set_copy, parentpmap);
 198                                 break;
 199                         case FKind.FlatLiteralNode:
 200                                 processFlatLiteralNode(curr, child_prefetch_set_copy, parentpmap);
 201                                 break;
 202                         case FKind.FlatSetElementNode:
 203                                 processFlatSetElementNode(curr, child_prefetch_set_copy, parentpmap);
 204                                 break;
 205                         case FKind.FlatSetFieldNode:
 206                                 processFlatSetFieldNode(curr, child_prefetch_set_copy, parentpmap);
 207                                 break;
 208                         case FKind.FlatAtomicEnterNode:
 209                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 210                                 break;
 211                         case FKind.FlatAtomicExitNode:
 212                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 213                                 break;
 214                         case FKind.FlatCastNode:
 215                                 processFlatCastNode(curr, child_prefetch_set_copy, parentpmap);
 216                                 break;
 217                         case FKind.FlatFlagActionNode:
 218                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 219                                 break;
 220                         case FKind.FlatGlobalConvNode:
 221                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 222                                 break;
 223                         case FKind.FlatNop:
 224                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 225                                 break;
 226                         case FKind.FlatTagDeclaration:
 227                                 processFlatTagDeclaration(curr, child_prefetch_set_copy, parentpmap);
 228                                 break;
 229                         default:
 230                                 throw new Error("No such Flatnode kind");
 231                 }
 232         }
 233
 234         /**This function compares all the prefetch pairs in a Prefetch set hashtable and
 235          * returns: true if something has changed in the new Prefetch set else
 236          * returns: false
 237          */
 238         private boolean comparePrefetchSets(Hashtable<PrefetchPair, Double> oldPrefetchSet, Hashtable<PrefetchPair, Double>
 239                         newPrefetchSet) {
 240                 boolean hasChanged = false;
 241                 PrefetchPair oldpp = null;
 242                 PrefetchPair newpp = null;
 243
 244                 if(oldPrefetchSet.size() != newPrefetchSet.size()) {
 245                         if(newPrefetchSet.size() == 0) {
 246                                 return false;
 247                         }
 248                         return true;
 249                 } else {
 250                         Enumeration e = newPrefetchSet.keys();
 251                         while(e.hasMoreElements()) {
 252                                 newpp = (PrefetchPair) e.nextElement();
 253                                 double newprob = newPrefetchSet.get(newpp).doubleValue();
 254                                 for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) {
 255                                         oldpp = (PrefetchPair) elem.nextElement();
 256                                         if(oldpp.equals(newpp)) {
 257                                                 /*Compare the difference in their probabilities */
 258                                                 double oldprob = oldPrefetchSet.get(oldpp).doubleValue();
 259                                                 if(((newprob - oldprob) > PROB_DIFF) || (newprob >= PREFETCH_THRESHOLD_PROB && oldprob < PREFETCH_THRESHOLD_PROB)) {
 260                                                         return true;
 261                                                 }
 262                                                 break;
 263                                         }
 264                                 }
 265                         }
 266                 }
 267                 return hasChanged;
 268         }
 269
 270         /** This function processes the prefetch set of FlatFieldNode
 271          * It generates a new prefetch set after comparision with its children
 272          * Then compares it with its old prefetch set
 273          * If old prefetch set is not same as new prefetch set then enqueue the parents
 274          * of the current FlatFieldNode
 275          * */
 276         private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 277                         Hashtable<FlatNode, PairMap> parentpmap) {
 278                 boolean pSetHasChanged = false;
 279                 Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
 280                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 281                 FlatFieldNode currffn = (FlatFieldNode) curr;
 282                 PairMap pm = new PairMap();
 283
 284                 /* Do Self analysis of the current node*/
 285                 FieldDescriptor currffn_field =  currffn.getField();
 286                 TempDescriptor currffn_src = currffn.getSrc();
 287                 if (currffn_field.getType().isPtr()) {
 288                         PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
 289                         Double prob = new Double(1.0);
 290                         currcopy.put(pp, prob);
 291                 }
 292
 293                 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 294                 Enumeration ecld = child_prefetch_set_copy.keys();
 295                 PrefetchPair currpp = null;
 296                 PrefetchPair childpp = null;
 297                 while (ecld.hasMoreElements()) {
 298                         childpp = (PrefetchPair) ecld.nextElement();
 299                         if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
 300                                 if (currffn.getField().getType().isPtr()) {
 301                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 302                                         newdesc.add(currffn.getField());
 303                                         newdesc.addAll(childpp.desc);
 304                                         PrefetchPair newpp =  new PrefetchPair(currffn.getSrc(), newdesc);
 305                                         Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 306                                         tocompare.put(newpp, newprob);
 307                                         pm.addPair(childpp, newpp);
 308                                         child_prefetch_set_copy.remove(childpp);
 309                                         /* Check for independence of prefetch pairs to compute new probability */
 310                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 311                                                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 312                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 313                                                         tocompare.remove(newpp);
 314                                                 } else {
 315                                                         tocompare.put(newpp, newprob);
 316                                                         pm.addPair(newpp, newpp);
 317                                                 }
 318                                                 child_prefetch_set_copy.remove(newpp);
 319                                         }
 320                                 }
 321                         } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
 322                                 child_prefetch_set_copy.remove(childpp);
 323                         } else if(isTempDescFound(childpp, currffn.getDst())) {
 324                                 child_prefetch_set_copy.remove(childpp);
 325                         } else {
 326                                 continue;
 327                         }
 328                 }
 329                 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 330                  * if so, calculate the new probability */
 331                 ecld = child_prefetch_set_copy.keys();
 332                 Enumeration e = null;
 333                 while(ecld.hasMoreElements()) {
 334                         childpp = (PrefetchPair) ecld.nextElement();
 335                         for(e = currcopy.keys(); e.hasMoreElements();) {
 336                                 currpp = (PrefetchPair) e.nextElement();
 337                                 if(currpp.equals(childpp)) {
 338                                         pm.addPair(childpp, currpp);
 339                                         child_prefetch_set_copy.remove(childpp);
 340                                         break;
 341                                 }
 342                         }
 343                 }
 344
 345                 /* Merge child prefetch pairs */
 346                 ecld = child_prefetch_set_copy.keys();
 347                 while(ecld.hasMoreElements()) {
 348                         childpp = (PrefetchPair) ecld.nextElement();
 349                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 350                         pm.addPair(childpp, childpp);
 351                         child_prefetch_set_copy.remove(childpp);
 352                 }
 353
 354                 /* Merge curr prefetch pairs */
 355                 e = currcopy.keys();
 356                 while(e.hasMoreElements()) {
 357                         currpp = (PrefetchPair) e.nextElement();
 358                         tocompare.put(currpp, currcopy.get(currpp).doubleValue());
 359                         currcopy.remove(currpp);
 360                 }
 361
 362                 /* Create prefetch mappings for child nodes */
 363                 if(!pm.isEmpty()) {
 364                         parentpmap.put(curr, pm);
 365                 }
 366
 367                 if(!pmap_hash.isEmpty()) {
 368                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 369                         if(pairmapping != null) {
 370                                 pairmapping.put(curr, pm);
 371                                 pmap_hash.put(curr.getNext(0), pairmapping);
 372                         } else {
 373                                 pmap_hash.put(curr.getNext(0), parentpmap);
 374                         }
 375                 } else {
 376                         pmap_hash.put(curr.getNext(0), parentpmap);
 377                 }
 378
 379                 /* Compare with the orginal prefetch pairs */
 380                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 381                 /* Enqueue parent nodes */
 382                 if(pSetHasChanged) {
 383                         for(int i=0; i<curr.numPrev(); i++) {
 384                                 tovisit.add(curr.getPrev(i));
 385                         }
 386                         /* Overwrite the new prefetch set to the global hash table */
 387                         prefetch_hash.put(curr,tocompare);
 388                 }
 389         }
 390
 391         /** This function processes the prefetch set of a FlatElementNode
 392          * It generates a new prefetch set after comparision with its children
 393          * It compares the old prefetch set with this new prefetch set and enqueues the parents
 394          * of the current node if change occurs and updates the global flatnode hash table
 395          * */
 396         private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 397                         Hashtable<FlatNode, PairMap> parentpmap) {
 398
 399                 boolean pSetHasChanged = false;
 400                 Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
 401                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 402                 FlatElementNode currfen = (FlatElementNode) curr;
 403                 PairMap pm = new PairMap();
 404
 405
 406                 /* Do Self analysis of the current node*/
 407                 TempDescriptor currfen_index = currfen.getIndex();
 408                 IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
 409                 TempDescriptor currfen_src = currfen.getSrc();
 410                 if(currfen.getDst().getType().isPtr()) {
 411                         PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
 412                         Double prob = new Double(1.0);
 413                         currcopy.put(pp, prob);
 414                 }
 415
 416                 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 417                 Enumeration ecld = child_prefetch_set_copy.keys();
 418                 PrefetchPair currpp = null;
 419                 while (ecld.hasMoreElements()) {
 420                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 421                         if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
 422                                 if (currfen.getDst().getType().isPtr()) {
 423                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 424                                         newdesc.add((Descriptor)idesc);
 425                                         newdesc.addAll(childpp.desc);
 426                                         PrefetchPair newpp =  new PrefetchPair(currfen.getSrc(), newdesc);
 427                                         Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 428                                         tocompare.put(newpp, newprob);
 429                                         pm.addPair(childpp, newpp);
 430                                         child_prefetch_set_copy.remove(childpp);
 431                                         /* Check for independence of prefetch pairs to compute new probability */
 432                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 433                                                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 434                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 435                                                         tocompare.remove(newpp);
 436                                                 } else {
 437                                                         tocompare.put(newpp, newprob);
 438                                                         pm.addPair(newpp, newpp);
 439                                                 }
 440                                                 child_prefetch_set_copy.remove(newpp);
 441                                         }
 442                                 }
 443                         } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
 444                                 child_prefetch_set_copy.remove(childpp);
 445                         } else if(isTempDescFound(childpp, currfen.getDst())) {
 446                                 child_prefetch_set_copy.remove(childpp);
 447                         } else {
 448                                 continue;
 449                         }
 450                 }
 451                 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 452                  * if so calculate the new probability */
 453                 ecld = child_prefetch_set_copy.keys();
 454                 Enumeration e = null;
 455                 while(ecld.hasMoreElements()) {
 456                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 457                         for(e = currcopy.keys(); e.hasMoreElements();) {
 458                                 currpp = (PrefetchPair) e.nextElement();
 459                                 if(currpp.equals(childpp)) {
 460                                         pm.addPair(childpp, currpp);
 461                                         child_prefetch_set_copy.remove(childpp);
 462                                         break;
 463                                 }
 464                         }
 465                 }
 466
 467                 /* Merge child prefetch pairs */
 468                 ecld = child_prefetch_set_copy.keys();
 469                 while(ecld.hasMoreElements()) {
 470                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 471                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 472                         pm.addPair(childpp, childpp);
 473                         child_prefetch_set_copy.remove(childpp);
 474                 }
 475
 476                 /* Merge curr prefetch pairs */
 477                 e = currcopy.keys();
 478                 while(e.hasMoreElements()) {
 479                         currpp = (PrefetchPair) e.nextElement();
 480                         tocompare.put(currpp, currcopy.get(currpp).doubleValue());
 481                         currcopy.remove(currpp);
 482                 }
 483
 484                 /* Create prefetch mappings for child nodes */
 485                 if(!pm.isEmpty()) {
 486                         parentpmap.put(curr, pm);
 487                 }
 488                 if(!pmap_hash.isEmpty()) {
 489                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 490                         if(pairmapping != null) {
 491                                 pairmapping.put(curr, pm);
 492                                 pmap_hash.put(curr.getNext(0), pairmapping);
 493                         } else {
 494                                 pmap_hash.put(curr.getNext(0), parentpmap);
 495                         }
 496                 } else {
 497                         pmap_hash.put(curr.getNext(0), parentpmap);
 498                 }
 499
 500                 /* Compare with the orginal prefetch pairs */
 501                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 502                 /* Enqueue parent nodes */
 503                 if(pSetHasChanged) {
 504                         for(int i=0; i<curr.numPrev(); i++) {
 505                                 tovisit.add(curr.getPrev(i));
 506                         }
 507                         /* Overwrite the new prefetch set to the global hash table */
 508                         prefetch_hash.put(curr,tocompare);
 509                 }
 510         }
 511
 512         /** This function processes the prefetch set of a FlatSetFieldNode
 513          * It generates a new prefetch set after comparision with its children
 514          * It compares the old prefetch set with this new prefetch set and enqueues the parents
 515          * of the current node if change occurs and then updates the global flatnode hash table
 516          * */
 517         private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 518                         Hashtable<FlatNode, PairMap> parentpmap) {
 519                 boolean pSetHasChanged = false;
 520                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 521                 FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
 522                 PairMap pm = new PairMap();
 523
 524                 Enumeration ecld = child_prefetch_set_copy.keys();
 525                 while (ecld.hasMoreElements()) {
 526                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 527                         if(childpp.base == currfsfn.getDst()) {
 528                                 int size = childpp.desc.size();
 529                                 if(size >=2) { /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */
 530                                         if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 531                                                 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 532                                                 for(int i = 0;i<(childpp.desc.size()-1); i++) {
 533                                                         newdesc.add(i,childpp.desc.get(i+1));
 534                                                 }
 535                                                 PrefetchPair newpp =  new PrefetchPair(currfsfn.getSrc(), newdesc);
 536                                                 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 537                                                 tocompare.put(newpp, newprob);
 538                                                 pm.addPair(childpp, newpp);
 539                                                 child_prefetch_set_copy.remove(childpp);
 540                                                 /* Check for independence of prefetch pairs in newly generated prefetch pair
 541                                                  * to compute new probability */
 542                                                 if(child_prefetch_set_copy.containsKey(newpp)) {
 543                                                         newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 544                                                         if(newprob < ANALYSIS_THRESHOLD_PROB) {
 545                                                                 tocompare.remove(newpp);
 546                                                         } else {
 547                                                                 tocompare.put(newpp, newprob);
 548                                                                 pm.addPair(newpp, newpp);
 549                                                         }
 550                                                         child_prefetch_set_copy.remove(newpp);
 551                                                 }
 552                                         }
 553                                 } else if(size==1) { /* e.g x.f = g (with child prefetch x.f) */
 554                                         if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 555                                                 child_prefetch_set_copy.remove(childpp);
 556                                         }
 557                                 } else {
 558                                         continue;
 559                                 }
 560                         }
 561                 }
 562
 563                 /* Merge child prefetch pairs */
 564                 ecld = child_prefetch_set_copy.keys();
 565                 while(ecld.hasMoreElements()) {
 566                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 567                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 568                         pm.addPair(childpp, childpp);
 569                         child_prefetch_set_copy.remove(childpp);
 570                 }
 571
 572                 /* Create prefetch mappings for child nodes */
 573                 if(!pm.isEmpty()) {
 574                         parentpmap.put(curr, pm);
 575                 }
 576                 if(!pmap_hash.isEmpty()) {
 577                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 578                         if(pairmapping != null) {
 579                                 pairmapping.put(curr, pm);
 580                                 pmap_hash.put(curr.getNext(0), pairmapping);
 581                         } else {
 582                                 pmap_hash.put(curr.getNext(0), parentpmap);
 583                         }
 584                 } else {
 585                         pmap_hash.put(curr.getNext(0), parentpmap);
 586                 }
 587
 588                 /* Compare with the orginal prefetch pairs */
 589                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 590                 /* Enqueue parent nodes */
 591                 if(pSetHasChanged) {
 592                         for(int i=0; i<curr.numPrev(); i++) {
 593                                 tovisit.add(curr.getPrev(i));
 594                         }
 595                         /* Overwrite the new prefetch set to the global hash table */
 596                         prefetch_hash.put(curr,tocompare);
 597                 }
 598         }
 599
 600         /** This function processes the prefetch set of a FlatSetElementNode
 601          * It generates a new prefetch set after comparision with its children
 602          * It compares the old prefetch set with this new prefetch set and enqueues the parents
 603          * of the current node if change occurs and then updates the global flatnode hash table
 604          * */
 605         private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 606                         Hashtable<FlatNode, PairMap> parentpmap) {
 607                 boolean pSetHasChanged = false;
 608                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 609                 FlatSetElementNode currfsen = (FlatSetElementNode) curr;
 610                 PairMap pm = new PairMap();
 611
 612                 Enumeration ecld = child_prefetch_set_copy.keys();
 613                 while (ecld.hasMoreElements()) {
 614                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 615                         if (childpp.base == currfsen.getDst()){
 616                                 int sizedesc = childpp.desc.size();
 617                                 if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
 618                                         int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
 619                                         if(sizetempdesc == 1) {
 620                                                 if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
 621                                                         /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */
 622                                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 623                                                         for(int i = 0;i<(childpp.desc.size()-1); i++) {
 624                                                                 newdesc.add(i,childpp.desc.get(i+1));
 625                                                         }
 626                                                         PrefetchPair newpp =  new PrefetchPair(currfsen.getSrc(), newdesc);
 627                                                         Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 628                                                         tocompare.put(newpp, newprob);
 629                                                         pm.addPair(childpp, newpp);
 630                                                         child_prefetch_set_copy.remove(childpp);
 631                                                         /* Check for independence of prefetch pairs to compute new probability */
 632                                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 633                                                                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 634                                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 635                                                                         tocompare.remove(newpp);
 636                                                                 } else {
 637                                                                         tocompare.put(newpp, newprob);
 638                                                                         pm.addPair(newpp, newpp);
 639                                                                 }
 640                                                                 child_prefetch_set_copy.remove(newpp);
 641                                                         }
 642                                                 } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1))
 643                                                         /* For e.g. a[i] = g with child prefetch set a[i] */
 644                                                         child_prefetch_set_copy.remove(childpp);
 645                                         } else {
 646                                                 continue;
 647                                         }
 648                                 }
 649                         }
 650                 }
 651                 /* Merge child prefetch pairs */
 652                 ecld = child_prefetch_set_copy.keys();
 653                 while(ecld.hasMoreElements()) {
 654                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 655                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 656                         pm.addPair(childpp, childpp);
 657                         child_prefetch_set_copy.remove(childpp);
 658                 }
 659
 660                 /* Create prefetch mappings for child nodes */
 661                 if(!pm.isEmpty()) {
 662                         parentpmap.put(curr, pm);
 663                 }
 664                 if(!pmap_hash.isEmpty()) {
 665                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 666                         if(pairmapping != null) {
 667                                 pairmapping.put(curr, pm);
 668                                 pmap_hash.put(curr.getNext(0), pairmapping);
 669                         } else {
 670                                 pmap_hash.put(curr.getNext(0), parentpmap);
 671                         }
 672                 } else {
 673                         pmap_hash.put(curr.getNext(0), parentpmap);
 674                 }
 675
 676                 /* Compare with the orginal prefetch pairs */
 677                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 678                 /* Enqueue parent nodes */
 679                 if(pSetHasChanged) {
 680                         for(int i=0; i<curr.numPrev(); i++) {
 681                                 tovisit.add(curr.getPrev(i));
 682                         }
 683                         /* Overwrite the new prefetch set to the global hash table */
 684                         prefetch_hash.put(curr,tocompare);
 685                 }
 686         }
 687
 688         /** This function applies rules and does analysis for a FlatOpNode
 689          *  And updates the global prefetch hashtable
 690          * */
 691         private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 692                         Hashtable<FlatNode, PairMap> parentpmap) {
 693                 boolean pSetHasChanged = false;
 694                 int index;
 695                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 696                 FlatOpNode currfopn = (FlatOpNode) curr;
 697                 Enumeration ecld = null;
 698                 PairMap pm = new PairMap();
 699
 700                 if(currfopn.getOp().getOp() == Operation.ASSIGN) {
 701                         ecld = child_prefetch_set_copy.keys();
 702                         while (ecld.hasMoreElements()) {
 703                                 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 704                                 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 705
 706                                 /* For cases like x=y  with child prefetch set x[i].z,x.g*/
 707                                 if(childpp.base == currfopn.getDest()) {
 708                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 709                                         newdesc.addAll(childpp.desc);
 710                                         PrefetchPair newpp =  new PrefetchPair(currfopn.getLeft(), newdesc);
 711                                         Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 712                                         tocompare.put(newpp, newprob);
 713                                         pm.addPair(childpp, newpp);
 714                                         child_prefetch_set_copy.remove(childpp);
 715                                         /* Check for independence of prefetch pairs to compute new probability */
 716                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 717                                                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 718                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 719                                                         tocompare.remove(newpp);
 720                                                 } else {
 721                                                         tocompare.put(newpp, newprob);
 722                                                         pm.addPair(newpp, newpp);
 723                                                 }
 724                                                 child_prefetch_set_copy.remove(newpp);
 725                                         }
 726                                         /* For cases like x=y  with child prefetch set r[x].p, r[p+x].q where x is a  tempdescriptor*/
 727                                 } else if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
 728                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 729                                         newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft()));
 730                                         PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 731                                         Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 732                                         tocompare.put(newpp, newprob);
 733                                         pm.addPair(childpp, newpp);
 734                                         child_prefetch_set_copy.remove(childpp);
 735                                         /* Check for independence of prefetch pairs to compute new probability*/
 736                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 737                                                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 738                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 739                                                         tocompare.remove(newpp);
 740                                                 } else {
 741                                                         tocompare.put(newpp, newprob);
 742                                                         pm.addPair(newpp, newpp);
 743                                                 }
 744                                                 child_prefetch_set_copy.remove(newpp);
 745                                         }
 746                                         newdesc = null;
 747                                         newpp = null;
 748                                 } else {
 749                                         continue;
 750                                 }
 751                         }
 752                         //case i = i+z with child prefetch set a[i].x
 753                 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
 754                         ecld = child_prefetch_set_copy.keys();
 755                         while (ecld.hasMoreElements()) {
 756                                 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 757                                 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 758
 759                                 if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
 760                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 761                                         newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft(), currfopn.getRight()));
 762                                         PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 763                                         Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
 764                                         tocompare.put(newpp, newprob);
 765                                         pm.addPair(childpp, newpp);
 766                                         child_prefetch_set_copy.remove(childpp);
 767                                         /* Check for independence of prefetch pairs to compute new probability*/
 768                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 769                                                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 770                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 771                                                         tocompare.remove(newpp);
 772                                                 } else {
 773                                                         tocompare.put(newpp, newprob);
 774                                                         pm.addPair(newpp, newpp);
 775                                                 }
 776                                                 child_prefetch_set_copy.remove(newpp);
 777                                         }
 778                                 } else {
 779                                         continue;
 780                                 }
 781                         }
 782                 } else {
 783                         //FIXME Is not taken care of for cases like x = -y followed by a[x].i
 784                 }
 785
 786                 /* Merge child prefetch pairs */
 787                 ecld = child_prefetch_set_copy.keys();
 788                 while(ecld.hasMoreElements()) {
 789                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 790                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 791                         pm.addPair(childpp, childpp);
 792                         child_prefetch_set_copy.remove(childpp);
 793                 }
 794
 795                 /* Create prefetch mappings for child nodes */
 796                 if(!pm.isEmpty()) {
 797                         parentpmap.put(curr, pm);
 798                 }
 799                 if(!pmap_hash.isEmpty()) {
 800                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 801                         if(pairmapping != null) {
 802                                 pairmapping.put(curr, pm);
 803                                 pmap_hash.put(curr.getNext(0), pairmapping);
 804                         } else {
 805                                 pmap_hash.put(curr.getNext(0), parentpmap);
 806                         }
 807                 } else {
 808                         pmap_hash.put(curr.getNext(0), parentpmap);
 809                 }
 810
 811                 /* Compare with the orginal prefetch pairs */
 812                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 813                 /* Enqueue parent nodes */
 814                 if(pSetHasChanged) {
 815                         for(int i=0; i<curr.numPrev(); i++) {
 816                                 tovisit.add(curr.getPrev(i));
 817                         }
 818                         /* Overwrite the new prefetch set to the global hash table */
 819                         prefetch_hash.put(curr,tocompare);
 820                 }
 821         }
 822
 823         /** This function processes a FlatLiteralNode where cases such as
 824          * for e.g. i = 0 with child prefetch sets a[i].r, a[j+i].r or a[j].b[i].r
 825          * are handled */
 826         private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 827                         Hashtable<FlatNode, PairMap> parentpmap) {
 828                 boolean pSetHasChanged = false;
 829                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 830                 FlatLiteralNode currfln = (FlatLiteralNode) curr;
 831                 Enumeration ecld = null;
 832                 PairMap pm = new PairMap();
 833
 834                 if(currfln.getType().isIntegerType()) {
 835                         ecld = child_prefetch_set_copy.keys();
 836                         while (ecld.hasMoreElements()) {
 837                                 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 838                                 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 839                                 if(isTempDescFound(copyofchildpp,currfln.getDst())) {
 840                                         ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
 841                                         int sizetempdesc = copychilddesc.size();
 842                                         for(ListIterator it = copychilddesc.listIterator();it.hasNext();) {
 843                                                 Object o = it.next();
 844                                                 if(o instanceof IndexDescriptor) {
 845                                                         ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
 846                                                         int sizetddesc = td.size();
 847                                                         if(td.contains(currfln.getDst())) {
 848                                                                 int index = td.indexOf(currfln.getDst());
 849                                                                 td.remove(index);
 850                                                                 ((IndexDescriptor)o).offset += (Integer)currfln.getValue();
 851                                                         }
 852                                                 }
 853                                         }
 854                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 855                                         newdesc.addAll(copychilddesc);
 856                                         PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 857                                         Double newprob = (child_prefetch_set_copy.get(childpp)).doubleValue();
 858                                         tocompare.put(newpp, newprob);
 859                                         pm.addPair(childpp, newpp);
 860                                         child_prefetch_set_copy.remove(childpp);
 861                                         /* Check for independence of prefetch pairs to compute new probability */
 862                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 863                                                 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
 864                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 865                                                         tocompare.remove(newpp);
 866                                                 } else {
 867                                                         tocompare.put(newpp, newprob);
 868                                                         pm.addPair(newpp, newpp);
 869                                                 }
 870                                                 child_prefetch_set_copy.remove(newpp);
 871                                         }
 872                                 }
 873                         }
 874                 }
 875
 876                 /* Merge child prefetch pairs */
 877                 ecld = child_prefetch_set_copy.keys();
 878                 while(ecld.hasMoreElements()) {
 879                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 880                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 881                         pm.addPair(childpp, childpp);
 882                         child_prefetch_set_copy.remove(childpp);
 883                 }
 884
 885                 /* Create prefetch mappings for child nodes */
 886                 if(!pm.isEmpty()) {
 887                         parentpmap.put(curr, pm);
 888                 }
 889                 if(!pmap_hash.isEmpty()) {
 890                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 891                         if(pairmapping != null) {
 892                                 pairmapping.put(curr, pm);
 893                                 pmap_hash.put(curr.getNext(0), pairmapping);
 894                         } else {
 895                                 pmap_hash.put(curr.getNext(0), parentpmap);
 896                         }
 897                 } else {
 898                         pmap_hash.put(curr.getNext(0), parentpmap);
 899                 }
 900
 901                 /* Compare with the orginal prefetch pairs */
 902                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 903                 /* Enqueue parent nodes */
 904                 if(pSetHasChanged) {
 905                         for(int i=0; i<curr.numPrev(); i++) {
 906                                 tovisit.add(curr.getPrev(i));
 907                         }
 908                         /* Overwrite the new prefetch set to the global hash table */
 909                         prefetch_hash.put(curr,tocompare);
 910                 }
 911         }
 912
 913         /** This function processes a FlatMethod where the method propagates
 914          * the entire prefetch set of its child node */
 915         private void processFlatMethod(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 916                         Hashtable<FlatNode, PairMap> parentpmap) {
 917                 boolean pSetHasChanged = false;
 918                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 919                 FlatMethod currfm = (FlatMethod) curr;
 920                 Enumeration ecld = null;
 921                 PairMap pm = new PairMap();
 922
 923                 /* Merge child prefetch pairs */
 924                 ecld = child_prefetch_set_copy.keys();
 925                 while(ecld.hasMoreElements()) {
 926                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 927                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 928                         pm.addPair(childpp, childpp);
 929                         child_prefetch_set_copy.remove(childpp);
 930                 }
 931
 932                 /* Create prefetch mappings for child nodes */
 933                 if(!pm.isEmpty()) {
 934                         parentpmap.put(curr, pm);
 935                 }
 936                 if(!pmap_hash.isEmpty()) {
 937                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 938                         if(pairmapping != null) {
 939                                 pairmapping.put(curr, pm);
 940                                 pmap_hash.put(curr.getNext(0), pairmapping);
 941                         } else {
 942                                 pmap_hash.put(curr.getNext(0), parentpmap);
 943                         }
 944                 } else {
 945                         pmap_hash.put(curr.getNext(0), parentpmap);
 946                 }
 947
 948                 /* Compare with the orginal prefetch pairs */
 949                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 950                 /* Enqueue parent nodes */
 951                 if(pSetHasChanged) {
 952                         /* Overwrite the new prefetch set to the global hash table */
 953                         prefetch_hash.put(curr,tocompare);
 954                 }
 955         }
 956
 957         /** This Function processes the FlatCalls
 958          * It currently drops the propagation of those prefetchpairs whose base is
 959          * same as the destination of the FlatCall
 960          */
 961         private void processFlatCall(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
 962                         Hashtable<FlatNode, PairMap> parentpmap) {
 963                 boolean pSetHasChanged = false;
 964                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
 965                 FlatCall currfcn = (FlatCall) curr;
 966                 PairMap pm = new PairMap();
 967                 Enumeration ecld = null;
 968
 969                 ecld = child_prefetch_set_copy.keys();
 970                 while(ecld.hasMoreElements()) {
 971                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
 972                         PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 973                         if(currfcn.getReturnTemp() != childpp.base) {
 974                                 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
 975                                 pm.addPair(childpp, childpp);
 976                                 child_prefetch_set_copy.remove(childpp);
 977                         } else {
 978                                 child_prefetch_set_copy.remove(childpp);
 979                         }
 980                 }
 981
 982                 /* Create prefetch mappings for child nodes */
 983                 if(!pm.isEmpty()) {
 984                         parentpmap.put(curr, pm);
 985                 }
 986                 if(!pmap_hash.isEmpty()) {
 987                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
 988                         if(pairmapping != null) {
 989                                 pairmapping.put(curr, pm);
 990                                 pmap_hash.put(curr.getNext(0), pairmapping);
 991                         } else {
 992                                 pmap_hash.put(curr.getNext(0), parentpmap);
 993                         }
 994                 } else {
 995                         pmap_hash.put(curr.getNext(0), parentpmap);
 996                 }
 997
 998                 /* Compare with the orginal prefetch pairs */
 999                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1000                 /* Enqueue parent nodes */
1001                 if(pSetHasChanged) {
1002                         for(int i=0; i<curr.numPrev(); i++) {
1003                                 tovisit.add(curr.getPrev(i));
1004                         }
1005                         /* Overwrite the new prefetch set to the global hash table */
1006                         prefetch_hash.put(curr,tocompare);
1007                 }
1008         }
1009
1010         /** This function handles the processes the FlatNode of type FlatCondBranch
1011          * It combines prefetches of both child elements and create a new hash table called
1012          * branch_prefetch_set to contains the entries of both its children
1013          */
1014         private void processFlatCondBranch(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy, int index,
1015                         Hashtable<PrefetchPair,Double> branch_prefetch_set, Hashtable<FlatNode, PairMap> parentpmap) {
1016                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();//temporary hash table
1017                 FlatCondBranch currfcb = (FlatCondBranch) curr;
1018                 PairMap pm = new PairMap();
1019                 Enumeration ecld = null;
1020
1021                 ecld = child_prefetch_set_copy.keys();
1022                 while (ecld.hasMoreElements()) {
1023                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
1024                         /* True Edge */
1025                         if(index == 0) {
1026                                 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue() * currfcb.getTrueProb();
1027                                 tocompare.put(childpp, newprob);
1028                                 pm.addPair(childpp, childpp);
1029                                 child_prefetch_set_copy.remove(childpp);
1030                         } else if(index == 1) { /* False Edge */
1031                                 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue() * currfcb.getFalseProb();
1032                                 tocompare.put(childpp, newprob);
1033                                 pm.addPair(childpp, childpp);
1034                                 child_prefetch_set_copy.remove(childpp);
1035                         } else {
1036                                 throw new Error("processFlatCondBranch() has only two child edges");
1037                         }
1038                 }
1039
1040                 /* Create prefetch mappings for child nodes */
1041                 if(!pm.isEmpty()) {
1042                         parentpmap.put(curr, pm);
1043                 }
1044                 if(!pmap_hash.isEmpty()) {
1045                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(index));
1046                         if(pairmapping != null) {
1047                                 pairmapping.put(curr, pm);
1048                                 pmap_hash.put(curr.getNext(index), pairmapping);
1049                         } else {
1050                                 pmap_hash.put(curr.getNext(index), parentpmap);
1051                         }
1052                 } else {
1053                         pmap_hash.put(curr.getNext(index), parentpmap);
1054                 }
1055
1056                 /* Update branch_prefetch_set (global hash table) to combine all prefetch pairs from childnodes of the
1057                  * cond branch that is currently stored in the tocompare hash table */
1058                 if(!tocompare.isEmpty()) {
1059                         if(index == 0) { /* True Edge */
1060                                 branch_prefetch_set.putAll(tocompare);
1061                         }else if(index == 1) { /* False Edge */
1062                                 if(branch_prefetch_set.isEmpty()) {
1063                                         branch_prefetch_set.putAll(tocompare);
1064                                 } else {
1065                                         Enumeration e = tocompare.keys();
1066                                         while(e.hasMoreElements()) {
1067                                                 PrefetchPair pp = (PrefetchPair) e.nextElement();
1068                                                 if(branch_prefetch_set.containsKey(pp)) {
1069                                                         Double newprob = (branch_prefetch_set.get(pp).doubleValue() + tocompare.get(pp).doubleValue());
1070                                                         if(newprob < ANALYSIS_THRESHOLD_PROB) {
1071                                                                 branch_prefetch_set.remove(pp);
1072                                                         } else {
1073                                                                 branch_prefetch_set.put(pp, newprob);
1074                                                         }
1075                                                 } else {
1076                                                         branch_prefetch_set.put(pp,tocompare.get(pp).doubleValue());
1077                                                 }
1078                                                 tocompare.remove(pp);
1079                                         }
1080                                 }
1081                         } else {
1082                                 throw new Error("processFlatCondBranch() has only two child edges");
1083                         }
1084                 }
1085
1086                 /* Compare prefetch sets and enqueue parent nodes: Only possible after combining prefetch pairs of both child nodes
1087                  * into branch_prefetch_set hashtable*/
1088                 if(index == 1) {
1089                         boolean pSetHasChanged = false;
1090                         /* Delete the prefetch pairs below threshold */
1091                         for(Iterator it = branch_prefetch_set.keySet().iterator(); it.hasNext();) {
1092                                 PrefetchPair pp = (PrefetchPair) it.next();
1093                                 if(branch_prefetch_set.get(pp).doubleValue() < ANALYSIS_THRESHOLD_PROB) {
1094                                         /* Delete pair mappings of PSChild-> PSParent for these prefetch pairs */
1095                                         for(int i = 0; i<curr.numNext(); i++) {
1096                                                 FlatNode fn = (FlatNode) curr.getNext(i);
1097                                                 Hashtable<FlatNode, PairMap> pairmap = pmap_hash.get(fn);
1098                                                 PairMap childpm = pairmap.get(curr);
1099                                                 if(childpm!=null && childpm.contains(pp)) {
1100                                                         childpm.removePair(pp);
1101                                                 }
1102                                         }
1103                                         branch_prefetch_set.remove(pp);
1104                                         it = branch_prefetch_set.keySet().iterator();
1105                                 }
1106                         }
1107
1108                         pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), branch_prefetch_set);
1109                         if(pSetHasChanged) {
1110                                 for(int i=0; i<curr.numPrev(); i++) {
1111                                         tovisit.add(curr.getPrev(i));
1112                                 }
1113                                 /* Overwrite the new prefetch set to the global hash table */
1114                                 prefetch_hash.put(curr,branch_prefetch_set);
1115                         }
1116                 }
1117         }
1118
1119         /** If FlatNode is not concerned with the prefetch set of its Child then propagate
1120          * prefetches up the FlatNode*/
1121         private void processDefaultCase(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
1122                         Hashtable<FlatNode, PairMap> parentpmap) {
1123                 boolean pSetHasChanged = false;
1124                 PairMap pm = new PairMap();
1125                 Enumeration e = null;
1126                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
1127
1128                 /* Propagate all child nodes */
1129                 for(e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
1130                         PrefetchPair childpp = (PrefetchPair) e.nextElement();
1131                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
1132                         pm.addPair(childpp, childpp);
1133                         child_prefetch_set_copy.remove(childpp);
1134                 }
1135
1136                 /* Check case for nodes with no children (e.g return null) and create prefetch mappings for child nodes*/
1137                 if(curr.numNext() != 0) {
1138                         if(!pm.isEmpty()) {
1139                                 parentpmap.put(curr, pm);
1140                         }
1141                         if(!pmap_hash.isEmpty()) {
1142                                 Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
1143                                 if(pairmapping != null) {
1144                                         pairmapping.put(curr, pm);
1145                                         pmap_hash.put(curr.getNext(0), pairmapping);
1146                                 } else {
1147                                         pmap_hash.put(curr.getNext(0), parentpmap);
1148                                 }
1149                         } else {
1150                                 pmap_hash.put(curr.getNext(0), parentpmap);
1151                         }
1152                 }
1153
1154                 /* Compare with old Prefetch sets */
1155                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1156                 if(pSetHasChanged){
1157                         for(int i=0; i<curr.numPrev(); i++) {
1158                                 tovisit.add(curr.getPrev(i));
1159                         }
1160                         /* Overwrite the new prefetch set to the global hash table */
1161                         prefetch_hash.put(curr,tocompare);
1162                 }
1163         }
1164
1165         /** This functions processes for FlatNewNode
1166          * for e.g x = NEW(foo) followed by childnode with prefetch set x.f
1167          * then drop the prefetches beyond this FlatNewNode */
1168         private void processFlatNewNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy,
1169                         Hashtable<FlatNode, PairMap> parentpmap) {
1170                 boolean pSetHasChanged = false;
1171                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
1172                 FlatNew currfnn = (FlatNew) curr;
1173                 Double newprob = new Double(0.0);
1174                 PairMap pm = new PairMap();
1175                 Enumeration ecld = null;
1176
1177                 ecld = child_prefetch_set_copy.keys();
1178                 while (ecld.hasMoreElements()) {
1179                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
1180                         if(childpp.base == currfnn.getDst()){
1181                                 child_prefetch_set_copy.remove(childpp);
1182                         } else if(isTempDescFound(childpp, currfnn.getDst())) {
1183                                 child_prefetch_set_copy.remove(childpp);
1184                         } else {
1185                                 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1186                                 pm.addPair(childpp, childpp);
1187                                 child_prefetch_set_copy.remove(childpp);
1188                         }
1189                 }
1190
1191                 /* Create prefetch mappings for child nodes */
1192                 if(!pm.isEmpty()) {
1193                         parentpmap.put(curr, pm);
1194                 }
1195                 if(!pmap_hash.isEmpty()) {
1196                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
1197                         if(pairmapping != null) {
1198                                 pairmapping.put(curr, pm);
1199                                 pmap_hash.put(curr.getNext(0), pairmapping);
1200                         } else {
1201                                 pmap_hash.put(curr.getNext(0), parentpmap);
1202                         }
1203                 } else {
1204                         pmap_hash.put(curr.getNext(0), parentpmap);
1205                 }
1206
1207                 /* Compare with the old prefetch set */
1208                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1209
1210                 /* Enqueue parent nodes */
1211                 if(pSetHasChanged) {
1212                         for(int i=0; i<curr.numPrev(); i++) {
1213                                 tovisit.add(curr.getPrev(i));
1214                         }
1215                         /* Overwrite the new prefetch set to the global hash table */
1216                         prefetch_hash.put(curr,tocompare);
1217                 }
1218         }
1219
1220         /** This functions processes for FlatCastNode
1221          * for e.g x = (cast type) y followed by childnode with prefetch set x.f
1222          * then drop the prefetches beyond this FlatCastNode */
1223         private void processFlatCastNode(FlatNode curr, Hashtable<PrefetchPair, Double>child_prefetch_set_copy,
1224                         Hashtable<FlatNode, PairMap> parentpmap) {
1225                 boolean pSetHasChanged = false;
1226                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
1227                 FlatCastNode currfcn = (FlatCastNode) curr;
1228                 Double newprob = new Double(0.0);
1229                 PairMap pm = new PairMap();
1230                 Enumeration ecld = null;
1231
1232                 ecld = child_prefetch_set_copy.keys();
1233                 while (ecld.hasMoreElements()) {
1234                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
1235                         if(childpp.base == currfcn.getDst()){
1236                                 child_prefetch_set_copy.remove(childpp);
1237                         } else if(isTempDescFound(childpp, currfcn.getDst())) {
1238                                 child_prefetch_set_copy.remove(childpp);
1239                         } else {
1240                                 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1241                                 pm.addPair(childpp, childpp);
1242                                 child_prefetch_set_copy.remove(childpp);
1243                         }
1244                 }
1245
1246                 /* Create prefetch mappings for child nodes */
1247                 if(!pm.isEmpty()) {
1248                         parentpmap.put(curr, pm);
1249                 }
1250                 if(!pmap_hash.isEmpty()) {
1251                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
1252                         if(pairmapping != null) {
1253                                 pairmapping.put(curr, pm);
1254                                 pmap_hash.put(curr.getNext(0), pairmapping);
1255                         } else {
1256                                 pmap_hash.put(curr.getNext(0), parentpmap);
1257                         }
1258                 } else {
1259                         pmap_hash.put(curr.getNext(0), parentpmap);
1260                 }
1261
1262                 /* Compare with the old prefetch set */
1263                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1264
1265                 /* Enqueue parent nodes */
1266                 if(pSetHasChanged) {
1267                         for(int i=0; i<curr.numPrev(); i++) {
1268                                 tovisit.add(curr.getPrev(i));
1269                         }
1270                         /* Overwrite the new prefetch set to the global hash table */
1271                         prefetch_hash.put(curr,tocompare);
1272                 }
1273         }
1274
1275         /** This functions processes for FlatTagDeclaration
1276          * for e.g x = (cast type) y followed by childnode with prefetch set x.f
1277          * then drop the prefetches beyond this FlatTagDeclaration */
1278         private void processFlatTagDeclaration(FlatNode curr, Hashtable<PrefetchPair, Double>child_prefetch_set_copy,
1279                         Hashtable<FlatNode, PairMap> parentpmap) {
1280                 boolean pSetHasChanged = false;
1281                 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
1282                 FlatTagDeclaration currftd = (FlatTagDeclaration) curr;
1283                 Double newprob = new Double(0.0);
1284                 PairMap pm = new PairMap();
1285                 Enumeration ecld = null;
1286
1287                 ecld = child_prefetch_set_copy.keys();
1288                 while (ecld.hasMoreElements()) {
1289                         PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
1290                         if(childpp.base == currftd.getDst()){
1291                                 child_prefetch_set_copy.remove(childpp);
1292                         } else if(isTempDescFound(childpp, currftd.getDst())) {
1293                                 child_prefetch_set_copy.remove(childpp);
1294                         } else {
1295                                 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
1296                                 pm.addPair(childpp, childpp);
1297                                 child_prefetch_set_copy.remove(childpp);
1298                         }
1299                 }
1300
1301                 /* Create prefetch mappings for child nodes */
1302                 if(!pm.isEmpty()) {
1303                         parentpmap.put(curr, pm);
1304                 }
1305                 if(!pmap_hash.isEmpty()) {
1306                         Hashtable<FlatNode, PairMap> pairmapping = pmap_hash.get(curr.getNext(0));
1307                         if(pairmapping != null) {
1308                                 pairmapping.put(curr, pm);
1309                                 pmap_hash.put(curr.getNext(0), pairmapping);
1310                         } else {
1311                                 pmap_hash.put(curr.getNext(0), parentpmap);
1312                         }
1313                 } else {
1314                         pmap_hash.put(curr.getNext(0), parentpmap);
1315                 }
1316
1317                 /* Compare with the old prefetch set */
1318                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1319
1320                 /* Enqueue parent nodes */
1321                 if(pSetHasChanged) {
1322                         for(int i=0; i<curr.numPrev(); i++) {
1323                                 tovisit.add(curr.getPrev(i));
1324                         }
1325                         /* Overwrite the new prefetch set to the global hash table */
1326                         prefetch_hash.put(curr,tocompare);
1327                 }
1328         }
1329
1330         /** This function prints the Prefetch pairs of a given flatnode */
1331         private void printPrefetchPairs(FlatNode fn) {
1332                 if(prefetch_hash.containsKey(fn)) {
1333                         System.out.print("Prefetch" + "(");
1334                         Hashtable<PrefetchPair, Double> currhash = (Hashtable) prefetch_hash.get(fn);
1335                         for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
1336                                 PrefetchPair pp = (PrefetchPair) pphash.nextElement();
1337                                 System.out.print(pp.toString() + ", ");
1338                         }
1339                         System.out.println(")");
1340                 } else {
1341                         System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
1342                 }
1343         }
1344
1345         private void doInsPrefetchAnalysis(FlatMethod fm, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
1346                 Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
1347                 HashSet<PrefetchPair> pset1_init = new HashSet<PrefetchPair>();
1348                 LinkedList<FlatNode> newtovisit = new LinkedList<FlatNode>();
1349                 LinkedList<FlatNode> newvisited = new LinkedList<FlatNode>();
1350
1351                 newtovisit.addLast((FlatNode)fm);
1352                 while(!newtovisit.isEmpty()) {
1353                         FlatNode fn = (FlatNode) newtovisit.iterator().next();
1354                         newtovisit.remove(0);
1355                         pset1_hash.put(fn, pset1_init); //Initialize pset1_hash
1356                         newvisited.addLast(fn);
1357                         for(int i=0; i<fn.numNext(); i++) {
1358                                 FlatNode nn = fn.getNext(i);
1359                                 if(!newtovisit.contains(nn) && !newvisited.contains(nn)){
1360                                         newtovisit.addLast(nn);
1361                                 }
1362                         }
1363                 }
1364
1365                 /* Delete redundant and subset prefetch pairs */
1366                 delSubsetPPairs();
1367
1368                 /* Start with a top down sorted order of nodes */
1369                 while(!newvisited.isEmpty()) {
1370                         applyPrefetchInsertRules((FlatNode) newvisited.getFirst(), newvisited, pset1_hash, newprefetchset);
1371                         newvisited.remove(0);
1372                 }
1373         }
1374
1375         /** This function deletes the smaller prefetch pair subset from a list of prefetch pairs
1376          * for e.g. if there are 2 prefetch pairs a.b.c.d and a.b.c for a given flatnode
1377          * then this function drops a.b.c from the prefetch set of the flatnode */
1378         private void delSubsetPPairs() {
1379                 Enumeration e = prefetch_hash.keys();
1380                 while(e.hasMoreElements()) {
1381                         FlatNode fn = (FlatNode) e.nextElement();
1382                         Hashtable ppairs = prefetch_hash.get(fn);
1383                         Enumeration epp = ((Hashtable)(prefetch_hash.get(fn))).keys();
1384                         Vector<PrefetchPair> pplist = new Vector<PrefetchPair>();
1385                         Vector pplength = new Vector();
1386                         Vector ppisMod = new Vector();
1387                         while(epp.hasMoreElements()) {
1388                                 PrefetchPair pp = (PrefetchPair) epp.nextElement();
1389                                 pplist.add(pp);
1390                                 int length = pp.desc.size()+ 1;
1391                                 pplength.add(length);
1392                                 ppisMod.add(0);
1393                         }
1394                         int numpp = ((Hashtable)(prefetch_hash.get(fn))).size();
1395                         for (int i = 0; i < numpp; i++) {
1396                                 for (int j = i+1; j < numpp; j++) {
1397                                         boolean ret;
1398                                         int x = ((Integer) (pplength.get(i))).intValue();
1399                                         if (((Integer) (pplength.get(i))).intValue() < ((Integer)( pplength.get(j))).intValue()) {
1400                                                 ret = isSubSet(pplist.get(i), pplist.get(j));
1401                                                 if (ret) {
1402                                                         ppisMod.set(i, 1);
1403                                                 }
1404                                         } else {
1405                                                 ret = isSubSet(pplist.get(j), pplist.get(i));
1406                                                 if (ret) {
1407                                                         ppisMod.set(j, 1);
1408                                                 }
1409                                         }
1410                                 }
1411                         }
1412                         for (int i = 0; i < numpp; i++) {
1413                                 if (((Integer)(ppisMod.get(i))).intValue() == 1) {
1414                                         PrefetchPair pp = (PrefetchPair) pplist.get(i);
1415                                         ppairs.remove(pp);
1416                                 }
1417                         }
1418                 }
1419         }
1420
1421         /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch
1422          * pair else it returns: false */
1423         private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) {
1424                 if (shrt.base != lng.base) {
1425                         return false;
1426                 }
1427                 for (int j = 0; j < shrt.desc.size(); j++) {
1428                         if(shrt.getDescAt(j) instanceof IndexDescriptor) {
1429                                 IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j);
1430                                 if(lng.getDescAt(j) instanceof IndexDescriptor){
1431                                         IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j);
1432                                         if(shrtid.equals(lngid)) {
1433                                                 continue;
1434                                         } else {
1435                                                 return false;
1436                                         }
1437                                 } else {
1438                                         return false;
1439                                 }
1440                         } else  {
1441                                 if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){
1442                                         return false;
1443                                 }
1444                         }
1445                 }
1446                 return true;
1447         }
1448
1449         /**This function compares all the prefetch pairs in a Prefetch set hashtable and
1450          * returns: true if something has changed in the new Prefetch set else
1451          * returns: false
1452          */
1453         private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
1454                 boolean hasChanged = false;
1455
1456                 if(oldPSet.size() != newPSet.size()) {
1457                         return true;
1458                 } else {
1459                         for(Iterator it = newPSet.iterator();it.hasNext();) {
1460                                 if(!oldPSet.contains((PrefetchPair)it.next())) {
1461                                         return true;
1462                                 }
1463                         }
1464                 }
1465                 return hasChanged;
1466         }
1467
1468         /** This function creates a set called pset1 that contains prefetch pairs that have already
1469          * been prefetched. While traversing the graph of a flat representation in a top down fashion,
1470          * this function creates pset1 such that it contains prefetch pairs that have been prefetched at
1471          * the previous nodes */
1472
1473         private void applyPrefetchInsertRules(FlatNode fn, LinkedList<FlatNode> newvisited, Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash,
1474                         Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
1475
1476                 if(fn.kind() == FKind.FlatMethod) {
1477                         HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
1478                         if(prefetch_hash.containsKey(fn)) {
1479                                 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
1480                                 for(Enumeration e = prefetchset.keys();e.hasMoreElements();) {
1481                                         PrefetchPair pp = (PrefetchPair) e.nextElement();
1482                                         /* Apply initial rule */
1483                                         if(prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB) {
1484                                                 pset1.add(pp);
1485                                         }
1486                                 }
1487                                 /* Enqueue child node if Pset1 has changed */
1488                                 if (comparePSet1(pset1_hash.get(fn), pset1)) {
1489                                         for(int j=0; j<fn.numNext(); j++) {
1490                                                 FlatNode nn = fn.getNext(j);
1491                                                 newvisited.addLast((FlatNode)nn);
1492                                         }
1493                                         pset1_hash.put(fn, pset1);
1494                                 }
1495                                 newprefetchset.put(fn, pset1);
1496                         }
1497                 } else { /* Nodes other than Flat Method Node */
1498                         HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
1499                         HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
1500                         if(prefetch_hash.containsKey(fn)) {
1501                                 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
1502                                 Hashtable<FlatNode, PairMap> ppairmaphash = pmap_hash.get(fn);
1503                                 for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
1504                                         PrefetchPair pp = (PrefetchPair) epset.nextElement();
1505                                         boolean pprobIsGreater = (prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB);
1506                                         boolean mapprobIsLess=false;
1507                                         boolean mapIsPresent=true;
1508                                         for(int i=0;i<fn.numPrev();i++) {
1509                                                 FlatNode parentnode=fn.getPrev(i);
1510                                                 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
1511                                                 /* Build newpset */
1512                                                 if(pm!=null&&pm.getPair(pp) != null) {
1513                                                         PrefetchPair mappedpp = pm.getPair(pp);
1514                                                         if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
1515                                                                 double prob = prefetch_hash.get(parentnode).get(mappedpp).doubleValue();
1516                                                                 if(prob < PREFETCH_THRESHOLD_PROB)
1517                                                                         mapprobIsLess = true;
1518                                                         }
1519                                                 } else {
1520                                                         mapprobIsLess = true;
1521                                                 }
1522                                                 /* Build pset2 */
1523                                                 if(pset1_hash.containsKey(parentnode)) {
1524                                                         if(pm !=null) {
1525                                                                 HashSet pset = pset1_hash.get(parentnode);
1526                                                                 if(pset.isEmpty()) {
1527                                                                         continue;
1528                                                                 } else {
1529                                                                         if(!pset.contains((PrefetchPair) pm.getPair(pp)))
1530                                                                                 mapIsPresent = false;
1531                                                                 }
1532                                                         }
1533                                                 } else {
1534                                                         throw new Error("applyPrefetchInsertRules() Parent node not present in pset1_hash: Not Possible");
1535                                                 }
1536                                         }
1537
1538                                         if(mapIsPresent)
1539                                                 pset2.add(pp);
1540
1541                                         if(pprobIsGreater && mapprobIsLess)
1542                                                 newpset.add(pp);
1543                                 }
1544                         } else {
1545                                 throw new Error("applyPrefetchInsertRules() fn: " +fn+ "not found");
1546                         }
1547
1548                         HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
1549                         pset1.addAll(pset2);
1550                         pset1.addAll(newpset);
1551                         /* Enqueue child node if Pset1 has changed */
1552                         if (comparePSet1(pset1_hash.get(fn), pset1)) {
1553                                 for(int i=0; i<fn.numNext(); i++) {
1554                                         FlatNode nn = fn.getNext(i);
1555                                         newvisited.addLast((FlatNode)nn);
1556                                 }
1557                                 pset1_hash.put(fn, pset1);
1558                         }
1559
1560                         /* To insert prefetch, apply rule: if the newpset minus pset2 is nonempty
1561                          * then insert a new prefetch node here*/
1562
1563                         HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
1564                         for(Iterator it = newpset.iterator(); it.hasNext();) {
1565                                 PrefetchPair pp = (PrefetchPair) it.next();
1566                                 if(!pset2.contains(pp)) {
1567                                         s.add(pp);
1568                                 }
1569                         }
1570                         newprefetchset.put(fn, s);
1571                 }
1572         }
1573
1574         private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
1575                 Enumeration e = null;
1576                 e = newprefetchset.keys();
1577                 boolean isFNPresent = false; /* Detects presence of FlatNew node */
1578                 /* This modifies the Flat representation graph */
1579                 while(e.hasMoreElements()) {
1580                         FlatNode fn = (FlatNode) e.nextElement();
1581                         FlatPrefetchNode fpn = new FlatPrefetchNode();
1582                         if(newprefetchset.get(fn).size() > 0) {
1583                                 fpn.insAllpp((HashSet)newprefetchset.get(fn));
1584                                 if(fn.kind() == FKind.FlatMethod) {
1585                                         FlatNode nn = fn.getNext(0);
1586                                         fn.setNext(0, fpn);
1587                                         fpn.addNext(nn);
1588                                 } else {
1589                                         /* Check if previous node of this FlatNode is a NEW node
1590                                          * If yes, delete this flatnode and its prefetch set from hash table
1591                                          * This eliminates prefetches for NULL ptrs*/
1592                                         for(int i = 0; i< fn.numPrev(); i++) {
1593                                                 FlatNode nn = fn.getPrev(i);
1594                                                 if(nn.kind() == FKind.FlatNew) {
1595                                                         isFNPresent = true;
1596                                                 }
1597                                         }
1598                                         if(!isFNPresent) {
1599                                                 while(fn.numPrev() > 0) {
1600                                                         FlatNode nn = fn.getPrev(0);
1601                                                         for(int j = 0; j<nn.numNext(); j++) {
1602                                                                 if(nn.getNext(j) == fn) {
1603                                                                         nn.setNext(j, fpn);
1604                                                                 }
1605                                                         }
1606                                                 }
1607                                                 fpn.addNext(fn);
1608                                         }
1609                                 } //end of else
1610                         } //End of if
1611                 } //end of while
1612         }
1613
1614         private void doAnalysis() {
1615                 Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
1616                 while(classit.hasNext()) {
1617                         ClassDescriptor cn=(ClassDescriptor)classit.next();
1618                         Iterator methodit=cn.getMethods();
1619                         while(methodit.hasNext()) {
1620                                 /* Classify parameters */
1621                                 MethodDescriptor md=(MethodDescriptor)methodit.next();
1622                                 FlatMethod fm=state.getMethodFlat(md);
1623                                 printMethod(fm);
1624                         }
1625                 }
1626         }
1627
1628         private void printMethod(FlatMethod fm) {
1629                 System.out.println(fm.getMethod()+" {");
1630                 HashSet tovisit=new HashSet();
1631                 HashSet visited=new HashSet();
1632                 int labelindex=0;
1633                 Hashtable nodetolabel=new Hashtable();
1634                 tovisit.add(fm);
1635                 FlatNode current_node=null;
1636                 //Assign labels 1st
1637                 //Node needs a label if it is
1638                 while(!tovisit.isEmpty()) {
1639                         FlatNode fn=(FlatNode)tovisit.iterator().next();
1640                         tovisit.remove(fn);
1641                         visited.add(fn);
1642
1643                         for(int i=0;i<fn.numNext();i++) {
1644                                 FlatNode nn=fn.getNext(i);
1645                                 if(i>0) {
1646                                         //1) Edge >1 of node
1647                                         nodetolabel.put(nn,new Integer(labelindex++));
1648                                 }
1649                                 if (!visited.contains(nn)&&!tovisit.contains(nn)) {
1650                                         tovisit.add(nn);
1651                                 } else {
1652                                         //2) Join point
1653                                         nodetolabel.put(nn,new Integer(labelindex++));
1654                                 }
1655                         }
1656                 }
1657                 //Do the actual printing
1658                 tovisit=new HashSet();
1659                 visited=new HashSet();
1660                 tovisit.add(fm);
1661                 while(current_node!=null||!tovisit.isEmpty()) {
1662                         if (current_node==null) {
1663                                 current_node=(FlatNode)tovisit.iterator().next();
1664                                 tovisit.remove(current_node);
1665                         }
1666                         visited.add(current_node);
1667                         if (nodetolabel.containsKey(current_node))
1668                                 System.out.println("L"+nodetolabel.get(current_node)+":");
1669                         if (current_node.numNext()==0) {
1670                                 System.out.println("   "+current_node.toString());
1671                                 current_node=null;
1672                         } else if(current_node.numNext()==1) {
1673                                 System.out.println("   "+current_node.toString());
1674                                 FlatNode nextnode=current_node.getNext(0);
1675                                 if (visited.contains(nextnode)) {
1676                                         System.out.println("goto L"+nodetolabel.get(nextnode));
1677                                         current_node=null;
1678                                 } else
1679                                         current_node=nextnode;
1680                         } else if (current_node.numNext()==2) {
1681                                 /* Branch */
1682                                 System.out.println("   "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1))));
1683                                 if (!visited.contains(current_node.getNext(1)))
1684                                         tovisit.add(current_node.getNext(1));
1685                                 if (visited.contains(current_node.getNext(0))) {
1686                                         System.out.println("goto L"+nodetolabel.get(current_node.getNext(0)));
1687                                         current_node=null;
1688                                 } else
1689                                         current_node=current_node.getNext(0);
1690                         } else throw new Error();
1691                 }
1692                 System.out.println("}");
1693         }
1694 }