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