truffle: src/share/vm/opto/loopnode.cpp comparison

comparison src/share/vm/opto/loopnode.cpp @ 921:046932b72aa2

6862956: PhaseIdealLoop should have a CFG verification mode Reviewed-by: kvn, twisti

author	never
date	Fri, 14 Aug 2009 00:02:12 -0700
parents	fbde8ec322d0
children	8b22f86d1740

comparison

equal deleted inserted replaced

-:10d8c0d0d60e
+:046932b72aa2
 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 )
+void PhaseIdealLoop::build_and_optimize(bool do_split_ifs) {
-: PhaseTransform(Ideal_Loop),
+int old_progress = C->major_progress();
-_igvn(igvn),
-_dom_lca_tags(C->comp_arena()) {
 // Reset major-progress flag for the driver's heuristics
 C->clear_major_progress();
 #ifndef PRODUCT
 // Capture for later assert
 if (C->failing()) {
 return;
 }
 // No loops after all
-if( !_ltree_root->_child ) C->set_has_loops(false);
+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())) {
-C->clear_major_progress();
+if (!_verify_only) {
-C->record_method_not_compilable("empty program detected during loop optimization");
+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) {
+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 && _ltree_root->_child ) {
+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();
 _dom_stk   = NULL; // Allocated on demand in recompute_dom_depth
 memset( _dom_depth, 0, _idom_size * sizeof(uint) );
 Dominators();
-// As a side effect, Dominators removed any unreachable CFG paths
+if (!_verify_only) {
-// into RegionNodes.  It doesn't do this test against Root, so
+// As a side effect, Dominators removed any unreachable CFG paths
-// we do it here.
+// into RegionNodes.  It doesn't do this test against Root, so
-for( uint i = 1; i < C->root()->req(); i++ ) {
+// we do it here.
-if( !_nodes[C->root()->in(i)->_idx] ) {    // Dead path into Root?
+for( uint i = 1; i < C->root()->req(); i++ ) {
-_igvn.hash_delete(C->root());
+if( !_nodes[C->root()->in(i)->_idx] ) {    // Dead path into Root?
-C->root()->del_req(i);
+_igvn.hash_delete(C->root());
-_igvn._worklist.push(C->root());
+C->root()->del_req(i);
-i--;                      // Rerun same iteration on compressed edges
+_igvn._worklist.push(C->root());
-}
+i--;                      // Rerun same iteration on compressed edges
 }
+}
-// Given dominators, try to find inner loops with calls that must
-// always be executed (call dominates loop tail).  These loops do
+// Given dominators, try to find inner loops with calls that must
-// not need a separate safepoint.
+// always be executed (call dominates loop tail).  These loops do
-Node_List cisstack(a);
+// not need a separate safepoint.
-_ltree_root->check_safepts(visited, cisstack);
+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.
 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 );
+build_loop_early( visited, worklist, nstack );
 // Given early legal placement, try finding counted loops.  This placement
 // is good enough to discover most loop invariants.
-if( !verify_me )
+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 );
+build_loop_late( visited, worklist, nstack );
+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());
+_igvn.remove_globally_dead_node(_deadlist.pop());
 }
 #ifndef PRODUCT
 C->verify_graph_edges();
