< prev index next >

src/hotspot/share/gc/shenandoah/c2/shenandoahSupport.cpp

Print this page


   1 /*
   2  * Copyright (c) 2015, 2018, Red Hat, Inc. All rights reserved.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  *
  22  */
  23 
  24 #include "precompiled.hpp"
  25 
  26 #include "gc/shenandoah/c2/shenandoahSupport.hpp"
  27 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
  28 #include "gc/shenandoah/shenandoahBarrierSetAssembler.hpp"
  29 #include "gc/shenandoah/shenandoahBrooksPointer.hpp"
  30 #include "gc/shenandoah/shenandoahHeap.hpp"
  31 #include "gc/shenandoah/shenandoahHeapRegion.hpp"
  32 #include "gc/shenandoah/shenandoahRuntime.hpp"

  33 #include "opto/arraycopynode.hpp"
  34 #include "opto/block.hpp"
  35 #include "opto/callnode.hpp"
  36 #include "opto/castnode.hpp"
  37 #include "opto/movenode.hpp"
  38 #include "opto/phaseX.hpp"
  39 #include "opto/rootnode.hpp"
  40 #include "opto/runtime.hpp"
  41 #include "opto/subnode.hpp"
  42 
  43 Node* ShenandoahBarrierNode::skip_through_barrier(Node* n) {
  44   if (n == NULL) {
  45     return NULL;
  46   }
  47   if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
  48     n = n->in(1);
  49   }
  50 
  51   if (n->is_ShenandoahBarrier()) {
  52     return n->in(ValueIn);
  53   } else if (n->is_Phi() &&
  54              n->req() == 3 &&
  55              n->in(1) != NULL &&
  56              n->in(1)->is_ShenandoahBarrier() &&
  57              n->in(2) != NULL &&
  58              n->in(2)->bottom_type() == TypePtr::NULL_PTR &&
  59              n->in(0) != NULL &&
  60              n->in(0)->in(1) != NULL &&
  61              n->in(0)->in(1)->is_IfProj() &&
  62              n->in(0)->in(2) != NULL &&
  63              n->in(0)->in(2)->is_IfProj() &&
  64              n->in(0)->in(1)->in(0) != NULL &&
  65              n->in(0)->in(1)->in(0) == n->in(0)->in(2)->in(0) &&
  66              n->in(1)->in(ValueIn)->Opcode() == Op_CastPP) {
  67     Node* iff = n->in(0)->in(1)->in(0);
  68     Node* res = n->in(1)->in(ValueIn)->in(1);
  69     if (iff->is_If() &&
  70         iff->in(1) != NULL &&
  71         iff->in(1)->is_Bool() &&
  72         iff->in(1)->as_Bool()->_test._test == BoolTest::ne &&
  73         iff->in(1)->in(1) != NULL &&
  74         iff->in(1)->in(1)->Opcode() == Op_CmpP &&
  75         iff->in(1)->in(1)->in(1) != NULL &&
  76         iff->in(1)->in(1)->in(1) == res &&
  77         iff->in(1)->in(1)->in(2) != NULL &&
  78         iff->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
  79       return res;
  80     }
  81   }
  82   return n;
  83 }
  84 
  85 bool ShenandoahBarrierNode::needs_barrier(PhaseGVN* phase, ShenandoahBarrierNode* orig, Node* n, Node* rb_mem, bool allow_fromspace) {
  86   Unique_Node_List visited;
  87   return needs_barrier_impl(phase, orig, n, rb_mem, allow_fromspace, visited);
  88 }
  89 
  90 bool ShenandoahBarrierNode::needs_barrier_impl(PhaseGVN* phase, ShenandoahBarrierNode* orig, Node* n, Node* rb_mem, bool allow_fromspace, Unique_Node_List &visited) {
  91   if (visited.member(n)) {
  92     return false; // Been there.
  93   }
  94   visited.push(n);
  95 
  96   if (n->is_Allocate()) {
  97     return false;
  98   }
  99 
 100   if (n->is_Call()) {
 101     return true;
 102   }
 103 
 104   const Type* type = phase->type(n);
 105   if (type == Type::TOP) {
 106     return false;
 107   }
 108   if (type->make_ptr()->higher_equal(TypePtr::NULL_PTR)) {
 109     return false;
 110   }
 111   if (type->make_oopptr() && type->make_oopptr()->const_oop() != NULL) {
 112     return false;
 113   }
 114 
 115   if (ShenandoahOptimizeStableFinals) {
 116     const TypeAryPtr* ary = type->isa_aryptr();
 117     if (ary && ary->is_stable() && allow_fromspace) {
 118       return false;
 119     }
 120   }
 121 
 122   if (n->is_CheckCastPP() || n->is_ConstraintCast() || n->Opcode() == Op_ShenandoahEnqueueBarrier) {
 123     return needs_barrier_impl(phase, orig, n->in(1), rb_mem, allow_fromspace, visited);
 124   }
 125   if (n->is_Parm()) {
 126     return true;
 127   }
 128   if (n->is_Proj()) {
 129     return needs_barrier_impl(phase, orig, n->in(0), rb_mem, allow_fromspace, visited);
 130   }
 131 
 132   if (n->Opcode() == Op_ShenandoahWBMemProj) {
 133     return needs_barrier_impl(phase, orig, n->in(ShenandoahWBMemProjNode::WriteBarrier), rb_mem, allow_fromspace, visited);
 134   }
 135   if (n->is_Phi()) {
 136     bool need_barrier = false;
 137     for (uint i = 1; i < n->req() && ! need_barrier; i++) {
 138       Node* input = n->in(i);
 139       if (input == NULL) {
 140         need_barrier = true; // Phi not complete yet?
 141       } else if (needs_barrier_impl(phase, orig, input, rb_mem, allow_fromspace, visited)) {
 142         need_barrier = true;
 143       }
 144     }
 145     return need_barrier;
 146   }
 147   if (n->is_CMove()) {
 148     return needs_barrier_impl(phase, orig, n->in(CMoveNode::IfFalse), rb_mem, allow_fromspace, visited) ||
 149            needs_barrier_impl(phase, orig, n->in(CMoveNode::IfTrue ), rb_mem, allow_fromspace, visited);
 150   }
 151   if (n->Opcode() == Op_CreateEx) {
 152     return true;
 153   }
 154   if (n->Opcode() == Op_ShenandoahWriteBarrier) {
 155     return false;
 156   }
 157   if (n->Opcode() == Op_ShenandoahReadBarrier) {
 158     if (rb_mem == n->in(Memory)) {
 159       return false;
 160     } else {
 161       return true;
 162     }
 163   }
 164 
 165   if (n->Opcode() == Op_LoadP ||
 166       n->Opcode() == Op_LoadN ||
 167       n->Opcode() == Op_GetAndSetP ||
 168       n->Opcode() == Op_CompareAndExchangeP ||
 169       n->Opcode() == Op_ShenandoahCompareAndExchangeP ||
 170       n->Opcode() == Op_GetAndSetN ||
 171       n->Opcode() == Op_CompareAndExchangeN ||
 172       n->Opcode() == Op_ShenandoahCompareAndExchangeN) {
 173     return true;
 174   }
 175   if (n->Opcode() == Op_DecodeN ||
 176       n->Opcode() == Op_EncodeP) {
 177     return needs_barrier_impl(phase, orig, n->in(1), rb_mem, allow_fromspace, visited);
 178   }
 179 
 180 #ifdef ASSERT
 181   tty->print("need barrier on?: "); n->dump();
 182   ShouldNotReachHere();
 183 #endif
 184   return true;
 185 }
 186 
 187 bool ShenandoahReadBarrierNode::dominates_memory_rb_impl(PhaseGVN* phase,
 188                                                          Node* b1,
 189                                                          Node* b2,
 190                                                          Node* current,
 191                                                          bool linear) {
 192   ResourceMark rm;
 193   VectorSet visited(Thread::current()->resource_area());
 194   Node_Stack phis(0);
 195 
 196   for(int i = 0; i < 10; i++) {
 197     if (current == NULL) {
 198       return false;
 199     } else if (visited.test_set(current->_idx) || current->is_top() || current == b1) {
 200       current = NULL;
 201       while (phis.is_nonempty() && current == NULL) {
 202         uint idx = phis.index();
 203         Node* phi = phis.node();
 204         if (idx >= phi->req()) {
 205           phis.pop();
 206         } else {
 207           current = phi->in(idx);
 208           phis.set_index(idx+1);
 209         }
 210       }
 211       if (current == NULL) {
 212         return true;
 213       }
 214     } else if (current == phase->C->immutable_memory()) {
 215       return false;
 216     } else if (current->isa_Phi()) {
 217       if (!linear) {
 218         return false;
 219       }
 220       phis.push(current, 2);
 221       current = current->in(1);
 222     } else if (current->Opcode() == Op_ShenandoahWriteBarrier) {
 223       const Type* in_type = current->bottom_type();
 224       const Type* this_type = b2->bottom_type();
 225       if (is_independent(in_type, this_type)) {
 226         current = current->in(Memory);
 227       } else {
 228         return false;
 229       }
 230     } else if (current->Opcode() == Op_ShenandoahWBMemProj) {
 231       current = current->in(ShenandoahWBMemProjNode::WriteBarrier);
 232     } else if (current->is_Proj()) {
 233       current = current->in(0);
 234     } else if (current->is_Call()) {
 235       return false; // TODO: Maybe improve by looking at the call's memory effects?
 236     } else if (current->is_MemBar()) {
 237       return false; // TODO: Do we need to stop at *any* membar?
 238     } else if (current->is_MergeMem()) {
 239       const TypePtr* adr_type = brooks_pointer_type(phase->type(b2));
 240       uint alias_idx = phase->C->get_alias_index(adr_type);
 241       current = current->as_MergeMem()->memory_at(alias_idx);
 242     } else {
 243 #ifdef ASSERT
 244       current->dump();
 245 #endif
 246       ShouldNotReachHere();
 247       return false;
 248     }
 249   }
 250   return false;
 251 }
 252 
 253 bool ShenandoahReadBarrierNode::is_independent(Node* mem) {
 254   if (mem->is_Phi() || mem->is_Proj() || mem->is_MergeMem()) {
 255     return true;
 256   } else if (mem->Opcode() == Op_ShenandoahWBMemProj) {
 257     return true;
 258   } else if (mem->Opcode() == Op_ShenandoahWriteBarrier) {
 259     const Type* mem_type = mem->bottom_type();
 260     const Type* this_type = bottom_type();
 261     if (is_independent(mem_type, this_type)) {
 262       return true;
 263     } else {
 264       return false;
 265     }
 266   } else if (mem->is_Call() || mem->is_MemBar()) {
 267     return false;
 268   }
 269 #ifdef ASSERT
 270   mem->dump();
 271 #endif
 272   ShouldNotReachHere();
 273   return true;
 274 }
 275 
 276 bool ShenandoahReadBarrierNode::dominates_memory_rb(PhaseGVN* phase, Node* b1, Node* b2, bool linear) {
 277   return dominates_memory_rb_impl(phase, b1->in(Memory), b2, b2->in(Memory), linear);
 278 }
 279 
 280 bool ShenandoahReadBarrierNode::is_independent(const Type* in_type, const Type* this_type) {
 281   assert(in_type->isa_oopptr(), "expect oop ptr");
 282   assert(this_type->isa_oopptr(), "expect oop ptr");
 283 
 284   ciKlass* in_kls = in_type->is_oopptr()->klass();
 285   ciKlass* this_kls = this_type->is_oopptr()->klass();
 286   if (in_kls != NULL && this_kls != NULL &&
 287       in_kls->is_loaded() && this_kls->is_loaded() &&
 288       (!in_kls->is_subclass_of(this_kls)) &&
 289       (!this_kls->is_subclass_of(in_kls))) {
 290     return true;
 291   }
 292   return false;
 293 }
 294 
 295 Node* ShenandoahReadBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 296   if (! can_reshape) {
 297     return NULL;
 298   }
 299 
 300   if (in(Memory) == phase->C->immutable_memory()) return NULL;
 301 
 302   // If memory input is a MergeMem, take the appropriate slice out of it.
 303   Node* mem_in = in(Memory);
 304   if (mem_in->isa_MergeMem()) {
 305     const TypePtr* adr_type = brooks_pointer_type(bottom_type());
 306     uint alias_idx = phase->C->get_alias_index(adr_type);
 307     mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);
 308     set_req(Memory, mem_in);
 309     return this;
 310   }
 311 
 312   Node* input = in(Memory);
 313   if (input->Opcode() == Op_ShenandoahWBMemProj) {
 314     ResourceMark rm;
 315     VectorSet seen(Thread::current()->resource_area());
 316     Node* n = in(Memory);
 317     while (n->Opcode() == Op_ShenandoahWBMemProj &&
 318            n->in(ShenandoahWBMemProjNode::WriteBarrier) != NULL &&
 319            n->in(ShenandoahWBMemProjNode::WriteBarrier)->Opcode() == Op_ShenandoahWriteBarrier &&
 320            n->in(ShenandoahWBMemProjNode::WriteBarrier)->in(Memory) != NULL) {
 321       if (seen.test_set(n->_idx)) {
 322         return NULL; // loop
 323       }
 324       n = n->in(ShenandoahWBMemProjNode::WriteBarrier)->in(Memory);
 325     }
 326 
 327     Node* wb = input->in(ShenandoahWBMemProjNode::WriteBarrier);
 328     const Type* in_type = phase->type(wb);
 329     // is_top() test not sufficient here: we can come here after CCP
 330     // in a dead branch of the graph that has not yet been removed.
 331     if (in_type == Type::TOP) return NULL; // Dead path.
 332     assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "expect write barrier");
 333     if (is_independent(in_type, _type)) {
 334       phase->igvn_rehash_node_delayed(wb);
 335       set_req(Memory, wb->in(Memory));
 336       if (can_reshape && input->outcnt() == 0) {
 337         phase->is_IterGVN()->_worklist.push(input);
 338       }
 339       return this;
 340     }
 341   }
 342   return NULL;
 343 }
 344 
 345 ShenandoahWriteBarrierNode::ShenandoahWriteBarrierNode(Compile* C, Node* ctrl, Node* mem, Node* obj)
 346   : ShenandoahBarrierNode(ctrl, mem, obj, false) {
 347   assert(UseShenandoahGC && ShenandoahWriteBarrier, "should be enabled");
 348   ShenandoahBarrierSetC2::bsc2()->state()->add_shenandoah_barrier(this);
 349 }
 350 
 351 Node* ShenandoahWriteBarrierNode::Identity(PhaseGVN* phase) {
 352   assert(in(0) != NULL, "should have control");
 353   PhaseIterGVN* igvn = phase->is_IterGVN();
 354   Node* mem_in = in(Memory);
 355   Node* mem_proj = NULL;
 356 
 357   if (igvn != NULL) {
 358     mem_proj = find_out_with(Op_ShenandoahWBMemProj);
 359     if (mem_in == mem_proj) {
 360       return this;
 361     }
 362   }
 363 
 364   Node* replacement = Identity_impl(phase);
 365   if (igvn != NULL) {
 366     if (replacement != NULL && replacement != this && mem_proj != NULL) {
 367       igvn->replace_node(mem_proj, mem_in);
 368     }
 369   }
 370   return replacement;
 371 }
 372 
 373 Node* ShenandoahWriteBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 374   assert(in(0) != NULL, "should have control");
 375   if (!can_reshape) {
 376     return NULL;
 377   }
 378 
 379   Node* mem_in = in(Memory);
 380 
 381   if (mem_in->isa_MergeMem()) {
 382     const TypePtr* adr_type = brooks_pointer_type(bottom_type());
 383     uint alias_idx = phase->C->get_alias_index(adr_type);
 384     mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);
 385     set_req(Memory, mem_in);
 386     return this;
 387   }
 388 
 389   Node* val = in(ValueIn);
 390   if (val->is_ShenandoahBarrier()) {
 391     set_req(ValueIn, val->in(ValueIn));
 392     return this;
 393   }
 394 
 395   return NULL;
 396 }
 397 
 398 bool ShenandoahWriteBarrierNode::expand(Compile* C, PhaseIterGVN& igvn) {
 399   if (UseShenandoahGC) {
 400     if (ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count() > 0 || (!ShenandoahWriteBarrier && ShenandoahStoreValEnqueueBarrier)) {
 401       bool attempt_more_loopopts = ShenandoahLoopOptsAfterExpansion;
 402       C->clear_major_progress();
 403       PhaseIdealLoop ideal_loop(igvn, LoopOptsShenandoahExpand);
 404       if (C->failing()) return false;
 405       PhaseIdealLoop::verify(igvn);
 406       DEBUG_ONLY(ShenandoahBarrierNode::verify_raw_mem(C->root());)
 407       if (attempt_more_loopopts) {
 408         C->set_major_progress();
 409         if (!C->optimize_loops(igvn, LoopOptsShenandoahPostExpand)) {
 410           return false;
 411         }
 412         C->clear_major_progress();
 413       }
 414     }
 415   }
 416   return true;
 417 }
 418 
 419 bool ShenandoahWriteBarrierNode::is_heap_state_test(Node* iff, int mask) {
 420   if (!UseShenandoahGC) {
 421     return false;
 422   }
 423   assert(iff->is_If(), "bad input");
 424   if (iff->Opcode() != Op_If) {
 425     return false;
 426   }
 427   Node* bol = iff->in(1);
 428   if (!bol->is_Bool() || bol->as_Bool()->_test._test != BoolTest::ne) {
 429     return false;
 430   }
 431   Node* cmp = bol->in(1);
 432   if (cmp->Opcode() != Op_CmpI) {
 433     return false;
 434   }
 435   Node* in1 = cmp->in(1);
 436   Node* in2 = cmp->in(2);
 437   if (in2->find_int_con(-1) != 0) {
 438     return false;
 439   }
 440   if (in1->Opcode() != Op_AndI) {
 441     return false;
 442   }
 443   in2 = in1->in(2);
 444   if (in2->find_int_con(-1) != mask) {
 445     return false;
 446   }
 447   in1 = in1->in(1);
 448 
 449   return is_gc_state_load(in1);
 450 }
 451 
 452 bool ShenandoahWriteBarrierNode::is_heap_stable_test(Node* iff) {
 453   return is_heap_state_test(iff, ShenandoahHeap::HAS_FORWARDED);
 454 }
 455 
 456 bool ShenandoahWriteBarrierNode::is_gc_state_load(Node *n) {
 457   if (!UseShenandoahGC) {
 458     return false;
 459   }
 460   if (n->Opcode() != Op_LoadB && n->Opcode() != Op_LoadUB) {
 461     return false;
 462   }
 463   Node* addp = n->in(MemNode::Address);
 464   if (!addp->is_AddP()) {
 465     return false;
 466   }
 467   Node* base = addp->in(AddPNode::Address);
 468   Node* off = addp->in(AddPNode::Offset);
 469   if (base->Opcode() != Op_ThreadLocal) {
 470     return false;
 471   }
 472   if (off->find_intptr_t_con(-1) != in_bytes(ShenandoahThreadLocalData::gc_state_offset())) {
 473     return false;
 474   }
 475   return true;
 476 }
 477 
 478 bool ShenandoahWriteBarrierNode::has_safepoint_between(Node* start, Node* stop, PhaseIdealLoop *phase) {
 479   assert(phase->is_dominator(stop, start), "bad inputs");
 480   ResourceMark rm;
 481   Unique_Node_List wq;
 482   wq.push(start);
 483   for (uint next = 0; next < wq.size(); next++) {
 484     Node *m = wq.at(next);
 485     if (m == stop) {
 486       continue;
 487     }
 488     if (m->is_SafePoint() && !m->is_CallLeaf()) {
 489       return true;
 490     }
 491     if (m->is_Region()) {
 492       for (uint i = 1; i < m->req(); i++) {
 493         wq.push(m->in(i));
 494       }
 495     } else {
 496       wq.push(m->in(0));
 497     }
 498   }
 499   return false;
 500 }
 501 
 502 bool ShenandoahWriteBarrierNode::try_common_gc_state_load(Node *n, PhaseIdealLoop *phase) {
 503   assert(is_gc_state_load(n), "inconsistent");
 504   Node* addp = n->in(MemNode::Address);
 505   Node* dominator = NULL;
 506   for (DUIterator_Fast imax, i = addp->fast_outs(imax); i < imax; i++) {
 507     Node* u = addp->fast_out(i);
 508     assert(is_gc_state_load(u), "inconsistent");
 509     if (u != n && phase->is_dominator(u->in(0), n->in(0))) {
 510       if (dominator == NULL) {
 511         dominator = u;
 512       } else {
 513         if (phase->dom_depth(u->in(0)) < phase->dom_depth(dominator->in(0))) {
 514           dominator = u;
 515         }
 516       }
 517     }
 518   }
 519   if (dominator == NULL || has_safepoint_between(n->in(0), dominator->in(0), phase)) {
 520     return false;
 521   }
 522   phase->igvn().replace_node(n, dominator);
 523 
 524   return true;
 525 }
 526 
 527 bool ShenandoahBarrierNode::dominates_memory_impl(PhaseGVN* phase,
 528                                                   Node* b1,
 529                                                   Node* b2,
 530                                                   Node* current,
 531                                                   bool linear) {
 532   ResourceMark rm;
 533   VectorSet visited(Thread::current()->resource_area());
 534   Node_Stack phis(0);
 535 
 536   for(int i = 0; i < 10; i++) {
 537     if (current == NULL) {
 538       return false;
 539     } else if (visited.test_set(current->_idx) || current->is_top() || current == b1) {
 540       current = NULL;
 541       while (phis.is_nonempty() && current == NULL) {
 542         uint idx = phis.index();
 543         Node* phi = phis.node();
 544         if (idx >= phi->req()) {
 545           phis.pop();
 546         } else {
 547           current = phi->in(idx);
 548           phis.set_index(idx+1);
 549         }
 550       }
 551       if (current == NULL) {
 552         return true;
 553       }
 554     } else if (current == b2) {
 555       return false;
 556     } else if (current == phase->C->immutable_memory()) {
 557       return false;
 558     } else if (current->isa_Phi()) {
 559       if (!linear) {
 560         return false;
 561       }
 562       phis.push(current, 2);
 563       current = current->in(1);
 564     } else if (current->Opcode() == Op_ShenandoahWriteBarrier) {
 565       current = current->in(Memory);
 566     } else if (current->Opcode() == Op_ShenandoahWBMemProj) {
 567       current = current->in(ShenandoahWBMemProjNode::WriteBarrier);
 568     } else if (current->is_Proj()) {
 569       current = current->in(0);
 570     } else if (current->is_Call()) {
 571       current = current->in(TypeFunc::Memory);
 572     } else if (current->is_MemBar()) {
 573       current = current->in(TypeFunc::Memory);
 574     } else if (current->is_MergeMem()) {
 575       const TypePtr* adr_type = brooks_pointer_type(phase->type(b2));
 576       uint alias_idx = phase->C->get_alias_index(adr_type);
 577       current = current->as_MergeMem()->memory_at(alias_idx);
 578     } else {
 579 #ifdef ASSERT
 580       current->dump();
 581 #endif
 582       ShouldNotReachHere();
 583       return false;
 584     }
 585   }
 586   return false;
 587 }
 588 
 589 /**
 590  * Determines if b1 dominates b2 through memory inputs. It returns true if:
 591  * - b1 can be reached by following each branch in b2's memory input (through phis, etc)
 592  * - or we get back to b2 (i.e. through a loop) without seeing b1
 593  * In all other cases, (in particular, if we reach immutable_memory without having seen b1)
 594  * we return false.
 595  */
 596 bool ShenandoahBarrierNode::dominates_memory(PhaseGVN* phase, Node* b1, Node* b2, bool linear) {
 597   return dominates_memory_impl(phase, b1, b2, b2->in(Memory), linear);
 598 }
 599 
 600 Node* ShenandoahBarrierNode::Identity_impl(PhaseGVN* phase) {
 601   Node* n = in(ValueIn);
 602 
 603   Node* rb_mem = Opcode() == Op_ShenandoahReadBarrier ? in(Memory) : NULL;
 604   if (! needs_barrier(phase, this, n, rb_mem, _allow_fromspace)) {
 605     return n;
 606   }
 607 
 608   // Try to find a write barrier sibling with identical inputs that we can fold into.
 609   for (DUIterator i = n->outs(); n->has_out(i); i++) {
 610     Node* sibling = n->out(i);
 611     if (sibling == this) {
 612       continue;
 613     }
 614     if (sibling->Opcode() != Op_ShenandoahWriteBarrier) {
 615       continue;
 616     }
 617 
 618     assert(sibling->in(ValueIn) == in(ValueIn), "sanity");
 619     assert(sibling->Opcode() == Op_ShenandoahWriteBarrier, "sanity");
 620 
 621     if (dominates_memory(phase, sibling, this, phase->is_IterGVN() == NULL)) {
 622       return sibling;
 623     }
 624   }
 625   return this;
 626 }
 627 
 628 #ifndef PRODUCT
 629 void ShenandoahBarrierNode::dump_spec(outputStream *st) const {
 630   const TypePtr* adr = adr_type();
 631   if (adr == NULL) {
 632     return;
 633   }
 634   st->print(" @");
 635   adr->dump_on(st);
 636   st->print(" (");
 637   Compile::current()->alias_type(adr)->adr_type()->dump_on(st);
 638   st->print(") ");
 639 }
 640 #endif
 641 
 642 Node* ShenandoahReadBarrierNode::Identity(PhaseGVN* phase) {
 643   Node* id = Identity_impl(phase);
 644 
 645   if (id == this && phase->is_IterGVN()) {
 646     Node* n = in(ValueIn);
 647     // No success in super call. Try to combine identical read barriers.
 648     for (DUIterator i = n->outs(); n->has_out(i); i++) {
 649       Node* sibling = n->out(i);
 650       if (sibling == this || sibling->Opcode() != Op_ShenandoahReadBarrier) {
 651         continue;
 652       }
 653       assert(sibling->in(ValueIn)  == in(ValueIn), "sanity");
 654       if (phase->is_IterGVN()->hash_find(sibling) &&
 655           sibling->bottom_type() == bottom_type() &&
 656           sibling->in(Control) == in(Control) &&
 657           dominates_memory_rb(phase, sibling, this, phase->is_IterGVN() == NULL)) {
 658         return sibling;
 659       }
 660     }
 661   }
 662   return id;
 663 }
 664 
 665 const Type* ShenandoahBarrierNode::Value(PhaseGVN* phase) const {
 666   // Either input is TOP ==> the result is TOP
 667   const Type *t1 = phase->type(in(Memory));
 668   if (t1 == Type::TOP) return Type::TOP;
 669   const Type *t2 = phase->type(in(ValueIn));
 670   if( t2 == Type::TOP ) return Type::TOP;
 671 
 672   if (t2 == TypePtr::NULL_PTR) {
 673     return _type;
 674   }
 675 
 676   const Type* type = t2->is_oopptr()->cast_to_nonconst();
 677   return type;
 678 }
 679 
 680 uint ShenandoahBarrierNode::hash() const {
 681   return TypeNode::hash() + _allow_fromspace;
 682 }
 683 
 684 uint ShenandoahBarrierNode::cmp(const Node& n) const {
 685   return _allow_fromspace == ((ShenandoahBarrierNode&) n)._allow_fromspace
 686     && TypeNode::cmp(n);
 687 }
 688 
 689 uint ShenandoahBarrierNode::size_of() const {
 690   return sizeof(*this);
 691 }
 692 
 693 Node* ShenandoahWBMemProjNode::Identity(PhaseGVN* phase) {
 694   Node* wb = in(WriteBarrier);
 695   if (wb->is_top()) return phase->C->top(); // Dead path.
 696 
 697   assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "expect write barrier");
 698   PhaseIterGVN* igvn = phase->is_IterGVN();
 699   // We can't do the below unless the graph is fully constructed.
 700   if (igvn == NULL) {
 701     return this;
 702   }
 703 
 704   // If the mem projection has no barrier users, it's not needed anymore.
 705   if (wb->outcnt() == 1) {
 706     return wb->in(ShenandoahBarrierNode::Memory);
 707   }
 708 
 709   return this;
 710 }
 711 
 712 #ifdef ASSERT
 713 bool ShenandoahBarrierNode::verify_helper(Node* in, Node_Stack& phis, VectorSet& visited, verify_type t, bool trace, Unique_Node_List& barriers_used) {
 714   assert(phis.size() == 0, "");
 715 
 716   while (true) {
 717     if (in->bottom_type() == TypePtr::NULL_PTR) {
 718       if (trace) {tty->print_cr("NULL");}
 719     } else if (!in->bottom_type()->make_ptr()->make_oopptr()) {
 720       if (trace) {tty->print_cr("Non oop");}
 721     } else if (t == ShenandoahLoad && ShenandoahOptimizeStableFinals &&
 722                in->bottom_type()->make_ptr()->isa_aryptr() &&
 723                in->bottom_type()->make_ptr()->is_aryptr()->is_stable()) {
 724       if (trace) {tty->print_cr("Stable array load");}
 725     } else {
 726       if (in->is_ConstraintCast()) {
 727         in = in->in(1);
 728         continue;
 729       } else if (in->is_AddP()) {
 730         assert(!in->in(AddPNode::Address)->is_top(), "no raw memory access");
 731         in = in->in(AddPNode::Address);
 732         continue;
 733       } else if (in->is_Con()) {
 734         if (trace) {tty->print("Found constant"); in->dump();}
 735       } else if (in->is_ShenandoahBarrier()) {















 736         if (t == ShenandoahOopStore) {
 737           if (in->Opcode() != Op_ShenandoahWriteBarrier) {
 738             return false;
 739           }
 740           uint i = 0;
 741           for (; i < phis.size(); i++) {
 742             Node* n = phis.node_at(i);
 743             if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
 744               break;
 745             }
 746           }
 747           if (i == phis.size()) {
 748             return false;
 749           }
 750         } else if (t == ShenandoahStore && in->Opcode() != Op_ShenandoahWriteBarrier) {
 751           return false;
 752         }
 753         barriers_used.push(in);
 754         if (trace) {tty->print("Found barrier"); in->dump();}
 755       } else if (in->Opcode() == Op_ShenandoahEnqueueBarrier) {
 756         if (t != ShenandoahOopStore) {
 757           in = in->in(1);
 758           continue;
 759         }
 760         if (trace) {tty->print("Found enqueue barrier"); in->dump();}
 761         phis.push(in, in->req());
 762         in = in->in(1);
 763         continue;
 764       } else if (in->is_Proj() && in->in(0)->is_Allocate()) {
 765         if (trace) {tty->print("Found alloc"); in->in(0)->dump();}







 766       } else if (in->is_Phi()) {
 767         if (!visited.test_set(in->_idx)) {
 768           if (trace) {tty->print("Pushed phi:"); in->dump();}
 769           phis.push(in, 2);
 770           in = in->in(1);
 771           continue;
 772         }
 773         if (trace) {tty->print("Already seen phi:"); in->dump();}
 774       } else if (in->Opcode() == Op_CMoveP || in->Opcode() == Op_CMoveN) {
 775         if (!visited.test_set(in->_idx)) {
 776           if (trace) {tty->print("Pushed cmovep:"); in->dump();}
 777           phis.push(in, CMoveNode::IfTrue);
 778           in = in->in(CMoveNode::IfFalse);
 779           continue;
 780         }
 781         if (trace) {tty->print("Already seen cmovep:"); in->dump();}
 782       } else if (in->Opcode() == Op_EncodeP || in->Opcode() == Op_DecodeN) {
 783         in = in->in(1);
 784         continue;
 785       } else {


 791       uint idx = phis.index();
 792       Node* phi = phis.node();
 793       if (idx >= phi->req()) {
 794         if (trace) {tty->print("Popped phi:"); phi->dump();}
 795         phis.pop();
 796         continue;
 797       }
 798       if (trace) {tty->print("Next entry(%d) for phi:", idx); phi->dump();}
 799       in = phi->in(idx);
 800       phis.set_index(idx+1);
 801       cont = true;
 802       break;
 803     }
 804     if (!cont) {
 805       break;
 806     }
 807   }
 808   return true;
 809 }
 810 
 811 void ShenandoahBarrierNode::report_verify_failure(const char *msg, Node *n1, Node *n2) {
 812   if (n1 != NULL) {
 813     n1->dump(+10);
 814   }
 815   if (n2 != NULL) {
 816     n2->dump(+10);
 817   }
 818   fatal("%s", msg);
 819 }
 820 
 821 void ShenandoahBarrierNode::verify(RootNode* root) {
 822   ResourceMark rm;
 823   Unique_Node_List wq;
 824   GrowableArray<Node*> barriers;
 825   Unique_Node_List barriers_used;
 826   Node_Stack phis(0);
 827   VectorSet visited(Thread::current()->resource_area());
 828   const bool trace = false;
 829   const bool verify_no_useless_barrier = false;
 830 
 831   wq.push(root);
 832   for (uint next = 0; next < wq.size(); next++) {
 833     Node *n = wq.at(next);
 834     if (n->is_Load()) {
 835       const bool trace = false;
 836       if (trace) {tty->print("Verifying"); n->dump();}
 837       if (n->Opcode() == Op_LoadRange || n->Opcode() == Op_LoadKlass || n->Opcode() == Op_LoadNKlass) {
 838         if (trace) {tty->print_cr("Load range/klass");}
 839       } else {
 840         const TypePtr* adr_type = n->as_Load()->adr_type();
 841 


 853             assert(k->is_instance_klass(), "");
 854             ciInstanceKlass* ik = (ciInstanceKlass*)k;
 855             int offset = adr_type->offset();
 856 
 857             if ((ik->debug_final_field_at(offset) && ShenandoahOptimizeInstanceFinals) ||
 858                 (ik->debug_stable_field_at(offset) && ShenandoahOptimizeStableFinals)) {
 859               if (trace) {tty->print_cr("Final/stable");}
 860               verify = false;
 861             } else if (k == ciEnv::current()->Class_klass() &&
 862                        tinst->const_oop() != NULL &&
 863                        tinst->offset() >= (ik->size_helper() * wordSize)) {
 864               ciInstanceKlass* k = tinst->const_oop()->as_instance()->java_lang_Class_klass()->as_instance_klass();
 865               ciField* field = k->get_field_by_offset(tinst->offset(), true);
 866               if ((ShenandoahOptimizeStaticFinals && field->is_final()) ||
 867                   (ShenandoahOptimizeStableFinals && field->is_stable())) {
 868                 verify = false;
 869               }
 870             }
 871           }
 872 
 873           if (verify && !ShenandoahBarrierNode::verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahLoad, trace, barriers_used)) {
 874             report_verify_failure("Shenandoah verification: Load should have barriers", n);
 875           }
 876         }
 877       }
 878     } else if (n->is_Store()) {
 879       const bool trace = false;
 880 
 881       if (trace) {tty->print("Verifying"); n->dump();}
 882       if (n->in(MemNode::ValueIn)->bottom_type()->make_oopptr()) {
 883         Node* adr = n->in(MemNode::Address);
 884         bool verify = true;
 885 
 886         if (adr->is_AddP() && adr->in(AddPNode::Base)->is_top()) {
 887           adr = adr->in(AddPNode::Address);
 888           if (adr->is_AddP()) {
 889             assert(adr->in(AddPNode::Base)->is_top(), "");
 890             adr = adr->in(AddPNode::Address);
 891             if (adr->Opcode() == Op_LoadP &&
 892                 adr->in(MemNode::Address)->in(AddPNode::Base)->is_top() &&
 893                 adr->in(MemNode::Address)->in(AddPNode::Address)->Opcode() == Op_ThreadLocal &&
 894                 adr->in(MemNode::Address)->in(AddPNode::Offset)->find_intptr_t_con(-1) == in_bytes(ShenandoahThreadLocalData::satb_mark_queue_buffer_offset())) {
 895               if (trace) {tty->print_cr("SATB prebarrier");}
 896               verify = false;
 897             }
 898           }
 899         }
 900 
 901         if (verify && !ShenandoahBarrierNode::verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahStoreValEnqueueBarrier ? ShenandoahOopStore : ShenandoahValue, trace, barriers_used)) {
 902           report_verify_failure("Shenandoah verification: Store should have barriers", n);
 903         }
 904       }
 905       if (!ShenandoahBarrierNode::verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 906         report_verify_failure("Shenandoah verification: Store (address) should have barriers", n);
 907       }
 908     } else if (n->Opcode() == Op_CmpP) {
 909       const bool trace = false;
 910 
 911       Node* in1 = n->in(1);
 912       Node* in2 = n->in(2);
 913       if (in1->bottom_type()->isa_oopptr()) {
 914         if (trace) {tty->print("Verifying"); n->dump();}
 915 
 916         bool mark_inputs = false;
 917         if (in1->bottom_type() == TypePtr::NULL_PTR || in2->bottom_type() == TypePtr::NULL_PTR ||
 918             (in1->is_Con() || in2->is_Con())) {
 919           if (trace) {tty->print_cr("Comparison against a constant");}
 920           mark_inputs = true;
 921         } else if ((in1->is_CheckCastPP() && in1->in(1)->is_Proj() && in1->in(1)->in(0)->is_Allocate()) ||
 922                    (in2->is_CheckCastPP() && in2->in(1)->is_Proj() && in2->in(1)->in(0)->is_Allocate())) {
 923           if (trace) {tty->print_cr("Comparison with newly alloc'ed object");}
 924           mark_inputs = true;
 925         } else {
 926           assert(in2->bottom_type()->isa_oopptr(), "");
 927 
 928           if (!ShenandoahBarrierNode::verify_helper(in1, phis, visited, ShenandoahStore, trace, barriers_used) ||
 929               !ShenandoahBarrierNode::verify_helper(in2, phis, visited, ShenandoahStore, trace, barriers_used)) {
 930             report_verify_failure("Shenandoah verification: Cmp should have barriers", n);
 931           }
 932         }
 933         if (verify_no_useless_barrier &&
 934             mark_inputs &&
 935             (!ShenandoahBarrierNode::verify_helper(in1, phis, visited, ShenandoahValue, trace, barriers_used) ||
 936              !ShenandoahBarrierNode::verify_helper(in2, phis, visited, ShenandoahValue, trace, barriers_used))) {
 937           phis.clear();
 938           visited.Reset();
 939         }
 940       }
 941     } else if (n->is_LoadStore()) {
 942       if (n->in(MemNode::ValueIn)->bottom_type()->make_ptr() &&
 943           !ShenandoahBarrierNode::verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahStoreValEnqueueBarrier ? ShenandoahOopStore : ShenandoahValue, trace, barriers_used)) {
 944         report_verify_failure("Shenandoah verification: LoadStore (value) should have barriers", n);
 945       }
 946 
 947       if (n->in(MemNode::Address)->bottom_type()->make_oopptr() && !ShenandoahBarrierNode::verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 948         report_verify_failure("Shenandoah verification: LoadStore (address) should have barriers", n);
 949       }
 950     } else if (n->Opcode() == Op_CallLeafNoFP || n->Opcode() == Op_CallLeaf) {
 951       CallNode* call = n->as_Call();
 952 
 953       static struct {
 954         const char* name;
 955         struct {
 956           int pos;
 957           verify_type t;
 958         } args[6];
 959       } calls[] = {
 960         "aescrypt_encryptBlock",
 961         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 962           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 963         "aescrypt_decryptBlock",
 964         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 965           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 966         "multiplyToLen",
 967         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },   { TypeFunc::Parms+4, ShenandoahStore },


1023         "sha512_implCompressMB",
1024         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
1025           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1026         "encodeBlock",
1027         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+3, ShenandoahStore },   { -1, ShenandoahNone },
1028           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1029       };
1030 
1031       if (call->is_call_to_arraycopystub()) {
1032         Node* dest = NULL;
1033         const TypeTuple* args = n->as_Call()->_tf->domain();
1034         for (uint i = TypeFunc::Parms, j = 0; i < args->cnt(); i++) {
1035           if (args->field_at(i)->isa_ptr()) {
1036             j++;
1037             if (j == 2) {
1038               dest = n->in(i);
1039               break;
1040             }
1041           }
1042         }
1043         if (!ShenandoahBarrierNode::verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahLoad, trace, barriers_used) ||
1044             !ShenandoahBarrierNode::verify_helper(dest, phis, visited, ShenandoahStore, trace, barriers_used)) {
1045           report_verify_failure("Shenandoah verification: ArrayCopy should have barriers", n);
1046         }
1047       } else if (strlen(call->_name) > 5 &&
1048                  !strcmp(call->_name + strlen(call->_name) - 5, "_fill")) {
1049         if (!ShenandoahBarrierNode::verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahStore, trace, barriers_used)) {
1050           report_verify_failure("Shenandoah verification: _fill should have barriers", n);
1051         }
1052       } else if (!strcmp(call->_name, "shenandoah_wb_pre")) {
1053         // skip
1054       } else {
1055         const int calls_len = sizeof(calls) / sizeof(calls[0]);
1056         int i = 0;
1057         for (; i < calls_len; i++) {
1058           if (!strcmp(calls[i].name, call->_name)) {
1059             break;
1060           }
1061         }
1062         if (i != calls_len) {
1063           const uint args_len = sizeof(calls[0].args) / sizeof(calls[0].args[0]);
1064           for (uint j = 0; j < args_len; j++) {
1065             int pos = calls[i].args[j].pos;
1066             if (pos == -1) {
1067               break;
1068             }
1069             if (!ShenandoahBarrierNode::verify_helper(call->in(pos), phis, visited, calls[i].args[j].t, trace, barriers_used)) {
1070               report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
1071             }
1072           }
1073           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
1074             if (call->in(j)->bottom_type()->make_ptr() &&
1075                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
1076               uint k = 0;
1077               for (; k < args_len && calls[i].args[k].pos != (int)j; k++);
1078               if (k == args_len) {
1079                 fatal("arg %d for call %s not covered", j, call->_name);
1080               }
1081             }
1082           }
1083         } else {
1084           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
1085             if (call->in(j)->bottom_type()->make_ptr() &&
1086                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
1087               fatal("%s not covered", call->_name);
1088             }
1089           }
1090         }
1091       }
1092     } else if (n->is_ShenandoahBarrier()) {
1093       assert(!barriers.contains(n), "");
1094       assert(n->Opcode() != Op_ShenandoahWriteBarrier || n->find_out_with(Op_ShenandoahWBMemProj) != NULL, "bad shenandoah write barrier");
1095       assert(n->Opcode() != Op_ShenandoahWriteBarrier || n->outcnt() > 1, "bad shenandoah write barrier");
1096       barriers.push(n);
1097     } else if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
1098       // skip
1099     } else if (n->Opcode() == Op_ShenandoahWBMemProj) {
1100       assert(n->in(0) == NULL && n->in(ShenandoahWBMemProjNode::WriteBarrier)->Opcode() == Op_ShenandoahWriteBarrier, "strange ShenandoahWBMemProj");
1101     } else if (n->is_AddP()
1102                || n->is_Phi()
1103                || n->is_ConstraintCast()
1104                || n->Opcode() == Op_Return
1105                || n->Opcode() == Op_CMoveP
1106                || n->Opcode() == Op_CMoveN
1107                || n->Opcode() == Op_Rethrow
1108                || n->is_MemBar()
1109                || n->Opcode() == Op_Conv2B
1110                || n->Opcode() == Op_SafePoint
1111                || n->is_CallJava()
1112                || n->Opcode() == Op_Unlock
1113                || n->Opcode() == Op_EncodeP
1114                || n->Opcode() == Op_DecodeN) {
1115       // nothing to do
1116     } else {
1117       static struct {
1118         int opcode;
1119         struct {
1120           int pos;


1147         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
1148         Op_StrIndexOfChar,
1149         { { 2, ShenandoahLoad },                  { -1, ShenandoahNone } },
1150       };
1151 
1152       const int others_len = sizeof(others) / sizeof(others[0]);
1153       int i = 0;
1154       for (; i < others_len; i++) {
1155         if (others[i].opcode == n->Opcode()) {
1156           break;
1157         }
1158       }
1159       uint stop = n->is_Call() ? n->as_Call()->tf()->domain()->cnt() : n->req();
1160       if (i != others_len) {
1161         const uint inputs_len = sizeof(others[0].inputs) / sizeof(others[0].inputs[0]);
1162         for (uint j = 0; j < inputs_len; j++) {
1163           int pos = others[i].inputs[j].pos;
1164           if (pos == -1) {
1165             break;
1166           }
1167           if (!ShenandoahBarrierNode::verify_helper(n->in(pos), phis, visited, others[i].inputs[j].t, trace, barriers_used)) {
1168             report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
1169           }
1170         }
1171         for (uint j = 1; j < stop; j++) {
1172           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
1173               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
1174             uint k = 0;
1175             for (; k < inputs_len && others[i].inputs[k].pos != (int)j; k++);
1176             if (k == inputs_len) {
1177               fatal("arg %d for node %s not covered", j, n->Name());
1178             }
1179           }
1180         }
1181       } else {
1182         for (uint j = 1; j < stop; j++) {
1183           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
1184               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
1185             fatal("%s not covered", n->Name());
1186           }
1187         }
1188       }
1189     }
1190 
1191     if (n->is_SafePoint()) {
1192       SafePointNode* sfpt = n->as_SafePoint();
1193       if (verify_no_useless_barrier && sfpt->jvms() != NULL) {
1194         for (uint i = sfpt->jvms()->scloff(); i < sfpt->jvms()->endoff(); i++) {
1195           if (!ShenandoahBarrierNode::verify_helper(sfpt->in(i), phis, visited, ShenandoahLoad, trace, barriers_used)) {
1196             phis.clear();
1197             visited.Reset();
1198           }
1199         }
1200       }
1201     }
1202     for( uint i = 0; i < n->len(); ++i ) {
1203       Node *m = n->in(i);
1204       if (m == NULL) continue;
1205 
1206       // In most cases, inputs should be known to be non null. If it's
1207       // not the case, it could be a missing cast_not_null() in an
1208       // intrinsic or support might be needed in AddPNode::Ideal() to
1209       // avoid a NULL+offset input.
1210       if (!(n->is_Phi() ||
1211             (n->is_SafePoint() && (!n->is_CallRuntime() || !strcmp(n->as_Call()->_name, "shenandoah_wb_pre") || !strcmp(n->as_Call()->_name, "unsafe_arraycopy"))) ||
1212             n->Opcode() == Op_CmpP ||
1213             n->Opcode() == Op_CmpN ||
1214             (n->Opcode() == Op_StoreP && i == StoreNode::ValueIn) ||
1215             (n->Opcode() == Op_StoreN && i == StoreNode::ValueIn) ||
1216             n->is_ConstraintCast() ||
1217             n->Opcode() == Op_Return ||
1218             n->Opcode() == Op_Conv2B ||
1219             n->is_AddP() ||
1220             n->Opcode() == Op_CMoveP ||
1221             n->Opcode() == Op_CMoveN ||
1222             n->Opcode() == Op_Rethrow ||
1223             n->is_MemBar() ||
1224             n->is_Mem() ||
1225             n->Opcode() == Op_AryEq ||
1226             n->Opcode() == Op_SCMemProj ||
1227             n->Opcode() == Op_EncodeP ||
1228             n->Opcode() == Op_DecodeN ||
1229             n->Opcode() == Op_ShenandoahWriteBarrier ||
1230             n->Opcode() == Op_ShenandoahWBMemProj ||
1231             n->Opcode() == Op_ShenandoahEnqueueBarrier)) {
1232         if (m->bottom_type()->make_oopptr() && m->bottom_type()->make_oopptr()->meet(TypePtr::NULL_PTR) == m->bottom_type()) {
1233           report_verify_failure("Shenandoah verification: null input", n, m);
1234         }
1235       }
1236 
1237       wq.push(m);
1238     }
1239   }
1240 
1241   if (verify_no_useless_barrier) {
1242     for (int i = 0; i < barriers.length(); i++) {
1243       Node* n = barriers.at(i);
1244       if (!barriers_used.member(n)) {
1245         tty->print("XXX useless barrier"); n->dump(-2);
1246         ShouldNotReachHere();
1247       }
1248     }
1249   }
1250 }
1251 #endif
1252 
1253 bool ShenandoahBarrierNode::is_dominator_same_ctrl(Node*c, Node* d, Node* n, PhaseIdealLoop* phase) {
1254   // That both nodes have the same control is not sufficient to prove
1255   // domination, verify that there's no path from d to n
1256   ResourceMark rm;
1257   Unique_Node_List wq;
1258   wq.push(d);
1259   for (uint next = 0; next < wq.size(); next++) {
1260     Node *m = wq.at(next);
1261     if (m == n) {
1262       return false;
1263     }
1264     if (m->is_Phi() && m->in(0)->is_Loop()) {
1265       assert(phase->ctrl_or_self(m->in(LoopNode::EntryControl)) != c, "following loop entry should lead to new control");
1266     } else {
1267       for (uint i = 0; i < m->req(); i++) {
1268         if (m->in(i) != NULL && phase->ctrl_or_self(m->in(i)) == c) {
1269           wq.push(m->in(i));
1270         }
1271       }
1272     }
1273   }
1274   return true;
1275 }
1276 
1277 bool ShenandoahBarrierNode::is_dominator(Node *d_c, Node *n_c, Node* d, Node* n, PhaseIdealLoop* phase) {
1278   if (d_c != n_c) {
1279     return phase->is_dominator(d_c, n_c);
1280   }
1281   return is_dominator_same_ctrl(d_c, d, n, phase);
1282 }
1283 
1284 Node* next_mem(Node* mem, int alias) {
1285   Node* res = NULL;
1286   if (mem->is_Proj()) {
1287     res = mem->in(0);
1288   } else if (mem->is_SafePoint() || mem->is_MemBar()) {
1289     res = mem->in(TypeFunc::Memory);
1290   } else if (mem->is_Phi()) {
1291     res = mem->in(1);
1292   } else if (mem->is_ShenandoahBarrier()) {
1293     res = mem->in(ShenandoahBarrierNode::Memory);
1294   } else if (mem->is_MergeMem()) {
1295     res = mem->as_MergeMem()->memory_at(alias);
1296   } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
1297     assert(alias = Compile::AliasIdxRaw, "following raw memory can't lead to a barrier");
1298     res = mem->in(MemNode::Memory);
1299   } else if (mem->Opcode() == Op_ShenandoahWBMemProj) {
1300     res = mem->in(ShenandoahWBMemProjNode::WriteBarrier);
1301   } else {
1302 #ifdef ASSERT
1303     mem->dump();
1304 #endif
1305     ShouldNotReachHere();
1306   }
1307   return res;
1308 }
1309 
1310 Node* ShenandoahBarrierNode::no_branches(Node* c, Node* dom, bool allow_one_proj, PhaseIdealLoop* phase) {
1311   Node* iffproj = NULL;
1312   while (c != dom) {
1313     Node* next = phase->idom(c);
1314     assert(next->unique_ctrl_out() == c || c->is_Proj() || c->is_Region(), "multiple control flow out but no proj or region?");
1315     if (c->is_Region()) {
1316       ResourceMark rm;
1317       Unique_Node_List wq;
1318       wq.push(c);
1319       for (uint i = 0; i < wq.size(); i++) {
1320         Node *n = wq.at(i);
1321         if (n == next) {
1322           continue;
1323         }
1324         if (n->is_Region()) {
1325           for (uint j = 1; j < n->req(); j++) {
1326             wq.push(n->in(j));
1327           }
1328         } else {
1329           wq.push(n->in(0));
1330         }


1355             iffproj = c;
1356           } else {
1357             return NodeSentinel;
1358           }
1359         }
1360       } else if (c->Opcode() == Op_JumpProj) {
1361         return NodeSentinel; // unsupported
1362       } else if (c->Opcode() == Op_CatchProj) {
1363         return NodeSentinel; // unsupported
1364       } else if (c->Opcode() == Op_CProj && next->Opcode() == Op_NeverBranch) {
1365         return NodeSentinel; // unsupported
1366       } else {
1367         assert(next->unique_ctrl_out() == c, "unsupported branch pattern");
1368       }
1369     }
1370     c = next;
1371   }
1372   return iffproj;
1373 }
1374 
1375 bool ShenandoahBarrierNode::build_loop_late_post(PhaseIdealLoop* phase, Node* n) {
1376   if (n->Opcode() == Op_ShenandoahReadBarrier ||
1377       n->Opcode() == Op_ShenandoahWriteBarrier ||
1378       n->Opcode() == Op_ShenandoahWBMemProj) {
1379 
1380     phase->build_loop_late_post_work(n, false);
1381 
1382     if (n->Opcode() == Op_ShenandoahWriteBarrier) {
1383       // The write barrier and its memory proj must have the same
1384       // control otherwise some loop opts could put nodes (Phis) between
1385       // them
1386       Node* proj = n->find_out_with(Op_ShenandoahWBMemProj);
1387       if (proj != NULL) {
1388         phase->set_ctrl_and_loop(proj, phase->get_ctrl(n));
1389       }
1390     }
1391     return true;
1392   }
1393   return false;
1394 }
1395 
1396 bool ShenandoahBarrierNode::sink_node(PhaseIdealLoop* phase, Node* ctrl, Node* n_ctrl) {
1397   ctrl = phase->find_non_split_ctrl(ctrl);
1398   assert(phase->dom_depth(n_ctrl) <= phase->dom_depth(ctrl), "n is later than its clone");
1399   set_req(0, ctrl);
1400   phase->register_new_node(this, ctrl);
1401   return true;
1402 }
1403 
1404 #ifdef ASSERT
1405 void ShenandoahWriteBarrierNode::memory_dominates_all_paths_helper(Node* c, Node* rep_ctrl, Unique_Node_List& controls, PhaseIdealLoop* phase) {
1406   const bool trace = false;
1407   if (trace) { tty->print("X control is"); c->dump(); }
1408 
1409   uint start = controls.size();
1410   controls.push(c);
1411   for (uint i = start; i < controls.size(); i++) {
1412     Node *n = controls.at(i);
1413 
1414     if (trace) { tty->print("X from"); n->dump(); }
1415 
1416     if (n == rep_ctrl) {
1417       continue;
1418     }
1419 
1420     if (n->is_Proj()) {
1421       Node* n_dom = n->in(0);
1422       IdealLoopTree* n_dom_loop = phase->get_loop(n_dom);
1423       if (n->is_IfProj() && n_dom->outcnt() == 2) {
1424         n_dom_loop = phase->get_loop(n_dom->as_If()->proj_out(n->as_Proj()->_con == 0 ? 1 : 0));
1425       }
1426       if (n_dom_loop != phase->ltree_root()) {
1427         Node* tail = n_dom_loop->tail();
1428         if (tail->is_Region()) {
1429           for (uint j = 1; j < tail->req(); j++) {
1430             if (phase->is_dominator(n_dom, tail->in(j)) && !phase->is_dominator(n, tail->in(j))) {
1431               assert(phase->is_dominator(rep_ctrl, tail->in(j)), "why are we here?");
1432               // entering loop from below, mark backedge
1433               if (trace) { tty->print("X pushing backedge"); tail->in(j)->dump(); }
1434               controls.push(tail->in(j));
1435               //assert(n->in(0) == n_dom, "strange flow control");
1436             }
1437           }
1438         } else if (phase->get_loop(n) != n_dom_loop && phase->is_dominator(n_dom, tail)) {
1439           // entering loop from below, mark backedge
1440           if (trace) { tty->print("X pushing backedge"); tail->dump(); }
1441           controls.push(tail);
1442           //assert(n->in(0) == n_dom, "strange flow control");
1443         }
1444       }
1445     }
1446 
1447     if (n->is_Loop()) {
1448       Node* c = n->in(LoopNode::EntryControl);
1449       if (trace) { tty->print("X pushing"); c->dump(); }
1450       controls.push(c);
1451     } else if (n->is_Region()) {
1452       for (uint i = 1; i < n->req(); i++) {
1453         Node* c = n->in(i);
1454         if (trace) { tty->print("X pushing"); c->dump(); }
1455         controls.push(c);
1456       }
1457     } else {
1458       Node* c = n->in(0);
1459       if (trace) { tty->print("X pushing"); c->dump(); }
1460       controls.push(c);
1461     }
1462   }
1463 }
1464 
1465 bool ShenandoahWriteBarrierNode::memory_dominates_all_paths(Node* mem, Node* rep_ctrl, int alias, PhaseIdealLoop* phase) {
1466   const bool trace = false;
1467   if (trace) {
1468     tty->print("XXX mem is"); mem->dump();
1469     tty->print("XXX rep ctrl is"); rep_ctrl->dump();
1470     tty->print_cr("XXX alias is %d", alias);
1471   }
1472   ResourceMark rm;
1473   Unique_Node_List wq;
1474   Unique_Node_List controls;
1475   wq.push(mem);
1476   for (uint next = 0; next < wq.size(); next++) {
1477     Node *nn = wq.at(next);
1478     if (trace) { tty->print("XX from mem"); nn->dump(); }
1479     assert(nn->bottom_type() == Type::MEMORY, "memory only");
1480 
1481     if (nn->is_Phi()) {
1482       Node* r = nn->in(0);
1483       for (DUIterator_Fast jmax, j = r->fast_outs(jmax); j < jmax; j++) {
1484         Node* u = r->fast_out(j);
1485         if (u->is_Phi() && u->bottom_type() == Type::MEMORY && u != nn &&
1486             (u->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(u->adr_type()) == alias)) {
1487           if (trace) { tty->print("XX Next mem (other phi)"); u->dump(); }
1488           wq.push(u);
1489         }
1490       }
1491     }
1492 
1493     for (DUIterator_Fast imax, i = nn->fast_outs(imax); i < imax; i++) {
1494       Node* use = nn->fast_out(i);
1495 
1496       if (trace) { tty->print("XX use %p", use->adr_type()); use->dump(); }
1497       if (use->is_CFG() && use->in(TypeFunc::Memory) == nn) {
1498         Node* c = use->in(0);
1499         if (phase->is_dominator(rep_ctrl, c)) {
1500           memory_dominates_all_paths_helper(c, rep_ctrl, controls, phase);
1501         } else if (use->is_CallStaticJava() && use->as_CallStaticJava()->uncommon_trap_request() != 0 && c->is_Region()) {
1502           Node* region = c;
1503           if (trace) { tty->print("XX unc region"); region->dump(); }
1504           for (uint j = 1; j < region->req(); j++) {
1505             if (phase->is_dominator(rep_ctrl, region->in(j))) {
1506               if (trace) { tty->print("XX unc follows"); region->in(j)->dump(); }
1507               memory_dominates_all_paths_helper(region->in(j), rep_ctrl, controls, phase);
1508             }
1509           }
1510         }
1511         //continue;
1512       } else if (use->is_Phi()) {
1513         assert(use->bottom_type() == Type::MEMORY, "bad phi");
1514         if ((use->adr_type() == TypePtr::BOTTOM) ||
1515             phase->C->get_alias_index(use->adr_type()) == alias) {
1516           for (uint j = 1; j < use->req(); j++) {
1517             if (use->in(j) == nn) {
1518               Node* c = use->in(0)->in(j);
1519               if (phase->is_dominator(rep_ctrl, c)) {
1520                 memory_dominates_all_paths_helper(c, rep_ctrl, controls, phase);
1521               }
1522             }
1523           }
1524         }
1525         //        continue;
1526       }
1527 
1528       if (use->is_MergeMem()) {
1529         if (use->as_MergeMem()->memory_at(alias) == nn) {
1530           if (trace) { tty->print("XX Next mem"); use->dump(); }
1531           // follow the memory edges
1532           wq.push(use);
1533         }
1534       } else if (use->is_Phi()) {
1535         assert(use->bottom_type() == Type::MEMORY, "bad phi");
1536         if ((use->adr_type() == TypePtr::BOTTOM) ||
1537             phase->C->get_alias_index(use->adr_type()) == alias) {
1538           if (trace) { tty->print("XX Next mem"); use->dump(); }
1539           // follow the memory edges
1540           wq.push(use);
1541         }
1542       } else if (use->bottom_type() == Type::MEMORY &&
1543                  (use->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(use->adr_type()) == alias)) {
1544         if (trace) { tty->print("XX Next mem"); use->dump(); }
1545         // follow the memory edges
1546         wq.push(use);
1547       } else if ((use->is_SafePoint() || use->is_MemBar()) &&
1548                  (use->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(use->adr_type()) == alias)) {
1549         for (DUIterator_Fast jmax, j = use->fast_outs(jmax); j < jmax; j++) {
1550           Node* u = use->fast_out(j);
1551           if (u->bottom_type() == Type::MEMORY) {
1552             if (trace) { tty->print("XX Next mem"); u->dump(); }
1553             // follow the memory edges
1554             wq.push(u);
1555           }
1556         }
1557       } else if (use->Opcode() == Op_ShenandoahWriteBarrier && phase->C->get_alias_index(use->adr_type()) == alias) {
1558         Node* m = use->find_out_with(Op_ShenandoahWBMemProj);
1559         if (m != NULL) {
1560           if (trace) { tty->print("XX Next mem"); m->dump(); }
1561           // follow the memory edges
1562           wq.push(m);
1563         }
1564       }
1565     }
1566   }
1567 
1568   if (controls.size() == 0) {
1569     return false;
1570   }
1571 
1572   for (uint i = 0; i < controls.size(); i++) {
1573     Node *n = controls.at(i);
1574 
1575     if (trace) { tty->print("X checking"); n->dump(); }
1576 
1577     if (n->unique_ctrl_out() != NULL) {
1578       continue;
1579     }
1580 
1581     if (n->Opcode() == Op_NeverBranch) {
1582       Node* taken = n->as_Multi()->proj_out(0);
1583       if (!controls.member(taken)) {
1584         if (trace) { tty->print("X not seen"); taken->dump(); }
1585         return false;
1586       }
1587       continue;
1588     }
1589 
1590     for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1591       Node* u = n->fast_out(j);
1592 
1593       if (u->is_CFG()) {
1594         if (!controls.member(u)) {
1595           if (u->is_Proj() && u->as_Proj()->is_uncommon_trap_proj(Deoptimization::Reason_none)) {
1596             if (trace) { tty->print("X not seen but unc"); u->dump(); }
1597           } else {
1598             Node* c = u;
1599             do {
1600               c = c->unique_ctrl_out();
1601             } while (c != NULL && c->is_Region());
1602             if (c != NULL && c->Opcode() == Op_Halt) {
1603               if (trace) { tty->print("X not seen but halt"); c->dump(); }
1604             } else {
1605               if (trace) { tty->print("X not seen"); u->dump(); }
1606               return false;
1607             }
1608           }
1609         } else {
1610           if (trace) { tty->print("X seen"); u->dump(); }
1611         }
1612       }
1613     }
1614   }
1615   return true;
1616 }
1617 #endif
1618 
1619 Node* ShenandoahBarrierNode::dom_mem(Node* mem, Node*& mem_ctrl, Node* n, Node* rep_ctrl, int alias, PhaseIdealLoop* phase) {
1620   ResourceMark rm;
1621   VectorSet wq(Thread::current()->resource_area());
1622   wq.set(mem->_idx);
1623   mem_ctrl = phase->get_ctrl(mem);
1624   while (!is_dominator(mem_ctrl, rep_ctrl, mem, n, phase)) {
1625     mem = next_mem(mem, alias);
1626     if (wq.test_set(mem->_idx)) {
1627       return NULL; // hit an unexpected loop
1628     }
1629     mem_ctrl = phase->ctrl_or_self(mem);
1630   }
1631   if (mem->is_MergeMem()) {
1632     mem = mem->as_MergeMem()->memory_at(alias);
1633     mem_ctrl = phase->ctrl_or_self(mem);
1634   }
1635   return mem;
1636 }
1637 
1638 Node* ShenandoahBarrierNode::dom_mem(Node* mem, Node* ctrl, int alias, Node*& mem_ctrl, PhaseIdealLoop* phase) {
1639   ResourceMark rm;
1640   VectorSet wq(Thread::current()->resource_area());
1641   wq.set(mem->_idx);
1642   mem_ctrl = phase->ctrl_or_self(mem);
1643   while (!phase->is_dominator(mem_ctrl, ctrl) || mem_ctrl == ctrl) {
1644     mem = next_mem(mem, alias);
1645     if (wq.test_set(mem->_idx)) {
1646       return NULL;
1647     }
1648     mem_ctrl = phase->ctrl_or_self(mem);
1649   }
1650   if (mem->is_MergeMem()) {
1651     mem = mem->as_MergeMem()->memory_at(alias);
1652     mem_ctrl = phase->ctrl_or_self(mem);
1653   }
1654   return mem;
1655 }
1656 
1657 static void disconnect_barrier_mem(Node* wb, PhaseIterGVN& igvn) {
1658   Node* mem_in = wb->in(ShenandoahBarrierNode::Memory);
1659   Node* proj = wb->find_out_with(Op_ShenandoahWBMemProj);
1660 
1661   for (DUIterator_Last imin, i = proj->last_outs(imin); i >= imin; ) {
1662     Node* u = proj->last_out(i);
1663     igvn.rehash_node_delayed(u);
1664     int nb = u->replace_edge(proj, mem_in);
1665     assert(nb > 0, "no replacement?");
1666     i -= nb;
1667   }
1668 }
1669 
1670 Node* ShenandoahWriteBarrierNode::move_above_predicates(LoopNode* cl, Node* val_ctrl, PhaseIdealLoop* phase) {
1671   Node* entry = cl->skip_strip_mined(-1)->in(LoopNode::EntryControl);
1672   Node* above_pred = phase->skip_all_loop_predicates(entry);
1673   Node* ctrl = entry;
1674   while (ctrl != above_pred) {
1675     Node* next = ctrl->in(0);
1676     if (!phase->is_dominator(val_ctrl, next)) {
1677       break;
1678     }
1679     ctrl = next;
1680   }
1681   return ctrl;
1682 }
1683 
1684 static MemoryGraphFixer* find_fixer(GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, int alias) {
1685   for (int i = 0; i < memory_graph_fixers.length(); i++) {
1686     if (memory_graph_fixers.at(i)->alias() == alias) {
1687       return memory_graph_fixers.at(i);
1688     }
1689   }
1690   return NULL;
1691 }
1692 
1693 static MemoryGraphFixer* create_fixer(GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, int alias, PhaseIdealLoop* phase, bool include_lsm) {
1694   assert(find_fixer(memory_graph_fixers, alias) == NULL, "none should exist yet");
1695   MemoryGraphFixer* fixer = new MemoryGraphFixer(alias, include_lsm, phase);
1696   memory_graph_fixers.push(fixer);
1697   return fixer;
1698 }
1699 
1700 void ShenandoahWriteBarrierNode::try_move_before_loop_helper(LoopNode* cl, Node* val_ctrl, GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, PhaseIdealLoop* phase, bool include_lsm, Unique_Node_List& uses) {
1701   assert(cl->is_Loop(), "bad control");
1702   Node* ctrl = move_above_predicates(cl, val_ctrl, phase);
1703   Node* mem_ctrl = NULL;
1704   int alias = phase->C->get_alias_index(adr_type());
1705 
1706   MemoryGraphFixer* fixer = find_fixer(memory_graph_fixers, alias);
1707   if (fixer == NULL) {
1708     fixer = create_fixer(memory_graph_fixers, alias, phase, include_lsm);
1709   }
1710 
1711   Node* proj = find_out_with(Op_ShenandoahWBMemProj);
1712 
1713   fixer->remove(proj);
1714   Node* mem = fixer->find_mem(ctrl, NULL);
1715 
1716   assert(!ShenandoahVerifyOptoBarriers || memory_dominates_all_paths(mem, ctrl, alias, phase), "can't fix the memory graph");
1717 
1718   phase->set_ctrl_and_loop(this, ctrl);
1719   phase->igvn().replace_input_of(this, Control, ctrl);
1720 
1721   disconnect_barrier_mem(this, phase->igvn());
1722 
1723   phase->igvn().replace_input_of(this, Memory, mem);
1724   phase->set_ctrl_and_loop(proj, ctrl);
1725 
1726   fixer->fix_mem(ctrl, ctrl, mem, mem, proj, uses);
1727   assert(proj->outcnt() > 0, "disconnected write barrier");
1728 }
1729 
1730 LoopNode* ShenandoahWriteBarrierNode::try_move_before_pre_loop(Node* c, Node* val_ctrl, PhaseIdealLoop* phase) {
1731   // A write barrier between a pre and main loop can get in the way of
1732   // vectorization. Move it above the pre loop if possible
1733   CountedLoopNode* cl = NULL;
1734   if (c->is_IfFalse() &&
1735       c->in(0)->is_CountedLoopEnd()) {
1736     cl = c->in(0)->as_CountedLoopEnd()->loopnode();
1737   } else if (c->is_IfProj() &&
1738              c->in(0)->is_If() &&
1739              c->in(0)->in(0)->is_IfFalse() &&
1740              c->in(0)->in(0)->in(0)->is_CountedLoopEnd()) {
1741     cl = c->in(0)->in(0)->in(0)->as_CountedLoopEnd()->loopnode();
1742   }
1743   if (cl != NULL &&
1744       cl->is_pre_loop() &&
1745       val_ctrl != cl &&
1746       phase->is_dominator(val_ctrl, cl)) {
1747     return cl;
1748   }
1749   return NULL;
1750 }
1751 
1752 void ShenandoahWriteBarrierNode::try_move_before_loop(GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, PhaseIdealLoop* phase, bool include_lsm, Unique_Node_List& uses) {
1753   Node *n_ctrl = phase->get_ctrl(this);
1754   IdealLoopTree *n_loop = phase->get_loop(n_ctrl);
1755   Node* val = in(ValueIn);
1756   Node* val_ctrl = phase->get_ctrl(val);
1757   if (n_loop != phase->ltree_root() && !n_loop->_irreducible) {
1758     IdealLoopTree *val_loop = phase->get_loop(val_ctrl);
1759     Node* mem = in(Memory);
1760     IdealLoopTree *mem_loop = phase->get_loop(phase->get_ctrl(mem));
1761     if (!n_loop->is_member(val_loop) &&
1762         n_loop->is_member(mem_loop)) {
1763       Node* n_loop_head = n_loop->_head;
1764 
1765       if (n_loop_head->is_Loop()) {
1766         LoopNode* loop = n_loop_head->as_Loop();
1767         if (n_loop_head->is_CountedLoop() && n_loop_head->as_CountedLoop()->is_main_loop()) {
1768           LoopNode* res = try_move_before_pre_loop(n_loop_head->in(LoopNode::EntryControl), val_ctrl, phase);
1769           if (res != NULL) {
1770             loop = res;
1771           }
1772         }
1773 
1774         try_move_before_loop_helper(loop, val_ctrl, memory_graph_fixers, phase, include_lsm, uses);
1775       }
1776     }
1777   }
1778   LoopNode* ctrl = try_move_before_pre_loop(in(0), val_ctrl, phase);
1779   if (ctrl != NULL) {
1780     try_move_before_loop_helper(ctrl, val_ctrl, memory_graph_fixers, phase, include_lsm, uses);
1781   }
1782 }
1783 
1784 Node* ShenandoahWriteBarrierNode::would_subsume(ShenandoahBarrierNode* other, PhaseIdealLoop* phase) {
1785   Node* val = in(ValueIn);
1786   Node* val_ctrl = phase->get_ctrl(val);
1787   Node* other_mem = other->in(Memory);
1788   Node* other_ctrl = phase->get_ctrl(other);
1789   Node* this_ctrl = phase->get_ctrl(this);
1790   IdealLoopTree* this_loop = phase->get_loop(this_ctrl);
1791   IdealLoopTree* other_loop = phase->get_loop(other_ctrl);
1792 
1793   Node* ctrl = phase->dom_lca(other_ctrl, this_ctrl);
1794 
1795   if (ctrl->is_Proj() &&
1796       ctrl->in(0)->is_Call() &&
1797       ctrl->unique_ctrl_out() != NULL &&
1798       ctrl->unique_ctrl_out()->Opcode() == Op_Catch &&
1799       !phase->is_dominator(val_ctrl, ctrl->in(0)->in(0))) {
1800     return NULL;
1801   }
1802 
1803   IdealLoopTree* loop = phase->get_loop(ctrl);
1804 
1805   // We don't want to move a write barrier in a loop
1806   // If the LCA is in a inner loop, try a control out of loop if possible
1807   while (!loop->is_member(this_loop) && (other->Opcode() != Op_ShenandoahWriteBarrier || !loop->is_member(other_loop))) {
1808     ctrl = phase->idom(ctrl);
1809     if (ctrl->is_MultiBranch()) {
1810       ctrl = ctrl->in(0);
1811     }
1812     if (ctrl != val_ctrl && phase->is_dominator(ctrl, val_ctrl)) {
1813       return NULL;
1814     }
1815     loop = phase->get_loop(ctrl);
1816   }
1817 
1818   if (ShenandoahDontIncreaseWBFreq) {
1819     Node* this_iffproj = no_branches(this_ctrl, ctrl, true, phase);
1820     if (other->Opcode() == Op_ShenandoahWriteBarrier) {
1821       Node* other_iffproj = no_branches(other_ctrl, ctrl, true, phase);
1822       if (other_iffproj == NULL || this_iffproj == NULL) {
1823         return ctrl;
1824       } else if (other_iffproj != NodeSentinel && this_iffproj != NodeSentinel &&
1825                  other_iffproj->in(0) == this_iffproj->in(0)) {
1826         return ctrl;
1827       }
1828     } else if (this_iffproj == NULL) {
1829       return ctrl;
1830     }
1831     return NULL;
1832   }
1833 
1834   return ctrl;
1835 }
1836 
1837 void ShenandoahWriteBarrierNode::optimize_before_expansion(PhaseIdealLoop* phase, GrowableArray<MemoryGraphFixer*> memory_graph_fixers, bool include_lsm) {
1838   bool progress = false;
1839   Unique_Node_List uses;
1840   do {
1841     progress = false;
1842     for (int i = 0; i < ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count(); i++) {
1843       ShenandoahWriteBarrierNode* wb = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barrier(i);
1844 
1845       wb->try_move_before_loop(memory_graph_fixers, phase, include_lsm, uses);
1846 
1847       Node* val = wb->in(ValueIn);
1848 
1849       for (DUIterator_Fast jmax, j = val->fast_outs(jmax); j < jmax; j++) {
1850         Node* u = val->fast_out(j);
1851         if (u != wb && u->is_ShenandoahBarrier()) {
1852           Node* rep_ctrl = wb->would_subsume(u->as_ShenandoahBarrier(), phase);
1853 
1854           if (rep_ctrl != NULL) {
1855             Node* other = u;
1856             Node* val_ctrl = phase->get_ctrl(val);
1857             if (rep_ctrl->is_Proj() &&
1858                 rep_ctrl->in(0)->is_Call() &&
1859                 rep_ctrl->unique_ctrl_out() != NULL &&
1860                 rep_ctrl->unique_ctrl_out()->Opcode() == Op_Catch) {
1861               rep_ctrl = rep_ctrl->in(0)->in(0);
1862 
1863               assert(phase->is_dominator(val_ctrl, rep_ctrl), "bad control");
1864             } else {
1865               LoopNode* c = ShenandoahWriteBarrierNode::try_move_before_pre_loop(rep_ctrl, val_ctrl, phase);
1866               if (c != NULL) {
1867                 rep_ctrl = ShenandoahWriteBarrierNode::move_above_predicates(c, val_ctrl, phase);
1868               } else {
1869                 while (rep_ctrl->is_IfProj()) {
1870                   CallStaticJavaNode* unc = rep_ctrl->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
1871                   if (unc != NULL) {
1872                     int req = unc->uncommon_trap_request();
1873                     Deoptimization::DeoptReason trap_reason = Deoptimization::trap_request_reason(req);
1874                     if ((trap_reason == Deoptimization::Reason_loop_limit_check ||
1875                          trap_reason == Deoptimization::Reason_predicate ||
1876                          trap_reason == Deoptimization::Reason_profile_predicate) &&
1877                         phase->is_dominator(val_ctrl, rep_ctrl->in(0)->in(0))) {
1878                       rep_ctrl = rep_ctrl->in(0)->in(0);
1879                       continue;
1880                     }
1881                   }
1882                   break;
1883                 }
1884               }
1885             }
1886 
1887             Node* wb_ctrl = phase->get_ctrl(wb);
1888             Node* other_ctrl = phase->get_ctrl(other);
1889             int alias = phase->C->get_alias_index(wb->adr_type());
1890             MemoryGraphFixer* fixer = find_fixer(memory_graph_fixers, alias);;
1891             if (!is_dominator(wb_ctrl, other_ctrl, wb, other, phase)) {
1892               if (fixer == NULL) {
1893                 fixer = create_fixer(memory_graph_fixers, alias, phase, include_lsm);
1894               }
1895               Node* mem = fixer->find_mem(rep_ctrl, phase->get_ctrl(other) == rep_ctrl ? other : NULL);
1896 
1897               if (mem->has_out_with(Op_Lock) || mem->has_out_with(Op_Unlock)) {
1898                 continue;
1899               }
1900 
1901               Node* wb_proj = wb->find_out_with(Op_ShenandoahWBMemProj);
1902               fixer->remove(wb_proj);
1903               Node* mem_for_ctrl = fixer->find_mem(rep_ctrl, NULL);
1904 
1905               if (wb->in(Memory) != mem) {
1906                 disconnect_barrier_mem(wb, phase->igvn());
1907                 phase->igvn().replace_input_of(wb, Memory, mem);
1908               }
1909               if (rep_ctrl != wb_ctrl) {
1910                 phase->set_ctrl_and_loop(wb, rep_ctrl);
1911                 phase->igvn().replace_input_of(wb, Control, rep_ctrl);
1912                 phase->set_ctrl_and_loop(wb_proj, rep_ctrl);
1913                 progress = true;
1914               }
1915 
1916               fixer->fix_mem(rep_ctrl, rep_ctrl, mem, mem_for_ctrl, wb_proj, uses);
1917 
1918               assert(!ShenandoahVerifyOptoBarriers || ShenandoahWriteBarrierNode::memory_dominates_all_paths(mem, rep_ctrl, alias, phase), "can't fix the memory graph");
1919             }
1920 
1921             if (other->Opcode() == Op_ShenandoahWriteBarrier) {
1922               Node* other_proj = other->find_out_with(Op_ShenandoahWBMemProj);
1923               if (fixer != NULL) {
1924                 fixer->remove(other_proj);
1925               }
1926               phase->igvn().replace_node(other_proj, other->in(Memory));
1927             }
1928             phase->igvn().replace_node(other, wb);
1929             --j; --jmax;
1930           }
1931         }
1932       }
1933     }
1934   } while(progress);
1935 }
1936 
1937 // Some code duplication with PhaseIdealLoop::split_if_with_blocks_pre()
1938 Node* ShenandoahWriteBarrierNode::try_split_thru_phi(PhaseIdealLoop* phase) {
1939   Node *ctrl = phase->get_ctrl(this);
1940   if (ctrl == NULL) {
1941     return this;
1942   }
1943   Node *blk = phase->has_local_phi_input(this);
1944   if (blk == NULL) {
1945     return this;
1946   }
1947 
1948   if (in(0) != blk) {
1949     return this;
1950   }
1951 
1952   int policy = blk->req() >> 2;
1953 
1954   if (blk->is_CountedLoop()) {
1955     IdealLoopTree *lp = phase->get_loop(blk);
1956     if (lp && lp->_rce_candidate) {
1957       return this;
1958     }
1959   }
1960 
1961   if (phase->C->live_nodes() > 35000) {
1962     return this;
1963   }
1964 
1965   uint unique = phase->C->unique();
1966   Node *phi = phase->split_thru_phi(this, blk, policy);
1967   if (phi == NULL) {
1968     return this;
1969   }
1970 
1971   Node* mem_phi = new PhiNode(blk, Type::MEMORY, phase->C->alias_type(adr_type())->adr_type());
1972   for (uint i = 1; i < blk->req(); i++) {
1973     Node* n = phi->in(i);
1974     if (n->Opcode() == Op_ShenandoahWriteBarrier &&
1975         n->_idx >= unique) {
1976       Node* proj = new ShenandoahWBMemProjNode(n);
1977       phase->register_new_node(proj, phase->get_ctrl(n));
1978       mem_phi->init_req(i, proj);
1979     } else {
1980       Node* mem = in(ShenandoahBarrierNode::Memory);
1981       if (mem->is_Phi() && mem->in(0) == blk) {
1982         mem = mem->in(i);
1983       }
1984       mem_phi->init_req(i, mem);
1985     }
1986   }
1987   phase->register_new_node(mem_phi, blk);
1988 
1989 
1990   Node* proj = find_out_with(Op_ShenandoahWBMemProj);
1991   phase->igvn().replace_node(proj, mem_phi);
1992   phase->igvn().replace_node(this, phi);
1993 
1994   return phi;
1995 }
1996 
1997 void ShenandoahReadBarrierNode::try_move(PhaseIdealLoop* phase) {
1998   Node *n_ctrl = phase->get_ctrl(this);
1999   if (n_ctrl == NULL) {
2000     return;
2001   }
2002   Node* mem = in(MemNode::Memory);
2003   int alias = phase->C->get_alias_index(adr_type());
2004   const bool trace = false;
2005 
2006 #ifdef ASSERT
2007   if (trace) { tty->print("Trying to move mem of"); dump(); }
2008 #endif
2009 
2010   Node* new_mem = mem;
2011 
2012   ResourceMark rm;
2013   VectorSet seen(Thread::current()->resource_area());
2014   Node_List phis;
2015 
2016   for (;;) {
2017 #ifdef ASSERT
2018     if (trace) { tty->print("Looking for dominator from"); mem->dump(); }
2019 #endif
2020     if (mem->is_Proj() && mem->in(0)->is_Start()) {
2021       if (new_mem != in(MemNode::Memory)) {
2022 #ifdef ASSERT
2023         if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2024 #endif
2025         phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2026       }
2027       return;
2028     }
2029 
2030     Node* candidate = mem;
2031     do {
2032       if (!is_independent(mem)) {
2033         if (trace) { tty->print_cr("Not independent"); }
2034         if (new_mem != in(MemNode::Memory)) {
2035 #ifdef ASSERT
2036           if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2037 #endif
2038           phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2039         }
2040         return;
2041       }
2042       if (seen.test_set(mem->_idx)) {
2043         if (trace) { tty->print_cr("Already seen"); }
2044         ShouldNotReachHere();
2045         // Strange graph
2046         if (new_mem != in(MemNode::Memory)) {
2047 #ifdef ASSERT
2048           if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2049 #endif
2050           phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2051         }
2052         return;
2053       }
2054       if (mem->is_Phi()) {
2055         phis.push(mem);
2056       }
2057       mem = next_mem(mem, alias);
2058       if (mem->bottom_type() == Type::MEMORY) {
2059         candidate = mem;
2060       }
2061       assert(is_dominator(phase->ctrl_or_self(mem), n_ctrl, mem, this, phase) == phase->is_dominator(phase->ctrl_or_self(mem), n_ctrl), "strange dominator");
2062 #ifdef ASSERT
2063       if (trace) { tty->print("Next mem is"); mem->dump(); }
2064 #endif
2065     } while (mem->bottom_type() != Type::MEMORY || !phase->is_dominator(phase->ctrl_or_self(mem), n_ctrl));
2066 
2067     assert(mem->bottom_type() == Type::MEMORY, "bad mem");
2068 
2069     bool not_dom = false;
2070     for (uint i = 0; i < phis.size() && !not_dom; i++) {
2071       Node* nn = phis.at(i);
2072 
2073 #ifdef ASSERT
2074       if (trace) { tty->print("Looking from phi"); nn->dump(); }
2075 #endif
2076       assert(nn->is_Phi(), "phis only");
2077       for (uint j = 2; j < nn->req() && !not_dom; j++) {
2078         Node* m = nn->in(j);
2079 #ifdef ASSERT
2080         if (trace) { tty->print("Input %d is", j); m->dump(); }
2081 #endif
2082         while (m != mem && !seen.test_set(m->_idx)) {
2083           if (is_dominator(phase->ctrl_or_self(m), phase->ctrl_or_self(mem), m, mem, phase)) {
2084             not_dom = true;
2085             // Scheduling anomaly
2086 #ifdef ASSERT
2087             if (trace) { tty->print("Giving up"); m->dump(); }
2088 #endif
2089             break;
2090           }
2091           if (!is_independent(m)) {
2092             if (trace) { tty->print_cr("Not independent"); }
2093             if (new_mem != in(MemNode::Memory)) {
2094 #ifdef ASSERT
2095               if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2096 #endif
2097               phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2098             }
2099             return;
2100           }
2101           if (m->is_Phi()) {
2102             phis.push(m);
2103           }
2104           m = next_mem(m, alias);
2105 #ifdef ASSERT
2106           if (trace) { tty->print("Next mem is"); m->dump(); }
2107 #endif
2108         }
2109       }
2110     }
2111     if (!not_dom) {
2112       new_mem = mem;
2113       phis.clear();
2114     } else {
2115       seen.Clear();
2116     }
2117   }
2118 }
2119 
2120 CallStaticJavaNode* ShenandoahWriteBarrierNode::pin_and_expand_null_check(PhaseIterGVN& igvn) {
2121   Node* val = in(ValueIn);
2122 
2123   const Type* val_t = igvn.type(val);
2124 
2125   if (val_t->meet(TypePtr::NULL_PTR) != val_t &&
2126       val->Opcode() == Op_CastPP &&
2127       val->in(0) != NULL &&
2128       val->in(0)->Opcode() == Op_IfTrue &&
2129       val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
2130       val->in(0)->in(0)->is_If() &&
2131       val->in(0)->in(0)->in(1)->Opcode() == Op_Bool &&
2132       val->in(0)->in(0)->in(1)->as_Bool()->_test._test == BoolTest::ne &&
2133       val->in(0)->in(0)->in(1)->in(1)->Opcode() == Op_CmpP &&
2134       val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1) &&
2135       val->in(0)->in(0)->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
2136     assert(val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1), "");
2137     CallStaticJavaNode* unc = val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
2138     return unc;
2139   }
2140   return NULL;
2141 }
2142 
2143 void ShenandoahWriteBarrierNode::pin_and_expand_move_barrier(PhaseIdealLoop* phase, GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, Unique_Node_List& uses) {
2144   Node* unc = pin_and_expand_null_check(phase->igvn());
2145   Node* val = in(ValueIn);
2146 
2147   if (unc != NULL) {
2148     Node* ctrl = phase->get_ctrl(this);
2149     Node* unc_ctrl = val->in(0);
2150 
2151     // Don't move write barrier in a loop
2152     IdealLoopTree* loop = phase->get_loop(ctrl);
2153     IdealLoopTree* unc_loop = phase->get_loop(unc_ctrl);
2154 
2155     if (!unc_loop->is_member(loop)) {
2156       return;
2157     }
2158 
2159     Node* branch = no_branches(ctrl, unc_ctrl, false, phase);
2160     assert(branch == NULL || branch == NodeSentinel, "was not looking for a branch");
2161     if (branch == NodeSentinel) {
2162       return;
2163     }
2164 
2165     RegionNode* r = new RegionNode(3);
2166     IfNode* iff = unc_ctrl->in(0)->as_If();
2167 
2168     Node* ctrl_use = unc_ctrl->unique_ctrl_out();
2169     Node* unc_ctrl_clone = unc_ctrl->clone();
2170     phase->register_control(unc_ctrl_clone, loop, iff);
2171     Node* c = unc_ctrl_clone;
2172     Node* new_cast = clone_null_check(c, val, unc_ctrl_clone, phase);
2173     r->init_req(1, new_cast->in(0)->in(0)->as_If()->proj_out(0));
2174 
2175     phase->igvn().replace_input_of(unc_ctrl, 0, c->in(0));
2176     phase->set_idom(unc_ctrl, c->in(0), phase->dom_depth(unc_ctrl));
2177     phase->lazy_replace(c, unc_ctrl);
2178     c = NULL;;
2179     phase->igvn().replace_input_of(val, 0, unc_ctrl_clone);
2180     phase->set_ctrl(val, unc_ctrl_clone);
2181 
2182     IfNode* new_iff = new_cast->in(0)->in(0)->as_If();
2183     fix_null_check(unc, unc_ctrl_clone, r, uses, phase);
2184     Node* iff_proj = iff->proj_out(0);
2185     r->init_req(2, iff_proj);
2186     phase->register_control(r, phase->ltree_root(), iff);
2187 
2188     Node* new_bol = new_iff->in(1)->clone();
2189     Node* new_cmp = new_bol->in(1)->clone();
2190     assert(new_cmp->Opcode() == Op_CmpP, "broken");
2191     assert(new_cmp->in(1) == val->in(1), "broken");
2192     new_bol->set_req(1, new_cmp);
2193     new_cmp->set_req(1, this);
2194     phase->register_new_node(new_bol, new_iff->in(0));
2195     phase->register_new_node(new_cmp, new_iff->in(0));
2196     phase->igvn().replace_input_of(new_iff, 1, new_bol);
2197     phase->igvn().replace_input_of(new_cast, 1, this);
2198 
2199     for (DUIterator_Fast imax, i = this->fast_outs(imax); i < imax; i++) {
2200       Node* u = this->fast_out(i);
2201       if (u == new_cast || u->Opcode() == Op_ShenandoahWBMemProj || u == new_cmp) {
2202         continue;
2203       }
2204       phase->igvn().rehash_node_delayed(u);
2205       int nb = u->replace_edge(this, new_cast);
2206       assert(nb > 0, "no update?");
2207       --i; imax -= nb;
2208     }
2209 
2210     for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
2211       Node* u = val->fast_out(i);
2212       if (u == this) {
2213         continue;
2214       }
2215       phase->igvn().rehash_node_delayed(u);
2216       int nb = u->replace_edge(val, new_cast);
2217       assert(nb > 0, "no update?");
2218       --i; imax -= nb;
2219     }
2220 
2221     Node* new_ctrl = unc_ctrl_clone;
2222 
2223     int alias = phase->C->get_alias_index(adr_type());
2224     MemoryGraphFixer* fixer = find_fixer(memory_graph_fixers, alias);
2225     if (fixer == NULL) {
2226       fixer = create_fixer(memory_graph_fixers, alias, phase, true);
2227     }
2228 
2229     Node* proj = find_out_with(Op_ShenandoahWBMemProj);
2230     fixer->remove(proj);
2231     Node* mem = fixer->find_mem(new_ctrl, NULL);
2232 
2233     if (in(Memory) != mem) {
2234       disconnect_barrier_mem(this, phase->igvn());
2235       phase->igvn().replace_input_of(this, Memory, mem);
2236     }
2237 
2238     phase->set_ctrl_and_loop(this, new_ctrl);
2239     phase->igvn().replace_input_of(this, Control, new_ctrl);
2240     phase->set_ctrl_and_loop(proj, new_ctrl);
2241 
2242     fixer->fix_mem(new_ctrl, new_ctrl, mem, mem, proj, uses);
2243   }
2244 }
2245 
2246 void ShenandoahWriteBarrierNode::pin_and_expand_helper(PhaseIdealLoop* phase) {
2247   Node* val = in(ValueIn);
2248   CallStaticJavaNode* unc = pin_and_expand_null_check(phase->igvn());
2249   Node* rep = this;
2250   Node* ctrl = phase->get_ctrl(this);
2251   if (unc != NULL && val->in(0) == ctrl) {
2252     Node* unc_ctrl = val->in(0);
2253     IfNode* other_iff = unc_ctrl->unique_ctrl_out()->as_If();
2254     ProjNode* other_unc_ctrl = other_iff->proj_out(1);
2255     Node* cast = NULL;
2256     for (DUIterator_Fast imax, i = other_unc_ctrl->fast_outs(imax); i < imax && cast == NULL; i++) {
2257       Node* u = other_unc_ctrl->fast_out(i);
2258       if (u->Opcode() == Op_CastPP && u->in(1) == this) {
2259         cast = u;
2260       }
2261     }
2262     assert(other_unc_ctrl->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) == unc, "broken");
2263     rep = cast;
2264   }
2265 
2266   // Replace all uses of barrier's input that are dominated by ctrl
2267   // with the value returned by the barrier: no need to keep both
2268   // live.
2269   for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
2270     Node* u = val->fast_out(i);
2271     if (u != this) {
2272       if (u->is_Phi()) {
2273         int nb = 0;
2274         for (uint j = 1; j < u->req(); j++) {
2275           if (u->in(j) == val) {
2276             Node* c = u->in(0)->in(j);
2277             if (phase->is_dominator(ctrl, c)) {
2278               phase->igvn().replace_input_of(u, j, rep);
2279               nb++;
2280             }
2281           }
2282         }
2283         if (nb > 0) {
2284           imax -= nb;
2285           --i;
2286         }
2287       } else {
2288         Node* c = phase->ctrl_or_self(u);
2289         if (is_dominator(ctrl, c, this, u, phase)) {
2290           phase->igvn().rehash_node_delayed(u);
2291           int nb = u->replace_edge(val, rep);
2292           assert(nb > 0, "no update?");
2293           --i, imax -= nb;
2294         }
2295       }
2296     }
2297   }
2298 }
2299 
2300 Node* ShenandoahWriteBarrierNode::find_bottom_mem(Node* ctrl, PhaseIdealLoop* phase) {
2301   Node* mem = NULL;
2302   Node* c = ctrl;
2303   do {
2304     if (c->is_Region()) {
2305       Node* phi_bottom = NULL;
2306       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax && mem == NULL; i++) {
2307         Node* u = c->fast_out(i);
2308         if (u->is_Phi() && u->bottom_type() == Type::MEMORY) {
2309           if (u->adr_type() == TypePtr::BOTTOM) {
2310             mem = u;
2311           }
2312         }
2313       }
2314     } else {
2315       if (c->is_Call() && c->as_Call()->adr_type() != NULL) {
2316         CallProjections projs;
2317         c->as_Call()->extract_projections(&projs, true, false);
2318         if (projs.fallthrough_memproj != NULL) {
2319           if (projs.fallthrough_memproj->adr_type() == TypePtr::BOTTOM) {
2320             if (projs.catchall_memproj == NULL) {


2337         }
2338       } else {
2339         for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
2340           Node* u = c->fast_out(i);
2341           if (u->is_Proj() &&
2342               u->bottom_type() == Type::MEMORY &&
2343               u->adr_type() == TypePtr::BOTTOM) {
2344               assert(c->is_SafePoint() || c->is_MemBar() || c->is_Start(), "");
2345               assert(mem == NULL, "only one proj");
2346               mem = u;
2347           }
2348         }
2349         assert(!c->is_Call() || c->as_Call()->adr_type() != NULL || mem == NULL, "no mem projection expected");
2350       }
2351     }
2352     c = phase->idom(c);
2353   } while (mem == NULL);
2354   return mem;
2355 }
2356 
2357 void ShenandoahWriteBarrierNode::follow_barrier_uses(Node* n, Node* ctrl, Unique_Node_List& uses, PhaseIdealLoop* phase) {
2358   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2359     Node* u = n->fast_out(i);
2360     if (!u->is_CFG() && phase->get_ctrl(u) == ctrl && (!u->is_Phi() || !u->in(0)->is_Loop() || u->in(LoopNode::LoopBackControl) != n)) {
2361       uses.push(u);
2362     }
2363   }
2364 }
2365 
2366 static void hide_strip_mined_loop(OuterStripMinedLoopNode* outer, CountedLoopNode* inner, PhaseIdealLoop* phase) {
2367   OuterStripMinedLoopEndNode* le = inner->outer_loop_end();
2368   Node* new_outer = new LoopNode(outer->in(LoopNode::EntryControl), outer->in(LoopNode::LoopBackControl));
2369   phase->register_control(new_outer, phase->get_loop(outer), outer->in(LoopNode::EntryControl));
2370   Node* new_le = new IfNode(le->in(0), le->in(1), le->_prob, le->_fcnt);
2371   phase->register_control(new_le, phase->get_loop(le), le->in(0));
2372   phase->lazy_replace(outer, new_outer);
2373   phase->lazy_replace(le, new_le);
2374   inner->clear_strip_mined();
2375 }
2376 
2377 void ShenandoahWriteBarrierNode::test_heap_stable(Node*& ctrl, Node* raw_mem, Node*& heap_stable_ctrl,
2378                                                   PhaseIdealLoop* phase) {
2379   IdealLoopTree* loop = phase->get_loop(ctrl);
2380   Node* thread = new ThreadLocalNode();
2381   phase->register_new_node(thread, ctrl);
2382   Node* offset = phase->igvn().MakeConX(in_bytes(ShenandoahThreadLocalData::gc_state_offset()));
2383   phase->set_ctrl(offset, phase->C->root());
2384   Node* gc_state_addr = new AddPNode(phase->C->top(), thread, offset);
2385   phase->register_new_node(gc_state_addr, ctrl);
2386   uint gc_state_idx = Compile::AliasIdxRaw;
2387   const TypePtr* gc_state_adr_type = NULL; // debug-mode-only argument
2388   debug_only(gc_state_adr_type = phase->C->get_adr_type(gc_state_idx));
2389 
2390   Node* gc_state = new LoadBNode(ctrl, raw_mem, gc_state_addr, gc_state_adr_type, TypeInt::BYTE, MemNode::unordered);
2391   phase->register_new_node(gc_state, ctrl);
2392   Node* heap_stable_and = new AndINode(gc_state, phase->igvn().intcon(ShenandoahHeap::HAS_FORWARDED));
2393   phase->register_new_node(heap_stable_and, ctrl);
2394   Node* heap_stable_cmp = new CmpINode(heap_stable_and, phase->igvn().zerocon(T_INT));
2395   phase->register_new_node(heap_stable_cmp, ctrl);
2396   Node* heap_stable_test = new BoolNode(heap_stable_cmp, BoolTest::ne);
2397   phase->register_new_node(heap_stable_test, ctrl);
2398   IfNode* heap_stable_iff = new IfNode(ctrl, heap_stable_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
2399   phase->register_control(heap_stable_iff, loop, ctrl);
2400 
2401   heap_stable_ctrl = new IfFalseNode(heap_stable_iff);
2402   phase->register_control(heap_stable_ctrl, loop, heap_stable_iff);
2403   ctrl = new IfTrueNode(heap_stable_iff);
2404   phase->register_control(ctrl, loop, heap_stable_iff);
2405 
2406   assert(is_heap_stable_test(heap_stable_iff), "Should match the shape");
2407 }
2408 
2409 void ShenandoahWriteBarrierNode::test_null(Node*& ctrl, Node* val, Node*& null_ctrl, PhaseIdealLoop* phase) {
2410   const Type* val_t = phase->igvn().type(val);
2411   if (val_t->meet(TypePtr::NULL_PTR) == val_t) {
2412     IdealLoopTree* loop = phase->get_loop(ctrl);
2413     Node* null_cmp = new CmpPNode(val, phase->igvn().zerocon(T_OBJECT));
2414     phase->register_new_node(null_cmp, ctrl);
2415     Node* null_test = new BoolNode(null_cmp, BoolTest::ne);
2416     phase->register_new_node(null_test, ctrl);
2417     IfNode* null_iff = new IfNode(ctrl, null_test, PROB_LIKELY(0.999), COUNT_UNKNOWN);
2418     phase->register_control(null_iff, loop, ctrl);
2419     ctrl = new IfTrueNode(null_iff);
2420     phase->register_control(ctrl, loop, null_iff);
2421     null_ctrl = new IfFalseNode(null_iff);
2422     phase->register_control(null_ctrl, loop, null_iff);
2423   }
2424 }
2425 
2426 Node* ShenandoahWriteBarrierNode::clone_null_check(Node*& c, Node* val, Node* unc_ctrl, PhaseIdealLoop* phase) {
2427   IdealLoopTree *loop = phase->get_loop(c);
2428   Node* iff = unc_ctrl->in(0);
2429   assert(iff->is_If(), "broken");
2430   Node* new_iff = iff->clone();
2431   new_iff->set_req(0, c);
2432   phase->register_control(new_iff, loop, c);
2433   Node* iffalse = new IfFalseNode(new_iff->as_If());
2434   phase->register_control(iffalse, loop, new_iff);
2435   Node* iftrue = new IfTrueNode(new_iff->as_If());
2436   phase->register_control(iftrue, loop, new_iff);
2437   c = iftrue;
2438   const Type *t = phase->igvn().type(val);
2439   assert(val->Opcode() == Op_CastPP, "expect cast to non null here");
2440   Node* uncasted_val = val->in(1);
2441   val = new CastPPNode(uncasted_val, t);
2442   val->init_req(0, c);
2443   phase->register_new_node(val, c);
2444   return val;
2445 }
2446 
2447 void ShenandoahWriteBarrierNode::fix_null_check(Node* unc, Node* unc_ctrl, Node* new_unc_ctrl,
2448                                                 Unique_Node_List& uses, PhaseIdealLoop* phase) {
2449   IfNode* iff = unc_ctrl->in(0)->as_If();
2450   Node* proj = iff->proj_out(0);
2451   assert(proj != unc_ctrl, "bad projection");
2452   Node* use = proj->unique_ctrl_out();
2453 
2454   assert(use == unc || use->is_Region(), "what else?");
2455 
2456   uses.clear();
2457   if (use == unc) {
2458     phase->set_idom(use, new_unc_ctrl, phase->dom_depth(use));
2459     for (uint i = 1; i < unc->req(); i++) {
2460       Node* n = unc->in(i);
2461       if (phase->has_ctrl(n) && phase->get_ctrl(n) == proj) {
2462         uses.push(n);
2463       }
2464     }
2465   } else {
2466     assert(use->is_Region(), "what else?");
2467     uint idx = 1;


2476   for(uint next = 0; next < uses.size(); next++ ) {
2477     Node *n = uses.at(next);
2478     assert(phase->get_ctrl(n) == proj, "bad control");
2479     phase->set_ctrl_and_loop(n, new_unc_ctrl);
2480     if (n->in(0) == proj) {
2481       phase->igvn().replace_input_of(n, 0, new_unc_ctrl);
2482     }
2483     for (uint i = 0; i < n->req(); i++) {
2484       Node* m = n->in(i);
2485       if (m != NULL && phase->has_ctrl(m) && phase->get_ctrl(m) == proj) {
2486         uses.push(m);
2487       }
2488     }
2489   }
2490 
2491   phase->igvn().rehash_node_delayed(use);
2492   int nb = use->replace_edge(proj, new_unc_ctrl);
2493   assert(nb == 1, "only use expected");
2494 }
2495 
2496 void ShenandoahWriteBarrierNode::in_cset_fast_test(Node*& ctrl, Node*& not_cset_ctrl, Node* val, Node* raw_mem, PhaseIdealLoop* phase) {
2497   IdealLoopTree *loop = phase->get_loop(ctrl);
2498   Node* raw_rbtrue = new CastP2XNode(ctrl, val);
2499   phase->register_new_node(raw_rbtrue, ctrl);
2500   Node* cset_offset = new URShiftXNode(raw_rbtrue, phase->igvn().intcon(ShenandoahHeapRegion::region_size_bytes_shift_jint()));
2501   phase->register_new_node(cset_offset, ctrl);
2502   Node* in_cset_fast_test_base_addr = phase->igvn().makecon(TypeRawPtr::make(ShenandoahHeap::in_cset_fast_test_addr()));
2503   phase->set_ctrl(in_cset_fast_test_base_addr, phase->C->root());
2504   Node* in_cset_fast_test_adr = new AddPNode(phase->C->top(), in_cset_fast_test_base_addr, cset_offset);
2505   phase->register_new_node(in_cset_fast_test_adr, ctrl);
2506   uint in_cset_fast_test_idx = Compile::AliasIdxRaw;
2507   const TypePtr* in_cset_fast_test_adr_type = NULL; // debug-mode-only argument
2508   debug_only(in_cset_fast_test_adr_type = phase->C->get_adr_type(in_cset_fast_test_idx));
2509   Node* in_cset_fast_test_load = new LoadBNode(ctrl, raw_mem, in_cset_fast_test_adr, in_cset_fast_test_adr_type, TypeInt::BYTE, MemNode::unordered);
2510   phase->register_new_node(in_cset_fast_test_load, ctrl);
2511   Node* in_cset_fast_test_cmp = new CmpINode(in_cset_fast_test_load, phase->igvn().zerocon(T_INT));
2512   phase->register_new_node(in_cset_fast_test_cmp, ctrl);
2513   Node* in_cset_fast_test_test = new BoolNode(in_cset_fast_test_cmp, BoolTest::eq);
2514   phase->register_new_node(in_cset_fast_test_test, ctrl);
2515   IfNode* in_cset_fast_test_iff = new IfNode(ctrl, in_cset_fast_test_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
2516   phase->register_control(in_cset_fast_test_iff, loop, ctrl);
2517 
2518   not_cset_ctrl = new IfTrueNode(in_cset_fast_test_iff);
2519   phase->register_control(not_cset_ctrl, loop, in_cset_fast_test_iff);
2520 
2521   ctrl = new IfFalseNode(in_cset_fast_test_iff);
2522   phase->register_control(ctrl, loop, in_cset_fast_test_iff);
2523 }
2524 
2525 void ShenandoahWriteBarrierNode::call_wb_stub(Node*& ctrl, Node*& val, Node*& result_mem,
2526                                               Node* raw_mem, Node* wb_mem,
2527                                               int alias,
2528                                               PhaseIdealLoop* phase) {
2529   IdealLoopTree*loop = phase->get_loop(ctrl);
2530   const TypePtr* obj_type = phase->igvn().type(val)->is_oopptr()->cast_to_nonconst();
2531 
2532   // The slow path stub consumes and produces raw memory in addition
2533   // to the existing memory edges
2534   Node* base = find_bottom_mem(ctrl, phase);
2535 
2536   MergeMemNode* mm = MergeMemNode::make(base);
2537   mm->set_memory_at(alias, wb_mem);
2538   mm->set_memory_at(Compile::AliasIdxRaw, raw_mem);
2539   phase->register_new_node(mm, ctrl);
2540 
2541   Node* call = new CallLeafNode(ShenandoahBarrierSetC2::shenandoah_write_barrier_Type(), CAST_FROM_FN_PTR(address, ShenandoahRuntime::write_barrier_JRT), "shenandoah_write_barrier", TypeRawPtr::BOTTOM);
2542   call->init_req(TypeFunc::Control, ctrl);
2543   call->init_req(TypeFunc::I_O, phase->C->top());
2544   call->init_req(TypeFunc::Memory, mm);
2545   call->init_req(TypeFunc::FramePtr, phase->C->top());
2546   call->init_req(TypeFunc::ReturnAdr, phase->C->top());
2547   call->init_req(TypeFunc::Parms, val);
2548   phase->register_control(call, loop, ctrl);
2549   ctrl = new ProjNode(call, TypeFunc::Control);
2550   phase->register_control(ctrl, loop, call);
2551   result_mem = new ProjNode(call, TypeFunc::Memory);
2552   phase->register_new_node(result_mem, call);
2553   val = new ProjNode(call, TypeFunc::Parms);
2554   phase->register_new_node(val, call);
2555   val = new CheckCastPPNode(ctrl, val, obj_type);
2556   phase->register_new_node(val, ctrl);
2557 }
2558 
2559 void ShenandoahWriteBarrierNode::fix_ctrl(Node* barrier, Node* region, const MemoryGraphFixer& fixer, Unique_Node_List& uses, Unique_Node_List& uses_to_ignore, uint last, PhaseIdealLoop* phase) {
2560   Node* ctrl = phase->get_ctrl(barrier);
2561   Node* init_raw_mem = fixer.find_mem(ctrl, barrier);
2562 
2563   // Update the control of all nodes that should be after the
2564   // barrier control flow
2565   uses.clear();
2566   // Every node that is control dependent on the barrier's input
2567   // control will be after the expanded barrier. The raw memory (if
2568   // its memory is control dependent on the barrier's input control)
2569   // must stay above the barrier.
2570   uses_to_ignore.clear();
2571   if (phase->has_ctrl(init_raw_mem) && phase->get_ctrl(init_raw_mem) == ctrl && !init_raw_mem->is_Phi()) {
2572     uses_to_ignore.push(init_raw_mem);
2573   }
2574   for (uint next = 0; next < uses_to_ignore.size(); next++) {
2575     Node *n = uses_to_ignore.at(next);
2576     for (uint i = 0; i < n->req(); i++) {
2577       Node* in = n->in(i);
2578       if (in != NULL && phase->has_ctrl(in) && phase->get_ctrl(in) == ctrl) {
2579         uses_to_ignore.push(in);


2592       if (c != ctrl ||
2593           is_dominator_same_ctrl(old_c, barrier, u, phase) ||
2594           ShenandoahBarrierSetC2::is_shenandoah_state_load(u)) {
2595         phase->igvn().rehash_node_delayed(u);
2596         int nb = u->replace_edge(ctrl, region);
2597         if (u->is_CFG()) {
2598           if (phase->idom(u) == ctrl) {
2599             phase->set_idom(u, region, phase->dom_depth(region));
2600           }
2601         } else if (phase->get_ctrl(u) == ctrl) {
2602           assert(u != init_raw_mem, "should leave input raw mem above the barrier");
2603           uses.push(u);
2604         }
2605         assert(nb == 1, "more than 1 ctrl input?");
2606         --i, imax -= nb;
2607       }
2608     }
2609   }
2610 }
2611 
2612 void ShenandoahWriteBarrierNode::pin_and_expand(PhaseIdealLoop* phase) {
2613   Node_List enqueue_barriers;
2614   if (ShenandoahStoreValEnqueueBarrier) {
2615     Unique_Node_List wq;
2616     wq.push(phase->C->root());
2617     for (uint i = 0; i < wq.size(); i++) {
2618       Node* n = wq.at(i);
2619       if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
2620         enqueue_barriers.push(n);
2621       }
2622       for (uint i = 0; i < n->req(); i++) {
2623         Node* in = n->in(i);
2624         if (in != NULL) {
2625           wq.push(in);
2626         }
2627       }


2628     }
2629   }



2630 
2631   const bool trace = false;

2632 
2633   // Collect raw memory state at CFG points in the entire graph and
2634   // record it in memory_nodes. Optimize the raw memory graph in the
2635   // process. Optimizing the memory graph also makes the memory graph
2636   // simpler.
2637   GrowableArray<MemoryGraphFixer*> memory_graph_fixers;
2638 
2639   // Let's try to common write barriers again
2640   optimize_before_expansion(phase, memory_graph_fixers, true);
2641 
2642   Unique_Node_List uses;
2643   for (int i = 0; i < ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count(); i++) {
2644     ShenandoahWriteBarrierNode* wb = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barrier(i);
2645     Node* ctrl = phase->get_ctrl(wb);
2646 
2647     Node* val = wb->in(ValueIn);
2648     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
2649       assert(is_dominator(phase->get_ctrl(val), ctrl->in(0)->in(0), val, ctrl->in(0), phase), "can't move");
2650       phase->set_ctrl(wb, ctrl->in(0)->in(0));
2651     } else if (ctrl->is_CallRuntime()) {
2652       assert(is_dominator(phase->get_ctrl(val), ctrl->in(0), val, ctrl, phase), "can't move");
2653       phase->set_ctrl(wb, ctrl->in(0));
2654     }
2655 
2656     assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "only for write barriers");
2657     // Look for a null check that dominates this barrier and move the
2658     // barrier right after the null check to enable implicit null
2659     // checks
2660     wb->pin_and_expand_move_barrier(phase, memory_graph_fixers, uses);
2661 
2662     wb->pin_and_expand_helper(phase);
2663   }
2664 
2665   for (uint i = 0; i < enqueue_barriers.size(); i++) {
2666     Node* barrier = enqueue_barriers.at(i);
2667     Node* ctrl = phase->get_ctrl(barrier);
2668     IdealLoopTree* loop = phase->get_loop(ctrl);
2669     if (loop->_head->is_OuterStripMinedLoop()) {
2670       // Expanding a barrier here will break loop strip mining
2671       // verification. Transform the loop so the loop nest doesn't
2672       // appear as strip mined.
2673       OuterStripMinedLoopNode* outer = loop->_head->as_OuterStripMinedLoop();
2674       hide_strip_mined_loop(outer, outer->unique_ctrl_out()->as_CountedLoop(), phase);
2675     }
2676   }
2677 
2678   for (int i = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count(); i > 0; i--) {
2679     int cnt = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count();
2680     ShenandoahWriteBarrierNode* wb = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barrier(i-1);
2681     Node* ctrl = phase->get_ctrl(wb);
2682     IdealLoopTree* loop = phase->get_loop(ctrl);
2683     if (loop->_head->is_OuterStripMinedLoop()) {
2684       // Expanding a barrier here will break loop strip mining
2685       // verification. Transform the loop so the loop nest doesn't
2686       // appear as strip mined.
2687       OuterStripMinedLoopNode* outer = loop->_head->as_OuterStripMinedLoop();
2688       hide_strip_mined_loop(outer, outer->unique_ctrl_out()->as_CountedLoop(), phase);






























































































































































































2689     }
2690   }
2691 

2692   MemoryGraphFixer fixer(Compile::AliasIdxRaw, true, phase);
2693   Unique_Node_List uses_to_ignore;
2694   for (uint i = 0; i < enqueue_barriers.size(); i++) {
2695     Node* barrier = enqueue_barriers.at(i);













































































































































































2696     Node* pre_val = barrier->in(1);
2697 
2698     if (phase->igvn().type(pre_val)->higher_equal(TypePtr::NULL_PTR)) {
2699       ShouldNotReachHere();
2700       continue;
2701     }
2702 
2703     Node* ctrl = phase->get_ctrl(barrier);
2704 
2705     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
2706       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0)->in(0), pre_val, ctrl->in(0), phase), "can't move");
2707       ctrl = ctrl->in(0)->in(0);
2708       phase->set_ctrl(barrier, ctrl);
2709     } else if (ctrl->is_CallRuntime()) {
2710       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0), pre_val, ctrl, phase), "can't move");
2711       ctrl = ctrl->in(0);
2712       phase->set_ctrl(barrier, ctrl);
2713     }
2714 
2715     Node* init_ctrl = ctrl;


