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 executing a given flat
  93   // 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   /* Returns all SESE's that this fn can be a member of
 139    * transitively. */
 140
 141   public Set<FlatSESEEnterNode> getTransitiveExecutingRBlocks(FlatNode fn) {
 142     if (fn2allSESEs.containsKey(fn))
 143       return fn2allSESEs.get(fn);
 144
 145     //Compute and memoize result
 146     HashSet<FlatSESEEnterNode> seseSet=new HashSet<FlatSESEEnterNode>();
 147     fn2allSESEs.put(fn, seseSet);
 148     Stack<FlatNode> toprocess=new Stack<FlatNode>();
 149     toprocess.add(fn);
 150     while(!toprocess.isEmpty()) {
 151       FlatNode curr=toprocess.pop();
 152       Set<FlatSESEEnterNode> callers=fn2currentSESEs.get(curr);
 153       if (callers!=null) {
 154         for(FlatSESEEnterNode sese:callers) {
 155           if (!seseSet.contains(sese)) {
 156             seseSet.add(sese);
 157             toprocess.add(fn);
 158           }
 159         }
 160       }
 161     }
 162     return seseSet;
 163   }
 164
 165   public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
 166     Set<FlatSESEEnterNode> out = fn2currentSESEs.get( fn );
 167     if( out == null ) {
 168       out = new HashSet<FlatSESEEnterNode>();
 169     }
 170     return out;
 171   }
 172
 173   public FlatSESEEnterNode getLocalInnerRBlock( FlatNode fn ) {
 174     return fn2localInnerSESE.get( fn );
 175   }
 176
 177   // the "caller proxy" is a static name for whichever
 178   // task invoked the current method context.  It is very
 179   // convenient to know this is ALWAYS a different instance
 180   // of any task defined within the current method context,
 181   // and so using its name simplifies many intraprocedural
 182   // analyses
 183   public FlatSESEEnterNode getCallerProxySESE() {
 184     return callerProxySESE;
 185   }
 186
 187   public boolean isPotentialStallSite( FlatNode fn ) {
 188     Boolean ipss = fn2isPotentialStallSite.get( fn );
 189     if( ipss == null ) {
 190       return false;
 191     }
 192     return ipss;
 193   }
 194
 195
 196   public RBlockRelationAnalysis( State     state,
 197                                  TypeUtil  typeUtil,
 198                                  CallGraph callGraph ) {
 199     this.state     = state;
 200     this.typeUtil  = typeUtil;
 201     this.callGraph = callGraph;
 202
 203     callerProxySESE = new FlatSESEEnterNode( null );
 204     callerProxySESE.setIsCallerProxySESE();
 205
 206     allSESEs                = new HashSet<FlatSESEEnterNode>();
 207     allLocalRootSESEs       = new HashSet<FlatSESEEnterNode>();
 208     methodsContainingSESEs  = new HashSet<MethodDescriptor>();
 209     md2localRootSESEs       = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
 210     fn2currentSESEs         = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
 211     fn2localInnerSESE       = new Hashtable<FlatNode, FlatSESEEnterNode>();
 212     fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
 213     fn2allSESEs             = new Hashtable< FlatNode, Set<FlatSESEEnterNode>>();
 214
 215
 216     MethodDescriptor mdSourceEntry = typeUtil.getMain();
 217     FlatMethod       fmMain        = state.getMethodFlat( mdSourceEntry );
 218
 219     mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
 220     mainSESE.setfmEnclosing( fmMain );
 221     mainSESE.setmdEnclosing( fmMain.getMethod() );
 222     mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
 223
 224
 225     // add all methods transitively reachable from the
 226     // source's main to set to find rblocks
 227     Set<MethodDescriptor> descriptorsToAnalyze =
 228       callGraph.getAllMethods( mdSourceEntry );
 229
 230     descriptorsToAnalyze.add( mdSourceEntry );
 231
 232     findRblocksAndLocalParentChildRelations( descriptorsToAnalyze );
 233
 234     findTransitiveParentChildRelations();
 235
 236     findPossibleExecutingRBlocksAndStallSites();
 237
 238
 239     // Uncomment this phase to debug the marking of potential
 240     // stall sites for parents between/after children tasks.
 241     // After this debug thing runs in calls System.exit()
 242     //debugPrintPotentialStallSites( descriptorsToAnalyze );
 243   }
 244
 245
 246
 247
 248   protected void findRblocksAndLocalParentChildRelations( Set<MethodDescriptor> descriptorsToAnalyze ) {
 249
 250     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 251     while( mdItr.hasNext() ) {
 252       FlatMethod fm = state.getMethodFlat( mdItr.next() );
 253
 254       // start from flat method top, visit every node in
 255       // method exactly once, find SESE stack on every
 256       // control path: this will discover every reachable
 257       // SESE in the program, and define the local parent
 258       // and local children relations
 259       Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
 260         new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
 261
 262       Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 263       flatNodesToVisit.add( fm );
 264
 265       Set<FlatNode> visited = new HashSet<FlatNode>();
 266
 267       Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
 268       seseStacks.put( fm, seseStackFirst );
 269
 270       while( !flatNodesToVisit.isEmpty() ) {
 271         Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 272         FlatNode fn = fnItr.next();
 273
 274         Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
 275         assert seseStack != null;
 276
 277         flatNodesToVisit.remove( fn );
 278         visited.add( fn );
 279
 280         if( !seseStack.isEmpty() ) {
 281           fn2localInnerSESE.put( fn, seseStack.peek() );
 282         }
 283
 284         nodeActions( fn, seseStack, fm );
 285
 286         for( int i = 0; i < fn.numNext(); i++ ) {
 287           FlatNode nn = fn.getNext( i );
 288
 289           if( !visited.contains( nn ) ) {
 290             flatNodesToVisit.add( nn );
 291
 292             // clone stack and send along each control path
 293             seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
 294           }
 295         }
 296       }
 297     }
 298   }
 299
 300   protected void nodeActions( FlatNode fn,
 301                               Stack<FlatSESEEnterNode> seseStack,
 302                               FlatMethod fm ) {
 303     switch( fn.kind() ) {
 304
 305     case FKind.FlatSESEEnterNode: {
 306       FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
 307
 308       allSESEs.add( fsen );
 309       methodsContainingSESEs.add( fm.getMethod() );
 310
 311       fsen.setfmEnclosing( fm );
 312       fsen.setmdEnclosing( fm.getMethod() );
 313       fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
 314
 315       if( seseStack.empty() ) {
 316         // no local parent
 317         fsen.setLocalParent( null );
 318
 319         allLocalRootSESEs.add( fsen );
 320
 321         Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( fm.getMethod() );
 322         if( seseSet == null ) {
 323           seseSet = new HashSet<FlatSESEEnterNode>();
 324         }
 325         seseSet.add( fsen );
 326         md2localRootSESEs.put( fm.getMethod(), seseSet );
 327
 328       } else {
 329         // otherwise a local parent/child relation
 330         // which is also the broader parent/child
 331         // relation as well
 332         seseStack.peek().addLocalChild( fsen );
 333         fsen.setLocalParent( seseStack.peek() );
 334
 335         seseStack.peek().addChild( fsen );
 336         fsen.addParent( seseStack.peek() );
 337       }
 338
 339       seseStack.push( fsen );
 340     } break;
 341
 342     case FKind.FlatSESEExitNode: {
 343       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
 344       assert !seseStack.empty();
 345       FlatSESEEnterNode fsen = seseStack.pop();
 346     } break;
 347
 348     case FKind.FlatReturnNode: {
 349       FlatReturnNode frn = (FlatReturnNode) fn;
 350       if( !seseStack.empty() ) {
 351         throw new Error( "Error: return statement enclosed within SESE "+
 352                          seseStack.peek().getPrettyIdentifier() );
 353       }
 354     } break;
 355
 356     }
 357   }
 358
 359
 360
 361   protected void findTransitiveParentChildRelations() {
 362
 363     for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext();) {
 364       FlatSESEEnterNode fsen = itr.next();
 365
 366       boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
 367       boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
 368
 369       fsen.setIsLeafSESE( hasNoNestedChildren && hasNoChildrenByCall );
 370     }
 371   }
 372
 373   protected boolean hasChildrenByCall( FlatSESEEnterNode fsen ) {
 374
 375     boolean hasChildrenByCall = false;
 376
 377     // visit every flat node in SESE body, find method calls that
 378     // may transitively call methods with SESEs enclosed
 379     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 380     flatNodesToVisit.add( fsen );
 381
 382     Set<FlatNode> visited = new HashSet<FlatNode>();
 383
 384     while( !flatNodesToVisit.isEmpty() ) {
 385       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 386       FlatNode fn = fnItr.next();
 387
 388       flatNodesToVisit.remove( fn );
 389       visited.add( fn );
 390
 391       if( fn.kind() == FKind.FlatCall ) {
 392         FlatCall         fc        = (FlatCall) fn;
 393         MethodDescriptor mdCallee  = fc.getMethod();
 394         Set              reachable = new HashSet();
 395
 396         reachable.add( mdCallee );
 397         reachable.addAll( callGraph.getAllMethods( mdCallee ) );
 398         reachable.retainAll( methodsContainingSESEs );
 399
 400         if( !reachable.isEmpty() ) {
 401           hasChildrenByCall = true;
 402
 403           Set reachableSESEMethodSet =
 404             callGraph.getFirstReachableMethodContainingSESE( mdCallee, methodsContainingSESEs );
 405
 406           reachableSESEMethodSet.add( mdCallee );
 407           reachableSESEMethodSet.retainAll( methodsContainingSESEs );
 408
 409           for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
 410             MethodDescriptor md = (MethodDescriptor) iterator.next();
 411             Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( md );
 412             if( seseSet != null ) {
 413               fsen.addChildren( seseSet );
 414               for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
 415                 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
 416                 child.addParent( fsen );
 417               }
 418             }
 419           }
 420         }
 421       }
 422
 423       if( fn == fsen.getFlatExit() ) {
 424         // don't enqueue any futher nodes
 425         continue;
 426       }
 427
 428       for( int i = 0; i < fn.numNext(); i++ ) {
 429         FlatNode nn = fn.getNext( i );
 430
 431         if( !visited.contains( nn ) ) {
 432           flatNodesToVisit.add( nn );
 433         }
 434       }
 435     }
 436
 437     return hasChildrenByCall;
 438   }
 439
 440   protected void findPossibleExecutingRBlocksAndStallSites() {
 441     for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
 442       FlatSESEEnterNode fsen = fsenItr.next();
 443
 444       // walk the program points, including across method calls, reachable within
 445       // this sese/rblock/task and mark that this rblock might be executing.
 446       // Important: skip the body of child rblocks, BUT DO mark the child ENTER
 447       // and EXIT flat nodes as the parent being the current executing rblock!
 448       Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
 449         new Hashtable<FlatNode, FlatMethod>();
 450
 451       for( int i = 0; i < fsen.numNext(); i++ ) {
 452         FlatNode nn = fsen.getNext( i );
 453         flatNodesToVisit.put( nn, fsen.getfmEnclosing() );
 454         mergeIsPotentialStallSite( nn, false );
 455       }
 456
 457       Set<FlatNode> visited = new HashSet<FlatNode>();
 458
 459       while( !flatNodesToVisit.isEmpty() ) {
 460         Map.Entry  me = (Map.Entry)  flatNodesToVisit.entrySet().iterator().next();
 461         FlatNode   fn = (FlatNode)   me.getKey();
 462         FlatMethod fm = (FlatMethod) me.getValue();
 463
 464         flatNodesToVisit.remove( fn );
 465         visited.add( fn );
 466
 467
 468         // the "is potential stall site" strategy is to propagate
 469         // "false" from the beginning of a task until you hit a
 470         // child, then from the child's exit propagate "true" for
 471         // the parent statements after children.  When you pull a node
 472         // out of the bag for traversal and it happens to be an
 473         // enter or an exit node, fix the dumb propagation that
 474         // your IR predecessor pushed on you
 475         Boolean isPotentialStallSite = isPotentialStallSite( fn );
 476
 477         if( fn instanceof FlatSESEEnterNode ||
 478             fn instanceof FlatSESEExitNode ) {
 479           // fix it so this is never a potential stall site, but from
 480           // a child definition onward propagate 'true'
 481           setIsPotentialStallSite( fn, false );
 482           isPotentialStallSite = true;
 483         }
 484
 485
 486         if( fn == fsen.getFlatExit() ) {
 487           // don't enqueue any futher nodes when you find your exit,
 488           // NOR mark your own flat as a statement you are currently
 489           // executing, your parent(s) will mark it
 490           continue;
 491         }
 492
 493
 494         // the purpose of this traversal is to find program
 495         // points where rblock 'fsen' might be executing
 496         addPossibleExecutingRBlock( fn, fsen );
 497
 498
 499         if( fn instanceof FlatSESEEnterNode ) {
 500           // don't visit internal nodes of child,
 501           // just enqueue the exit node
 502           FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
 503           assert fsen.getChildren().contains( child );
 504           assert child.getParents().contains( fsen );
 505           flatNodesToVisit.put( child.getFlatExit(), fm );
 506
 507           // explicitly do this to handle the case that you
 508           // should mark yourself as possibly executing at
 509           // your own exit, because one instance can
 510           // recursively invoke another
 511           addPossibleExecutingRBlock( child.getFlatExit(), fsen );
 512
 513           continue;
 514         }
 515
 516         if( fn instanceof FlatCall ) {
 517           // start visiting nodes in other contexts
 518           FlatCall         fc       = (FlatCall) fn;
 519           MethodDescriptor mdCallee = fc.getMethod();
 520
 521           Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
 522
 523           if( mdCallee.isStatic() ) {
 524             implementations.add( mdCallee );
 525           } else {
 526             TypeDescriptor typeDesc = fc.getThis().getType();
 527             implementations.addAll( callGraph.getMethods( mdCallee, typeDesc ) );
 528           }
 529
 530           for( Iterator imps = implementations.iterator(); imps.hasNext(); ) {
 531             MethodDescriptor mdImp = (MethodDescriptor) imps.next();
 532             FlatMethod       fmImp = state.getMethodFlat( mdImp );
 533             flatNodesToVisit.put( fmImp, fmImp );
 534
 535             // propagate your IR graph predecessor's stall site potential
 536             mergeIsPotentialStallSite( fmImp, isPotentialStallSite );
 537           }
 538           // don't 'continue' out of this loop, also enqueue
 539           // flat nodes that flow in the current method context
 540         }
 541
 542         // otherwise keep visiting nodes in same context
 543         for( int i = 0; i < fn.numNext(); i++ ) {
 544           FlatNode nn = fn.getNext( i );
 545
 546           if( !visited.contains( nn ) ) {
 547             flatNodesToVisit.put( nn, fm );
 548
 549             // propagate your IR graph predecessor's stall site potential
 550             mergeIsPotentialStallSite( nn, isPotentialStallSite );
 551           }
 552         }
 553       }
 554     }
 555   }
 556
 557
 558
 559   protected void addPossibleExecutingRBlock( FlatNode          fn,
 560                                              FlatSESEEnterNode fsen ) {
 561
 562     Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get( fn );
 563     if( currentSESEs == null ) {
 564       currentSESEs = new HashSet<FlatSESEEnterNode>();
 565     }
 566
 567     currentSESEs.add( fsen );
 568     fn2currentSESEs.put( fn, currentSESEs );
 569   }
 570
 571
 572   // definitively set whether a statement is a potential stall site
 573   // such as a task exit is FALSE and the statement following an exit
 574   // is TRUE
 575   protected void setIsPotentialStallSite( FlatNode   fn,
 576                                           Boolean    ipss ) {
 577     fn2isPotentialStallSite.put( fn, ipss );
 578   }
 579
 580
 581   // Use this to OR the previous result with a new result
 582   protected void mergeIsPotentialStallSite( FlatNode   fn,
 583                                             Boolean    ipss ) {
 584     Boolean ipssPrev = isPotentialStallSite( fn );
 585     setIsPotentialStallSite( fn, ipssPrev || ipss );
 586   }
 587
 588
 589
 590
 591
 592   /////////////////////////////////////////////////
 593   // for DEBUG
 594   /////////////////////////////////////////////////
 595   protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
 596     Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
 597     while (mdItr.hasNext()) {
 598       FlatMethod fm = state.getMethodFlat(mdItr.next());
 599       printStatusMap(fm);
 600     }
 601     System.exit( 0 );
 602   }
 603
 604   protected void printStatusMap(FlatMethod fm) {
 605
 606     System.out.println("\n\n=== "+fm+" ===");
 607
 608     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 609     flatNodesToVisit.add(fm);
 610
 611     Set<FlatNode> visited = new HashSet<FlatNode>();
 612
 613     while (!flatNodesToVisit.isEmpty()) {
 614       Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
 615       FlatNode fn = fnItr.next();
 616
 617       flatNodesToVisit.remove(fn);
 618       visited.add(fn);
 619
 620       System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
 621
 622       for (int i = 0; i < fn.numNext(); i++) {
 623         FlatNode nn = fn.getNext(i);
 624
 625         if (!visited.contains(nn)) {
 626           flatNodesToVisit.add(nn);
 627         }
 628       }
 629     }
 630   }
 631
 632 }