Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java

   1 package Analysis.OoOJava;
   2
   3 import IR.State;
   4 import IR.TypeUtil;
   5 import IR.MethodDescriptor;
   6 import IR.TypeDescriptor;
   7 import IR.Flat.*;
   8 import Analysis.CallGraph.CallGraph;
   9 import java.util.*;
  10
  11
  12 // This analysis finds all reachable rblocks in the
  13 // program and computes parent/child relations
  14 // between those rblocks
  15
  16 // SPECIAL NOTE!
  17 // There is a distict between parent/child and
  18 // local parent/local child!  "Local" means defined
  19 // and nested within a single method context.
  20 // Otherwise, SESE/rblocks/tasks may have many
  21 // parents and many non-method-context-local
  22 // children considering the call graph
  23
  24 // Also this analysis should identify "critical regions"
  25 // in the context of interprocedural sese/rblock/task relations
  26 // where a statement may conflict with some previously executing
  27 // child task, even if it is in another method context.
  28 //
  29 // Ex:
  30 //
  31 // void main() {
  32 //   task a {
  33 //     Foo f = new Foo();
  34 //     task achild1 {
  35 //       f.z = 1;
  36 //     }
  37 //     doSomething( f );
  38 //   }
  39 // }
  40 //
  41 // void doSomething( Foo f ) {
  42 //   f.z++;     <-------- These two statements are in the critical
  43 //   f.z--;     <-------- region of 'a' after 'c1' and before 'c2'
  44 //   task achild2 {
  45 //     f.z--;
  46 //   }
  47 // }
  48
  49
  50 public class RBlockRelationAnalysis {
  51
  52   // compiler data
  53   State     state;
  54   TypeUtil  typeUtil;
  55   CallGraph callGraph;
  56
  57   // an implicit SESE is automatically spliced into
  58   // the IR graph around the C main before this analysis--it
  59   // is nothing special except that we can make assumptions
  60   // about it, such as the whole program ends when it ends
  61   protected FlatSESEEnterNode mainSESE;
  62
  63   // this is a special task object, it is not in any IR graph
  64   // and it does not appear to have any children or parents.
  65   // It is a stand-in for whichever task is running when a
  66   // method context starts such that intraprocedural task
  67   // analyses have one static name for "the task who invoked
  68   // this method" to attach facts to.  It GREATLY simplifies
  69   // the OoOJava variable analysis, for instance
  70   protected FlatSESEEnterNode callerProxySESE;
  71
  72   // simply the set of every reachable SESE in the program
  73   protected Set<FlatSESEEnterNode> allSESEs;
  74
  75   // to support calculation of leaf SESEs (no children even
  76   // through method calls) for optimization during code gen
  77   protected Set<MethodDescriptor> methodsContainingSESEs;
  78
  79   // maps method descriptor to SESE defined inside of it
  80   // only contains local root SESE definitions in corresponding method
  81   // (has no parent in the local method context)
  82   protected Hashtable< MethodDescriptor, Set<FlatSESEEnterNode> > md2localRootSESEs;
  83
  84   // the set of every local root SESE in the program (SESE that
  85   // has no parent in the local method context)
  86   protected Set<FlatSESEEnterNode> allLocalRootSESEs;
  87
  88   // if you want to know which rblocks might be executing a given flat
  89   // node it will be in this set
  90   protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2currentSESEs;
  91
  92   // if you want to know which rblocks might be TRANSITIVELY executing
  93   // a given flat node it will be in this set
  94   protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2allSESEs;
  95
  96   // if you want to know the method-local, inner-most nested task that
  97   // is executing a flat node, it is either here or null.
  98   //
  99   // ex:
 100   // void foo() {
 101   //   task a {
 102   //     bar();  <-- here 'a' is the localInnerSESE
 103   //   }
 104   // void bar() {
 105   //   baz();  <-- here there is no locally-defined SESE, would be null
 106   // }
 107   protected Hashtable<FlatNode, FlatSESEEnterNode> fn2localInnerSESE;
 108
 109   // indicates whether this statement might occur in a task and
 110   // after some child task definition such that, without looking at
 111   // the flat node itself, the parent might have to stall for child
 112   protected Hashtable<FlatNode, Boolean> fn2isPotentialStallSite;
 113
 114
 115   ////////////////////////
 116   // public interface
 117   ////////////////////////
 118   public FlatSESEEnterNode getMainSESE() {
 119     return mainSESE;
 120   }
 121
 122   public Set<FlatSESEEnterNode> getAllSESEs() {
 123     return allSESEs;
 124   }
 125
 126   public Set<FlatSESEEnterNode> getLocalRootSESEs() {
 127     return allLocalRootSESEs;
 128   }
 129
 130   public Set<FlatSESEEnterNode> getLocalRootSESEs( FlatMethod fm ) {
 131     Set<FlatSESEEnterNode> out = md2localRootSESEs.get( fm );
 132     if( out == null ) {
 133       out = new HashSet<FlatSESEEnterNode>();
 134     }
 135     return out;
 136   }
 137
 138   public Set<MethodDescriptor> getMethodsWithSESEs() {
 139     return methodsContainingSESEs;
 140   }
 141
 142   /* Returns all SESE's that this fn can be a member of
 143    * transitively. */
 144
 145   public Set<FlatSESEEnterNode> getTransitiveExecutingRBlocks(FlatNode fn) {
 146     if (fn2allSESEs.containsKey(fn))
 147       return fn2allSESEs.get(fn);
 148
 149     //Compute and memoize result
 150     HashSet<FlatSESEEnterNode> seseSet=new HashSet<FlatSESEEnterNode>();
 151     fn2allSESEs.put(fn, seseSet);
 152     Stack<FlatNode> toprocess=new Stack<FlatNode>();
 153     toprocess.add(fn);
 154     while(!toprocess.isEmpty()) {
 155       FlatNode curr=toprocess.pop();
 156       Set<FlatSESEEnterNode> callers=fn2currentSESEs.get(curr);
 157       if (callers!=null) {
 158         for(FlatSESEEnterNode sese:callers) {
 159           if (!seseSet.contains(sese)) {
 160             seseSet.add(sese);
 161             toprocess.add(fn);
 162           }
 163         }
 164       }
 165     }
 166     return seseSet;
 167   }
 168
 169   public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
 170     Set<FlatSESEEnterNode> out = fn2currentSESEs.get( fn );
 171     if( out == null ) {
 172       out = new HashSet<FlatSESEEnterNode>();
 173     }
 174     return out;
 175   }
 176
 177   public FlatSESEEnterNode getLocalInnerRBlock( FlatNode fn ) {
 178     return fn2localInnerSESE.get( fn );
 179   }
 180
 181   // the "caller proxy" is a static name for whichever
 182   // task invoked the current method context.  It is very
 183   // convenient to know this is ALWAYS a different instance
 184   // of any task defined within the current method context,
 185   // and so using its name simplifies many intraprocedural
 186   // analyses
 187   public FlatSESEEnterNode getCallerProxySESE() {
 188     return callerProxySESE;
 189   }
 190
 191   public boolean isPotentialStallSite( FlatNode fn ) {
 192     Boolean ipss = fn2isPotentialStallSite.get( fn );
 193     if( ipss == null ) {
 194       return false;
 195     }
 196     return ipss;
 197   }
 198
 199
 200   public RBlockRelationAnalysis( State     state,
 201                                  TypeUtil  typeUtil,
 202                                  CallGraph callGraph ) {
 203     this.state     = state;
 204     this.typeUtil  = typeUtil;
 205     this.callGraph = callGraph;
 206
 207     callerProxySESE = new FlatSESEEnterNode( null );
 208     callerProxySESE.setIsCallerProxySESE();
 209
 210     allSESEs                = new HashSet<FlatSESEEnterNode>();
 211     allLocalRootSESEs       = new HashSet<FlatSESEEnterNode>();
 212     methodsContainingSESEs  = new HashSet<MethodDescriptor>();
 213     md2localRootSESEs       = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
 214     fn2currentSESEs         = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
 215     fn2localInnerSESE       = new Hashtable<FlatNode, FlatSESEEnterNode>();
 216     fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
 217     fn2allSESEs             = new Hashtable< FlatNode, Set<FlatSESEEnterNode>>();
 218
 219
 220     MethodDescriptor mdSourceEntry = typeUtil.getMain();
 221     FlatMethod       fmMain        = state.getMethodFlat( mdSourceEntry );
 222
 223     mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
 224     mainSESE.setfmEnclosing( fmMain );
 225     mainSESE.setmdEnclosing( fmMain.getMethod() );
 226     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
 227
 228
 229     // add all methods transitively reachable from the
 230     // source's main to set to find rblocks
 231     Set<MethodDescriptor> descriptorsToAnalyze =
 232       callGraph.getAllMethods( mdSourceEntry );
 233
 234     descriptorsToAnalyze.add( mdSourceEntry );
 235
 236     findRblocksAndLocalParentChildRelations( descriptorsToAnalyze );
 237
 238     findTransitiveParentChildRelations();
 239
 240     findPossibleExecutingRBlocksAndStallSites();
 241
 242
 243     // Uncomment this phase to debug the marking of potential
 244     // stall sites for parents between/after children tasks.
 245     // After this debug thing runs in calls System.exit()
 246     //debugPrintPotentialStallSites( descriptorsToAnalyze );
 247   }
 248
 249
 250
 251
 252   protected void findRblocksAndLocalParentChildRelations( Set<MethodDescriptor> descriptorsToAnalyze ) {
 253
 254     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 255     while( mdItr.hasNext() ) {
 256       FlatMethod fm = state.getMethodFlat( mdItr.next() );
 257
 258       // start from flat method top, visit every node in
 259       // method exactly once, find SESE stack on every
 260       // control path: this will discover every reachable
 261       // SESE in the program, and define the local parent
 262       // and local children relations
 263       Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
 264         new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 265
 266       Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 267       flatNodesToVisit.add( fm );
 268
 269       Set<FlatNode> visited = new HashSet<FlatNode>();
 270
 271       Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 272       seseStacks.put( fm, seseStackFirst );
 273
 274       while( !flatNodesToVisit.isEmpty() ) {
 275         Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 276         FlatNode fn = fnItr.next();
 277
 278         Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 279         assert seseStack != null;
 280
 281         flatNodesToVisit.remove( fn );
 282         visited.add( fn );
 283
 284         if( !seseStack.isEmpty() ) {
 285           fn2localInnerSESE.put( fn, seseStack.peek() );
 286         }
 287
 288         nodeActions( fn, seseStack, fm );
 289
 290         for( int i = 0; i < fn.numNext(); i++ ) {
 291           FlatNode nn = fn.getNext( i );
 292
 293           if( !visited.contains( nn ) ) {
 294             flatNodesToVisit.add( nn );
 295
 296             // clone stack and send along each control path
 297             seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 298           }
 299         }
 300       }
 301     }
 302   }
 303
 304   protected void nodeActions( FlatNode fn,
 305                               Stack<FlatSESEEnterNode> seseStack,
 306                               FlatMethod fm ) {
 307     switch( fn.kind() ) {
 308
 309     case FKind.FlatSESEEnterNode: {
 310       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 311
 312       allSESEs.add( fsen );
 313       methodsContainingSESEs.add( fm.getMethod() );
 314
 315       fsen.setfmEnclosing( fm );
 316       fsen.setmdEnclosing( fm.getMethod() );
 317       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 318
 319       if( seseStack.empty() ) {
 320         // no local parent
 321         fsen.setLocalParent( null );
 322
 323         allLocalRootSESEs.add( fsen );
 324
 325         Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( fm.getMethod() );
 326         if( seseSet == null ) {
 327           seseSet = new HashSet<FlatSESEEnterNode>();
 328         }
 329         seseSet.add( fsen );
 330         md2localRootSESEs.put( fm.getMethod(), seseSet );
 331
 332       } else {
 333         // otherwise a local parent/child relation
 334         // which is also the broader parent/child
 335         // relation as well
 336         seseStack.peek().addLocalChild( fsen );
 337         fsen.setLocalParent( seseStack.peek() );
 338
 339         seseStack.peek().addChild( fsen );
 340         fsen.addParent( seseStack.peek() );
 341       }
 342
 343       seseStack.push( fsen );
 344     } break;
 345
 346     case FKind.FlatSESEExitNode: {
 347       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 348       assert !seseStack.empty();
 349       FlatSESEEnterNode fsen = seseStack.pop();
 350     } break;
 351
 352     case FKind.FlatReturnNode: {
 353       FlatReturnNode frn = (FlatReturnNode) fn;
 354       if( !seseStack.empty() ) {
 355         throw new Error( "Error: return statement enclosed within SESE "+
 356                          seseStack.peek().getPrettyIdentifier() );
 357       }
 358     } break;
 359
 360     }
 361   }
 362
 363
 364
 365   protected void findTransitiveParentChildRelations() {
 366
 367     for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext();) {
 368       FlatSESEEnterNode fsen = itr.next();
 369
 370       boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
 371       boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
 372
 373       fsen.setIsLeafSESE( hasNoNestedChildren && hasNoChildrenByCall );
 374     }
 375   }
 376
 377   protected boolean hasChildrenByCall( FlatSESEEnterNode fsen ) {
 378
 379     boolean hasChildrenByCall = false;
 380
 381     // visit every flat node in SESE body, find method calls that
 382     // may transitively call methods with SESEs enclosed
 383     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 384     flatNodesToVisit.add( fsen );
 385
 386     Set<FlatNode> visited = new HashSet<FlatNode>();
 387
 388     while( !flatNodesToVisit.isEmpty() ) {
 389       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 390       FlatNode fn = fnItr.next();
 391
 392       flatNodesToVisit.remove( fn );
 393       visited.add( fn );
 394
 395       if( fn.kind() == FKind.FlatCall ) {
 396         FlatCall         fc        = (FlatCall) fn;
 397         MethodDescriptor mdCallee  = fc.getMethod();
 398         Set              reachable = new HashSet();
 399
 400         reachable.add( mdCallee );
 401         reachable.addAll( callGraph.getAllMethods( mdCallee ) );
 402         reachable.retainAll( methodsContainingSESEs );
 403
 404         if( !reachable.isEmpty() ) {
 405           hasChildrenByCall = true;
 406
 407           Set reachableSESEMethodSet =
 408             callGraph.getFirstReachableMethodContainingSESE( mdCallee, methodsContainingSESEs );
 409
 410           reachableSESEMethodSet.add( mdCallee );
 411           reachableSESEMethodSet.retainAll( methodsContainingSESEs );
 412
 413           for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
 414             MethodDescriptor md = (MethodDescriptor) iterator.next();
 415             Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( md );
 416             if( seseSet != null ) {
 417               fsen.addChildren( seseSet );
 418               for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
 419                 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
 420                 child.addParent( fsen );
 421               }
 422             }
 423           }
 424         }
 425       }
 426
 427       if( fn == fsen.getFlatExit() ) {
 428         // don't enqueue any futher nodes
 429         continue;
 430       }
 431
 432       for( int i = 0; i < fn.numNext(); i++ ) {
 433         FlatNode nn = fn.getNext( i );
 434
 435         if( !visited.contains( nn ) ) {
 436           flatNodesToVisit.add( nn );
 437         }
 438       }
 439     }
 440
 441     return hasChildrenByCall;
 442   }
 443
 444   protected void findPossibleExecutingRBlocksAndStallSites() {
 445     for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
 446       FlatSESEEnterNode fsen = fsenItr.next();
 447
 448       // walk the program points, including across method calls, reachable within
 449       // this sese/rblock/task and mark that this rblock might be executing.
 450       // Important: skip the body of child rblocks, BUT DO mark the child ENTER
 451       // and EXIT flat nodes as the parent being the current executing rblock!
 452       Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
 453         new Hashtable<FlatNode, FlatMethod>();
 454
 455       for( int i = 0; i < fsen.numNext(); i++ ) {
 456         FlatNode nn = fsen.getNext( i );
 457         flatNodesToVisit.put( nn, fsen.getfmEnclosing() );
 458         mergeIsPotentialStallSite( nn, false );
 459       }
 460
 461       Set<FlatNode> visited = new HashSet<FlatNode>();
 462
 463       while( !flatNodesToVisit.isEmpty() ) {
 464         Map.Entry  me = (Map.Entry)  flatNodesToVisit.entrySet().iterator().next();
 465         FlatNode   fn = (FlatNode)   me.getKey();
 466         FlatMethod fm = (FlatMethod) me.getValue();
 467
 468         flatNodesToVisit.remove( fn );
 469         visited.add( fn );
 470
 471
 472         // the "is potential stall site" strategy is to propagate
 473         // "false" from the beginning of a task until you hit a
 474         // child, then from the child's exit propagate "true" for
 475         // the parent statements after children.  When you pull a node
 476         // out of the bag for traversal and it happens to be an
 477         // enter or an exit node, fix the dumb propagation that
 478         // your IR predecessor pushed on you
 479         Boolean isPotentialStallSite = isPotentialStallSite( fn );
 480
 481         if( fn instanceof FlatSESEEnterNode ||
 482             fn instanceof FlatSESEExitNode ) {
 483           // fix it so this is never a potential stall site, but from
 484           // a child definition onward propagate 'true'
 485           setIsPotentialStallSite( fn, false );
 486           isPotentialStallSite = true;
 487         }
 488
 489
 490         if( fn == fsen.getFlatExit() ) {
 491           // don't enqueue any futher nodes when you find your exit,
 492           // NOR mark your own flat as a statement you are currently
 493           // executing, your parent(s) will mark it
 494           continue;
 495         }
 496
 497
 498         // the purpose of this traversal is to find program
 499         // points where rblock 'fsen' might be executing
 500         addPossibleExecutingRBlock( fn, fsen );
 501
 502
 503         if( fn instanceof FlatSESEEnterNode ) {
 504           // don't visit internal nodes of child,
 505           // just enqueue the exit node
 506           FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
 507           assert fsen.getChildren().contains( child );
 508           assert child.getParents().contains( fsen );
 509           flatNodesToVisit.put( child.getFlatExit(), fm );
 510
 511           // explicitly do this to handle the case that you
 512           // should mark yourself as possibly executing at
 513           // your own exit, because one instance can
 514           // recursively invoke another
 515           addPossibleExecutingRBlock( child.getFlatExit(), fsen );
 516
 517           continue;
 518         }
 519
 520         if( fn instanceof FlatCall ) {
 521           // start visiting nodes in other contexts
 522           FlatCall         fc       = (FlatCall) fn;
 523           MethodDescriptor mdCallee = fc.getMethod();
 524
 525           Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
 526
 527           if( mdCallee.isStatic() ) {
 528             implementations.add( mdCallee );
 529           } else {
 530             TypeDescriptor typeDesc = fc.getThis().getType();
 531             implementations.addAll( callGraph.getMethods( mdCallee, typeDesc ) );
 532           }
 533
 534           for( Iterator imps = implementations.iterator(); imps.hasNext(); ) {
 535             MethodDescriptor mdImp = (MethodDescriptor) imps.next();
 536             FlatMethod       fmImp = state.getMethodFlat( mdImp );
 537             flatNodesToVisit.put( fmImp, fmImp );
 538
 539             // propagate your IR graph predecessor's stall site potential
 540             mergeIsPotentialStallSite( fmImp, isPotentialStallSite );
 541           }
 542           // don't 'continue' out of this loop, also enqueue
 543           // flat nodes that flow in the current method context
 544         }
 545
 546         // otherwise keep visiting nodes in same context
 547         for( int i = 0; i < fn.numNext(); i++ ) {
 548           FlatNode nn = fn.getNext( i );
 549
 550           if( !visited.contains( nn ) ) {
 551             flatNodesToVisit.put( nn, fm );
 552
 553             // propagate your IR graph predecessor's stall site potential
 554             mergeIsPotentialStallSite( nn, isPotentialStallSite );
 555           }
 556         }
 557       }
 558     }
 559   }
 560
 561
 562
 563   protected void addPossibleExecutingRBlock( FlatNode          fn,
 564                                              FlatSESEEnterNode fsen ) {
 565
 566     Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get( fn );
 567     if( currentSESEs == null ) {
 568       currentSESEs = new HashSet<FlatSESEEnterNode>();
 569     }
 570
 571     currentSESEs.add( fsen );
 572     fn2currentSESEs.put( fn, currentSESEs );
 573   }
 574
 575
 576   // definitively set whether a statement is a potential stall site
 577   // such as a task exit is FALSE and the statement following an exit
 578   // is TRUE
 579   protected void setIsPotentialStallSite( FlatNode   fn,
 580                                           Boolean    ipss ) {
 581     fn2isPotentialStallSite.put( fn, ipss );
 582   }
 583
 584
 585   // Use this to OR the previous result with a new result
 586   protected void mergeIsPotentialStallSite( FlatNode   fn,
 587                                             Boolean    ipss ) {
 588     Boolean ipssPrev = isPotentialStallSite( fn );
 589     setIsPotentialStallSite( fn, ipssPrev || ipss );
 590   }
 591
 592
 593
 594
 595
 596   /////////////////////////////////////////////////
 597   // for DEBUG
 598   /////////////////////////////////////////////////
 599   protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
 600     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 601     while (mdItr.hasNext()) {
 602       FlatMethod fm = state.getMethodFlat(mdItr.next());
 603       printStatusMap(fm);
 604     }
 605     System.exit( 0 );
 606   }
 607
 608   protected void printStatusMap(FlatMethod fm) {
 609
 610     System.out.println("\n\n=== "+fm+" ===");
 611
 612     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 613     flatNodesToVisit.add(fm);
 614
 615     Set<FlatNode> visited = new HashSet<FlatNode>();
 616
 617     while (!flatNodesToVisit.isEmpty()) {
 618       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 619       FlatNode fn = fnItr.next();
 620
 621       flatNodesToVisit.remove(fn);
 622       visited.add(fn);
 623
 624       System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
 625
 626       for (int i = 0; i < fn.numNext(); i++) {
 627         FlatNode nn = fn.getNext(i);
 628
 629         if (!visited.contains(nn)) {
 630           flatNodesToVisit.add(nn);
 631         }
 632       }
 633     }
 634   }
 635
 636 }