*** old/src/share/vm/opto/loopnode.cpp	Wed Aug 12 15:10:32 2009
--- new/src/share/vm/opto/loopnode.cpp	Wed Aug 12 15:10:31 2009

*** 1418,1434 ****
--- 1418,1433 ----
      if( loop->_next  ) log_loop_tree(root, loop->_next, log);
    }
  }
  
  //=============================================================================
! //------------------------------PhaseIdealLoop---------------------------------
! //----------------------------build_and_optimize-------------------------------
  // Create a PhaseLoop.  Build the ideal Loop tree.  Map each Ideal Node to
  // its corresponding LoopNode.  If 'optimize' is true, do some loop cleanups.
  PhaseIdealLoop::PhaseIdealLoop( PhaseIterGVN &igvn, const PhaseIdealLoop *verify_me, bool do_split_ifs )
    : PhaseTransform(Ideal_Loop),
      _igvn(igvn),
      _dom_lca_tags(C->comp_arena()) {
+ void PhaseIdealLoop::build_and_optimize(bool do_split_ifs) {
+   int old_progress = C->major_progress();
+ 
    // Reset major-progress flag for the driver's heuristics
    C->clear_major_progress();
  
  #ifndef PRODUCT
    // Capture for later assert

*** 1463,1494 ****
--- 1462,1495 ----
    if (C->failing()) {
      return;
    }
  
    // No loops after all
!   if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
  
    // There should always be an outer loop containing the Root and Return nodes.
    // If not, we have a degenerate empty program.  Bail out in this case.
    if (!has_node(C->root())) {
+     if (!_verify_only) {
        C->clear_major_progress();
        C->record_method_not_compilable("empty program detected during loop optimization");
+     }
      return;
    }
  
    // Nothing to do, so get out
!   if( !C->has_loops() && !do_split_ifs && !_verify_me && !_verify_only ) {
      _igvn.optimize();           // Cleanup NeverBranches
      return;
    }
  
    // Set loop nesting depth
    _ltree_root->set_nest( 0 );
  
    // Split shared headers and insert loop landing pads.
    // Do not bother doing this on the Root loop of course.
!   if( !_verify_me && !_verify_only && _ltree_root->_child ) {
      if( _ltree_root->_child->beautify_loops( this ) ) {
        // Re-build loop tree!
        _ltree_root->_child = NULL;
        _nodes.clear();
        reallocate_preorders();

*** 1513,1522 ****
--- 1514,1524 ----
    _dom_stk   = NULL; // Allocated on demand in recompute_dom_depth
    memset( _dom_depth, 0, _idom_size * sizeof(uint) );
  
    Dominators();
  
+   if (!_verify_only) {
      // As a side effect, Dominators removed any unreachable CFG paths
      // into RegionNodes.  It doesn't do this test against Root, so
      // we do it here.
      for( uint i = 1; i < C->root()->req(); i++ ) {
        if( !_nodes[C->root()->in(i)->_idx] ) {    // Dead path into Root?

*** 1530,1539 ****
--- 1532,1542 ----
      // Given dominators, try to find inner loops with calls that must
      // always be executed (call dominates loop tail).  These loops do
      // not need a separate safepoint.
      Node_List cisstack(a);
      _ltree_root->check_safepts(visited, cisstack);
+   }
  
    // Walk the DATA nodes and place into loops.  Find earliest control
    // node.  For CFG nodes, the _nodes array starts out and remains
    // holding the associated IdealLoopTree pointer.  For DATA nodes, the
    // _nodes array holds the earliest legal controlling CFG node.

*** 1546,1579 ****
--- 1549,1591 ----
    Node_List worklist(a);
    // Don't need C->root() on worklist since
    // it will be processed among C->top() inputs
    worklist.push( C->top() );
    visited.set( C->top()->_idx ); // Set C->top() as visited now
-   build_loop_early( visited, worklist, nstack, verify_me );
  
    // Given early legal placement, try finding counted loops.  This placement
    // is good enough to discover most loop invariants.
!   if( !_verify_me && !_verify_only )
      _ltree_root->counted_loop( this );
  
    // Find latest loop placement.  Find ideal loop placement.
    visited.Clear();
    init_dom_lca_tags();
    // Need C->root() on worklist when processing outs
    worklist.push( C->root() );
    NOT_PRODUCT( C->verify_graph_edges(); )
    worklist.push( C->top() );
-   build_loop_late( visited, worklist, nstack, verify_me );
  
+   if (_verify_only) {
+     // restore major progress flag
+     for (int i = 0; i < old_progress; i++)
+       C->set_major_progress();
+     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
+     assert(_igvn._worklist.size() == 0, "shouldn't push anything");
+     return;
+   }
+ 
    // clear out the dead code
    while(_deadlist.size()) {
!     _igvn.remove_globally_dead_node(_deadlist.pop());
    }
  
  #ifndef PRODUCT
    C->verify_graph_edges();
!   if( _verify_me ) {             // Nested verify pass?
      // Check to see if the verify mode is broken
      assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
      return;
    }
    if( VerifyLoopOptimizations ) verify();

*** 1676,1686 ****
--- 1688,1698 ----
  // Build a verify-only PhaseIdealLoop, and see that it agrees with me.
  static int fail;                // debug only, so its multi-thread dont care
  void PhaseIdealLoop::verify() const {
    int old_progress = C->major_progress();
    ResourceMark rm;
-   PhaseIdealLoop loop_verify( _igvn, this, false );
    VectorSet visited(Thread::current()->resource_area());
  
    fail = 0;
    verify_compare( C->root(), &loop_verify, visited );
    assert( fail == 0, "verify loops failed" );

*** 2136,2145 ****
--- 2148,2158 ----
          // new loop exit.  This would make the infinite loop a first-class
          // loop and it would then get properly optimized.  What's the use of
          // optimizing an infinite loop?
          l = _ltree_root;        // Oops, found infinite loop
  
+         if (!_verify_only) {
            // Insert the NeverBranch between 'm' and it's control user.
            NeverBranchNode *iff = new (C, 1) NeverBranchNode( m );
            _igvn.register_new_node_with_optimizer(iff);
            set_loop(iff, l);
            Node *if_t = new (C, 1) CProjNode( iff, 0 );

*** 2169,2184 ****
--- 2182,2199 ----
            // Halt & Catch Fire
            Node *halt = new (C, TypeFunc::Parms) HaltNode( if_f, frame );
            _igvn.register_new_node_with_optimizer(halt);
            set_loop(halt, l);
            C->root()->add_req(halt);
+         }
          set_loop(C->root(), _ltree_root);
        }
      }
      // Weeny check for irreducible.  This child was already visited (this
      // IS the post-work phase).  Is this child's loop header post-visited
      // as well?  If so, then I found another entry into the loop.
+     if (!_verify_only) {
        while( is_postvisited(l->_head) ) {
          // found irreducible
          l->_irreducible = 1; // = true
          l = l->_parent;
          _has_irreducible_loops = true;

*** 2186,2195 ****
--- 2201,2211 ----
          if (l == NULL) {
            C->record_method_not_compilable("unhandled CFG detected during loop optimization");
            return pre_order;
          }
        }
+     }
  
      // This Node might be a decision point for loops.  It is only if
      // it's children belong to several different loops.  The sort call
      // does a trivial amount of work if there is only 1 child or all
      // children belong to the same loop.  If however, the children

*** 2251,2261 ****
--- 2267,2277 ----
  
  //------------------------------build_loop_early-------------------------------
  // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
  // First pass computes the earliest controlling node possible.  This is the
  // controlling input with the deepest dominating depth.
- void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack, const PhaseIdealLoop *verify_me ) {
    while (worklist.size() != 0) {
      // Use local variables nstack_top_n & nstack_top_i to cache values
      // on nstack's top.
      Node *nstack_top_n = worklist.pop();
      uint  nstack_top_i = 0;

*** 2283,2293 ****
--- 2299,2309 ----
            }
            // Remove safepoints ONLY if I've already seen I don't need one.
            // (the old code here would yank a 2nd safepoint after seeing a
            // first one, even though the 1st did not dominate in the loop body
            // and thus could be avoided indefinitely)
!           if( !_verify_only && !_verify_me && ilt->_has_sfpt && n->Opcode() == Op_SafePoint &&
                is_deleteable_safept(n)) {
              Node *in = n->in(TypeFunc::Control);
              lazy_replace(n,in);       // Pull safepoint now
              // Carry on with the recursion "as if" we are walking
              // only the control input

*** 2406,2440 ****
--- 2422,2494 ----
        LCA = dom_lca( LCA, region->in(i) );
    }
    return LCA;
  }
  
  //------------------------------get_late_ctrl----------------------------------
  // Compute latest legal control.
  Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) {
    assert(early != NULL, "early control should not be NULL");
+ bool PhaseIdealLoop::verify_dominance(Node* n, Node* use, Node* LCA, Node* early) {
+   bool had_error = false;
+ #ifdef ASSERT
+   if (early != C->root()) {
+     // Make sure that there's a dominance path from use to LCA
+     Node* d = use;
+     while (d != LCA) {
+       d = idom(d);
+       if (d == C->root()) {
+         tty->print_cr("*** Use %d isn't dominated by def %s", use->_idx, n->_idx);
+         n->dump();
+         use->dump();
+         had_error = true;
+         break;
+       }
+     }
+   }
+ #endif
+   return had_error;
+ }
  
+ 
+ Node* PhaseIdealLoop::compute_lca_of_uses(Node* n, Node* early, bool verify) {
    // Compute LCA over list of uses
+   bool had_error = false;
    Node *LCA = NULL;
    for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && LCA != early; i++) {
      Node* c = n->fast_out(i);
      if (_nodes[c->_idx] == NULL)
        continue;                 // Skip the occasional dead node
      if( c->is_Phi() ) {         // For Phis, we must land above on the path
        for( uint j=1; j<c->req(); j++ ) {// For all inputs
          if( c->in(j) == n ) {   // Found matching input?
            Node *use = c->in(0)->in(j);
+           if (_verify_only && use->is_top()) continue;
            LCA = dom_lca_for_get_late_ctrl( LCA, use, n );
+           if (verify) had_error = verify_dominance(n, use, LCA, early) || had_error;
          }
        }
      } else {
        // For CFG data-users, use is in the block just prior
        Node *use = has_ctrl(c) ? get_ctrl(c) : c->in(0);
        LCA = dom_lca_for_get_late_ctrl( LCA, use, n );
+       if (verify) had_error = verify_dominance(n, use, LCA, early) || had_error;
      }
    }
+   assert(!had_error, "bad dominance");
+   return LCA;
+ }
  
+ //------------------------------get_late_ctrl----------------------------------
+ // Compute latest legal control.
+ Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) {
+   assert(early != NULL, "early control should not be NULL");
+ 
+   Node* LCA = compute_lca_of_uses(n, early);
+ #ifdef ASSERT
+   if (LCA == C->root() && LCA != early) {
+     // def doesn't dominate uses so print some useful debugging output
+     compute_lca_of_uses(n, early, true);
+   }
+ #endif
+ 
    // if this is a load, check for anti-dependent stores
    // We use a conservative algorithm to identify potential interfering
    // instructions and for rescheduling the load.  The users of the memory
    // input of this load are examined.  Any use which is not a load and is
    // dominated by early is considered a potentially interfering store.

*** 2574,2584 ****
--- 2628,2638 ----
  }
  
  //------------------------------build_loop_late--------------------------------
  // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
  // Second pass finds latest legal placement, and ideal loop placement.
- void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack, const PhaseIdealLoop *verify_me ) {
    while (worklist.size() != 0) {
      Node *n = worklist.pop();
      // Only visit once
      if (visited.test_set(n->_idx)) continue;
      uint cnt = n->outcnt();

*** 2610,2620 ****
--- 2664,2674 ----
            // push dead code onto a worklist
            _deadlist.push(use);
          }
        } else {
          // All of n's children have been processed, complete post-processing.
-         build_loop_late_post(n, verify_me);
          if (nstack.is_empty()) {
            // Finished all nodes on stack.
            // Process next node on the worklist.
            break;
          }

*** 2629,2641 ****
--- 2683,2695 ----
  }
  
  //------------------------------build_loop_late_post---------------------------
  // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
  // Second pass finds latest legal placement, and ideal loop placement.
- void PhaseIdealLoop::build_loop_late_post( Node *n, const PhaseIdealLoop *verify_me ) {
  
!   if (n->req() == 2 && n->Opcode() == Op_ConvI2L && !C->major_progress() && !_verify_only) {
      _igvn._worklist.push(n);  // Maybe we'll normalize it, if no more loops.
    }
  
    // CFG and pinned nodes already handled
    if( n->in(0) ) {

*** 2712,2721 ****
--- 2766,2776 ----
      legal = idom(legal);        // Bump up the IDOM tree
      // Check for lower nesting depth
      if( get_loop(legal)->_nest < get_loop(least)->_nest )
        least = legal;
    }
+   assert(early == legal || legal != C->root(), "bad dominance of inputs");
  
    // Try not to place code on a loop entry projection
    // which can inhibit range check elimination.
    if (least != early) {
      Node* ctrl_out = least->unique_ctrl_out();

*** 2729,2740 ****
--- 2784,2795 ----
    }
  
  #ifdef ASSERT
    // If verifying, verify that 'verify_me' has a legal location
    // and choose it as our location.
!   if( _verify_me ) {
!     Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
      Node *legal = LCA;
      while( early != legal ) {   // While not at earliest legal
        if( legal == v_ctrl ) break;  // Check for prior good location
        legal = idom(legal)      ;// Bump up the IDOM tree
      }