# HG changeset patch
# User roland
# Date 1496387314 -7200
# Node ID 64e07017ce01798938f6b0a41118192ab5661cb5
# Parent  77c950d7840aaee6c026c15cad6961aa85bd615a
8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash
Summary: Replacing load on dst with load on src only valid if copy doesn't modify src element to load
Reviewed-by: kvn, thartmann

diff -r 77c950d7840a -r 64e07017ce01 hotspot/src/share/vm/opto/arraycopynode.cpp
--- a/hotspot/src/share/vm/opto/arraycopynode.cpp	Thu Jun 01 18:48:34 2017 +0000
+++ b/hotspot/src/share/vm/opto/arraycopynode.cpp	Fri Jun 02 09:08:34 2017 +0200
@@ -25,6 +25,7 @@
 #include "precompiled.hpp"
 #include "opto/arraycopynode.hpp"
 #include "opto/graphKit.hpp"
+#include "runtime/sharedRuntime.hpp"
 
 ArrayCopyNode::ArrayCopyNode(Compile* C, bool alloc_tightly_coupled, bool has_negative_length_guard)
   : CallNode(arraycopy_type(), NULL, TypeRawPtr::BOTTOM),
@@ -631,42 +632,76 @@
   return CallNode::may_modify_arraycopy_helper(dest_t, t_oop, phase);
 }
 