2822     phase->register_new_node(phi2, region2);
2823 
2824     region->init_req(_heap_unstable, region2);
2825     phi->init_req(_heap_unstable, phi2);
2826 
2827     phase->register_control(region, loop, heap_stable_ctrl->in(0));
2828     phase->register_new_node(phi, region);
2829 
2830     fix_ctrl(barrier, region, fixer, uses, uses_to_ignore, last, phase);
2831     for(uint next = 0; next < uses.size(); next++ ) {
2832       Node *n = uses.at(next);
2833       assert(phase->get_ctrl(n) == init_ctrl, "bad control");
2834       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
2835       phase->set_ctrl(n, region);
2836       follow_barrier_uses(n, init_ctrl, uses, phase);
2837     }
2838     fixer.fix_mem(init_ctrl, region, init_raw_mem, raw_mem_for_ctrl, phi, uses);
2839 
2840     phase->igvn().replace_node(barrier, pre_val);
2841   }

2842 
2843   for (int i = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count(); i > 0; i--) {
2844     int cnt = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count();
2845     ShenandoahWriteBarrierNode* wb = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barrier(i-1);
2846 
2847     uint last = phase->C->unique();
2848     Node* ctrl = phase->get_ctrl(wb);
2849     Node* orig_ctrl = ctrl;
2850 
2851     Node* raw_mem = fixer.find_mem(ctrl, wb);
2852     Node* init_raw_mem = raw_mem;
2853     Node* raw_mem_for_ctrl = fixer.find_mem(ctrl, NULL);
2854     int alias = phase->C->get_alias_index(wb->adr_type());
2855     Node* wb_mem =  wb->in(Memory);
2856     Node* init_wb_mem = wb_mem;
2857 
2858     Node* val = wb->in(ValueIn);
2859     Node* wbproj = wb->find_out_with(Op_ShenandoahWBMemProj);
2860     IdealLoopTree *loop = phase->get_loop(ctrl);
2861 
2862     assert(val->Opcode() != Op_ShenandoahWriteBarrier, "No chain of write barriers");
2863 
2864     CallStaticJavaNode* unc = wb->pin_and_expand_null_check(phase->igvn());
2865     Node* unc_ctrl = NULL;
2866     if (unc != NULL) {
2867       if (val->in(0) != ctrl) {
2868         unc = NULL;
2869       } else {
2870         unc_ctrl = val->in(0);
2871       }
2872     }
2873 
2874     Node* uncasted_val = val;
2875     if (unc != NULL) {
2876       uncasted_val = val->in(1);
2877     }
2878 
2879     Node* heap_stable_ctrl = NULL;
2880     Node* null_ctrl = NULL;
2881 
2882     assert(val->bottom_type()->make_oopptr(), "need oop");
2883     assert(val->bottom_type()->make_oopptr()->const_oop() == NULL, "expect non-constant");
2884 
2885     enum { _heap_stable = 1, _heap_unstable, PATH_LIMIT };
2886     Node* region = new RegionNode(PATH_LIMIT);
2887     Node* val_phi = new PhiNode(region, uncasted_val->bottom_type()->is_oopptr());
2888     Node* mem_phi = PhiNode::make(region, wb_mem, Type::MEMORY, phase->C->alias_type(wb->adr_type())->adr_type());
2889     Node* raw_mem_phi = PhiNode::make(region, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
2890 
2891     enum { _not_cset = 1, _not_equal, _evac_path, _null_path, PATH_LIMIT2 };
2892     Node* region2 = new RegionNode(PATH_LIMIT2);
2893     Node* val_phi2 = new PhiNode(region2, uncasted_val->bottom_type()->is_oopptr());
2894     Node* mem_phi2 = PhiNode::make(region2, wb_mem, Type::MEMORY, phase->C->alias_type(wb->adr_type())->adr_type());
2895     Node* raw_mem_phi2 = PhiNode::make(region2, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
2896 
2897       // Stable path.
2898     test_heap_stable(ctrl, raw_mem, heap_stable_ctrl, phase);
2899     IfNode* heap_stable_iff = heap_stable_ctrl->in(0)->as_If();
2900 
2901     // Heap stable case
2902     region->init_req(_heap_stable, heap_stable_ctrl);
2903     val_phi->init_req(_heap_stable, uncasted_val);
2904     mem_phi->init_req(_heap_stable, wb_mem);
2905     raw_mem_phi->init_req(_heap_stable, raw_mem);
2906 
2907     Node* reg2_ctrl = NULL;
2908     // Null case
2909     test_null(ctrl, val, null_ctrl, phase);
2910     if (null_ctrl != NULL) {
2911       reg2_ctrl = null_ctrl->in(0);
2912       region2->init_req(_null_path, null_ctrl);
2913       val_phi2->init_req(_null_path, uncasted_val);
2914       mem_phi2->init_req(_null_path, wb_mem);
2915       raw_mem_phi2->init_req(_null_path, raw_mem);
2916     } else {
2917       region2->del_req(_null_path);
2918       val_phi2->del_req(_null_path);
2919       mem_phi2->del_req(_null_path);
2920       raw_mem_phi2->del_req(_null_path);
2921     }
2922 
2923     // Test for in-cset.
2924     // Wires !in_cset(obj) to slot 2 of region and phis
2925     Node* not_cset_ctrl = NULL;
2926     in_cset_fast_test(ctrl, not_cset_ctrl, uncasted_val, raw_mem, phase);
2927     if (not_cset_ctrl != NULL) {
2928       if (reg2_ctrl == NULL) reg2_ctrl = not_cset_ctrl->in(0);
2929       region2->init_req(_not_cset, not_cset_ctrl);
2930       val_phi2->init_req(_not_cset, uncasted_val);
2931       mem_phi2->init_req(_not_cset, wb_mem);
2932       raw_mem_phi2->init_req(_not_cset, raw_mem);
2933     }
2934 
2935     // Resolve object when orig-value is in cset.
2936     // Make the unconditional resolve for fwdptr, not the read barrier.
2937     Node* new_val = uncasted_val;
2938     if (unc_ctrl != NULL) {
2939       // Clone the null check in this branch to allow implicit null check
2940       new_val = clone_null_check(ctrl, val, unc_ctrl, phase);
2941       fix_null_check(unc, unc_ctrl, ctrl->in(0)->as_If()->proj_out(0), uses, phase);
2942 
2943       IfNode* iff = unc_ctrl->in(0)->as_If();
2944       phase->igvn().replace_input_of(iff, 1, phase->igvn().intcon(1));
2945     }
2946     Node* addr = new AddPNode(new_val, uncasted_val, phase->igvn().MakeConX(ShenandoahBrooksPointer::byte_offset()));
2947     phase->register_new_node(addr, ctrl);
2948     assert(val->bottom_type()->isa_oopptr(), "what else?");
2949     const TypePtr* obj_type =  val->bottom_type()->is_oopptr();
2950     const TypePtr* adr_type = ShenandoahBarrierNode::brooks_pointer_type(obj_type);
2951     Node* fwd = new LoadPNode(ctrl, wb_mem, addr, adr_type, obj_type, MemNode::unordered);
2952     phase->register_new_node(fwd, ctrl);
2953 
2954     // Only branch to WB stub if object is not forwarded; otherwise reply with fwd ptr
2955     Node* cmp = new CmpPNode(fwd, new_val);
2956     phase->register_new_node(cmp, ctrl);
2957     Node* bol = new BoolNode(cmp, BoolTest::eq);
2958     phase->register_new_node(bol, ctrl);
2959 
2960     IfNode* iff = new IfNode(ctrl, bol, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
2961     if (reg2_ctrl == NULL) reg2_ctrl = iff;
2962     phase->register_control(iff, loop, ctrl);
2963     Node* if_not_eq = new IfFalseNode(iff);
2964     phase->register_control(if_not_eq, loop, iff);
2965     Node* if_eq = new IfTrueNode(iff);
2966     phase->register_control(if_eq, loop, iff);
2967 
2968     // Wire up not-equal-path in slots 3.
2969     region2->init_req(_not_equal, if_not_eq);
2970     val_phi2->init_req(_not_equal, fwd);
2971     mem_phi2->init_req(_not_equal, wb_mem);
2972     raw_mem_phi2->init_req(_not_equal, raw_mem);
2973 
2974     // Call wb-stub and wire up that path in slots 4
2975     Node* result_mem = NULL;
2976     ctrl = if_eq;
2977     call_wb_stub(ctrl, new_val, result_mem,
2978                  raw_mem, wb_mem,
2979                  alias, phase);
2980     region2->init_req(_evac_path, ctrl);
2981     val_phi2->init_req(_evac_path, new_val);
2982     mem_phi2->init_req(_evac_path, result_mem);
2983     raw_mem_phi2->init_req(_evac_path, result_mem);
2984 
2985     phase->register_control(region2, loop, reg2_ctrl);
2986     phase->register_new_node(val_phi2, region2);
2987     phase->register_new_node(mem_phi2, region2);
2988     phase->register_new_node(raw_mem_phi2, region2);
2989 
2990     region->init_req(_heap_unstable, region2);
2991     val_phi->init_req(_heap_unstable, val_phi2);
2992     mem_phi->init_req(_heap_unstable, mem_phi2);
2993     raw_mem_phi->init_req(_heap_unstable, raw_mem_phi2);
2994 
2995     phase->register_control(region, loop, heap_stable_iff);
2996     Node* out_val = val_phi;
2997     phase->register_new_node(val_phi, region);
2998     phase->register_new_node(mem_phi, region);
2999     phase->register_new_node(raw_mem_phi, region);
3000 
3001     fix_ctrl(wb, region, fixer, uses, uses_to_ignore, last, phase);
3002 
3003     ctrl = orig_ctrl;
3004 
3005     phase->igvn().replace_input_of(wbproj, ShenandoahWBMemProjNode::WriteBarrier, phase->C->top());
3006     phase->igvn().replace_node(wbproj, mem_phi);
3007     if (unc != NULL) {
3008       for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
3009         Node* u = val->fast_out(i);
3010         Node* c = phase->ctrl_or_self(u);
3011         if (u != wb && (c != ctrl || is_dominator_same_ctrl(c, wb, u, phase))) {
3012           phase->igvn().rehash_node_delayed(u);
3013           int nb = u->replace_edge(val, out_val);
3014           --i, imax -= nb;
3015         }
3016       }
3017       if (val->outcnt() == 0) {
3018         phase->igvn()._worklist.push(val);
3019       }
3020     }
3021     phase->igvn().replace_node(wb, out_val);
3022 
3023     follow_barrier_uses(mem_phi, ctrl, uses, phase);
3024     follow_barrier_uses(out_val, ctrl, uses, phase);
3025 
3026     for(uint next = 0; next < uses.size(); next++ ) {
3027       Node *n = uses.at(next);
3028       assert(phase->get_ctrl(n) == ctrl, "bad control");
3029       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
3030       phase->set_ctrl(n, region);
3031       follow_barrier_uses(n, ctrl, uses, phase);
3032     }
3033 
3034     // The slow path call produces memory: hook the raw memory phi
3035     // from the expanded write barrier with the rest of the graph
3036     // which may require adding memory phis at every post dominated
3037     // region and at enclosing loop heads. Use the memory state
3038     // collected in memory_nodes to fix the memory graph. Update that
3039     // memory state as we go.
3040     fixer.fix_mem(ctrl, region, init_raw_mem, raw_mem_for_ctrl, raw_mem_phi, uses);
3041     assert(ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count() == cnt - 1, "not replaced");
3042   }
3043 
3044   assert(ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count() == 0, "all write barrier nodes should have been replaced");
3045 }
3046 
3047 void ShenandoahWriteBarrierNode::move_heap_stable_test_out_of_loop(IfNode* iff, PhaseIdealLoop* phase) {
3048   IdealLoopTree *loop = phase->get_loop(iff);
3049   Node* loop_head = loop->_head;
3050   Node* entry_c = loop_head->in(LoopNode::EntryControl);
3051 
3052   Node* bol = iff->in(1);
3053   Node* cmp = bol->in(1);
3054   Node* andi = cmp->in(1);
3055   Node* load = andi->in(1);
3056 
3057   assert(is_gc_state_load(load), "broken");
3058   if (!phase->is_dominator(load->in(0), entry_c)) {
3059     Node* mem_ctrl = NULL;
3060     Node* mem = dom_mem(load->in(MemNode::Memory), loop_head, Compile::AliasIdxRaw, mem_ctrl, phase);
3061     load = load->clone();
3062     load->set_req(MemNode::Memory, mem);
3063     load->set_req(0, entry_c);
3064     phase->register_new_node(load, entry_c);
3065     andi = andi->clone();
3066     andi->set_req(1, load);
3067     phase->register_new_node(andi, entry_c);
3068     cmp = cmp->clone();
3069     cmp->set_req(1, andi);
3070     phase->register_new_node(cmp, entry_c);
3071     bol = bol->clone();
3072     bol->set_req(1, cmp);
3073     phase->register_new_node(bol, entry_c);
3074 
3075     Node* old_bol =iff->in(1);
3076     phase->igvn().replace_input_of(iff, 1, bol);
3077   }
3078 }
3079 
3080 bool ShenandoahWriteBarrierNode::identical_backtoback_ifs(Node *n, PhaseIdealLoop* phase) {
3081   if (!n->is_If() || n->is_CountedLoopEnd()) {
3082     return false;
3083   }
3084   Node* region = n->in(0);
3085 
3086   if (!region->is_Region()) {
3087     return false;
3088   }
3089   Node* dom = phase->idom(region);
3090   if (!dom->is_If()) {
3091     return false;
3092   }
3093 
3094   if (!is_heap_stable_test(n) || !is_heap_stable_test(dom)) {
3095     return false;
3096   }
3097 
3098   IfNode* dom_if = dom->as_If();
3099   Node* proj_true = dom_if->proj_out(1);
3100   Node* proj_false = dom_if->proj_out(0);
3101 
3102   for (uint i = 1; i < region->req(); i++) {
3103     if (phase->is_dominator(proj_true, region->in(i))) {
3104       continue;
3105     }
3106     if (phase->is_dominator(proj_false, region->in(i))) {
3107       continue;
3108     }
3109     return false;
3110   }
3111 
3112   return true;
3113 }
3114 
3115 void ShenandoahWriteBarrierNode::merge_back_to_back_tests(Node* n, PhaseIdealLoop* phase) {
3116   assert(is_heap_stable_test(n), "no other tests");
3117   if (identical_backtoback_ifs(n, phase)) {
3118     Node* n_ctrl = n->in(0);
3119     if (phase->can_split_if(n_ctrl)) {
3120       IfNode* dom_if = phase->idom(n_ctrl)->as_If();
3121       if (is_heap_stable_test(n)) {
3122         Node* gc_state_load = n->in(1)->in(1)->in(1)->in(1);
3123         assert(is_gc_state_load(gc_state_load), "broken");
3124         Node* dom_gc_state_load = dom_if->in(1)->in(1)->in(1)->in(1);
3125         assert(is_gc_state_load(dom_gc_state_load), "broken");
3126         if (gc_state_load != dom_gc_state_load) {
3127           phase->igvn().replace_node(gc_state_load, dom_gc_state_load);
3128         }
3129       }
3130       PhiNode* bolphi = PhiNode::make_blank(n_ctrl, n->in(1));
3131       Node* proj_true = dom_if->proj_out(1);
3132       Node* proj_false = dom_if->proj_out(0);
3133       Node* con_true = phase->igvn().makecon(TypeInt::ONE);
3134       Node* con_false = phase->igvn().makecon(TypeInt::ZERO);
3135 
3136       for (uint i = 1; i < n_ctrl->req(); i++) {
3137         if (phase->is_dominator(proj_true, n_ctrl->in(i))) {
3138           bolphi->init_req(i, con_true);
3139         } else {
3140           assert(phase->is_dominator(proj_false, n_ctrl->in(i)), "bad if");
3141           bolphi->init_req(i, con_false);
3142         }
3143       }
3144       phase->register_new_node(bolphi, n_ctrl);
3145       phase->igvn().replace_input_of(n, 1, bolphi);
3146       phase->do_split_if(n);
3147     }
3148   }
3149 }
3150 
3151 IfNode* ShenandoahWriteBarrierNode::find_unswitching_candidate(const IdealLoopTree *loop, PhaseIdealLoop* phase) {
3152   // Find first invariant test that doesn't exit the loop
3153   LoopNode *head = loop->_head->as_Loop();
3154   IfNode* unswitch_iff = NULL;
3155   Node* n = head->in(LoopNode::LoopBackControl);
3156   int loop_has_sfpts = -1;
3157   while (n != head) {
3158     Node* n_dom = phase->idom(n);
3159     if (n->is_Region()) {
3160       if (n_dom->is_If()) {
3161         IfNode* iff = n_dom->as_If();
3162         if (iff->in(1)->is_Bool()) {
3163           BoolNode* bol = iff->in(1)->as_Bool();
3164           if (bol->in(1)->is_Cmp()) {
3165             // If condition is invariant and not a loop exit,
3166             // then found reason to unswitch.
3167             if (is_heap_stable_test(iff) &&
3168                 (loop_has_sfpts == -1 || loop_has_sfpts == 0)) {
3169               assert(!loop->is_loop_exit(iff), "both branches should be in the loop");
3170               if (loop_has_sfpts == -1) {
3171                 for(uint i = 0; i < loop->_body.size(); i++) {


3176                   }
3177                 }
3178                 if (loop_has_sfpts == -1) {
3179                   loop_has_sfpts = 0;
3180                 }
3181               }
3182               if (!loop_has_sfpts) {
3183                 unswitch_iff = iff;
3184               }
3185             }
3186           }
3187         }
3188       }
3189     }
3190     n = n_dom;
3191   }
3192   return unswitch_iff;
3193 }
3194 
3195 
3196 void ShenandoahWriteBarrierNode::optimize_after_expansion(VectorSet &visited, Node_Stack &stack, Node_List &old_new, PhaseIdealLoop* phase) {
3197   Node_List heap_stable_tests;
3198   Node_List gc_state_loads;
3199 
3200   stack.push(phase->C->start(), 0);
3201   do {
3202     Node* n = stack.node();
3203     uint i = stack.index();
3204 
3205     if (i < n->outcnt()) {
3206       Node* u = n->raw_out(i);
3207       stack.set_index(i+1);
3208       if (!visited.test_set(u->_idx)) {
3209         stack.push(u, 0);
3210       }
3211     } else {
3212       stack.pop();
3213       if (ShenandoahCommonGCStateLoads && is_gc_state_load(n)) {
3214         gc_state_loads.push(n);
3215       }
3216       if (n->is_If() && is_heap_stable_test(n)) {
3217         heap_stable_tests.push(n);
3218       }
3219     }


3256             move_heap_stable_test_out_of_loop(iff, phase);
3257             if (loop->policy_unswitching(phase)) {
3258               if (head->is_strip_mined()) {
3259                 OuterStripMinedLoopNode* outer = head->as_CountedLoop()->outer_loop();
3260                 hide_strip_mined_loop(outer, head->as_CountedLoop(), phase);
3261               }
3262               phase->do_unswitching(loop, old_new);
3263             } else {
3264               // Not proceeding with unswitching. Move load back in
3265               // the loop.
3266               phase->igvn().replace_input_of(iff, 1, bol);
3267             }
3268           }
3269         }
3270       }
3271     }
3272   }
3273 }
3274 
3275 #ifdef ASSERT
3276 void ShenandoahBarrierNode::verify_raw_mem(RootNode* root) {
3277   const bool trace = false;
3278   ResourceMark rm;
3279   Unique_Node_List nodes;
3280   Unique_Node_List controls;
3281   Unique_Node_List memories;
3282 
3283   nodes.push(root);
3284   for (uint next = 0; next < nodes.size(); next++) {
3285     Node *n  = nodes.at(next);
3286     if (ShenandoahBarrierSetC2::is_shenandoah_wb_call(n)) {
3287       controls.push(n);
3288       if (trace) { tty->print("XXXXXX verifying"); n->dump(); }
3289       for (uint next2 = 0; next2 < controls.size(); next2++) {
3290         Node *m = controls.at(next2);
3291         for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
3292           Node* u = m->fast_out(i);
3293           if (u->is_CFG() && !u->is_Root() &&
3294               !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1) &&
3295               !(u->is_Region() && u->unique_ctrl_out()->Opcode() == Op_Halt)) {
3296             if (trace) { tty->print("XXXXXX pushing control"); u->dump(); }


3354                 }
3355               }
3356             }
3357           }
3358           assert(found_phi || all_in, "");
3359         }
3360       }
3361       controls.clear();
3362       memories.clear();
3363     }
3364     for( uint i = 0; i < n->len(); ++i ) {
3365       Node *m = n->in(i);
3366       if (m != NULL) {
3367         nodes.push(m);
3368       }
3369     }
3370   }
3371 }
3372 #endif
3373 




