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                                 printMethod(fm);
 118                         }
 119                 }
 120         }
 121
 122         /** This function calls analysis for every node in a method */
 123         private void doFlatNodeAnalysis(FlatMethod fm) {
 124                 tovisit = fm.getNodeSet();
 125                 Hashtable<PrefetchPair, Float> nodehash = new Hashtable<PrefetchPair, Float>();
 126                 /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
 127                 while(!tovisit.isEmpty()) {
 128                         FlatNode fn = (FlatNode)tovisit.iterator().next();
 129                         prefetch_hash.put(fn, nodehash);
 130                         tovisit.remove(fn);
 131                 }
 132                 /* Visit and process nodes */
 133                 tovisit = fm.getNodeSet();
 134                 while(!tovisit.isEmpty()) {
 135                         FlatNode fn = (FlatNode)tovisit.iterator().next();
 136                         doChildNodeAnalysis(fn);
 137                         tovisit.remove(fn);
 138                 }
 139         }
 140
 141         /**
 142          * This function generates the prefetch sets for a given Flatnode considering the kind of node
 143          * It calls severals functions based on the kind of the node and
 144          * returns true: if the prefetch set has changed since last time the node was analysed
 145          * returns false : otherwise
 146          */
 147         private void doChildNodeAnalysis(FlatNode curr) {
 148                 Hashtable<PrefetchPair, Float> child_prefetch_set_copy = new Hashtable<PrefetchPair, Float>();
 149                 Hashtable<FlatNode, PairMap> parentpmap = new Hashtable<FlatNode, PairMap>();
 150                 FlatNode child_node = null;
 151                 if(curr.numNext() != 0) {
 152                         child_node = curr.getNext(0);
 153                         if(prefetch_hash.containsKey(child_node)) {
 154                                 child_prefetch_set_copy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
 155                         }
 156                 }
 157
 158                 switch(curr.kind()) {
 159                         case FKind.FlatBackEdge:
 160                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 161                                 break;
 162                         case FKind.FlatCall:
 163                                 //TODO change it to take care of FlatMethod, Flatcalls
 164                                 processFlatCall(curr, child_prefetch_set_copy, parentpmap);
 165                                 break;
 166                         case FKind.FlatCheckNode:
 167                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 168                                 break;
 169                         case FKind.FlatMethod:
 170                                 //TODO change it to take care of FlatMethod, Flatcalls
 171                                 processFlatMethod(curr, child_prefetch_set_copy, parentpmap);
 172                                 break;
 173                         case FKind.FlatNew:
 174                                 processFlatNewNode(curr, child_prefetch_set_copy, parentpmap);
 175                                 break;
 176                         case FKind.FlatReturnNode:
 177                                 //TODO change it to take care of FlatMethod, Flatcalls
 178                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 179                                 break;
 180                         case FKind.FlatFieldNode:
 181                                 processFlatFieldNode(curr, child_prefetch_set_copy, parentpmap);
 182                                 break;
 183                         case FKind.FlatElementNode:
 184                                 processFlatElementNode(curr, child_prefetch_set_copy, parentpmap);
 185                                 break;
 186                         case FKind.FlatCondBranch:
 187                                 branch_prefetch_set =  new Hashtable<PrefetchPair,Float>();
 188                                 for (int i = 0; i < curr.numNext(); i++) {
 189                                         parentpmap = new Hashtable<FlatNode, PairMap>();
 190                                         child_node = curr.getNext(i);
 191                                         if (prefetch_hash.containsKey(child_node)) {
 192                                                 child_prefetch_set_copy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
 193                                         }
 194                                         processFlatCondBranch(curr, child_prefetch_set_copy, i, branch_prefetch_set, parentpmap);
 195                                 }
 196                                 break;
 197                         case FKind.FlatOpNode:
 198                                 processFlatOpNode(curr, child_prefetch_set_copy,parentpmap);
 199                                 break;
 200                         case FKind.FlatLiteralNode:
 201                                 processFlatLiteralNode(curr, child_prefetch_set_copy, parentpmap);
 202                                 break;
 203                         case FKind.FlatSetElementNode:
 204                                 processFlatSetElementNode(curr, child_prefetch_set_copy, parentpmap);
 205                                 break;
 206                         case FKind.FlatSetFieldNode:
 207                                 processFlatSetFieldNode(curr, child_prefetch_set_copy, parentpmap);
 208                                 break;
 209                         case FKind.FlatAtomicEnterNode:
 210                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 211                                 break;
 212                         case FKind.FlatAtomicExitNode:
 213                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 214                                 break;
 215                         case FKind.FlatCastNode:
 216                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 217                                 break;
 218                         case FKind.FlatFlagActionNode:
 219                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 220                                 break;
 221                         case FKind.FlatGlobalConvNode:
 222                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 223                                 break;
 224                         case FKind.FlatNop:
 225                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 226                                 break;
 227                         case FKind.FlatTagDeclaration:
 228                                 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
 229                                 break;
 230                         default:
 231                                 System.out.println("NO SUCH FLATNODE");
 232                                 break;
 233                 }
 234         }
 235
 236         /**This function compares all the prefetch pairs in a Prefetch set hashtable and
 237          * returns: true if something has changed in the new Prefetch set else
 238          * returns: false
 239          */
 240         private boolean comparePrefetchSets(Hashtable<PrefetchPair, Float> oldPrefetchSet, Hashtable<PrefetchPair, Float>
 241                         newPrefetchSet) {
 242                 boolean hasChanged = false;
 243                 PrefetchPair oldpp = null;
 244                 PrefetchPair newpp = null;
 245
 246                 if(oldPrefetchSet.size() != newPrefetchSet.size()) {
 247                         if(newPrefetchSet.size() == 0) {
 248                                 return false;
 249                         }
 250                         return true;
 251                 } else {
 252                         Enumeration e = newPrefetchSet.keys();
 253                         while(e.hasMoreElements()) {
 254                                 newpp = (PrefetchPair) e.nextElement();
 255                                 float newprob = newPrefetchSet.get(newpp);
 256                                 for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) {
 257                                         oldpp = (PrefetchPair) elem.nextElement();
 258                                         if(oldpp.equals(newpp)) {
 259                                                 /*Compare the difference in their probabilities */
 260                                                 float oldprob = oldPrefetchSet.get(oldpp);
 261                                                 int diff = (int) ((newprob - oldprob)/oldprob)*100;
 262                                                 if(diff >= PROB_DIFF) {
 263                                                         return true;
 264                                                 }
 265                                                 break;
 266                                         }
 267                                 }
 268                         }
 269                 }
 270                 return hasChanged;
 271         }
 272
 273         /** This function processes the prefetch set of FlatFieldNode
 274          * It generates a new prefetch set after comparision with its children
 275          * Then compares it with its old prefetch set
 276          * If old prefetch set is not same as new prefetch set then enqueue the parents
 277          * of the current FlatFieldNode
 278          * */
 279         private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
 280                         Hashtable<FlatNode, PairMap> parentpmap) {
 281                 boolean pSetHasChanged = false;
 282                 Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
 283                 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 284                 FlatFieldNode currffn = (FlatFieldNode) curr;
 285                 PairMap pm = new PairMap();
 286
 287                 /* Do Self analysis of the current node*/
 288                 FieldDescriptor currffn_field =  currffn.getField();
 289                 TempDescriptor currffn_src = currffn.getSrc();
 290                 if (currffn_field.getType().isPtr()) {
 291                         PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
 292                         Float prob = new Float((float)1.0);
 293                         currcopy.put(pp, prob);
 294                 }
 295
 296                 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 297                 Enumeration ecld = child_prefetch_set_copy.keys();
 298                 PrefetchPair currpp = null;
 299                 PrefetchPair childpp = null;
 300                 while (ecld.hasMoreElements()) {
 301                         childpp = (PrefetchPair) ecld.nextElement();
 302                         if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
 303                                 if (currffn.getField().getType().isPtr()) {
 304                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 305                                         newdesc.add(currffn.getField());
 306                                         newdesc.addAll(childpp.desc);
 307                                         PrefetchPair newpp =  new PrefetchPair(currffn.getSrc(), newdesc);
 308                                         Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
 309                                         tocompare.put(newpp, newprob);
 310                                         pm.addPair(childpp, newpp);
 311                                         child_prefetch_set_copy.remove(childpp);
 312                                         /* Check for independence of prefetch pairs to compute new probability */
 313                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 314                                                 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 315                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 316                                                         tocompare.remove(newpp);
 317                                                 } else {
 318                                                         tocompare.put(newpp, newprob);
 319                                                         pm.addPair(newpp, newpp);
 320                                                 }
 321                                                 child_prefetch_set_copy.remove(newpp);
 322                                         }
 323                                 }
 324                         } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
 325                                 child_prefetch_set_copy.remove(childpp);
 326                         } else {
 327                                 continue;
 328                         }
 329                 }
 330                 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 331                  * if so, calculate the new probability */
 332                 ecld = child_prefetch_set_copy.keys();
 333                 Enumeration e = null;
 334                 while(ecld.hasMoreElements()) {
 335                         childpp = (PrefetchPair) ecld.nextElement();
 336                         for(e = currcopy.keys(); e.hasMoreElements();) {
 337                                 currpp = (PrefetchPair) e.nextElement();
 338                                 if(currpp.equals(childpp)) {
 339                                         Float prob = currcopy.get(currpp).floatValue();
 340                                         currcopy.put(currpp, prob);
 341                                         pm.addPair(childpp, currpp);
 342                                         child_prefetch_set_copy.remove(childpp);
 343                                         break;
 344                                 }
 345                         }
 346                 }
 347
 348                 /* Merge child prefetch pairs */
 349                 ecld = child_prefetch_set_copy.keys();
 350                 while(ecld.hasMoreElements()) {
 351                         childpp = (PrefetchPair) ecld.nextElement();
 352                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
 353                         pm.addPair(childpp, childpp);
 354                         child_prefetch_set_copy.remove(childpp);
 355                 }
 356
 357                 /* Merge curr prefetch pairs */
 358                 e = currcopy.keys();
 359                 while(e.hasMoreElements()) {
 360                         currpp = (PrefetchPair) e.nextElement();
 361                         tocompare.put(currpp, currcopy.get(currpp));
 362                         currcopy.remove(currpp);
 363                 }
 364
 365                 /* Create prefetch mappings for child nodes */
 366                 if(!pm.isEmpty()) {
 367                         parentpmap.put(curr, pm);
 368                 }
 369                 pmap_hash.put(curr.getNext(0), parentpmap);
 370
 371                 /* Compare with the orginal prefetch pairs */
 372                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 373                 /* Enqueue parent nodes */
 374                 if(pSetHasChanged) {
 375                         for(int i=0; i<curr.numPrev(); i++) {
 376                                 tovisit.add(curr.getPrev(i));
 377                         }
 378                         /* Overwrite the new prefetch set to the global hash table */
 379                         prefetch_hash.put(curr,tocompare);
 380                 }
 381         }
 382
 383         /** This function processes the prefetch set of a FlatElementNode
 384          * It generates a new prefetch set after comparision with its children
 385          * It compares the old prefetch set with this new prefetch set and enqueues the parents
 386          * of the current node if change occurs and updates the global flatnode hash table
 387          * */
 388         private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
 389                         Hashtable<FlatNode, PairMap> parentpmap) {
 390
 391                 boolean pSetHasChanged = false;
 392                 Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
 393                 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 394                 FlatElementNode currfen = (FlatElementNode) curr;
 395                 PairMap pm = new PairMap();
 396
 397
 398                 /* Do Self analysis of the current node*/
 399                 TempDescriptor currfen_index = currfen.getIndex();
 400                 IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
 401                 TempDescriptor currfen_src = currfen.getSrc();
 402                 if(currfen.getDst().getType().isPtr()) {
 403                         PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
 404                         Float prob = new Float((float)1.0);
 405                         currcopy.put(pp, prob);
 406                 }
 407
 408                 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 409                 Enumeration ecld = child_prefetch_set_copy.keys();
 410                 PrefetchPair currpp = null;
 411                 PrefetchPair childpp = null;
 412                 while (ecld.hasMoreElements()) {
 413                         childpp = (PrefetchPair) ecld.nextElement();
 414                         if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
 415                                 if (currfen.getDst().getType().isPtr()) {
 416                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 417                                         newdesc.add((Descriptor)idesc);
 418                                         newdesc.addAll(childpp.desc);
 419                                         PrefetchPair newpp =  new PrefetchPair(currfen.getSrc(), newdesc);
 420                                         Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
 421                                         tocompare.put(newpp, newprob);
 422                                         pm.addPair(childpp, newpp);
 423                                         child_prefetch_set_copy.remove(childpp);
 424                                         /* Check for independence of prefetch pairs to compute new probability */
 425                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 426                                                 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 427                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 428                                                         tocompare.remove(newpp);
 429                                                 } else {
 430                                                         tocompare.put(newpp, newprob);
 431                                                         pm.addPair(newpp, newpp);
 432                                                 }
 433                                                 child_prefetch_set_copy.remove(newpp);
 434                                         }
 435                                 }
 436                         } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
 437                                 child_prefetch_set_copy.remove(childpp);
 438                         }
 439                 }
 440                 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 441                  * if so calculate the new probability */
 442                 ecld = child_prefetch_set_copy.keys();
 443                 Enumeration e = null;
 444                 while(ecld.hasMoreElements()) {
 445                         childpp = (PrefetchPair) ecld.nextElement();
 446                         for(e = currcopy.keys(); e.hasMoreElements();) {
 447                                 currpp = (PrefetchPair) e.nextElement();
 448                                 if(currpp.equals(childpp)) {
 449                                         Float prob = currcopy.get(currpp).floatValue();
 450                                         currcopy.put(currpp, prob);
 451                                         pm.addPair(childpp, currpp);
 452                                         child_prefetch_set_copy.remove(childpp);
 453                                         break;
 454                                 }
 455                         }
 456                 }
 457
 458                 /* Merge child prefetch pairs */
 459                 ecld = child_prefetch_set_copy.keys();
 460                 while(ecld.hasMoreElements()) {
 461                         childpp = (PrefetchPair) ecld.nextElement();
 462                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
 463                         pm.addPair(childpp, childpp);
 464                         child_prefetch_set_copy.remove(childpp);
 465                 }
 466
 467                 /* Merge curr prefetch pairs */
 468                 e = currcopy.keys();
 469                 while(e.hasMoreElements()) {
 470                         currpp = (PrefetchPair) e.nextElement();
 471                         tocompare.put(currpp, currcopy.get(currpp));
 472                         currcopy.remove(currpp);
 473                 }
 474
 475                 /* Create prefetch mappings for child nodes */
 476                 if(!pm.isEmpty()) {
 477                         parentpmap.put(curr, pm);
 478                 }
 479                 pmap_hash.put(curr.getNext(0), parentpmap);
 480
 481                 /* Compare with the orginal prefetch pairs */
 482                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 483                 /* Enqueue parent nodes */
 484                 if(pSetHasChanged) {
 485                         for(int i=0; i<curr.numPrev(); i++) {
 486                                 tovisit.add(curr.getPrev(i));
 487                         }
 488                         /* Overwrite the new prefetch set to the global hash table */
 489                         prefetch_hash.put(curr,tocompare);
 490                 }
 491         }
 492
 493         /** This function processes the prefetch set of a FlatSetFieldNode
 494          * It generates a new prefetch set after comparision with its children
 495          * It compares the old prefetch set with this new prefetch set and enqueues the parents
 496          * of the current node if change occurs and then updates the global flatnode hash table
 497          * */
 498         private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
 499                         Hashtable<FlatNode, PairMap> parentpmap) {
 500                 boolean pSetHasChanged = false;
 501                 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 502                 FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
 503                 PrefetchPair childpp = null;
 504                 PairMap pm = new PairMap();
 505
 506                 Enumeration ecld = child_prefetch_set_copy.keys();
 507                 while (ecld.hasMoreElements()) {
 508                         childpp = (PrefetchPair) ecld.nextElement();
 509                         if(childpp.base == currfsfn.getDst()) {
 510                                 int size = childpp.desc.size();
 511                                 if(size >=2) {
 512                                         if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 513                                                 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 514                                                 for(int i = 0;i<(childpp.desc.size()-1); i++) {
 515                                                         newdesc.add(i,childpp.desc.get(i+1));
 516                                                 }
 517                                                 PrefetchPair newpp =  new PrefetchPair(currfsfn.getSrc(), newdesc);
 518                                                 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
 519                                                 tocompare.put(newpp, newprob);
 520                                                 pm.addPair(childpp, newpp);
 521                                                 child_prefetch_set_copy.remove(childpp);
 522                                                 /* Check for independence of prefetch pairs in newly generated prefetch pair
 523                                                  * to compute new probability */
 524                                                 if(child_prefetch_set_copy.containsKey(newpp)) {
 525                                                         newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 526                                                         if(newprob < ANALYSIS_THRESHOLD_PROB) {
 527                                                                 tocompare.remove(newpp);
 528                                                         } else {
 529                                                                 tocompare.put(newpp, newprob);
 530                                                                 pm.addPair(newpp, newpp);
 531                                                         }
 532                                                         child_prefetch_set_copy.remove(newpp);
 533                                                 }
 534                                         }
 535                                 } else if(size==1) {
 536                                         if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
 537                                                 child_prefetch_set_copy.remove(childpp);
 538                                         }
 539                                 } else {
 540                                         continue;
 541                                 }
 542                         }
 543                 }
 544
 545                 /* Merge child prefetch pairs */
 546                 ecld = child_prefetch_set_copy.keys();
 547                 while(ecld.hasMoreElements()) {
 548                         childpp = (PrefetchPair) ecld.nextElement();
 549                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
 550                         pm.addPair(childpp, childpp);
 551                         child_prefetch_set_copy.remove(childpp);
 552                 }
 553
 554                 /* Create prefetch mappings for child nodes */
 555                 if(!pm.isEmpty()) {
 556                         parentpmap.put(curr, pm);
 557                 }
 558                 pmap_hash.put(curr.getNext(0), parentpmap);
 559
 560                 /* Compare with the orginal prefetch pairs */
 561                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 562                 /* Enqueue parent nodes */
 563                 if(pSetHasChanged) {
 564                         for(int i=0; i<curr.numPrev(); i++) {
 565                                 tovisit.add(curr.getPrev(i));
 566                         }
 567                         /* Overwrite the new prefetch set to the global hash table */
 568                         prefetch_hash.put(curr,tocompare);
 569                 }
 570         }
 571
 572         /** This function processes the prefetch set of a FlatSeElementNode
 573          * It generates a new prefetch set after comparision with its children
 574          * It compares the old prefetch set with this new prefetch set and enqueues the parents
 575          * of the current node if change occurs and then updates the global flatnode hash table
 576          * */
 577         private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
 578                         Hashtable<FlatNode, PairMap> parentpmap) {
 579                 boolean pSetHasChanged = false;
 580                 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 581                 PrefetchPair childpp = null;
 582                 FlatSetElementNode currfsen = (FlatSetElementNode) curr;
 583                 PairMap pm = new PairMap();
 584
 585                 Enumeration ecld = child_prefetch_set_copy.keys();
 586                 while (ecld.hasMoreElements()) {
 587                         childpp = (PrefetchPair) ecld.nextElement();
 588                         if (childpp.base == currfsen.getDst()){
 589                                 int sizedesc = childpp.desc.size();
 590                                 if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
 591                                         int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
 592                                         if(sizetempdesc == 1) {
 593                                                 if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
 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                                                         child_prefetch_set_copy.remove(childpp);
 616                                         } else {
 617                                                 continue;
 618                                         }
 619                                 }
 620                         }
 621                 }
 622                 /* Merge child prefetch pairs */
 623                 ecld = child_prefetch_set_copy.keys();
 624                 while(ecld.hasMoreElements()) {
 625                         childpp = (PrefetchPair) ecld.nextElement();
 626                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
 627                         pm.addPair(childpp, childpp);
 628                         child_prefetch_set_copy.remove(childpp);
 629                 }
 630
 631                 /* Create prefetch mappings for child nodes */
 632                 if(!pm.isEmpty()) {
 633                         parentpmap.put(curr, pm);
 634                 }
 635                 pmap_hash.put(curr.getNext(0), parentpmap);
 636
 637                 /* Compare with the orginal prefetch pairs */
 638                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 639                 /* Enqueue parent nodes */
 640                 if(pSetHasChanged) {
 641                         for(int i=0; i<curr.numPrev(); i++) {
 642                                 tovisit.add(curr.getPrev(i));
 643                         }
 644                         /* Overwrite the new prefetch set to the global hash table */
 645                         prefetch_hash.put(curr,tocompare);
 646                 }
 647         }
 648
 649         /** This function applies rules and does analysis for a FlatOpNode
 650          *  And updates the global prefetch hashtable
 651          * */
 652         private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
 653                         Hashtable<FlatNode, PairMap> parentpmap) {
 654                 boolean pSetHasChanged = false;
 655                 int index;
 656                 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 657                 FlatOpNode currfopn = (FlatOpNode) curr;
 658                 Enumeration ecld = null;
 659                 PrefetchPair childpp = null;
 660                 PairMap pm = new PairMap();
 661
 662                 if(currfopn.getOp().getOp()== Operation.ASSIGN) {
 663                         ecld = child_prefetch_set_copy.keys();
 664                         while (ecld.hasMoreElements()) {
 665                                 childpp = (PrefetchPair) ecld.nextElement();
 666                                 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 667
 668                                 /* For cases like x=y followed by childnode t=x[i].z or t=x.g*/
 669                                 if(childpp.base == currfopn.getDest()) {
 670                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 671                                         newdesc.addAll(childpp.desc);
 672                                         PrefetchPair newpp =  new PrefetchPair(currfopn.getLeft(), newdesc);
 673                                         Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
 674                                         tocompare.put(newpp, newprob);
 675                                         pm.addPair(childpp, newpp);
 676                                         child_prefetch_set_copy.remove(childpp);
 677                                         /* Check for independence of prefetch pairs to compute new probability */
 678                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 679                                                 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 680                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 681                                                         tocompare.remove(newpp);
 682                                                 } else {
 683                                                         tocompare.put(newpp, newprob);
 684                                                         pm.addPair(newpp, newpp);
 685                                                 }
 686                                                 child_prefetch_set_copy.remove(newpp);
 687                                         }
 688                                         /* For cases like x=y followed by t = r[i].x or t =r[x].p or t = r[p+x].q*/
 689                                 } else if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
 690                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 691                                         newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft()));
 692                                         PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 693                                         Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
 694                                         tocompare.put(newpp, newprob);
 695                                         pm.addPair(childpp, newpp);
 696                                         child_prefetch_set_copy.remove(childpp);
 697                                         /* Check for independence of prefetch pairs to compute new probability*/
 698                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 699                                                 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 700                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 701                                                         tocompare.remove(newpp);
 702                                                 } else {
 703                                                         tocompare.put(newpp, newprob);
 704                                                         pm.addPair(newpp, newpp);
 705                                                 }
 706                                                 child_prefetch_set_copy.remove(newpp);
 707                                         }
 708                                 }else {
 709                                         continue;
 710                                 }
 711                         }
 712                         //case i = i+z  followed by a[i].x
 713                 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
 714                         ecld = child_prefetch_set_copy.keys();
 715                         while (ecld.hasMoreElements()) {
 716                                 childpp = (PrefetchPair) ecld.nextElement();
 717                                 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 718
 719                                 if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
 720                                         ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 721                                         newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft(), currfopn.getRight()));
 722                                         PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 723                                         Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
 724                                         tocompare.put(newpp, newprob);
 725                                         pm.addPair(childpp, newpp);
 726                                         child_prefetch_set_copy.remove(childpp);
 727                                         /* Check for independence of prefetch pairs to compute new probability*/
 728                                         if(child_prefetch_set_copy.containsKey(newpp)) {
 729                                                 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 730                                                 if(newprob < ANALYSIS_THRESHOLD_PROB) {
 731                                                         tocompare.remove(newpp);
 732                                                 } else {
 733                                                         tocompare.put(newpp, newprob);
 734                                                         pm.addPair(newpp, newpp);
 735                                                 }
 736                                                 child_prefetch_set_copy.remove(newpp);
 737                                         }
 738                                 }else {
 739                                         continue;
 740                                 }
 741                         }
 742                 } else {
 743                         //FIXME Is not taken care of for cases like x = -y followed by a[x].i
 744                 }
 745
 746                 /* Merge child prefetch pairs */
 747                 ecld = child_prefetch_set_copy.keys();
 748                 while(ecld.hasMoreElements()) {
 749                         childpp = (PrefetchPair) ecld.nextElement();
 750                         tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
 751                         pm.addPair(childpp, childpp);
 752                         child_prefetch_set_copy.remove(childpp);
 753                 }
 754
 755                 /* Create prefetch mappings for child nodes */
 756                 if(!pm.isEmpty()) {
 757                         parentpmap.put(curr, pm);
 758                 }
 759                 pmap_hash.put(curr.getNext(0), parentpmap);
 760
 761                 /* Compare with the orginal prefetch pairs */
 762                 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 763                 /* Enqueue parent nodes */
 764                 if(pSetHasChanged) {
 765                         for(int i=0; i<curr.numPrev(); i++) {
 766                                 tovisit.add(curr.getPrev(i));
 767                         }
 768                         /* Overwrite the new prefetch set to the global hash table */
 769                         prefetch_hash.put(curr,tocompare);
 770                 }
 771         }
 772
 773         /** This function processes a FlatLiteralNode where cases such as
 774          * for cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r
 775          * are handled */
 776         private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
 777                         Hashtable<FlatNode, PairMap> parentpmap) {
 778                 boolean pSetHasChanged = false;
 779                 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 780                 FlatLiteralNode currfln = (FlatLiteralNode) curr;
 781                 Enumeration ecld = null;
 782                 PrefetchPair childpp = null;
 783                 PairMap pm = new PairMap();
 784
 785                 if(currfln.getType().isIntegerType()) {
 786                         ecld = child_prefetch_set_copy.keys();
 787                         while (ecld.hasMoreElements()) {
 788                                 childpp = (PrefetchPair) ecld.nextElement();
 789                                 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 790                                 /* For cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r*/
 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 that are passed as
 893          * arguments in 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 function prints the Prefetch pairs of a given flatnode */
1108         private void printPrefetchPairs(FlatNode fn) {
1109                 if(prefetch_hash.containsKey(fn)) {
1110                         System.out.print("Prefetch" + "(");
1111                         Hashtable<PrefetchPair, Float> currhash = (Hashtable) prefetch_hash.get(fn);
1112                         for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
1113                                 PrefetchPair pp = (PrefetchPair) pphash.nextElement();
1114                                 System.out.print(pp.toString() + ", ");
1115                         }
1116                         System.out.println(")");
1117                 } else {
1118                         System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
1119                 }
1120         }
1121
1122         private void doInsPrefetchAnalysis(FlatMethod fm) {
1123                 HashSet<PrefetchPair> pset1_init = new HashSet<PrefetchPair>();
1124                 LinkedList<FlatNode> newtovisit = new LinkedList<FlatNode>();
1125                 newvisited = new LinkedList<FlatNode>();
1126
1127                 newtovisit.addLast((FlatNode)fm);
1128                 while(!newtovisit.isEmpty()) {
1129                         FlatNode fn = (FlatNode) newtovisit.iterator().next();
1130                         newtovisit.remove(0);
1131                         pset1_hash.put(fn, pset1_init);
1132                         newvisited.addLast(fn);
1133                         for(int i=0; i<fn.numNext(); i++) {
1134                                 FlatNode nn = fn.getNext(i);
1135                                 if(!newtovisit.contains(nn) && !newvisited.contains(nn)){
1136                                         newtovisit.addLast(nn);
1137                                 }
1138                         }
1139                 }
1140
1141                 while(!newvisited.isEmpty()) {
1142                         applyPrefetchInsertRules((FlatNode) newvisited.getFirst());
1143                         newvisited.remove(0);
1144                 }
1145         }
1146
1147
1148
1149         /**This function compares all the prefetch pairs in a Prefetch set hashtable and
1150          * returns: true if something has changed in the new Prefetch set else
1151          * returns: false
1152          */
1153         private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
1154                 boolean hasChanged = false;
1155
1156                 if(oldPSet.size() != newPSet.size()) {
1157                         return true;
1158                 } else {
1159                         for(Iterator it = newPSet.iterator();it.hasNext();) {
1160                                 if(!oldPSet.contains((PrefetchPair)it.next())) {
1161                                         return true;
1162                                 }
1163                         }
1164                 }
1165                 return hasChanged;
1166         }
1167
1168         private void applyPrefetchInsertRules(FlatNode fn) {
1169                 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
1170                 HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
1171                 HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
1172                 Hashtable<PrefetchPair, Float> prefetchset = new Hashtable<PrefetchPair, Float>();
1173                 boolean ppairIsPresent = false;
1174                 boolean mapIsPresent = true;
1175                 boolean pprobIsGreater = false;
1176                 boolean mapprobIsLess = false;
1177                 boolean probIsLess = false;
1178                 boolean pSet1HasChanged = false;
1179                 Enumeration e = null;
1180                 /* Create pset1 */
1181                 if(fn.kind() == FKind.FlatMethod) {
1182                         if(prefetch_hash.containsKey(fn)) {
1183                                 prefetchset = prefetch_hash.get(fn);
1184                                 e = prefetchset.keys();
1185                                 while(e.hasMoreElements()) {
1186                                         PrefetchPair pp = (PrefetchPair) e.nextElement();
1187                                         /* Apply initial rule */
1188                                         if(((float)prefetchset.get(pp).floatValue()) > PREFETCH_THRESHOLD_PROB) {
1189                                                 pset1.add(pp);
1190                                         }
1191                                 }
1192                                 /* Enqueue child node is Pset1 has changed */
1193                                 pSet1HasChanged = comparePSet1(pset1_hash.get(fn), pset1);
1194                                 if(pSet1HasChanged) {
1195                                         for(int j=0; j<fn.numNext(); j++) {
1196                                                 FlatNode nn = fn.getNext(j);
1197                                                 newvisited.addLast((FlatNode)nn);
1198                                         }
1199                                 }
1200                                 pset1_hash.put(fn, pset1);
1201                                 if(pset1.size() > 0) {
1202                                         newprefetchset.put(fn, pset1);
1203                                 }
1204                         }
1205                 } else {
1206                         if(prefetch_hash.containsKey(fn)) {
1207                                 prefetchset = prefetch_hash.get(fn);
1208                                 for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
1209                                         PrefetchPair pp = (PrefetchPair) epset.nextElement();
1210                                         /* Create pset2 */
1211                                         Hashtable<FlatNode, PairMap> ppairmaphash = new Hashtable<FlatNode, PairMap>();
1212                                         ppairmaphash = pmap_hash.get(fn);
1213                                         if(!ppairmaphash.isEmpty()) {
1214                                                 e = ppairmaphash.keys();
1215                                                 while(e.hasMoreElements()) {
1216                                                         FlatNode parentnode = (FlatNode) e.nextElement();
1217                                                         PairMap pm = (PairMap) ppairmaphash.get(parentnode);
1218                                                         if(pset1_hash.containsKey(parentnode)) {
1219                                                                 Set pset = pset1_hash.get(parentnode);
1220                                                                 if(!pset.isEmpty()) {
1221                                                                         if(ppairIsPresent = (pset.contains((PrefetchPair) pm.getPair(pp)))) {
1222                                                                                 mapIsPresent = ppairIsPresent && mapIsPresent;
1223                                                                         }
1224                                                                 } else {
1225                                                                         mapIsPresent = false;
1226                                                                 }
1227                                                         }
1228                                                 }
1229                                                 if(mapIsPresent) {
1230                                                         pset2.add(pp);
1231                                                 }
1232                                         }
1233
1234                                         /* Create newprefetchset */
1235                                         if(pprobIsGreater = (prefetchset.get(pp).floatValue() > PREFETCH_THRESHOLD_PROB)) {
1236                                                 ppairmaphash = pmap_hash.get(fn);
1237                                                 if(!ppairmaphash.isEmpty()) {
1238                                                         e = ppairmaphash.keys();
1239                                                         while(e.hasMoreElements()) {
1240                                                                 FlatNode parentnode = (FlatNode) e.nextElement();
1241                                                                 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
1242                                                                 PrefetchPair mappedpp = pm.getPair(pp);
1243                                                                 if(mappedpp != null) {
1244                                                                         if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
1245                                                                                 float prob = (float)prefetch_hash.get(parentnode).get(mappedpp).floatValue();
1246                                                                                 if(probIsLess = (prob < PREFETCH_THRESHOLD_PROB))
1247                                                                                         mapprobIsLess = mapprobIsLess || probIsLess;
1248                                                                         }
1249                                                                 } else {
1250                                                                         mapprobIsLess = false;
1251                                                                 }
1252                                                         }
1253                                                 } else {
1254                                                         mapprobIsLess = true;
1255                                                 }
1256                                         }
1257                                         if(pprobIsGreater && mapprobIsLess) {
1258                                                 newpset.add(pp);
1259                                         }
1260                                 }
1261                         }
1262                         if(!pset2.isEmpty())
1263                                 pset1.addAll(pset2);
1264                         if(!newpset.isEmpty())
1265                                 pset1.addAll(newpset);
1266                         /* Enqueue child node if Pset1 has changed */
1267                         pSet1HasChanged = comparePSet1(pset1_hash.get(fn), pset1);
1268                         if(pSet1HasChanged) {
1269                                 for(int i=0; i<fn.numNext(); i++) {
1270                                         FlatNode nn = fn.getNext(i);
1271                                         newvisited.addLast((FlatNode)nn);
1272                                 }
1273                         }
1274                         pset1_hash.put(fn, pset1);
1275                 }
1276
1277                 /* To insert prefetch apply rule */
1278                 HashSet s = null;
1279                 if(!newpset.isEmpty() && !pset2.isEmpty()) {
1280                         for(Iterator it = newpset.iterator(); it.hasNext();) {
1281                                 PrefetchPair pp = (PrefetchPair) it.next();
1282                                 if(!pset2.contains(pp)) {
1283                                         s.add(pp);
1284                                 }
1285                         }
1286                 }
1287                 if(s != null) {
1288                         newprefetchset.put(fn, s);
1289                 }
1290         }
1291
1292
1293         private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
1294                 int i;
1295                 Enumeration e = null;
1296                 e = newprefetchset.keys();
1297                 /* This modifies the graph */
1298                 while(e.hasMoreElements()) {
1299                         FlatNode fn = (FlatNode) e.nextElement();
1300                         FlatPrefetchNode fpn = new FlatPrefetchNode();
1301                         for(i = 0; i< newprefetchset.get(fn).size(); i++) {
1302                                 fpn.insAllpp((HashSet)newprefetchset.get(fn));
1303                         }
1304                         if(fn.kind() == FKind.FlatMethod) {
1305                                 FlatNode nn = fn.getNext(0);
1306                                 TempDescriptor tdsrc = new TempDescriptor("a");
1307                                 TempDescriptor tddst = new TempDescriptor("b");
1308                                 TypeDescriptor type = new TypeDescriptor("Hash");
1309                                 FlatNode fpn2 = new FlatNode();
1310                                 FlatNop fpn1 = new FlatNop();
1311                                 FlatCastNode fcn = new FlatCastNode(type,tdsrc,tddst);
1312                                 fn.setNext(0, fcn);
1313                                 fcn.addNext(nn);
1314
1315                         } else {
1316                                 while(fn.numPrev() > 0) {
1317                                         FlatNode nn = fn.getPrev(0);
1318                                         for(int j = 0; j<nn.numNext(); j++) {
1319                                                 if(nn.getNext(j) == fn) {
1320                                                         nn.setNext(j, fpn);
1321                                                 }
1322                                         }
1323                                 }
1324                                 fpn.addNext(fn);
1325                         }
1326                 }
1327         }
1328
1329         private void doAnalysis() {
1330                 Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
1331                 while(classit.hasNext()) {
1332                         ClassDescriptor cn=(ClassDescriptor)classit.next();
1333                         Iterator methodit=cn.getMethods();
1334                         while(methodit.hasNext()) {
1335                                 /* Classify parameters */
1336                                 MethodDescriptor md=(MethodDescriptor)methodit.next();
1337                                 FlatMethod fm=state.getMethodFlat(md);
1338                                 printMethod(fm);
1339                         }
1340                 }
1341         }
1342
1343         private void printMethod(FlatMethod fm) {
1344                 System.out.println(fm.getMethod()+" {");
1345                 HashSet tovisit=new HashSet();
1346                 HashSet visited=new HashSet();
1347                 int labelindex=0;
1348                 Hashtable nodetolabel=new Hashtable();
1349                 tovisit.add(fm);
1350                 FlatNode current_node=null;
1351                 //Assign labels 1st
1352                 //Node needs a label if it is
1353                 while(!tovisit.isEmpty()) {
1354                         FlatNode fn=(FlatNode)tovisit.iterator().next();
1355                         tovisit.remove(fn);
1356                         visited.add(fn);
1357
1358                         for(int i=0;i<fn.numNext();i++) {
1359                                 FlatNode nn=fn.getNext(i);
1360                                 if(i>0) {
1361                                         //1) Edge >1 of node
1362                                         nodetolabel.put(nn,new Integer(labelindex++));
1363                                 }
1364                                 if (!visited.contains(nn)&&!tovisit.contains(nn)) {
1365                                         tovisit.add(nn);
1366                                 } else {
1367                                         //2) Join point
1368                                         nodetolabel.put(nn,new Integer(labelindex++));
1369                                 }
1370                         }
1371                 }
1372                 //Do the actual printing
1373                 tovisit=new HashSet();
1374                 visited=new HashSet();
1375                 tovisit.add(fm);
1376                 while(current_node!=null||!tovisit.isEmpty()) {
1377                         if (current_node==null) {
1378                                 current_node=(FlatNode)tovisit.iterator().next();
1379                                 tovisit.remove(current_node);
1380                         }
1381                         visited.add(current_node);
1382                         if (nodetolabel.containsKey(current_node))
1383                                 System.out.println("L"+nodetolabel.get(current_node)+":");
1384                         if (current_node.numNext()==0) {
1385                                 System.out.println("   "+current_node.toString());
1386                                 current_node=null;
1387                         } else if(current_node.numNext()==1) {
1388                                 System.out.println("   "+current_node.toString());
1389                                 FlatNode nextnode=current_node.getNext(0);
1390                                 if (visited.contains(nextnode)) {
1391                                         System.out.println("goto L"+nodetolabel.get(nextnode));
1392                                         current_node=null;
1393                                 } else
1394                                         current_node=nextnode;
1395                         } else if (current_node.numNext()==2) {
1396                                 /* Branch */
1397                                 System.out.println("   "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1))));
1398                                 if (!visited.contains(current_node.getNext(1)))
1399                                         tovisit.add(current_node.getNext(1));
1400                                 if (visited.contains(current_node.getNext(0))) {
1401                                         System.out.println("goto L"+nodetolabel.get(current_node.getNext(0)));
1402                                         current_node=null;
1403                                 } else
1404                                         current_node=current_node.getNext(0);
1405                         } else throw new Error();
1406                 }
1407                 System.out.println("}");
1408         }
1409 }