# HG changeset patch
# User rkennke
# Date 1488900697 -3600
#      Tue Mar 07 16:31:37 2017 +0100
# Node ID 3e1f6459e39de7e60c8213adf96ca6bdb79ef2ff
# Parent  253c4298bd492851a603ea523c2ac925c0408f7a
Implement barriers for maintaining connection matrix.

diff --git a/src/cpu/x86/vm/c1_LIRGenerator_x86.cpp b/src/cpu/x86/vm/c1_LIRGenerator_x86.cpp
--- a/src/cpu/x86/vm/c1_LIRGenerator_x86.cpp
+++ b/src/cpu/x86/vm/c1_LIRGenerator_x86.cpp
@@ -341,7 +341,7 @@
                 true /* do_load */, false /* patch */, NULL);
     __ move(val, array_addr, null_check_info);
     // Seems to be a precise
-    post_barrier(LIR_OprFact::address(array_addr), value.result());
+    post_barrier(LIR_OprFact::address(array_addr), val);
   } else {
     LIR_Opr result = maybe_mask_boolean(x, ary, val, null_check_info);
     __ move(result, array_addr, null_check_info);
diff --git a/src/cpu/x86/vm/c1_LIR_x86.cpp b/src/cpu/x86/vm/c1_LIR_x86.cpp
--- a/src/cpu/x86/vm/c1_LIR_x86.cpp
+++ b/src/cpu/x86/vm/c1_LIR_x86.cpp
@@ -60,9 +60,9 @@
 #ifndef PRODUCT
 void LIR_Address::verify() const {
 #ifdef _LP64
-  assert(base()->is_cpu_register(), "wrong base operand");
+  assert(base()->is_illegal() || base()->is_cpu_register(), "wrong base operand");
   assert(index()->is_illegal() || index()->is_double_cpu(), "wrong index operand");
-  assert(base()->type() == T_OBJECT || base()->type() == T_LONG || base()->type() == T_METADATA,
+  assert(base()->is_illegal() || base()->type() == T_OBJECT || base()->type() == T_LONG || base()->type() == T_METADATA,
          "wrong type for addresses");
 #else
   assert(base()->is_single_cpu(), "wrong base operand");
diff --git a/src/cpu/x86/vm/macroAssembler_x86.cpp b/src/cpu/x86/vm/macroAssembler_x86.cpp
--- a/src/cpu/x86/vm/macroAssembler_x86.cpp
+++ b/src/cpu/x86/vm/macroAssembler_x86.cpp
@@ -45,6 +45,7 @@
 #include "gc/g1/g1CollectedHeap.inline.hpp"
 #include "gc/g1/g1SATBCardTableModRefBS.hpp"
 #include "gc/g1/heapRegion.hpp"
+#include "gc/shenandoah/shenandoahConnectionMatrix.hpp"
 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
 #include "gc/shenandoah/shenandoahHeapRegion.hpp"
 #endif // INCLUDE_ALL_GCS
@@ -5349,6 +5350,42 @@
   bind(done);
 }
 
+void MacroAssembler::shenandoah_write_barrier_post(Register store_addr,
+                                                   Register new_val,
+                                                   Register thread,
+                                                   Register tmp,
+                                                   Register tmp2) {
+  assert(UseShenandoahGC, "why else should we be here?");
+
+  if (! UseShenandoahMatrix) {
+    // No need for that barrier if not using matrix.
+    return;
+  }
+
+  Label done;
+  testptr(new_val, new_val);
+  jcc(Assembler::zero, done);
+  ShenandoahConnectionMatrix* matrix = ShenandoahHeap::heap()->connection_matrix();
+  address matrix_addr = matrix->matrix_addr();
+  movptr(rscratch1, (intptr_t) ShenandoahHeap::heap()->first_region_bottom());
+  // Compute from-region index
+  movptr(tmp, store_addr);
+  subptr(tmp, rscratch1);
+  shrptr(tmp, ShenandoahHeapRegion::RegionSizeShift);
+  // Compute to-region index
+  movptr(tmp2, new_val);
+  subptr(tmp2, rscratch1);
+  shrptr(tmp2, ShenandoahHeapRegion::RegionSizeShift);
+  // Compute matrix index
+  imulq(tmp, tmp, matrix->stride());
+  addq(tmp, tmp2);
+  movptr(rscratch1, (intptr_t) matrix_addr);
+  // Store true at _matrix[from * stride + to]
+  //movb(Address(rscratch1, tmp, Address::times_1), 3 /*true*/);
+  movbool(Address(rscratch1, tmp, Address::times_1), true);
+  bind(done);
+}
+
 void MacroAssembler::g1_write_barrier_post(Register store_addr,
                                            Register new_val,
                                            Register thread,
@@ -5358,11 +5395,6 @@
   assert(thread == r15_thread, "must be");
 #endif // _LP64
 
-  if (UseShenandoahGC) {
-    // No need for this in Shenandoah.
-    return;
-  }
-
   assert(UseG1GC, "expect G1 GC");
 
   Address queue_index(thread, in_bytes(JavaThread::dirty_card_queue_offset() +
diff --git a/src/cpu/x86/vm/macroAssembler_x86.hpp b/src/cpu/x86/vm/macroAssembler_x86.hpp
--- a/src/cpu/x86/vm/macroAssembler_x86.hpp
+++ b/src/cpu/x86/vm/macroAssembler_x86.hpp
@@ -312,6 +312,12 @@
                              Register tmp,
                              Register tmp2);
 
+  void shenandoah_write_barrier_post(Register store_addr,
+                                     Register new_val,
+                                     Register thread,
+                                     Register tmp,
+                                     Register tmp2);
+
   void shenandoah_write_barrier(Register dst);
 
 #endif // INCLUDE_ALL_GCS
diff --git a/src/cpu/x86/vm/templateTable_x86.cpp b/src/cpu/x86/vm/templateTable_x86.cpp
--- a/src/cpu/x86/vm/templateTable_x86.cpp
+++ b/src/cpu/x86/vm/templateTable_x86.cpp
@@ -182,21 +182,31 @@
         if (val == noreg) {
           __ store_heap_oop_null(Address(rdx, 0));
         } else {
+          // For Shenandoah, make sure we only store refs into to-space.
+          oopDesc::bs()->interpreter_read_barrier(_masm, val);
+
           // G1 barrier needs uncompressed oop for region cross check.
           Register new_val = val;
           if (UseCompressedOops) {
             new_val = rbx;
             __ movptr(new_val, val);
           }
-          // For Shenandoah, make sure we only store refs into to-space.
-          oopDesc::bs()->interpreter_read_barrier(_masm, val);
 
           __ store_heap_oop(Address(rdx, 0), val);
-          __ g1_write_barrier_post(rdx /* store_adr */,
-                                   new_val /* new_val */,
-                                   rthread /* thread */,
-                                   rtmp /* tmp */,
-                                   rbx /* tmp2 */);
+          if (UseG1GC) {
+            __ g1_write_barrier_post(rdx /* store_adr */,
+                                     new_val /* new_val */,
+                                     rthread /* thread */,
+                                     rtmp /* tmp */,
+                                     rbx /* tmp2 */);
+          } else {
+            assert(UseShenandoahGC, "sanity");
+            __ shenandoah_write_barrier_post(rdx /* store_adr */,
+                                             new_val /* new_val */,
+                                             rthread /* thread */,
+                                             rtmp /* tmp */,
+                                             rbx /* tmp2 */);
+          }
         }
         NOT_LP64( __ restore_bcp());
       }
diff --git a/src/share/vm/c1/c1_LIRGenerator.cpp b/src/share/vm/c1/c1_LIRGenerator.cpp
--- a/src/share/vm/c1/c1_LIRGenerator.cpp
+++ b/src/share/vm/c1/c1_LIRGenerator.cpp
@@ -43,6 +43,9 @@
 #include "utilities/macros.hpp"
 #if INCLUDE_ALL_GCS
 #include "gc/g1/heapRegion.hpp"
+#include "gc/shenandoah/shenandoahConnectionMatrix.hpp"
+#include "gc/shenandoah/shenandoahHeap.hpp"
+#include "gc/shenandoah/shenandoahHeapRegion.hpp"
 #endif // INCLUDE_ALL_GCS
 #ifdef TRACE_HAVE_INTRINSICS
 #include "trace/traceMacros.hpp"
@@ -1487,6 +1490,7 @@
       G1SATBCardTableModRef_post_barrier(addr,  new_val);
       break;
     case BarrierSet::ShenandoahBarrierSet:
+      Shenandoah_post_barrier(addr,  new_val);
       break;
 #endif // INCLUDE_ALL_GCS
     case BarrierSet::CardTableForRS:
@@ -1620,6 +1624,69 @@
   __ branch_destination(slow->continuation());
 }
 
+void LIRGenerator::Shenandoah_post_barrier(LIR_OprDesc* addr, LIR_OprDesc* new_val) {
+  if (! UseShenandoahMatrix) {
+    // No need for that barrier if not using matrix.
+    return;
+  }
+
+  // If the "new_val" is a constant NULL, no barrier is necessary.
+  if (new_val->is_constant() &&
+      new_val->as_constant_ptr()->as_jobject() == NULL) return;
+
+  if (!new_val->is_register()) {
+    LIR_Opr new_val_reg = new_register(T_OBJECT);
+    if (new_val->is_constant()) {
+      __ move(new_val, new_val_reg);
+    } else {
+      __ leal(new_val, new_val_reg);
+    }
+    new_val = new_val_reg;
+  }
+  assert(new_val->is_register(), "must be a register at this point");
+
+  if (addr->is_address()) {
+    LIR_Address* address = addr->as_address_ptr();
+    LIR_Opr ptr = new_pointer_register();
+    if (!address->index()->is_valid() && address->disp() == 0) {
+      __ move(address->base(), ptr);
+    } else {
+      assert(address->disp() != max_jint, "lea doesn't support patched addresses!");
+      __ leal(addr, ptr);
+    }
+    addr = ptr;
+  }
+  assert(addr->is_register(), "must be a register at this point");
+
+  LabelObj* L_done = new LabelObj();
+  __ cmp(lir_cond_equal, new_val, LIR_OprFact::oopConst(NULL_WORD));
+  __ branch(lir_cond_equal, T_OBJECT, L_done->label());
+
+  ShenandoahConnectionMatrix* matrix = ShenandoahHeap::heap()->connection_matrix();
+
+  LIR_Opr tmp1 = new_pointer_register();
+  //LIR_Address* first_region_bottom = new LIR_Address(LIR_OprDesc::illegalOpr(), (intx) , T_ADDRESS);
+  __ move(addr, tmp1);
+  __ sub(tmp1, LIR_OprFact::intptrConst(ShenandoahHeap::heap()->first_region_bottom()), tmp1);
+  __ unsigned_shift_right(tmp1, LIR_OprFact::intConst(ShenandoahHeapRegion::RegionSizeShift), tmp1, LIR_OprDesc::illegalOpr());
+
+  LIR_Opr tmp2 = new_pointer_register();
+  __ move(new_val, tmp2);
+  __ sub(tmp2, LIR_OprFact::intptrConst(ShenandoahHeap::heap()->first_region_bottom()), tmp2);
+  __ unsigned_shift_right(tmp2, LIR_OprFact::intConst(ShenandoahHeapRegion::RegionSizeShift), tmp2, LIR_OprDesc::illegalOpr());
+
+  LIR_Opr tmp3 = new_pointer_register();
+  __ move(LIR_OprFact::longConst(matrix->stride()), tmp3);
+  __ mul(tmp1, tmp3, tmp1);
+  __ add(tmp1, tmp2, tmp1);
+
+  LIR_Opr tmp4 = new_pointer_register();
+  __ move(LIR_OprFact::intptrConst((intptr_t) matrix->matrix_addr()), tmp4);
+  LIR_Address* matrix_elem_addr = new LIR_Address(tmp4, tmp1, T_BOOLEAN);
+  __ move(LIR_OprFact::intConst((int) true), matrix_elem_addr);
+  __ branch_destination(L_done->label());
+}
+
 #endif // INCLUDE_ALL_GCS
 ////////////////////////////////////////////////////////////////////////
 
diff --git a/src/share/vm/c1/c1_LIRGenerator.hpp b/src/share/vm/c1/c1_LIRGenerator.hpp
--- a/src/share/vm/c1/c1_LIRGenerator.hpp
+++ b/src/share/vm/c1/c1_LIRGenerator.hpp
@@ -286,6 +286,7 @@
   // post barriers
 
   void G1SATBCardTableModRef_post_barrier(LIR_OprDesc* addr, LIR_OprDesc* new_val);
+  void Shenandoah_post_barrier(LIR_OprDesc* addr, LIR_OprDesc* new_val);
   void CardTableModRef_post_barrier(LIR_OprDesc* addr, LIR_OprDesc* new_val);
 #ifdef CARDTABLEMODREF_POST_BARRIER_HELPER
   void CardTableModRef_post_barrier_helper(LIR_OprDesc* addr, LIR_Const* card_table_base);
diff --git a/src/share/vm/gc/shared/referenceProcessor.cpp b/src/share/vm/gc/shared/referenceProcessor.cpp
--- a/src/share/vm/gc/shared/referenceProcessor.cpp
+++ b/src/share/vm/gc/shared/referenceProcessor.cpp
@@ -326,7 +326,11 @@
     assert(java_lang_ref_Reference::next(obj) == NULL,
            "Reference not active; should not be discovered");
     // Self-loop next, so as to make Ref not active.
-    java_lang_ref_Reference::set_next_raw(obj, obj);
+    if (UseShenandoahGC && UseShenandoahMatrix) {
+      java_lang_ref_Reference::set_next(obj, obj);
+    } else {
+      java_lang_ref_Reference::set_next_raw(obj, obj);
+    }
     if (! oopDesc::safe_equals(next_d, obj)) {
       oopDesc::bs()->write_ref_field(java_lang_ref_Reference::discovered_addr(obj), next_d);
     } else {
@@ -895,7 +899,7 @@
   oop next_discovered = (current_head != NULL) ? current_head : obj;
 
   oop retest = oopDesc::atomic_compare_exchange_oop(next_discovered, discovered_addr,
-                                                    NULL);
+                                                    NULL, UseShenandoahGC && UseShenandoahMatrix);
   if (retest == NULL) {
     // This thread just won the right to enqueue the object.
     // We have separate lists for enqueueing, so no synchronization
diff --git a/src/share/vm/gc/shenandoah/shenandoahBarrierSet.cpp b/src/share/vm/gc/shenandoah/shenandoahBarrierSet.cpp
--- a/src/share/vm/gc/shenandoah/shenandoahBarrierSet.cpp
+++ b/src/share/vm/gc/shenandoah/shenandoahBarrierSet.cpp
@@ -24,6 +24,7 @@
 #include "precompiled.hpp"
 #include "gc/g1/g1SATBCardTableModRefBS.hpp"
 #include "gc/shenandoah/shenandoahBarrierSet.hpp"
+#include "gc/shenandoah/shenandoahConnectionMatrix.hpp"
 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
 #include "runtime/interfaceSupport.hpp"
 
@@ -50,6 +51,32 @@
 
 };
 
+class UpdateRefsForOopMatrixClosure: public ExtendedOopClosure {
+
+private:
+  ShenandoahHeap* _heap;
+  template <class T>
+  inline void do_oop_work(T* p) {
+    oop o = _heap->maybe_update_oop_ref(p);
+    if (! oopDesc::is_null(o)) {
+      _heap->connection_matrix()->set_connected(_heap->heap_region_index_containing(p), _heap->heap_region_index_containing(o), true);
+    }
+  }
+public:
+  UpdateRefsForOopMatrixClosure() {
+    _heap = ShenandoahHeap::heap();
+  }
+
+  void do_oop(oop* p)       {
+    do_oop_work(p);
+  }
+
+  void do_oop(narrowOop* p) {
+    do_oop_work(p);
+  }
+
+};
+
 ShenandoahBarrierSet::ShenandoahBarrierSet(ShenandoahHeap* heap) :
   BarrierSet(BarrierSet::FakeRtti(BarrierSet::ShenandoahBarrierSet)),
   _heap(heap)
@@ -160,7 +187,7 @@
 }
 
 bool ShenandoahBarrierSet::need_update_refs_barrier() {
-  return _heap->concurrent_mark_in_progress() && _heap->need_update_refs();
+  return UseShenandoahMatrix || (_heap->concurrent_mark_in_progress() && _heap->need_update_refs());
 }
 
 void ShenandoahBarrierSet::write_ref_array_work(MemRegion r) {
@@ -169,15 +196,24 @@
 
 void ShenandoahBarrierSet::write_ref_array(HeapWord* start, size_t count) {
   if (! need_update_refs_barrier()) return;
+  ShenandoahHeap* heap = ShenandoahHeap::heap();
+  ShenandoahConnectionMatrix* matrix = heap->connection_matrix();
+  // TODO: Use templated loop and split on oop/narrowOop and UseShenandoahMatrix.
   if (UseCompressedOops) {
     narrowOop* dst = (narrowOop*) start;
     for (size_t i = 0; i < count; i++, dst++) {
-      _heap->maybe_update_oop_ref(dst);
+      oop o = _heap->maybe_update_oop_ref(dst);
+      if (UseShenandoahMatrix && ! oopDesc::is_null(o)) {
+        matrix->set_connected(heap->heap_region_index_containing(dst), heap->heap_region_index_containing(o), true);
+      }
     }
   } else {
     oop* dst = (oop*) start;
     for (size_t i = 0; i < count; i++, dst++) {
-      _heap->maybe_update_oop_ref(dst);
+      oop o = _heap->maybe_update_oop_ref(dst);
+      if (UseShenandoahMatrix && ! oopDesc::is_null(o)) {
+        matrix->set_connected(heap->heap_region_index_containing(dst), heap->heap_region_index_containing(o), true);
+      }
     }
   }
 }
@@ -218,11 +254,12 @@
 }
 
 template <class T>
-void ShenandoahBarrierSet::write_ref_field_pre_static(T* field, oop newVal) {
+void ShenandoahBarrierSet::write_ref_field_pre_static(T* field, oop new_val) {
   T heap_oop = oopDesc::load_heap_oop(field);
 
 #ifdef ASSERT
-  ShenandoahHeap* heap = ShenandoahHeap::heap();
+  {
+    ShenandoahHeap* heap = ShenandoahHeap::heap();
     if (heap->is_in(field) &&
         heap->in_collection_set(field) &&
         ! heap->cancelled_concgc()) {
@@ -234,11 +271,17 @@
                     BOOL_TO_STR(heap->is_evacuation_in_progress()));
       assert(false, "We should have fixed this earlier");
     }
+  }
 #endif
 
   if (!oopDesc::is_null(heap_oop)) {
     G1SATBCardTableModRefBS::enqueue(oopDesc::decode_heap_oop(heap_oop));
   }
+  if (UseShenandoahMatrix && ! oopDesc::is_null(new_val)) {
+    ShenandoahHeap* heap = ShenandoahHeap::heap();
+    ShenandoahConnectionMatrix* matrix = heap->connection_matrix();
+    matrix->set_connected(heap->heap_region_index_containing(field), heap->heap_region_index_containing(new_val), true);
+  }
 }
 
 template <class T>
@@ -268,10 +311,16 @@
     ShenandoahHeap::heap()->heap_region_containing(v)->print();
   }
   assert(heap->cancelled_concgc() || !heap->in_collection_set(v), "only write to to-space");