3374 const Type* ShenandoahEnqueueBarrierNode::bottom_type() const {
3375   if (in(1) == NULL || in(1)->is_top()) {
3376     return Type::TOP;
3377   }
3378   const Type* t = in(1)->bottom_type();
3379   if (t == TypePtr::NULL_PTR) {
3380     return t;
3381   }
3382   return t->is_oopptr()->cast_to_nonconst();
3383 }
3384 
3385 const Type* ShenandoahEnqueueBarrierNode::Value(PhaseGVN* phase) const {
3386   if (in(1) == NULL) {
3387     return Type::TOP;
3388   }
3389   const Type* t = phase->type(in(1));
3390   if (t == Type::TOP) {
3391     return Type::TOP;
3392   }
3393   if (t == TypePtr::NULL_PTR) {


3512     uint i = stack.index();
3513     if (i < n->req()) {
3514       Node* mem = NULL;
3515       if (opc == Op_Root) {
3516         Node* in = n->in(i);
3517         int in_opc = in->Opcode();
3518         if (in_opc == Op_Return || in_opc == Op_Rethrow) {
3519           mem = in->in(TypeFunc::Memory);
3520         } else if (in_opc == Op_Halt) {
3521           if (!in->in(0)->is_Region()) {
3522             Node* proj = in->in(0);
3523             assert(proj->is_Proj(), "");
3524             Node* in = proj->in(0);
3525             assert(in->is_CallStaticJava() || in->Opcode() == Op_NeverBranch || in->Opcode() == Op_Catch || proj->is_IfProj(), "");
3526             if (in->is_CallStaticJava()) {
3527               mem = in->in(TypeFunc::Memory);
3528             } else if (in->Opcode() == Op_Catch) {
3529               Node* call = in->in(0)->in(0);
3530               assert(call->is_Call(), "");
3531               mem = call->in(TypeFunc::Memory);




















3532             }
3533           }
3534         } else {
3535 #ifdef ASSERT
3536           n->dump();
3537           in->dump();
3538 #endif
3539           ShouldNotReachHere();
3540         }
3541       } else {
3542         assert(n->is_Phi() && n->bottom_type() == Type::MEMORY, "");
3543         assert(n->adr_type() == TypePtr::BOTTOM || _phase->C->get_alias_index(n->adr_type()) == _alias, "");
3544         mem = n->in(i);
3545       }
3546       i++;
3547       stack.set_index(i);
3548       if (mem == NULL) {
3549         continue;
3550       }
3551       for (;;) {
3552         if (visited.test_set(mem->_idx) || mem->is_Start()) {
3553           break;
3554         }
3555         if (mem->is_Phi()) {
3556           stack.push(mem, 2);
3557           mem = mem->in(1);
3558         } else if (mem->is_Proj()) {
3559           stack.push(mem, mem->req());
3560           mem = mem->in(0);
3561         } else if (mem->is_SafePoint() || mem->is_MemBar()) {
3562           mem = mem->in(TypeFunc::Memory);
3563         } else if (mem->is_MergeMem()) {
3564           MergeMemNode* mm = mem->as_MergeMem();
3565           mem = mm->memory_at(_alias);
3566         } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
3567           assert(_alias == Compile::AliasIdxRaw, "");
3568           stack.push(mem, mem->req());
3569           mem = mem->in(MemNode::Memory);
3570         } else if (mem->Opcode() == Op_ShenandoahWriteBarrier) {
3571           assert(_alias != Compile::AliasIdxRaw, "");
3572           mem = mem->in(ShenandoahBarrierNode::Memory);
3573         } else if (mem->Opcode() == Op_ShenandoahWBMemProj) {
3574           stack.push(mem, mem->req());
3575           mem = mem->in(ShenandoahWBMemProjNode::WriteBarrier);
3576         } else {
3577 #ifdef ASSERT
3578           mem->dump();
3579 #endif
3580           ShouldNotReachHere();
3581         }
3582       }
3583     } else {
3584       if (n->is_Phi()) {
3585         // Nothing
3586       } else if (!n->is_Root()) {
3587         Node* c = get_ctrl(n);
3588         _memory_nodes.map(c->_idx, n);
3589       }
3590       stack.pop();
3591     }
3592   } while(stack.is_nonempty());
3593 
3594   // Iterate over CFG nodes in rpo and propagate memory state to
3595   // compute memory state at regions, creating new phis if needed.


