changeset 59790:49fee4ea8073

8246203: Segmentation fault in verification due to stack overflow with -XX:+VerifyIterativeGVN Summary: Replace the recursive verification algorithm with an iterative one to avoid a stack overflow for large graphs. Reviewed-by: kvn, thartmann
author chagedorn
date Mon, 15 Jun 2020 09:50:11 +0200
parents 627cfc1935b7
children a22af2c3d969
files src/hotspot/share/opto/node.cpp src/hotspot/share/opto/node.hpp src/hotspot/share/opto/phaseX.cpp test/hotspot/jtreg/compiler/loopopts/TestDeepGraphVerifyIterativeGVN.java
diffstat 4 files changed, 157 insertions(+), 54 deletions(-) [+]
line wrap: on
line diff
--- a/src/hotspot/share/opto/node.cpp	Fri Jun 12 16:40:47 2020 +0200
+++ b/src/hotspot/share/opto/node.cpp	Mon Jun 15 09:50:11 2020 +0200
@@ -2152,63 +2152,79 @@
   }
 }
 
-void Node::verify_recur(const Node *n, int verify_depth,
-                        VectorSet &old_space, VectorSet &new_space) {
-  if ( verify_depth == 0 )  return;
-  if (verify_depth > 0)  --verify_depth;
+// Verify all nodes if verify_depth is negative
+void Node::verify(Node* n, int verify_depth) {
+  assert(verify_depth != 0, "depth should not be 0");
+  ResourceMark rm;
+  ResourceArea* area = Thread::current()->resource_area();
+  VectorSet old_space(area);
+  VectorSet new_space(area);
+  Node_List worklist(area);
+  worklist.push(n);
+  Compile* C = Compile::current();
+  uint last_index_on_current_depth = 0;
+  verify_depth--; // Visiting the first node on depth 1
+  // Only add nodes to worklist if verify_depth is negative (visit all nodes) or greater than 0
+  bool add_to_worklist = verify_depth != 0;
 
-  Compile* C = Compile::current();
 
-  // Contained in new_space or old_space?
-  VectorSet *v = C->node_arena()->contains(n) ? &new_space : &old_space;
-  // Check for visited in the proper space.  Numberings are not unique
-  // across spaces so we need a separate VectorSet for each space.
-  if( v->test_set(n->_idx) ) return;
+  for (uint list_index = 0; list_index < worklist.size(); list_index++) {
+    n = worklist[list_index];
 
-  if (n->is_Con() && n->bottom_type() == Type::TOP) {
-    if (C->cached_top_node() == NULL)
-      C->set_cached_top_node((Node*)n);
-    assert(C->cached_top_node() == n, "TOP node must be unique");
-  }
+    if (n->is_Con() && n->bottom_type() == Type::TOP) {
+      if (C->cached_top_node() == NULL) {
+        C->set_cached_top_node((Node*)n);
+      }
+      assert(C->cached_top_node() == n, "TOP node must be unique");
+    }
 
-  for( uint i = 0; i < n->len(); i++ ) {
-    Node *x = n->in(i);
-    if (!x || x->is_top()) continue;
+    for (uint i = 0; i < n->len(); i++) {
+      Node* x = n->in(i);
+      if (!x || x->is_top()) {
+        continue;
+      }
 
-    // Verify my input has a def-use edge to me
-    if (true /*VerifyDefUse*/) {
+      // Verify my input has a def-use edge to me
       // Count use-def edges from n to x
       int cnt = 0;
-      for( uint j = 0; j < n->len(); j++ )
-        if( n->in(j) == x )
+      for (uint j = 0; j < n->len(); j++) {
+        if (n->in(j) == x) {
           cnt++;
+        }
+      }
+
       // Count def-use edges from x to n
       uint max = x->_outcnt;
-      for( uint k = 0; k < max; k++ )
-        if (x->_out[k] == n)
+      for (uint k = 0; k < max; k++) {
+        if (x->_out[k] == n) {
           cnt--;
-      assert( cnt == 0, "mismatched def-use edge counts" );
+        }
+      }
+      assert(cnt == 0, "mismatched def-use edge counts");
+
+      // Contained in new_space or old_space?
+      VectorSet* v = C->node_arena()->contains(x) ? &new_space : &old_space;
+      // Check for visited in the proper space. Numberings are not unique
+      // across spaces so we need a separate VectorSet for each space.
+      if (add_to_worklist && !v->test_set(x->_idx)) {
+        worklist.push(x);
+      }
     }
 
-    verify_recur(x, verify_depth, old_space, new_space);
+    if (verify_depth > 0 && list_index == last_index_on_current_depth) {
+      // All nodes on this depth were processed and its inputs are on the worklist. Decrement verify_depth and
+      // store the current last list index which is the last node in the list with the new depth. All nodes
+      // added afterwards will have a new depth again. Stop adding new nodes if depth limit is reached (=0).
+      verify_depth--;
+      if (verify_depth == 0) {
+        add_to_worklist = false;
+      }
+      last_index_on_current_depth = worklist.size() - 1;
+    }
   }
-
-}
-
-//------------------------------verify-----------------------------------------
-// Check Def-Use info for my subgraph
-void Node::verify() const {
-  Compile* C = Compile::current();
-  Node* old_top = C->cached_top_node();
-  ResourceMark rm;
-  ResourceArea *area = Thread::current()->resource_area();
-  VectorSet old_space(area), new_space(area);
-  verify_recur(this, -1, old_space, new_space);
-  C->set_cached_top_node(old_top);
 }
 #endif
 
-
 //------------------------------walk-------------------------------------------
 // Graph walk, with both pre-order and post-order functions
 void Node::walk(NFunc pre, NFunc post, void *env) {
--- a/src/hotspot/share/opto/node.hpp	Fri Jun 12 16:40:47 2020 +0200
+++ b/src/hotspot/share/opto/node.hpp	Mon Jun 15 09:50:11 2020 +0200
@@ -1150,8 +1150,7 @@
   void collect_nodes_out_all_ctrl_boundary(GrowableArray<Node*> *ns) const;
 
   void verify_edges(Unique_Node_List &visited); // Verify bi-directional edges
-  void verify() const;               // Check Def-Use info for my subgraph
-  static void verify_recur(const Node *n, int verify_depth, VectorSet &old_space, VectorSet &new_space);
+  static void verify(Node* n, int verify_depth);
 
   // This call defines a class-unique string used to identify class instances
   virtual const char *Name() const;
--- a/src/hotspot/share/opto/phaseX.cpp	Fri Jun 12 16:40:47 2020 +0200
+++ b/src/hotspot/share/opto/phaseX.cpp	Mon Jun 15 09:50:11 2020 +0200
@@ -1005,24 +1005,22 @@
   if (VerifyIterativeGVN) {
     _verify_window[_verify_counter % _verify_window_size] = n;
     ++_verify_counter;
-    ResourceMark rm;
-    ResourceArea* area = Thread::current()->resource_area();
-    VectorSet old_space(area), new_space(area);
-    if (C->unique() < 1000 ||
-        0 == _verify_counter % (C->unique() < 10000 ? 10 : 100)) {
+    if (C->unique() < 1000 || 0 == _verify_counter % (C->unique() < 10000 ? 10 : 100)) {
       ++_verify_full_passes;
-      Node::verify_recur(C->root(), -1, old_space, new_space);
+      Node::verify(C->root(), -1);
     }
-    const int verify_depth = 4;
-    for ( int i = 0; i < _verify_window_size; i++ ) {
+    for (int i = 0; i < _verify_window_size; i++) {
       Node* n = _verify_window[i];
-      if ( n == NULL )  continue;
-      if( n->in(0) == NodeSentinel ) {  // xform_idom
+      if (n == NULL) {
+        continue;
+      }
+      if (n->in(0) == NodeSentinel) { // xform_idom
         _verify_window[i] = n->in(1);
-        --i; continue;
+        --i;
+        continue;
       }
       // Typical fanout is 1-2, so this call visits about 6 nodes.
-      Node::verify_recur(n, verify_depth, old_space, new_space);
+      Node::verify(n, 4);
     }
   }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/jtreg/compiler/loopopts/TestDeepGraphVerifyIterativeGVN.java	Mon Jun 15 09:50:11 2020 +0200
@@ -0,0 +1,90 @@
+/*
+ * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * @test
+ * @bug 8246203
+ * @requires vm.debug == true & vm.flavor == "server"
+ * @summary Test which causes a stack overflow segmentation fault with -XX:+VerifyIterativeGVN due to a too deep recursion in Node::verify_recur().
+ *
+ * @run main/othervm/timeout=600 -Xcomp -XX:+VerifyIterativeGVN -XX:CompileCommand=compileonly,compiler.loopopts.TestDeepGraphVerifyIterativeGVN::*
+ *                               compiler.loopopts.TestDeepGraphVerifyIterativeGVN
+ */
+
+package compiler.loopopts;
+
+public class TestDeepGraphVerifyIterativeGVN
+{
+    static volatile int[] iArr;
+    static volatile int x;
+
+    public static void main(String[] arr) {
+        /*
+         * Just enough statements to create a deep enough graph (i.e. many nodes in one chain). The current recursive verification in Node::verify_recur() will follow this chain
+         * and call itself again for each newly discovered input node. The current implementation can only handle up to around 10000 recursive calls and will then crash with a
+         * stack overflow segementation fault. The iterative fix needs much less memory and does not result in a segementation fault anymore.
+         */
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+        iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 }; iArr = new int[] { x % 2 };
+    }
+}