-  if (! need_update_refs_barrier()) return;
-  assert(o == NULL || oopDesc::unsafe_equals(o, resolve_oop_static(o)), "only write to-space values");
-  assert(o == NULL || !heap->in_collection_set(o), "only write to-space values");
+  if (_heap->concurrent_mark_in_progress()) {
+    assert(o == NULL || oopDesc::unsafe_equals(o, resolve_oop_static(o)), "only write to-space values");
+    assert(o == NULL || !heap->in_collection_set(o), "only write to-space values");
+  }
 #endif
+  if (UseShenandoahMatrix && ! oopDesc::is_null(o)) {
+    ShenandoahHeap* heap = ShenandoahHeap::heap();
+    ShenandoahConnectionMatrix* matrix = heap->connection_matrix();
+    matrix->set_connected(heap->heap_region_index_containing(v), heap->heap_region_index_containing(o), true);
+  }
 }
 
 void ShenandoahBarrierSet::write_region_work(MemRegion mr) {
@@ -285,8 +334,13 @@
 
   oop obj = oop(mr.start());
   assert(obj->is_oop(), "must be an oop");
-  UpdateRefsForOopClosure cl;
-  obj->oop_iterate(&cl);
+  if (UseShenandoahMatrix) {
+    UpdateRefsForOopMatrixClosure cl;
+    obj->oop_iterate(&cl);
+  } else {
+    UpdateRefsForOopClosure cl;
+    obj->oop_iterate(&cl);
+  }
 }
 
 oop ShenandoahBarrierSet::read_barrier(oop src) {
diff --git a/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.cpp b/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.cpp
--- a/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.cpp
+++ b/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.cpp
@@ -50,7 +50,7 @@
 
   template <class T>
   inline void do_oop_nv(T* p) {
-    ShenandoahConcurrentMark::mark_through_ref<T, RESOLVE>(p, _heap, _queue);
+    ShenandoahConcurrentMark::mark_through_ref<T, RESOLVE, false>(p, _heap, _queue, NULL);
   }
 
 public:
@@ -64,7 +64,8 @@
 ShenandoahMarkRefsSuperClosure::ShenandoahMarkRefsSuperClosure(SCMObjToScanQueue* q, ReferenceProcessor* rp) :
   MetadataAwareOopClosure(rp),
   _queue(q),
-  _heap((ShenandoahHeap*) Universe::heap())
+  _heap(ShenandoahHeap::heap()),
+  _conn_matrix(ShenandoahHeap::heap()->connection_matrix())
 {
 }
 
@@ -189,7 +190,8 @@
                    true, // drain SATBs as we go
                    true, // count liveness
                    _cm->unload_classes(),
-                   _update_refs);
+                   _update_refs,
+                   UseShenandoahMatrix);
   }
 };
 
