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