3609       }
3610     }
3611   }
3612 #endif
3613   uint last = _phase->C->unique();
3614 
3615 #ifdef ASSERT
3616   uint8_t max_depth = 0;
3617   for (LoopTreeIterator iter(_phase->ltree_root()); !iter.done(); iter.next()) {
3618     IdealLoopTree* lpt = iter.current();
3619     max_depth = MAX2(max_depth, lpt->_nest);
3620   }
3621 #endif
3622 
3623   bool progress = true;
3624   int iteration = 0;
3625   Node_List dead_phis;
3626   while (progress) {
3627     progress = false;
3628     iteration++;
3629     assert(iteration <= 2+max_depth || _phase->C->has_irreducible_loop(), "");
3630     if (trace) { tty->print_cr("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"); }
3631     IdealLoopTree* last_updated_ilt = NULL;
3632     for (int i = rpo_list.size() - 1; i >= 0; i--) {
3633       Node* c = rpo_list.at(i);
3634 
3635       Node* prev_mem = _memory_nodes[c->_idx];
3636       if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
3637         Node* prev_region = regions[c->_idx];
3638         Node* unique = NULL;
3639         for (uint j = 1; j < c->req() && unique != NodeSentinel; j++) {
3640           Node* m = _memory_nodes[c->in(j)->_idx];
3641           assert(m != NULL || (c->is_Loop() && j == LoopNode::LoopBackControl && iteration == 1) || _phase->C->has_irreducible_loop() || has_never_branch(_phase->C->root()), "expect memory state");
3642           if (m != NULL) {
3643             if (m == prev_region && ((c->is_Loop() && j == LoopNode::LoopBackControl) || (prev_region->is_Phi() && prev_region->in(0) == c))) {
3644               assert(c->is_Loop() && j == LoopNode::LoopBackControl || _phase->C->has_irreducible_loop(), "");
3645               // continue
3646             } else if (unique == NULL) {
3647               unique = m;
3648             } else if (m == unique) {
3649               // continue


3777   else {
3778     assert (n->is_CFG(), "must be a CFG node");
3779     return n;
3780   }
3781 }
3782 
3783 bool MemoryGraphFixer::mem_is_valid(Node* m, Node* c) const {
3784   return m != NULL && get_ctrl(m) == c;
3785 }
3786 
3787 Node* MemoryGraphFixer::find_mem(Node* ctrl, Node* n) const {
3788   assert(n == NULL || _phase->ctrl_or_self(n) == ctrl, "");
3789   Node* mem = _memory_nodes[ctrl->_idx];
3790   Node* c = ctrl;
3791   while (!mem_is_valid(mem, c) &&
3792          (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem))) {
3793     c = _phase->idom(c);
3794     mem = _memory_nodes[c->_idx];
3795   }
3796   if (n != NULL && mem_is_valid(mem, c)) {
3797     while (!ShenandoahWriteBarrierNode::is_dominator_same_ctrl(c, mem, n, _phase) && _phase->ctrl_or_self(mem) == ctrl) {
3798       mem = next_mem(mem, _alias);
3799     }
3800     if (mem->is_MergeMem()) {
3801       mem = mem->as_MergeMem()->memory_at(_alias);
3802     }
3803     if (!mem_is_valid(mem, c)) {
3804       do {
3805         c = _phase->idom(c);
3806         mem = _memory_nodes[c->_idx];
3807       } while (!mem_is_valid(mem, c) &&
3808                (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem)));
3809     }
3810   }
3811   assert(mem->bottom_type() == Type::MEMORY, "");
3812   return mem;
3813 }
3814 
3815 bool MemoryGraphFixer::has_mem_phi(Node* region) const {
3816   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
3817     Node* use = region->fast_out(i);


3823   return false;
3824 }
3825 
3826 void MemoryGraphFixer::fix_mem(Node* ctrl, Node* new_ctrl, Node* mem, Node* mem_for_ctrl, Node* new_mem, Unique_Node_List& uses) {
3827   assert(_phase->ctrl_or_self(new_mem) == new_ctrl, "");
3828   const bool trace = false;
3829   DEBUG_ONLY(if (trace) { tty->print("ZZZ control is"); ctrl->dump(); });
3830   DEBUG_ONLY(if (trace) { tty->print("ZZZ mem is"); mem->dump(); });
3831   GrowableArray<Node*> phis;
3832   if (mem_for_ctrl != mem) {
3833     Node* old = mem_for_ctrl;
3834     Node* prev = NULL;
3835     while (old != mem) {
3836       prev = old;
3837       if (old->is_Store() || old->is_ClearArray() || old->is_LoadStore()) {
3838         assert(_alias == Compile::AliasIdxRaw, "");
3839         old = old->in(MemNode::Memory);
3840       } else if (old->Opcode() == Op_SCMemProj) {
3841         assert(_alias == Compile::AliasIdxRaw, "");
3842         old = old->in(0);
3843       } else if (old->Opcode() == Op_ShenandoahWBMemProj) {
3844         assert(_alias != Compile::AliasIdxRaw, "");
3845         old = old->in(ShenandoahWBMemProjNode::WriteBarrier);
3846       } else if (old->Opcode() == Op_ShenandoahWriteBarrier) {
3847         assert(_alias != Compile::AliasIdxRaw, "");
3848         old = old->in(ShenandoahBarrierNode::Memory);
3849       } else {
3850         ShouldNotReachHere();
3851       }
3852     }
3853     assert(prev != NULL, "");
3854     if (new_ctrl != ctrl) {
3855       _memory_nodes.map(ctrl->_idx, mem);
3856       _memory_nodes.map(new_ctrl->_idx, mem_for_ctrl);
3857     }
3858     uint input = prev->Opcode() == Op_ShenandoahWriteBarrier ? (uint)ShenandoahBarrierNode::Memory : (uint)MemNode::Memory;
3859     _phase->igvn().replace_input_of(prev, input, new_mem);
3860   } else {
3861     uses.clear();
3862     _memory_nodes.map(new_ctrl->_idx, new_mem);
3863     uses.push(new_ctrl);
3864     for(uint next = 0; next < uses.size(); next++ ) {
3865       Node *n = uses.at(next);
3866       assert(n->is_CFG(), "");
3867       DEBUG_ONLY(if (trace) { tty->print("ZZZ ctrl"); n->dump(); });
3868       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3869         Node* u = n->fast_out(i);
3870         if (!u->is_Root() && u->is_CFG() && u != n) {
3871           Node* m = _memory_nodes[u->_idx];
3872           if (u->is_Region() && (!u->is_OuterStripMinedLoop() || _include_lsm) &&
3873               !has_mem_phi(u) &&
3874               u->unique_ctrl_out()->Opcode() != Op_Halt) {
3875             DEBUG_ONLY(if (trace) { tty->print("ZZZ region"); u->dump(); });
3876             DEBUG_ONLY(if (trace && m != NULL) { tty->print("ZZZ mem"); m->dump(); });
3877 
3878             if (!mem_is_valid(m, u) || !m->is_Phi()) {


3906                       do_check = false;
3907                     }
3908                   }
3909                 }
3910 
3911                 if (do_check && _phase->is_dominator(_phase->idom(u), new_ctrl)) {
3912                   create_phi = true;
3913                 }
3914               }
3915               if (create_phi) {
3916                 Node* phi = new PhiNode(u, Type::MEMORY, _phase->C->get_adr_type(_alias));
3917                 _phase->register_new_node(phi, u);
3918                 phis.push(phi);
3919                 DEBUG_ONLY(if (trace) { tty->print("ZZZ new phi"); phi->dump(); });
3920                 if (!mem_is_valid(m, u)) {
3921                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting mem"); phi->dump(); });
3922                   _memory_nodes.map(u->_idx, phi);
3923                 } else {
3924                   DEBUG_ONLY(if (trace) { tty->print("ZZZ NOT setting mem"); m->dump(); });
3925                   for (;;) {
3926                     assert(m->is_Mem() || m->is_LoadStore() || m->is_Proj() || m->Opcode() == Op_ShenandoahWriteBarrier || m->Opcode() == Op_ShenandoahWBMemProj, "");
3927                     Node* next = NULL;
3928                     if (m->is_Proj()) {
3929                       next = m->in(0);
3930                     } else if (m->Opcode() == Op_ShenandoahWBMemProj) {
3931                       next = m->in(ShenandoahWBMemProjNode::WriteBarrier);
3932                     } else if (m->is_Mem() || m->is_LoadStore()) {
3933                       assert(_alias == Compile::AliasIdxRaw, "");
3934                       next = m->in(MemNode::Memory);
3935                     } else {
3936                       assert(_alias != Compile::AliasIdxRaw, "");
3937                       assert (m->Opcode() == Op_ShenandoahWriteBarrier, "");
3938                       next = m->in(ShenandoahBarrierNode::Memory);
3939                     }
3940                     if (_phase->get_ctrl(next) != u) {
3941                       break;
3942                     }
3943                     if (next->is_MergeMem()) {
3944                       assert(_phase->get_ctrl(next->as_MergeMem()->memory_at(_alias)) != u, "");
3945                       break;
3946                     }
3947                     if (next->is_Phi()) {
3948                       assert(next->adr_type() == TypePtr::BOTTOM && next->in(0) == u, "");
3949                       break;
3950                     }
3951                     m = next;
3952                   }
3953 
3954                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting to phi"); m->dump(); });
3955                   assert(m->is_Mem() || m->is_LoadStore() || m->Opcode() == Op_ShenandoahWriteBarrier, "");
3956                   uint input = (m->is_Mem() || m->is_LoadStore()) ? (uint)MemNode::Memory : (uint)ShenandoahBarrierNode::Memory;
3957                   _phase->igvn().replace_input_of(m, input, phi);
3958                   push = false;
3959                 }
3960               } else {
3961                 DEBUG_ONLY(if (trace) { tty->print("ZZZ skipping region"); u->dump(); });
3962               }
3963               if (push) {
3964                 uses.push(u);
3965               }
3966             }
3967           } else if (!mem_is_valid(m, u) &&
3968                      !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1)) {
3969             uses.push(u);
3970           }
3971         }
3972       }
3973     }
3974     for (int i = 0; i < phis.length(); i++) {
3975       Node* n = phis.at(i);
3976       Node* r = n->in(0);


4162   if (phi->adr_type() == TypePtr::BOTTOM) {
4163     Node* region = phi->in(0);
4164     for (DUIterator_Fast jmax, j = region->fast_outs(jmax); j < jmax; j++) {
4165       Node* uu = region->fast_out(j);
4166       if (uu->is_Phi() && uu != phi && uu->bottom_type() == Type::MEMORY && _phase->C->get_alias_index(uu->adr_type()) == _alias) {
4167         return false;
4168       }
4169     }
4170     return true;
4171   }
4172   return _phase->C->get_alias_index(phi->adr_type()) == _alias;
4173 }
4174 
4175 void MemoryGraphFixer::fix_memory_uses(Node* mem, Node* replacement, Node* rep_proj, Node* rep_ctrl) const {
4176   uint last = _phase-> C->unique();
4177   MergeMemNode* mm = NULL;
4178   assert(mem->bottom_type() == Type::MEMORY, "");
4179   for (DUIterator i = mem->outs(); mem->has_out(i); i++) {
4180     Node* u = mem->out(i);
4181     if (u != replacement && u->_idx < last) {
4182       if (u->is_ShenandoahBarrier() && _alias != Compile::AliasIdxRaw) {
4183         if (_phase->C->get_alias_index(u->adr_type()) == _alias && ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4184           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
4185           assert(u->find_edge(mem) == -1, "only one edge");
4186           --i;
4187         }
4188       } else if (u->is_Mem()) {
4189         if (_phase->C->get_alias_index(u->adr_type()) == _alias && ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4190           assert(_alias == Compile::AliasIdxRaw , "only raw memory can lead to a memory operation");
4191           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
4192           assert(u->find_edge(mem) == -1, "only one edge");
4193           --i;
4194         }
4195       } else if (u->is_MergeMem()) {
4196         MergeMemNode* u_mm = u->as_MergeMem();
4197         if (u_mm->memory_at(_alias) == mem) {
4198           MergeMemNode* newmm = NULL;
4199           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
4200             Node* uu = u->fast_out(j);
4201             assert(!uu->is_MergeMem(), "chain of MergeMems?");
4202             if (uu->is_Phi()) {
4203               if (should_process_phi(uu)) {
4204                 Node* region = uu->in(0);
4205                 int nb = 0;
4206                 for (uint k = 1; k < uu->req(); k++) {
4207                   if (uu->in(k) == u && _phase->is_dominator(rep_ctrl, region->in(k))) {
4208                     if (newmm == NULL) {
4209                       newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
4210                     }
4211                     if (newmm != u) {
4212                       _phase->igvn().replace_input_of(uu, k, newmm);
4213                       nb++;
4214                       --jmax;
4215                     }
4216                   }
4217                 }
4218                 if (nb > 0) {
4219                   --j;
4220                 }
4221               }
4222             } else {
4223               if (rep_ctrl != uu && ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(uu), replacement, uu, _phase)) {
4224                 if (newmm == NULL) {
4225                   newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
4226                 }
4227                 if (newmm != u) {
4228                   _phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
4229                   --j, --jmax;
4230                 }
4231               }
4232             }
4233           }
4234         }
4235       } else if (u->is_Phi()) {
4236         assert(u->bottom_type() == Type::MEMORY, "what else?");
4237         Node* region = u->in(0);
4238         if (should_process_phi(u)) {
4239           bool replaced = false;
4240           for (uint j = 1; j < u->req(); j++) {
4241             if (u->in(j) == mem && _phase->is_dominator(rep_ctrl, region->in(j))) {
4242               Node* nnew = rep_proj;
4243               if (u->adr_type() == TypePtr::BOTTOM) {
4244                 if (mm == NULL) {
4245                   mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
4246                 }
4247                 nnew = mm;
4248               }
4249               _phase->igvn().replace_input_of(u, j, nnew);
4250               replaced = true;
4251             }
4252           }
4253           if (replaced) {
4254             --i;
4255           }
4256 
4257         }
4258       } else if ((u->adr_type() == TypePtr::BOTTOM && u->Opcode() != Op_StrInflatedCopy) ||
4259                  u->adr_type() == NULL) {
4260         assert(u->adr_type() != NULL ||
4261                u->Opcode() == Op_Rethrow ||
4262                u->Opcode() == Op_Return ||
4263                u->Opcode() == Op_SafePoint ||

4264                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
4265                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
4266                u->Opcode() == Op_CallLeaf, "");
4267         if (ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4268           if (mm == NULL) {
4269             mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
4270           }
4271           _phase->igvn().replace_input_of(u, u->find_edge(mem), mm);
4272           --i;
4273         }
4274       } else if (_phase->C->get_alias_index(u->adr_type()) == _alias) {
4275         if (ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4276           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
4277           --i;
4278         }
4279       }
4280     }
4281   }
4282 }
4283 
4284 void MemoryGraphFixer::remove(Node* n) {
4285   assert(n->Opcode() == Op_ShenandoahWBMemProj, "");
4286   Node* c = _phase->get_ctrl(n);
4287   Node* mem = find_mem(c, NULL);
4288   if (mem == n) {
4289     _memory_nodes.map(c->_idx, mem->in(ShenandoahWBMemProjNode::WriteBarrier)->in(ShenandoahBarrierNode::Memory));



























































4290   }

































































































































































































































































4291 }
   1 /*
   2  * Copyright (c) 2015, 2019, Red Hat, Inc. All rights reserved.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  *
  22  */
  23 
  24 #include "precompiled.hpp"
  25 
  26 #include "gc/shenandoah/c2/shenandoahSupport.hpp"
  27 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
  28 #include "gc/shenandoah/shenandoahBarrierSetAssembler.hpp"
  29 #include "gc/shenandoah/shenandoahBrooksPointer.hpp"
  30 #include "gc/shenandoah/shenandoahHeap.hpp"
  31 #include "gc/shenandoah/shenandoahHeapRegion.hpp"
  32 #include "gc/shenandoah/shenandoahRuntime.hpp"
  33 #include "gc/shenandoah/shenandoahThreadLocalData.hpp"
  34 #include "opto/arraycopynode.hpp"
  35 #include "opto/block.hpp"
  36 #include "opto/callnode.hpp"
  37 #include "opto/castnode.hpp"
  38 #include "opto/movenode.hpp"
  39 #include "opto/phaseX.hpp"
  40 #include "opto/rootnode.hpp"
  41 #include "opto/runtime.hpp"
  42 #include "opto/subnode.hpp"
  43 
  44 bool ShenandoahBarrierC2Support::expand(Compile* C, PhaseIterGVN& igvn) {
  45   ShenandoahBarrierSetC2State* state = ShenandoahBarrierSetC2::bsc2()->state();
  46   if ((state->enqueue_barriers_count() +
  47        state->load_reference_barriers_count()) > 0) {
  48     bool attempt_more_loopopts = ShenandoahLoopOptsAfterExpansion;
  49     C->clear_major_progress();
  50     PhaseIdealLoop ideal_loop(igvn, LoopOptsShenandoahExpand);
  51     if (C->failing()) return false;
  52     PhaseIdealLoop::verify(igvn);
  53     DEBUG_ONLY(verify_raw_mem(C->root());)
  54     if (attempt_more_loopopts) {
  55       C->set_major_progress();
  56       if (!C->optimize_loops(igvn, LoopOptsShenandoahPostExpand)) {












































































































































































  57         return false;
  58       }












































































































































































  59       C->clear_major_progress();











  60     }
  61   }
  62   return true;
  63 }
  64 
  65 bool ShenandoahBarrierC2Support::is_heap_state_test(Node* iff, int mask) {
  66   if (!UseShenandoahGC) {
  67     return false;
  68   }
  69   assert(iff->is_If(), "bad input");
  70   if (iff->Opcode() != Op_If) {
  71     return false;
  72   }
  73   Node* bol = iff->in(1);
  74   if (!bol->is_Bool() || bol->as_Bool()->_test._test != BoolTest::ne) {
  75     return false;
  76   }
  77   Node* cmp = bol->in(1);
  78   if (cmp->Opcode() != Op_CmpI) {
  79     return false;
  80   }
  81   Node* in1 = cmp->in(1);
  82   Node* in2 = cmp->in(2);
  83   if (in2->find_int_con(-1) != 0) {
  84     return false;
  85   }
  86   if (in1->Opcode() != Op_AndI) {
  87     return false;
  88   }
  89   in2 = in1->in(2);
  90   if (in2->find_int_con(-1) != mask) {
  91     return false;
  92   }
  93   in1 = in1->in(1);
  94 
  95   return is_gc_state_load(in1);
  96 }
  97 
  98 bool ShenandoahBarrierC2Support::is_heap_stable_test(Node* iff) {
  99   return is_heap_state_test(iff, ShenandoahHeap::HAS_FORWARDED);
 100 }
 101 
 102 bool ShenandoahBarrierC2Support::is_gc_state_load(Node *n) {
 103   if (!UseShenandoahGC) {
 104     return false;
 105   }
 106   if (n->Opcode() != Op_LoadB && n->Opcode() != Op_LoadUB) {
 107     return false;
 108   }
 109   Node* addp = n->in(MemNode::Address);
 110   if (!addp->is_AddP()) {
 111     return false;
 112   }
 113   Node* base = addp->in(AddPNode::Address);
 114   Node* off = addp->in(AddPNode::Offset);
 115   if (base->Opcode() != Op_ThreadLocal) {
 116     return false;
 117   }
 118   if (off->find_intptr_t_con(-1) != in_bytes(ShenandoahThreadLocalData::gc_state_offset())) {
 119     return false;
 120   }
 121   return true;
 122 }
 123 
 124 bool ShenandoahBarrierC2Support::has_safepoint_between(Node* start, Node* stop, PhaseIdealLoop *phase) {
 125   assert(phase->is_dominator(stop, start), "bad inputs");
 126   ResourceMark rm;
 127   Unique_Node_List wq;
 128   wq.push(start);
 129   for (uint next = 0; next < wq.size(); next++) {
 130     Node *m = wq.at(next);
 131     if (m == stop) {
 132       continue;
 133     }
 134     if (m->is_SafePoint() && !m->is_CallLeaf()) {
 135       return true;
 136     }
 137     if (m->is_Region()) {
 138       for (uint i = 1; i < m->req(); i++) {
 139         wq.push(m->in(i));
 140       }
 141     } else {
 142       wq.push(m->in(0));
 143     }
 144   }
 145   return false;
 146 }
 147 
 148 bool ShenandoahBarrierC2Support::try_common_gc_state_load(Node *n, PhaseIdealLoop *phase) {
 149   assert(is_gc_state_load(n), "inconsistent");
 150   Node* addp = n->in(MemNode::Address);
 151   Node* dominator = NULL;
 152   for (DUIterator_Fast imax, i = addp->fast_outs(imax); i < imax; i++) {
 153     Node* u = addp->fast_out(i);
 154     assert(is_gc_state_load(u), "inconsistent");
 155     if (u != n && phase->is_dominator(u->in(0), n->in(0))) {
 156       if (dominator == NULL) {
 157         dominator = u;
 158       } else {
 159         if (phase->dom_depth(u->in(0)) < phase->dom_depth(dominator->in(0))) {
 160           dominator = u;
 161         }
 162       }
 163     }
 164   }
 165   if (dominator == NULL || has_safepoint_between(n->in(0), dominator->in(0), phase)) {
 166     return false;
 167   }
 168   phase->igvn().replace_node(n, dominator);
 169 
 170   return true;
 171 }
 172 




















































 173 #ifdef ASSERT
 174 bool ShenandoahBarrierC2Support::verify_helper(Node* in, Node_Stack& phis, VectorSet& visited, verify_type t, bool trace, Unique_Node_List& barriers_used) {





































































































































 175   assert(phis.size() == 0, "");
 176 
 177   while (true) {
 178     if (in->bottom_type() == TypePtr::NULL_PTR) {
 179       if (trace) {tty->print_cr("NULL");}
 180     } else if (!in->bottom_type()->make_ptr()->make_oopptr()) {
 181       if (trace) {tty->print_cr("Non oop");}
 182     } else if (t == ShenandoahLoad && ShenandoahOptimizeStableFinals &&
 183                in->bottom_type()->make_ptr()->isa_aryptr() &&
 184                in->bottom_type()->make_ptr()->is_aryptr()->is_stable()) {
 185       if (trace) {tty->print_cr("Stable array load");}
 186     } else {
 187       if (in->is_ConstraintCast()) {
 188         in = in->in(1);
 189         continue;
 190       } else if (in->is_AddP()) {
 191         assert(!in->in(AddPNode::Address)->is_top(), "no raw memory access");
 192         in = in->in(AddPNode::Address);
 193         continue;
 194       } else if (in->is_Con()) {
 195         if (trace) {
 196           tty->print("Found constant");
 197           in->dump();
 198         }
 199       } else if (in->Opcode() == Op_Parm) {
 200         if (trace) {
 201           tty->print("Found argument");
 202         }
 203       } else if (in->Opcode() == Op_CreateEx) {
 204         if (trace) {
 205           tty->print("Found create-exception");
 206         }
 207       } else if (in->Opcode() == Op_LoadP && in->adr_type() == TypeRawPtr::BOTTOM) {
 208         if (trace) {
 209           tty->print("Found raw LoadP (OSR argument?)");
 210         }
 211       } else if (in->Opcode() == Op_ShenandoahLoadReferenceBarrier) {
 212         if (t == ShenandoahOopStore) {



 213           uint i = 0;
 214           for (; i < phis.size(); i++) {
 215             Node* n = phis.node_at(i);
 216             if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
 217               break;
 218             }
 219           }
 220           if (i == phis.size()) {
 221             return false;
 222           }


 223         }
 224         barriers_used.push(in);
 225         if (trace) {tty->print("Found barrier"); in->dump();}
 226       } else if (in->Opcode() == Op_ShenandoahEnqueueBarrier) {
 227         if (t != ShenandoahOopStore) {
 228           in = in->in(1);
 229           continue;
 230         }
 231         if (trace) {tty->print("Found enqueue barrier"); in->dump();}
 232         phis.push(in, in->req());
 233         in = in->in(1);
 234         continue;
 235       } else if (in->is_Proj() && in->in(0)->is_Allocate()) {
 236         if (trace) {
 237           tty->print("Found alloc");
 238           in->in(0)->dump();
 239         }
 240       } else if (in->is_Proj() && (in->in(0)->Opcode() == Op_CallStaticJava || in->in(0)->Opcode() == Op_CallDynamicJava)) {
 241         if (trace) {
 242           tty->print("Found Java call");
 243         }
 244       } else if (in->is_Phi()) {
 245         if (!visited.test_set(in->_idx)) {
 246           if (trace) {tty->print("Pushed phi:"); in->dump();}
 247           phis.push(in, 2);
 248           in = in->in(1);
 249           continue;
 250         }
 251         if (trace) {tty->print("Already seen phi:"); in->dump();}
 252       } else if (in->Opcode() == Op_CMoveP || in->Opcode() == Op_CMoveN) {
 253         if (!visited.test_set(in->_idx)) {
 254           if (trace) {tty->print("Pushed cmovep:"); in->dump();}
 255           phis.push(in, CMoveNode::IfTrue);
 256           in = in->in(CMoveNode::IfFalse);
 257           continue;
 258         }
 259         if (trace) {tty->print("Already seen cmovep:"); in->dump();}
 260       } else if (in->Opcode() == Op_EncodeP || in->Opcode() == Op_DecodeN) {
 261         in = in->in(1);
 262         continue;
 263       } else {


 269       uint idx = phis.index();
 270       Node* phi = phis.node();
 271       if (idx >= phi->req()) {
 272         if (trace) {tty->print("Popped phi:"); phi->dump();}
 273         phis.pop();
 274         continue;
 275       }
 276       if (trace) {tty->print("Next entry(%d) for phi:", idx); phi->dump();}
 277       in = phi->in(idx);
 278       phis.set_index(idx+1);
 279       cont = true;
 280       break;
 281     }
 282     if (!cont) {
 283       break;
 284     }
 285   }
 286   return true;
 287 }
 288 
 289 void ShenandoahBarrierC2Support::report_verify_failure(const char* msg, Node* n1, Node* n2) {
 290   if (n1 != NULL) {
 291     n1->dump(+10);
 292   }
 293   if (n2 != NULL) {
 294     n2->dump(+10);
 295   }
 296   fatal("%s", msg);
 297 }
 298 
 299 void ShenandoahBarrierC2Support::verify(RootNode* root) {
 300   ResourceMark rm;
 301   Unique_Node_List wq;
 302   GrowableArray<Node*> barriers;
 303   Unique_Node_List barriers_used;
 304   Node_Stack phis(0);
 305   VectorSet visited(Thread::current()->resource_area());
 306   const bool trace = false;
 307   const bool verify_no_useless_barrier = false;
 308 
 309   wq.push(root);
 310   for (uint next = 0; next < wq.size(); next++) {
 311     Node *n = wq.at(next);
 312     if (n->is_Load()) {
 313       const bool trace = false;
 314       if (trace) {tty->print("Verifying"); n->dump();}
 315       if (n->Opcode() == Op_LoadRange || n->Opcode() == Op_LoadKlass || n->Opcode() == Op_LoadNKlass) {
 316         if (trace) {tty->print_cr("Load range/klass");}
 317       } else {
 318         const TypePtr* adr_type = n->as_Load()->adr_type();
 319 


 331             assert(k->is_instance_klass(), "");
 332             ciInstanceKlass* ik = (ciInstanceKlass*)k;
 333             int offset = adr_type->offset();
 334 
 335             if ((ik->debug_final_field_at(offset) && ShenandoahOptimizeInstanceFinals) ||
 336                 (ik->debug_stable_field_at(offset) && ShenandoahOptimizeStableFinals)) {
 337               if (trace) {tty->print_cr("Final/stable");}
 338               verify = false;
 339             } else if (k == ciEnv::current()->Class_klass() &&
 340                        tinst->const_oop() != NULL &&
 341                        tinst->offset() >= (ik->size_helper() * wordSize)) {
 342               ciInstanceKlass* k = tinst->const_oop()->as_instance()->java_lang_Class_klass()->as_instance_klass();
 343               ciField* field = k->get_field_by_offset(tinst->offset(), true);
 344               if ((ShenandoahOptimizeStaticFinals && field->is_final()) ||
 345                   (ShenandoahOptimizeStableFinals && field->is_stable())) {
 346                 verify = false;
 347               }
 348             }
 349           }
 350 
 351           if (verify && !verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahLoad, trace, barriers_used)) {
 352             report_verify_failure("Shenandoah verification: Load should have barriers", n);
 353           }
 354         }
 355       }
 356     } else if (n->is_Store()) {
 357       const bool trace = false;
 358 
 359       if (trace) {tty->print("Verifying"); n->dump();}
 360       if (n->in(MemNode::ValueIn)->bottom_type()->make_oopptr()) {
 361         Node* adr = n->in(MemNode::Address);
 362         bool verify = true;
 363 
 364         if (adr->is_AddP() && adr->in(AddPNode::Base)->is_top()) {
 365           adr = adr->in(AddPNode::Address);
 366           if (adr->is_AddP()) {
 367             assert(adr->in(AddPNode::Base)->is_top(), "");
 368             adr = adr->in(AddPNode::Address);
 369             if (adr->Opcode() == Op_LoadP &&
 370                 adr->in(MemNode::Address)->in(AddPNode::Base)->is_top() &&
 371                 adr->in(MemNode::Address)->in(AddPNode::Address)->Opcode() == Op_ThreadLocal &&
 372                 adr->in(MemNode::Address)->in(AddPNode::Offset)->find_intptr_t_con(-1) == in_bytes(ShenandoahThreadLocalData::satb_mark_queue_buffer_offset())) {
 373               if (trace) {tty->print_cr("SATB prebarrier");}
 374               verify = false;
 375             }
 376           }
 377         }
 378 
 379         if (verify && !verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahStoreValEnqueueBarrier ? ShenandoahOopStore : ShenandoahValue, trace, barriers_used)) {
 380           report_verify_failure("Shenandoah verification: Store should have barriers", n);
 381         }
 382       }
 383       if (!verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 384         report_verify_failure("Shenandoah verification: Store (address) should have barriers", n);
 385       }
 386     } else if (n->Opcode() == Op_CmpP) {
 387       const bool trace = false;
 388 
 389       Node* in1 = n->in(1);
 390       Node* in2 = n->in(2);
 391       if (in1->bottom_type()->isa_oopptr()) {
 392         if (trace) {tty->print("Verifying"); n->dump();}
 393 
 394         bool mark_inputs = false;
 395         if (in1->bottom_type() == TypePtr::NULL_PTR || in2->bottom_type() == TypePtr::NULL_PTR ||
 396             (in1->is_Con() || in2->is_Con())) {
 397           if (trace) {tty->print_cr("Comparison against a constant");}
 398           mark_inputs = true;
 399         } else if ((in1->is_CheckCastPP() && in1->in(1)->is_Proj() && in1->in(1)->in(0)->is_Allocate()) ||
 400                    (in2->is_CheckCastPP() && in2->in(1)->is_Proj() && in2->in(1)->in(0)->is_Allocate())) {
 401           if (trace) {tty->print_cr("Comparison with newly alloc'ed object");}
 402           mark_inputs = true;
 403         } else {
 404           assert(in2->bottom_type()->isa_oopptr(), "");
 405 
 406           if (!verify_helper(in1, phis, visited, ShenandoahStore, trace, barriers_used) ||
 407               !verify_helper(in2, phis, visited, ShenandoahStore, trace, barriers_used)) {
 408             report_verify_failure("Shenandoah verification: Cmp should have barriers", n);
 409           }
 410         }
 411         if (verify_no_useless_barrier &&
 412             mark_inputs &&
 413             (!verify_helper(in1, phis, visited, ShenandoahValue, trace, barriers_used) ||
 414              !verify_helper(in2, phis, visited, ShenandoahValue, trace, barriers_used))) {
 415           phis.clear();
 416           visited.Reset();
 417         }
 418       }
 419     } else if (n->is_LoadStore()) {
 420       if (n->in(MemNode::ValueIn)->bottom_type()->make_ptr() &&
 421           !verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahStoreValEnqueueBarrier ? ShenandoahOopStore : ShenandoahValue, trace, barriers_used)) {
 422         report_verify_failure("Shenandoah verification: LoadStore (value) should have barriers", n);
 423       }
 424 
 425       if (n->in(MemNode::Address)->bottom_type()->make_oopptr() && !verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 426         report_verify_failure("Shenandoah verification: LoadStore (address) should have barriers", n);
 427       }
 428     } else if (n->Opcode() == Op_CallLeafNoFP || n->Opcode() == Op_CallLeaf) {
 429       CallNode* call = n->as_Call();
 430 
 431       static struct {
 432         const char* name;
 433         struct {
 434           int pos;
 435           verify_type t;
 436         } args[6];
 437       } calls[] = {
 438         "aescrypt_encryptBlock",
 439         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 440           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 441         "aescrypt_decryptBlock",
 442         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 443           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 444         "multiplyToLen",
 445         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },   { TypeFunc::Parms+4, ShenandoahStore },


 501         "sha512_implCompressMB",
 502         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 503           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 504         "encodeBlock",
 505         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+3, ShenandoahStore },   { -1, ShenandoahNone },
 506           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 507       };
 508 
 509       if (call->is_call_to_arraycopystub()) {
 510         Node* dest = NULL;
 511         const TypeTuple* args = n->as_Call()->_tf->domain();
 512         for (uint i = TypeFunc::Parms, j = 0; i < args->cnt(); i++) {
 513           if (args->field_at(i)->isa_ptr()) {
 514             j++;
 515             if (j == 2) {
 516               dest = n->in(i);
 517               break;
 518             }
 519           }
 520         }
 521         if (!verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahLoad, trace, barriers_used) ||
 522             !verify_helper(dest, phis, visited, ShenandoahStore, trace, barriers_used)) {
 523           report_verify_failure("Shenandoah verification: ArrayCopy should have barriers", n);
 524         }
 525       } else if (strlen(call->_name) > 5 &&
 526                  !strcmp(call->_name + strlen(call->_name) - 5, "_fill")) {
 527         if (!verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahStore, trace, barriers_used)) {
 528           report_verify_failure("Shenandoah verification: _fill should have barriers", n);
 529         }
 530       } else if (!strcmp(call->_name, "shenandoah_wb_pre")) {
 531         // skip
 532       } else {
 533         const int calls_len = sizeof(calls) / sizeof(calls[0]);
 534         int i = 0;
 535         for (; i < calls_len; i++) {
 536           if (!strcmp(calls[i].name, call->_name)) {
 537             break;
 538           }
 539         }
 540         if (i != calls_len) {
 541           const uint args_len = sizeof(calls[0].args) / sizeof(calls[0].args[0]);
 542           for (uint j = 0; j < args_len; j++) {
 543             int pos = calls[i].args[j].pos;
 544             if (pos == -1) {
 545               break;
 546             }
 547             if (!verify_helper(call->in(pos), phis, visited, calls[i].args[j].t, trace, barriers_used)) {
 548               report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
 549             }
 550           }
 551           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
 552             if (call->in(j)->bottom_type()->make_ptr() &&
 553                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 554               uint k = 0;
 555               for (; k < args_len && calls[i].args[k].pos != (int)j; k++);
 556               if (k == args_len) {
 557                 fatal("arg %d for call %s not covered", j, call->_name);
 558               }
 559             }
 560           }
 561         } else {
 562           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
 563             if (call->in(j)->bottom_type()->make_ptr() &&
 564                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 565               fatal("%s not covered", call->_name);
 566             }
 567           }
 568         }
 569       }
 570     } else if (n->Opcode() == Op_ShenandoahEnqueueBarrier || n->Opcode() == Op_ShenandoahLoadReferenceBarrier) {





 571       // skip


 572     } else if (n->is_AddP()
 573                || n->is_Phi()
 574                || n->is_ConstraintCast()
 575                || n->Opcode() == Op_Return
 576                || n->Opcode() == Op_CMoveP
 577                || n->Opcode() == Op_CMoveN
 578                || n->Opcode() == Op_Rethrow
 579                || n->is_MemBar()
 580                || n->Opcode() == Op_Conv2B
 581                || n->Opcode() == Op_SafePoint
 582                || n->is_CallJava()
 583                || n->Opcode() == Op_Unlock
 584                || n->Opcode() == Op_EncodeP
 585                || n->Opcode() == Op_DecodeN) {
 586       // nothing to do
 587     } else {
 588       static struct {
 589         int opcode;
 590         struct {
 591           int pos;


 618         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
 619         Op_StrIndexOfChar,
 620         { { 2, ShenandoahLoad },                  { -1, ShenandoahNone } },
 621       };
 622 
 623       const int others_len = sizeof(others) / sizeof(others[0]);
 624       int i = 0;
 625       for (; i < others_len; i++) {
 626         if (others[i].opcode == n->Opcode()) {
 627           break;
 628         }
 629       }
 630       uint stop = n->is_Call() ? n->as_Call()->tf()->domain()->cnt() : n->req();
 631       if (i != others_len) {
 632         const uint inputs_len = sizeof(others[0].inputs) / sizeof(others[0].inputs[0]);
 633         for (uint j = 0; j < inputs_len; j++) {
 634           int pos = others[i].inputs[j].pos;
 635           if (pos == -1) {
 636             break;
 637           }
 638           if (!verify_helper(n->in(pos), phis, visited, others[i].inputs[j].t, trace, barriers_used)) {
 639             report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
 640           }
 641         }
 642         for (uint j = 1; j < stop; j++) {
 643           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
 644               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
 645             uint k = 0;
 646             for (; k < inputs_len && others[i].inputs[k].pos != (int)j; k++);
 647             if (k == inputs_len) {
 648               fatal("arg %d for node %s not covered", j, n->Name());
 649             }
 650           }
 651         }
 652       } else {
 653         for (uint j = 1; j < stop; j++) {
 654           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
 655               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
 656             fatal("%s not covered", n->Name());
 657           }
 658         }
 659       }
 660     }
 661 
 662     if (n->is_SafePoint()) {
 663       SafePointNode* sfpt = n->as_SafePoint();
 664       if (verify_no_useless_barrier && sfpt->jvms() != NULL) {
 665         for (uint i = sfpt->jvms()->scloff(); i < sfpt->jvms()->endoff(); i++) {
 666           if (!verify_helper(sfpt->in(i), phis, visited, ShenandoahLoad, trace, barriers_used)) {
 667             phis.clear();
 668             visited.Reset();
 669           }
 670         }
 671       }
 672     }
 673     for( uint i = 0; i < n->len(); ++i ) {
 674       Node *m = n->in(i);
 675       if (m == NULL) continue;
 676 
 677       // In most cases, inputs should be known to be non null. If it's
 678       // not the case, it could be a missing cast_not_null() in an
 679       // intrinsic or support might be needed in AddPNode::Ideal() to
 680       // avoid a NULL+offset input.
 681       if (!(n->is_Phi() ||
 682             (n->is_SafePoint() && (!n->is_CallRuntime() || !strcmp(n->as_Call()->_name, "shenandoah_wb_pre") || !strcmp(n->as_Call()->_name, "unsafe_arraycopy"))) ||
 683             n->Opcode() == Op_CmpP ||
 684             n->Opcode() == Op_CmpN ||
 685             (n->Opcode() == Op_StoreP && i == StoreNode::ValueIn) ||
 686             (n->Opcode() == Op_StoreN && i == StoreNode::ValueIn) ||
 687             n->is_ConstraintCast() ||
 688             n->Opcode() == Op_Return ||
 689             n->Opcode() == Op_Conv2B ||
 690             n->is_AddP() ||
 691             n->Opcode() == Op_CMoveP ||
 692             n->Opcode() == Op_CMoveN ||
 693             n->Opcode() == Op_Rethrow ||
 694             n->is_MemBar() ||
 695             n->is_Mem() ||
 696             n->Opcode() == Op_AryEq ||
 697             n->Opcode() == Op_SCMemProj ||
 698             n->Opcode() == Op_EncodeP ||
 699             n->Opcode() == Op_DecodeN ||
 700             n->Opcode() == Op_ShenandoahEnqueueBarrier ||
 701             n->Opcode() == Op_ShenandoahLoadReferenceBarrier)) {

 702         if (m->bottom_type()->make_oopptr() && m->bottom_type()->make_oopptr()->meet(TypePtr::NULL_PTR) == m->bottom_type()) {
 703           report_verify_failure("Shenandoah verification: null input", n, m);
 704         }
 705       }
 706 
 707       wq.push(m);
 708     }
 709   }
 710 
 711   if (verify_no_useless_barrier) {
 712     for (int i = 0; i < barriers.length(); i++) {
 713       Node* n = barriers.at(i);
 714       if (!barriers_used.member(n)) {
 715         tty->print("XXX useless barrier"); n->dump(-2);
 716         ShouldNotReachHere();
 717       }
 718     }
 719   }
 720 }
 721 #endif
 722 
 723 bool ShenandoahBarrierC2Support::is_dominator_same_ctrl(Node* c, Node* d, Node* n, PhaseIdealLoop* phase) {
 724   // That both nodes have the same control is not sufficient to prove
 725   // domination, verify that there's no path from d to n
 726   ResourceMark rm;
 727   Unique_Node_List wq;
 728   wq.push(d);
 729   for (uint next = 0; next < wq.size(); next++) {
 730     Node *m = wq.at(next);
 731     if (m == n) {
 732       return false;
 733     }
 734     if (m->is_Phi() && m->in(0)->is_Loop()) {
 735       assert(phase->ctrl_or_self(m->in(LoopNode::EntryControl)) != c, "following loop entry should lead to new control");
 736     } else {
 737       for (uint i = 0; i < m->req(); i++) {
 738         if (m->in(i) != NULL && phase->ctrl_or_self(m->in(i)) == c) {
 739           wq.push(m->in(i));
 740         }
 741       }
 742     }
 743   }
 744   return true;
 745 }
 746 
 747 bool ShenandoahBarrierC2Support::is_dominator(Node* d_c, Node* n_c, Node* d, Node* n, PhaseIdealLoop* phase) {
 748   if (d_c != n_c) {
 749     return phase->is_dominator(d_c, n_c);
 750   }
 751   return is_dominator_same_ctrl(d_c, d, n, phase);
 752 }
 753 
 754 Node* next_mem(Node* mem, int alias) {
 755   Node* res = NULL;
 756   if (mem->is_Proj()) {
 757     res = mem->in(0);
 758   } else if (mem->is_SafePoint() || mem->is_MemBar()) {
 759     res = mem->in(TypeFunc::Memory);
 760   } else if (mem->is_Phi()) {
 761     res = mem->in(1);


 762   } else if (mem->is_MergeMem()) {
 763     res = mem->as_MergeMem()->memory_at(alias);
 764   } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
 765     assert(alias = Compile::AliasIdxRaw, "following raw memory can't lead to a barrier");
 766     res = mem->in(MemNode::Memory);


 767   } else {
 768 #ifdef ASSERT
 769     mem->dump();
 770 #endif
 771     ShouldNotReachHere();
 772   }
 773   return res;
 774 }
 775 
 776 Node* ShenandoahBarrierC2Support::no_branches(Node* c, Node* dom, bool allow_one_proj, PhaseIdealLoop* phase) {
 777   Node* iffproj = NULL;
 778   while (c != dom) {
 779     Node* next = phase->idom(c);
 780     assert(next->unique_ctrl_out() == c || c->is_Proj() || c->is_Region(), "multiple control flow out but no proj or region?");
 781     if (c->is_Region()) {
 782       ResourceMark rm;
 783       Unique_Node_List wq;
 784       wq.push(c);
 785       for (uint i = 0; i < wq.size(); i++) {
 786         Node *n = wq.at(i);
 787         if (n == next) {
 788           continue;
 789         }
 790         if (n->is_Region()) {
 791           for (uint j = 1; j < n->req(); j++) {
 792             wq.push(n->in(j));
 793           }
 794         } else {
 795           wq.push(n->in(0));
 796         }


 821             iffproj = c;
 822           } else {
 823             return NodeSentinel;
 824           }
 825         }
 826       } else if (c->Opcode() == Op_JumpProj) {
 827         return NodeSentinel; // unsupported
 828       } else if (c->Opcode() == Op_CatchProj) {
 829         return NodeSentinel; // unsupported
 830       } else if (c->Opcode() == Op_CProj && next->Opcode() == Op_NeverBranch) {
 831         return NodeSentinel; // unsupported
 832       } else {
 833         assert(next->unique_ctrl_out() == c, "unsupported branch pattern");
 834       }
 835     }
 836     c = next;
 837   }
 838   return iffproj;
 839 }
 840 
 841 Node* ShenandoahBarrierC2Support::dom_mem(Node* mem, Node* ctrl, int alias, Node*& mem_ctrl, PhaseIdealLoop* phase) {







































































































































































































































































 842   ResourceMark rm;
 843   VectorSet wq(Thread::current()->resource_area());
 844   wq.set(mem->_idx);
 845   mem_ctrl = phase->ctrl_or_self(mem);
 846   while (!phase->is_dominator(mem_ctrl, ctrl) || mem_ctrl == ctrl) {
 847     mem = next_mem(mem, alias);
 848     if (wq.test_set(mem->_idx)) {
 849       return NULL;
 850     }
 851     mem_ctrl = phase->ctrl_or_self(mem);
 852   }
 853   if (mem->is_MergeMem()) {
 854     mem = mem->as_MergeMem()->memory_at(alias);
 855     mem_ctrl = phase->ctrl_or_self(mem);
 856   }
 857   return mem;
 858 }
 859 
 860 Node* ShenandoahBarrierC2Support::find_bottom_mem(Node* ctrl, PhaseIdealLoop* phase) {



































































































































































































































































































































































































































































































































































































































































 861   Node* mem = NULL;
 862   Node* c = ctrl;
 863   do {
 864     if (c->is_Region()) {
 865       Node* phi_bottom = NULL;
 866       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax && mem == NULL; i++) {
 867         Node* u = c->fast_out(i);
 868         if (u->is_Phi() && u->bottom_type() == Type::MEMORY) {
 869           if (u->adr_type() == TypePtr::BOTTOM) {
 870             mem = u;
 871           }
 872         }
 873       }
 874     } else {
 875       if (c->is_Call() && c->as_Call()->adr_type() != NULL) {
 876         CallProjections projs;
 877         c->as_Call()->extract_projections(&projs, true, false);
 878         if (projs.fallthrough_memproj != NULL) {
 879           if (projs.fallthrough_memproj->adr_type() == TypePtr::BOTTOM) {
 880             if (projs.catchall_memproj == NULL) {


 897         }
 898       } else {
 899         for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
 900           Node* u = c->fast_out(i);
 901           if (u->is_Proj() &&
 902               u->bottom_type() == Type::MEMORY &&
 903               u->adr_type() == TypePtr::BOTTOM) {
 904               assert(c->is_SafePoint() || c->is_MemBar() || c->is_Start(), "");
 905               assert(mem == NULL, "only one proj");
 906               mem = u;
 907           }
 908         }
 909         assert(!c->is_Call() || c->as_Call()->adr_type() != NULL || mem == NULL, "no mem projection expected");
 910       }
 911     }
 912     c = phase->idom(c);
 913   } while (mem == NULL);
 914   return mem;
 915 }
 916 
 917 void ShenandoahBarrierC2Support::follow_barrier_uses(Node* n, Node* ctrl, Unique_Node_List& uses, PhaseIdealLoop* phase) {
 918   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
 919     Node* u = n->fast_out(i);
 920     if (!u->is_CFG() && phase->get_ctrl(u) == ctrl && (!u->is_Phi() || !u->in(0)->is_Loop() || u->in(LoopNode::LoopBackControl) != n)) {
 921       uses.push(u);
 922     }
 923   }
 924 }
 925 
 926 static void hide_strip_mined_loop(OuterStripMinedLoopNode* outer, CountedLoopNode* inner, PhaseIdealLoop* phase) {
 927   OuterStripMinedLoopEndNode* le = inner->outer_loop_end();
 928   Node* new_outer = new LoopNode(outer->in(LoopNode::EntryControl), outer->in(LoopNode::LoopBackControl));
 929   phase->register_control(new_outer, phase->get_loop(outer), outer->in(LoopNode::EntryControl));
 930   Node* new_le = new IfNode(le->in(0), le->in(1), le->_prob, le->_fcnt);
 931   phase->register_control(new_le, phase->get_loop(le), le->in(0));
 932   phase->lazy_replace(outer, new_outer);
 933   phase->lazy_replace(le, new_le);
 934   inner->clear_strip_mined();
 935 }
 936 
 937 void ShenandoahBarrierC2Support::test_heap_stable(Node*& ctrl, Node* raw_mem, Node*& heap_stable_ctrl,
 938                                                   PhaseIdealLoop* phase) {
 939   IdealLoopTree* loop = phase->get_loop(ctrl);
 940   Node* thread = new ThreadLocalNode();
 941   phase->register_new_node(thread, ctrl);
 942   Node* offset = phase->igvn().MakeConX(in_bytes(ShenandoahThreadLocalData::gc_state_offset()));
 943   phase->set_ctrl(offset, phase->C->root());
 944   Node* gc_state_addr = new AddPNode(phase->C->top(), thread, offset);
 945   phase->register_new_node(gc_state_addr, ctrl);
 946   uint gc_state_idx = Compile::AliasIdxRaw;
 947   const TypePtr* gc_state_adr_type = NULL; // debug-mode-only argument
 948   debug_only(gc_state_adr_type = phase->C->get_adr_type(gc_state_idx));
 949 
 950   Node* gc_state = new LoadBNode(ctrl, raw_mem, gc_state_addr, gc_state_adr_type, TypeInt::BYTE, MemNode::unordered);
 951   phase->register_new_node(gc_state, ctrl);
 952   Node* heap_stable_and = new AndINode(gc_state, phase->igvn().intcon(ShenandoahHeap::HAS_FORWARDED));
 953   phase->register_new_node(heap_stable_and, ctrl);
 954   Node* heap_stable_cmp = new CmpINode(heap_stable_and, phase->igvn().zerocon(T_INT));
 955   phase->register_new_node(heap_stable_cmp, ctrl);
 956   Node* heap_stable_test = new BoolNode(heap_stable_cmp, BoolTest::ne);
 957   phase->register_new_node(heap_stable_test, ctrl);
 958   IfNode* heap_stable_iff = new IfNode(ctrl, heap_stable_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
 959   phase->register_control(heap_stable_iff, loop, ctrl);
 960 
 961   heap_stable_ctrl = new IfFalseNode(heap_stable_iff);
 962   phase->register_control(heap_stable_ctrl, loop, heap_stable_iff);
 963   ctrl = new IfTrueNode(heap_stable_iff);
 964   phase->register_control(ctrl, loop, heap_stable_iff);
 965 
 966   assert(is_heap_stable_test(heap_stable_iff), "Should match the shape");
 967 }
 968 
 969 void ShenandoahBarrierC2Support::test_null(Node*& ctrl, Node* val, Node*& null_ctrl, PhaseIdealLoop* phase) {
 970   const Type* val_t = phase->igvn().type(val);
 971   if (val_t->meet(TypePtr::NULL_PTR) == val_t) {
 972     IdealLoopTree* loop = phase->get_loop(ctrl);
 973     Node* null_cmp = new CmpPNode(val, phase->igvn().zerocon(T_OBJECT));
 974     phase->register_new_node(null_cmp, ctrl);
 975     Node* null_test = new BoolNode(null_cmp, BoolTest::ne);
 976     phase->register_new_node(null_test, ctrl);
 977     IfNode* null_iff = new IfNode(ctrl, null_test, PROB_LIKELY(0.999), COUNT_UNKNOWN);
 978     phase->register_control(null_iff, loop, ctrl);
 979     ctrl = new IfTrueNode(null_iff);
 980     phase->register_control(ctrl, loop, null_iff);
 981     null_ctrl = new IfFalseNode(null_iff);
 982     phase->register_control(null_ctrl, loop, null_iff);
 983   }
 984 }
 985 
 986 Node* ShenandoahBarrierC2Support::clone_null_check(Node*& c, Node* val, Node* unc_ctrl, PhaseIdealLoop* phase) {
 987   IdealLoopTree *loop = phase->get_loop(c);
 988   Node* iff = unc_ctrl->in(0);
 989   assert(iff->is_If(), "broken");
 990   Node* new_iff = iff->clone();
 991   new_iff->set_req(0, c);
 992   phase->register_control(new_iff, loop, c);
 993   Node* iffalse = new IfFalseNode(new_iff->as_If());
 994   phase->register_control(iffalse, loop, new_iff);
 995   Node* iftrue = new IfTrueNode(new_iff->as_If());
 996   phase->register_control(iftrue, loop, new_iff);
 997   c = iftrue;
 998   const Type *t = phase->igvn().type(val);
 999   assert(val->Opcode() == Op_CastPP, "expect cast to non null here");
1000   Node* uncasted_val = val->in(1);
1001   val = new CastPPNode(uncasted_val, t);
1002   val->init_req(0, c);
1003   phase->register_new_node(val, c);
1004   return val;
1005 }
1006 
1007 void ShenandoahBarrierC2Support::fix_null_check(Node* unc, Node* unc_ctrl, Node* new_unc_ctrl,
1008                                                 Unique_Node_List& uses, PhaseIdealLoop* phase) {
1009   IfNode* iff = unc_ctrl->in(0)->as_If();
1010   Node* proj = iff->proj_out(0);
1011   assert(proj != unc_ctrl, "bad projection");
1012   Node* use = proj->unique_ctrl_out();
1013 
1014   assert(use == unc || use->is_Region(), "what else?");
1015 
1016   uses.clear();
1017   if (use == unc) {
1018     phase->set_idom(use, new_unc_ctrl, phase->dom_depth(use));
1019     for (uint i = 1; i < unc->req(); i++) {
1020       Node* n = unc->in(i);
1021       if (phase->has_ctrl(n) && phase->get_ctrl(n) == proj) {
1022         uses.push(n);
1023       }
1024     }
1025   } else {
1026     assert(use->is_Region(), "what else?");
1027     uint idx = 1;


1036   for(uint next = 0; next < uses.size(); next++ ) {
1037     Node *n = uses.at(next);
1038     assert(phase->get_ctrl(n) == proj, "bad control");
1039     phase->set_ctrl_and_loop(n, new_unc_ctrl);
1040     if (n->in(0) == proj) {
1041       phase->igvn().replace_input_of(n, 0, new_unc_ctrl);
1042     }
1043     for (uint i = 0; i < n->req(); i++) {
1044       Node* m = n->in(i);
1045       if (m != NULL && phase->has_ctrl(m) && phase->get_ctrl(m) == proj) {
1046         uses.push(m);
1047       }
1048     }
1049   }
1050 
1051   phase->igvn().rehash_node_delayed(use);
1052   int nb = use->replace_edge(proj, new_unc_ctrl);
1053   assert(nb == 1, "only use expected");
1054 }
1055 
1056 void ShenandoahBarrierC2Support::in_cset_fast_test(Node*& ctrl, Node*& not_cset_ctrl, Node* val, Node* raw_mem, PhaseIdealLoop* phase) {
1057   IdealLoopTree *loop = phase->get_loop(ctrl);
1058   Node* raw_rbtrue = new CastP2XNode(ctrl, val);
1059   phase->register_new_node(raw_rbtrue, ctrl);
1060   Node* cset_offset = new URShiftXNode(raw_rbtrue, phase->igvn().intcon(ShenandoahHeapRegion::region_size_bytes_shift_jint()));
1061   phase->register_new_node(cset_offset, ctrl);
1062   Node* in_cset_fast_test_base_addr = phase->igvn().makecon(TypeRawPtr::make(ShenandoahHeap::in_cset_fast_test_addr()));
1063   phase->set_ctrl(in_cset_fast_test_base_addr, phase->C->root());
1064   Node* in_cset_fast_test_adr = new AddPNode(phase->C->top(), in_cset_fast_test_base_addr, cset_offset);
1065   phase->register_new_node(in_cset_fast_test_adr, ctrl);
1066   uint in_cset_fast_test_idx = Compile::AliasIdxRaw;
1067   const TypePtr* in_cset_fast_test_adr_type = NULL; // debug-mode-only argument
1068   debug_only(in_cset_fast_test_adr_type = phase->C->get_adr_type(in_cset_fast_test_idx));
1069   Node* in_cset_fast_test_load = new LoadBNode(ctrl, raw_mem, in_cset_fast_test_adr, in_cset_fast_test_adr_type, TypeInt::BYTE, MemNode::unordered);
1070   phase->register_new_node(in_cset_fast_test_load, ctrl);
1071   Node* in_cset_fast_test_cmp = new CmpINode(in_cset_fast_test_load, phase->igvn().zerocon(T_INT));
1072   phase->register_new_node(in_cset_fast_test_cmp, ctrl);
1073   Node* in_cset_fast_test_test = new BoolNode(in_cset_fast_test_cmp, BoolTest::eq);
1074   phase->register_new_node(in_cset_fast_test_test, ctrl);
1075   IfNode* in_cset_fast_test_iff = new IfNode(ctrl, in_cset_fast_test_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
1076   phase->register_control(in_cset_fast_test_iff, loop, ctrl);
1077 
1078   not_cset_ctrl = new IfTrueNode(in_cset_fast_test_iff);
1079   phase->register_control(not_cset_ctrl, loop, in_cset_fast_test_iff);
1080 
1081   ctrl = new IfFalseNode(in_cset_fast_test_iff);
1082   phase->register_control(ctrl, loop, in_cset_fast_test_iff);
1083 }
1084 
1085 void ShenandoahBarrierC2Support::call_lrb_stub(Node*& ctrl, Node*& val, Node*& result_mem, Node* raw_mem, PhaseIdealLoop* phase) {



1086   IdealLoopTree*loop = phase->get_loop(ctrl);
1087   const TypePtr* obj_type = phase->igvn().type(val)->is_oopptr()->cast_to_nonconst();
1088 
1089   // The slow path stub consumes and produces raw memory in addition
1090   // to the existing memory edges
1091   Node* base = find_bottom_mem(ctrl, phase);

1092   MergeMemNode* mm = MergeMemNode::make(base);

1093   mm->set_memory_at(Compile::AliasIdxRaw, raw_mem);
1094   phase->register_new_node(mm, ctrl);
1095 
1096   Node* call = new CallLeafNode(ShenandoahBarrierSetC2::shenandoah_write_barrier_Type(), CAST_FROM_FN_PTR(address, ShenandoahRuntime::load_reference_barrier_JRT), "shenandoah_write_barrier", TypeRawPtr::BOTTOM);
1097   call->init_req(TypeFunc::Control, ctrl);
1098   call->init_req(TypeFunc::I_O, phase->C->top());
1099   call->init_req(TypeFunc::Memory, mm);
1100   call->init_req(TypeFunc::FramePtr, phase->C->top());
1101   call->init_req(TypeFunc::ReturnAdr, phase->C->top());
1102   call->init_req(TypeFunc::Parms, val);
1103   phase->register_control(call, loop, ctrl);
1104   ctrl = new ProjNode(call, TypeFunc::Control);
1105   phase->register_control(ctrl, loop, call);
1106   result_mem = new ProjNode(call, TypeFunc::Memory);
1107   phase->register_new_node(result_mem, call);
1108   val = new ProjNode(call, TypeFunc::Parms);
1109   phase->register_new_node(val, call);
1110   val = new CheckCastPPNode(ctrl, val, obj_type);
1111   phase->register_new_node(val, ctrl);
1112 }
1113 
1114 void ShenandoahBarrierC2Support::fix_ctrl(Node* barrier, Node* region, const MemoryGraphFixer& fixer, Unique_Node_List& uses, Unique_Node_List& uses_to_ignore, uint last, PhaseIdealLoop* phase) {
1115   Node* ctrl = phase->get_ctrl(barrier);
1116   Node* init_raw_mem = fixer.find_mem(ctrl, barrier);
1117 
1118   // Update the control of all nodes that should be after the
1119   // barrier control flow
1120   uses.clear();
1121   // Every node that is control dependent on the barrier's input
1122   // control will be after the expanded barrier. The raw memory (if
1123   // its memory is control dependent on the barrier's input control)
1124   // must stay above the barrier.
1125   uses_to_ignore.clear();
1126   if (phase->has_ctrl(init_raw_mem) && phase->get_ctrl(init_raw_mem) == ctrl && !init_raw_mem->is_Phi()) {
1127     uses_to_ignore.push(init_raw_mem);
1128   }
1129   for (uint next = 0; next < uses_to_ignore.size(); next++) {
1130     Node *n = uses_to_ignore.at(next);
1131     for (uint i = 0; i < n->req(); i++) {
1132       Node* in = n->in(i);
1133       if (in != NULL && phase->has_ctrl(in) && phase->get_ctrl(in) == ctrl) {
1134         uses_to_ignore.push(in);


1147       if (c != ctrl ||
1148           is_dominator_same_ctrl(old_c, barrier, u, phase) ||
1149           ShenandoahBarrierSetC2::is_shenandoah_state_load(u)) {
1150         phase->igvn().rehash_node_delayed(u);
1151         int nb = u->replace_edge(ctrl, region);
1152         if (u->is_CFG()) {
1153           if (phase->idom(u) == ctrl) {
1154             phase->set_idom(u, region, phase->dom_depth(region));
1155           }
1156         } else if (phase->get_ctrl(u) == ctrl) {
1157           assert(u != init_raw_mem, "should leave input raw mem above the barrier");
1158           uses.push(u);
1159         }
1160         assert(nb == 1, "more than 1 ctrl input?");
1161         --i, imax -= nb;
1162       }
1163     }
1164   }
1165 }
1166 
1167 static Node* create_phis_on_call_return(Node* ctrl, Node* c, Node* n, Node* n_clone, const CallProjections& projs, PhaseIdealLoop* phase) {
1168   Node* region = NULL;
1169   while (c != ctrl) {
1170     if (c->is_Region()) {
1171       region = c;
1172     }
1173     c = phase->idom(c);
1174   }
1175   assert(region != NULL, "");
1176   Node* phi = new PhiNode(region, n->bottom_type());
1177   for (uint j = 1; j < region->req(); j++) {
1178     Node* in = region->in(j);
1179     if (phase->is_dominator(projs.fallthrough_catchproj, in)) {
1180       phi->init_req(j, n);
1181     } else if (phase->is_dominator(projs.catchall_catchproj, in)) {
1182       phi->init_req(j, n_clone);
1183     } else {
1184       phi->init_req(j, create_phis_on_call_return(ctrl, in, n, n_clone, projs, phase));
1185     }
1186   }
1187   phase->register_new_node(phi, region);
1188   return phi;
1189 }
1190 
1191 void ShenandoahBarrierC2Support::pin_and_expand(PhaseIdealLoop* phase) {
1192   ShenandoahBarrierSetC2State* state = ShenandoahBarrierSetC2::bsc2()->state();
1193 
1194   // Collect raw memory state at CFG points in the entire graph and
1195   // record it in memory_nodes. Optimize the raw memory graph in the
1196   // process. Optimizing the memory graph also makes the memory graph
1197   // simpler.
1198   GrowableArray<MemoryGraphFixer*> memory_graph_fixers;
1199 



1200   Unique_Node_List uses;
1201   for (int i = 0; i < state->enqueue_barriers_count(); i++) {
1202     Node* barrier = state->enqueue_barrier(i);






















1203     Node* ctrl = phase->get_ctrl(barrier);
1204     IdealLoopTree* loop = phase->get_loop(ctrl);
1205     if (loop->_head->is_OuterStripMinedLoop()) {
1206       // Expanding a barrier here will break loop strip mining
1207       // verification. Transform the loop so the loop nest doesn't
1208       // appear as strip mined.
1209       OuterStripMinedLoopNode* outer = loop->_head->as_OuterStripMinedLoop();
1210       hide_strip_mined_loop(outer, outer->unique_ctrl_out()->as_CountedLoop(), phase);
1211     }
1212   }
1213 
1214   Node_Stack stack(0);
1215   Node_List clones;
1216   for (int i = state->load_reference_barriers_count() - 1; i >= 0; i--) {
1217     ShenandoahLoadReferenceBarrierNode* lrb = state->load_reference_barrier(i);
1218     if (lrb->get_barrier_strength() == ShenandoahLoadReferenceBarrierNode::NONE) {
1219       continue;
1220     }
1221 
1222     Node* ctrl = phase->get_ctrl(lrb);
1223     Node* val = lrb->in(ShenandoahLoadReferenceBarrierNode::ValueIn);
1224 
1225     CallStaticJavaNode* unc = NULL;
1226     Node* unc_ctrl = NULL;
1227     Node* uncasted_val = val;
1228 
1229     for (DUIterator_Fast imax, i = lrb->fast_outs(imax); i < imax; i++) {
1230       Node* u = lrb->fast_out(i);
1231       if (u->Opcode() == Op_CastPP &&
1232           u->in(0) != NULL &&
1233           phase->is_dominator(u->in(0), ctrl)) {
1234         const Type* u_t = phase->igvn().type(u);
1235 
1236         if (u_t->meet(TypePtr::NULL_PTR) != u_t &&
1237             u->in(0)->Opcode() == Op_IfTrue &&
1238             u->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
1239             u->in(0)->in(0)->is_If() &&
1240             u->in(0)->in(0)->in(1)->Opcode() == Op_Bool &&
1241             u->in(0)->in(0)->in(1)->as_Bool()->_test._test == BoolTest::ne &&
1242             u->in(0)->in(0)->in(1)->in(1)->Opcode() == Op_CmpP &&
1243             u->in(0)->in(0)->in(1)->in(1)->in(1) == val &&
1244             u->in(0)->in(0)->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
1245           IdealLoopTree* loop = phase->get_loop(ctrl);
1246           IdealLoopTree* unc_loop = phase->get_loop(u->in(0));
1247 
1248           if (!unc_loop->is_member(loop)) {
1249             continue;
1250           }
1251 
1252           Node* branch = no_branches(ctrl, u->in(0), false, phase);
1253           assert(branch == NULL || branch == NodeSentinel, "was not looking for a branch");
1254           if (branch == NodeSentinel) {
1255             continue;
1256           }
1257 
1258           phase->igvn().replace_input_of(u, 1, val);
1259           phase->igvn().replace_input_of(lrb, ShenandoahLoadReferenceBarrierNode::ValueIn, u);
1260           phase->set_ctrl(u, u->in(0));
1261           phase->set_ctrl(lrb, u->in(0));
1262           unc = u->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
1263           unc_ctrl = u->in(0);
1264           val = u;
1265 
1266           for (DUIterator_Fast jmax, j = val->fast_outs(jmax); j < jmax; j++) {
1267             Node* u = val->fast_out(j);
1268             if (u == lrb) continue;
1269             phase->igvn().rehash_node_delayed(u);
1270             int nb = u->replace_edge(val, lrb);
1271             --j; jmax -= nb;
1272           }
1273 
1274           RegionNode* r = new RegionNode(3);
1275           IfNode* iff = unc_ctrl->in(0)->as_If();
1276 
1277           Node* ctrl_use = unc_ctrl->unique_ctrl_out();
1278           Node* unc_ctrl_clone = unc_ctrl->clone();
1279           phase->register_control(unc_ctrl_clone, loop, iff);
1280           Node* c = unc_ctrl_clone;
1281           Node* new_cast = clone_null_check(c, val, unc_ctrl_clone, phase);
1282           r->init_req(1, new_cast->in(0)->in(0)->as_If()->proj_out(0));
1283 
1284           phase->igvn().replace_input_of(unc_ctrl, 0, c->in(0));
1285           phase->set_idom(unc_ctrl, c->in(0), phase->dom_depth(unc_ctrl));
1286           phase->lazy_replace(c, unc_ctrl);
1287           c = NULL;;
1288           phase->igvn().replace_input_of(val, 0, unc_ctrl_clone);
1289           phase->set_ctrl(val, unc_ctrl_clone);
1290 
1291           IfNode* new_iff = new_cast->in(0)->in(0)->as_If();
1292           fix_null_check(unc, unc_ctrl_clone, r, uses, phase);
1293           Node* iff_proj = iff->proj_out(0);
1294           r->init_req(2, iff_proj);
1295           phase->register_control(r, phase->ltree_root(), iff);
1296 
1297           Node* new_bol = new_iff->in(1)->clone();
1298           Node* new_cmp = new_bol->in(1)->clone();
1299           assert(new_cmp->Opcode() == Op_CmpP, "broken");
1300           assert(new_cmp->in(1) == val->in(1), "broken");
1301           new_bol->set_req(1, new_cmp);
1302           new_cmp->set_req(1, lrb);
1303           phase->register_new_node(new_bol, new_iff->in(0));
1304           phase->register_new_node(new_cmp, new_iff->in(0));
1305           phase->igvn().replace_input_of(new_iff, 1, new_bol);
1306           phase->igvn().replace_input_of(new_cast, 1, lrb);
1307 
1308           for (DUIterator_Fast imax, i = lrb->fast_outs(imax); i < imax; i++) {
1309             Node* u = lrb->fast_out(i);
1310             if (u == new_cast || u == new_cmp) {
1311               continue;
1312             }
1313             phase->igvn().rehash_node_delayed(u);
1314             int nb = u->replace_edge(lrb, new_cast);
1315             assert(nb > 0, "no update?");
1316             --i; imax -= nb;
1317           }
1318 
1319           for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
1320             Node* u = val->fast_out(i);
1321             if (u == lrb) {
1322               continue;
1323             }
1324             phase->igvn().rehash_node_delayed(u);
1325             int nb = u->replace_edge(val, new_cast);
1326             assert(nb > 0, "no update?");
1327             --i; imax -= nb;
1328           }
1329 
1330           ctrl = unc_ctrl_clone;
1331           phase->set_ctrl_and_loop(lrb, ctrl);
1332           break;
1333         }
1334       }
1335     }
1336     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
1337       CallNode* call = ctrl->in(0)->as_CallJava();
1338       CallProjections projs;
1339       call->extract_projections(&projs, false, false);
1340 
1341       Node* lrb_clone = lrb->clone();
1342       phase->register_new_node(lrb_clone, projs.catchall_catchproj);
1343       phase->set_ctrl(lrb, projs.fallthrough_catchproj);
1344 
1345       stack.push(lrb, 0);
1346       clones.push(lrb_clone);
1347 
1348       do {
1349         assert(stack.size() == clones.size(), "");
1350         Node* n = stack.node();
1351 #ifdef ASSERT
1352         if (n->is_Load()) {
1353           Node* mem = n->in(MemNode::Memory);
1354           for (DUIterator_Fast jmax, j = mem->fast_outs(jmax); j < jmax; j++) {
1355             Node* u = mem->fast_out(j);
1356             assert(!u->is_Store() || !u->is_LoadStore() || phase->get_ctrl(u) != ctrl, "anti dependent store?");
1357           }
1358         }
1359 #endif
1360         uint idx = stack.index();
1361         Node* n_clone = clones.at(clones.size()-1);
1362         if (idx < n->outcnt()) {
1363           Node* u = n->raw_out(idx);
1364           Node* c = phase->ctrl_or_self(u);
1365           if (c == ctrl) {
1366             stack.set_index(idx+1);
1367             assert(!u->is_CFG(), "");
1368             stack.push(u, 0);
1369             Node* u_clone = u->clone();
1370             int nb = u_clone->replace_edge(n, n_clone);
1371             assert(nb > 0, "should have replaced some uses");
1372             phase->register_new_node(u_clone, projs.catchall_catchproj);
1373             clones.push(u_clone);
1374             phase->set_ctrl(u, projs.fallthrough_catchproj);
1375           } else {
1376             bool replaced = false;
1377             if (u->is_Phi()) {
1378               for (uint k = 1; k < u->req(); k++) {
1379                 if (u->in(k) == n) {
1380                   if (phase->is_dominator(projs.catchall_catchproj, u->in(0)->in(k))) {
1381                     phase->igvn().replace_input_of(u, k, n_clone);
1382                     replaced = true;
1383                   } else if (!phase->is_dominator(projs.fallthrough_catchproj, u->in(0)->in(k))) {
1384                     phase->igvn().replace_input_of(u, k, create_phis_on_call_return(ctrl, u->in(0)->in(k), n, n_clone, projs, phase));
1385                     replaced = true;
1386                   }
1387                 }
1388               }
1389             } else {
1390               if (phase->is_dominator(projs.catchall_catchproj, c)) {
1391                 phase->igvn().rehash_node_delayed(u);
1392                 int nb = u->replace_edge(n, n_clone);
1393                 assert(nb > 0, "should have replaced some uses");
1394                 replaced = true;
1395               } else if (!phase->is_dominator(projs.fallthrough_catchproj, c)) {
1396                 phase->igvn().rehash_node_delayed(u);
1397                 int nb = u->replace_edge(n, create_phis_on_call_return(ctrl, c, n, n_clone, projs, phase));
1398                 assert(nb > 0, "should have replaced some uses");
1399                 replaced = true;
1400               }
1401             }
1402             if (!replaced) {
1403               stack.set_index(idx+1);
1404             }
1405           }
1406         } else {
1407           // assert(n_clone->outcnt() > 0, "");
1408           // assert(n->outcnt() > 0, "");
1409           stack.pop();
1410           clones.pop();
1411         }
1412       } while (stack.size() > 0);
1413       assert(stack.size() == 0 && clones.size() == 0, "");
1414       ctrl = projs.fallthrough_catchproj;
1415     }
1416   }
1417 
1418   // Expand loadref-barriers
1419   MemoryGraphFixer fixer(Compile::AliasIdxRaw, true, phase);
1420   Unique_Node_List uses_to_ignore;
1421   for (int i = state->load_reference_barriers_count() - 1; i >= 0; i--) {
1422     ShenandoahLoadReferenceBarrierNode* lrb = state->load_reference_barrier(i);
1423     if (lrb->get_barrier_strength() == ShenandoahLoadReferenceBarrierNode::NONE) {
1424       phase->igvn().replace_node(lrb, lrb->in(ShenandoahLoadReferenceBarrierNode::ValueIn));
1425       continue;
1426     }
1427     uint last = phase->C->unique();
1428     Node* ctrl = phase->get_ctrl(lrb);
1429     Node* val = lrb->in(ShenandoahLoadReferenceBarrierNode::ValueIn);
1430 
1431 
1432     Node* orig_ctrl = ctrl;
1433 
1434     Node* raw_mem = fixer.find_mem(ctrl, lrb);
1435     Node* init_raw_mem = raw_mem;
1436     Node* raw_mem_for_ctrl = fixer.find_mem(ctrl, NULL);
1437     // int alias = phase->C->get_alias_index(lrb->adr_type());
1438 
1439     IdealLoopTree *loop = phase->get_loop(ctrl);
1440     CallStaticJavaNode* unc = lrb->pin_and_expand_null_check(phase->igvn());
1441     Node* unc_ctrl = NULL;
1442     if (unc != NULL) {
1443       if (val->in(ShenandoahLoadReferenceBarrierNode::Control) != ctrl) {
1444         unc = NULL;
1445       } else {
1446         unc_ctrl = val->in(ShenandoahLoadReferenceBarrierNode::Control);
1447       }
1448     }
1449 
1450     Node* uncasted_val = val;
1451     if (unc != NULL) {
1452       uncasted_val = val->in(1);
1453     }
1454 
1455     Node* heap_stable_ctrl = NULL;
1456     Node* null_ctrl = NULL;
1457 
1458     assert(val->bottom_type()->make_oopptr(), "need oop");
1459     assert(val->bottom_type()->make_oopptr()->const_oop() == NULL, "expect non-constant");
1460 
1461     enum { _heap_stable = 1, _not_cset, _not_equal, _evac_path, _null_path, PATH_LIMIT };
1462     Node* region = new RegionNode(PATH_LIMIT);
1463     Node* val_phi = new PhiNode(region, uncasted_val->bottom_type()->is_oopptr());
1464     Node* raw_mem_phi = PhiNode::make(region, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
1465 
1466     // Stable path.
1467     test_heap_stable(ctrl, raw_mem, heap_stable_ctrl, phase);
1468     IfNode* heap_stable_iff = heap_stable_ctrl->in(0)->as_If();
1469 
1470     // Heap stable case
1471     region->init_req(_heap_stable, heap_stable_ctrl);
1472     val_phi->init_req(_heap_stable, uncasted_val);
1473     raw_mem_phi->init_req(_heap_stable, raw_mem);
1474 
1475     Node* reg2_ctrl = NULL;
1476     // Null case
1477     test_null(ctrl, val, null_ctrl, phase);
1478     if (null_ctrl != NULL) {
1479       reg2_ctrl = null_ctrl->in(0);
1480       region->init_req(_null_path, null_ctrl);
1481       val_phi->init_req(_null_path, uncasted_val);
1482       raw_mem_phi->init_req(_null_path, raw_mem);
1483     } else {
1484       region->del_req(_null_path);
1485       val_phi->del_req(_null_path);
1486       raw_mem_phi->del_req(_null_path);
1487     }
1488 
1489     // Test for in-cset.
1490     // Wires !in_cset(obj) to slot 2 of region and phis
1491     Node* not_cset_ctrl = NULL;
1492     in_cset_fast_test(ctrl, not_cset_ctrl, uncasted_val, raw_mem, phase);
1493     if (not_cset_ctrl != NULL) {
1494       if (reg2_ctrl == NULL) reg2_ctrl = not_cset_ctrl->in(0);
1495       region->init_req(_not_cset, not_cset_ctrl);
1496       val_phi->init_req(_not_cset, uncasted_val);
1497       raw_mem_phi->init_req(_not_cset, raw_mem);
1498     }
1499 
1500     // Resolve object when orig-value is in cset.
1501     // Make the unconditional resolve for fwdptr, not the read barrier.
1502     Node* new_val = uncasted_val;
1503     if (unc_ctrl != NULL) {
1504       // Clone the null check in this branch to allow implicit null check
1505       new_val = clone_null_check(ctrl, val, unc_ctrl, phase);
1506       fix_null_check(unc, unc_ctrl, ctrl->in(0)->as_If()->proj_out(0), uses, phase);
1507 
1508       IfNode* iff = unc_ctrl->in(0)->as_If();
1509       phase->igvn().replace_input_of(iff, 1, phase->igvn().intcon(1));
1510     }
1511     Node* addr = new AddPNode(new_val, uncasted_val, phase->igvn().MakeConX(ShenandoahBrooksPointer::byte_offset()));
1512     phase->register_new_node(addr, ctrl);
1513     assert(val->bottom_type()->isa_oopptr(), "what else?");
1514     const TypePtr* obj_type =  val->bottom_type()->is_oopptr();
1515     const TypePtr* adr_type = TypeRawPtr::BOTTOM;
1516     Node* fwd = new LoadPNode(ctrl, raw_mem, addr, adr_type, obj_type, MemNode::unordered);
1517     phase->register_new_node(fwd, ctrl);
1518 
1519     // Only branch to WB stub if object is not forwarded; otherwise reply with fwd ptr
1520     Node* cmp = new CmpPNode(fwd, new_val);
1521     phase->register_new_node(cmp, ctrl);
1522     Node* bol = new BoolNode(cmp, BoolTest::eq);
1523     phase->register_new_node(bol, ctrl);
1524 
1525     IfNode* iff = new IfNode(ctrl, bol, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
1526     if (reg2_ctrl == NULL) reg2_ctrl = iff;
1527     phase->register_control(iff, loop, ctrl);
1528     Node* if_not_eq = new IfFalseNode(iff);
1529     phase->register_control(if_not_eq, loop, iff);
1530     Node* if_eq = new IfTrueNode(iff);
1531     phase->register_control(if_eq, loop, iff);
1532 
1533     // Wire up not-equal-path in slots 3.
1534     region->init_req(_not_equal, if_not_eq);
1535     val_phi->init_req(_not_equal, fwd);
1536     raw_mem_phi->init_req(_not_equal, raw_mem);
1537 
1538     // Call wb-stub and wire up that path in slots 4
1539     Node* result_mem = NULL;
1540     ctrl = if_eq;
1541     call_lrb_stub(ctrl, fwd, result_mem, raw_mem, phase);
1542     region->init_req(_evac_path, ctrl);
1543     val_phi->init_req(_evac_path, fwd);
1544     raw_mem_phi->init_req(_evac_path, result_mem);
1545 
1546     phase->register_control(region, loop, heap_stable_iff);
1547     Node* out_val = val_phi;
1548     phase->register_new_node(val_phi, region);
1549     phase->register_new_node(raw_mem_phi, region);
1550 
1551     fix_ctrl(lrb, region, fixer, uses, uses_to_ignore, last, phase);
1552 
1553     ctrl = orig_ctrl;
1554 
1555     if (unc != NULL) {
1556       for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
1557         Node* u = val->fast_out(i);
1558         Node* c = phase->ctrl_or_self(u);
1559         if (u != lrb && (c != ctrl || is_dominator_same_ctrl(c, lrb, u, phase))) {
1560           phase->igvn().rehash_node_delayed(u);
1561           int nb = u->replace_edge(val, out_val);
1562           --i, imax -= nb;
1563         }
1564       }
1565       if (val->outcnt() == 0) {
1566         phase->igvn()._worklist.push(val);
1567       }
1568     }
1569     phase->igvn().replace_node(lrb, out_val);
1570 
1571     follow_barrier_uses(out_val, ctrl, uses, phase);
1572 
1573     for(uint next = 0; next < uses.size(); next++ ) {
1574       Node *n = uses.at(next);
1575       assert(phase->get_ctrl(n) == ctrl, "bad control");
1576       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
1577       phase->set_ctrl(n, region);
1578       follow_barrier_uses(n, ctrl, uses, phase);
1579     }
1580 
1581     // The slow path call produces memory: hook the raw memory phi
1582     // from the expanded write barrier with the rest of the graph
1583     // which may require adding memory phis at every post dominated
1584     // region and at enclosing loop heads. Use the memory state
1585     // collected in memory_nodes to fix the memory graph. Update that
1586     // memory state as we go.
1587     fixer.fix_mem(ctrl, region, init_raw_mem, raw_mem_for_ctrl, raw_mem_phi, uses);
1588   }
1589   // Done expanding loadref-barriers.
1590 
1591   assert(ShenandoahBarrierSetC2::bsc2()->state()->load_reference_barriers_count() == 0, "all load reference barrier nodes should have been replaced");
1592 
1593 
1594   for (int i = state->enqueue_barriers_count() - 1; i >= 0; i--) {
1595     Node* barrier = state->enqueue_barrier(i);
1596     Node* pre_val = barrier->in(1);
1597 
1598     if (phase->igvn().type(pre_val)->higher_equal(TypePtr::NULL_PTR)) {
1599       ShouldNotReachHere();
1600       continue;
1601     }
1602 
1603     Node* ctrl = phase->get_ctrl(barrier);
1604 
1605     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
1606       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0)->in(0), pre_val, ctrl->in(0), phase), "can't move");
1607       ctrl = ctrl->in(0)->in(0);
1608       phase->set_ctrl(barrier, ctrl);
1609     } else if (ctrl->is_CallRuntime()) {
1610       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0), pre_val, ctrl, phase), "can't move");
1611       ctrl = ctrl->in(0);
1612       phase->set_ctrl(barrier, ctrl);
1613     }
1614 
1615     Node* init_ctrl = ctrl;


