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 IR.SymbolTable;
   7 import IR.State;
   8 import IR.TypeUtil;
   9 import IR.MethodDescriptor;
  10 import IR.Flat.*;
  11 import IR.*;
  12 import IR.ClassDescriptor;
  13
  14 public class PrefetchAnalysis {
  15     State state;
  16     CallGraph callgraph;
  17     TypeUtil typeutil;
  18     Set<FlatNode> tovisit;
  19     Hashtable<FlatNode, Hashtable<PrefetchPair, Float>> prefetch_hash;
  20     public static final int ROUNDED_MODE = 5;
  21
  22     public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
  23         this.typeutil=typeutil;
  24         this.state=state;
  25         this.callgraph=callgraph;
  26         prefetch_hash = new Hashtable();
  27         DoPrefetch();
  28     }
  29
  30     /** This function starts the prefetch analysis */
  31     private void DoPrefetch() {
  32         Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
  33         while(classit.hasNext()) {
  34             ClassDescriptor cn=(ClassDescriptor)classit.next();
  35             doMethodAnalysis(cn);
  36         }
  37     }
  38
  39     /** This function calls analysis for every method in a class */
  40     private void doMethodAnalysis(ClassDescriptor cn) {
  41             Iterator methodit=cn.getMethods();
  42             while(methodit.hasNext()) {
  43                     /* Classify parameters */
  44                     MethodDescriptor md=(MethodDescriptor)methodit.next();
  45                     FlatMethod fm=state.getMethodFlat(md);
  46                     doFlatNodeAnalysis(fm);
  47             }
  48     }
  49
  50     /** This function calls analysis for every node in a method */
  51     private void doFlatNodeAnalysis(FlatMethod fm) {
  52             tovisit = fm.getNodeSet(); //Flat nodes to process
  53             while(!tovisit.isEmpty()) {
  54                     FlatNode fn = (FlatNode)tovisit.iterator().next();
  55                     /* Generate self node prefetch pairs */
  56                     doNodePrefetch(fn);
  57                     /* Generate prefetch pairs after the child node analysis */
  58                     boolean curr_modified = doNodeChildPrefetch(fn);
  59                     tovisit.remove(fn);
  60             }
  61     }
  62
  63     /**
  64      * This function generates initial prefetch pair for a Flat node that is of the
  65      * following  kind FlatFieldNode, FlatElementNode, FlatSetFieldNode or FlatSetElementNode
  66      * */
  67     private void doNodePrefetch(FlatNode fn) {
  68             Hashtable<PrefetchPair, Float> nodehash = new Hashtable<PrefetchPair, Float>();
  69             switch(fn.kind()) {
  70                     case FKind.FlatFieldNode:
  71                             FlatFieldNode currffn = (FlatFieldNode) fn;
  72                             FieldDescriptor currffn_field =  currffn.getField();
  73                             TempDescriptor currffn_src = currffn.getSrc();
  74                             if (currffn_field.getType().isPtr()) {
  75                                     Boolean b = new Boolean(false);
  76                                     PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field, b);
  77                                     Float prob = new Float((float)1.0);
  78                                     nodehash.put(pp, prob);
  79                                     prefetch_hash.put(fn, nodehash);
  80                             }
  81                             break;
  82                     case FKind.FlatElementNode:
  83                             FlatElementNode currfen = (FlatElementNode) fn;
  84                             TempDescriptor currfen_index = currfen.getIndex();
  85                             TempDescriptor currfen_src = currfen.getSrc();
  86                             if(currfen.getDst().getType().isPtr()) {
  87                                     PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) currfen_index, true);
  88                                     Float prob = new Float((float)1.0);
  89                                     nodehash.put(pp, prob);
  90                                     prefetch_hash.put(fn, nodehash);
  91                             }
  92                             break;
  93                     case FKind.FlatSetFieldNode:
  94                             FlatSetFieldNode currfsfn = (FlatSetFieldNode) fn;
  95                             TempDescriptor currfsfn_src = currfsfn.getSrc();
  96                             if (currfsfn_src.getType().isPtr()) {
  97                                     PrefetchPair pp = new PrefetchPair(currfsfn_src);
  98                                     Float prob = new Float((float)1.0);
  99                                     nodehash.put(pp, prob);
 100                                     prefetch_hash.put(fn, nodehash);
 101                             }
 102                             break;
 103                     case FKind.FlatSetElementNode:
 104                             FlatSetElementNode currfsen = (FlatSetElementNode) fn;
 105                             TempDescriptor currfsen_src = currfsen.getSrc();
 106                             if (currfsen_src.getType().isPtr()) {
 107                                     PrefetchPair pp = new PrefetchPair(currfsen_src);
 108                                     Float prob = new Float((float)1.0);
 109                                     nodehash.put(pp, prob);
 110                                     prefetch_hash.put(fn, nodehash);
 111                             }
 112                             break;
 113                     default:
 114                             break;
 115             }
 116     }
 117
 118     /**
 119      * This function generates the prefetch sets for a given Flatnode considering the kind of node
 120      * It calls severals functions based on the kind of the node and
 121      * returns true: if the prefetch set has changed since last time the node was analysed
 122      * returns false : otherwise
 123      */
 124     private boolean doNodeChildPrefetch(FlatNode curr) {
 125             boolean ppSetHasChanged = false;
 126             Hashtable<PrefetchPair, Float> child_hash = new Hashtable<PrefetchPair, Float>();
 127             for (int i = 0; i < curr.numNext(); i++) {
 128                     FlatNode child_node = curr.getNext(i);
 129                     if (prefetch_hash.containsKey(child_node)) {
 130                             child_hash = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
 131                     }
 132                     switch(curr.kind()) {
 133                             case FKind.FlatFieldNode:
 134                                     if(prefetch_hash.containsKey(curr)) {
 135                                             processFlatFieldNode(curr, child_hash);
 136                                     } else {
 137                                             prefetch_hash.put(curr, child_hash);
 138                                     }
 139                                     break;
 140                             case FKind.FlatElementNode:
 141                                     if(prefetch_hash.containsKey(curr)) {
 142                                             processFlatElementNode(curr, child_hash);
 143                                     } else {
 144                                             prefetch_hash.put(curr, child_hash);
 145                                     }
 146                                     break;
 147                             case FKind.FlatCall:
 148                                     //processFlatCallNode();
 149                                     break;
 150                             case FKind.FlatCondBranch:
 151                                     //processFlatCondBranchNode();
 152                                     break;
 153                             case FKind.FlatNew:
 154                                     //processFlatNewNode();
 155                                     break;
 156                             case FKind.FlatOpNode:
 157                                     //processFlatOpNode();
 158                                     break;
 159                             case FKind.FlatSetElementNode:
 160                                     //processFlatSetElementNode();
 161                                     break;
 162                             case FKind.FlatSetFieldNode:
 163                                     //processFlatSetFieldNode();
 164                                     break;
 165                             default:
 166                                     /*If FlatNode is not concerned with the prefetch set of its Child then propagate
 167                                      * prefetches up the FlatNode*/
 168                                     //TODO make this a new method
 169                                     if(prefetch_hash.containsKey(curr)) {
 170                                             Hashtable<PrefetchPair, Float> currcopy = (Hashtable<PrefetchPair,Float>)prefetch_hash.get(curr).clone();
 171                                             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 172                                             Enumeration e = currcopy.keys();
 173                                             while (e.hasMoreElements()) {
 174                                                     PrefetchPair pp = (PrefetchPair) e.nextElement();
 175                                                     if (child_hash.contains(pp)) {
 176                                                             Float cprob = child_hash.get(pp);
 177                                                             Float fprob = currcopy.get(pp);
 178                                                             // TODO fix this
 179                                                             Float newprob = cprob.floatValue() * fprob.floatValue();
 180                                                             tocompare.put(pp, newprob);
 181                                                             child_hash.remove(pp);
 182                                                     } else {
 183                                                             tocompare.put(pp, currcopy.get(pp));
 184                                                     }
 185                                             }
 186                                             for(e = child_hash.keys(); e.hasMoreElements();) {
 187                                                     PrefetchPair newpp = (PrefetchPair) e.nextElement();
 188                                                     tocompare.put(newpp, child_hash.get(newpp));
 189                                             }
 190                                             /* Compare with old Prefetch sets */
 191                                             ppSetHasChanged = comparePrefetchSets(currcopy, tocompare);
 192
 193                                     } else {
 194                                             /* Add the child prefetch set to Curr FlatNode */
 195                                             prefetch_hash.put(curr, child_hash);
 196                                     }
 197                                     break;
 198                     }
 199             }
 200             return ppSetHasChanged;
 201     }
 202
 203     /**This function compares all the prefetch pairs in a Prefetch set hashtable and
 204      * returns: true if something has changed in the new Prefetch set else
 205      * returns: false
 206      */
 207     private boolean comparePrefetchSets(Hashtable<PrefetchPair, Float> oldPrefetchSet, Hashtable<PrefetchPair, Float>
 208                     newPrefetchSet) {
 209             boolean hasChanged = false;
 210             PrefetchPair oldpp = null;
 211             PrefetchPair newpp = null;
 212             if(oldPrefetchSet.size() != newPrefetchSet.size()) {
 213                     return true;
 214             } else {
 215                     Enumeration e = newPrefetchSet.keys();
 216                     while(e.hasMoreElements()) {
 217                             newpp = (PrefetchPair) e.nextElement();
 218                             float newprob = newPrefetchSet.get(newpp);
 219                             for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) {
 220                                     oldpp = (PrefetchPair) elem.nextElement();
 221                                     if(oldpp.equals(newpp)) {
 222                                             /*Compare the difference in their probabilities */
 223                                             float oldprob = oldPrefetchSet.get(oldpp);
 224                                             int diff = (int) ((newprob - oldprob)/oldprob)*100;
 225                                             if(diff >= ROUNDED_MODE) {
 226                                                     return true;
 227                                             }
 228                                             break;
 229                                     } else {
 230                                             return true;
 231                                     }
 232                             }
 233                     }
 234             }
 235             return hasChanged;
 236     }
 237
 238     /** This function processes the prefetch set of FlatFieldNode
 239      * It generates a new prefetch set after comparision with its children
 240      * Then compares it with its old prefetch set
 241      * If old prefetch set is not same as new prefetch set then enqueue the parents
 242      * of the current FlatFieldNode
 243      * */
 244     void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 245             boolean pSetHasChanged = false;
 246             Hashtable<PrefetchPair, Float> currcopy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(curr).clone();
 247             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 248             FlatFieldNode currffn = (FlatFieldNode) curr;
 249             Float newprob = new Float((float)1.0);
 250
 251             //1.Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode
 252             Enumeration ecld = child_hash.keys();
 253             PrefetchPair currpp = null;
 254             PrefetchPair childpp = null;
 255             while (ecld.hasMoreElements()) {
 256                     childpp = (PrefetchPair) ecld.nextElement();
 257                     if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null || childpp.getisTempDesc()!=null)) {
 258                             if (currffn.getField().getType().isPtr()) {
 259                                     //pSetHasChanged = true;
 260                                     //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table
 261                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 262                                     ArrayList<Boolean> newbool = new ArrayList<Boolean>();
 263                                     newdesc.add(currffn.getField());
 264                                     Boolean b = new Boolean(false);
 265                                     newbool.add(b);
 266                                     newdesc.addAll(childpp.desc);
 267                                     newbool.addAll(childpp.isTempDesc);
 268                                     PrefetchPair newpp =  new PrefetchPair(currffn.getSrc(), newdesc, newbool);
 269                                     tocompare.put(newpp, newprob);
 270                                     child_hash.remove(childpp);
 271                             }
 272                     } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null ||
 273                                             childpp.getisTempDesc() == null)) {
 274                             child_hash.remove(childpp);
 275                     }
 276             }
 277             /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 278              * if so calculate the new probability and then remove the common one from the child prefetch set */
 279             ecld = child_hash.keys();
 280             Enumeration e = null;
 281             while(ecld.hasMoreElements()) {
 282                     childpp = (PrefetchPair) ecld.nextElement();
 283                     for(e = currcopy.keys(); e.hasMoreElements();) {
 284                             currpp = (PrefetchPair) e.nextElement();
 285                             if(currpp.equals(childpp)) {
 286                                     /* Calculate the new probability */
 287                                     Float cprob = child_hash.get(childpp);
 288                                     Float fprob = currcopy.get(currpp);
 289                                     // TODO fix this
 290                                     Float prob = cprob.floatValue() * fprob.floatValue();
 291                                     currcopy.put(currpp, prob);
 292                                     child_hash.remove(childpp);
 293                                     break;
 294                             }
 295                     }
 296             }
 297
 298             /* Merge child prefetch pairs */
 299             ecld = child_hash.keys();
 300             while(ecld.hasMoreElements()) {
 301                     childpp = (PrefetchPair) ecld.nextElement();
 302                     tocompare.put(childpp, child_hash.get(childpp));
 303                     child_hash.remove(childpp);
 304             }
 305
 306             /* Merge curr prefetch pairs */
 307             e = currcopy.keys();
 308             while(e.hasMoreElements()) {
 309                     currpp = (PrefetchPair) e.nextElement();
 310                     tocompare.put(currpp, currcopy.get(currpp));
 311                     currcopy.remove(currpp);
 312             }
 313
 314             /* Compare with the orginal prefetch pairs */
 315             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 316             /* Enqueue parent nodes */
 317             if(pSetHasChanged) {
 318                     for(int i=0; i<curr.numPrev(); i++) {
 319                             tovisit.add(curr.getPrev(i));
 320                     }
 321                     /* Overwrite the new prefetch set to the global hash table */
 322                     prefetch_hash.put(curr,tocompare);
 323             }
 324     }
 325
 326     /** This function processes the prefetch set of a FlatElementNode
 327      * It generates a new prefetch set after comparision with its children
 328      * It compares the old prefetch set with this new prefetch set and enqueues the parents
 329      * of the current node if change occurs and updates the global flatnode hash table
 330      * */
 331     void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_hash) {
 332             boolean pSetHasChanged = false;
 333             Hashtable<PrefetchPair, Float> currcopy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(curr).clone();
 334             Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
 335             FlatElementNode currfen = (FlatElementNode) curr;
 336             Float newprob = new Float((float)1.0);
 337
 338             /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
 339             Enumeration ecld = child_hash.keys();
 340             PrefetchPair currpp = null;
 341             PrefetchPair childpp = null;
 342             while (ecld.hasMoreElements()) {
 343                     childpp = (PrefetchPair) ecld.nextElement();
 344                     if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null || childpp.getisTempDesc()!=null)) {
 345                             if (currfen.getDst().getType().isPtr()) {
 346                                     //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table
 347                                     ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
 348                                     ArrayList<Boolean> newbool = new ArrayList<Boolean>();
 349                                     newdesc.add(currfen.getIndex());
 350                                     Boolean b = new Boolean(true);
 351                                     newbool.add(b);
 352                                     newdesc.addAll(childpp.desc);
 353                                     newbool.addAll(childpp.isTempDesc);
 354                                     PrefetchPair newpp =  new PrefetchPair(currfen.getSrc(), newdesc, newbool);
 355                                     tocompare.put(newpp, newprob);
 356                                     child_hash.remove(childpp);
 357                             }
 358                     } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null ||
 359                                             childpp.getisTempDesc() == null)) {
 360                             child_hash.remove(childpp);
 361                     }
 362             }
 363             /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
 364              * if so calculate the new probability and then remove the common one from the child prefetch set */
 365             ecld = child_hash.keys();
 366             Enumeration e = null;
 367             while(ecld.hasMoreElements()) {
 368                     childpp = (PrefetchPair) ecld.nextElement();
 369                     for(e = currcopy.keys(); e.hasMoreElements();) {
 370                             currpp = (PrefetchPair) e.nextElement();
 371                             if(currpp.equals(childpp)) {
 372                                     /* Calculate the new probability */
 373                                     Float cprob = child_hash.get(childpp);
 374                                     Float fprob = currcopy.get(currpp);
 375                                     // TODO fix this
 376                                     Float prob = cprob.floatValue() * fprob.floatValue();
 377                                     currcopy.put(currpp, prob);
 378                                     child_hash.remove(childpp);
 379                                     break;
 380                             }
 381                     }
 382             }
 383
 384             /* Merge child prefetch pairs */
 385             ecld = child_hash.keys();
 386             while(ecld.hasMoreElements()) {
 387                     childpp = (PrefetchPair) ecld.nextElement();
 388                     tocompare.put(childpp, child_hash.get(childpp));
 389                     child_hash.remove(childpp);
 390             }
 391
 392             /* Merge curr prefetch pairs */
 393             e = currcopy.keys();
 394             while(e.hasMoreElements()) {
 395                     currpp = (PrefetchPair) e.nextElement();
 396                     tocompare.put(currpp, currcopy.get(currpp));
 397                     currcopy.remove(currpp);
 398             }
 399
 400             /* Compare with the orginal prefetch pairs */
 401             pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
 402             /* Enqueue parent nodes */
 403             if(pSetHasChanged) {
 404                     for(int i=0; i<curr.numPrev(); i++) {
 405                             tovisit.add(curr.getPrev(i));
 406                     }
 407                     /* Overwrite the new prefetch set to the global hash table */
 408                     prefetch_hash.put(curr,tocompare);
 409             }
 410     }
 411
 412
 413     /** This function prints the Prefetch pairs of a given flatnode */
 414     void printPrefetchPairs(FlatNode fn) {
 415             if(prefetch_hash.containsKey(fn)) {
 416                     System.out.print("Prefetch" + "(");
 417                     Hashtable<PrefetchPair, Float> currhash = (Hashtable) prefetch_hash.get(fn);
 418                     for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
 419                             PrefetchPair pp = (PrefetchPair) pphash.nextElement();
 420                             System.out.print(pp.toString() + ", ");
 421                     }
 422                     System.out.println(")");
 423             }
 424     }
 425
 426     private void doAnalysis() {
 427         Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
 428         while(classit.hasNext()) {
 429             ClassDescriptor cn=(ClassDescriptor)classit.next();
 430             Iterator methodit=cn.getMethods();
 431             while(methodit.hasNext()) {
 432                 /* Classify parameters */
 433                 MethodDescriptor md=(MethodDescriptor)methodit.next();
 434                 FlatMethod fm=state.getMethodFlat(md);
 435                 printMethod(fm);
 436             }
 437         }
 438     }
 439
 440     private void printMethod(FlatMethod fm) {
 441         System.out.println(fm.getMethod()+" {");
 442         HashSet tovisit=new HashSet();
 443         HashSet visited=new HashSet();
 444         int labelindex=0;
 445         Hashtable nodetolabel=new Hashtable();
 446         tovisit.add(fm);
 447         FlatNode current_node=null;
 448         //Assign labels 1st
 449         //Node needs a label if it is
 450         while(!tovisit.isEmpty()) {
 451             FlatNode fn=(FlatNode)tovisit.iterator().next();
 452             tovisit.remove(fn);
 453             visited.add(fn);
 454
 455             for(int i=0;i<fn.numNext();i++) {
 456                 FlatNode nn=fn.getNext(i);
 457                 if(i>0) {
 458                     //1) Edge >1 of node
 459                     nodetolabel.put(nn,new Integer(labelindex++));
 460                 }
 461                 if (!visited.contains(nn)&&!tovisit.contains(nn)) {
 462                     tovisit.add(nn);
 463                 } else {
 464                     //2) Join point
 465                     nodetolabel.put(nn,new Integer(labelindex++));
 466                 }
 467             }
 468         }
 469         //Do the actual printing
 470         tovisit=new HashSet();
 471         visited=new HashSet();
 472         tovisit.add(fm);
 473         while(current_node!=null||!tovisit.isEmpty()) {
 474             if (current_node==null) {
 475                 current_node=(FlatNode)tovisit.iterator().next();
 476                 tovisit.remove(current_node);
 477             }
 478             visited.add(current_node);
 479             if (nodetolabel.containsKey(current_node))
 480                 System.out.println("L"+nodetolabel.get(current_node)+":");
 481             if (current_node.numNext()==0) {
 482                 System.out.println("   "+current_node.toString());
 483                 current_node=null;
 484             } else if(current_node.numNext()==1) {
 485                 System.out.println("   "+current_node.toString());
 486                 FlatNode nextnode=current_node.getNext(0);
 487                 if (visited.contains(nextnode)) {
 488                     System.out.println("goto L"+nodetolabel.get(nextnode));
 489                     current_node=null;
 490                 } else
 491                     current_node=nextnode;
 492             } else if (current_node.numNext()==2) {
 493                 /* Branch */
 494                 System.out.println("   "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1))));
 495                 if (!visited.contains(current_node.getNext(1)))
 496                     tovisit.add(current_node.getNext(1));
 497                 if (visited.contains(current_node.getNext(0))) {
 498                     System.out.println("goto L"+nodetolabel.get(current_node.getNext(0)));
 499                     current_node=null;
 500                 } else
 501                     current_node=current_node.getNext(0);
 502             } else throw new Error();
 503         }
 504         System.out.println("}");
 505     }
 506
 507 }