8231412: C2: InitializeNode::detect_init_independence() bails out on simple IR shapes
authorchagedorn
Wed, 23 Oct 2019 12:21:32 +0200
changeset 58751 0f882d53c204
parent 58750 c8d42aa9359a
child 58752 765710337ee1
8231412: C2: InitializeNode::detect_init_independence() bails out on simple IR shapes Summary: Avoids early bailout of capturing a field store to remove unnecessary zeroing in simple methods containing only non-escaping objects. Reviewed-by: roland, thartmann
src/hotspot/share/opto/memnode.cpp
src/hotspot/share/opto/memnode.hpp
src/hotspot/share/opto/phaseX.cpp
test/hotspot/jtreg/compiler/escapeAnalysis/TestEliminateAllocation.java
--- a/src/hotspot/share/opto/memnode.cpp	Wed Oct 23 12:17:14 2019 +0200
+++ b/src/hotspot/share/opto/memnode.cpp	Wed Oct 23 12:21:32 2019 +0200
@@ -3534,37 +3534,51 @@
 // within the initialization without creating a vicious cycle, such as:
 //     { Foo p = new Foo(); p.next = p; }
 // True for constants and parameters and small combinations thereof.
-bool InitializeNode::detect_init_independence(Node* n, int& count) {
-  if (n == NULL)      return true;   // (can this really happen?)
-  if (n->is_Proj())   n = n->in(0);
-  if (n == this)      return false;  // found a cycle
-  if (n->is_Con())    return true;
-  if (n->is_Start())  return true;   // params, etc., are OK
-  if (n->is_Root())   return true;   // even better
-
-  Node* ctl = n->in(0);
-  if (ctl != NULL && !ctl->is_top()) {
-    if (ctl->is_Proj())  ctl = ctl->in(0);
-    if (ctl == this)  return false;
-
-    // If we already know that the enclosing memory op is pinned right after
-    // the init, then any control flow that the store has picked up
-    // must have preceded the init, or else be equal to the init.
-    // Even after loop optimizations (which might change control edges)
-    // a store is never pinned *before* the availability of its inputs.
-    if (!MemNode::all_controls_dominate(n, this))
-      return false;                  // failed to prove a good control
-  }
-
-  // Check data edges for possible dependencies on 'this'.
-  if ((count += 1) > 20)  return false;  // complexity limit
-  for (uint i = 1; i < n->req(); i++) {
-    Node* m = n->in(i);
-    if (m == NULL || m == n || m->is_top())  continue;
-    uint first_i = n->find_edge(m);
-    if (i != first_i)  continue;  // process duplicate edge just once
-    if (!detect_init_independence(m, count)) {
-      return false;
+bool InitializeNode::detect_init_independence(Node* value, PhaseGVN* phase) {
+  ResourceMark rm;
+  Unique_Node_List worklist;
+  worklist.push(value);
+
+  uint complexity_limit = 20;
+  for (uint j = 0; j < worklist.size(); j++) {
+    if (j >= complexity_limit) {
+      return false;  // Bail out if processed too many nodes
+    }
+
+    Node* n = worklist.at(j);
+    if (n == NULL)      continue;   // (can this really happen?)
+    if (n->is_Proj())   n = n->in(0);
+    if (n == this)      return false;  // found a cycle
+    if (n->is_Con())    continue;
+    if (n->is_Start())  continue;   // params, etc., are OK
+    if (n->is_Root())   continue;   // even better
+
+    // There cannot be any dependency if 'n' is a CFG node that dominates the current allocation
+    if (n->is_CFG() && phase->is_dominator(n, allocation())) {
+      continue;
+    }
+
+    Node* ctl = n->in(0);
+    if (ctl != NULL && !ctl->is_top()) {
+      if (ctl->is_Proj())  ctl = ctl->in(0);
+      if (ctl == this)  return false;
+
+      // If we already know that the enclosing memory op is pinned right after
+      // the init, then any control flow that the store has picked up
+      // must have preceded the init, or else be equal to the init.
+      // Even after loop optimizations (which might change control edges)
+      // a store is never pinned *before* the availability of its inputs.
+      if (!MemNode::all_controls_dominate(n, this))
+        return false;                  // failed to prove a good control
+    }
+
+    // Check data edges for possible dependencies on 'this'.
+    for (uint i = 1; i < n->req(); i++) {
+      Node* m = n->in(i);
+      if (m == NULL || m == n || m->is_top())  continue;
+
+      // Only process data inputs once
+      worklist.push(m);
     }
   }
 
@@ -3575,7 +3589,7 @@
 // an initialization.  Returns zero if a check fails.
 // On success, returns the (constant) offset to which the store applies,
 // within the initialized memory.
-intptr_t InitializeNode::can_capture_store(StoreNode* st, PhaseTransform* phase, bool can_reshape) {
+intptr_t InitializeNode::can_capture_store(StoreNode* st, PhaseGVN* phase, bool can_reshape) {
   const int FAIL = 0;
   if (st->req() != MemNode::ValueIn + 1)
     return FAIL;                // an inscrutable StoreNode (card mark?)
@@ -3597,8 +3611,8 @@
     return FAIL;                // mismatched access
   }
   Node* val = st->in(MemNode::ValueIn);
-  int complexity_count = 0;
-  if (!detect_init_independence(val, complexity_count))
+
+  if (!detect_init_independence(val, phase))
     return FAIL;                // stored value must be 'simple enough'
 
   // The Store can be captured only if nothing after the allocation
@@ -3796,7 +3810,7 @@
 //                      rawstore1 rawstore2)
 //
 Node* InitializeNode::capture_store(StoreNode* st, intptr_t start,
-                                    PhaseTransform* phase, bool can_reshape) {
+                                    PhaseGVN* phase, bool can_reshape) {
   assert(stores_are_sane(phase), "");
 
   if (start < 0)  return NULL;
--- a/src/hotspot/share/opto/memnode.hpp	Wed Oct 23 12:17:14 2019 +0200
+++ b/src/hotspot/share/opto/memnode.hpp	Wed Oct 23 12:21:32 2019 +0200
@@ -1387,11 +1387,11 @@
 
   // See if this store can be captured; return offset where it initializes.
   // Return 0 if the store cannot be moved (any sort of problem).
-  intptr_t can_capture_store(StoreNode* st, PhaseTransform* phase, bool can_reshape);
+  intptr_t can_capture_store(StoreNode* st, PhaseGVN* phase, bool can_reshape);
 
   // Capture another store; reformat it to write my internal raw memory.
   // Return the captured copy, else NULL if there is some sort of problem.
-  Node* capture_store(StoreNode* st, intptr_t start, PhaseTransform* phase, bool can_reshape);
+  Node* capture_store(StoreNode* st, intptr_t start, PhaseGVN* phase, bool can_reshape);
 
   // Find captured store which corresponds to the range [start..start+size).
   // Return my own memory projection (meaning the initial zero bits)
@@ -1414,7 +1414,7 @@
 
   Node* make_raw_address(intptr_t offset, PhaseTransform* phase);
 
-  bool detect_init_independence(Node* n, int& count);
+  bool detect_init_independence(Node* value, PhaseGVN* phase);
 
   void coalesce_subword_stores(intptr_t header_size, Node* size_in_bytes,
                                PhaseGVN* phase);
--- a/src/hotspot/share/opto/phaseX.cpp	Wed Oct 23 12:17:14 2019 +0200
+++ b/src/hotspot/share/opto/phaseX.cpp	Wed Oct 23 12:21:32 2019 +0200
@@ -899,7 +899,7 @@
   while (d != n) {
     n = IfNode::up_one_dom(n, linear_only);
     i++;
-    if (n == NULL || i >= 10) {
+    if (n == NULL || i >= 100) {
       return false;
     }
   }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/jtreg/compiler/escapeAnalysis/TestEliminateAllocation.java	Wed Oct 23 12:21:32 2019 +0200
@@ -0,0 +1,74 @@
+/*
+ * Copyright (c) 2019, 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 8231412
+ * @summary The enhancement eliminates all allocations in the loop body of test() due to an improved field zeroing elimination dominance check.
+ * @run main/othervm -XX:-TieredCompilation -XX:CompileCommand=compileonly,compiler.escapeAnalysis.TestEliminateAllocation::test
+ *                   compiler.escapeAnalysis.TestEliminateAllocation
+ */
+
+package compiler.escapeAnalysis;
+
+public class TestEliminateAllocation {
+
+    public static int a = 20;
+    public static int b = 30;
+    public static int c = 40;
+
+    public void test() {
+        int i = 0;
+
+        /*
+         * The resulting IR for the loop body contains 2 allocations, one Wrapper and an int array
+         * The array field store in the Wrapper object 'wrapper.arr = arr' cannot be capturued due to an early bail out.
+         * Therefore, the initial value of wrapper.arr is null.
+         * As a result, the escape analysis marks the array allocation as not scalar replaceable:
+         * 'wrapper.arr' which is null is merged with the int array object in the assignment 'wrapper.arr = arr'.
+         * Both null and the int array are treated as different objects. As a result the array allocation cannot be eliminated.
+         *
+         * The new enhancement does not bail out early anymore and therefore escape analysis does not mark it as
+         * not scalar replaceable. This results in elimination of all allocations in this method.
+         */
+        do {
+            int[] arr = new int[] { a / b / c };
+            Wrapper wrapper = new Wrapper();
+            wrapper.setArr(arr);
+            i++;
+        }
+        while (i < 10);
+    }
+
+    public static void main(String[] strArr) {
+        TestEliminateAllocation _instance = new TestEliminateAllocation();
+        for (int i = 0; i < 10_000; i++ ) {
+            _instance.test();
+        }
+    }
+}
+
+class Wrapper {
+    int[] arr;
+    void setArr(int... many) { arr = many; }
+}