1722     phase->register_new_node(phi2, region2);
1723 
1724     region->init_req(_heap_unstable, region2);
1725     phi->init_req(_heap_unstable, phi2);
1726 
1727     phase->register_control(region, loop, heap_stable_ctrl->in(0));
1728     phase->register_new_node(phi, region);
1729 
1730     fix_ctrl(barrier, region, fixer, uses, uses_to_ignore, last, phase);
1731     for(uint next = 0; next < uses.size(); next++ ) {
1732       Node *n = uses.at(next);
1733       assert(phase->get_ctrl(n) == init_ctrl, "bad control");
1734       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
1735       phase->set_ctrl(n, region);
1736       follow_barrier_uses(n, init_ctrl, uses, phase);
1737     }
1738     fixer.fix_mem(init_ctrl, region, init_raw_mem, raw_mem_for_ctrl, phi, uses);
1739 
1740     phase->igvn().replace_node(barrier, pre_val);
1741   }
1742   assert(state->enqueue_barriers_count() == 0, "all enqueue barrier nodes should have been replaced");
1743 










































































































































































































1744 }
1745 
1746 void ShenandoahBarrierC2Support::move_heap_stable_test_out_of_loop(IfNode* iff, PhaseIdealLoop* phase) {
1747   IdealLoopTree *loop = phase->get_loop(iff);
1748   Node* loop_head = loop->_head;
1749   Node* entry_c = loop_head->in(LoopNode::EntryControl);
1750 
1751   Node* bol = iff->in(1);
1752   Node* cmp = bol->in(1);
1753   Node* andi = cmp->in(1);
1754   Node* load = andi->in(1);
1755 
1756   assert(is_gc_state_load(load), "broken");
1757   if (!phase->is_dominator(load->in(0), entry_c)) {
1758     Node* mem_ctrl = NULL;
1759     Node* mem = dom_mem(load->in(MemNode::Memory), loop_head, Compile::AliasIdxRaw, mem_ctrl, phase);
1760     load = load->clone();
1761     load->set_req(MemNode::Memory, mem);
1762     load->set_req(0, entry_c);
1763     phase->register_new_node(load, entry_c);
1764     andi = andi->clone();
1765     andi->set_req(1, load);
1766     phase->register_new_node(andi, entry_c);
1767     cmp = cmp->clone();
1768     cmp->set_req(1, andi);
1769     phase->register_new_node(cmp, entry_c);
1770     bol = bol->clone();
1771     bol->set_req(1, cmp);
1772     phase->register_new_node(bol, entry_c);
1773 
1774     Node* old_bol =iff->in(1);
1775     phase->igvn().replace_input_of(iff, 1, bol);
1776   }
1777 }
1778 
1779 bool ShenandoahBarrierC2Support::identical_backtoback_ifs(Node* n, PhaseIdealLoop* phase) {
1780   if (!n->is_If() || n->is_CountedLoopEnd()) {
1781     return false;
1782   }
1783   Node* region = n->in(0);
1784 
1785   if (!region->is_Region()) {
1786     return false;
1787   }
1788   Node* dom = phase->idom(region);
1789   if (!dom->is_If()) {
1790     return false;
1791   }
1792 
1793   if (!is_heap_stable_test(n) || !is_heap_stable_test(dom)) {
1794     return false;
1795   }
1796 
1797   IfNode* dom_if = dom->as_If();
1798   Node* proj_true = dom_if->proj_out(1);
1799   Node* proj_false = dom_if->proj_out(0);
1800 
1801   for (uint i = 1; i < region->req(); i++) {
1802     if (phase->is_dominator(proj_true, region->in(i))) {
1803       continue;
1804     }
1805     if (phase->is_dominator(proj_false, region->in(i))) {
1806       continue;
1807     }
1808     return false;
1809   }
1810 
1811   return true;
1812 }
1813 
1814 void ShenandoahBarrierC2Support::merge_back_to_back_tests(Node* n, PhaseIdealLoop* phase) {
1815   assert(is_heap_stable_test(n), "no other tests");
1816   if (identical_backtoback_ifs(n, phase)) {
1817     Node* n_ctrl = n->in(0);
1818     if (phase->can_split_if(n_ctrl)) {
1819       IfNode* dom_if = phase->idom(n_ctrl)->as_If();
1820       if (is_heap_stable_test(n)) {
1821         Node* gc_state_load = n->in(1)->in(1)->in(1)->in(1);
1822         assert(is_gc_state_load(gc_state_load), "broken");
1823         Node* dom_gc_state_load = dom_if->in(1)->in(1)->in(1)->in(1);
1824         assert(is_gc_state_load(dom_gc_state_load), "broken");
1825         if (gc_state_load != dom_gc_state_load) {
1826           phase->igvn().replace_node(gc_state_load, dom_gc_state_load);
1827         }
1828       }
1829       PhiNode* bolphi = PhiNode::make_blank(n_ctrl, n->in(1));
1830       Node* proj_true = dom_if->proj_out(1);
1831       Node* proj_false = dom_if->proj_out(0);
1832       Node* con_true = phase->igvn().makecon(TypeInt::ONE);
1833       Node* con_false = phase->igvn().makecon(TypeInt::ZERO);
1834 
1835       for (uint i = 1; i < n_ctrl->req(); i++) {
1836         if (phase->is_dominator(proj_true, n_ctrl->in(i))) {
1837           bolphi->init_req(i, con_true);
1838         } else {
1839           assert(phase->is_dominator(proj_false, n_ctrl->in(i)), "bad if");
1840           bolphi->init_req(i, con_false);
1841         }
1842       }
1843       phase->register_new_node(bolphi, n_ctrl);
1844       phase->igvn().replace_input_of(n, 1, bolphi);
1845       phase->do_split_if(n);
1846     }
1847   }
1848 }
1849 
1850 IfNode* ShenandoahBarrierC2Support::find_unswitching_candidate(const IdealLoopTree* loop, PhaseIdealLoop* phase) {
1851   // Find first invariant test that doesn't exit the loop
1852   LoopNode *head = loop->_head->as_Loop();
1853   IfNode* unswitch_iff = NULL;
1854   Node* n = head->in(LoopNode::LoopBackControl);
1855   int loop_has_sfpts = -1;
1856   while (n != head) {
1857     Node* n_dom = phase->idom(n);
1858     if (n->is_Region()) {
1859       if (n_dom->is_If()) {
1860         IfNode* iff = n_dom->as_If();
1861         if (iff->in(1)->is_Bool()) {
1862           BoolNode* bol = iff->in(1)->as_Bool();
1863           if (bol->in(1)->is_Cmp()) {
1864             // If condition is invariant and not a loop exit,
1865             // then found reason to unswitch.
1866             if (is_heap_stable_test(iff) &&
1867                 (loop_has_sfpts == -1 || loop_has_sfpts == 0)) {
1868               assert(!loop->is_loop_exit(iff), "both branches should be in the loop");
1869               if (loop_has_sfpts == -1) {
1870                 for(uint i = 0; i < loop->_body.size(); i++) {


1875                   }
1876                 }
1877                 if (loop_has_sfpts == -1) {
1878                   loop_has_sfpts = 0;
1879                 }
1880               }
1881               if (!loop_has_sfpts) {
1882                 unswitch_iff = iff;
1883               }
1884             }
1885           }
1886         }
1887       }
1888     }
1889     n = n_dom;
1890   }
1891   return unswitch_iff;
1892 }
1893 
1894 
1895 void ShenandoahBarrierC2Support::optimize_after_expansion(VectorSet &visited, Node_Stack &stack, Node_List &old_new, PhaseIdealLoop* phase) {
1896   Node_List heap_stable_tests;
1897   Node_List gc_state_loads;

1898   stack.push(phase->C->start(), 0);
1899   do {
1900     Node* n = stack.node();
1901     uint i = stack.index();
1902 
1903     if (i < n->outcnt()) {
1904       Node* u = n->raw_out(i);
1905       stack.set_index(i+1);
1906       if (!visited.test_set(u->_idx)) {
1907         stack.push(u, 0);
1908       }
1909     } else {
1910       stack.pop();
1911       if (ShenandoahCommonGCStateLoads && is_gc_state_load(n)) {
1912         gc_state_loads.push(n);
1913       }
1914       if (n->is_If() && is_heap_stable_test(n)) {
1915         heap_stable_tests.push(n);
1916       }
1917     }


1954             move_heap_stable_test_out_of_loop(iff, phase);
1955             if (loop->policy_unswitching(phase)) {
1956               if (head->is_strip_mined()) {
1957                 OuterStripMinedLoopNode* outer = head->as_CountedLoop()->outer_loop();
1958                 hide_strip_mined_loop(outer, head->as_CountedLoop(), phase);
1959               }
1960               phase->do_unswitching(loop, old_new);
1961             } else {
1962               // Not proceeding with unswitching. Move load back in
1963               // the loop.
1964               phase->igvn().replace_input_of(iff, 1, bol);
1965             }
1966           }
1967         }
1968       }
1969     }
1970   }
1971 }
1972 
1973 #ifdef ASSERT
1974 void ShenandoahBarrierC2Support::verify_raw_mem(RootNode* root) {
1975   const bool trace = false;
1976   ResourceMark rm;
1977   Unique_Node_List nodes;
1978   Unique_Node_List controls;
1979   Unique_Node_List memories;
1980 
1981   nodes.push(root);
1982   for (uint next = 0; next < nodes.size(); next++) {
1983     Node *n  = nodes.at(next);
1984     if (ShenandoahBarrierSetC2::is_shenandoah_wb_call(n)) {
1985       controls.push(n);
1986       if (trace) { tty->print("XXXXXX verifying"); n->dump(); }
1987       for (uint next2 = 0; next2 < controls.size(); next2++) {
1988         Node *m = controls.at(next2);
1989         for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
1990           Node* u = m->fast_out(i);
1991           if (u->is_CFG() && !u->is_Root() &&
1992               !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1) &&
1993               !(u->is_Region() && u->unique_ctrl_out()->Opcode() == Op_Halt)) {
1994             if (trace) { tty->print("XXXXXX pushing control"); u->dump(); }


2052                 }
2053               }
2054             }
2055           }
2056           assert(found_phi || all_in, "");
2057         }
2058       }
2059       controls.clear();
2060       memories.clear();
2061     }
2062     for( uint i = 0; i < n->len(); ++i ) {
2063       Node *m = n->in(i);
2064       if (m != NULL) {
2065         nodes.push(m);
2066       }
2067     }
2068   }
2069 }
2070 #endif
2071 
2072 ShenandoahEnqueueBarrierNode::ShenandoahEnqueueBarrierNode(Node* val) : Node(NULL, val) {
2073   ShenandoahBarrierSetC2::bsc2()->state()->add_enqueue_barrier(this);
2074 }
2075 
2076 const Type* ShenandoahEnqueueBarrierNode::bottom_type() const {
2077   if (in(1) == NULL || in(1)->is_top()) {
2078     return Type::TOP;
2079   }
2080   const Type* t = in(1)->bottom_type();
2081   if (t == TypePtr::NULL_PTR) {
2082     return t;
2083   }
2084   return t->is_oopptr()->cast_to_nonconst();
2085 }
2086 
2087 const Type* ShenandoahEnqueueBarrierNode::Value(PhaseGVN* phase) const {
2088   if (in(1) == NULL) {
2089     return Type::TOP;
2090   }
2091   const Type* t = phase->type(in(1));
2092   if (t == Type::TOP) {
2093     return Type::TOP;
2094   }
2095   if (t == TypePtr::NULL_PTR) {


2214     uint i = stack.index();
2215     if (i < n->req()) {
2216       Node* mem = NULL;
2217       if (opc == Op_Root) {
2218         Node* in = n->in(i);
2219         int in_opc = in->Opcode();
2220         if (in_opc == Op_Return || in_opc == Op_Rethrow) {
2221           mem = in->in(TypeFunc::Memory);
2222         } else if (in_opc == Op_Halt) {
2223           if (!in->in(0)->is_Region()) {
2224             Node* proj = in->in(0);
2225             assert(proj->is_Proj(), "");
2226             Node* in = proj->in(0);
2227             assert(in->is_CallStaticJava() || in->Opcode() == Op_NeverBranch || in->Opcode() == Op_Catch || proj->is_IfProj(), "");
2228             if (in->is_CallStaticJava()) {
2229               mem = in->in(TypeFunc::Memory);
2230             } else if (in->Opcode() == Op_Catch) {
2231               Node* call = in->in(0)->in(0);
2232               assert(call->is_Call(), "");
2233               mem = call->in(TypeFunc::Memory);
2234             } else if (in->Opcode() == Op_NeverBranch) {
2235               ResourceMark rm;
2236               Unique_Node_List wq;
2237               wq.push(in);
2238               wq.push(in->as_Multi()->proj_out(0));
2239               for (uint j = 1; j < wq.size(); j++) {
2240                 Node* c = wq.at(j);
2241                 assert(!c->is_Root(), "shouldn't leave loop");
2242                 if (c->is_SafePoint()) {
2243                   assert(mem == NULL, "only one safepoint");
2244                   mem = c->in(TypeFunc::Memory);
2245                 }
2246                 for (DUIterator_Fast kmax, k = c->fast_outs(kmax); k < kmax; k++) {
2247                   Node* u = c->fast_out(k);
2248                   if (u->is_CFG()) {
2249                     wq.push(u);
2250                   }
2251                 }
2252               }
2253               assert(mem != NULL, "should have found safepoint");
2254             }
2255           }
2256         } else {
2257 #ifdef ASSERT
2258           n->dump();
2259           in->dump();
2260 #endif
2261           ShouldNotReachHere();
2262         }
2263       } else {
2264         assert(n->is_Phi() && n->bottom_type() == Type::MEMORY, "");
2265         assert(n->adr_type() == TypePtr::BOTTOM || _phase->C->get_alias_index(n->adr_type()) == _alias, "");
2266         mem = n->in(i);
2267       }
2268       i++;
2269       stack.set_index(i);
2270       if (mem == NULL) {
2271         continue;
2272       }
2273       for (;;) {
2274         if (visited.test_set(mem->_idx) || mem->is_Start()) {
2275           break;
2276         }
2277         if (mem->is_Phi()) {
2278           stack.push(mem, 2);
2279           mem = mem->in(1);
2280         } else if (mem->is_Proj()) {
2281           stack.push(mem, mem->req());
2282           mem = mem->in(0);
2283         } else if (mem->is_SafePoint() || mem->is_MemBar()) {
2284           mem = mem->in(TypeFunc::Memory);
2285         } else if (mem->is_MergeMem()) {
2286           MergeMemNode* mm = mem->as_MergeMem();
2287           mem = mm->memory_at(_alias);
2288         } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
2289           assert(_alias == Compile::AliasIdxRaw, "");
2290           stack.push(mem, mem->req());
2291           mem = mem->in(MemNode::Memory);






2292         } else {
2293 #ifdef ASSERT
2294           mem->dump();
2295 #endif
2296           ShouldNotReachHere();
2297         }
2298       }
2299     } else {
2300       if (n->is_Phi()) {
2301         // Nothing
2302       } else if (!n->is_Root()) {
2303         Node* c = get_ctrl(n);
2304         _memory_nodes.map(c->_idx, n);
2305       }
2306       stack.pop();
2307     }
2308   } while(stack.is_nonempty());
2309 
2310   // Iterate over CFG nodes in rpo and propagate memory state to
2311   // compute memory state at regions, creating new phis if needed.