-bool ArrayCopyNode::may_modify_helper(const TypeOopPtr *t_oop, Node* n, PhaseTransform *phase, ArrayCopyNode*& ac) {
-  if (n->Opcode() == Op_StoreCM ||
-      n->Opcode() == Op_StoreB) {
-    // Ignore card mark stores
-    n = n->in(MemNode::Memory);
-  }
-
-  if (n->is_Proj()) {
-    n = n->in(0);
-    if (n->is_Call() && n->as_Call()->may_modify(t_oop, phase)) {
-      if (n->isa_ArrayCopy() != NULL) {
-        ac = n->as_ArrayCopy();
-      }
-      return true;
-    }
+bool ArrayCopyNode::may_modify_helper(const TypeOopPtr *t_oop, Node* n, PhaseTransform *phase, CallNode*& call) {
+  if (n != NULL &&
+      n->is_Call() &&
+      n->as_Call()->may_modify(t_oop, phase) &&
+      (n->as_Call()->is_ArrayCopy() || n->as_Call()->is_call_to_arraycopystub())) {
+    call = n->as_Call();
+    return true;
   }
   return false;
 }
 
-bool ArrayCopyNode::may_modify(const TypeOopPtr *t_oop, MemBarNode* mb, PhaseTransform *phase, ArrayCopyNode*& ac) {
-  Node* mem = mb->in(TypeFunc::Memory);
-
-  if (mem->is_MergeMem()) {
-    Node* n = mem->as_MergeMem()->memory_at(Compile::AliasIdxRaw);
-    if (may_modify_helper(t_oop, n, phase, ac)) {
-      return true;
-    } else if (n->is_Phi()) {
-      for (uint i = 1; i < n->req(); i++) {
-        if (n->in(i) != NULL) {
-          if (may_modify_helper(t_oop, n->in(i), phase, ac)) {
-            return true;
+static Node* step_over_gc_barrier(Node* c) {
+  if (UseG1GC && !GraphKit::use_ReduceInitialCardMarks() &&
+      c != NULL && c->is_Region() && c->req() == 3) {
+    for (uint i = 1; i < c->req(); i++) {
+      if (c->in(i) != NULL && c->in(i)->is_Region() &&
+          c->in(i)->req() == 3) {
+        Node* r = c->in(i);
+        for (uint j = 1; j < r->req(); j++) {
+          if (r->in(j) != NULL && r->in(j)->is_Proj() &&
+              r->in(j)->in(0) != NULL &&
+              r->in(j)->in(0)->Opcode() == Op_CallLeaf &&
+              r->in(j)->in(0)->as_Call()->entry_point() == CAST_FROM_FN_PTR(address, SharedRuntime::g1_wb_post)) {
+            Node* call = r->in(j)->in(0);
+            c = c->in(i == 1 ? 2 : 1);
+            if (c != NULL) {
+              c = c->in(0);
+              if (c != NULL) {
+                c = c->in(0);
+                assert(call->in(0) == NULL ||
+                       call->in(0)->in(0) == NULL ||
+                       call->in(0)->in(0)->in(0) == NULL ||
+                       call->in(0)->in(0)->in(0)->in(0) == NULL ||
+                       call->in(0)->in(0)->in(0)->in(0)->in(0) == NULL ||
+                       c == call->in(0)->in(0)->in(0)->in(0)->in(0), "bad barrier shape");
+                return c;
+              }
+            }
           }
         }
       }
     }
   }
+  return c;
+}
+
+bool ArrayCopyNode::may_modify(const TypeOopPtr *t_oop, MemBarNode* mb, PhaseTransform *phase, ArrayCopyNode*& ac) {
+
+  Node* c = mb->in(0);
+
+  // step over g1 gc barrier if we're at a clone with ReduceInitialCardMarks off
+  c = step_over_gc_barrier(c);
+
+  CallNode* call = NULL;
+  if (c != NULL && c->is_Region()) {
+    for (uint i = 1; i < c->req(); i++) {
+      if (c->in(i) != NULL) {
+        Node* n = c->in(i)->in(0);
+        if (may_modify_helper(t_oop, n, phase, call)) {
+          ac = call->isa_ArrayCopy();
+          assert(c == mb->in(0), "only for clone");
+          return true;
+        }
+      }
+    }
+  } else if (may_modify_helper(t_oop, c->in(0), phase, call)) {
+    ac = call->isa_ArrayCopy();
+    assert(c == mb->in(0) || (ac != NULL && ac->is_clonebasic() && !GraphKit::use_ReduceInitialCardMarks()), "only for clone");
+    return true;
+  }
 
   return false;
 }
@@ -677,37 +712,77 @@
 // between offset_lo and offset_hi
 // if must_modify is true, return true if the copy is guaranteed to
 // write between offset_lo and offset_hi
-bool ArrayCopyNode::modifies(intptr_t offset_lo, intptr_t offset_hi, PhaseTransform* phase, bool must_modify) {
+bool ArrayCopyNode::modifies(intptr_t offset_lo, intptr_t offset_hi, PhaseTransform* phase, bool must_modify) const {
   assert(_kind == ArrayCopy || _kind == CopyOf || _kind == CopyOfRange, "only for real array copies");
 
-  Node* dest = in(ArrayCopyNode::Dest);
-  Node* src_pos = in(ArrayCopyNode::SrcPos);
-  Node* dest_pos = in(ArrayCopyNode::DestPos);
-  Node* len = in(ArrayCopyNode::Length);
+  Node* dest = in(Dest);
+  Node* dest_pos = in(DestPos);
+  Node* len = in(Length);
 
   const TypeInt *dest_pos_t = phase->type(dest_pos)->isa_int();
   const TypeInt *len_t = phase->type(len)->isa_int();
   const TypeAryPtr* ary_t = phase->type(dest)->isa_aryptr();
 
-  if (dest_pos_t != NULL && len_t != NULL && ary_t != NULL) {
-    BasicType ary_elem = ary_t->klass()->as_array_klass()->element_type()->basic_type();
-    uint header = arrayOopDesc::base_offset_in_bytes(ary_elem);
-    uint elemsize = type2aelembytes(ary_elem);
+  if (dest_pos_t == NULL || len_t == NULL || ary_t == NULL) {
+    return !must_modify;
+  }
+
+  BasicType ary_elem = ary_t->klass()->as_array_klass()->element_type()->basic_type();
+  uint header = arrayOopDesc::base_offset_in_bytes(ary_elem);
+  uint elemsize = type2aelembytes(ary_elem);
 
-    jlong dest_pos_plus_len_lo = (((jlong)dest_pos_t->_lo) + len_t->_lo) * elemsize + header;
-    jlong dest_pos_plus_len_hi = (((jlong)dest_pos_t->_hi) + len_t->_hi) * elemsize + header;
-    jlong dest_pos_lo = ((jlong)dest_pos_t->_lo) * elemsize + header;
-    jlong dest_pos_hi = ((jlong)dest_pos_t->_hi) * elemsize + header;
+  jlong dest_pos_plus_len_lo = (((jlong)dest_pos_t->_lo) + len_t->_lo) * elemsize + header;
+  jlong dest_pos_plus_len_hi = (((jlong)dest_pos_t->_hi) + len_t->_hi) * elemsize + header;
+  jlong dest_pos_lo = ((jlong)dest_pos_t->_lo) * elemsize + header;
+  jlong dest_pos_hi = ((jlong)dest_pos_t->_hi) * elemsize + header;
 
-    if (must_modify) {
-      if (offset_lo >= dest_pos_hi && offset_hi < dest_pos_plus_len_lo) {
-        return true;
-      }
-    } else {
-      if (offset_hi >= dest_pos_lo && offset_lo < dest_pos_plus_len_hi) {
-        return true;
-      }
+  if (must_modify) {
+    if (offset_lo >= dest_pos_hi && offset_hi < dest_pos_plus_len_lo) {
+      return true;
+    }
+  } else {
+    if (offset_hi >= dest_pos_lo && offset_lo < dest_pos_plus_len_hi) {
+      return true;
     }
   }
   return false;
 }
+
+// We try to replace a load from the destination of an arraycopy with
+// a load from the source so the arraycopy has a chance to be
+// eliminated. It's only valid if the arraycopy doesn't change the
+// element that would be loaded from the source array.
+bool ArrayCopyNode::can_replace_dest_load_with_src_load(intptr_t offset_lo, intptr_t offset_hi, PhaseTransform* phase) const {
+  assert(_kind == ArrayCopy || _kind == CopyOf || _kind == CopyOfRange, "only for real array copies");
+
+  Node* src = in(Src);
+  Node* dest = in(Dest);
+
+  // Check whether, assuming source and destination are the same
+  // array, the arraycopy modifies the element from the source we
+  // would load.
+  if ((src != dest && in(SrcPos) == in(DestPos)) || !modifies(offset_lo, offset_hi, phase, false)) {
+    // if not the transformation is legal
+    return true;
+  }
+
+  AllocateNode* src_alloc = AllocateNode::Ideal_allocation(src, phase);
+  AllocateNode* dest_alloc = AllocateNode::Ideal_allocation(dest, phase);
+
+  // Check whether source and destination can be proved to be
+  // different arrays
+  const TypeOopPtr* t_src = phase->type(src)->isa_oopptr();
+  const TypeOopPtr* t_dest = phase->type(dest)->isa_oopptr();
+
+  if (t_src != NULL && t_dest != NULL &&
+      (t_src->is_known_instance() || t_dest->is_known_instance()) &&
+      t_src->instance_id() != t_dest->instance_id()) {
+    return true;
+  }
+
+  if (MemNode::detect_ptr_independence(src->uncast(), src_alloc, dest->uncast(), dest_alloc, phase)) {
+    return true;
+  }
+
+  return false;
+}
diff -r 77c950d7840a -r 64e07017ce01 hotspot/src/share/vm/opto/arraycopynode.hpp
--- a/hotspot/src/share/vm/opto/arraycopynode.hpp	Thu Jun 01 18:48:34 2017 +0000
+++ b/hotspot/src/share/vm/opto/arraycopynode.hpp	Fri Jun 02 09:08:34 2017 +0200
@@ -108,7 +108,7 @@
                             BasicType copy_type, const Type* value_type, int count);
   bool finish_transform(PhaseGVN *phase, bool can_reshape,
                         Node* ctl, Node *mem);
-  static bool may_modify_helper(const TypeOopPtr *t_oop, Node* n, PhaseTransform *phase, ArrayCopyNode*& ac);
+  static bool may_modify_helper(const TypeOopPtr *t_oop, Node* n, PhaseTransform *phase, CallNode*& call);
 
 public:
 
@@ -167,7 +167,8 @@
   bool has_negative_length_guard() const { return _has_negative_length_guard; }
 
   static bool may_modify(const TypeOopPtr *t_oop, MemBarNode* mb, PhaseTransform *phase, ArrayCopyNode*& ac);
-  bool modifies(intptr_t offset_lo, intptr_t offset_hi, PhaseTransform* phase, bool must_modify);
+  bool modifies(intptr_t offset_lo, intptr_t offset_hi, PhaseTransform* phase, bool must_modify) const;
+  bool can_replace_dest_load_with_src_load(intptr_t offset_lo, intptr_t offset_hi, PhaseTransform* phase) const;
 
 #ifndef PRODUCT
   virtual void dump_spec(outputStream *st) const;
diff -r 77c950d7840a -r 64e07017ce01 hotspot/src/share/vm/opto/macro.cpp
--- a/hotspot/src/share/vm/opto/macro.cpp	Thu Jun 01 18:48:34 2017 +0000
+++ b/hotspot/src/share/vm/opto/macro.cpp	Fri Jun 02 09:08:34 2017 +0200
@@ -1047,7 +1047,9 @@
         // opportunities for allocation elimination
         Node* src = ac->in(ArrayCopyNode::Src);
         ac->replace_edge(src, top());
-        if (src->outcnt() == 0) {
+        // src can be top at this point if src and dest of the
+        // arraycopy were the same
+        if (src->outcnt() == 0 && !src->is_top()) {
           _igvn.remove_dead_node(src);
         }
 
diff -r 77c950d7840a -r 64e07017ce01 hotspot/src/share/vm/opto/macroArrayCopy.cpp
--- a/hotspot/src/share/vm/opto/macroArrayCopy.cpp	Thu Jun 01 18:48:34 2017 +0000
+++ b/hotspot/src/share/vm/opto/macroArrayCopy.cpp	Fri Jun 02 09:08:34 2017 +0200
@@ -718,6 +718,15 @@
   _igvn.replace_node(_ioproj_fallthrough, *io);
   _igvn.replace_node(_fallthroughcatchproj, *ctrl);
 
+#ifdef ASSERT
+  const TypeOopPtr* dest_t = _igvn.type(dest)->is_oopptr();
+  if (dest_t->is_known_instance()) {
+    ArrayCopyNode* ac = NULL;
+    assert(ArrayCopyNode::may_modify(dest_t, (*ctrl)->in(0)->as_MemBar(), &_igvn, ac), "dependency on arraycopy lost");
+    assert(ac == NULL, "no arraycopy anymore");
+  }
+#endif
+
   return out_mem;
 }
 
@@ -1139,8 +1148,25 @@
   const TypeAryPtr* top_src = src_type->isa_aryptr();
   const TypeAryPtr* top_dest = dest_type->isa_aryptr();
 
-  if (top_src  == NULL || top_src->klass()  == NULL ||
-      top_dest == NULL || top_dest->klass() == NULL) {
+  BasicType src_elem = T_CONFLICT;
+  BasicType dest_elem = T_CONFLICT;
+
+  if (top_dest != NULL && top_dest->klass() != NULL) {
+    dest_elem = top_dest->klass()->as_array_klass()->element_type()->basic_type();
+  }
+  if (top_src != NULL && top_src->klass() != NULL) {
+    src_elem = top_src->klass()->as_array_klass()->element_type()->basic_type();
+  }
+  if (src_elem  == T_ARRAY)  src_elem  = T_OBJECT;
+  if (dest_elem == T_ARRAY)  dest_elem = T_OBJECT;
+
+  if (ac->is_arraycopy_validated() &&
+      dest_elem != T_CONFLICT &&
+      src_elem == T_CONFLICT) {
+    src_elem = dest_elem;
+  }
+
+  if (src_elem == T_CONFLICT || dest_elem == T_CONFLICT) {
     // Conservatively insert a memory barrier on all memory slices.
     // Do not let writes into the source float below the arraycopy.
     {
@@ -1169,13 +1195,11 @@
     }
     return;
   }
+
+  assert(!ac->is_arraycopy_validated() || (src_elem == dest_elem && dest_elem != T_VOID), "validated but different basic types");
+
   // (2) src and dest arrays must have elements of the same BasicType
   // Figure out the size and type of the elements we will be copying.
-  BasicType src_elem  = top_src->klass()->as_array_klass()->element_type()->basic_type();
-  BasicType dest_elem = top_dest->klass()->as_array_klass()->element_type()->basic_type();
-  if (src_elem  == T_ARRAY)  src_elem  = T_OBJECT;
-  if (dest_elem == T_ARRAY)  dest_elem = T_OBJECT;
-
   if (src_elem != dest_elem || dest_elem == T_VOID) {
     // The component types are not the same or are not recognized.  Punt.
     // (But, avoid the native method wrapper to JVM_ArrayCopy.)
diff -r 77c950d7840a -r 64e07017ce01 hotspot/src/share/vm/opto/memnode.cpp
--- a/hotspot/src/share/vm/opto/memnode.cpp	Thu Jun 01 18:48:34 2017 +0000
+++ b/hotspot/src/share/vm/opto/memnode.cpp	Fri Jun 02 09:08:34 2017 +0200
@@ -908,10 +908,11 @@
         ld->set_req(0, ld_alloc->in(0));
       }
     } else {
+      Node* src = ac->in(ArrayCopyNode::Src);
       Node* addp = in(MemNode::Address)->clone();
       assert(addp->in(AddPNode::Base) == addp->in(AddPNode::Address), "should be");
-      addp->set_req(AddPNode::Base, ac->in(ArrayCopyNode::Src));
-      addp->set_req(AddPNode::Address, ac->in(ArrayCopyNode::Src));
+      addp->set_req(AddPNode::Base, src);
+      addp->set_req(AddPNode::Address, src);
 
       const TypeAryPtr* ary_t = phase->type(in(MemNode::Address))->isa_aryptr();
       BasicType ary_elem  = ary_t->klass()->as_array_klass()->element_type()->basic_type();
@@ -928,6 +929,12 @@
       addp->set_req(AddPNode::Offset, offset);
       ld->set_req(MemNode::Address, phase->transform(addp));
 
+      const TypeX *ld_offs_t = phase->type(offset)->isa_intptr_t();
+
+      if (!ac->as_ArrayCopy()->can_replace_dest_load_with_src_load(ld_offs_t->_lo, ld_offs_t->_hi, phase)) {
+        return NULL;
+      }
+
       if (in(0) != NULL) {
         assert(ac->in(0) != NULL, "alloc must have control");
         ld->set_req(0, ac->in(0));
diff -r 77c950d7840a -r 64e07017ce01 hotspot/test/compiler/arraycopy/TestACSameSrcDst.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/compiler/arraycopy/TestACSameSrcDst.java	Fri Jun 02 09:08:34 2017 +0200
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2017, Red Hat, Inc. 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 8179678
+ * @summary ArrayCopy with same src and dst can cause incorrect execution or compiler crash
+ *
+ * @run main/othervm -XX:CompileCommand=compileonly,TestACSameSrcDst::test* TestACSameSrcDst
+ *
+ */
+
+public class TestACSameSrcDst {
+
+    static int test1(int[] src, int[] dst) {
+        System.arraycopy(src, 5, dst, 0, 10);
+         // this shouldn't be transformed to src[5] because the copy
+         // can modify src[5] if src and dst are the same.
+        return dst[0];
+    }
+
+    static int test2(int[] src) {
+        System.arraycopy(src, 0, src, 0, 10);
+        // same source and destination. If load from destination is
+        // transformed to load of source, the compiler performs that
+        // optimization in an infinite loop.
+        return src[0];
+    }
+
+    static int test3() {
+        int[] src = new int[15];
+        src[5] = 0x42;
+        System.arraycopy(src, 5, src, 0, 10);
+        // That load can't bypass the arraycopy
+        return src[0];
+    }
+
+    static int test4() {
+        int[] src = new int[15];
+        System.arraycopy(src, 0, src, 5, 10);
+        return src[0];
+    }
+
+    // The dst[0] load can't bypass the arraycopy. After ArrayCopyNode
+    // is expanded, C2 looks for a stub call on the control paths of
+    // the array copy subgraph to decide whether the load's memory
+    // input can bypass the arraycopy. This test verifies the case of
+    // a source array that's not declared as an array.
+    static int test5(Object src, int l, boolean flag) {
+        int[] dst = new int[10];
+        if (flag) {
+            dst[0] = 0x42;
+            System.arraycopy(src, 0, dst, 0, l);
+            return dst[0];
+        }
+        return 0;
+    }
+
+    public static void main(String[] args) {
+        int[] array = new int[15];
+        for (int i = 0; i < 20000; i++) {
+            int res;
+            for (int j = 0; j < array.length; j++) {
+                array[j] = j;
+            }
+            int expected = array[5];
+            res = test1(array, array);
+            if (res != expected) {
+                throw new RuntimeException("bad result: " + res + " != " + expected);
+            }
+            test2(array);
+            res = test3();
+            if (res != 0x42) {
+                throw new RuntimeException("bad result: " + res + " != " + 0x42);
+            }
+            test4();
+            for (int j = 0; j < array.length; j++) {
+                array[j] = j;
+            }
+            res = test5(array, 10, (i%2) == 0);
+            if (res != 0) {
+                throw new RuntimeException("bad result: " + res + " != " + 0);
+            }
+        }
+    }
+}