-if( verify_me ) {             // Nested verify pass?
+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();
 // 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 );
+PhaseIdealLoop loop_verify( _igvn, this );
 VectorSet visited(Thread::current()->resource_area());
 fail = 0;
 verify_compare( C->root(), &loop_verify, visited );
 assert( fail == 0, "verify loops failed" );
 // 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
-// Insert the NeverBranch between 'm' and it's control user.
+if (!_verify_only) {
-NeverBranchNode *iff = new (C, 1) NeverBranchNode( m );
+// Insert the NeverBranch between 'm' and it's control user.
-_igvn.register_new_node_with_optimizer(iff);
+NeverBranchNode *iff = new (C, 1) NeverBranchNode( m );
-set_loop(iff, l);
+_igvn.register_new_node_with_optimizer(iff);
-Node *if_t = new (C, 1) CProjNode( iff, 0 );
+set_loop(iff, l);
-_igvn.register_new_node_with_optimizer(if_t);
+Node *if_t = new (C, 1) CProjNode( iff, 0 );
-set_loop(if_t, l);
+_igvn.register_new_node_with_optimizer(if_t);
+set_loop(if_t, l);
-Node* cfg = NULL;       // Find the One True Control User of m
-for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) {
+Node* cfg = NULL;       // Find the One True Control User of m
-Node* x = m->fast_out(j);
+for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) {
-if (x->is_CFG() && x != m && x != iff)
+Node* x = m->fast_out(j);
-{ cfg = x; break; }
+if (x->is_CFG() && x != m && x != iff)
+{ cfg = x; break; }
+}
+assert(cfg != NULL, "must find the control user of m");
+uint k = 0;             // Probably cfg->in(0)
+while( cfg->in(k) != m ) k++; // But check incase cfg is a Region
+cfg->set_req( k, if_t ); // Now point to NeverBranch
+// Now create the never-taken loop exit
+Node *if_f = new (C, 1) CProjNode( iff, 1 );
+_igvn.register_new_node_with_optimizer(if_f);
+set_loop(if_f, l);
+// Find frame ptr for Halt.  Relies on the optimizer
+// V-N'ing.  Easier and quicker than searching through
+// the program structure.
+Node *frame = new (C, 1) ParmNode( C->start(), TypeFunc::FramePtr );
+_igvn.register_new_node_with_optimizer(frame);
+// 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);
 }
-assert(cfg != NULL, "must find the control user of m");
-uint k = 0;             // Probably cfg->in(0)
-while( cfg->in(k) != m ) k++; // But check incase cfg is a Region
-cfg->set_req( k, if_t ); // Now point to NeverBranch
-// Now create the never-taken loop exit
-Node *if_f = new (C, 1) CProjNode( iff, 1 );
-_igvn.register_new_node_with_optimizer(if_f);
-set_loop(if_f, l);
-// Find frame ptr for Halt.  Relies on the optimizer
-// V-N'ing.  Easier and quicker than searching through
-// the program structure.
-Node *frame = new (C, 1) ParmNode( C->start(), TypeFunc::FramePtr );
-_igvn.register_new_node_with_optimizer(frame);
-// 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.
-while( is_postvisited(l->_head) ) {
+if (!_verify_only) {
-// found irreducible
+while( is_postvisited(l->_head) ) {
-l->_irreducible = 1; // = true
+// found irreducible
-l = l->_parent;
+l->_irreducible = 1; // = true
-_has_irreducible_loops = true;
+l = l->_parent;
-// Check for bad CFG here to prevent crash, and bailout of compile
+_has_irreducible_loops = true;
-if (l == NULL) {
+// Check for bad CFG here to prevent crash, and bailout of compile
-C->record_method_not_compilable("unhandled CFG detected during loop optimization");
+if (l == NULL) {
-return pre_order;
+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
 //------------------------------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 ) {
+void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
 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;
 }
 // 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_me && ilt->_has_sfpt && n->Opcode() == Op_SafePoint &&
+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
 LCA = dom_lca( LCA, region->in(i) );
 }
 return LCA;
 }
-//------------------------------get_late_ctrl----------------------------------
+bool PhaseIdealLoop::verify_dominance(Node* n, Node* use, Node* LCA, Node* early) {
-// Compute latest legal control.
+bool had_error = false;
-Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) {
+#ifdef ASSERT
-assert(early != NULL, "early control should not be NULL");
+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
 }
 //------------------------------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 ) {
+void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
 while (worklist.size() != 0) {
 Node *n = worklist.pop();
 // Only visit once
 if (visited.test_set(n->_idx)) continue;
 uint cnt = n->outcnt();
 // 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);
+build_loop_late_post(n);
 if (nstack.is_empty()) {
 // Finished all nodes on stack.
 // Process next node on the worklist.
 break;
 }
 }
 //------------------------------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 ) {
+void PhaseIdealLoop::build_loop_late_post( Node *n ) {
-if (n->req() == 2 && n->Opcode() == Op_ConvI2L && !C->major_progress()) {
+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) ) {
 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();
 }
 #ifdef ASSERT
 // If verifying, verify that 'verify_me' has a legal location
 // and choose it as our location.
-if( verify_me ) {
+if( _verify_me ) {
-Node *v_ctrl = verify_me->get_ctrl_no_update(n);
+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
 }

Mercurial > hg > truffle

comparison src/share/vm/opto/loopnode.cpp @ 921:046932b72aa2