@@ -226,7 +228,8 @@
                    false, // do not drain SATBs, already drained
                    _count_live,
                    _unload_classes,
-                   _update_refs);
+                   _update_refs,
+                   UseShenandoahMatrix);
 
     assert(_cm->task_queues()->is_empty(), "Should be empty");
   }
@@ -614,7 +617,8 @@
                    false, // do not drain SATBs
                    true,  // count liveness
                    scm->unload_classes(),
-                   sh->need_update_refs());
+                   sh->need_update_refs(),
+                   UseShenandoahMatrix);
   }
 };
 
@@ -626,12 +630,12 @@
 
   template <class T>
   inline void do_oop_nv(T* p) {
-    ShenandoahConcurrentMark::mark_through_ref<T, NONE>(p, _heap, _queue);
+    ShenandoahConcurrentMark::mark_through_ref<T, NONE, false>(p, _heap, _queue, NULL);
   }
 
 public:
   ShenandoahCMKeepAliveClosure(SCMObjToScanQueue* q) :
-    _queue(q), _heap(ShenandoahHeap::heap()) {};
+    _queue(q), _heap(ShenandoahHeap::heap()) {}
 
   void do_oop(narrowOop* p) { do_oop_nv(p); }
   void do_oop(oop* p)       { do_oop_nv(p); }
@@ -644,12 +648,52 @@
 
   template <class T>
   inline void do_oop_nv(T* p) {
-    ShenandoahConcurrentMark::mark_through_ref<T, SIMPLE>(p, _heap, _queue);
+    ShenandoahConcurrentMark::mark_through_ref<T, SIMPLE, false>(p, _heap, _queue, NULL);
   }
 
 public:
   ShenandoahCMKeepAliveUpdateClosure(SCMObjToScanQueue* q) :
-    _queue(q), _heap(ShenandoahHeap::heap()) {};
+    _queue(q), _heap(ShenandoahHeap::heap()) {}
+
+  void do_oop(narrowOop* p) { do_oop_nv(p); }
+  void do_oop(oop* p)       { do_oop_nv(p); }
+};
+
+class ShenandoahCMKeepAliveMatrixClosure : public OopClosure {
+private:
+  SCMObjToScanQueue* _queue;
+  ShenandoahHeap* _heap;
+  ShenandoahConnectionMatrix* _conn_matrix;
+
+  template <class T>
+  inline void do_oop_nv(T* p) {
+    ShenandoahConcurrentMark::mark_through_ref<T, NONE, true>(p, _heap, _queue, _conn_matrix);
+  }
+
+public:
+  ShenandoahCMKeepAliveMatrixClosure(SCMObjToScanQueue* q) :
+    _queue(q), _heap(ShenandoahHeap::heap()),
+    _conn_matrix(ShenandoahHeap::heap()->connection_matrix()) {};
+
+  void do_oop(narrowOop* p) { do_oop_nv(p); }
+  void do_oop(oop* p)       { do_oop_nv(p); }
+};
+
+class ShenandoahCMKeepAliveUpdateMatrixClosure : public OopClosure {
+private:
+  SCMObjToScanQueue* _queue;
+  ShenandoahHeap* _heap;
+  ShenandoahConnectionMatrix* _conn_matrix;
+
+  template <class T>
+  inline void do_oop_nv(T* p) {
+    ShenandoahConcurrentMark::mark_through_ref<T, SIMPLE, true>(p, _heap, _queue, _conn_matrix);
+  }
+
+public:
+  ShenandoahCMKeepAliveUpdateMatrixClosure(SCMObjToScanQueue* q) :
+    _queue(q), _heap(ShenandoahHeap::heap()),
+    _conn_matrix(ShenandoahHeap::heap()->connection_matrix()) {};
 
   void do_oop(narrowOop* p) { do_oop_nv(p); }
   void do_oop(oop* p)       { do_oop_nv(p); }
@@ -674,12 +718,22 @@
     ShenandoahHeap* heap = ShenandoahHeap::heap();
     ShenandoahForwardedIsAliveClosure is_alive;
     ShenandoahCMDrainMarkingStackClosure complete_gc(worker_id, _terminator);
-    if (heap->need_update_refs()) {
-      ShenandoahCMKeepAliveUpdateClosure keep_alive(heap->concurrentMark()->get_queue(worker_id));
-      _proc_task.work(worker_id, is_alive, keep_alive, complete_gc);
+    if (UseShenandoahMatrix) {
+      if (heap->need_update_refs()) {
+        ShenandoahCMKeepAliveUpdateMatrixClosure keep_alive(heap->concurrentMark()->get_queue(worker_id));
+        _proc_task.work(worker_id, is_alive, keep_alive, complete_gc);
+      } else {
+        ShenandoahCMKeepAliveMatrixClosure keep_alive(heap->concurrentMark()->get_queue(worker_id));
+        _proc_task.work(worker_id, is_alive, keep_alive, complete_gc);
+      }
     } else {
-      ShenandoahCMKeepAliveClosure keep_alive(heap->concurrentMark()->get_queue(worker_id));
-      _proc_task.work(worker_id, is_alive, keep_alive, complete_gc);
+      if (heap->need_update_refs()) {
+        ShenandoahCMKeepAliveUpdateClosure keep_alive(heap->concurrentMark()->get_queue(worker_id));
+        _proc_task.work(worker_id, is_alive, keep_alive, complete_gc);
+      } else {
+        ShenandoahCMKeepAliveClosure keep_alive(heap->concurrentMark()->get_queue(worker_id));
+        _proc_task.work(worker_id, is_alive, keep_alive, complete_gc);
+      }
     }
   }
 };
@@ -816,7 +870,7 @@
   q->clear_buffer();
 }
 
