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