Robust/src/Analysis/Prefetch/PrefetchAnalysis.java

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