-template <bool CANCELLABLE, bool DRAIN_SATB, bool COUNT_LIVENESS, bool CLASS_UNLOAD, bool UPDATE_REFS>
+template <bool CANCELLABLE, bool DRAIN_SATB, bool COUNT_LIVENESS, bool CLASS_UNLOAD, bool UPDATE_REFS, bool UPDATE_MATRIX>
 void ShenandoahConcurrentMark::mark_loop_prework(uint w, ParallelTaskTerminator *t, ReferenceProcessor *rp) {
   SCMObjToScanQueue* q = get_queue(w);
 
@@ -830,24 +884,43 @@
 
   // TODO: We can clean up this if we figure out how to do templated oop closures that
   // play nice with specialized_oop_iterators.
-  if (CLASS_UNLOAD) {
-    if (UPDATE_REFS) {
-      ShenandoahMarkUpdateRefsMetadataClosure cl(q, rp);
-      mark_loop_work<ShenandoahMarkUpdateRefsMetadataClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+  if (UPDATE_MATRIX) {
+    if (CLASS_UNLOAD) {
+      if (UPDATE_REFS) {
+        ShenandoahMarkUpdateRefsMetadataMatrixClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkUpdateRefsMetadataMatrixClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      } else {
+        ShenandoahMarkRefsMetadataMatrixClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkRefsMetadataMatrixClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      }
     } else {
-      ShenandoahMarkRefsMetadataClosure cl(q, rp);
-      mark_loop_work<ShenandoahMarkRefsMetadataClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      if (UPDATE_REFS) {
+        ShenandoahMarkUpdateRefsMatrixClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkUpdateRefsMatrixClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      } else {
+        ShenandoahMarkRefsMatrixClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkRefsMatrixClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      }
     }
   } else {
-    if (UPDATE_REFS) {
-      ShenandoahMarkUpdateRefsClosure cl(q, rp);
-      mark_loop_work<ShenandoahMarkUpdateRefsClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+    if (CLASS_UNLOAD) {
+      if (UPDATE_REFS) {
+        ShenandoahMarkUpdateRefsMetadataClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkUpdateRefsMetadataClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      } else {
+        ShenandoahMarkRefsMetadataClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkRefsMetadataClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      }
     } else {
-      ShenandoahMarkRefsClosure cl(q, rp);
-      mark_loop_work<ShenandoahMarkRefsClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      if (UPDATE_REFS) {
+        ShenandoahMarkUpdateRefsClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkUpdateRefsClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      } else {
+        ShenandoahMarkRefsClosure cl(q, rp);
+        mark_loop_work<ShenandoahMarkRefsClosure, CANCELLABLE, DRAIN_SATB, COUNT_LIVENESS>(&cl, ld, w, t);
+      }
     }
   }
-
   if (COUNT_LIVENESS) {
     for (uint i = 0; i < _heap->max_regions(); i++) {
       ShenandoahHeapRegion *r = _heap->regions()->get(i);
diff --git a/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.hpp b/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.hpp
--- a/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.hpp
@@ -84,44 +84,53 @@
   template <class T, bool CANCELLABLE, bool DRAIN_SATB, bool COUNT_LIVENESS>
   void mark_loop_work(T* cl, jushort* live_data, uint worker_id, ParallelTaskTerminator *t);
 
-  template <bool CANCELLABLE, bool DRAIN_SATB, bool COUNT_LIVENESS, bool CLASS_UNLOAD, bool UPDATE_REFS>
+  template <bool CANCELLABLE, bool DRAIN_SATB, bool COUNT_LIVENESS, bool CLASS_UNLOAD, bool UPDATE_REFS, bool UPDATE_MATRIX>
   void mark_loop_prework(uint worker_id, ParallelTaskTerminator *terminator, ReferenceProcessor *rp);
 
   // ------------------------ Currying dynamic arguments to template args ----------------------------
 
+  template <bool B1, bool B2, bool B3, bool B4, bool B5>
+  void mark_loop_5(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b6) {
+    if (b6) {
+      mark_loop_prework<B1, B2, B3, B4, B5, true>(w, t, rp);
+    } else {
+      mark_loop_prework<B1, B2, B3, B4, B5, false>(w, t, rp);
+    }
+  };
+
   template <bool B1, bool B2, bool B3, bool B4>
-  void mark_loop_4(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b5) {
+  void mark_loop_4(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b5, bool b6) {
     if (b5) {
-      mark_loop_prework<B1, B2, B3, B4, true>(w, t, rp);
+      mark_loop_5<B1, B2, B3, B4, true>(w, t, rp, b6);
     } else {
-      mark_loop_prework<B1, B2, B3, B4, false>(w, t, rp);
+      mark_loop_5<B1, B2, B3, B4, false>(w, t, rp, b6);
     }
   };
 
   template <bool B1, bool B2, bool B3>
-  void mark_loop_3(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b4, bool b5) {
+  void mark_loop_3(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b4, bool b5, bool b6) {
     if (b4) {
-      mark_loop_4<B1, B2, B3, true>(w, t, rp, b5);
+      mark_loop_4<B1, B2, B3, true>(w, t, rp, b5, b6);
     } else {
-      mark_loop_4<B1, B2, B3, false>(w, t, rp, b5);
+      mark_loop_4<B1, B2, B3, false>(w, t, rp, b5, b6);
     }
   };
 
   template <bool B1, bool B2>
-  void mark_loop_2(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b3, bool b4, bool b5) {
+  void mark_loop_2(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b3, bool b4, bool b5, bool b6) {
     if (b3) {
-      mark_loop_3<B1, B2, true>(w, t, rp, b4, b5);
+      mark_loop_3<B1, B2, true>(w, t, rp, b4, b5, b6);
     } else {
-      mark_loop_3<B1, B2, false>(w, t, rp, b4, b5);
+      mark_loop_3<B1, B2, false>(w, t, rp, b4, b5, b6);
     }
   };
 
   template <bool B1>
-  void mark_loop_1(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b2, bool b3, bool b4, bool b5) {
+  void mark_loop_1(uint w, ParallelTaskTerminator* t, ReferenceProcessor* rp, bool b2, bool b3, bool b4, bool b5, bool b6) {
     if (b2) {
-      mark_loop_2<B1, true>(w, t, rp, b3, b4, b5);
+      mark_loop_2<B1, true>(w, t, rp, b3, b4, b5, b6);
     } else {
-      mark_loop_2<B1, false>(w, t, rp, b3, b4, b5);
+      mark_loop_2<B1, false>(w, t, rp, b3, b4, b5, b6);
     }
   };
 
@@ -140,8 +149,8 @@
   bool claim_codecache();
   void clear_claim_codecache();
 
-  template<class T, UpdateRefsMode UPDATE_REFS>
-  static inline void mark_through_ref(T* p, ShenandoahHeap* heap, SCMObjToScanQueue* q);
+  template<class T, UpdateRefsMode UPDATE_REFS, bool UPDATE_MATRIX>
+  static inline void mark_through_ref(T* p, ShenandoahHeap* heap, SCMObjToScanQueue* q, ShenandoahConnectionMatrix* conn_matrix);
 
   void mark_from_roots();
 
@@ -159,11 +168,12 @@
   // Mark loop entry.
   // Translates dynamic arguments to template parameters with progressive currying.
   void mark_loop(uint worker_id, ParallelTaskTerminator* terminator, ReferenceProcessor *rp,
-                 bool cancellable, bool drain_satb, bool count_liveness, bool class_unload, bool update_refs) {
+                 bool cancellable, bool drain_satb, bool count_liveness, bool class_unload,
+                 bool update_refs, bool update_matrix) {
     if (cancellable) {
-      mark_loop_1<true>(worker_id, terminator, rp, drain_satb, count_liveness, class_unload, update_refs);
+      mark_loop_1<true>(worker_id, terminator, rp, drain_satb, count_liveness, class_unload, update_refs, update_matrix);
     } else {
-      mark_loop_1<false>(worker_id, terminator, rp, drain_satb, count_liveness, class_unload, update_refs);
+      mark_loop_1<false>(worker_id, terminator, rp, drain_satb, count_liveness, class_unload, update_refs, update_matrix);
     }
   }
 
diff --git a/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.inline.hpp b/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.inline.hpp
--- a/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.inline.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoahConcurrentMark.inline.hpp
@@ -206,7 +206,7 @@
   void do_buffer(void** buffer, size_t size) {
     for (size_t i = 0; i < size; ++i) {
       oop* p = (oop*) &buffer[i];
-      ShenandoahConcurrentMark::mark_through_ref<oop, RESOLVE>(p, _heap, _queue);
+      ShenandoahConcurrentMark::mark_through_ref<oop, RESOLVE, false>(p, _heap, _queue, NULL);
     }
   }
 };
@@ -218,8 +218,8 @@
   return had_refs && try_queue(q, task);
 }
 
-template<class T, UpdateRefsMode UPDATE_REFS>
-inline void ShenandoahConcurrentMark::mark_through_ref(T *p, ShenandoahHeap* heap, SCMObjToScanQueue* q) {
+template<class T, UpdateRefsMode UPDATE_REFS, bool UPDATE_MATRIX>
+inline void ShenandoahConcurrentMark::mark_through_ref(T *p, ShenandoahHeap* heap, SCMObjToScanQueue* q, ShenandoahConnectionMatrix* conn_matrix) {
   T o = oopDesc::load_heap_oop(p);
   if (! oopDesc::is_null(o)) {
     oop obj = oopDesc::decode_heap_oop_not_null(o);
@@ -248,6 +248,15 @@
       assert(!oopDesc::is_null(obj), "Must not be null here");
       assert(heap->is_in(obj), "We shouldn't be calling this on objects not in the heap: " PTR_FORMAT, p2i(obj));
       assert(oopDesc::bs()->is_safe(obj), "Only mark objects in from-space");
+
+      if (UPDATE_MATRIX) {
+        if (heap->is_in_reserved(p)) { // Could also be in CLD, when marking through metadata.
+          uint from_idx = heap->heap_region_index_containing(p);
+          uint to_idx = heap->heap_region_index_containing(obj);
+          conn_matrix->set_connected(from_idx, to_idx, true);
+        }
+      }
+
       if (heap->mark_next(obj)) {
         log_develop_trace(gc, marking)("Marked obj: " PTR_FORMAT, p2i((HeapWord*) obj));
 
diff --git a/src/share/vm/gc/shenandoah/shenandoahConnectionMatrix.cpp b/src/share/vm/gc/shenandoah/shenandoahConnectionMatrix.cpp
new file mode 100644
--- /dev/null
+++ b/src/share/vm/gc/shenandoah/shenandoahConnectionMatrix.cpp
@@ -0,0 +1,88 @@
+/*
+ * Copyright (c) 2017, Red Hat, Inc. and/or its affiliates.
+ *
+ * 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.
+ *
+ */
+
+#include "gc/shenandoah/shenandoahConnectionMatrix.hpp"
+#include "gc/shenandoah/shenandoahHeap.hpp"
+#include "gc/shenandoah/shenandoahHeapRegion.hpp"
+#include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
+#include "memory/allocation.inline.hpp"
+#include "utilities/copy.hpp"
+
+ShenandoahConnectionMatrix::ShenandoahConnectionMatrix(uint max_regions) :
+  _stride(max_regions),
+  _matrix(NEW_C_HEAP_ARRAY(bool, max_regions * max_regions, mtGC))
+{
+  clear_all();
+}
+
+ShenandoahConnectionMatrix::~ShenandoahConnectionMatrix() {
+  FREE_C_HEAP_ARRAY(bool, _matrix);
+}
+
+size_t ShenandoahConnectionMatrix::index_of(uint from_idx, uint to_idx) const {
+  return from_idx * _stride + to_idx;
+}
+
+bool ShenandoahConnectionMatrix::is_connected(uint from_idx, uint to_idx) const {
+  return _matrix[index_of(from_idx, to_idx)];
+}
+
+void ShenandoahConnectionMatrix::set_connected(uint from_idx, uint to_idx, bool connected) {
+  _matrix[index_of(from_idx, to_idx)] = connected;
+}
+
+void ShenandoahConnectionMatrix::clear_region(uint idx) {
+  for (uint i = 0; i < _stride; i++) {
+    set_connected(i, idx, false);
+    set_connected(idx, i, false);
+  }
+}
+
+void ShenandoahConnectionMatrix::clear_all() {
+  size_t count = sizeof(bool) * _stride * _stride;
+  Copy::fill_to_bytes(_matrix, count, 0);
+}
+
+void ShenandoahConnectionMatrix::print_on(outputStream* st) const {
+  ShenandoahHeap* heap = ShenandoahHeap::heap();
+  uint num_regions = heap->num_regions();
+  for (uint from_idx = 0; from_idx < num_regions; from_idx++) {
+    ShenandoahHeapRegion* r = heap->regions()->get(from_idx);
+    if (! r->is_empty()) {
+      uint count = 0;
+      for (uint to_idx = 0; to_idx < _stride; to_idx++) {
+        if (is_connected(to_idx, from_idx)) {
+          count++;
+        }
+      }
+
+      st->print("Region %u (live: "SIZE_FORMAT", used: "SIZE_FORMAT", garbage: "SIZE_FORMAT") is referenced by %u regions: {", from_idx, r->get_live_data_bytes(), r->used(), r->garbage(), count);
+      for (uint to_idx = 0; to_idx < _stride; to_idx++) {
+        if (is_connected(to_idx, from_idx)) {
+          st->print("%u, ", to_idx);
+        }
+      }
+      st->print_cr("}");
+    }
+  }
+}
diff --git a/src/share/vm/gc/shenandoah/shenandoahConnectionMatrix.hpp b/src/share/vm/gc/shenandoah/shenandoahConnectionMatrix.hpp
new file mode 100644
--- /dev/null
+++ b/src/share/vm/gc/shenandoah/shenandoahConnectionMatrix.hpp
@@ -0,0 +1,52 @@
+/*
+ * Copyright (c) 2017, Red Hat, Inc. and/or its affiliates.
+ *
+ * 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.
+ *
+ */
+
+#ifndef SHARE_VM_GC_SHENANDOAH_SHENANDOAHCONNECTIONMATRIX_HPP
+#define SHARE_VM_GC_SHENANDOAH_SHENANDOAHCONNECTIONMATRIX_HPP
+
+#include "memory/allocation.hpp"
+
+class ShenandoahConnectionMatrix : public CHeapObj<mtGC> {
+private:
+  const uint _stride;
+  bool* _matrix;
+
+  size_t index_of(uint from_idx, uint to_idx) const;
+
+public:
+  ShenandoahConnectionMatrix(uint max_regions);
+
+  ~ShenandoahConnectionMatrix();
+
+  bool is_connected(uint from_idx, uint to_idx) const;
+
+  void set_connected(uint from_idx, uint to_idx, bool connected);
+  void clear_region(uint idx);
+  void clear_all();
+
+  address matrix_addr() { return (address) _matrix; }
+  uint stride() { return _stride; }
+  void print_on(outputStream* st) const;
+};
+
+#endif // SHARE_VM_GC_SHENANDOAH_SHENANDOAHCONNECTIONMATRIX_HPP
diff --git a/src/share/vm/gc/shenandoah/shenandoahHeap.cpp b/src/share/vm/gc/shenandoah/shenandoahHeap.cpp
--- a/src/share/vm/gc/shenandoah/shenandoahHeap.cpp
+++ b/src/share/vm/gc/shenandoah/shenandoahHeap.cpp
@@ -263,6 +263,8 @@
   _mark_bit_map1.initialize(heap_region, bitmap_region1);
   _next_mark_bit_map = &_mark_bit_map1;
 
+  _connection_matrix = new ShenandoahConnectionMatrix(_max_regions);
+
   _monitoring_support = new ShenandoahMonitoringSupport(this);
 
   _concurrent_gc_thread = new ShenandoahConcurrentThread();
@@ -295,6 +297,7 @@
   _complete_top_at_mark_starts_base(NULL),
   _mark_bit_map0(),
   _mark_bit_map1(),
+  _connection_matrix(NULL),
   _cancelled_concgc(false),
   _need_update_refs(false),
   _need_reset_bitmaps(false),
@@ -1135,6 +1138,15 @@
     if (ShenandoahVerify) {
       verify_heap_after_marking();
     }
+
+    if (UseShenandoahMatrix) {
+      if (PrintShenandoahMatrix) {
+        connection_matrix()->print_on(tty);
+      }
+      if (VerifyShenandoahMatrix) {
+        verify_matrix();
+      }
+    }
 #endif
 
     // NOTE: This needs to be done during a stop the world pause, because
@@ -1159,22 +1171,9 @@
       _ordered_regions->heap_region_iterate(&ccsc);
 #endif
 
-    if (UseShenandoahMatrix) {
-      int num = num_regions();
-      int *connections = NEW_C_HEAP_ARRAY(int, num * num, mtGC);
-      calculate_matrix(connections);
-      print_matrix(connections);
-      _shenandoah_policy->choose_collection_set(_collection_set, connections);
-      FREE_C_HEAP_ARRAY(int,connections);
-    } else {
       _shenandoah_policy->choose_collection_set(_collection_set);
-    }
-
-    _shenandoah_policy->choose_free_set(_free_regions);
-    }
-
-    if (UseShenandoahMatrix) {
-      _collection_set->print();
+
+      _shenandoah_policy->choose_free_set(_free_regions);
     }
 
     _bytes_allocated_since_cm = 0;
@@ -1788,7 +1787,6 @@
   }
 };
 
-
 void ShenandoahHeap::start_concurrent_marking() {
 
   shenandoahPolicy()->record_phase_start(ShenandoahCollectorPolicy::accumulate_stats);
@@ -1818,6 +1816,9 @@
   heap_region_iterate(&clc);
   shenandoahPolicy()->record_phase_end(ShenandoahCollectorPolicy::clear_liveness);
 
+  if (UseShenandoahMatrix) {
+    connection_matrix()->clear_all();
+  }
   // print_all_refs("pre -mark");
 
   // oopDesc::_debug = true;
@@ -1900,6 +1901,85 @@
   _next_top_at_mark_starts_base = tmp3;
 }
 
+class ShenandoahVerifyMatrixOopClosure : public ExtendedOopClosure {
+private:
+  oop _obj;
+
+  template <class T>
+  inline void do_oop_nv(T* p) {
+    T o = oopDesc::load_heap_oop(p);
+    if (! oopDesc::is_null(o)) {
+      oop obj = oopDesc::decode_heap_oop_not_null(o);
+      ShenandoahHeap* heap = ShenandoahHeap::heap();
+      guarantee(heap->is_marked_complete(obj), "must be marked");
+
+      uint from_idx = heap->heap_region_index_containing(p);
+      uint to_idx = heap->heap_region_index_containing(obj);
+      if (!heap->connection_matrix()->is_connected(from_idx, to_idx)) {
+        tty->print_cr("from-obj: ");
+        _obj->print_on(tty);
+        tty->print_cr("to-obj:");
+        obj->print_on(tty);
+        tty->print_cr("from-obj allocated after mark: %s", BOOL_TO_STR(heap->allocated_after_complete_mark_start((HeapWord*) _obj)));
+        tty->print_cr("to-obj allocated after mark: %s", BOOL_TO_STR(heap->allocated_after_complete_mark_start((HeapWord*) obj)));
+        tty->print_cr("from-obj marked: %s", BOOL_TO_STR(heap->is_marked_complete(_obj)));
+        tty->print_cr("to-obj marked: %s", BOOL_TO_STR(heap->is_marked_complete(obj)));
+        tty->print_cr("from-idx: %u, to-idx: %u", from_idx, to_idx);
+
+        oop fwd_from = BrooksPointer::forwardee(_obj);
+        oop fwd_to = BrooksPointer::forwardee(obj);
+        tty->print_cr("from-obj forwardee: " PTR_FORMAT, p2i(fwd_from));
+        tty->print_cr("to-obj forwardee: " PTR_FORMAT, p2i(fwd_to));
+        tty->print_cr("forward(from-obj) marked: %s", BOOL_TO_STR(heap->is_marked_complete(fwd_from)));
+        tty->print_cr("forward(to-obj) marked: %s", BOOL_TO_STR(heap->is_marked_complete(fwd_to)));
+        uint fwd_from_idx = heap->heap_region_index_containing(fwd_from);
+        uint fwd_to_idx = heap->heap_region_index_containing(fwd_to);
+        tty->print_cr("forward(from-idx): %u, forward(to-idx): %u", fwd_from_idx, fwd_to_idx);
+        tty->print_cr("forward(from) connected with forward(to)? %s", BOOL_TO_STR(heap->connection_matrix()->is_connected(fwd_from_idx, fwd_to_idx)));
+        tty->print_cr("sizeof(bool): %lu", sizeof(bool));
+      }
+      guarantee(oopDesc::unsafe_equals(ShenandoahBarrierSet::resolve_oop_static_not_null(obj), obj), "polizeilich verboten");
+      guarantee(heap->connection_matrix()->is_connected(from_idx, to_idx), "must be connected");
+    }
+  }
+
+public:
+  ShenandoahVerifyMatrixOopClosure(oop obj) : _obj(obj) {}
+
+  void do_oop(oop* o) {
+    do_oop_nv(o);
+  }
+
+  void do_oop(narrowOop* o) {
+    do_oop_nv(o);
+  }
+};
+
+class ShenandoahVerifyMatrixObjectClosure : public ObjectClosure {
+public:
+  void do_object(oop obj) {
+    guarantee(ShenandoahHeap::heap()->is_marked_complete(obj), "must be marked");
+    ShenandoahVerifyMatrixOopClosure cl(obj);
+    obj->oop_iterate(&cl);
+  }
+
+};
+
+class ShenandoahVerifyMatrixRegionClosure : public ShenandoahHeapRegionClosure {
+  bool doHeapRegion(ShenandoahHeapRegion* r) {
+    ShenandoahVerifyMatrixObjectClosure cl;
+    ShenandoahHeap::heap()->marked_object_iterate(r, &cl);
+    return false;
+  }
+};
+
+void ShenandoahHeap::verify_matrix() {
+  OrderAccess::fence();
+  ensure_parsability(false);
+  ShenandoahVerifyMatrixRegionClosure cl;
+  heap_region_iterate(&cl, true, true);
+}
+
 void ShenandoahHeap::stop_concurrent_marking() {
   assert(concurrent_mark_in_progress(), "How else could we get here?");
   if (! cancelled_concgc()) {
@@ -2442,6 +2522,10 @@
   return cl.garbage();
 }
 
+ShenandoahConnectionMatrix* ShenandoahHeap::connection_matrix() {
+  return _connection_matrix;
+}
+
 #ifdef ASSERT
 void ShenandoahHeap::assert_heaplock_owned_by_current_thread() {
   assert(_heap_lock == locked, "must be locked");
diff --git a/src/share/vm/gc/shenandoah/shenandoahHeap.hpp b/src/share/vm/gc/shenandoah/shenandoahHeap.hpp
--- a/src/share/vm/gc/shenandoah/shenandoahHeap.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoahHeap.hpp
@@ -30,6 +30,7 @@
 class ConcurrentGCTimer;
 
 class ShenandoahCollectorPolicy;
+class ShenandoahConnectionMatrix;
 class ShenandoahHeapRegion;
 class ShenandoahHeapRegionClosure;
 class ShenandoahHeapRegionSet;
@@ -140,6 +141,7 @@
   ShenandoahHeapRegionSet* _sorted_regions;
   ShenandoahFreeSet* _free_regions;
   ShenandoahCollectionSet* _collection_set;
+
   ShenandoahHeapRegion* _currentAllocationRegion;
   ShenandoahConcurrentMark* _scm;
 
@@ -203,6 +205,8 @@
   // See allocate_memory()
   volatile jbyte _heap_lock;
 
+  ShenandoahConnectionMatrix* _connection_matrix;
+
 #ifdef ASSERT
   volatile Thread* _heap_lock_owner;
 #endif
@@ -295,6 +299,7 @@
   void prepare_for_concurrent_evacuation();
   void evacuate_and_update_roots();
 
+  void verify_matrix();
 private:
   void set_evacuation_in_progress(bool in_progress);
 public:
@@ -340,6 +345,8 @@
   void clear_free_regions();
   void add_free_region(ShenandoahHeapRegion* r);
 
+  ShenandoahConnectionMatrix* connection_matrix();
+
   void increase_used(size_t bytes);
   void decrease_used(size_t bytes);
 
diff --git a/src/share/vm/gc/shenandoah/shenandoahHeap.inline.hpp b/src/share/vm/gc/shenandoah/shenandoahHeap.inline.hpp
--- a/src/share/vm/gc/shenandoah/shenandoahHeap.inline.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoahHeap.inline.hpp
@@ -28,6 +28,7 @@
 #include "gc/shared/threadLocalAllocBuffer.inline.hpp"
 #include "gc/shenandoah/brooksPointer.inline.hpp"
 #include "gc/shenandoah/shenandoahBarrierSet.inline.hpp"
+#include "gc/shenandoah/shenandoahConnectionMatrix.hpp"
 #include "gc/shenandoah/shenandoahHeap.hpp"
 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
 #include "gc/shenandoah/shenandoahHeapRegion.inline.hpp"
@@ -176,6 +177,11 @@
   assert(is_in(heap_oop), "only ever call this on objects in the heap");
   if (in_collection_set(heap_oop)) {
     oop forwarded_oop = ShenandoahBarrierSet::resolve_oop_static_not_null(heap_oop); // read brooks ptr
+    if (oopDesc::unsafe_equals(forwarded_oop, heap_oop)) {
+      // E.g. during evacuation.
+      return forwarded_oop;
+    }
+
     assert(! oopDesc::unsafe_equals(forwarded_oop, heap_oop) || is_full_gc_in_progress(), "expect forwarded object");
 
     log_develop_trace(gc)("Updating old ref: "PTR_FORMAT" pointing to "PTR_FORMAT" to new ref: "PTR_FORMAT,
@@ -225,6 +231,40 @@
   }
 }
 
+class UpdateMatrixClosure : public ExtendedOopClosure {
+
+private:
+  uint _from_idx;
+  ShenandoahHeap* _heap;
+  ShenandoahConnectionMatrix* _matrix;
+
+  template <class T>
+  inline void do_oop_nv(T* o) {
+    T t = oopDesc::load_heap_oop(o);
+    if (! oopDesc::is_null(t)) {
+      oop obj = oopDesc::decode_heap_oop_not_null(t);
+      uint to_idx = _heap->heap_region_index_containing(obj);
+      _matrix->set_connected(_from_idx, to_idx, true);
+    }
+  }
+
+public:
+
+  UpdateMatrixClosure(uint from_idx) :
+    _from_idx(from_idx),
+    _heap(ShenandoahHeap::heap()),
+    _matrix(ShenandoahHeap::heap()->connection_matrix()) {
+  }
+
+  void do_oop(oop* o) {
+    do_oop_nv(o);
+  }
+
+  void do_oop(narrowOop* o) {
+    do_oop_nv(o);
+  }
+};
+
 inline void ShenandoahHeap::copy_object(oop p, HeapWord* s, size_t words) {
   assert(s != NULL, "allocation of brooks pointer must not fail");
   HeapWord* copy = s + BrooksPointer::word_size();
@@ -310,6 +350,10 @@
     assert(return_val->is_oop(), "expect oop");
     assert(p->klass() == return_val->klass(), "Should have the same class p: "PTR_FORMAT", copy: "PTR_FORMAT,
                                               p2i((HeapWord*) p), p2i((HeapWord*) copy));
+
+    uint from_idx = heap_region_index_containing(copy_val);
+    UpdateMatrixClosure cl(from_idx);
+    copy_val->oop_iterate(&cl);
 #endif
   }  else {
     if (alloc_from_gclab) {
diff --git a/src/share/vm/gc/shenandoah/shenandoahHeapRegion.cpp b/src/share/vm/gc/shenandoah/shenandoahHeapRegion.cpp
--- a/src/share/vm/gc/shenandoah/shenandoahHeapRegion.cpp
+++ b/src/share/vm/gc/shenandoah/shenandoahHeapRegion.cpp
@@ -23,6 +23,7 @@
 
 #include "memory/allocation.hpp"
 #include "gc/shenandoah/brooksPointer.hpp"
+#include "gc/shenandoah/shenandoahConnectionMatrix.hpp"
 #include "gc/shenandoah/shenandoahHeap.hpp"
 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
 #include "gc/shenandoah/shenandoahHeapRegion.hpp"
@@ -254,6 +255,7 @@
   _heap->set_complete_top_at_mark_start(bottom(), bottom());
   // We can only safely reset the C-TAMS pointer if the bitmap is clear for that region.
   assert(_heap->is_complete_bitmap_clear_range(bottom(), end()), "must be clear");
+  _heap->connection_matrix()->clear_region(region_number());
 }
 
 HeapWord* ShenandoahHeapRegion::block_start_const(const void* p) const {
diff --git a/src/share/vm/gc/shenandoah/shenandoahMarkCompact.cpp b/src/share/vm/gc/shenandoah/shenandoahMarkCompact.cpp
--- a/src/share/vm/gc/shenandoah/shenandoahMarkCompact.cpp
+++ b/src/share/vm/gc/shenandoah/shenandoahMarkCompact.cpp
@@ -305,6 +305,15 @@
 
   _heap->swap_mark_bitmaps();
 
+  if (UseShenandoahMatrix) {
+    if (PrintShenandoahMatrix) {
+      _heap->connection_matrix()->print_on(tty);
+    }
+    if (VerifyShenandoahMatrix) {
+      _heap->verify_matrix();
+    }
+  }
+
   if (VerifyDuringGC) {
     HandleMark hm;  // handle scope
     //    Universe::heap()->prepare_for_verify();
diff --git a/src/share/vm/gc/shenandoah/shenandoahOopClosures.hpp b/src/share/vm/gc/shenandoah/shenandoahOopClosures.hpp
--- a/src/share/vm/gc/shenandoah/shenandoahOopClosures.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoahOopClosures.hpp
@@ -30,6 +30,7 @@
 typedef Padded<ShenandoahBufferedOverflowTaskQueue> SCMObjToScanQueue;
 
 class ShenandoahHeap;
+class ShenandoahConnectionMatrix;
 
 enum UpdateRefsMode {
   NONE,       // No reference updating
@@ -42,10 +43,11 @@
 private:
   SCMObjToScanQueue* _queue;
   ShenandoahHeap* _heap;
+  ShenandoahConnectionMatrix* _conn_matrix;
 public:
   ShenandoahMarkRefsSuperClosure(SCMObjToScanQueue* q, ReferenceProcessor* rp);
 
-  template <class T, UpdateRefsMode UPDATE_MODE>
+  template <class T, UpdateRefsMode UPDATE_MODE, bool UPDATE_MATRIX>
   void work(T *p);
 };
 
@@ -55,7 +57,7 @@
           ShenandoahMarkRefsSuperClosure(q, rp) {};
 
   template <class T>
-  inline void do_oop_nv(T* p)       { work<T, CONCURRENT>(p); }
+  inline void do_oop_nv(T* p)       { work<T, CONCURRENT, false>(p); }
   virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
   virtual void do_oop(oop* p)       { do_oop_nv(p); }
   inline bool do_metadata_nv()      { return false; }
@@ -68,7 +70,7 @@
           ShenandoahMarkRefsSuperClosure(q, rp) {};
 
   template <class T>
-  inline void do_oop_nv(T* p)       { work<T, CONCURRENT>(p); }
+  inline void do_oop_nv(T* p)       { work<T, CONCURRENT, false>(p); }
   virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
   virtual void do_oop(oop* p)       { do_oop_nv(p); }
   inline bool do_metadata_nv()      { return true; }
@@ -81,7 +83,7 @@
     ShenandoahMarkRefsSuperClosure(q, rp) {};
 
   template <class T>
-  inline void do_oop_nv(T* p)       { work<T, NONE>(p); }
+  inline void do_oop_nv(T* p)       { work<T, NONE, false>(p); }
   virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
   virtual void do_oop(oop* p)       { do_oop_nv(p); }
   inline bool do_metadata_nv()      { return false; }
@@ -94,7 +96,7 @@
     ShenandoahMarkRefsSuperClosure(q, rp) {};
 
   template <class T>
-  inline void do_oop_nv(T* p)       { work<T, RESOLVE>(p); }
+  inline void do_oop_nv(T* p)       { work<T, RESOLVE, false>(p); }
   virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
   virtual void do_oop(oop* p)       { do_oop_nv(p); }
   inline bool do_metadata_nv()      { return false; }
@@ -107,7 +109,59 @@
     ShenandoahMarkRefsSuperClosure(q, rp) {};
 
   template <class T>
-  inline void do_oop_nv(T* p)       { work<T, NONE>(p); }
+  inline void do_oop_nv(T* p)       { work<T, NONE, false>(p); }
+  virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
+  virtual void do_oop(oop* p)       { do_oop_nv(p); }
+  inline bool do_metadata_nv()      { return true; }
+  virtual bool do_metadata()        { return true; }
+};
+
+class ShenandoahMarkUpdateRefsMatrixClosure : public ShenandoahMarkRefsSuperClosure {
+public:
+  ShenandoahMarkUpdateRefsMatrixClosure(SCMObjToScanQueue* q, ReferenceProcessor* rp) :
+          ShenandoahMarkRefsSuperClosure(q, rp) {};
+
+  template <class T>
+  inline void do_oop_nv(T* p)       { work<T, CONCURRENT, true>(p); }
+  virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
+  virtual void do_oop(oop* p)       { do_oop_nv(p); }
+  inline bool do_metadata_nv()      { return false; }
+  virtual bool do_metadata()        { return false; }
+};
+
+class ShenandoahMarkUpdateRefsMetadataMatrixClosure : public ShenandoahMarkRefsSuperClosure {
+public:
+  ShenandoahMarkUpdateRefsMetadataMatrixClosure(SCMObjToScanQueue* q, ReferenceProcessor* rp) :
+          ShenandoahMarkRefsSuperClosure(q, rp) {};
+
+  template <class T>
+  inline void do_oop_nv(T* p)       { work<T, CONCURRENT, true>(p); }
+  virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
+  virtual void do_oop(oop* p)       { do_oop_nv(p); }
+  inline bool do_metadata_nv()      { return true; }
+  virtual bool do_metadata()        { return true; }
+};
+
+class ShenandoahMarkRefsMatrixClosure : public ShenandoahMarkRefsSuperClosure {
+public:
+  ShenandoahMarkRefsMatrixClosure(SCMObjToScanQueue* q, ReferenceProcessor* rp) :
+    ShenandoahMarkRefsSuperClosure(q, rp) {};
+
+  template <class T>
+  inline void do_oop_nv(T* p)       { work<T, NONE, true>(p); }
+  virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
+  virtual void do_oop(oop* p)       { do_oop_nv(p); }
+  inline bool do_metadata_nv()      { return false; }
+  virtual bool do_metadata()        { return false; }
+};
+
+class ShenandoahMarkRefsMetadataMatrixClosure : public ShenandoahMarkRefsSuperClosure {
+public:
+  ShenandoahMarkRefsMetadataMatrixClosure(SCMObjToScanQueue* q, ReferenceProcessor* rp) :
+    ShenandoahMarkRefsSuperClosure(q, rp) {};
+
+  template <class T>
+  inline void do_oop_nv(T* p)       { work<T, NONE, true>(p); }
   virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
   virtual void do_oop(oop* p)       { do_oop_nv(p); }
   inline bool do_metadata_nv()      { return true; }
diff --git a/src/share/vm/gc/shenandoah/shenandoahOopClosures.inline.hpp b/src/share/vm/gc/shenandoah/shenandoahOopClosures.inline.hpp
--- a/src/share/vm/gc/shenandoah/shenandoahOopClosures.inline.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoahOopClosures.inline.hpp
@@ -27,9 +27,9 @@
 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
 #include "gc/shenandoah/shenandoahConcurrentMark.inline.hpp"
 
-template<class T, UpdateRefsMode UPDATE_REFS>
+template<class T, UpdateRefsMode UPDATE_REFS, bool UPDATE_MATRIX>
 inline void ShenandoahMarkRefsSuperClosure::work(T *p) {
-  ShenandoahConcurrentMark::mark_through_ref<T, UPDATE_REFS>(p, _heap, _queue);
+  ShenandoahConcurrentMark::mark_through_ref<T, UPDATE_REFS, UPDATE_MATRIX>(p, _heap, _queue, _conn_matrix);
 }
 
 #endif // SHARE_VM_GC_SHENANDOAH_SHENANDOAHOOPCLOSURES_INLINE_HPP
diff --git a/src/share/vm/gc/shenandoah/shenandoah_globals.hpp b/src/share/vm/gc/shenandoah/shenandoah_globals.hpp
--- a/src/share/vm/gc/shenandoah/shenandoah_globals.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoah_globals.hpp
@@ -66,6 +66,12 @@
   product(bool, UseShenandoahMatrix, false,                                 \
           "Keep a connection matrix and use this to drive collection sets") \
                                                                             \
+  product(bool, PrintShenandoahMatrix, false,                               \
+          "Print connection matrix after marking")                          \
+                                                                            \
+  product(bool, VerifyShenandoahMatrix, false,                              \
+          "Verify connection matrix after marking")                         \
+                                                                            \
   product(ccstr, ShenandoahGCHeuristics, "adaptive",                        \
           "The heuristics to use in Shenandoah GC. Possible values: "       \
           "dynamic, adaptive, aggressive."                                  \
diff --git a/src/share/vm/gc/shenandoah/shenandoah_specialized_oop_closures.hpp b/src/share/vm/gc/shenandoah/shenandoah_specialized_oop_closures.hpp
--- a/src/share/vm/gc/shenandoah/shenandoah_specialized_oop_closures.hpp
+++ b/src/share/vm/gc/shenandoah/shenandoah_specialized_oop_closures.hpp
@@ -28,11 +28,19 @@
 class ShenandoahMarkUpdateRefsMetadataClosure;
 class ShenandoahMarkRefsClosure;
 class ShenandoahMarkRefsMetadataClosure;
+class ShenandoahMarkUpdateRefsMatrixClosure;
+class ShenandoahMarkUpdateRefsMetadataMatrixClosure;
+class ShenandoahMarkRefsMatrixClosure;
+class ShenandoahMarkRefsMetadataMatrixClosure;
 
 #define SPECIALIZED_OOP_OOP_ITERATE_CLOSURES_SHENANDOAH(f) \
       f(ShenandoahMarkUpdateRefsClosure,_nv)               \
       f(ShenandoahMarkUpdateRefsMetadataClosure,_nv)       \
       f(ShenandoahMarkRefsClosure,_nv)                     \
-      f(ShenandoahMarkRefsMetadataClosure,_nv)
+      f(ShenandoahMarkRefsMetadataClosure,_nv)             \
+      f(ShenandoahMarkUpdateRefsMatrixClosure,_nv)         \
+      f(ShenandoahMarkUpdateRefsMetadataMatrixClosure,_nv) \
+      f(ShenandoahMarkRefsMatrixClosure,_nv)               \
+      f(ShenandoahMarkRefsMetadataMatrixClosure,_nv)
 
 #endif // SHARE_VM_GC_SHENANDOAH_SHENANDOAH_SPECIALIZED_OOP_CLOSURES_HPP
diff --git a/src/share/vm/opto/addnode.cpp b/src/share/vm/opto/addnode.cpp
--- a/src/share/vm/opto/addnode.cpp
+++ b/src/share/vm/opto/addnode.cpp
@@ -647,6 +647,14 @@
           if (u->as_LoadStore()->adr_type() != NULL) {
             u->as_LoadStore()->set_adr_type(TypeRawPtr::BOTTOM);
           }
+        } else if (u->Opcode() == Op_CastP2X) {
+          PhaseIterGVN *igvn = phase->is_IterGVN();
+          phase->C->shenandoah_eliminate_matrix_update(u, igvn);
+          --i; --imax;
+        } else if (u->is_g1_wb_pre_call()) {
+          PhaseIterGVN *igvn = phase->is_IterGVN();
+          phase->C->shenandoah_eliminate_g1_wb_pre(u, igvn);
+          --i; --imax;
         }
 #ifdef ASSERT
         else if (u->is_Mem()) {
diff --git a/src/share/vm/opto/compile.cpp b/src/share/vm/opto/compile.cpp
--- a/src/share/vm/opto/compile.cpp
+++ b/src/share/vm/opto/compile.cpp
@@ -4655,3 +4655,44 @@
     ni.dump();
   }
 }
+
+void Compile::shenandoah_eliminate_matrix_update(Node* p2x, PhaseIterGVN* igvn) {
+  assert(UseShenandoahGC && p2x->Opcode() == Op_CastP2X, "");
+  ResourceMark rm;
+  Unique_Node_List wq;
+
+  wq.push(p2x);
+  for (uint next = 0; next < wq.size(); next++) {
+    Node *n = wq.at(next);
+    if (n->is_Store()) {
+      igvn->replace_node(n, n->in(MemNode::Memory));
+    } else {
+      for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
+        Node* u = n->fast_out(i);
+        wq.push(u);
+      }
+    }
+    }
+  igvn->replace_node(p2x, C->top());
+}
+
+void Compile::shenandoah_eliminate_g1_wb_pre(Node* call, PhaseIterGVN* igvn) {
+  assert(UseShenandoahGC && call->is_g1_wb_pre_call(), "");
+  Node* c = call->as_Call()->proj_out(TypeFunc::Control);
+  c = c->unique_ctrl_out();
+  assert(c->is_Region() && c->req() == 3, "where's the pre barrier control flow?");
+  c = c->unique_ctrl_out();
+  assert(c->is_Region() && c->req() == 3, "where's the pre barrier control flow?");
+  Node* iff = c->in(1)->is_IfProj() ? c->in(1)->in(0) : c->in(2)->in(0);
+  assert(iff->is_If(), "expect test");
+  if (!iff->is_g1_marking_if(igvn)) {
+    c = c->unique_ctrl_out();
+    assert(c->is_Region() && c->req() == 3, "where's the pre barrier control flow?");
+    iff = c->in(1)->is_IfProj() ? c->in(1)->in(0) : c->in(2)->in(0);
+    assert(iff->is_g1_marking_if(igvn), "expect marking test");
+  }
+  Node* cmpx = iff->in(1)->in(1);
+  igvn->replace_node(cmpx, igvn->makecon(TypeInt::CC_EQ));
+  igvn->rehash_node_delayed(call);
+  call->del_req(call->req()-1);
+}
diff --git a/src/share/vm/opto/compile.hpp b/src/share/vm/opto/compile.hpp
--- a/src/share/vm/opto/compile.hpp
+++ b/src/share/vm/opto/compile.hpp
@@ -1360,6 +1360,9 @@
   CloneMap&     clone_map();
   void          set_clone_map(Dict* d);
 
+  void shenandoah_eliminate_matrix_update(Node* p2x, PhaseIterGVN* igvn);
+  void shenandoah_eliminate_g1_wb_pre(Node* call, PhaseIterGVN* igvn);
+
 };
 
 #endif // SHARE_VM_OPTO_COMPILE_HPP
diff --git a/src/share/vm/opto/graphKit.cpp b/src/share/vm/opto/graphKit.cpp
--- a/src/share/vm/opto/graphKit.cpp
+++ b/src/share/vm/opto/graphKit.cpp
@@ -30,6 +30,9 @@
 #include "gc/shared/cardTableModRefBS.hpp"
 #include "gc/shared/collectedHeap.hpp"
 #include "gc/shenandoah/brooksPointer.hpp"
+#include "gc/shenandoah/shenandoahConnectionMatrix.hpp"
+#include "gc/shenandoah/shenandoahHeap.hpp"
+#include "gc/shenandoah/shenandoahHeapRegion.hpp"
 #include "memory/resourceArea.hpp"
 #include "opto/addnode.hpp"
 #include "opto/castnode.hpp"
@@ -4143,8 +4146,10 @@
   }
 
   if (! ShenandoahReduceStoreValBarrier) {
+    val = shenandoah_read_barrier_storeval(val);
+    shenandoah_update_matrix(adr, val);
     g1_write_barrier_pre(do_load, obj, adr, alias_idx, val, val_type, pre_val, bt);
-    return shenandoah_read_barrier_storeval(val);
+    return val;
   }
 
   if (do_load) {
@@ -4263,6 +4268,60 @@
   return val;
 }
 
+void GraphKit::shenandoah_update_matrix(Node* adr, Node* val) {
+  assert(val != NULL, "checked before");
+  if (adr == NULL) {
+    return; // Nothing to do
+  }
+  assert(adr != NULL, "must not happen");
+  if (val->bottom_type()->higher_equal(TypePtr::NULL_PTR)) {
+    // Nothing to do.
+    return;
+  }
+
+  ShenandoahConnectionMatrix* matrix = ShenandoahHeap::heap()->connection_matrix();
+
+  enum { _not_null_path = 1, _null_path, PATH_LIMIT };
+  RegionNode* region = new RegionNode(PATH_LIMIT);
+  Node* prev_mem = memory(Compile::AliasIdxRaw);
+  Node* memphi    = PhiNode::make(region, prev_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
+  Node* null_ctrl = top();
+  Node* not_null_val = null_check_oop(val, &null_ctrl);
+
+  // Null path: nothing to do.
+  region->init_req(_null_path, null_ctrl);
+  memphi->init_req(_null_path, prev_mem);
+
+  // Not null path. Update the matrix.
+  Node* heapbase = MakeConX((intx) ShenandoahHeap::heap()->first_region_bottom());
+  Node* region_size_shift = intcon((jint) ShenandoahHeapRegion::RegionSizeShift);
+  Node* stride = MakeConX((intx) matrix->stride());
+  Node* matrix_base = makecon(TypeRawPtr::make(matrix->matrix_addr()));
+  // Compute region index for adr.
+  Node* adr_idx = _gvn.transform(new CastP2XNode(control(), adr));
+  adr_idx = _gvn.transform(new SubXNode(adr_idx, heapbase));
+  adr_idx = _gvn.transform(new URShiftXNode(adr_idx, region_size_shift));
+  // Compute region index for val.
+  Node* val_idx = _gvn.transform(new CastP2XNode(control(), not_null_val));
+  val_idx = _gvn.transform(new SubXNode(val_idx, heapbase));
+  val_idx = _gvn.transform(new URShiftXNode(val_idx, region_size_shift));
+  // Compute matrix index & address.
+  Node* matrix_idx = _gvn.transform(new MulXNode(adr_idx, stride));
+  matrix_idx = _gvn.transform(new AddXNode(matrix_idx, val_idx));
+  Node* matrix_adr = basic_plus_adr(top(), matrix_base, matrix_idx);
+  // Do the store.
+  const TypePtr* adr_type = TypeRawPtr::BOTTOM;
+  Node* store = _gvn.transform(StoreNode::make(_gvn, control(), memory(Compile::AliasIdxRaw), matrix_adr, adr_type, intcon(1), T_BOOLEAN, MemNode::unordered));
+
+  region->init_req(_not_null_path, control());
+  memphi->init_req(_not_null_path, store);
+
+  // Merge control flows and memory.
+  set_control(_gvn.transform(region));
+  record_for_igvn(region);
+  set_memory(_gvn.transform(memphi), Compile::AliasIdxRaw);
+}
+
 /*
  * G1 similar to any GC with a Young Generation requires a way to keep track of
  * references from Old Generation to Young Generation to make sure all live
diff --git a/src/share/vm/opto/graphKit.hpp b/src/share/vm/opto/graphKit.hpp
--- a/src/share/vm/opto/graphKit.hpp
+++ b/src/share/vm/opto/graphKit.hpp
@@ -926,6 +926,7 @@
   // Produce new array node of stable type
   Node* cast_array_to_stable(Node* ary, const TypeAryPtr* ary_type);
 
+  void shenandoah_update_matrix(Node* adr, Node* val);
   Node* shenandoah_read_barrier(Node* obj);
   Node* shenandoah_read_barrier_storeval(Node* obj);
   Node* shenandoah_write_barrier(Node* obj);
diff --git a/src/share/vm/opto/library_call.cpp b/src/share/vm/opto/library_call.cpp
--- a/src/share/vm/opto/library_call.cpp
+++ b/src/share/vm/opto/library_call.cpp
@@ -3013,7 +3013,7 @@
         }
         // The only known value which might get overwritten is oldval.
         newval = pre_barrier(false /* do_load */,
-                    control(), NULL, NULL, max_juint, newval, NULL,
+                    control(), NULL, adr, max_juint, newval, NULL,
                     oldval /* pre_val */,
                     T_OBJECT);
         break;
diff --git a/src/share/vm/opto/macro.cpp b/src/share/vm/opto/macro.cpp
--- a/src/share/vm/opto/macro.cpp
+++ b/src/share/vm/opto/macro.cpp
@@ -228,7 +228,7 @@
 // Eliminate a card mark sequence.  p2x is a ConvP2XNode
 void PhaseMacroExpand::eliminate_card_mark(Node* p2x) {
   assert(p2x->Opcode() == Op_CastP2X, "ConvP2XNode required");
-  if (!UseG1GC) {
+  if (!UseG1GC && !UseShenandoahGC) {
     // vanilla/CMS post barrier
     Node *shift = p2x->unique_out();
     Node *addp = shift->unique_out();
@@ -244,7 +244,7 @@
       assert(mem->is_Store(), "store required");
       _igvn.replace_node(mem, mem->in(MemNode::Memory));
     }
-  } else {
+  } else if (!UseShenandoahGC) {
     // G1 pre/post barriers
     assert(p2x->outcnt() <= 2, "expects 1 or 2 users: Xor and URShift nodes");
     // It could be only one user, URShift node, in Object.clone() intrinsic
@@ -311,29 +311,12 @@
     // which currently still alive until igvn optimize it.
     assert(p2x->outcnt() == 0 || p2x->unique_out()->Opcode() == Op_URShiftX, "");
     _igvn.replace_node(p2x, top());
+  } else {
+    assert(UseShenandoahGC, "only get here with Shenandoah GC");
+    C->shenandoah_eliminate_matrix_update(p2x, &_igvn);
   }
 }
 
-void PhaseMacroExpand::eliminate_g1_wb_pre(Node* n) {
-  Node* c = n->as_Call()->proj_out(TypeFunc::Control);
-  c = c->unique_ctrl_out();
-  assert(c->is_Region() && c->req() == 3, "where's the pre barrier control flow?");
-  c = c->unique_ctrl_out();
-  assert(c->is_Region() && c->req() == 3, "where's the pre barrier control flow?");
-  Node* iff = c->in(1)->is_IfProj() ? c->in(1)->in(0) : c->in(2)->in(0);
-  assert(iff->is_If(), "expect test");
-  if (!iff->is_g1_marking_if(&_igvn)) {
-    c = c->unique_ctrl_out();
-    assert(c->is_Region() && c->req() == 3, "where's the pre barrier control flow?");
-    iff = c->in(1)->is_IfProj() ? c->in(1)->in(0) : c->in(2)->in(0);
-    assert(iff->is_g1_marking_if(&_igvn), "expect marking test");
-  }
-  Node* cmpx = iff->in(1)->in(1);
-  _igvn.replace_node(cmpx, makecon(TypeInt::CC_EQ));
-  _igvn.rehash_node_delayed(n);
-  n->del_req(n->req()-1);
-}
-
 // Search for a memory operation for the specified memory slice.
 static Node *scan_mem_chain(Node *mem, int alias_idx, int offset, Node *start_mem, Node *alloc, PhaseGVN *phase) {
   Node *orig_mem = mem;
@@ -1033,7 +1016,7 @@
               disconnect_projections(membar_after->as_MemBar(), _igvn);
             }
           } else if (n->is_g1_wb_pre_call()) {
-            eliminate_g1_wb_pre(n);
+            C->shenandoah_eliminate_g1_wb_pre(n, &_igvn);
           } else {
             eliminate_card_mark(n);
           }
diff --git a/src/share/vm/opto/macro.hpp b/src/share/vm/opto/macro.hpp
--- a/src/share/vm/opto/macro.hpp
+++ b/src/share/vm/opto/macro.hpp
@@ -95,7 +95,6 @@
   void process_users_of_allocation(CallNode *alloc);
 
   void eliminate_card_mark(Node *cm);
-  void eliminate_g1_wb_pre(Node *n);
   void mark_eliminated_box(Node* box, Node* obj);
   void mark_eliminated_locking_nodes(AbstractLockNode *alock);
   bool eliminate_locking_node(AbstractLockNode *alock);