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.IndexDescriptor;
   7 import IR.SymbolTable;
   8 import IR.State;
   9 import IR.TypeUtil;
  10 import IR.MethodDescriptor;
  11 import IR.Flat.*;
  12 import IR.*;
  13 import IR.ClassDescriptor;
  14
  15 public class PrefetchAnalysis {
  16     State state;
  17     CallGraph callgraph;
  18     TypeUtil typeutil;
  19     Set<FlatNode> tovisit;
  20     Hashtable<FlatNode, Hashtable<PrefetchPair, Float>> prefetch_hash;
  21     public static final int ROUNDED_MODE = 5;
  22
  23     /** This function finds if a tempdescriptor object is found in a given prefetch pair
  24      * It returns true if found else returns false*/
  25     private boolean isTempDescFound(PrefetchPair pp, TempDescriptor td) {
  26             ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  27             ListIterator it = desc.listIterator();
  28             for(;it.hasNext();) {
  29                     Object o = it.next();
  30                     if(o instanceof IndexDescriptor) {
  31                             ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
  32                             if(tdarray.contains(td)) {
  33                                     return true;
  34                             }
  35                     }
  36             }
  37             return false;
  38     }
  39
  40     /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
  41      * tempdescriptors when there is a match for FlatOpNodes or FlatLiteralNodes */
  42     private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor newtd) {
  43             ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
  44             ListIterator it = desc.listIterator();
  45             for(;it.hasNext();) {
  46                     Object currdesc = it.next();
  47                     if(currdesc instanceof IndexDescriptor) {
  48                             ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
  49                             if(tdarray.contains(td)) {
  50                                     int index = tdarray.indexOf(td);
  51                                     tdarray.set(index, newtd);
  52                             }
  53                     }
  54             }
  55             return desc;
  56     }
  57
  58     /** This function starts the prefetchanalysis */
  59     public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
  60             this.typeutil=typeutil;
  61             this.state=state;
  62             this.callgraph=callgraph;
  63             prefetch_hash = new Hashtable();
  64             DoPrefetch();
  65     }
  66
  67     /** This function starts the prefetch analysis */
  68     private void DoPrefetch() {
  69             Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
  70             while(classit.hasNext()) {
  71                     ClassDescriptor cn=(ClassDescriptor)classit.next();
  72             doMethodAnalysis(cn);
  73         }
  74     }
  75
  76     /** This function calls analysis for every method in a class */
  77     private void doMethodAnalysis(ClassDescriptor cn) {
  78             Iterator methodit=cn.getMethods();
  79             while(methodit.hasNext()) {
  80                     /* Classify parameters */
  81                     MethodDescriptor md=(MethodDescriptor)methodit.next();
  82                     FlatMethod fm=state.getMethodFlat(md);
  83                     doFlatNodeAnalysis(fm);
  84             }
  85     }
  86
  87     /** This function calls analysis for every node in a method */
  88     private void doFlatNodeAnalysis(FlatMethod fm) {
  89             tovisit = fm.getNodeSet(); //Flat nodes to process
  90             Hashtable<PrefetchPair, Float> nodehash = new Hashtable<PrefetchPair, Float>();
  91             /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
  92             while(!tovisit.isEmpty()) {
  93                     FlatNode fn = (FlatNode)tovisit.iterator().next();
  94                     prefetch_hash.put(fn, nodehash);
  95                     tovisit.remove(fn);
  96             }
  97             tovisit = fm.getNodeSet(); //Flat nodes to process
  98             while(!tovisit.isEmpty()) {
  99                     FlatNode fn = (FlatNode)tovisit.iterator().next();
 100                     /* Generate prefetch pairs after the child node analysis */
 101                     boolean curr_modified = doChildNodeAnalysis(fn);
 102                     tovisit.remove(fn);
 103             }
 104     }
 105
 106     /**
 107      * This function generates the prefetch sets for a given Flatnode considering the kind of node
 108      * It calls severals functions based on the kind of the node and
 109      * returns true: if the prefetch set has changed since last time the node was analysed
 110      * returns false : otherwise
 111      */
 112     private boolean doChildNodeAnalysis(FlatNode curr) {
 113             boolean pSetHasChanged = false;
 114             Hashtable<PrefetchPair, Float> child_hash = new Hashtable<PrefetchPair, Float>();
 115             for (int i = 0; i < curr.numNext(); i++) {
 116                     FlatNode child_node = curr.getNext(i);
 117                     if (prefetch_hash.containsKey(child_node)) {
 118                             child_hash = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
 119                     }
 120                     switch(curr.kind()) {
 121                             case FKind.FlatFieldNode:
 122                                     processFlatFieldNode(curr, child_hash);
 123                                     break;
 124                             case FKind.FlatElementNode:
 125                                     processFlatElementNode(curr, child_hash);
 126                                     break;
 127                             case FKind.FlatCondBranch:
 128                                     //processFlatCondBranchNode();
 129                                     break;
 130                             case FKind.FlatNew:
 131                                     //processFlatNewNode(curr, child_hash);
 132                                     break;
 133                             case FKind.FlatOpNode:
 134                                     processFlatOpNode(curr, child_hash);
 135                                     break;
 136                             case FKind.FlatLiteralNode:
 137                                     processFlatLiteralNode(curr, child_hash);
 138                                     break;
 139                             case FKind.FlatSetElementNode:
 140                                     processFlatSetElementNode(curr, child_hash);
 141                                     break;
 142                             case FKind.FlatSetFieldNode:
 143                                     processFlatSetFieldNode(curr, child_hash);
 144                                     break;
 145                             case FKind.FlatMethod:
 146                                     //processFlatMethod(curr, child_hash);
 147                                     break;
 148                             default:
 149                                     /*If FlatNode is not concerned with the prefetch set of its Child then propagate
 150                                      * prefetches up the FlatNode*/
 151                                     Enumeration e = null;
 152                                     Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 153                                     for(e = child_hash.keys(); e.hasMoreElements();) {
 154                                             PrefetchPair newpp = (PrefetchPair) e.nextElement();
 155                                             tocompare.put(newpp, child_hash.get(newpp));
 156                                     }
 157
 158                                     /* Compare with old Prefetch sets */
 159                                     pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 160                                     if(pSetHasChanged){
 161                                             for(int j=0; j<curr.numPrev(); j++) {
 162                                                     tovisit.add(curr.getPrev(j));
 163                                             }
 164                                             /* Overwrite the new prefetch set to the global hash table */
 165                                             prefetch_hash.put(curr,tocompare);
 166                                     }
 167                                     break;
 168                     }
 169             }
 170             return pSetHasChanged;
 171     }
 172
 173     /**This function compares all the prefetch pairs in a Prefetch set hashtable and
 174      * returns: true if something has changed in the new Prefetch set else
 175      * returns: false
 176      */
 177     private boolean comparePrefetchSets(Hashtable<PrefetchPair, Float> oldPrefetchSet, Hashtable<PrefetchPair, Float>
 178                     newPrefetchSet) {
 179             boolean hasChanged = false;
 180             PrefetchPair oldpp = null;
 181             PrefetchPair newpp = null;
 182
 183             if(oldPrefetchSet.size() != newPrefetchSet.size()) {
 184                     return true;
 185             } else {
 186                     Enumeration e = newPrefetchSet.keys();
 187                     while(e.hasMoreElements()) {
 188                             newpp = (PrefetchPair) e.nextElement();
 189                             float newprob = newPrefetchSet.get(newpp);
 190                             for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) {
 191                                     oldpp = (PrefetchPair) elem.nextElement();
 192                                     if(oldpp.equals(newpp)) {
 193                                             /*Compare the difference in their probabilities */
 194                                             float oldprob = oldPrefetchSet.get(oldpp);
 195                                             int diff = (int) ((newprob - oldprob)/oldprob)*100;
 196                                             if(diff >= ROUNDED_MODE) {
 197                                                     return true;
 198                                             }
 199                                             break;
 200                                     } else {
 201                                             return true;
 202                                     }
 203                             }
 204                     }
 205             }
 206             return hasChanged;
 207     }
 208
 209     /** This function processes the prefetch set of FlatFieldNode
 210      * It generates a new prefetch set after comparision with its children
 211      * Then compares it with its old prefetch set
 212      * If old prefetch set is not same as new prefetch set then enqueue the parents
 213      * of the current FlatFieldNode
 214      * */
 215     private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 216             boolean pSetHasChanged = false;
 217             Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
 218             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 219             FlatFieldNode currffn = (FlatFieldNode) curr;
 220
 221             /* Do Self analysis of the current node*/
 222             FieldDescriptor currffn_field =  currffn.getField();
 223             TempDescriptor currffn_src = currffn.getSrc();
 224             if (currffn_field.getType().isPtr()) {
 225                     PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
 226                     Float prob = new Float((float)1.0);
 227                     currcopy.put(pp, prob);
 228             }
 229
 230             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 231             Enumeration ecld = child_hash.keys();
 232             PrefetchPair currpp = null;
 233             PrefetchPair childpp = null;
 234             while (ecld.hasMoreElements()) {
 235                     childpp = (PrefetchPair) ecld.nextElement();
 236                     if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
 237                             if (currffn.getField().getType().isPtr()) {
 238                                     /* Create a new Prefetch set*/
 239                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 240                                     newdesc.add(currffn.getField());
 241                                     newdesc.addAll(childpp.desc);
 242                                     PrefetchPair newpp =  new PrefetchPair(currffn.getSrc(), newdesc);
 243                                     Float newprob = child_hash.get(childpp).floatValue();
 244                                     tocompare.put(newpp, newprob);
 245                                     child_hash.remove(childpp);
 246                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 247                                      * to compute new probability */
 248                                     if(child_hash.containsKey(newpp)) {
 249                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 250                                             tocompare.put(newpp, newprob);
 251                                             child_hash.remove(newpp);
 252                                     }
 253                             }
 254                     } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
 255                             child_hash.remove(childpp);
 256                     } else {
 257                             continue;
 258                     }
 259             }
 260             /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 261              * if so calculate the new probability and then remove the common one from the child prefetch set */
 262             ecld = child_hash.keys();
 263             Enumeration e = null;
 264             while(ecld.hasMoreElements()) {
 265                     childpp = (PrefetchPair) ecld.nextElement();
 266                     for(e = currcopy.keys(); e.hasMoreElements();) {
 267                             currpp = (PrefetchPair) e.nextElement();
 268                             if(currpp.equals(childpp)) {
 269                                     /* Probability of the incoming edge for a FlatFieldNode is always 100% */
 270                                     Float prob = currcopy.get(currpp).floatValue();
 271                                     currcopy.put(currpp, prob);
 272                                     child_hash.remove(childpp);
 273                                     break;
 274                             }
 275                     }
 276             }
 277
 278             /* Merge child prefetch pairs */
 279             ecld = child_hash.keys();
 280             while(ecld.hasMoreElements()) {
 281                     childpp = (PrefetchPair) ecld.nextElement();
 282                     tocompare.put(childpp, child_hash.get(childpp));
 283                     child_hash.remove(childpp);
 284             }
 285
 286             /* Merge curr prefetch pairs */
 287             e = currcopy.keys();
 288             while(e.hasMoreElements()) {
 289                     currpp = (PrefetchPair) e.nextElement();
 290                     tocompare.put(currpp, currcopy.get(currpp));
 291                     currcopy.remove(currpp);
 292             }
 293
 294             /* Compare with the orginal prefetch pairs */
 295             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 296             /* Enqueue parent nodes */
 297             if(pSetHasChanged) {
 298                     for(int i=0; i<curr.numPrev(); i++) {
 299                             tovisit.add(curr.getPrev(i));
 300                     }
 301                     /* Overwrite the new prefetch set to the global hash table */
 302                     prefetch_hash.put(curr,tocompare);
 303             }
 304     }
 305
 306     /** This function processes the prefetch set of a FlatElementNode
 307      * It generates a new prefetch set after comparision with its children
 308      * It compares the old prefetch set with this new prefetch set and enqueues the parents
 309      * of the current node if change occurs and updates the global flatnode hash table
 310      * */
 311     private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 312
 313             boolean pSetHasChanged = false;
 314             Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
 315             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 316             FlatElementNode currfen = (FlatElementNode) curr;
 317
 318             /* Do Self analysis of the current node*/
 319             TempDescriptor currfen_index = currfen.getIndex();
 320             IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
 321             TempDescriptor currfen_src = currfen.getSrc();
 322             if(currfen.getDst().getType().isPtr()) {
 323                     PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
 324                     Float prob = new Float((float)1.0);
 325                     currcopy.put(pp, prob);
 326             }
 327
 328             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 329             Enumeration ecld = child_hash.keys();
 330             PrefetchPair currpp = null;
 331             PrefetchPair childpp = null;
 332             while (ecld.hasMoreElements()) {
 333                     childpp = (PrefetchPair) ecld.nextElement();
 334                     if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
 335                             if (currfen.getDst().getType().isPtr()) {
 336                                     //TODO  Modify the Prefetch Pair to insert cases like f=a[i+1]
 337                                     //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table
 338                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 339                                     newdesc.add((Descriptor)idesc);
 340                                     newdesc.addAll(childpp.desc);
 341                                     PrefetchPair newpp =  new PrefetchPair(currfen.getSrc(), newdesc);
 342                                     Float newprob = child_hash.get(childpp).floatValue();
 343                                     tocompare.put(newpp, newprob);
 344                                     child_hash.remove(childpp);
 345                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 346                                      * to compute new probability */
 347                                     if(child_hash.containsKey(newpp)) {
 348                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 349                                             tocompare.put(newpp, newprob);
 350                                             child_hash.remove(newpp);
 351                                     }
 352                             }
 353                     } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
 354                             child_hash.remove(childpp);
 355                     }
 356             }
 357             /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 358              * if so calculate the new probability and then remove the common one from the child prefetch set */
 359             ecld = child_hash.keys();
 360             Enumeration e = null;
 361             while(ecld.hasMoreElements()) {
 362                     childpp = (PrefetchPair) ecld.nextElement();
 363                     for(e = currcopy.keys(); e.hasMoreElements();) {
 364                             currpp = (PrefetchPair) e.nextElement();
 365                             if(currpp.equals(childpp)) {
 366                                     /* Probability of the incoming edge for a FlatElementNode is always 100% */
 367                                     Float prob = currcopy.get(currpp).floatValue();
 368                                     currcopy.put(currpp, prob);
 369                                     child_hash.remove(childpp);
 370                                     break;
 371                             }
 372                     }
 373             }
 374
 375             /* Merge child prefetch pairs */
 376             ecld = child_hash.keys();
 377             while(ecld.hasMoreElements()) {
 378                     childpp = (PrefetchPair) ecld.nextElement();
 379                     tocompare.put(childpp, child_hash.get(childpp));
 380                     child_hash.remove(childpp);
 381             }
 382
 383             /* Merge curr prefetch pairs */
 384             e = currcopy.keys();
 385             while(e.hasMoreElements()) {
 386                     currpp = (PrefetchPair) e.nextElement();
 387                     tocompare.put(currpp, currcopy.get(currpp));
 388                     currcopy.remove(currpp);
 389             }
 390
 391             /* Compare with the orginal prefetch pairs */
 392             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 393             /* Enqueue parent nodes */
 394             if(pSetHasChanged) {
 395                     for(int i=0; i<curr.numPrev(); i++) {
 396                             tovisit.add(curr.getPrev(i));
 397                     }
 398                     /* Overwrite the new prefetch set to the global hash table */
 399                     prefetch_hash.put(curr,tocompare);
 400             }
 401     }
 402
 403     /** This function processes the prefetch set of a FlatSetFieldNode
 404      * It generates a new prefetch set after comparision with its children
 405      * It compares the old prefetch set with this new prefetch set and enqueues the parents
 406      * of the current node if change occurs and then updates the global flatnode hash table
 407      * */
 408     private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 409             boolean pSetHasChanged = false;
 410             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 411             FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
 412             PrefetchPair childpp = null;
 413
 414             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 415             Enumeration ecld = child_hash.keys();
 416             while (ecld.hasMoreElements()) {
 417                     childpp = (PrefetchPair) ecld.nextElement();
 418                     if(childpp.base == currfsfn.getDst()) {
 419                             if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())
 420                                             && (childpp.getDescAt(1)!= null)) {
 421                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 422                                     newdesc.addAll(1,childpp.desc);
 423                                     PrefetchPair newpp =  new PrefetchPair(currfsfn.getSrc(), newdesc);
 424                                     Float newprob = child_hash.get(childpp).floatValue();
 425                                     tocompare.put(newpp, newprob);
 426                                     child_hash.remove(childpp);
 427                                     /* Check for independence of prefetch pairs in newly generated and child_hash prefetch pairs
 428                                      * to compute new probability */
 429                                     if(child_hash.containsKey(newpp)) {
 430                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 431                                             tocompare.put(newpp, newprob);
 432                                             child_hash.remove(newpp);
 433                                     }
 434
 435                             } else if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())
 436                                             && (childpp.getDescAt(1)== null)){
 437                                     child_hash.remove(childpp);
 438                             } else {
 439                                     continue;
 440                             }
 441                     }
 442             }
 443
 444             /* Merge child prefetch pairs */
 445             ecld = child_hash.keys();
 446             while(ecld.hasMoreElements()) {
 447                     childpp = (PrefetchPair) ecld.nextElement();
 448                     tocompare.put(childpp, child_hash.get(childpp));
 449                     child_hash.remove(childpp);
 450             }
 451
 452             /* Compare with the orginal prefetch pairs */
 453             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 454             /* Enqueue parent nodes */
 455             if(pSetHasChanged) {
 456                     for(int i=0; i<curr.numPrev(); i++) {
 457                             tovisit.add(curr.getPrev(i));
 458                     }
 459                     /* Overwrite the new prefetch set to the global hash table */
 460                     prefetch_hash.put(curr,tocompare);
 461             }
 462     }
 463
 464     /** This function processes the prefetch set of a FlatSeElementNode
 465      * It generates a new prefetch set after comparision with its children
 466      * It compares the old prefetch set with this new prefetch set and enqueues the parents
 467      * of the current node if change occurs and then updates the global flatnode hash table
 468      * */
 469     private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 470             boolean pSetHasChanged = false;
 471             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 472             PrefetchPair childpp = null;
 473             FlatSetElementNode currfsen = (FlatSetElementNode) curr;
 474
 475             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 476             Enumeration ecld = child_hash.keys();
 477             while (ecld.hasMoreElements()) {
 478                     childpp = (PrefetchPair) ecld.nextElement();
 479                     //TODO Add comparision for cases like a[i+1]=f.The following only works for cases like a[i]=f
 480                     if (childpp.base == currfsen.getDst()){
 481                             if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
 482                                     if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex())
 483                                                     && (((IndexDescriptor)(childpp.getDescAt(0))).tddesc.get(1) == null) && (childpp.getDescAt(1)!=null)) {
 484                                             //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table
 485                                             ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 486                                             newdesc.addAll(1,childpp.desc);
 487                                             PrefetchPair newpp =  new PrefetchPair(currfsen.getSrc(), newdesc);
 488                                             Float newprob = child_hash.get(childpp).floatValue();
 489                                             tocompare.put(newpp, newprob);
 490                                             child_hash.remove(childpp);
 491                                             /* Check for independence of prefetch pairs if any in the child prefetch set
 492                                              * to compute new probability */
 493                                             if(child_hash.containsKey(newpp)) {
 494                                                     newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 495                                                     tocompare.put(newpp, newprob);
 496                                                     child_hash.remove(newpp);
 497                                             }
 498                                     } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) &&
 499                                                     (((IndexDescriptor) (childpp.getDescAt(0))).tddesc.get(1) == null) && (childpp.getDescAt(1)==null)) {
 500                                             child_hash.remove(childpp);
 501                                     } else {
 502                                             continue;
 503                                     }
 504                             }
 505                     }
 506             }
 507             /* Merge child prefetch pairs */
 508             ecld = child_hash.keys();
 509             while(ecld.hasMoreElements()) {
 510                     childpp = (PrefetchPair) ecld.nextElement();
 511                     tocompare.put(childpp, child_hash.get(childpp));
 512                     child_hash.remove(childpp);
 513             }
 514             /* Compare with the orginal prefetch pairs */
 515             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 516             /* Enqueue parent nodes */
 517             if(pSetHasChanged) {
 518                     for(int i=0; i<curr.numPrev(); i++) {
 519                             tovisit.add(curr.getPrev(i));
 520                     }
 521                     /* Overwrite the new prefetch set to the global hash table */
 522                     prefetch_hash.put(curr,tocompare);
 523             }
 524     }
 525
 526     /** This function applies rules and does analysis for a FlatOpNode
 527      *  And updates the global prefetch hashtable
 528      * */
 529     private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 530             boolean pSetHasChanged = false;
 531             int index;
 532             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 533             FlatOpNode currfopn = (FlatOpNode) curr;
 534             Enumeration ecld = null;
 535             PrefetchPair childpp = null;
 536
 537             /* Check the  Operation type of flatOpNode */
 538             if(currfopn.getOp().getOp()== Operation.ASSIGN) {
 539                     ecld = child_hash.keys();
 540                     while (ecld.hasMoreElements()) {
 541                             childpp = (PrefetchPair) ecld.nextElement();
 542                             PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 543
 544                             /* Base of child prefetch pair same as destination of the current FlatOpNode
 545                              * For cases like x=y followed by t=x[i] or t=x.g*/
 546                             if(childpp.base == currfopn.getDest()) {
 547                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 548                                     newdesc.addAll(childpp.desc);
 549                                     PrefetchPair newpp =  new PrefetchPair(currfopn.getLeft(), newdesc);
 550                                     Float newprob = child_hash.get(childpp).floatValue();
 551                                     tocompare.put(newpp, newprob);
 552                                     child_hash.remove(childpp);
 553                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 554                                      * to compute new probability */
 555                                     if(child_hash.containsKey(newpp)) {
 556                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 557                                             tocompare.put(newpp, newprob);
 558                                             child_hash.remove(newpp);
 559                                     }
 560                                     /* Any member of the desc of child prefetch pair is same as destination of the current FlatOpNode
 561                                      * For cases like x=y followed by t = r[i].x or t =r[x].p or t = r[p+x].q*/
 562                             } else if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
 563                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 564                                     newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft()));
 565                                     //ArrayList<Descriptor> newdesc = (ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft());
 566                                     PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 567                                     Float newprob = child_hash.get(childpp).floatValue();
 568                                     tocompare.put(newpp, newprob);
 569                                     child_hash.remove(childpp);
 570                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 571                                      * to compute new probability*/
 572                                     if(child_hash.containsKey(newpp)) {
 573                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 574                                             tocompare.put(newpp, newprob);
 575                                             child_hash.remove(newpp);
 576                                     }
 577                             }else {
 578                                     continue;
 579                             }
 580                     }
 581             } else if(currfopn.getRight()!=null) {
 582                     //FIXME case i = i+z followed by a[i].x
 583             } else {
 584                     //FIXME
 585             }
 586
 587             /* Merge child prefetch pairs */
 588             ecld = child_hash.keys();
 589             while(ecld.hasMoreElements()) {
 590                     childpp = (PrefetchPair) ecld.nextElement();
 591                     tocompare.put(childpp, child_hash.get(childpp));
 592                     child_hash.remove(childpp);
 593             }
 594
 595             /* Compare with the orginal prefetch pairs */
 596             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 597             /* Enqueue parent nodes */
 598             if(pSetHasChanged) {
 599                     for(int i=0; i<curr.numPrev(); i++) {
 600                             tovisit.add(curr.getPrev(i));
 601                     }
 602                     /* Overwrite the new prefetch set to the global hash table */
 603                     prefetch_hash.put(curr,tocompare);
 604             }
 605     }
 606
 607     private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 608             boolean pSetHasChanged = false;
 609             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 610             FlatLiteralNode currfln = (FlatLiteralNode) curr;
 611             Enumeration ecld = null;
 612             PrefetchPair childpp = null;
 613
 614             if(currfln.getType().isIntegerType()) {
 615                     ecld = child_hash.keys();
 616                     while (ecld.hasMoreElements()) {
 617                             childpp = (PrefetchPair) ecld.nextElement();
 618                             PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
 619                             /* Check for same index in child prefetch pairs
 620                              * for cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r*/
 621                             if(isTempDescFound(copyofchildpp,currfln.getDst())) {
 622                                     ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
 623                                     ListIterator it = copychilddesc.listIterator();
 624                                     for(;it.hasNext();) {
 625                                             Object o = it.next();
 626                                             if(o instanceof IndexDescriptor) {
 627                                                     ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
 628                                                     for(ListIterator lit = td.listIterator();lit.hasNext();) {
 629                                                             if(td.contains(currfln.getDst())) {
 630                                                                     int index = td.indexOf(currfln.getDst());
 631                                                                     ((IndexDescriptor)o).offset = (Integer)currfln.getValue();
 632                                                                     td.remove(index);
 633                                                             }
 634                                                     }
 635                                             }
 636                                     }
 637                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 638                                     newdesc.addAll(copychilddesc);
 639                                     PrefetchPair newpp =  new PrefetchPair(childpp.base, newdesc);
 640                                     Float newprob = (child_hash.get(childpp)).floatValue();
 641                                     tocompare.put(newpp, newprob);
 642                                     child_hash.remove(childpp);
 643                                     /* Check for independence of prefetch pairs if any in the child prefetch set
 644                                      * to compute new probability */
 645                                     if(child_hash.containsKey(newpp)) {
 646                                             newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
 647                                             tocompare.put(newpp, newprob);
 648                                             child_hash.remove(newpp);
 649                                     }
 650                             }
 651                     }
 652             }
 653
 654             /* Merge child prefetch pairs */
 655             ecld = child_hash.keys();
 656             while(ecld.hasMoreElements()) {
 657                     childpp = (PrefetchPair) ecld.nextElement();
 658                     tocompare.put(childpp, child_hash.get(childpp));
 659                     child_hash.remove(childpp);
 660             }
 661
 662             /* Compare with the orginal prefetch pairs */
 663             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 664             /* Enqueue parent nodes */
 665             if(pSetHasChanged) {
 666                     for(int i=0; i<curr.numPrev(); i++) {
 667                             tovisit.add(curr.getPrev(i));
 668                     }
 669                     /* Overwrite the new prefetch set to the global hash table */
 670                     prefetch_hash.put(curr,tocompare);
 671             }
 672
 673     }
 674
 675     private void processFlatMethod() {
 676
 677     }
 678
 679     /** This function prints the Prefetch pairs of a given flatnode */
 680     private void printPrefetchPairs(FlatNode fn) {
 681             if(prefetch_hash.containsKey(fn)) {
 682                     System.out.print("Prefetch" + "(");
 683                     Hashtable<PrefetchPair, Float> currhash = (Hashtable) prefetch_hash.get(fn);
 684                     for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
 685                             PrefetchPair pp = (PrefetchPair) pphash.nextElement();
 686                             System.out.print(pp.toString() + ", ");
 687                     }
 688                     System.out.println(")");
 689             } else {
 690                     System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
 691             }
 692     }
 693
 694     private void doAnalysis() {
 695         Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
 696         while(classit.hasNext()) {
 697             ClassDescriptor cn=(ClassDescriptor)classit.next();
 698             Iterator methodit=cn.getMethods();
 699             while(methodit.hasNext()) {
 700                 /* Classify parameters */
 701                 MethodDescriptor md=(MethodDescriptor)methodit.next();
 702                 FlatMethod fm=state.getMethodFlat(md);
 703                 printMethod(fm);
 704             }
 705         }
 706     }
 707
 708     private void printMethod(FlatMethod fm) {
 709         System.out.println(fm.getMethod()+" {");
 710         HashSet tovisit=new HashSet();
 711         HashSet visited=new HashSet();
 712         int labelindex=0;
 713         Hashtable nodetolabel=new Hashtable();
 714         tovisit.add(fm);
 715         FlatNode current_node=null;
 716         //Assign labels 1st
 717         //Node needs a label if it is
 718         while(!tovisit.isEmpty()) {
 719             FlatNode fn=(FlatNode)tovisit.iterator().next();
 720             tovisit.remove(fn);
 721             visited.add(fn);
 722
 723             for(int i=0;i<fn.numNext();i++) {
 724                 FlatNode nn=fn.getNext(i);
 725                 if(i>0) {
 726                     //1) Edge >1 of node
 727                     nodetolabel.put(nn,new Integer(labelindex++));
 728                 }
 729                 if (!visited.contains(nn)&&!tovisit.contains(nn)) {
 730                     tovisit.add(nn);
 731                 } else {
 732                     //2) Join point
 733                     nodetolabel.put(nn,new Integer(labelindex++));
 734                 }
 735             }
 736         }
 737         //Do the actual printing
 738         tovisit=new HashSet();
 739         visited=new HashSet();
 740         tovisit.add(fm);
 741         while(current_node!=null||!tovisit.isEmpty()) {
 742             if (current_node==null) {
 743                 current_node=(FlatNode)tovisit.iterator().next();
 744                 tovisit.remove(current_node);
 745             }
 746             visited.add(current_node);
 747             if (nodetolabel.containsKey(current_node))
 748                 System.out.println("L"+nodetolabel.get(current_node)+":");
 749             if (current_node.numNext()==0) {
 750                 System.out.println("   "+current_node.toString());
 751                 current_node=null;
 752             } else if(current_node.numNext()==1) {
 753                 System.out.println("   "+current_node.toString());
 754                 FlatNode nextnode=current_node.getNext(0);
 755                 if (visited.contains(nextnode)) {
 756                     System.out.println("goto L"+nodetolabel.get(nextnode));
 757                     current_node=null;
 758                 } else
 759                     current_node=nextnode;
 760             } else if (current_node.numNext()==2) {
 761                 /* Branch */
 762                 System.out.println("   "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1))));
 763                 if (!visited.contains(current_node.getNext(1)))
 764                     tovisit.add(current_node.getNext(1));
 765                 if (visited.contains(current_node.getNext(0))) {
 766                     System.out.println("goto L"+nodetolabel.get(current_node.getNext(0)));
 767                     current_node=null;
 768                 } else
 769                     current_node=current_node.getNext(0);
 770             } else throw new Error();
 771         }
 772         System.out.println("}");
 773     }
 774
 775 }