2325       }
2326     }
2327   }
2328 #endif
2329   uint last = _phase->C->unique();
2330 
2331 #ifdef ASSERT
2332   uint8_t max_depth = 0;
2333   for (LoopTreeIterator iter(_phase->ltree_root()); !iter.done(); iter.next()) {
2334     IdealLoopTree* lpt = iter.current();
2335     max_depth = MAX2(max_depth, lpt->_nest);
2336   }
2337 #endif
2338 
2339   bool progress = true;
2340   int iteration = 0;
2341   Node_List dead_phis;
2342   while (progress) {
2343     progress = false;
2344     iteration++;
2345     assert(iteration <= 2+max_depth || _phase->C->has_irreducible_loop() || has_never_branch(_phase->C->root()), "");
2346     if (trace) { tty->print_cr("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"); }
2347     IdealLoopTree* last_updated_ilt = NULL;
2348     for (int i = rpo_list.size() - 1; i >= 0; i--) {
2349       Node* c = rpo_list.at(i);
2350 
2351       Node* prev_mem = _memory_nodes[c->_idx];
2352       if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
2353         Node* prev_region = regions[c->_idx];
2354         Node* unique = NULL;
2355         for (uint j = 1; j < c->req() && unique != NodeSentinel; j++) {
2356           Node* m = _memory_nodes[c->in(j)->_idx];
2357           assert(m != NULL || (c->is_Loop() && j == LoopNode::LoopBackControl && iteration == 1) || _phase->C->has_irreducible_loop() || has_never_branch(_phase->C->root()), "expect memory state");
2358           if (m != NULL) {
2359             if (m == prev_region && ((c->is_Loop() && j == LoopNode::LoopBackControl) || (prev_region->is_Phi() && prev_region->in(0) == c))) {
2360               assert(c->is_Loop() && j == LoopNode::LoopBackControl || _phase->C->has_irreducible_loop(), "");
2361               // continue
2362             } else if (unique == NULL) {
2363               unique = m;
2364             } else if (m == unique) {
2365               // continue


2493   else {
2494     assert (n->is_CFG(), "must be a CFG node");
2495     return n;
2496   }
2497 }
2498 
2499 bool MemoryGraphFixer::mem_is_valid(Node* m, Node* c) const {
2500   return m != NULL && get_ctrl(m) == c;
2501 }
2502 
2503 Node* MemoryGraphFixer::find_mem(Node* ctrl, Node* n) const {
2504   assert(n == NULL || _phase->ctrl_or_self(n) == ctrl, "");
2505   Node* mem = _memory_nodes[ctrl->_idx];
2506   Node* c = ctrl;
2507   while (!mem_is_valid(mem, c) &&
2508          (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem))) {
2509     c = _phase->idom(c);
2510     mem = _memory_nodes[c->_idx];
2511   }
2512   if (n != NULL && mem_is_valid(mem, c)) {
2513     while (!ShenandoahBarrierC2Support::is_dominator_same_ctrl(c, mem, n, _phase) && _phase->ctrl_or_self(mem) == ctrl) {
2514       mem = next_mem(mem, _alias);
2515     }
2516     if (mem->is_MergeMem()) {
2517       mem = mem->as_MergeMem()->memory_at(_alias);
2518     }
2519     if (!mem_is_valid(mem, c)) {
2520       do {
2521         c = _phase->idom(c);
2522         mem = _memory_nodes[c->_idx];
2523       } while (!mem_is_valid(mem, c) &&
2524                (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem)));
2525     }
2526   }
2527   assert(mem->bottom_type() == Type::MEMORY, "");
2528   return mem;
2529 }
2530 
2531 bool MemoryGraphFixer::has_mem_phi(Node* region) const {
2532   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
2533     Node* use = region->fast_out(i);


2539   return false;
2540 }
2541 
2542 void MemoryGraphFixer::fix_mem(Node* ctrl, Node* new_ctrl, Node* mem, Node* mem_for_ctrl, Node* new_mem, Unique_Node_List& uses) {
2543   assert(_phase->ctrl_or_self(new_mem) == new_ctrl, "");
2544   const bool trace = false;
2545   DEBUG_ONLY(if (trace) { tty->print("ZZZ control is"); ctrl->dump(); });
2546   DEBUG_ONLY(if (trace) { tty->print("ZZZ mem is"); mem->dump(); });
2547   GrowableArray<Node*> phis;
2548   if (mem_for_ctrl != mem) {
2549     Node* old = mem_for_ctrl;
2550     Node* prev = NULL;
2551     while (old != mem) {
2552       prev = old;
2553       if (old->is_Store() || old->is_ClearArray() || old->is_LoadStore()) {
2554         assert(_alias == Compile::AliasIdxRaw, "");
2555         old = old->in(MemNode::Memory);
2556       } else if (old->Opcode() == Op_SCMemProj) {
2557         assert(_alias == Compile::AliasIdxRaw, "");
2558         old = old->in(0);






2559       } else {
2560         ShouldNotReachHere();
2561       }
2562     }
2563     assert(prev != NULL, "");
2564     if (new_ctrl != ctrl) {
2565       _memory_nodes.map(ctrl->_idx, mem);
2566       _memory_nodes.map(new_ctrl->_idx, mem_for_ctrl);
2567     }
2568     uint input = (uint)MemNode::Memory;
2569     _phase->igvn().replace_input_of(prev, input, new_mem);
2570   } else {
2571     uses.clear();
2572     _memory_nodes.map(new_ctrl->_idx, new_mem);
2573     uses.push(new_ctrl);
2574     for(uint next = 0; next < uses.size(); next++ ) {
2575       Node *n = uses.at(next);
2576       assert(n->is_CFG(), "");
2577       DEBUG_ONLY(if (trace) { tty->print("ZZZ ctrl"); n->dump(); });
2578       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2579         Node* u = n->fast_out(i);
2580         if (!u->is_Root() && u->is_CFG() && u != n) {
2581           Node* m = _memory_nodes[u->_idx];
2582           if (u->is_Region() && (!u->is_OuterStripMinedLoop() || _include_lsm) &&
2583               !has_mem_phi(u) &&
2584               u->unique_ctrl_out()->Opcode() != Op_Halt) {
2585             DEBUG_ONLY(if (trace) { tty->print("ZZZ region"); u->dump(); });
2586             DEBUG_ONLY(if (trace && m != NULL) { tty->print("ZZZ mem"); m->dump(); });
2587 
2588             if (!mem_is_valid(m, u) || !m->is_Phi()) {


2616                       do_check = false;
2617                     }
2618                   }
2619                 }
2620 
2621                 if (do_check && _phase->is_dominator(_phase->idom(u), new_ctrl)) {
2622                   create_phi = true;
2623                 }
2624               }
2625               if (create_phi) {
2626                 Node* phi = new PhiNode(u, Type::MEMORY, _phase->C->get_adr_type(_alias));
2627                 _phase->register_new_node(phi, u);
2628                 phis.push(phi);
2629                 DEBUG_ONLY(if (trace) { tty->print("ZZZ new phi"); phi->dump(); });
2630                 if (!mem_is_valid(m, u)) {
2631                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting mem"); phi->dump(); });
2632                   _memory_nodes.map(u->_idx, phi);
2633                 } else {
2634                   DEBUG_ONLY(if (trace) { tty->print("ZZZ NOT setting mem"); m->dump(); });
2635                   for (;;) {
2636                     assert(m->is_Mem() || m->is_LoadStore() || m->is_Proj(), "");
2637                     Node* next = NULL;
2638                     if (m->is_Proj()) {
2639                       next = m->in(0);
2640                     } else {
2641                       assert(m->is_Mem() || m->is_LoadStore(), "");

2642                       assert(_alias == Compile::AliasIdxRaw, "");
2643                       next = m->in(MemNode::Memory);




2644                     }
2645                     if (_phase->get_ctrl(next) != u) {
2646                       break;
2647                     }
2648                     if (next->is_MergeMem()) {
2649                       assert(_phase->get_ctrl(next->as_MergeMem()->memory_at(_alias)) != u, "");
2650                       break;
2651                     }
2652                     if (next->is_Phi()) {
2653                       assert(next->adr_type() == TypePtr::BOTTOM && next->in(0) == u, "");
2654                       break;
2655                     }
2656                     m = next;
2657                   }
2658 
2659                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting to phi"); m->dump(); });
2660                   assert(m->is_Mem() || m->is_LoadStore(), "");
2661                   uint input = (uint)MemNode::Memory;
2662                   _phase->igvn().replace_input_of(m, input, phi);
2663                   push = false;
2664                 }
2665               } else {
2666                 DEBUG_ONLY(if (trace) { tty->print("ZZZ skipping region"); u->dump(); });
2667               }
2668               if (push) {
2669                 uses.push(u);
2670               }
2671             }
2672           } else if (!mem_is_valid(m, u) &&
2673                      !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1)) {
2674             uses.push(u);
2675           }
2676         }
2677       }
2678     }
2679     for (int i = 0; i < phis.length(); i++) {
2680       Node* n = phis.at(i);
2681       Node* r = n->in(0);


2867   if (phi->adr_type() == TypePtr::BOTTOM) {
2868     Node* region = phi->in(0);
2869     for (DUIterator_Fast jmax, j = region->fast_outs(jmax); j < jmax; j++) {
2870       Node* uu = region->fast_out(j);
2871       if (uu->is_Phi() && uu != phi && uu->bottom_type() == Type::MEMORY && _phase->C->get_alias_index(uu->adr_type()) == _alias) {
2872         return false;
2873       }
2874     }
2875     return true;
2876   }
2877   return _phase->C->get_alias_index(phi->adr_type()) == _alias;
2878 }
2879 
2880 void MemoryGraphFixer::fix_memory_uses(Node* mem, Node* replacement, Node* rep_proj, Node* rep_ctrl) const {
2881   uint last = _phase-> C->unique();
2882   MergeMemNode* mm = NULL;
2883   assert(mem->bottom_type() == Type::MEMORY, "");
2884   for (DUIterator i = mem->outs(); mem->has_out(i); i++) {
2885     Node* u = mem->out(i);
2886     if (u != replacement && u->_idx < last) {
2887       if (u->is_MergeMem()) {













2888         MergeMemNode* u_mm = u->as_MergeMem();
2889         if (u_mm->memory_at(_alias) == mem) {
2890           MergeMemNode* newmm = NULL;
2891           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
2892             Node* uu = u->fast_out(j);
2893             assert(!uu->is_MergeMem(), "chain of MergeMems?");
2894             if (uu->is_Phi()) {
2895               if (should_process_phi(uu)) {
2896                 Node* region = uu->in(0);
2897                 int nb = 0;
2898                 for (uint k = 1; k < uu->req(); k++) {
2899                   if (uu->in(k) == u && _phase->is_dominator(rep_ctrl, region->in(k))) {
2900                     if (newmm == NULL) {
2901                       newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
2902                     }
2903                     if (newmm != u) {
2904                       _phase->igvn().replace_input_of(uu, k, newmm);
2905                       nb++;
2906                       --jmax;
2907                     }
2908                   }
2909                 }
2910                 if (nb > 0) {
2911                   --j;
2912                 }
2913               }
2914             } else {
2915               if (rep_ctrl != uu && ShenandoahBarrierC2Support::is_dominator(rep_ctrl, _phase->ctrl_or_self(uu), replacement, uu, _phase)) {
2916                 if (newmm == NULL) {
2917                   newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
2918                 }
2919                 if (newmm != u) {
2920                   _phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
2921                   --j, --jmax;
2922                 }
2923               }
2924             }
2925           }
2926         }
2927       } else if (u->is_Phi()) {
2928         assert(u->bottom_type() == Type::MEMORY, "what else?");
2929         Node* region = u->in(0);
2930         if (should_process_phi(u)) {
2931           bool replaced = false;
2932           for (uint j = 1; j < u->req(); j++) {
2933             if (u->in(j) == mem && _phase->is_dominator(rep_ctrl, region->in(j))) {
2934               Node* nnew = rep_proj;
2935               if (u->adr_type() == TypePtr::BOTTOM) {
2936                 if (mm == NULL) {
2937                   mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
2938                 }
2939                 nnew = mm;
2940               }
2941               _phase->igvn().replace_input_of(u, j, nnew);
2942               replaced = true;
2943             }
2944           }
2945           if (replaced) {
2946             --i;
2947           }
2948 
2949         }
2950       } else if ((u->adr_type() == TypePtr::BOTTOM && u->Opcode() != Op_StrInflatedCopy) ||
2951                  u->adr_type() == NULL) {
2952         assert(u->adr_type() != NULL ||
2953                u->Opcode() == Op_Rethrow ||
2954                u->Opcode() == Op_Return ||
2955                u->Opcode() == Op_SafePoint ||
2956                u->Opcode() == Op_StoreLConditional ||
2957                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
2958                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
2959                u->Opcode() == Op_CallLeaf, "");
2960         if (ShenandoahBarrierC2Support::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
2961           if (mm == NULL) {
2962             mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
2963           }
2964           _phase->igvn().replace_input_of(u, u->find_edge(mem), mm);
2965           --i;
2966         }
2967       } else if (_phase->C->get_alias_index(u->adr_type()) == _alias) {
2968         if (ShenandoahBarrierC2Support::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
2969           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
2970           --i;
2971         }
2972       }
2973     }
2974   }
2975 }
2976 
2977 ShenandoahLoadReferenceBarrierNode::ShenandoahLoadReferenceBarrierNode(Node* ctrl, Node* obj)
2978 : Node(ctrl, obj) {
2979   ShenandoahBarrierSetC2::bsc2()->state()->add_load_reference_barrier(this);
2980 }
2981 
2982 const Type* ShenandoahLoadReferenceBarrierNode::bottom_type() const {
2983   if (in(ValueIn) == NULL || in(ValueIn)->is_top()) {
2984     return Type::TOP;
2985   }
2986   const Type* t = in(ValueIn)->bottom_type();
2987   if (t == TypePtr::NULL_PTR) {
2988     return t;
2989   }
2990   return t->is_oopptr();
2991 }
2992 
2993 const Type* ShenandoahLoadReferenceBarrierNode::Value(PhaseGVN* phase) const {
2994   // Either input is TOP ==> the result is TOP
2995   const Type *t2 = phase->type(in(ValueIn));
2996   if( t2 == Type::TOP ) return Type::TOP;
2997 
2998   if (t2 == TypePtr::NULL_PTR) {
2999     return t2;
3000   }
3001 
3002   const Type* type = t2->is_oopptr()/*->cast_to_nonconst()*/;
3003   return type;
3004 }
3005 
3006 Node* ShenandoahLoadReferenceBarrierNode::Identity(PhaseGVN* phase) {
3007   Node* value = in(ValueIn);
3008   if (!needs_barrier(phase, value)) {
3009     return value;
3010   }
3011   return this;
3012 }
3013 
3014 bool ShenandoahLoadReferenceBarrierNode::needs_barrier(PhaseGVN* phase, Node* n) {
3015   Unique_Node_List visited;
3016   return needs_barrier_impl(phase, n, visited);
3017 }
3018 
3019 bool ShenandoahLoadReferenceBarrierNode::needs_barrier_impl(PhaseGVN* phase, Node* n, Unique_Node_List &visited) {
3020   if (n == NULL) return false;
3021   if (visited.member(n)) {
3022     return false; // Been there.
3023   }
3024   visited.push(n);
3025 
3026   if (n->is_Allocate()) {
3027     // tty->print_cr("optimize barrier on alloc");
3028     return false;
3029   }
3030   if (n->is_Call()) {
3031     // tty->print_cr("optimize barrier on call");
3032     return false;
3033   }
3034 
3035   const Type* type = phase->type(n);
3036   if (type == Type::TOP) {
3037     return false;
3038   }
3039   if (type->make_ptr()->higher_equal(TypePtr::NULL_PTR)) {
3040     // tty->print_cr("optimize barrier on null");
3041     return false;
3042   }
3043   if (type->make_oopptr() && type->make_oopptr()->const_oop() != NULL) {
3044     // tty->print_cr("optimize barrier on constant");
3045     return false;
3046   }
3047 
3048   switch (n->Opcode()) {
3049     case Op_AddP:
3050 //      tty->print_cr("ins:");
3051 //      n->dump(2);
3052 //      tty->print_cr("outs:");
3053 //      n->dump(-3);
3054 //      assert(false, "can refine?");
3055       return true; // TODO: Can refine?
3056     case Op_LoadP:
3057     case Op_ShenandoahCompareAndExchangeN:
3058     case Op_ShenandoahCompareAndExchangeP:
3059     case Op_CompareAndExchangeN:
3060     case Op_CompareAndExchangeP:
3061     case Op_GetAndSetN:
3062     case Op_GetAndSetP:
3063       return true;
3064     case Op_Phi: {
3065       for (uint i = 1; i < n->req(); i++) {
3066         if (needs_barrier_impl(phase, n->in(i), visited)) return true;
3067       }
3068       return false;
3069     }
3070     case Op_CheckCastPP:
3071     case Op_CastPP:
3072       return needs_barrier_impl(phase, n->in(1), visited);
3073     case Op_Proj:
3074       return needs_barrier_impl(phase, n->in(0), visited);
3075     case Op_ShenandoahLoadReferenceBarrier:
3076       // tty->print_cr("optimize barrier on barrier");
3077       return false;
3078     case Op_Parm:
3079       // tty->print_cr("optimize barrier on input arg");
3080       return false;
3081     case Op_DecodeN:
3082     case Op_EncodeP:
3083       return needs_barrier_impl(phase, n->in(1), visited);
3084     case Op_LoadN:
3085       return true;
3086     case Op_CMoveP:
3087       return needs_barrier_impl(phase, n->in(2), visited) ||
3088              needs_barrier_impl(phase, n->in(3), visited);
3089     case Op_ShenandoahEnqueueBarrier:
3090       return needs_barrier_impl(phase, n->in(1), visited);
3091     default:
3092       break;
3093   }
3094 #ifdef ASSERT
3095   tty->print("need barrier on?: ");
3096   tty->print_cr("ins:");
3097   n->dump(2);
3098   tty->print_cr("outs:");
3099   n->dump(-2);
3100   ShouldNotReachHere();
3101 #endif
3102   return true;
3103 }
3104 
3105 ShenandoahLoadReferenceBarrierNode::Strength ShenandoahLoadReferenceBarrierNode::get_barrier_strength() {
3106   Unique_Node_List visited;
3107   Node_Stack stack(0);
3108   stack.push(this, 0);
3109   Strength strength = NONE;
3110   while (strength != STRONG && stack.size() > 0) {
3111     Node* n = stack.node();
3112     if (visited.member(n)) {
3113       stack.pop();
3114       continue;
3115     }
3116     visited.push(n);
3117     bool visit_users = false;
3118     switch (n->Opcode()) {
3119       case Op_StoreN:
3120       case Op_StoreP: {
3121         strength = STRONG;
3122         break;
3123       }
3124       case Op_CmpP: {
3125         if (!n->in(1)->bottom_type()->higher_equal(TypePtr::NULL_PTR) &&
3126             !n->in(2)->bottom_type()->higher_equal(TypePtr::NULL_PTR)) {
3127           strength = STRONG;
3128         }
3129         break;
3130       }
3131       case Op_CallStaticJava: {
3132         strength = STRONG;
3133         break;
3134       }
3135       case Op_CallDynamicJava:
3136       case Op_CallLeaf:
3137       case Op_CallLeafNoFP:
3138       case Op_CompareAndSwapL:
3139       case Op_CompareAndSwapI:
3140       case Op_CompareAndSwapB:
3141       case Op_CompareAndSwapS:
3142       case Op_ShenandoahCompareAndSwapN:
3143       case Op_ShenandoahCompareAndSwapP:
3144       case Op_ShenandoahWeakCompareAndSwapN:
3145       case Op_ShenandoahWeakCompareAndSwapP:
3146       case Op_ShenandoahCompareAndExchangeN:
3147       case Op_ShenandoahCompareAndExchangeP:
3148       case Op_CompareAndExchangeL:
3149       case Op_CompareAndExchangeI:
3150       case Op_CompareAndExchangeB:
3151       case Op_CompareAndExchangeS:
3152       case Op_WeakCompareAndSwapL:
3153       case Op_WeakCompareAndSwapI:
3154       case Op_WeakCompareAndSwapB:
3155       case Op_WeakCompareAndSwapS:
3156       case Op_GetAndSetL:
3157       case Op_GetAndSetI:
3158       case Op_GetAndSetB:
3159       case Op_GetAndSetS:
3160       case Op_GetAndSetP:
3161       case Op_GetAndSetN:
3162       case Op_GetAndAddL:
3163       case Op_GetAndAddI:
3164       case Op_GetAndAddB:
3165       case Op_GetAndAddS:
3166       case Op_ShenandoahEnqueueBarrier:
3167       case Op_FastLock:
3168       case Op_FastUnlock:
3169       case Op_Rethrow:
3170       case Op_Return:
3171       case Op_StoreB:
3172       case Op_StoreC:
3173       case Op_StoreD:
3174       case Op_StoreF:
3175       case Op_StoreL:
3176       case Op_StoreLConditional:
3177       case Op_StoreI:
3178       case Op_StoreVector:
3179       case Op_StrInflatedCopy:
3180       case Op_StrCompressedCopy:
3181       case Op_EncodeP:
3182       case Op_CastP2X:
3183       case Op_SafePoint:
3184       case Op_EncodeISOArray:
3185         strength = STRONG;
3186         break;
3187       case Op_LoadB:
3188       case Op_LoadUB:
3189       case Op_LoadUS:
3190       case Op_LoadD:
3191       case Op_LoadF:
3192       case Op_LoadL:
3193       case Op_LoadI:
3194       case Op_LoadS:
3195       case Op_LoadN:
3196       case Op_LoadP:
3197       case Op_LoadVector: {
3198         const TypePtr* adr_type = n->adr_type();
3199         int alias_idx = Compile::current()->get_alias_index(adr_type);
3200         Compile::AliasType* alias_type = Compile::current()->alias_type(alias_idx);
3201         ciField* field = alias_type->field();
3202         bool is_static = field != NULL && field->is_static();
3203         bool is_final = field != NULL && field->is_final();
3204         bool is_stable = field != NULL && field->is_stable();
3205         if (ShenandoahOptimizeStaticFinals && is_static && is_final) {
3206           // Leave strength as is.
3207         } else if (ShenandoahOptimizeInstanceFinals && !is_static && is_final) {
3208           // Leave strength as is.
3209         } else if (ShenandoahOptimizeStableFinals && (is_stable || (adr_type->isa_aryptr() && adr_type->isa_aryptr()->is_stable()))) {
3210           // Leave strength as is.
3211         } else {
3212           strength = WEAK;
3213         }
3214         break;
3215       }
3216       case Op_AryEq: {
3217         Node* n1 = n->in(2);
3218         Node* n2 = n->in(3);
3219         if (!ShenandoahOptimizeStableFinals ||
3220             !n1->bottom_type()->isa_aryptr() || !n1->bottom_type()->isa_aryptr()->is_stable() ||
3221             !n2->bottom_type()->isa_aryptr() || !n2->bottom_type()->isa_aryptr()->is_stable()) {
3222           strength = WEAK;
3223         }
3224         break;
3225       }
3226       case Op_StrEquals:
3227       case Op_StrComp:
3228       case Op_StrIndexOf:
3229       case Op_StrIndexOfChar:
3230         if (!ShenandoahOptimizeStableFinals) {
3231            strength = WEAK;
3232         }
3233         break;
3234       case Op_Conv2B:
3235       case Op_LoadRange:
3236       case Op_LoadKlass:
3237       case Op_LoadNKlass:
3238         // NONE, i.e. leave current strength as is
3239         break;
3240       case Op_AddP:
3241       case Op_CheckCastPP:
3242       case Op_CastPP:
3243       case Op_CMoveP:
3244       case Op_Phi:
3245       case Op_ShenandoahLoadReferenceBarrier:
3246         visit_users = true;
3247         break;
3248       default: {
3249 #ifdef ASSERT
3250         tty->print_cr("Unknown node in get_barrier_strength:");
3251         n->dump(1);
3252         ShouldNotReachHere();
3253 #else
3254         strength = STRONG;
3255 #endif
3256       }
3257     }
3258 #ifdef ASSERT
3259 /*
3260     if (strength == STRONG) {
3261       tty->print("strengthening node: ");
3262       n->dump();
3263     }
3264     */
3265 #endif
3266     stack.pop();
3267     if (visit_users) {
3268       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3269         Node* user = n->fast_out(i);
3270         if (user != NULL) {
3271           stack.push(user, 0);
3272         }
3273       }
3274     }
3275   }
3276   return strength;
3277 }
3278 
3279 CallStaticJavaNode* ShenandoahLoadReferenceBarrierNode::pin_and_expand_null_check(PhaseIterGVN& igvn) {
3280   Node* val = in(ValueIn);
3281 
3282   const Type* val_t = igvn.type(val);
3283 
3284   if (val_t->meet(TypePtr::NULL_PTR) != val_t &&
3285       val->Opcode() == Op_CastPP &&
3286       val->in(0) != NULL &&
3287       val->in(0)->Opcode() == Op_IfTrue &&
3288       val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
3289       val->in(0)->in(0)->is_If() &&
3290       val->in(0)->in(0)->in(1)->Opcode() == Op_Bool &&
3291       val->in(0)->in(0)->in(1)->as_Bool()->_test._test == BoolTest::ne &&
3292       val->in(0)->in(0)->in(1)->in(1)->Opcode() == Op_CmpP &&
3293       val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1) &&
3294       val->in(0)->in(0)->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
3295     assert(val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1), "");
3296     CallStaticJavaNode* unc = val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
3297     return unc;
3298   }
3299   return NULL;
3300 }
< prev index next >