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_CallJava() || n->Opcode() == Op_CallLeafNoFP) {
 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 {
 786         return false;
 787       }
 788     }
 789     bool cont = false;
 790     while (phis.is_nonempty()) {
 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 
 842         if (adr_type->isa_oopptr() && adr_type->is_oopptr()->offset() == oopDesc::mark_offset_in_bytes()) {
 843           if (trace) {tty->print_cr("Mark load");}
 844         } else if (adr_type->isa_instptr() &&
 845                    adr_type->is_instptr()->klass()->is_subtype_of(Compile::current()->env()->Reference_klass()) &&
 846                    adr_type->is_instptr()->offset() == java_lang_ref_Reference::referent_offset) {
 847           if (trace) {tty->print_cr("Reference.get()");}
 848         } else {
 849           bool verify = true;
 850           if (adr_type->isa_instptr()) {
 851             const TypeInstPtr* tinst = adr_type->is_instptr();
 852             ciKlass* k = tinst->klass();
 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 },
 968           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 969         "squareToLen",
 970         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },   { -1,  ShenandoahNone},
 971           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 972         "montgomery_multiply",
 973         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },
 974           { TypeFunc::Parms+6, ShenandoahStore }, { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 975         "montgomery_square",
 976         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+5, ShenandoahStore },
 977           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 978         "mulAdd",
 979         { { TypeFunc::Parms, ShenandoahStore },  { TypeFunc::Parms+1, ShenandoahLoad },   { -1,  ShenandoahNone},
 980           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 981         "vectorizedMismatch",
 982         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { -1,  ShenandoahNone},
 983           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 984         "updateBytesCRC32",
 985         { { TypeFunc::Parms+1, ShenandoahLoad }, { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 986           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 987         "updateBytesAdler32",
 988         { { TypeFunc::Parms+1, ShenandoahLoad }, { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 989           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 990         "updateBytesCRC32C",
 991         { { TypeFunc::Parms+1, ShenandoahLoad }, { TypeFunc::Parms+3, ShenandoahLoad},    { -1,  ShenandoahNone},
 992           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 993         "counterMode_AESCrypt",
 994         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 995           { TypeFunc::Parms+3, ShenandoahStore }, { TypeFunc::Parms+5, ShenandoahStore }, { TypeFunc::Parms+6, ShenandoahStore } },
 996         "cipherBlockChaining_encryptAESCrypt",
 997         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 998           { TypeFunc::Parms+3, ShenandoahLoad },  { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 999         "cipherBlockChaining_decryptAESCrypt",
1000         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
1001           { TypeFunc::Parms+3, ShenandoahLoad },  { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1002         "shenandoah_clone_barrier",
1003         { { TypeFunc::Parms, ShenandoahLoad },   { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
1004           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1005         "ghash_processBlocks",
1006         { { TypeFunc::Parms, ShenandoahStore },  { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },
1007           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1008         "sha1_implCompress",
1009         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
1010           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1011         "sha256_implCompress",
1012         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
1013           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1014         "sha512_implCompress",
1015         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
1016           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1017         "sha1_implCompressMB",
1018         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
1019           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1020         "sha256_implCompressMB",
1021         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
1022           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1023         "sha512_implCompressMB",
1024         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
1025           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
1026       };
1027 
1028       if (call->is_call_to_arraycopystub()) {
1029         Node* dest = NULL;
1030         const TypeTuple* args = n->as_Call()->_tf->domain();
1031         for (uint i = TypeFunc::Parms, j = 0; i < args->cnt(); i++) {
1032           if (args->field_at(i)->isa_ptr()) {
1033             j++;
1034             if (j == 2) {
1035               dest = n->in(i);
1036               break;
1037             }
1038           }
1039         }
1040         if (!ShenandoahBarrierNode::verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahLoad, trace, barriers_used) ||
1041             !ShenandoahBarrierNode::verify_helper(dest, phis, visited, ShenandoahStore, trace, barriers_used)) {
1042           report_verify_failure("Shenandoah verification: ArrayCopy should have barriers", n);
1043         }
1044       } else if (strlen(call->_name) > 5 &&
1045                  !strcmp(call->_name + strlen(call->_name) - 5, "_fill")) {
1046         if (!ShenandoahBarrierNode::verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahStore, trace, barriers_used)) {
1047           report_verify_failure("Shenandoah verification: _fill should have barriers", n);
1048         }
1049       } else if (!strcmp(call->_name, "shenandoah_wb_pre")) {
1050         // skip
1051       } else {
1052         const int calls_len = sizeof(calls) / sizeof(calls[0]);
1053         int i = 0;
1054         for (; i < calls_len; i++) {
1055           if (!strcmp(calls[i].name, call->_name)) {
1056             break;
1057           }
1058         }
1059         if (i != calls_len) {
1060           const uint args_len = sizeof(calls[0].args) / sizeof(calls[0].args[0]);
1061           for (uint j = 0; j < args_len; j++) {
1062             int pos = calls[i].args[j].pos;
1063             if (pos == -1) {
1064               break;
1065             }
1066             if (!ShenandoahBarrierNode::verify_helper(call->in(pos), phis, visited, calls[i].args[j].t, trace, barriers_used)) {
1067               report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
1068             }
1069           }
1070           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
1071             if (call->in(j)->bottom_type()->make_ptr() &&
1072                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
1073               uint k = 0;
1074               for (; k < args_len && calls[i].args[k].pos != (int)j; k++);
1075               if (k == args_len) {
1076                 fatal("arg %d for call %s not covered", j, call->_name);
1077               }
1078             }
1079           }
1080         } else {
1081           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
1082             if (call->in(j)->bottom_type()->make_ptr() &&
1083                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
1084               fatal("%s not covered", call->_name);
1085             }
1086           }
1087         }
1088       }
1089     } else if (n->is_ShenandoahBarrier()) {
1090       assert(!barriers.contains(n), "");
1091       assert(n->Opcode() != Op_ShenandoahWriteBarrier || n->find_out_with(Op_ShenandoahWBMemProj) != NULL, "bad shenandoah write barrier");
1092       assert(n->Opcode() != Op_ShenandoahWriteBarrier || n->outcnt() > 1, "bad shenandoah write barrier");
1093       barriers.push(n);
1094     } else if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
1095       // skip
1096     } else if (n->Opcode() == Op_ShenandoahWBMemProj) {
1097       assert(n->in(0) == NULL && n->in(ShenandoahWBMemProjNode::WriteBarrier)->Opcode() == Op_ShenandoahWriteBarrier, "strange ShenandoahWBMemProj");
1098     } else if (n->is_AddP()
1099                || n->is_Phi()
1100                || n->is_ConstraintCast()
1101                || n->Opcode() == Op_Return
1102                || n->Opcode() == Op_CMoveP
1103                || n->Opcode() == Op_CMoveN
1104                || n->Opcode() == Op_Rethrow
1105                || n->is_MemBar()
1106                || n->Opcode() == Op_Conv2B
1107                || n->Opcode() == Op_SafePoint
1108                || n->is_CallJava()
1109                || n->Opcode() == Op_Unlock
1110                || n->Opcode() == Op_EncodeP
1111                || n->Opcode() == Op_DecodeN) {
1112       // nothing to do
1113     } else {
1114       static struct {
1115         int opcode;
1116         struct {
1117           int pos;
1118           verify_type t;
1119         } inputs[2];
1120       } others[] = {
1121         Op_FastLock,
1122         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
1123         Op_Lock,
1124         { { TypeFunc::Parms, ShenandoahLoad },    { -1, ShenandoahNone} },
1125         Op_ArrayCopy,
1126         { { ArrayCopyNode::Src, ShenandoahLoad }, { ArrayCopyNode::Dest, ShenandoahStore } },
1127         Op_StrCompressedCopy,
1128         { { 2, ShenandoahLoad },                  { 3, ShenandoahStore } },
1129         Op_StrInflatedCopy,
1130         { { 2, ShenandoahLoad },                  { 3, ShenandoahStore } },
1131         Op_AryEq,
1132         { { 2, ShenandoahLoad },                  { 3, ShenandoahLoad } },
1133         Op_StrIndexOf,
1134         { { 2, ShenandoahLoad },                  { 4, ShenandoahLoad } },
1135         Op_StrComp,
1136         { { 2, ShenandoahLoad },                  { 4, ShenandoahLoad } },
1137         Op_StrEquals,
1138         { { 2, ShenandoahLoad },                  { 3, ShenandoahLoad } },
1139         Op_EncodeISOArray,
1140         { { 2, ShenandoahLoad },                  { 3, ShenandoahStore } },
1141         Op_HasNegatives,
1142         { { 2, ShenandoahLoad },                  { -1, ShenandoahNone} },
1143         Op_CastP2X,
1144         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
1145         Op_StrIndexOfChar,
1146         { { 2, ShenandoahLoad },                  { -1, ShenandoahNone } },
1147       };
1148 
1149       const int others_len = sizeof(others) / sizeof(others[0]);
1150       int i = 0;
1151       for (; i < others_len; i++) {
1152         if (others[i].opcode == n->Opcode()) {
1153           break;
1154         }
1155       }
1156       uint stop = n->is_Call() ? n->as_Call()->tf()->domain()->cnt() : n->req();
1157       if (i != others_len) {
1158         const uint inputs_len = sizeof(others[0].inputs) / sizeof(others[0].inputs[0]);
1159         for (uint j = 0; j < inputs_len; j++) {
1160           int pos = others[i].inputs[j].pos;
1161           if (pos == -1) {
1162             break;
1163           }
1164           if (!ShenandoahBarrierNode::verify_helper(n->in(pos), phis, visited, others[i].inputs[j].t, trace, barriers_used)) {
1165             report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
1166           }
1167         }
1168         for (uint j = 1; j < stop; j++) {
1169           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
1170               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
1171             uint k = 0;
1172             for (; k < inputs_len && others[i].inputs[k].pos != (int)j; k++);
1173             if (k == inputs_len) {
1174               fatal("arg %d for node %s not covered", j, n->Name());
1175             }
1176           }
1177         }
1178       } else {
1179         for (uint j = 1; j < stop; j++) {
1180           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
1181               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
1182             fatal("%s not covered", n->Name());
1183           }
1184         }
1185       }
1186     }
1187 
1188     if (n->is_SafePoint()) {
1189       SafePointNode* sfpt = n->as_SafePoint();
1190       if (verify_no_useless_barrier && sfpt->jvms() != NULL) {
1191         for (uint i = sfpt->jvms()->scloff(); i < sfpt->jvms()->endoff(); i++) {
1192           if (!ShenandoahBarrierNode::verify_helper(sfpt->in(i), phis, visited, ShenandoahLoad, trace, barriers_used)) {
1193             phis.clear();
1194             visited.Reset();
1195           }
1196         }
1197       }
1198     }
1199     for( uint i = 0; i < n->len(); ++i ) {
1200       Node *m = n->in(i);
1201       if (m == NULL) continue;
1202 
1203       // In most cases, inputs should be known to be non null. If it's
1204       // not the case, it could be a missing cast_not_null() in an
1205       // intrinsic or support might be needed in AddPNode::Ideal() to
1206       // avoid a NULL+offset input.
1207       if (!(n->is_Phi() ||
1208             (n->is_SafePoint() && (!n->is_CallRuntime() || !strcmp(n->as_Call()->_name, "shenandoah_wb_pre") || !strcmp(n->as_Call()->_name, "unsafe_arraycopy"))) ||
1209             n->Opcode() == Op_CmpP ||
1210             n->Opcode() == Op_CmpN ||
1211             (n->Opcode() == Op_StoreP && i == StoreNode::ValueIn) ||
1212             (n->Opcode() == Op_StoreN && i == StoreNode::ValueIn) ||
1213             n->is_ConstraintCast() ||
1214             n->Opcode() == Op_Return ||
1215             n->Opcode() == Op_Conv2B ||
1216             n->is_AddP() ||
1217             n->Opcode() == Op_CMoveP ||
1218             n->Opcode() == Op_CMoveN ||
1219             n->Opcode() == Op_Rethrow ||
1220             n->is_MemBar() ||
1221             n->is_Mem() ||
1222             n->Opcode() == Op_AryEq ||
1223             n->Opcode() == Op_SCMemProj ||
1224             n->Opcode() == Op_EncodeP ||
1225             n->Opcode() == Op_DecodeN ||
1226             n->Opcode() == Op_ShenandoahWriteBarrier ||
1227             n->Opcode() == Op_ShenandoahWBMemProj ||
1228             n->Opcode() == Op_ShenandoahEnqueueBarrier)) {
1229         if (m->bottom_type()->make_oopptr() && m->bottom_type()->make_oopptr()->meet(TypePtr::NULL_PTR) == m->bottom_type()) {
1230           report_verify_failure("Shenandoah verification: null input", n, m);
1231         }
1232       }
1233 
1234       wq.push(m);
1235     }
1236   }
1237 
1238   if (verify_no_useless_barrier) {
1239     for (int i = 0; i < barriers.length(); i++) {
1240       Node* n = barriers.at(i);
1241       if (!barriers_used.member(n)) {
1242         tty->print("XXX useless barrier"); n->dump(-2);
1243         ShouldNotReachHere();
1244       }
1245     }
1246   }
1247 }
1248 #endif
1249 
1250 bool ShenandoahBarrierNode::is_dominator_same_ctrl(Node*c, Node* d, Node* n, PhaseIdealLoop* phase) {
1251   // That both nodes have the same control is not sufficient to prove
1252   // domination, verify that there's no path from d to n
1253   ResourceMark rm;
1254   Unique_Node_List wq;
1255   wq.push(d);
1256   for (uint next = 0; next < wq.size(); next++) {
1257     Node *m = wq.at(next);
1258     if (m == n) {
1259       return false;
1260     }
1261     if (m->is_Phi() && m->in(0)->is_Loop()) {
1262       assert(phase->ctrl_or_self(m->in(LoopNode::EntryControl)) != c, "following loop entry should lead to new control");
1263     } else {
1264       for (uint i = 0; i < m->req(); i++) {
1265         if (m->in(i) != NULL && phase->ctrl_or_self(m->in(i)) == c) {
1266           wq.push(m->in(i));
1267         }
1268       }
1269     }
1270   }
1271   return true;
1272 }
1273 
1274 bool ShenandoahBarrierNode::is_dominator(Node *d_c, Node *n_c, Node* d, Node* n, PhaseIdealLoop* phase) {
1275   if (d_c != n_c) {
1276     return phase->is_dominator(d_c, n_c);
1277   }
1278   return is_dominator_same_ctrl(d_c, d, n, phase);
1279 }
1280 
1281 Node* next_mem(Node* mem, int alias) {
1282   Node* res = NULL;
1283   if (mem->is_Proj()) {
1284     res = mem->in(0);
1285   } else if (mem->is_SafePoint() || mem->is_MemBar()) {
1286     res = mem->in(TypeFunc::Memory);
1287   } else if (mem->is_Phi()) {
1288     res = mem->in(1);
1289   } else if (mem->is_ShenandoahBarrier()) {
1290     res = mem->in(ShenandoahBarrierNode::Memory);
1291   } else if (mem->is_MergeMem()) {
1292     res = mem->as_MergeMem()->memory_at(alias);
1293   } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
1294     assert(alias = Compile::AliasIdxRaw, "following raw memory can't lead to a barrier");
1295     res = mem->in(MemNode::Memory);
1296   } else if (mem->Opcode() == Op_ShenandoahWBMemProj) {
1297     res = mem->in(ShenandoahWBMemProjNode::WriteBarrier);
1298   } else {
1299 #ifdef ASSERT
1300     mem->dump();
1301 #endif
1302     ShouldNotReachHere();
1303   }
1304   return res;
1305 }
1306 
1307 Node* ShenandoahBarrierNode::no_branches(Node* c, Node* dom, bool allow_one_proj, PhaseIdealLoop* phase) {
1308   Node* iffproj = NULL;
1309   while (c != dom) {
1310     Node* next = phase->idom(c);
1311     assert(next->unique_ctrl_out() == c || c->is_Proj() || c->is_Region(), "multiple control flow out but no proj or region?");
1312     if (c->is_Region()) {
1313       ResourceMark rm;
1314       Unique_Node_List wq;
1315       wq.push(c);
1316       for (uint i = 0; i < wq.size(); i++) {
1317         Node *n = wq.at(i);
1318         if (n == next) {
1319           continue;
1320         }
1321         if (n->is_Region()) {
1322           for (uint j = 1; j < n->req(); j++) {
1323             wq.push(n->in(j));
1324           }
1325         } else {
1326           wq.push(n->in(0));
1327         }
1328       }
1329       for (uint i = 0; i < wq.size(); i++) {
1330         Node *n = wq.at(i);
1331         assert(n->is_CFG(), "");
1332         if (n->is_Multi()) {
1333           for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1334             Node* u = n->fast_out(j);
1335             if (u->is_CFG()) {
1336               if (!wq.member(u) && !u->as_Proj()->is_uncommon_trap_proj(Deoptimization::Reason_none)) {
1337                 return NodeSentinel;
1338               }
1339             }
1340           }
1341         }
1342       }
1343     } else  if (c->is_Proj()) {
1344       if (c->is_IfProj()) {
1345         if (c->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) != NULL) {
1346           // continue;
1347         } else {
1348           if (!allow_one_proj) {
1349             return NodeSentinel;
1350           }
1351           if (iffproj == NULL) {
1352             iffproj = c;
1353           } else {
1354             return NodeSentinel;
1355           }
1356         }
1357       } else if (c->Opcode() == Op_JumpProj) {
1358         return NodeSentinel; // unsupported
1359       } else if (c->Opcode() == Op_CatchProj) {
1360         return NodeSentinel; // unsupported
1361       } else if (c->Opcode() == Op_CProj && next->Opcode() == Op_NeverBranch) {
1362         return NodeSentinel; // unsupported
1363       } else {
1364         assert(next->unique_ctrl_out() == c, "unsupported branch pattern");
1365       }
1366     }
1367     c = next;
1368   }
1369   return iffproj;
1370 }
1371 
1372 bool ShenandoahBarrierNode::build_loop_late_post(PhaseIdealLoop* phase, Node* n) {
1373   if (n->Opcode() == Op_ShenandoahReadBarrier ||
1374       n->Opcode() == Op_ShenandoahWriteBarrier ||
1375       n->Opcode() == Op_ShenandoahWBMemProj) {
1376 
1377     phase->build_loop_late_post_work(n, false);
1378 
1379     if (n->Opcode() == Op_ShenandoahWriteBarrier) {
1380       // The write barrier and its memory proj must have the same
1381       // control otherwise some loop opts could put nodes (Phis) between
1382       // them
1383       Node* proj = n->find_out_with(Op_ShenandoahWBMemProj);
1384       if (proj != NULL) {
1385         phase->set_ctrl_and_loop(proj, phase->get_ctrl(n));
1386       }
1387     }
1388     return true;
1389   }
1390   return false;
1391 }
1392 
1393 bool ShenandoahBarrierNode::sink_node(PhaseIdealLoop* phase, Node* ctrl, Node* n_ctrl) {
1394   ctrl = phase->find_non_split_ctrl(ctrl);
1395   assert(phase->dom_depth(n_ctrl) <= phase->dom_depth(ctrl), "n is later than its clone");
1396   set_req(0, ctrl);
1397   phase->register_new_node(this, ctrl);
1398   return true;
1399 }
1400 
1401 #ifdef ASSERT
1402 void ShenandoahWriteBarrierNode::memory_dominates_all_paths_helper(Node* c, Node* rep_ctrl, Unique_Node_List& controls, PhaseIdealLoop* phase) {
1403   const bool trace = false;
1404   if (trace) { tty->print("X control is"); c->dump(); }
1405 
1406   uint start = controls.size();
1407   controls.push(c);
1408   for (uint i = start; i < controls.size(); i++) {
1409     Node *n = controls.at(i);
1410 
1411     if (trace) { tty->print("X from"); n->dump(); }
1412 
1413     if (n == rep_ctrl) {
1414       continue;
1415     }
1416 
1417     if (n->is_Proj()) {
1418       Node* n_dom = n->in(0);
1419       IdealLoopTree* n_dom_loop = phase->get_loop(n_dom);
1420       if (n->is_IfProj() && n_dom->outcnt() == 2) {
1421         n_dom_loop = phase->get_loop(n_dom->as_If()->proj_out(n->as_Proj()->_con == 0 ? 1 : 0));
1422       }
1423       if (n_dom_loop != phase->ltree_root()) {
1424         Node* tail = n_dom_loop->tail();
1425         if (tail->is_Region()) {
1426           for (uint j = 1; j < tail->req(); j++) {
1427             if (phase->is_dominator(n_dom, tail->in(j)) && !phase->is_dominator(n, tail->in(j))) {
1428               assert(phase->is_dominator(rep_ctrl, tail->in(j)), "why are we here?");
1429               // entering loop from below, mark backedge
1430               if (trace) { tty->print("X pushing backedge"); tail->in(j)->dump(); }
1431               controls.push(tail->in(j));
1432               //assert(n->in(0) == n_dom, "strange flow control");
1433             }
1434           }
1435         } else if (phase->get_loop(n) != n_dom_loop && phase->is_dominator(n_dom, tail)) {
1436           // entering loop from below, mark backedge
1437           if (trace) { tty->print("X pushing backedge"); tail->dump(); }
1438           controls.push(tail);
1439           //assert(n->in(0) == n_dom, "strange flow control");
1440         }
1441       }
1442     }
1443 
1444     if (n->is_Loop()) {
1445       Node* c = n->in(LoopNode::EntryControl);
1446       if (trace) { tty->print("X pushing"); c->dump(); }
1447       controls.push(c);
1448     } else if (n->is_Region()) {
1449       for (uint i = 1; i < n->req(); i++) {
1450         Node* c = n->in(i);
1451         if (trace) { tty->print("X pushing"); c->dump(); }
1452         controls.push(c);
1453       }
1454     } else {
1455       Node* c = n->in(0);
1456       if (trace) { tty->print("X pushing"); c->dump(); }
1457       controls.push(c);
1458     }
1459   }
1460 }
1461 
1462 bool ShenandoahWriteBarrierNode::memory_dominates_all_paths(Node* mem, Node* rep_ctrl, int alias, PhaseIdealLoop* phase) {
1463   const bool trace = false;
1464   if (trace) {
1465     tty->print("XXX mem is"); mem->dump();
1466     tty->print("XXX rep ctrl is"); rep_ctrl->dump();
1467     tty->print_cr("XXX alias is %d", alias);
1468   }
1469   ResourceMark rm;
1470   Unique_Node_List wq;
1471   Unique_Node_List controls;
1472   wq.push(mem);
1473   for (uint next = 0; next < wq.size(); next++) {
1474     Node *nn = wq.at(next);
1475     if (trace) { tty->print("XX from mem"); nn->dump(); }
1476     assert(nn->bottom_type() == Type::MEMORY, "memory only");
1477 
1478     if (nn->is_Phi()) {
1479       Node* r = nn->in(0);
1480       for (DUIterator_Fast jmax, j = r->fast_outs(jmax); j < jmax; j++) {
1481         Node* u = r->fast_out(j);
1482         if (u->is_Phi() && u->bottom_type() == Type::MEMORY && u != nn &&
1483             (u->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(u->adr_type()) == alias)) {
1484           if (trace) { tty->print("XX Next mem (other phi)"); u->dump(); }
1485           wq.push(u);
1486         }
1487       }
1488     }
1489 
1490     for (DUIterator_Fast imax, i = nn->fast_outs(imax); i < imax; i++) {
1491       Node* use = nn->fast_out(i);
1492 
1493       if (trace) { tty->print("XX use %p", use->adr_type()); use->dump(); }
1494       if (use->is_CFG() && use->in(TypeFunc::Memory) == nn) {
1495         Node* c = use->in(0);
1496         if (phase->is_dominator(rep_ctrl, c)) {
1497           memory_dominates_all_paths_helper(c, rep_ctrl, controls, phase);
1498         } else if (use->is_CallStaticJava() && use->as_CallStaticJava()->uncommon_trap_request() != 0 && c->is_Region()) {
1499           Node* region = c;
1500           if (trace) { tty->print("XX unc region"); region->dump(); }
1501           for (uint j = 1; j < region->req(); j++) {
1502             if (phase->is_dominator(rep_ctrl, region->in(j))) {
1503               if (trace) { tty->print("XX unc follows"); region->in(j)->dump(); }
1504               memory_dominates_all_paths_helper(region->in(j), rep_ctrl, controls, phase);
1505             }
1506           }
1507         }
1508         //continue;
1509       } else if (use->is_Phi()) {
1510         assert(use->bottom_type() == Type::MEMORY, "bad phi");
1511         if ((use->adr_type() == TypePtr::BOTTOM) ||
1512             phase->C->get_alias_index(use->adr_type()) == alias) {
1513           for (uint j = 1; j < use->req(); j++) {
1514             if (use->in(j) == nn) {
1515               Node* c = use->in(0)->in(j);
1516               if (phase->is_dominator(rep_ctrl, c)) {
1517                 memory_dominates_all_paths_helper(c, rep_ctrl, controls, phase);
1518               }
1519             }
1520           }
1521         }
1522         //        continue;
1523       }
1524 
1525       if (use->is_MergeMem()) {
1526         if (use->as_MergeMem()->memory_at(alias) == nn) {
1527           if (trace) { tty->print("XX Next mem"); use->dump(); }
1528           // follow the memory edges
1529           wq.push(use);
1530         }
1531       } else if (use->is_Phi()) {
1532         assert(use->bottom_type() == Type::MEMORY, "bad phi");
1533         if ((use->adr_type() == TypePtr::BOTTOM) ||
1534             phase->C->get_alias_index(use->adr_type()) == alias) {
1535           if (trace) { tty->print("XX Next mem"); use->dump(); }
1536           // follow the memory edges
1537           wq.push(use);
1538         }
1539       } else if (use->bottom_type() == Type::MEMORY &&
1540                  (use->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(use->adr_type()) == alias)) {
1541         if (trace) { tty->print("XX Next mem"); use->dump(); }
1542         // follow the memory edges
1543         wq.push(use);
1544       } else if ((use->is_SafePoint() || use->is_MemBar()) &&
1545                  (use->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(use->adr_type()) == alias)) {
1546         for (DUIterator_Fast jmax, j = use->fast_outs(jmax); j < jmax; j++) {
1547           Node* u = use->fast_out(j);
1548           if (u->bottom_type() == Type::MEMORY) {
1549             if (trace) { tty->print("XX Next mem"); u->dump(); }
1550             // follow the memory edges
1551             wq.push(u);
1552           }
1553         }
1554       } else if (use->Opcode() == Op_ShenandoahWriteBarrier && phase->C->get_alias_index(use->adr_type()) == alias) {
1555         Node* m = use->find_out_with(Op_ShenandoahWBMemProj);
1556         if (m != NULL) {
1557           if (trace) { tty->print("XX Next mem"); m->dump(); }
1558           // follow the memory edges
1559           wq.push(m);
1560         }
1561       }
1562     }
1563   }
1564 
1565   if (controls.size() == 0) {
1566     return false;
1567   }
1568 
1569   for (uint i = 0; i < controls.size(); i++) {
1570     Node *n = controls.at(i);
1571 
1572     if (trace) { tty->print("X checking"); n->dump(); }
1573 
1574     if (n->unique_ctrl_out() != NULL) {
1575       continue;
1576     }
1577 
1578     if (n->Opcode() == Op_NeverBranch) {
1579       Node* taken = n->as_Multi()->proj_out(0);
1580       if (!controls.member(taken)) {
1581         if (trace) { tty->print("X not seen"); taken->dump(); }
1582         return false;
1583       }
1584       continue;
1585     }
1586 
1587     for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1588       Node* u = n->fast_out(j);
1589 
1590       if (u->is_CFG()) {
1591         if (!controls.member(u)) {
1592           if (u->is_Proj() && u->as_Proj()->is_uncommon_trap_proj(Deoptimization::Reason_none)) {
1593             if (trace) { tty->print("X not seen but unc"); u->dump(); }
1594           } else {
1595             Node* c = u;
1596             do {
1597               c = c->unique_ctrl_out();
1598             } while (c != NULL && c->is_Region());
1599             if (c != NULL && c->Opcode() == Op_Halt) {
1600               if (trace) { tty->print("X not seen but halt"); c->dump(); }
1601             } else {
1602               if (trace) { tty->print("X not seen"); u->dump(); }
1603               return false;
1604             }
1605           }
1606         } else {
1607           if (trace) { tty->print("X seen"); u->dump(); }
1608         }
1609       }
1610     }
1611   }
1612   return true;
1613 }
1614 #endif
1615 
1616 Node* ShenandoahBarrierNode::dom_mem(Node* mem, Node*& mem_ctrl, Node* n, Node* rep_ctrl, int alias, PhaseIdealLoop* phase) {
1617   ResourceMark rm;
1618   VectorSet wq(Thread::current()->resource_area());
1619   wq.set(mem->_idx);
1620   mem_ctrl = phase->get_ctrl(mem);
1621   while (!is_dominator(mem_ctrl, rep_ctrl, mem, n, phase)) {
1622     mem = next_mem(mem, alias);
1623     if (wq.test_set(mem->_idx)) {
1624       return NULL; // hit an unexpected loop
1625     }
1626     mem_ctrl = phase->ctrl_or_self(mem);
1627   }
1628   if (mem->is_MergeMem()) {
1629     mem = mem->as_MergeMem()->memory_at(alias);
1630     mem_ctrl = phase->ctrl_or_self(mem);
1631   }
1632   return mem;
1633 }
1634 
1635 Node* ShenandoahBarrierNode::dom_mem(Node* mem, Node* ctrl, int alias, Node*& mem_ctrl, PhaseIdealLoop* phase) {
1636   ResourceMark rm;
1637   VectorSet wq(Thread::current()->resource_area());
1638   wq.set(mem->_idx);
1639   mem_ctrl = phase->ctrl_or_self(mem);
1640   while (!phase->is_dominator(mem_ctrl, ctrl) || mem_ctrl == ctrl) {
1641     mem = next_mem(mem, alias);
1642     if (wq.test_set(mem->_idx)) {
1643       return NULL;
1644     }
1645     mem_ctrl = phase->ctrl_or_self(mem);
1646   }
1647   if (mem->is_MergeMem()) {
1648     mem = mem->as_MergeMem()->memory_at(alias);
1649     mem_ctrl = phase->ctrl_or_self(mem);
1650   }
1651   return mem;
1652 }
1653 
1654 static void disconnect_barrier_mem(Node* wb, PhaseIterGVN& igvn) {
1655   Node* mem_in = wb->in(ShenandoahBarrierNode::Memory);
1656   Node* proj = wb->find_out_with(Op_ShenandoahWBMemProj);
1657 
1658   for (DUIterator_Last imin, i = proj->last_outs(imin); i >= imin; ) {
1659     Node* u = proj->last_out(i);
1660     igvn.rehash_node_delayed(u);
1661     int nb = u->replace_edge(proj, mem_in);
1662     assert(nb > 0, "no replacement?");
1663     i -= nb;
1664   }
1665 }
1666 
1667 Node* ShenandoahWriteBarrierNode::move_above_predicates(LoopNode* cl, Node* val_ctrl, PhaseIdealLoop* phase) {
1668   Node* entry = cl->skip_strip_mined(-1)->in(LoopNode::EntryControl);
1669   Node* above_pred = phase->skip_all_loop_predicates(entry);
1670   Node* ctrl = entry;
1671   while (ctrl != above_pred) {
1672     Node* next = ctrl->in(0);
1673     if (!phase->is_dominator(val_ctrl, next)) {
1674       break;
1675     }
1676     ctrl = next;
1677   }
1678   return ctrl;
1679 }
1680 
1681 static MemoryGraphFixer* find_fixer(GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, int alias) {
1682   for (int i = 0; i < memory_graph_fixers.length(); i++) {
1683     if (memory_graph_fixers.at(i)->alias() == alias) {
1684       return memory_graph_fixers.at(i);
1685     }
1686   }
1687   return NULL;
1688 }
1689 
1690 static MemoryGraphFixer* create_fixer(GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, int alias, PhaseIdealLoop* phase, bool include_lsm) {
1691   assert(find_fixer(memory_graph_fixers, alias) == NULL, "none should exist yet");
1692   MemoryGraphFixer* fixer = new MemoryGraphFixer(alias, include_lsm, phase);
1693   memory_graph_fixers.push(fixer);
1694   return fixer;
1695 }
1696 
1697 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) {
1698   assert(cl->is_Loop(), "bad control");
1699   Node* ctrl = move_above_predicates(cl, val_ctrl, phase);
1700   Node* mem_ctrl = NULL;
1701   int alias = phase->C->get_alias_index(adr_type());
1702 
1703   MemoryGraphFixer* fixer = find_fixer(memory_graph_fixers, alias);
1704   if (fixer == NULL) {
1705     fixer = create_fixer(memory_graph_fixers, alias, phase, include_lsm);
1706   }
1707 
1708   Node* proj = find_out_with(Op_ShenandoahWBMemProj);
1709 
1710   fixer->remove(proj);
1711   Node* mem = fixer->find_mem(ctrl, NULL);
1712 
1713   assert(!ShenandoahVerifyOptoBarriers || memory_dominates_all_paths(mem, ctrl, alias, phase), "can't fix the memory graph");
1714 
1715   phase->set_ctrl_and_loop(this, ctrl);
1716   phase->igvn().replace_input_of(this, Control, ctrl);
1717 
1718   disconnect_barrier_mem(this, phase->igvn());
1719 
1720   phase->igvn().replace_input_of(this, Memory, mem);
1721   phase->set_ctrl_and_loop(proj, ctrl);
1722 
1723   fixer->fix_mem(ctrl, ctrl, mem, mem, proj, uses);
1724   assert(proj->outcnt() > 0, "disconnected write barrier");
1725 }
1726 
1727 LoopNode* ShenandoahWriteBarrierNode::try_move_before_pre_loop(Node* c, Node* val_ctrl, PhaseIdealLoop* phase) {
1728   // A write barrier between a pre and main loop can get in the way of
1729   // vectorization. Move it above the pre loop if possible
1730   CountedLoopNode* cl = NULL;
1731   if (c->is_IfFalse() &&
1732       c->in(0)->is_CountedLoopEnd()) {
1733     cl = c->in(0)->as_CountedLoopEnd()->loopnode();
1734   } else if (c->is_IfProj() &&
1735              c->in(0)->is_If() &&
1736              c->in(0)->in(0)->is_IfFalse() &&
1737              c->in(0)->in(0)->in(0)->is_CountedLoopEnd()) {
1738     cl = c->in(0)->in(0)->in(0)->as_CountedLoopEnd()->loopnode();
1739   }
1740   if (cl != NULL &&
1741       cl->is_pre_loop() &&
1742       val_ctrl != cl &&
1743       phase->is_dominator(val_ctrl, cl)) {
1744     return cl;
1745   }
1746   return NULL;
1747 }
1748 
1749 void ShenandoahWriteBarrierNode::try_move_before_loop(GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, PhaseIdealLoop* phase, bool include_lsm, Unique_Node_List& uses) {
1750   Node *n_ctrl = phase->get_ctrl(this);
1751   IdealLoopTree *n_loop = phase->get_loop(n_ctrl);
1752   Node* val = in(ValueIn);
1753   Node* val_ctrl = phase->get_ctrl(val);
1754   if (n_loop != phase->ltree_root() && !n_loop->_irreducible) {
1755     IdealLoopTree *val_loop = phase->get_loop(val_ctrl);
1756     Node* mem = in(Memory);
1757     IdealLoopTree *mem_loop = phase->get_loop(phase->get_ctrl(mem));
1758     if (!n_loop->is_member(val_loop) &&
1759         n_loop->is_member(mem_loop)) {
1760       Node* n_loop_head = n_loop->_head;
1761 
1762       if (n_loop_head->is_Loop()) {
1763         LoopNode* loop = n_loop_head->as_Loop();
1764         if (n_loop_head->is_CountedLoop() && n_loop_head->as_CountedLoop()->is_main_loop()) {
1765           LoopNode* res = try_move_before_pre_loop(n_loop_head->in(LoopNode::EntryControl), val_ctrl, phase);
1766           if (res != NULL) {
1767             loop = res;
1768           }
1769         }
1770 
1771         try_move_before_loop_helper(loop, val_ctrl, memory_graph_fixers, phase, include_lsm, uses);
1772       }
1773     }
1774   }
1775   LoopNode* ctrl = try_move_before_pre_loop(in(0), val_ctrl, phase);
1776   if (ctrl != NULL) {
1777     try_move_before_loop_helper(ctrl, val_ctrl, memory_graph_fixers, phase, include_lsm, uses);
1778   }
1779 }
1780 
1781 Node* ShenandoahWriteBarrierNode::would_subsume(ShenandoahBarrierNode* other, PhaseIdealLoop* phase) {
1782   Node* val = in(ValueIn);
1783   Node* val_ctrl = phase->get_ctrl(val);
1784   Node* other_mem = other->in(Memory);
1785   Node* other_ctrl = phase->get_ctrl(other);
1786   Node* this_ctrl = phase->get_ctrl(this);
1787   IdealLoopTree* this_loop = phase->get_loop(this_ctrl);
1788   IdealLoopTree* other_loop = phase->get_loop(other_ctrl);
1789 
1790   Node* ctrl = phase->dom_lca(other_ctrl, this_ctrl);
1791 
1792   if (ctrl->is_Proj() &&
1793       ctrl->in(0)->is_Call() &&
1794       ctrl->unique_ctrl_out() != NULL &&
1795       ctrl->unique_ctrl_out()->Opcode() == Op_Catch &&
1796       !phase->is_dominator(val_ctrl, ctrl->in(0)->in(0))) {
1797     return NULL;
1798   }
1799 
1800   IdealLoopTree* loop = phase->get_loop(ctrl);
1801 
1802   // We don't want to move a write barrier in a loop
1803   // If the LCA is in a inner loop, try a control out of loop if possible
1804   while (!loop->is_member(this_loop) && (other->Opcode() != Op_ShenandoahWriteBarrier || !loop->is_member(other_loop))) {
1805     ctrl = phase->idom(ctrl);
1806     if (ctrl->is_MultiBranch()) {
1807       ctrl = ctrl->in(0);
1808     }
1809     if (ctrl != val_ctrl && phase->is_dominator(ctrl, val_ctrl)) {
1810       return NULL;
1811     }
1812     loop = phase->get_loop(ctrl);
1813   }
1814 
1815   if (ShenandoahDontIncreaseWBFreq) {
1816     Node* this_iffproj = no_branches(this_ctrl, ctrl, true, phase);
1817     if (other->Opcode() == Op_ShenandoahWriteBarrier) {
1818       Node* other_iffproj = no_branches(other_ctrl, ctrl, true, phase);
1819       if (other_iffproj == NULL || this_iffproj == NULL) {
1820         return ctrl;
1821       } else if (other_iffproj != NodeSentinel && this_iffproj != NodeSentinel &&
1822                  other_iffproj->in(0) == this_iffproj->in(0)) {
1823         return ctrl;
1824       }
1825     } else if (this_iffproj == NULL) {
1826       return ctrl;
1827     }
1828     return NULL;
1829   }
1830 
1831   return ctrl;
1832 }
1833 
1834 void ShenandoahWriteBarrierNode::optimize_before_expansion(PhaseIdealLoop* phase, GrowableArray<MemoryGraphFixer*> memory_graph_fixers, bool include_lsm) {
1835   bool progress = false;
1836   Unique_Node_List uses;
1837   do {
1838     progress = false;
1839     for (int i = 0; i < ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count(); i++) {
1840       ShenandoahWriteBarrierNode* wb = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barrier(i);
1841 
1842       wb->try_move_before_loop(memory_graph_fixers, phase, include_lsm, uses);
1843 
1844       Node* val = wb->in(ValueIn);
1845 
1846       for (DUIterator_Fast jmax, j = val->fast_outs(jmax); j < jmax; j++) {
1847         Node* u = val->fast_out(j);
1848         if (u != wb && u->is_ShenandoahBarrier()) {
1849           Node* rep_ctrl = wb->would_subsume(u->as_ShenandoahBarrier(), phase);
1850 
1851           if (rep_ctrl != NULL) {
1852             Node* other = u;
1853             Node* val_ctrl = phase->get_ctrl(val);
1854             if (rep_ctrl->is_Proj() &&
1855                 rep_ctrl->in(0)->is_Call() &&
1856                 rep_ctrl->unique_ctrl_out() != NULL &&
1857                 rep_ctrl->unique_ctrl_out()->Opcode() == Op_Catch) {
1858               rep_ctrl = rep_ctrl->in(0)->in(0);
1859 
1860               assert(phase->is_dominator(val_ctrl, rep_ctrl), "bad control");
1861             } else {
1862               LoopNode* c = ShenandoahWriteBarrierNode::try_move_before_pre_loop(rep_ctrl, val_ctrl, phase);
1863               if (c != NULL) {
1864                 rep_ctrl = ShenandoahWriteBarrierNode::move_above_predicates(c, val_ctrl, phase);
1865               } else {
1866                 while (rep_ctrl->is_IfProj()) {
1867                   CallStaticJavaNode* unc = rep_ctrl->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
1868                   if (unc != NULL) {
1869                     int req = unc->uncommon_trap_request();
1870                     Deoptimization::DeoptReason trap_reason = Deoptimization::trap_request_reason(req);
1871                     if ((trap_reason == Deoptimization::Reason_loop_limit_check ||
1872                          trap_reason == Deoptimization::Reason_predicate ||
1873                          trap_reason == Deoptimization::Reason_profile_predicate) &&
1874                         phase->is_dominator(val_ctrl, rep_ctrl->in(0)->in(0))) {
1875                       rep_ctrl = rep_ctrl->in(0)->in(0);
1876                       continue;
1877                     }
1878                   }
1879                   break;
1880                 }
1881               }
1882             }
1883 
1884             Node* wb_ctrl = phase->get_ctrl(wb);
1885             Node* other_ctrl = phase->get_ctrl(other);
1886             int alias = phase->C->get_alias_index(wb->adr_type());
1887             MemoryGraphFixer* fixer = find_fixer(memory_graph_fixers, alias);;
1888             if (!is_dominator(wb_ctrl, other_ctrl, wb, other, phase)) {
1889               if (fixer == NULL) {
1890                 fixer = create_fixer(memory_graph_fixers, alias, phase, include_lsm);
1891               }
1892               Node* mem = fixer->find_mem(rep_ctrl, phase->get_ctrl(other) == rep_ctrl ? other : NULL);
1893 
1894               if (mem->has_out_with(Op_Lock) || mem->has_out_with(Op_Unlock)) {
1895                 continue;
1896               }
1897 
1898               Node* wb_proj = wb->find_out_with(Op_ShenandoahWBMemProj);
1899               fixer->remove(wb_proj);
1900               Node* mem_for_ctrl = fixer->find_mem(rep_ctrl, NULL);
1901 
1902               if (wb->in(Memory) != mem) {
1903                 disconnect_barrier_mem(wb, phase->igvn());
1904                 phase->igvn().replace_input_of(wb, Memory, mem);
1905               }
1906               if (rep_ctrl != wb_ctrl) {
1907                 phase->set_ctrl_and_loop(wb, rep_ctrl);
1908                 phase->igvn().replace_input_of(wb, Control, rep_ctrl);
1909                 phase->set_ctrl_and_loop(wb_proj, rep_ctrl);
1910                 progress = true;
1911               }
1912 
1913               fixer->fix_mem(rep_ctrl, rep_ctrl, mem, mem_for_ctrl, wb_proj, uses);
1914 
1915               assert(!ShenandoahVerifyOptoBarriers || ShenandoahWriteBarrierNode::memory_dominates_all_paths(mem, rep_ctrl, alias, phase), "can't fix the memory graph");
1916             }
1917 
1918             if (other->Opcode() == Op_ShenandoahWriteBarrier) {
1919               Node* other_proj = other->find_out_with(Op_ShenandoahWBMemProj);
1920               if (fixer != NULL) {
1921                 fixer->remove(other_proj);
1922               }
1923               phase->igvn().replace_node(other_proj, other->in(Memory));
1924             }
1925             phase->igvn().replace_node(other, wb);
1926             --j; --jmax;
1927           }
1928         }
1929       }
1930     }
1931   } while(progress);
1932 }
1933 
1934 // Some code duplication with PhaseIdealLoop::split_if_with_blocks_pre()
1935 Node* ShenandoahWriteBarrierNode::try_split_thru_phi(PhaseIdealLoop* phase) {
1936   Node *ctrl = phase->get_ctrl(this);
1937   if (ctrl == NULL) {
1938     return this;
1939   }
1940   Node *blk = phase->has_local_phi_input(this);
1941   if (blk == NULL) {
1942     return this;
1943   }
1944 
1945   if (in(0) != blk) {
1946     return this;
1947   }
1948 
1949   int policy = blk->req() >> 2;
1950 
1951   if (blk->is_CountedLoop()) {
1952     IdealLoopTree *lp = phase->get_loop(blk);
1953     if (lp && lp->_rce_candidate) {
1954       return this;
1955     }
1956   }
1957 
1958   if (phase->C->live_nodes() > 35000) {
1959     return this;
1960   }
1961 
1962   uint unique = phase->C->unique();
1963   Node *phi = phase->split_thru_phi(this, blk, policy);
1964   if (phi == NULL) {
1965     return this;
1966   }
1967 
1968   Node* mem_phi = new PhiNode(blk, Type::MEMORY, phase->C->alias_type(adr_type())->adr_type());
1969   for (uint i = 1; i < blk->req(); i++) {
1970     Node* n = phi->in(i);
1971     if (n->Opcode() == Op_ShenandoahWriteBarrier &&
1972         n->_idx >= unique) {
1973       Node* proj = new ShenandoahWBMemProjNode(n);
1974       phase->register_new_node(proj, phase->get_ctrl(n));
1975       mem_phi->init_req(i, proj);
1976     } else {
1977       Node* mem = in(ShenandoahBarrierNode::Memory);
1978       if (mem->is_Phi() && mem->in(0) == blk) {
1979         mem = mem->in(i);
1980       }
1981       mem_phi->init_req(i, mem);
1982     }
1983   }
1984   phase->register_new_node(mem_phi, blk);
1985 
1986 
1987   Node* proj = find_out_with(Op_ShenandoahWBMemProj);
1988   phase->igvn().replace_node(proj, mem_phi);
1989   phase->igvn().replace_node(this, phi);
1990 
1991   return phi;
1992 }
1993 
1994 void ShenandoahReadBarrierNode::try_move(PhaseIdealLoop* phase) {
1995   Node *n_ctrl = phase->get_ctrl(this);
1996   if (n_ctrl == NULL) {
1997     return;
1998   }
1999   Node* mem = in(MemNode::Memory);
2000   int alias = phase->C->get_alias_index(adr_type());
2001   const bool trace = false;
2002 
2003 #ifdef ASSERT
2004   if (trace) { tty->print("Trying to move mem of"); dump(); }
2005 #endif
2006 
2007   Node* new_mem = mem;
2008 
2009   ResourceMark rm;
2010   VectorSet seen(Thread::current()->resource_area());
2011   Node_List phis;
2012 
2013   for (;;) {
2014 #ifdef ASSERT
2015     if (trace) { tty->print("Looking for dominator from"); mem->dump(); }
2016 #endif
2017     if (mem->is_Proj() && mem->in(0)->is_Start()) {
2018       if (new_mem != in(MemNode::Memory)) {
2019 #ifdef ASSERT
2020         if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2021 #endif
2022         phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2023       }
2024       return;
2025     }
2026 
2027     Node* candidate = mem;
2028     do {
2029       if (!is_independent(mem)) {
2030         if (trace) { tty->print_cr("Not independent"); }
2031         if (new_mem != in(MemNode::Memory)) {
2032 #ifdef ASSERT
2033           if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2034 #endif
2035           phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2036         }
2037         return;
2038       }
2039       if (seen.test_set(mem->_idx)) {
2040         if (trace) { tty->print_cr("Already seen"); }
2041         ShouldNotReachHere();
2042         // Strange graph
2043         if (new_mem != in(MemNode::Memory)) {
2044 #ifdef ASSERT
2045           if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2046 #endif
2047           phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2048         }
2049         return;
2050       }
2051       if (mem->is_Phi()) {
2052         phis.push(mem);
2053       }
2054       mem = next_mem(mem, alias);
2055       if (mem->bottom_type() == Type::MEMORY) {
2056         candidate = mem;
2057       }
2058       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");
2059 #ifdef ASSERT
2060       if (trace) { tty->print("Next mem is"); mem->dump(); }
2061 #endif
2062     } while (mem->bottom_type() != Type::MEMORY || !phase->is_dominator(phase->ctrl_or_self(mem), n_ctrl));
2063 
2064     assert(mem->bottom_type() == Type::MEMORY, "bad mem");
2065 
2066     bool not_dom = false;
2067     for (uint i = 0; i < phis.size() && !not_dom; i++) {
2068       Node* nn = phis.at(i);
2069 
2070 #ifdef ASSERT
2071       if (trace) { tty->print("Looking from phi"); nn->dump(); }
2072 #endif
2073       assert(nn->is_Phi(), "phis only");
2074       for (uint j = 2; j < nn->req() && !not_dom; j++) {
2075         Node* m = nn->in(j);
2076 #ifdef ASSERT
2077         if (trace) { tty->print("Input %d is", j); m->dump(); }
2078 #endif
2079         while (m != mem && !seen.test_set(m->_idx)) {
2080           if (is_dominator(phase->ctrl_or_self(m), phase->ctrl_or_self(mem), m, mem, phase)) {
2081             not_dom = true;
2082             // Scheduling anomaly
2083 #ifdef ASSERT
2084             if (trace) { tty->print("Giving up"); m->dump(); }
2085 #endif
2086             break;
2087           }
2088           if (!is_independent(m)) {
2089             if (trace) { tty->print_cr("Not independent"); }
2090             if (new_mem != in(MemNode::Memory)) {
2091 #ifdef ASSERT
2092               if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); dump(); }
2093 #endif
2094               phase->igvn().replace_input_of(this, MemNode::Memory, new_mem);
2095             }
2096             return;
2097           }
2098           if (m->is_Phi()) {
2099             phis.push(m);
2100           }
2101           m = next_mem(m, alias);
2102 #ifdef ASSERT
2103           if (trace) { tty->print("Next mem is"); m->dump(); }
2104 #endif
2105         }
2106       }
2107     }
2108     if (!not_dom) {
2109       new_mem = mem;
2110       phis.clear();
2111     } else {
2112       seen.Clear();
2113     }
2114   }
2115 }
2116 
2117 CallStaticJavaNode* ShenandoahWriteBarrierNode::pin_and_expand_null_check(PhaseIterGVN& igvn) {
2118   Node* val = in(ValueIn);
2119 
2120   const Type* val_t = igvn.type(val);
2121 
2122   if (val_t->meet(TypePtr::NULL_PTR) != val_t &&
2123       val->Opcode() == Op_CastPP &&
2124       val->in(0) != NULL &&
2125       val->in(0)->Opcode() == Op_IfTrue &&
2126       val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
2127       val->in(0)->in(0)->is_If() &&
2128       val->in(0)->in(0)->in(1)->Opcode() == Op_Bool &&
2129       val->in(0)->in(0)->in(1)->as_Bool()->_test._test == BoolTest::ne &&
2130       val->in(0)->in(0)->in(1)->in(1)->Opcode() == Op_CmpP &&
2131       val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1) &&
2132       val->in(0)->in(0)->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
2133     assert(val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1), "");
2134     CallStaticJavaNode* unc = val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
2135     return unc;
2136   }
2137   return NULL;
2138 }
2139 
2140 void ShenandoahWriteBarrierNode::pin_and_expand_move_barrier(PhaseIdealLoop* phase, GrowableArray<MemoryGraphFixer*>& memory_graph_fixers, Unique_Node_List& uses) {
2141   Node* unc = pin_and_expand_null_check(phase->igvn());
2142   Node* val = in(ValueIn);
2143 
2144   if (unc != NULL) {
2145     Node* ctrl = phase->get_ctrl(this);
2146     Node* unc_ctrl = val->in(0);
2147 
2148     // Don't move write barrier in a loop
2149     IdealLoopTree* loop = phase->get_loop(ctrl);
2150     IdealLoopTree* unc_loop = phase->get_loop(unc_ctrl);
2151 
2152     if (!unc_loop->is_member(loop)) {
2153       return;
2154     }
2155 
2156     Node* branch = no_branches(ctrl, unc_ctrl, false, phase);
2157     assert(branch == NULL || branch == NodeSentinel, "was not looking for a branch");
2158     if (branch == NodeSentinel) {
2159       return;
2160     }
2161 
2162     RegionNode* r = new RegionNode(3);
2163     IfNode* iff = unc_ctrl->in(0)->as_If();
2164 
2165     Node* ctrl_use = unc_ctrl->unique_ctrl_out();
2166     Node* unc_ctrl_clone = unc_ctrl->clone();
2167     phase->register_control(unc_ctrl_clone, loop, iff);
2168     Node* c = unc_ctrl_clone;
2169     Node* new_cast = clone_null_check(c, val, unc_ctrl_clone, phase);
2170     r->init_req(1, new_cast->in(0)->in(0)->as_If()->proj_out(0));
2171 
2172     phase->igvn().replace_input_of(unc_ctrl, 0, c->in(0));
2173     phase->set_idom(unc_ctrl, c->in(0), phase->dom_depth(unc_ctrl));
2174     phase->lazy_replace(c, unc_ctrl);
2175     c = NULL;;
2176     phase->igvn().replace_input_of(val, 0, unc_ctrl_clone);
2177     phase->set_ctrl(val, unc_ctrl_clone);
2178 
2179     IfNode* new_iff = new_cast->in(0)->in(0)->as_If();
2180     fix_null_check(unc, unc_ctrl_clone, r, uses, phase);
2181     Node* iff_proj = iff->proj_out(0);
2182     r->init_req(2, iff_proj);
2183     phase->register_control(r, phase->ltree_root(), iff);
2184 
2185     Node* new_bol = new_iff->in(1)->clone();
2186     Node* new_cmp = new_bol->in(1)->clone();
2187     assert(new_cmp->Opcode() == Op_CmpP, "broken");
2188     assert(new_cmp->in(1) == val->in(1), "broken");
2189     new_bol->set_req(1, new_cmp);
2190     new_cmp->set_req(1, this);
2191     phase->register_new_node(new_bol, new_iff->in(0));
2192     phase->register_new_node(new_cmp, new_iff->in(0));
2193     phase->igvn().replace_input_of(new_iff, 1, new_bol);
2194     phase->igvn().replace_input_of(new_cast, 1, this);
2195 
2196     for (DUIterator_Fast imax, i = this->fast_outs(imax); i < imax; i++) {
2197       Node* u = this->fast_out(i);
2198       if (u == new_cast || u->Opcode() == Op_ShenandoahWBMemProj || u == new_cmp) {
2199         continue;
2200       }
2201       phase->igvn().rehash_node_delayed(u);
2202       int nb = u->replace_edge(this, new_cast);
2203       assert(nb > 0, "no update?");
2204       --i; imax -= nb;
2205     }
2206 
2207     for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
2208       Node* u = val->fast_out(i);
2209       if (u == this) {
2210         continue;
2211       }
2212       phase->igvn().rehash_node_delayed(u);
2213       int nb = u->replace_edge(val, new_cast);
2214       assert(nb > 0, "no update?");
2215       --i; imax -= nb;
2216     }
2217 
2218     Node* new_ctrl = unc_ctrl_clone;
2219 
2220     int alias = phase->C->get_alias_index(adr_type());
2221     MemoryGraphFixer* fixer = find_fixer(memory_graph_fixers, alias);
2222     if (fixer == NULL) {
2223       fixer = create_fixer(memory_graph_fixers, alias, phase, true);
2224     }
2225 
2226     Node* proj = find_out_with(Op_ShenandoahWBMemProj);
2227     fixer->remove(proj);
2228     Node* mem = fixer->find_mem(new_ctrl, NULL);
2229 
2230     if (in(Memory) != mem) {
2231       disconnect_barrier_mem(this, phase->igvn());
2232       phase->igvn().replace_input_of(this, Memory, mem);
2233     }
2234 
2235     phase->set_ctrl_and_loop(this, new_ctrl);
2236     phase->igvn().replace_input_of(this, Control, new_ctrl);
2237     phase->set_ctrl_and_loop(proj, new_ctrl);
2238 
2239     fixer->fix_mem(new_ctrl, new_ctrl, mem, mem, proj, uses);
2240   }
2241 }
2242 
2243 void ShenandoahWriteBarrierNode::pin_and_expand_helper(PhaseIdealLoop* phase) {
2244   Node* val = in(ValueIn);
2245   CallStaticJavaNode* unc = pin_and_expand_null_check(phase->igvn());
2246   Node* rep = this;
2247   Node* ctrl = phase->get_ctrl(this);
2248   if (unc != NULL && val->in(0) == ctrl) {
2249     Node* unc_ctrl = val->in(0);
2250     IfNode* other_iff = unc_ctrl->unique_ctrl_out()->as_If();
2251     ProjNode* other_unc_ctrl = other_iff->proj_out(1);
2252     Node* cast = NULL;
2253     for (DUIterator_Fast imax, i = other_unc_ctrl->fast_outs(imax); i < imax && cast == NULL; i++) {
2254       Node* u = other_unc_ctrl->fast_out(i);
2255       if (u->Opcode() == Op_CastPP && u->in(1) == this) {
2256         cast = u;
2257       }
2258     }
2259     assert(other_unc_ctrl->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) == unc, "broken");
2260     rep = cast;
2261   }
2262 
2263   // Replace all uses of barrier's input that are dominated by ctrl
2264   // with the value returned by the barrier: no need to keep both
2265   // live.
2266   for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
2267     Node* u = val->fast_out(i);
2268     if (u != this) {
2269       if (u->is_Phi()) {
2270         int nb = 0;
2271         for (uint j = 1; j < u->req(); j++) {
2272           if (u->in(j) == val) {
2273             Node* c = u->in(0)->in(j);
2274             if (phase->is_dominator(ctrl, c)) {
2275               phase->igvn().replace_input_of(u, j, rep);
2276               nb++;
2277             }
2278           }
2279         }
2280         if (nb > 0) {
2281           imax -= nb;
2282           --i;
2283         }
2284       } else {
2285         Node* c = phase->ctrl_or_self(u);
2286         if (is_dominator(ctrl, c, this, u, phase)) {
2287           phase->igvn().rehash_node_delayed(u);
2288           int nb = u->replace_edge(val, rep);
2289           assert(nb > 0, "no update?");
2290           --i, imax -= nb;
2291         }
2292       }
2293     }
2294   }
2295 }
2296 
2297 Node* ShenandoahWriteBarrierNode::find_bottom_mem(Node* ctrl, PhaseIdealLoop* phase) {
2298   Node* mem = NULL;
2299   Node* c = ctrl;
2300   do {
2301     if (c->is_Region()) {
2302       Node* phi_bottom = NULL;
2303       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax && mem == NULL; i++) {
2304         Node* u = c->fast_out(i);
2305         if (u->is_Phi() && u->bottom_type() == Type::MEMORY) {
2306           if (u->adr_type() == TypePtr::BOTTOM) {
2307             mem = u;
2308           }
2309         }
2310       }
2311     } else {
2312       if (c->is_Call() && c->as_Call()->adr_type() != NULL) {
2313         CallProjections projs;
2314         c->as_Call()->extract_projections(&projs, true, false);
2315         if (projs.fallthrough_memproj != NULL) {
2316           if (projs.fallthrough_memproj->adr_type() == TypePtr::BOTTOM) {
2317             if (projs.catchall_memproj == NULL) {
2318               mem = projs.fallthrough_memproj;
2319             } else {
2320               if (phase->is_dominator(projs.fallthrough_catchproj, ctrl)) {
2321                 mem = projs.fallthrough_memproj;
2322               } else {
2323                 assert(phase->is_dominator(projs.catchall_catchproj, ctrl), "one proj must dominate barrier");
2324                 mem = projs.catchall_memproj;
2325               }
2326             }
2327           }
2328         } else {
2329           Node* proj = c->as_Call()->proj_out(TypeFunc::Memory);
2330           if (proj != NULL &&
2331               proj->adr_type() == TypePtr::BOTTOM) {
2332             mem = proj;
2333           }
2334         }
2335       } else {
2336         for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
2337           Node* u = c->fast_out(i);
2338           if (u->is_Proj() &&
2339               u->bottom_type() == Type::MEMORY &&
2340               u->adr_type() == TypePtr::BOTTOM) {
2341               assert(c->is_SafePoint() || c->is_MemBar() || c->is_Start(), "");
2342               assert(mem == NULL, "only one proj");
2343               mem = u;
2344           }
2345         }
2346         assert(!c->is_Call() || c->as_Call()->adr_type() != NULL || mem == NULL, "no mem projection expected");
2347       }
2348     }
2349     c = phase->idom(c);
2350   } while (mem == NULL);
2351   return mem;
2352 }
2353 
2354 void ShenandoahWriteBarrierNode::follow_barrier_uses(Node* n, Node* ctrl, Unique_Node_List& uses, PhaseIdealLoop* phase) {
2355   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2356     Node* u = n->fast_out(i);
2357     if (!u->is_CFG() && phase->get_ctrl(u) == ctrl && (!u->is_Phi() || !u->in(0)->is_Loop() || u->in(LoopNode::LoopBackControl) != n)) {
2358       uses.push(u);
2359     }
2360   }
2361 }
2362 
2363 static void hide_strip_mined_loop(OuterStripMinedLoopNode* outer, CountedLoopNode* inner, PhaseIdealLoop* phase) {
2364   OuterStripMinedLoopEndNode* le = inner->outer_loop_end();
2365   Node* new_outer = new LoopNode(outer->in(LoopNode::EntryControl), outer->in(LoopNode::LoopBackControl));
2366   phase->register_control(new_outer, phase->get_loop(outer), outer->in(LoopNode::EntryControl));
2367   Node* new_le = new IfNode(le->in(0), le->in(1), le->_prob, le->_fcnt);
2368   phase->register_control(new_le, phase->get_loop(le), le->in(0));
2369   phase->lazy_replace(outer, new_outer);
2370   phase->lazy_replace(le, new_le);
2371   inner->clear_strip_mined();
2372 }
2373 
2374 void ShenandoahWriteBarrierNode::test_heap_stable(Node*& ctrl, Node* raw_mem, Node*& heap_stable_ctrl,
2375                                                   PhaseIdealLoop* phase) {
2376   IdealLoopTree* loop = phase->get_loop(ctrl);
2377   Node* thread = new ThreadLocalNode();
2378   phase->register_new_node(thread, ctrl);
2379   Node* offset = phase->igvn().MakeConX(in_bytes(ShenandoahThreadLocalData::gc_state_offset()));
2380   phase->set_ctrl(offset, phase->C->root());
2381   Node* gc_state_addr = new AddPNode(phase->C->top(), thread, offset);
2382   phase->register_new_node(gc_state_addr, ctrl);
2383   uint gc_state_idx = Compile::AliasIdxRaw;
2384   const TypePtr* gc_state_adr_type = NULL; // debug-mode-only argument
2385   debug_only(gc_state_adr_type = phase->C->get_adr_type(gc_state_idx));
2386 
2387   Node* gc_state = new LoadBNode(ctrl, raw_mem, gc_state_addr, gc_state_adr_type, TypeInt::BYTE, MemNode::unordered);
2388   phase->register_new_node(gc_state, ctrl);
2389   Node* heap_stable_and = new AndINode(gc_state, phase->igvn().intcon(ShenandoahHeap::HAS_FORWARDED));
2390   phase->register_new_node(heap_stable_and, ctrl);
2391   Node* heap_stable_cmp = new CmpINode(heap_stable_and, phase->igvn().zerocon(T_INT));
2392   phase->register_new_node(heap_stable_cmp, ctrl);
2393   Node* heap_stable_test = new BoolNode(heap_stable_cmp, BoolTest::ne);
2394   phase->register_new_node(heap_stable_test, ctrl);
2395   IfNode* heap_stable_iff = new IfNode(ctrl, heap_stable_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
2396   phase->register_control(heap_stable_iff, loop, ctrl);
2397 
2398   heap_stable_ctrl = new IfFalseNode(heap_stable_iff);
2399   phase->register_control(heap_stable_ctrl, loop, heap_stable_iff);
2400   ctrl = new IfTrueNode(heap_stable_iff);
2401   phase->register_control(ctrl, loop, heap_stable_iff);
2402 
2403   assert(is_heap_stable_test(heap_stable_iff), "Should match the shape");
2404 }
2405 
2406 void ShenandoahWriteBarrierNode::test_null(Node*& ctrl, Node* val, Node*& null_ctrl, PhaseIdealLoop* phase) {
2407   const Type* val_t = phase->igvn().type(val);
2408   if (val_t->meet(TypePtr::NULL_PTR) == val_t) {
2409     IdealLoopTree* loop = phase->get_loop(ctrl);
2410     Node* null_cmp = new CmpPNode(val, phase->igvn().zerocon(T_OBJECT));
2411     phase->register_new_node(null_cmp, ctrl);
2412     Node* null_test = new BoolNode(null_cmp, BoolTest::ne);
2413     phase->register_new_node(null_test, ctrl);
2414     IfNode* null_iff = new IfNode(ctrl, null_test, PROB_LIKELY(0.999), COUNT_UNKNOWN);
2415     phase->register_control(null_iff, loop, ctrl);
2416     ctrl = new IfTrueNode(null_iff);
2417     phase->register_control(ctrl, loop, null_iff);
2418     null_ctrl = new IfFalseNode(null_iff);
2419     phase->register_control(null_ctrl, loop, null_iff);
2420   }
2421 }
2422 
2423 Node* ShenandoahWriteBarrierNode::clone_null_check(Node*& c, Node* val, Node* unc_ctrl, PhaseIdealLoop* phase) {
2424   IdealLoopTree *loop = phase->get_loop(c);
2425   Node* iff = unc_ctrl->in(0);
2426   assert(iff->is_If(), "broken");
2427   Node* new_iff = iff->clone();
2428   new_iff->set_req(0, c);
2429   phase->register_control(new_iff, loop, c);
2430   Node* iffalse = new IfFalseNode(new_iff->as_If());
2431   phase->register_control(iffalse, loop, new_iff);
2432   Node* iftrue = new IfTrueNode(new_iff->as_If());
2433   phase->register_control(iftrue, loop, new_iff);
2434   c = iftrue;
2435   const Type *t = phase->igvn().type(val);
2436   assert(val->Opcode() == Op_CastPP, "expect cast to non null here");
2437   Node* uncasted_val = val->in(1);
2438   val = new CastPPNode(uncasted_val, t);
2439   val->init_req(0, c);
2440   phase->register_new_node(val, c);
2441   return val;
2442 }
2443 
2444 void ShenandoahWriteBarrierNode::fix_null_check(Node* unc, Node* unc_ctrl, Node* new_unc_ctrl,
2445                                                 Unique_Node_List& uses, PhaseIdealLoop* phase) {
2446   IfNode* iff = unc_ctrl->in(0)->as_If();
2447   Node* proj = iff->proj_out(0);
2448   assert(proj != unc_ctrl, "bad projection");
2449   Node* use = proj->unique_ctrl_out();
2450 
2451   assert(use == unc || use->is_Region(), "what else?");
2452 
2453   uses.clear();
2454   if (use == unc) {
2455     phase->set_idom(use, new_unc_ctrl, phase->dom_depth(use));
2456     for (uint i = 1; i < unc->req(); i++) {
2457       Node* n = unc->in(i);
2458       if (phase->has_ctrl(n) && phase->get_ctrl(n) == proj) {
2459         uses.push(n);
2460       }
2461     }
2462   } else {
2463     assert(use->is_Region(), "what else?");
2464     uint idx = 1;
2465     for (; use->in(idx) != proj; idx++);
2466     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2467       Node* u = use->fast_out(i);
2468       if (u->is_Phi() && phase->get_ctrl(u->in(idx)) == proj) {
2469         uses.push(u->in(idx));
2470       }
2471     }
2472   }
2473   for(uint next = 0; next < uses.size(); next++ ) {
2474     Node *n = uses.at(next);
2475     assert(phase->get_ctrl(n) == proj, "bad control");
2476     phase->set_ctrl_and_loop(n, new_unc_ctrl);
2477     if (n->in(0) == proj) {
2478       phase->igvn().replace_input_of(n, 0, new_unc_ctrl);
2479     }
2480     for (uint i = 0; i < n->req(); i++) {
2481       Node* m = n->in(i);
2482       if (m != NULL && phase->has_ctrl(m) && phase->get_ctrl(m) == proj) {
2483         uses.push(m);
2484       }
2485     }
2486   }
2487 
2488   phase->igvn().rehash_node_delayed(use);
2489   int nb = use->replace_edge(proj, new_unc_ctrl);
2490   assert(nb == 1, "only use expected");
2491 }
2492 
2493 void ShenandoahWriteBarrierNode::in_cset_fast_test(Node*& ctrl, Node*& not_cset_ctrl, Node* val, Node* raw_mem, PhaseIdealLoop* phase) {
2494   IdealLoopTree *loop = phase->get_loop(ctrl);
2495   Node* raw_rbtrue = new CastP2XNode(ctrl, val);
2496   phase->register_new_node(raw_rbtrue, ctrl);
2497   Node* cset_offset = new URShiftXNode(raw_rbtrue, phase->igvn().intcon(ShenandoahHeapRegion::region_size_bytes_shift_jint()));
2498   phase->register_new_node(cset_offset, ctrl);
2499   Node* in_cset_fast_test_base_addr = phase->igvn().makecon(TypeRawPtr::make(ShenandoahHeap::in_cset_fast_test_addr()));
2500   phase->set_ctrl(in_cset_fast_test_base_addr, phase->C->root());
2501   Node* in_cset_fast_test_adr = new AddPNode(phase->C->top(), in_cset_fast_test_base_addr, cset_offset);
2502   phase->register_new_node(in_cset_fast_test_adr, ctrl);
2503   uint in_cset_fast_test_idx = Compile::AliasIdxRaw;
2504   const TypePtr* in_cset_fast_test_adr_type = NULL; // debug-mode-only argument
2505   debug_only(in_cset_fast_test_adr_type = phase->C->get_adr_type(in_cset_fast_test_idx));
2506   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);
2507   phase->register_new_node(in_cset_fast_test_load, ctrl);
2508   Node* in_cset_fast_test_cmp = new CmpINode(in_cset_fast_test_load, phase->igvn().zerocon(T_INT));
2509   phase->register_new_node(in_cset_fast_test_cmp, ctrl);
2510   Node* in_cset_fast_test_test = new BoolNode(in_cset_fast_test_cmp, BoolTest::eq);
2511   phase->register_new_node(in_cset_fast_test_test, ctrl);
2512   IfNode* in_cset_fast_test_iff = new IfNode(ctrl, in_cset_fast_test_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
2513   phase->register_control(in_cset_fast_test_iff, loop, ctrl);
2514 
2515   not_cset_ctrl = new IfTrueNode(in_cset_fast_test_iff);
2516   phase->register_control(not_cset_ctrl, loop, in_cset_fast_test_iff);
2517 
2518   ctrl = new IfFalseNode(in_cset_fast_test_iff);
2519   phase->register_control(ctrl, loop, in_cset_fast_test_iff);
2520 }
2521 
2522 void ShenandoahWriteBarrierNode::call_wb_stub(Node*& ctrl, Node*& val, Node*& result_mem,
2523                                               Node* raw_mem, Node* wb_mem,
2524                                               int alias,
2525                                               PhaseIdealLoop* phase) {
2526   IdealLoopTree*loop = phase->get_loop(ctrl);
2527   const TypePtr* obj_type = phase->igvn().type(val)->is_oopptr()->cast_to_nonconst();
2528 
2529   // The slow path stub consumes and produces raw memory in addition
2530   // to the existing memory edges
2531   Node* base = find_bottom_mem(ctrl, phase);
2532 
2533   MergeMemNode* mm = MergeMemNode::make(base);
2534   mm->set_memory_at(alias, wb_mem);
2535   mm->set_memory_at(Compile::AliasIdxRaw, raw_mem);
2536   phase->register_new_node(mm, ctrl);
2537 
2538   Node* call = new CallLeafNode(ShenandoahBarrierSetC2::shenandoah_write_barrier_Type(), CAST_FROM_FN_PTR(address, ShenandoahRuntime::write_barrier_JRT), "shenandoah_write_barrier", TypeRawPtr::BOTTOM);
2539   call->init_req(TypeFunc::Control, ctrl);
2540   call->init_req(TypeFunc::I_O, phase->C->top());
2541   call->init_req(TypeFunc::Memory, mm);
2542   call->init_req(TypeFunc::FramePtr, phase->C->top());
2543   call->init_req(TypeFunc::ReturnAdr, phase->C->top());
2544   call->init_req(TypeFunc::Parms, val);
2545   phase->register_control(call, loop, ctrl);
2546   ctrl = new ProjNode(call, TypeFunc::Control);
2547   phase->register_control(ctrl, loop, call);
2548   result_mem = new ProjNode(call, TypeFunc::Memory);
2549   phase->register_new_node(result_mem, call);
2550   val = new ProjNode(call, TypeFunc::Parms);
2551   phase->register_new_node(val, call);
2552   val = new CheckCastPPNode(ctrl, val, obj_type);
2553   phase->register_new_node(val, ctrl);
2554 }
2555 
2556 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) {
2557   Node* ctrl = phase->get_ctrl(barrier);
2558   Node* init_raw_mem = fixer.find_mem(ctrl, barrier);
2559 
2560   // Update the control of all nodes that should be after the
2561   // barrier control flow
2562   uses.clear();
2563   // Every node that is control dependent on the barrier's input
2564   // control will be after the expanded barrier. The raw memory (if
2565   // its memory is control dependent on the barrier's input control)
2566   // must stay above the barrier.
2567   uses_to_ignore.clear();
2568   if (phase->has_ctrl(init_raw_mem) && phase->get_ctrl(init_raw_mem) == ctrl && !init_raw_mem->is_Phi()) {
2569     uses_to_ignore.push(init_raw_mem);
2570   }
2571   for (uint next = 0; next < uses_to_ignore.size(); next++) {
2572     Node *n = uses_to_ignore.at(next);
2573     for (uint i = 0; i < n->req(); i++) {
2574       Node* in = n->in(i);
2575       if (in != NULL && phase->has_ctrl(in) && phase->get_ctrl(in) == ctrl) {
2576         uses_to_ignore.push(in);
2577       }
2578     }
2579   }
2580   for (DUIterator_Fast imax, i = ctrl->fast_outs(imax); i < imax; i++) {
2581     Node* u = ctrl->fast_out(i);
2582     if (u->_idx < last &&
2583         u != barrier &&
2584         !uses_to_ignore.member(u) &&
2585         (u->in(0) != ctrl || (!u->is_Region() && !u->is_Phi())) &&
2586         (ctrl->Opcode() != Op_CatchProj || u->Opcode() != Op_CreateEx)) {
2587       Node* old_c = phase->ctrl_or_self(u);
2588       Node* c = old_c;
2589       if (c != ctrl ||
2590           is_dominator_same_ctrl(old_c, barrier, u, phase) ||
2591           ShenandoahBarrierSetC2::is_shenandoah_state_load(u)) {
2592         phase->igvn().rehash_node_delayed(u);
2593         int nb = u->replace_edge(ctrl, region);
2594         if (u->is_CFG()) {
2595           if (phase->idom(u) == ctrl) {
2596             phase->set_idom(u, region, phase->dom_depth(region));
2597           }
2598         } else if (phase->get_ctrl(u) == ctrl) {
2599           assert(u != init_raw_mem, "should leave input raw mem above the barrier");
2600           uses.push(u);
2601         }
2602         assert(nb == 1, "more than 1 ctrl input?");
2603         --i, imax -= nb;
2604       }
2605     }
2606   }
2607 }
2608 
2609 void ShenandoahWriteBarrierNode::pin_and_expand(PhaseIdealLoop* phase) {
2610   Node_List enqueue_barriers;
2611   if (ShenandoahStoreValEnqueueBarrier) {
2612     Unique_Node_List wq;
2613     wq.push(phase->C->root());
2614     for (uint i = 0; i < wq.size(); i++) {
2615       Node* n = wq.at(i);
2616       if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
2617         enqueue_barriers.push(n);
2618       }
2619       for (uint i = 0; i < n->req(); i++) {
2620         Node* in = n->in(i);
2621         if (in != NULL) {
2622           wq.push(in);
2623         }
2624       }
2625     }
2626   }
2627 
2628   const bool trace = false;
2629 
2630   // Collect raw memory state at CFG points in the entire graph and
2631   // record it in memory_nodes. Optimize the raw memory graph in the
2632   // process. Optimizing the memory graph also makes the memory graph
2633   // simpler.
2634   GrowableArray<MemoryGraphFixer*> memory_graph_fixers;
2635 
2636   // Let's try to common write barriers again
2637   optimize_before_expansion(phase, memory_graph_fixers, true);
2638 
2639   Unique_Node_List uses;
2640   for (int i = 0; i < ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count(); i++) {
2641     ShenandoahWriteBarrierNode* wb = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barrier(i);
2642     Node* ctrl = phase->get_ctrl(wb);
2643 
2644     Node* val = wb->in(ValueIn);
2645     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
2646       assert(is_dominator(phase->get_ctrl(val), ctrl->in(0)->in(0), val, ctrl->in(0), phase), "can't move");
2647       phase->set_ctrl(wb, ctrl->in(0)->in(0));
2648     } else if (ctrl->is_CallRuntime()) {
2649       assert(is_dominator(phase->get_ctrl(val), ctrl->in(0), val, ctrl, phase), "can't move");
2650       phase->set_ctrl(wb, ctrl->in(0));
2651     }
2652 
2653     assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "only for write barriers");
2654     // Look for a null check that dominates this barrier and move the
2655     // barrier right after the null check to enable implicit null
2656     // checks
2657     wb->pin_and_expand_move_barrier(phase, memory_graph_fixers, uses);
2658 
2659     wb->pin_and_expand_helper(phase);
2660   }
2661 
2662   MemoryGraphFixer fixer(Compile::AliasIdxRaw, true, phase);
2663   Unique_Node_List uses_to_ignore;
2664   Unique_Node_List outer_lsms;
2665   for (uint i = 0; i < enqueue_barriers.size(); i++) {
2666     Node* barrier = enqueue_barriers.at(i);
2667     Node* pre_val = barrier->in(1);
2668 
2669     if (phase->igvn().type(pre_val)->higher_equal(TypePtr::NULL_PTR)) {
2670       ShouldNotReachHere();
2671       continue;
2672     }
2673 
2674     Node* ctrl = phase->get_ctrl(barrier);
2675 
2676     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
2677       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0)->in(0), pre_val, ctrl->in(0), phase), "can't move");
2678       ctrl = ctrl->in(0)->in(0);
2679       phase->set_ctrl(barrier, ctrl);
2680     } else if (ctrl->is_CallRuntime()) {
2681       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0), pre_val, ctrl, phase), "can't move");
2682       ctrl = ctrl->in(0);
2683       phase->set_ctrl(barrier, ctrl);
2684     }
2685 
2686     Node* init_ctrl = ctrl;
2687     IdealLoopTree* loop = phase->get_loop(ctrl);
2688     if (loop->_head->is_OuterStripMinedLoop()) {
2689       outer_lsms.push(loop->_head);
2690     }
2691     Node* raw_mem = fixer.find_mem(ctrl, barrier);
2692     Node* init_raw_mem = raw_mem;
2693     Node* raw_mem_for_ctrl = fixer.find_mem(ctrl, NULL);
2694     Node* heap_stable_ctrl = NULL;
2695     Node* null_ctrl = NULL;
2696     uint last = phase->C->unique();
2697 
2698     enum { _heap_stable = 1, _heap_unstable, PATH_LIMIT };
2699     Node* region = new RegionNode(PATH_LIMIT);
2700     Node* phi = PhiNode::make(region, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
2701 
2702     enum { _fast_path = 1, _slow_path, _null_path, PATH_LIMIT2 };
2703     Node* region2 = new RegionNode(PATH_LIMIT2);
2704     Node* phi2 = PhiNode::make(region2, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
2705 
2706     // Stable path.
2707     test_heap_stable(ctrl, raw_mem, heap_stable_ctrl, phase);
2708     region->init_req(_heap_stable, heap_stable_ctrl);
2709     phi->init_req(_heap_stable, raw_mem);
2710 
2711     // Null path
2712     Node* reg2_ctrl = NULL;
2713     test_null(ctrl, pre_val, null_ctrl, phase);
2714     if (null_ctrl != NULL) {
2715       reg2_ctrl = null_ctrl->in(0);
2716       region2->init_req(_null_path, null_ctrl);
2717       phi2->init_req(_null_path, raw_mem);
2718     } else {
2719       region2->del_req(_null_path);
2720       phi2->del_req(_null_path);
2721     }
2722 
2723     const int index_offset = in_bytes(ShenandoahThreadLocalData::satb_mark_queue_index_offset());
2724     const int buffer_offset = in_bytes(ShenandoahThreadLocalData::satb_mark_queue_buffer_offset());
2725     Node* thread = new ThreadLocalNode();
2726     phase->register_new_node(thread, ctrl);
2727     Node* buffer_adr = new AddPNode(phase->C->top(), thread, phase->igvn().MakeConX(buffer_offset));
2728     phase->register_new_node(buffer_adr, ctrl);
2729     Node* index_adr = new AddPNode(phase->C->top(), thread, phase->igvn().MakeConX(index_offset));
2730     phase->register_new_node(index_adr, ctrl);
2731 
2732     BasicType index_bt = TypeX_X->basic_type();
2733     assert(sizeof(size_t) == type2aelembytes(index_bt), "Loading G1 SATBMarkQueue::_index with wrong size.");
2734     const TypePtr* adr_type = TypeRawPtr::BOTTOM;
2735     Node* index = new LoadXNode(ctrl, raw_mem, index_adr, adr_type, TypeX_X, MemNode::unordered);
2736     phase->register_new_node(index, ctrl);
2737     Node* index_cmp = new CmpXNode(index, phase->igvn().MakeConX(0));
2738     phase->register_new_node(index_cmp, ctrl);
2739     Node* index_test = new BoolNode(index_cmp, BoolTest::ne);
2740     phase->register_new_node(index_test, ctrl);
2741     IfNode* queue_full_iff = new IfNode(ctrl, index_test, PROB_LIKELY(0.999), COUNT_UNKNOWN);
2742     if (reg2_ctrl == NULL) reg2_ctrl = queue_full_iff;
2743     phase->register_control(queue_full_iff, loop, ctrl);
2744     Node* not_full = new IfTrueNode(queue_full_iff);
2745     phase->register_control(not_full, loop, queue_full_iff);
2746     Node* full = new IfFalseNode(queue_full_iff);
2747     phase->register_control(full, loop, queue_full_iff);
2748 
2749     ctrl = not_full;
2750 
2751     Node* next_index = new SubXNode(index, phase->igvn().MakeConX(sizeof(intptr_t)));
2752     phase->register_new_node(next_index, ctrl);
2753 
2754     Node* buffer  = new LoadPNode(ctrl, raw_mem, buffer_adr, adr_type, TypeRawPtr::NOTNULL, MemNode::unordered);
2755     phase->register_new_node(buffer, ctrl);
2756     Node *log_addr = new AddPNode(phase->C->top(), buffer, next_index);
2757     phase->register_new_node(log_addr, ctrl);
2758     Node* log_store = new StorePNode(ctrl, raw_mem, log_addr, adr_type, pre_val, MemNode::unordered);
2759     phase->register_new_node(log_store, ctrl);
2760     // update the index
2761     Node* index_update = new StoreXNode(ctrl, log_store, index_adr, adr_type, next_index, MemNode::unordered);
2762     phase->register_new_node(index_update, ctrl);
2763 
2764     // Fast-path case
2765     region2->init_req(_fast_path, ctrl);
2766     phi2->init_req(_fast_path, index_update);
2767 
2768     ctrl = full;
2769 
2770     Node* base = find_bottom_mem(ctrl, phase);
2771 
2772     MergeMemNode* mm = MergeMemNode::make(base);
2773     mm->set_memory_at(Compile::AliasIdxRaw, raw_mem);
2774     phase->register_new_node(mm, ctrl);
2775 
2776     Node* call = new CallLeafNode(ShenandoahBarrierSetC2::write_ref_field_pre_entry_Type(), CAST_FROM_FN_PTR(address, ShenandoahRuntime::write_ref_field_pre_entry), "shenandoah_wb_pre", TypeRawPtr::BOTTOM);
2777     call->init_req(TypeFunc::Control, ctrl);
2778     call->init_req(TypeFunc::I_O, phase->C->top());
2779     call->init_req(TypeFunc::Memory, mm);
2780     call->init_req(TypeFunc::FramePtr, phase->C->top());
2781     call->init_req(TypeFunc::ReturnAdr, phase->C->top());
2782     call->init_req(TypeFunc::Parms, pre_val);
2783     call->init_req(TypeFunc::Parms+1, thread);
2784     phase->register_control(call, loop, ctrl);
2785 
2786     Node* ctrl_proj = new ProjNode(call, TypeFunc::Control);
2787     phase->register_control(ctrl_proj, loop, call);
2788     Node* mem_proj = new ProjNode(call, TypeFunc::Memory);
2789     phase->register_new_node(mem_proj, call);
2790 
2791     // Slow-path case
2792     region2->init_req(_slow_path, ctrl_proj);
2793     phi2->init_req(_slow_path, mem_proj);
2794 
2795     phase->register_control(region2, loop, reg2_ctrl);
2796     phase->register_new_node(phi2, region2);
2797 
2798     region->init_req(_heap_unstable, region2);
2799     phi->init_req(_heap_unstable, phi2);
2800 
2801     phase->register_control(region, loop, heap_stable_ctrl->in(0));
2802     phase->register_new_node(phi, region);
2803 
2804     fix_ctrl(barrier, region, fixer, uses, uses_to_ignore, last, phase);
2805     for(uint next = 0; next < uses.size(); next++ ) {
2806       Node *n = uses.at(next);
2807       assert(phase->get_ctrl(n) == init_ctrl, "bad control");
2808       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
2809       phase->set_ctrl(n, region);
2810       follow_barrier_uses(n, init_ctrl, uses, phase);
2811     }
2812     fixer.fix_mem(init_ctrl, region, init_raw_mem, raw_mem_for_ctrl, phi, uses);
2813 
2814     phase->igvn().replace_node(barrier, pre_val);
2815   }
2816 
2817   for (int i = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count(); i > 0; i--) {
2818     int cnt = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count();
2819     ShenandoahWriteBarrierNode* wb = ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barrier(i-1);
2820 
2821     uint last = phase->C->unique();
2822     Node* ctrl = phase->get_ctrl(wb);
2823     Node* orig_ctrl = ctrl;
2824 
2825     Node* raw_mem = fixer.find_mem(ctrl, wb);
2826     Node* init_raw_mem = raw_mem;
2827     Node* raw_mem_for_ctrl = fixer.find_mem(ctrl, NULL);
2828     int alias = phase->C->get_alias_index(wb->adr_type());
2829     Node* wb_mem =  wb->in(Memory);
2830     Node* init_wb_mem = wb_mem;
2831 
2832     Node* val = wb->in(ValueIn);
2833     Node* wbproj = wb->find_out_with(Op_ShenandoahWBMemProj);
2834     IdealLoopTree *loop = phase->get_loop(ctrl);
2835     if (loop->_head->is_OuterStripMinedLoop()) {
2836       outer_lsms.push(loop->_head);
2837     }
2838 
2839     assert(val->Opcode() != Op_ShenandoahWriteBarrier, "No chain of write barriers");
2840 
2841     CallStaticJavaNode* unc = wb->pin_and_expand_null_check(phase->igvn());
2842     Node* unc_ctrl = NULL;
2843     if (unc != NULL) {
2844       if (val->in(0) != ctrl) {
2845         unc = NULL;
2846       } else {
2847         unc_ctrl = val->in(0);
2848       }
2849     }
2850 
2851     Node* uncasted_val = val;
2852     if (unc != NULL) {
2853       uncasted_val = val->in(1);
2854     }
2855 
2856     Node* heap_stable_ctrl = NULL;
2857     Node* null_ctrl = NULL;
2858 
2859     assert(val->bottom_type()->make_oopptr(), "need oop");
2860     assert(val->bottom_type()->make_oopptr()->const_oop() == NULL, "expect non-constant");
2861 
2862     enum { _heap_stable = 1, _heap_unstable, PATH_LIMIT };
2863     Node* region = new RegionNode(PATH_LIMIT);
2864     Node* val_phi = new PhiNode(region, uncasted_val->bottom_type()->is_oopptr());
2865     Node* mem_phi = PhiNode::make(region, wb_mem, Type::MEMORY, phase->C->alias_type(wb->adr_type())->adr_type());
2866     Node* raw_mem_phi = PhiNode::make(region, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
2867 
2868     enum { _not_cset = 1, _not_equal, _evac_path, _null_path, PATH_LIMIT2 };
2869     Node* region2 = new RegionNode(PATH_LIMIT2);
2870     Node* val_phi2 = new PhiNode(region2, uncasted_val->bottom_type()->is_oopptr());
2871     Node* mem_phi2 = PhiNode::make(region2, wb_mem, Type::MEMORY, phase->C->alias_type(wb->adr_type())->adr_type());
2872     Node* raw_mem_phi2 = PhiNode::make(region2, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
2873 
2874       // Stable path.
2875     test_heap_stable(ctrl, raw_mem, heap_stable_ctrl, phase);
2876     IfNode* heap_stable_iff = heap_stable_ctrl->in(0)->as_If();
2877 
2878     // Heap stable case
2879     region->init_req(_heap_stable, heap_stable_ctrl);
2880     val_phi->init_req(_heap_stable, uncasted_val);
2881     mem_phi->init_req(_heap_stable, wb_mem);
2882     raw_mem_phi->init_req(_heap_stable, raw_mem);
2883 
2884     Node* reg2_ctrl = NULL;
2885     // Null case
2886     test_null(ctrl, val, null_ctrl, phase);
2887     if (null_ctrl != NULL) {
2888       reg2_ctrl = null_ctrl->in(0);
2889       region2->init_req(_null_path, null_ctrl);
2890       val_phi2->init_req(_null_path, uncasted_val);
2891       mem_phi2->init_req(_null_path, wb_mem);
2892       raw_mem_phi2->init_req(_null_path, raw_mem);
2893     } else {
2894       region2->del_req(_null_path);
2895       val_phi2->del_req(_null_path);
2896       mem_phi2->del_req(_null_path);
2897       raw_mem_phi2->del_req(_null_path);
2898     }
2899 
2900     // Test for in-cset.
2901     // Wires !in_cset(obj) to slot 2 of region and phis
2902     Node* not_cset_ctrl = NULL;
2903     in_cset_fast_test(ctrl, not_cset_ctrl, uncasted_val, raw_mem, phase);
2904     if (not_cset_ctrl != NULL) {
2905       if (reg2_ctrl == NULL) reg2_ctrl = not_cset_ctrl->in(0);
2906       region2->init_req(_not_cset, not_cset_ctrl);
2907       val_phi2->init_req(_not_cset, uncasted_val);
2908       mem_phi2->init_req(_not_cset, wb_mem);
2909       raw_mem_phi2->init_req(_not_cset, raw_mem);
2910     }
2911 
2912     // Resolve object when orig-value is in cset.
2913     // Make the unconditional resolve for fwdptr, not the read barrier.
2914     Node* new_val = uncasted_val;
2915     if (unc_ctrl != NULL) {
2916       // Clone the null check in this branch to allow implicit null check
2917       new_val = clone_null_check(ctrl, val, unc_ctrl, phase);
2918       fix_null_check(unc, unc_ctrl, ctrl->in(0)->as_If()->proj_out(0), uses, phase);
2919 
2920       IfNode* iff = unc_ctrl->in(0)->as_If();
2921       phase->igvn().replace_input_of(iff, 1, phase->igvn().intcon(1));
2922     }
2923     Node* addr = new AddPNode(new_val, uncasted_val, phase->igvn().MakeConX(ShenandoahBrooksPointer::byte_offset()));
2924     phase->register_new_node(addr, ctrl);
2925     assert(val->bottom_type()->isa_oopptr(), "what else?");
2926     const TypePtr* obj_type =  val->bottom_type()->is_oopptr();
2927     const TypePtr* adr_type = ShenandoahBarrierNode::brooks_pointer_type(obj_type);
2928     Node* fwd = new LoadPNode(ctrl, wb_mem, addr, adr_type, obj_type, MemNode::unordered);
2929     phase->register_new_node(fwd, ctrl);
2930 
2931     // Only branch to WB stub if object is not forwarded; otherwise reply with fwd ptr
2932     Node* cmp = new CmpPNode(fwd, new_val);
2933     phase->register_new_node(cmp, ctrl);
2934     Node* bol = new BoolNode(cmp, BoolTest::eq);
2935     phase->register_new_node(bol, ctrl);
2936 
2937     IfNode* iff = new IfNode(ctrl, bol, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
2938     if (reg2_ctrl == NULL) reg2_ctrl = iff;
2939     phase->register_control(iff, loop, ctrl);
2940     Node* if_not_eq = new IfFalseNode(iff);
2941     phase->register_control(if_not_eq, loop, iff);
2942     Node* if_eq = new IfTrueNode(iff);
2943     phase->register_control(if_eq, loop, iff);
2944 
2945     // Wire up not-equal-path in slots 3.
2946     region2->init_req(_not_equal, if_not_eq);
2947     val_phi2->init_req(_not_equal, fwd);
2948     mem_phi2->init_req(_not_equal, wb_mem);
2949     raw_mem_phi2->init_req(_not_equal, raw_mem);
2950 
2951     // Call wb-stub and wire up that path in slots 4
2952     Node* result_mem = NULL;
2953     ctrl = if_eq;
2954     call_wb_stub(ctrl, new_val, result_mem,
2955                  raw_mem, wb_mem,
2956                  alias, phase);
2957     region2->init_req(_evac_path, ctrl);
2958     val_phi2->init_req(_evac_path, new_val);
2959     mem_phi2->init_req(_evac_path, result_mem);
2960     raw_mem_phi2->init_req(_evac_path, result_mem);
2961 
2962     phase->register_control(region2, loop, reg2_ctrl);
2963     phase->register_new_node(val_phi2, region2);
2964     phase->register_new_node(mem_phi2, region2);
2965     phase->register_new_node(raw_mem_phi2, region2);
2966 
2967     region->init_req(_heap_unstable, region2);
2968     val_phi->init_req(_heap_unstable, val_phi2);
2969     mem_phi->init_req(_heap_unstable, mem_phi2);
2970     raw_mem_phi->init_req(_heap_unstable, raw_mem_phi2);
2971 
2972     phase->register_control(region, loop, heap_stable_iff);
2973     Node* out_val = val_phi;
2974     phase->register_new_node(val_phi, region);
2975     phase->register_new_node(mem_phi, region);
2976     phase->register_new_node(raw_mem_phi, region);
2977 
2978     fix_ctrl(wb, region, fixer, uses, uses_to_ignore, last, phase);
2979 
2980     ctrl = orig_ctrl;
2981 
2982     phase->igvn().replace_input_of(wbproj, ShenandoahWBMemProjNode::WriteBarrier, phase->C->top());
2983     phase->igvn().replace_node(wbproj, mem_phi);
2984     if (unc != NULL) {
2985       for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
2986         Node* u = val->fast_out(i);
2987         Node* c = phase->ctrl_or_self(u);
2988         if (u != wb && (c != ctrl || is_dominator_same_ctrl(c, wb, u, phase))) {
2989           phase->igvn().rehash_node_delayed(u);
2990           int nb = u->replace_edge(val, out_val);
2991           --i, imax -= nb;
2992         }
2993       }
2994       if (val->outcnt() == 0) {
2995         phase->igvn()._worklist.push(val);
2996       }
2997     }
2998     phase->igvn().replace_node(wb, out_val);
2999 
3000     follow_barrier_uses(mem_phi, ctrl, uses, phase);
3001     follow_barrier_uses(out_val, ctrl, uses, phase);
3002 
3003     for(uint next = 0; next < uses.size(); next++ ) {
3004       Node *n = uses.at(next);
3005       assert(phase->get_ctrl(n) == ctrl, "bad control");
3006       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
3007       phase->set_ctrl(n, region);
3008       follow_barrier_uses(n, ctrl, uses, phase);
3009     }
3010 
3011     // The slow path call produces memory: hook the raw memory phi
3012     // from the expanded write barrier with the rest of the graph
3013     // which may require adding memory phis at every post dominated
3014     // region and at enclosing loop heads. Use the memory state
3015     // collected in memory_nodes to fix the memory graph. Update that
3016     // memory state as we go.
3017     fixer.fix_mem(ctrl, region, init_raw_mem, raw_mem_for_ctrl, raw_mem_phi, uses);
3018     assert(ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count() == cnt - 1, "not replaced");
3019   }
3020 
3021   assert(ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count() == 0, "all write barrier nodes should have been replaced");
3022 
3023   for (uint i = 0; i < outer_lsms.size(); i++) {
3024     // Expanding a barrier here will break loop strip mining
3025     // verification. Transform the loop so the loop nest doesn't
3026     // appear as strip mined.
3027     OuterStripMinedLoopNode* outer = outer_lsms.at(i)->as_OuterStripMinedLoop();
3028     hide_strip_mined_loop(outer, outer->unique_ctrl_out()->as_CountedLoop(), phase);
3029   }
3030 }
3031 
3032 void ShenandoahWriteBarrierNode::move_heap_stable_test_out_of_loop(IfNode* iff, PhaseIdealLoop* phase) {
3033   IdealLoopTree *loop = phase->get_loop(iff);
3034   Node* loop_head = loop->_head;
3035   Node* entry_c = loop_head->in(LoopNode::EntryControl);
3036 
3037   Node* bol = iff->in(1);
3038   Node* cmp = bol->in(1);
3039   Node* andi = cmp->in(1);
3040   Node* load = andi->in(1);
3041 
3042   assert(is_gc_state_load(load), "broken");
3043   if (!phase->is_dominator(load->in(0), entry_c)) {
3044     Node* mem_ctrl = NULL;
3045     Node* mem = dom_mem(load->in(MemNode::Memory), loop_head, Compile::AliasIdxRaw, mem_ctrl, phase);
3046     load = load->clone();
3047     load->set_req(MemNode::Memory, mem);
3048     load->set_req(0, entry_c);
3049     phase->register_new_node(load, entry_c);
3050     andi = andi->clone();
3051     andi->set_req(1, load);
3052     phase->register_new_node(andi, entry_c);
3053     cmp = cmp->clone();
3054     cmp->set_req(1, andi);
3055     phase->register_new_node(cmp, entry_c);
3056     bol = bol->clone();
3057     bol->set_req(1, cmp);
3058     phase->register_new_node(bol, entry_c);
3059 
3060     Node* old_bol =iff->in(1);
3061     phase->igvn().replace_input_of(iff, 1, bol);
3062   }
3063 }
3064 
3065 bool ShenandoahWriteBarrierNode::identical_backtoback_ifs(Node *n, PhaseIdealLoop* phase) {
3066   if (!n->is_If() || n->is_CountedLoopEnd()) {
3067     return false;
3068   }
3069   Node* region = n->in(0);
3070 
3071   if (!region->is_Region()) {
3072     return false;
3073   }
3074   Node* dom = phase->idom(region);
3075   if (!dom->is_If()) {
3076     return false;
3077   }
3078 
3079   if (!is_heap_stable_test(n) || !is_heap_stable_test(dom)) {
3080     return false;
3081   }
3082 
3083   IfNode* dom_if = dom->as_If();
3084   Node* proj_true = dom_if->proj_out(1);
3085   Node* proj_false = dom_if->proj_out(0);
3086 
3087   for (uint i = 1; i < region->req(); i++) {
3088     if (phase->is_dominator(proj_true, region->in(i))) {
3089       continue;
3090     }
3091     if (phase->is_dominator(proj_false, region->in(i))) {
3092       continue;
3093     }
3094     return false;
3095   }
3096 
3097   return true;
3098 }
3099 
3100 void ShenandoahWriteBarrierNode::merge_back_to_back_tests(Node* n, PhaseIdealLoop* phase) {
3101   assert(is_heap_stable_test(n), "no other tests");
3102   if (identical_backtoback_ifs(n, phase)) {
3103     Node* n_ctrl = n->in(0);
3104     if (phase->can_split_if(n_ctrl)) {
3105       IfNode* dom_if = phase->idom(n_ctrl)->as_If();
3106       if (is_heap_stable_test(n)) {
3107         Node* gc_state_load = n->in(1)->in(1)->in(1)->in(1);
3108         assert(is_gc_state_load(gc_state_load), "broken");
3109         Node* dom_gc_state_load = dom_if->in(1)->in(1)->in(1)->in(1);
3110         assert(is_gc_state_load(dom_gc_state_load), "broken");
3111         if (gc_state_load != dom_gc_state_load) {
3112           phase->igvn().replace_node(gc_state_load, dom_gc_state_load);
3113         }
3114       }
3115       PhiNode* bolphi = PhiNode::make_blank(n_ctrl, n->in(1));
3116       Node* proj_true = dom_if->proj_out(1);
3117       Node* proj_false = dom_if->proj_out(0);
3118       Node* con_true = phase->igvn().makecon(TypeInt::ONE);
3119       Node* con_false = phase->igvn().makecon(TypeInt::ZERO);
3120 
3121       for (uint i = 1; i < n_ctrl->req(); i++) {
3122         if (phase->is_dominator(proj_true, n_ctrl->in(i))) {
3123           bolphi->init_req(i, con_true);
3124         } else {
3125           assert(phase->is_dominator(proj_false, n_ctrl->in(i)), "bad if");
3126           bolphi->init_req(i, con_false);
3127         }
3128       }
3129       phase->register_new_node(bolphi, n_ctrl);
3130       phase->igvn().replace_input_of(n, 1, bolphi);
3131       phase->do_split_if(n);
3132     }
3133   }
3134 }
3135 
3136 IfNode* ShenandoahWriteBarrierNode::find_unswitching_candidate(const IdealLoopTree *loop, PhaseIdealLoop* phase) {
3137   // Find first invariant test that doesn't exit the loop
3138   LoopNode *head = loop->_head->as_Loop();
3139   IfNode* unswitch_iff = NULL;
3140   Node* n = head->in(LoopNode::LoopBackControl);
3141   int loop_has_sfpts = -1;
3142   while (n != head) {
3143     Node* n_dom = phase->idom(n);
3144     if (n->is_Region()) {
3145       if (n_dom->is_If()) {
3146         IfNode* iff = n_dom->as_If();
3147         if (iff->in(1)->is_Bool()) {
3148           BoolNode* bol = iff->in(1)->as_Bool();
3149           if (bol->in(1)->is_Cmp()) {
3150             // If condition is invariant and not a loop exit,
3151             // then found reason to unswitch.
3152             if (is_heap_stable_test(iff) &&
3153                 (loop_has_sfpts == -1 || loop_has_sfpts == 0)) {
3154               assert(!loop->is_loop_exit(iff), "both branches should be in the loop");
3155               if (loop_has_sfpts == -1) {
3156                 for(uint i = 0; i < loop->_body.size(); i++) {
3157                   Node *m = loop->_body[i];
3158                   if (m->is_SafePoint() && !m->is_CallLeaf()) {
3159                     loop_has_sfpts = 1;
3160                     break;
3161                   }
3162                 }
3163                 if (loop_has_sfpts == -1) {
3164                   loop_has_sfpts = 0;
3165                 }
3166               }
3167               if (!loop_has_sfpts) {
3168                 unswitch_iff = iff;
3169               }
3170             }
3171           }
3172         }
3173       }
3174     }
3175     n = n_dom;
3176   }
3177   return unswitch_iff;
3178 }
3179 
3180 
3181 void ShenandoahWriteBarrierNode::optimize_after_expansion(VectorSet &visited, Node_Stack &stack, Node_List &old_new, PhaseIdealLoop* phase) {
3182   Node_List heap_stable_tests;
3183   Node_List gc_state_loads;
3184 
3185   stack.push(phase->C->start(), 0);
3186   do {
3187     Node* n = stack.node();
3188     uint i = stack.index();
3189 
3190     if (i < n->outcnt()) {
3191       Node* u = n->raw_out(i);
3192       stack.set_index(i+1);
3193       if (!visited.test_set(u->_idx)) {
3194         stack.push(u, 0);
3195       }
3196     } else {
3197       stack.pop();
3198       if (ShenandoahCommonGCStateLoads && is_gc_state_load(n)) {
3199         gc_state_loads.push(n);
3200       }
3201       if (n->is_If() && is_heap_stable_test(n)) {
3202         heap_stable_tests.push(n);
3203       }
3204     }
3205   } while (stack.size() > 0);
3206 
3207   bool progress;
3208   do {
3209     progress = false;
3210     for (uint i = 0; i < gc_state_loads.size(); i++) {
3211       Node* n = gc_state_loads.at(i);
3212       if (n->outcnt() != 0) {
3213         progress |= try_common_gc_state_load(n, phase);
3214       }
3215     }
3216   } while (progress);
3217 
3218   for (uint i = 0; i < heap_stable_tests.size(); i++) {
3219     Node* n = heap_stable_tests.at(i);
3220     assert(is_heap_stable_test(n), "only evacuation test");
3221     merge_back_to_back_tests(n, phase);
3222   }
3223 
3224   if (!phase->C->major_progress()) {
3225     VectorSet seen(Thread::current()->resource_area());
3226     for (uint i = 0; i < heap_stable_tests.size(); i++) {
3227       Node* n = heap_stable_tests.at(i);
3228       IdealLoopTree* loop = phase->get_loop(n);
3229       if (loop != phase->ltree_root() &&
3230           loop->_child == NULL &&
3231           !loop->_irreducible) {
3232         LoopNode* head = loop->_head->as_Loop();
3233         if ((!head->is_CountedLoop() || head->as_CountedLoop()->is_main_loop() || head->as_CountedLoop()->is_normal_loop()) &&
3234             !seen.test_set(head->_idx)) {
3235           IfNode* iff = find_unswitching_candidate(loop, phase);
3236           if (iff != NULL) {
3237             Node* bol = iff->in(1);
3238             if (head->is_strip_mined()) {
3239               head->verify_strip_mined(0);
3240             }
3241             move_heap_stable_test_out_of_loop(iff, phase);
3242             if (loop->policy_unswitching(phase)) {
3243               if (head->is_strip_mined()) {
3244                 OuterStripMinedLoopNode* outer = head->as_CountedLoop()->outer_loop();
3245                 hide_strip_mined_loop(outer, head->as_CountedLoop(), phase);
3246               }
3247               phase->do_unswitching(loop, old_new);
3248             } else {
3249               // Not proceeding with unswitching. Move load back in
3250               // the loop.
3251               phase->igvn().replace_input_of(iff, 1, bol);
3252             }
3253           }
3254         }
3255       }
3256     }
3257   }
3258 }
3259 
3260 #ifdef ASSERT
3261 void ShenandoahBarrierNode::verify_raw_mem(RootNode* root) {
3262   const bool trace = false;
3263   ResourceMark rm;
3264   Unique_Node_List nodes;
3265   Unique_Node_List controls;
3266   Unique_Node_List memories;
3267 
3268   nodes.push(root);
3269   for (uint next = 0; next < nodes.size(); next++) {
3270     Node *n  = nodes.at(next);
3271     if (ShenandoahBarrierSetC2::is_shenandoah_wb_call(n)) {
3272       controls.push(n);
3273       if (trace) { tty->print("XXXXXX verifying"); n->dump(); }
3274       for (uint next2 = 0; next2 < controls.size(); next2++) {
3275         Node *m = controls.at(next2);
3276         for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
3277           Node* u = m->fast_out(i);
3278           if (u->is_CFG() && !u->is_Root() &&
3279               !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1) &&
3280               !(u->is_Region() && u->unique_ctrl_out()->Opcode() == Op_Halt)) {
3281             if (trace) { tty->print("XXXXXX pushing control"); u->dump(); }
3282             controls.push(u);
3283           }
3284         }
3285       }
3286       memories.push(n->as_Call()->proj_out(TypeFunc::Memory));
3287       for (uint next2 = 0; next2 < memories.size(); next2++) {
3288         Node *m = memories.at(next2);
3289         assert(m->bottom_type() == Type::MEMORY, "");
3290         for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
3291           Node* u = m->fast_out(i);
3292           if (u->bottom_type() == Type::MEMORY && (u->is_Mem() || u->is_ClearArray())) {
3293             if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
3294             memories.push(u);
3295           } else if (u->is_LoadStore()) {
3296             if (trace) { tty->print("XXXXXX pushing memory"); u->find_out_with(Op_SCMemProj)->dump(); }
3297             memories.push(u->find_out_with(Op_SCMemProj));
3298           } else if (u->is_MergeMem() && u->as_MergeMem()->memory_at(Compile::AliasIdxRaw) == m) {
3299             if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
3300             memories.push(u);
3301           } else if (u->is_Phi()) {
3302             assert(u->bottom_type() == Type::MEMORY, "");
3303             if (u->adr_type() == TypeRawPtr::BOTTOM || u->adr_type() == TypePtr::BOTTOM) {
3304               assert(controls.member(u->in(0)), "");
3305               if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
3306               memories.push(u);
3307             }
3308           } else if (u->is_SafePoint() || u->is_MemBar()) {
3309             for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
3310               Node* uu = u->fast_out(j);
3311               if (uu->bottom_type() == Type::MEMORY) {
3312                 if (trace) { tty->print("XXXXXX pushing memory"); uu->dump(); }
3313                 memories.push(uu);
3314               }
3315             }
3316           }
3317         }
3318       }
3319       for (uint next2 = 0; next2 < controls.size(); next2++) {
3320         Node *m = controls.at(next2);
3321         if (m->is_Region()) {
3322           bool all_in = true;
3323           for (uint i = 1; i < m->req(); i++) {
3324             if (!controls.member(m->in(i))) {
3325               all_in = false;
3326               break;
3327             }
3328           }
3329           if (trace) { tty->print("XXX verifying %s", all_in ? "all in" : ""); m->dump(); }
3330           bool found_phi = false;
3331           for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax && !found_phi; j++) {
3332             Node* u = m->fast_out(j);
3333             if (u->is_Phi() && memories.member(u)) {
3334               found_phi = true;
3335               for (uint i = 1; i < u->req() && found_phi; i++) {
3336                 Node* k = u->in(i);
3337                 if (memories.member(k) != controls.member(m->in(i))) {
3338                   found_phi = false;
3339                 }
3340               }
3341             }
3342           }
3343           assert(found_phi || all_in, "");
3344         }
3345       }
3346       controls.clear();
3347       memories.clear();
3348     }
3349     for( uint i = 0; i < n->len(); ++i ) {
3350       Node *m = n->in(i);
3351       if (m != NULL) {
3352         nodes.push(m);
3353       }
3354     }
3355   }
3356 }
3357 #endif
3358 
3359 const Type* ShenandoahEnqueueBarrierNode::bottom_type() const {
3360   if (in(1) == NULL || in(1)->is_top()) {
3361     return Type::TOP;
3362   }
3363   const Type* t = in(1)->bottom_type();
3364   if (t == TypePtr::NULL_PTR) {
3365     return t;
3366   }
3367   return t->is_oopptr()->cast_to_nonconst();
3368 }
3369 
3370 const Type* ShenandoahEnqueueBarrierNode::Value(PhaseGVN* phase) const {
3371   if (in(1) == NULL) {
3372     return Type::TOP;
3373   }
3374   const Type* t = phase->type(in(1));
3375   if (t == Type::TOP) {
3376     return Type::TOP;
3377   }
3378   if (t == TypePtr::NULL_PTR) {
3379     return t;
3380   }
3381   return t->is_oopptr()->cast_to_nonconst();
3382 }
3383 
3384 int ShenandoahEnqueueBarrierNode::needed(Node* n) {
3385   if (n == NULL ||
3386       n->is_Allocate() ||
3387       n->bottom_type() == TypePtr::NULL_PTR ||
3388       (n->bottom_type()->make_oopptr() != NULL && n->bottom_type()->make_oopptr()->const_oop() != NULL)) {
3389     return NotNeeded;
3390   }
3391   if (n->is_Phi() ||
3392       n->is_CMove()) {
3393     return MaybeNeeded;
3394   }
3395   return Needed;
3396 }
3397 
3398 Node* ShenandoahEnqueueBarrierNode::next(Node* n) {
3399   for (;;) {
3400     if (n == NULL) {
3401       return n;
3402     } else if (n->bottom_type() == TypePtr::NULL_PTR) {
3403       return n;
3404     } else if (n->bottom_type()->make_oopptr() != NULL && n->bottom_type()->make_oopptr()->const_oop() != NULL) {
3405       return n;
3406     } else if (n->is_ConstraintCast() ||
3407                n->Opcode() == Op_DecodeN ||
3408                n->Opcode() == Op_EncodeP) {
3409       n = n->in(1);
3410     } else if (n->is_Proj()) {
3411       n = n->in(0);
3412     } else {
3413       return n;
3414     }
3415   }
3416   ShouldNotReachHere();
3417   return NULL;
3418 }
3419 
3420 Node* ShenandoahEnqueueBarrierNode::Identity(PhaseGVN* phase) {
3421   PhaseIterGVN* igvn = phase->is_IterGVN();
3422 
3423   Node* n = next(in(1));
3424 
3425   int cont = needed(n);
3426 
3427   if (cont == NotNeeded) {
3428     return in(1);
3429   } else if (cont == MaybeNeeded) {
3430     if (igvn == NULL) {
3431       phase->record_for_igvn(this);
3432       return this;
3433     } else {
3434       ResourceMark rm;
3435       Unique_Node_List wq;
3436       uint wq_i = 0;
3437 
3438       for (;;) {
3439         if (n->is_Phi()) {
3440           for (uint i = 1; i < n->req(); i++) {
3441             Node* m = n->in(i);
3442             if (m != NULL) {
3443               wq.push(m);
3444             }
3445           }
3446         } else {
3447           assert(n->is_CMove(), "nothing else here");
3448           Node* m = n->in(CMoveNode::IfFalse);
3449           wq.push(m);
3450           m = n->in(CMoveNode::IfTrue);
3451           wq.push(m);
3452         }
3453         Node* orig_n = NULL;
3454         do {
3455           if (wq_i >= wq.size()) {
3456             return in(1);
3457           }
3458           n = wq.at(wq_i);
3459           wq_i++;
3460           orig_n = n;
3461           n = next(n);
3462           cont = needed(n);
3463           if (cont == Needed) {
3464             return this;
3465           }
3466         } while (cont != MaybeNeeded || (orig_n != n && wq.member(n)));
3467       }
3468     }
3469   }
3470 
3471   return this;
3472 }
3473 
3474 #ifdef ASSERT
3475 static bool has_never_branch(Node* root) {
3476   for (uint i = 1; i < root->req(); i++) {
3477     Node* in = root->in(i);
3478     if (in != NULL && in->Opcode() == Op_Halt && in->in(0)->is_Proj() && in->in(0)->in(0)->Opcode() == Op_NeverBranch) {
3479       return true;
3480     }
3481   }
3482   return false;
3483 }
3484 #endif
3485 
3486 void MemoryGraphFixer::collect_memory_nodes() {
3487   Node_Stack stack(0);
3488   VectorSet visited(Thread::current()->resource_area());
3489   Node_List regions;
3490 
3491   // Walk the raw memory graph and create a mapping from CFG node to
3492   // memory node. Exclude phis for now.
3493   stack.push(_phase->C->root(), 1);
3494   do {
3495     Node* n = stack.node();
3496     int opc = n->Opcode();
3497     uint i = stack.index();
3498     if (i < n->req()) {
3499       Node* mem = NULL;
3500       if (opc == Op_Root) {
3501         Node* in = n->in(i);
3502         int in_opc = in->Opcode();
3503         if (in_opc == Op_Return || in_opc == Op_Rethrow) {
3504           mem = in->in(TypeFunc::Memory);
3505         } else if (in_opc == Op_Halt) {
3506           if (!in->in(0)->is_Region()) {
3507             Node* proj = in->in(0);
3508             assert(proj->is_Proj(), "");
3509             Node* in = proj->in(0);
3510             assert(in->is_CallStaticJava() || in->Opcode() == Op_NeverBranch || in->Opcode() == Op_Catch || proj->is_IfProj(), "");
3511             if (in->is_CallStaticJava()) {
3512               mem = in->in(TypeFunc::Memory);
3513             } else if (in->Opcode() == Op_Catch) {
3514               Node* call = in->in(0)->in(0);
3515               assert(call->is_Call(), "");
3516               mem = call->in(TypeFunc::Memory);
3517             }
3518           }
3519         } else {
3520 #ifdef ASSERT
3521           n->dump();
3522           in->dump();
3523 #endif
3524           ShouldNotReachHere();
3525         }
3526       } else {
3527         assert(n->is_Phi() && n->bottom_type() == Type::MEMORY, "");
3528         assert(n->adr_type() == TypePtr::BOTTOM || _phase->C->get_alias_index(n->adr_type()) == _alias, "");
3529         mem = n->in(i);
3530       }
3531       i++;
3532       stack.set_index(i);
3533       if (mem == NULL) {
3534         continue;
3535       }
3536       for (;;) {
3537         if (visited.test_set(mem->_idx) || mem->is_Start()) {
3538           break;
3539         }
3540         if (mem->is_Phi()) {
3541           stack.push(mem, 2);
3542           mem = mem->in(1);
3543         } else if (mem->is_Proj()) {
3544           stack.push(mem, mem->req());
3545           mem = mem->in(0);
3546         } else if (mem->is_SafePoint() || mem->is_MemBar()) {
3547           mem = mem->in(TypeFunc::Memory);
3548         } else if (mem->is_MergeMem()) {
3549           MergeMemNode* mm = mem->as_MergeMem();
3550           mem = mm->memory_at(_alias);
3551         } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
3552           assert(_alias == Compile::AliasIdxRaw, "");
3553           stack.push(mem, mem->req());
3554           mem = mem->in(MemNode::Memory);
3555         } else if (mem->Opcode() == Op_ShenandoahWriteBarrier) {
3556           assert(_alias != Compile::AliasIdxRaw, "");
3557           mem = mem->in(ShenandoahBarrierNode::Memory);
3558         } else if (mem->Opcode() == Op_ShenandoahWBMemProj) {
3559           stack.push(mem, mem->req());
3560           mem = mem->in(ShenandoahWBMemProjNode::WriteBarrier);
3561         } else {
3562 #ifdef ASSERT
3563           mem->dump();
3564 #endif
3565           ShouldNotReachHere();
3566         }
3567       }
3568     } else {
3569       if (n->is_Phi()) {
3570         // Nothing
3571       } else if (!n->is_Root()) {
3572         Node* c = get_ctrl(n);
3573         _memory_nodes.map(c->_idx, n);
3574       }
3575       stack.pop();
3576     }
3577   } while(stack.is_nonempty());
3578 
3579   // Iterate over CFG nodes in rpo and propagate memory state to
3580   // compute memory state at regions, creating new phis if needed.
3581   Node_List rpo_list;
3582   visited.Clear();
3583   _phase->rpo(_phase->C->root(), stack, visited, rpo_list);
3584   Node* root = rpo_list.pop();
3585   assert(root == _phase->C->root(), "");
3586 
3587   const bool trace = false;
3588 #ifdef ASSERT
3589   if (trace) {
3590     for (int i = rpo_list.size() - 1; i >= 0; i--) {
3591       Node* c = rpo_list.at(i);
3592       if (_memory_nodes[c->_idx] != NULL) {
3593         tty->print("X %d", c->_idx);  _memory_nodes[c->_idx]->dump();
3594       }
3595     }
3596   }
3597 #endif
3598   uint last = _phase->C->unique();
3599 
3600 #ifdef ASSERT
3601   uint8_t max_depth = 0;
3602   for (LoopTreeIterator iter(_phase->ltree_root()); !iter.done(); iter.next()) {
3603     IdealLoopTree* lpt = iter.current();
3604     max_depth = MAX2(max_depth, lpt->_nest);
3605   }
3606 #endif
3607 
3608   bool progress = true;
3609   int iteration = 0;
3610   Node_List dead_phis;
3611   while (progress) {
3612     progress = false;
3613     iteration++;
3614     assert(iteration <= 2+max_depth || _phase->C->has_irreducible_loop(), "");
3615     if (trace) { tty->print_cr("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"); }
3616     IdealLoopTree* last_updated_ilt = NULL;
3617     for (int i = rpo_list.size() - 1; i >= 0; i--) {
3618       Node* c = rpo_list.at(i);
3619 
3620       Node* prev_mem = _memory_nodes[c->_idx];
3621       if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
3622         Node* prev_region = regions[c->_idx];
3623         Node* unique = NULL;
3624         for (uint j = 1; j < c->req() && unique != NodeSentinel; j++) {
3625           Node* m = _memory_nodes[c->in(j)->_idx];
3626           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");
3627           if (m != NULL) {
3628             if (m == prev_region && ((c->is_Loop() && j == LoopNode::LoopBackControl) || (prev_region->is_Phi() && prev_region->in(0) == c))) {
3629               assert(c->is_Loop() && j == LoopNode::LoopBackControl || _phase->C->has_irreducible_loop(), "");
3630               // continue
3631             } else if (unique == NULL) {
3632               unique = m;
3633             } else if (m == unique) {
3634               // continue
3635             } else {
3636               unique = NodeSentinel;
3637             }
3638           }
3639         }
3640         assert(unique != NULL, "empty phi???");
3641         if (unique != NodeSentinel) {
3642           if (prev_region != NULL && prev_region->is_Phi() && prev_region->in(0) == c) {
3643             dead_phis.push(prev_region);
3644           }
3645           regions.map(c->_idx, unique);
3646         } else {
3647           Node* phi = NULL;
3648           if (prev_region != NULL && prev_region->is_Phi() && prev_region->in(0) == c && prev_region->_idx >= last) {
3649             phi = prev_region;
3650             for (uint k = 1; k < c->req(); k++) {
3651               Node* m = _memory_nodes[c->in(k)->_idx];
3652               assert(m != NULL, "expect memory state");
3653               phi->set_req(k, m);
3654             }
3655           } else {
3656             for (DUIterator_Fast jmax, j = c->fast_outs(jmax); j < jmax && phi == NULL; j++) {
3657               Node* u = c->fast_out(j);
3658               if (u->is_Phi() && u->bottom_type() == Type::MEMORY &&
3659                   (u->adr_type() == TypePtr::BOTTOM || _phase->C->get_alias_index(u->adr_type()) == _alias)) {
3660                 phi = u;
3661                 for (uint k = 1; k < c->req() && phi != NULL; k++) {
3662                   Node* m = _memory_nodes[c->in(k)->_idx];
3663                   assert(m != NULL, "expect memory state");
3664                   if (u->in(k) != m) {
3665                     phi = NULL;
3666                   }
3667                 }
3668               }
3669             }
3670             if (phi == NULL) {
3671               phi = new PhiNode(c, Type::MEMORY, _phase->C->get_adr_type(_alias));
3672               for (uint k = 1; k < c->req(); k++) {
3673                 Node* m = _memory_nodes[c->in(k)->_idx];
3674                 assert(m != NULL, "expect memory state");
3675                 phi->init_req(k, m);
3676               }
3677             }
3678           }
3679           assert(phi != NULL, "");
3680           regions.map(c->_idx, phi);
3681         }
3682         Node* current_region = regions[c->_idx];
3683         if (current_region != prev_region) {
3684           progress = true;
3685           if (prev_region == prev_mem) {
3686             _memory_nodes.map(c->_idx, current_region);
3687           }
3688         }
3689       } else if (prev_mem == NULL || prev_mem->is_Phi() || ctrl_or_self(prev_mem) != c) {
3690         Node* m = _memory_nodes[_phase->idom(c)->_idx];
3691         assert(m != NULL, "expect memory state");
3692         if (m != prev_mem) {
3693           _memory_nodes.map(c->_idx, m);
3694           progress = true;
3695         }
3696       }
3697 #ifdef ASSERT
3698       if (trace) { tty->print("X %d", c->_idx);  _memory_nodes[c->_idx]->dump(); }
3699 #endif
3700     }
3701   }
3702 
3703   // Replace existing phi with computed memory state for that region
3704   // if different (could be a new phi or a dominating memory node if
3705   // that phi was found to be useless).
3706   while (dead_phis.size() > 0) {
3707     Node* n = dead_phis.pop();
3708     n->replace_by(_phase->C->top());
3709     n->destruct();
3710   }
3711   for (int i = rpo_list.size() - 1; i >= 0; i--) {
3712     Node* c = rpo_list.at(i);
3713     if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
3714       Node* n = regions[c->_idx];
3715       if (n->is_Phi() && n->_idx >= last && n->in(0) == c) {
3716         _phase->register_new_node(n, c);
3717       }
3718     }
3719   }
3720   for (int i = rpo_list.size() - 1; i >= 0; i--) {
3721     Node* c = rpo_list.at(i);
3722     if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
3723       Node* n = regions[c->_idx];
3724       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
3725         Node* u = c->fast_out(i);
3726         if (u->is_Phi() && u->bottom_type() == Type::MEMORY &&
3727             u != n) {
3728           if (u->adr_type() == TypePtr::BOTTOM) {
3729             fix_memory_uses(u, n, n, c);
3730           } else if (_phase->C->get_alias_index(u->adr_type()) == _alias) {
3731             _phase->lazy_replace(u, n);
3732             --i; --imax;
3733           }
3734         }
3735       }
3736     }
3737   }
3738 }
3739 
3740 Node* MemoryGraphFixer::get_ctrl(Node* n) const {
3741   Node* c = _phase->get_ctrl(n);
3742   if (n->is_Proj() && n->in(0) != NULL && n->in(0)->is_Call()) {
3743     assert(c == n->in(0), "");
3744     CallNode* call = c->as_Call();
3745     CallProjections projs;
3746     call->extract_projections(&projs, true, false);
3747     if (projs.catchall_memproj != NULL) {
3748       if (projs.fallthrough_memproj == n) {
3749         c = projs.fallthrough_catchproj;
3750       } else {
3751         assert(projs.catchall_memproj == n, "");
3752         c = projs.catchall_catchproj;
3753       }
3754     }
3755   }
3756   return c;
3757 }
3758 
3759 Node* MemoryGraphFixer::ctrl_or_self(Node* n) const {
3760   if (_phase->has_ctrl(n))
3761     return get_ctrl(n);
3762   else {
3763     assert (n->is_CFG(), "must be a CFG node");
3764     return n;
3765   }
3766 }
3767 
3768 bool MemoryGraphFixer::mem_is_valid(Node* m, Node* c) const {
3769   return m != NULL && get_ctrl(m) == c;
3770 }
3771 
3772 Node* MemoryGraphFixer::find_mem(Node* ctrl, Node* n) const {
3773   assert(n == NULL || _phase->ctrl_or_self(n) == ctrl, "");
3774   Node* mem = _memory_nodes[ctrl->_idx];
3775   Node* c = ctrl;
3776   while (!mem_is_valid(mem, c) &&
3777          (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem))) {
3778     c = _phase->idom(c);
3779     mem = _memory_nodes[c->_idx];
3780   }
3781   if (n != NULL && mem_is_valid(mem, c)) {
3782     while (!ShenandoahWriteBarrierNode::is_dominator_same_ctrl(c, mem, n, _phase) && _phase->ctrl_or_self(mem) == ctrl) {
3783       mem = next_mem(mem, _alias);
3784     }
3785     if (mem->is_MergeMem()) {
3786       mem = mem->as_MergeMem()->memory_at(_alias);
3787     }
3788     if (!mem_is_valid(mem, c)) {
3789       do {
3790         c = _phase->idom(c);
3791         mem = _memory_nodes[c->_idx];
3792       } while (!mem_is_valid(mem, c) &&
3793                (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem)));
3794     }
3795   }
3796   assert(mem->bottom_type() == Type::MEMORY, "");
3797   return mem;
3798 }
3799 
3800 bool MemoryGraphFixer::has_mem_phi(Node* region) const {
3801   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
3802     Node* use = region->fast_out(i);
3803     if (use->is_Phi() && use->bottom_type() == Type::MEMORY &&
3804         (_phase->C->get_alias_index(use->adr_type()) == _alias)) {
3805       return true;
3806     }
3807   }
3808   return false;
3809 }
3810 
3811 void MemoryGraphFixer::fix_mem(Node* ctrl, Node* new_ctrl, Node* mem, Node* mem_for_ctrl, Node* new_mem, Unique_Node_List& uses) {
3812   assert(_phase->ctrl_or_self(new_mem) == new_ctrl, "");
3813   const bool trace = false;
3814   DEBUG_ONLY(if (trace) { tty->print("ZZZ control is"); ctrl->dump(); });
3815   DEBUG_ONLY(if (trace) { tty->print("ZZZ mem is"); mem->dump(); });
3816   GrowableArray<Node*> phis;
3817   if (mem_for_ctrl != mem) {
3818     Node* old = mem_for_ctrl;
3819     Node* prev = NULL;
3820     while (old != mem) {
3821       prev = old;
3822       if (old->is_Store() || old->is_ClearArray() || old->is_LoadStore()) {
3823         assert(_alias == Compile::AliasIdxRaw, "");
3824         old = old->in(MemNode::Memory);
3825       } else if (old->Opcode() == Op_SCMemProj) {
3826         assert(_alias == Compile::AliasIdxRaw, "");
3827         old = old->in(0);
3828       } else if (old->Opcode() == Op_ShenandoahWBMemProj) {
3829         assert(_alias != Compile::AliasIdxRaw, "");
3830         old = old->in(ShenandoahWBMemProjNode::WriteBarrier);
3831       } else if (old->Opcode() == Op_ShenandoahWriteBarrier) {
3832         assert(_alias != Compile::AliasIdxRaw, "");
3833         old = old->in(ShenandoahBarrierNode::Memory);
3834       } else {
3835         ShouldNotReachHere();
3836       }
3837     }
3838     assert(prev != NULL, "");
3839     if (new_ctrl != ctrl) {
3840       _memory_nodes.map(ctrl->_idx, mem);
3841       _memory_nodes.map(new_ctrl->_idx, mem_for_ctrl);
3842     }
3843     uint input = prev->Opcode() == Op_ShenandoahWriteBarrier ? (uint)ShenandoahBarrierNode::Memory : (uint)MemNode::Memory;
3844     _phase->igvn().replace_input_of(prev, input, new_mem);
3845   } else {
3846     uses.clear();
3847     _memory_nodes.map(new_ctrl->_idx, new_mem);
3848     uses.push(new_ctrl);
3849     for(uint next = 0; next < uses.size(); next++ ) {
3850       Node *n = uses.at(next);
3851       assert(n->is_CFG(), "");
3852       DEBUG_ONLY(if (trace) { tty->print("ZZZ ctrl"); n->dump(); });
3853       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3854         Node* u = n->fast_out(i);
3855         if (!u->is_Root() && u->is_CFG() && u != n) {
3856           Node* m = _memory_nodes[u->_idx];
3857           if (u->is_Region() && (!u->is_OuterStripMinedLoop() || _include_lsm) &&
3858               !has_mem_phi(u) &&
3859               u->unique_ctrl_out()->Opcode() != Op_Halt) {
3860             DEBUG_ONLY(if (trace) { tty->print("ZZZ region"); u->dump(); });
3861             DEBUG_ONLY(if (trace && m != NULL) { tty->print("ZZZ mem"); m->dump(); });
3862 
3863             if (!mem_is_valid(m, u) || !m->is_Phi()) {
3864               bool push = true;
3865               bool create_phi = true;
3866               if (_phase->is_dominator(new_ctrl, u)) {
3867                 create_phi = false;
3868               } else if (!_phase->C->has_irreducible_loop()) {
3869                 IdealLoopTree* loop = _phase->get_loop(ctrl);
3870                 bool do_check = true;
3871                 IdealLoopTree* l = loop;
3872                 create_phi = false;
3873                 while (l != _phase->ltree_root()) {
3874                   if (_phase->is_dominator(l->_head, u) && _phase->is_dominator(_phase->idom(u), l->_head)) {
3875                     create_phi = true;
3876                     do_check = false;
3877                     break;
3878                   }
3879                   l = l->_parent;
3880                 }
3881 
3882                 if (do_check) {
3883                   assert(!create_phi, "");
3884                   IdealLoopTree* u_loop = _phase->get_loop(u);
3885                   if (u_loop != _phase->ltree_root() && u_loop->is_member(loop)) {
3886                     Node* c = ctrl;
3887                     while (!_phase->is_dominator(c, u_loop->tail())) {
3888                       c = _phase->idom(c);
3889                     }
3890                     if (!_phase->is_dominator(c, u)) {
3891                       do_check = false;
3892                     }
3893                   }
3894                 }
3895 
3896                 if (do_check && _phase->is_dominator(_phase->idom(u), new_ctrl)) {
3897                   create_phi = true;
3898                 }
3899               }
3900               if (create_phi) {
3901                 Node* phi = new PhiNode(u, Type::MEMORY, _phase->C->get_adr_type(_alias));
3902                 _phase->register_new_node(phi, u);
3903                 phis.push(phi);
3904                 DEBUG_ONLY(if (trace) { tty->print("ZZZ new phi"); phi->dump(); });
3905                 if (!mem_is_valid(m, u)) {
3906                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting mem"); phi->dump(); });
3907                   _memory_nodes.map(u->_idx, phi);
3908                 } else {
3909                   DEBUG_ONLY(if (trace) { tty->print("ZZZ NOT setting mem"); m->dump(); });
3910                   for (;;) {
3911                     assert(m->is_Mem() || m->is_LoadStore() || m->is_Proj() || m->Opcode() == Op_ShenandoahWriteBarrier || m->Opcode() == Op_ShenandoahWBMemProj, "");
3912                     Node* next = NULL;
3913                     if (m->is_Proj()) {
3914                       next = m->in(0);
3915                     } else if (m->Opcode() == Op_ShenandoahWBMemProj) {
3916                       next = m->in(ShenandoahWBMemProjNode::WriteBarrier);
3917                     } else if (m->is_Mem() || m->is_LoadStore()) {
3918                       assert(_alias == Compile::AliasIdxRaw, "");
3919                       next = m->in(MemNode::Memory);
3920                     } else {
3921                       assert(_alias != Compile::AliasIdxRaw, "");
3922                       assert (m->Opcode() == Op_ShenandoahWriteBarrier, "");
3923                       next = m->in(ShenandoahBarrierNode::Memory);
3924                     }
3925                     if (_phase->get_ctrl(next) != u) {
3926                       break;
3927                     }
3928                     if (next->is_MergeMem()) {
3929                       assert(_phase->get_ctrl(next->as_MergeMem()->memory_at(_alias)) != u, "");
3930                       break;
3931                     }
3932                     if (next->is_Phi()) {
3933                       assert(next->adr_type() == TypePtr::BOTTOM && next->in(0) == u, "");
3934                       break;
3935                     }
3936                     m = next;
3937                   }
3938 
3939                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting to phi"); m->dump(); });
3940                   assert(m->is_Mem() || m->is_LoadStore() || m->Opcode() == Op_ShenandoahWriteBarrier, "");
3941                   uint input = (m->is_Mem() || m->is_LoadStore()) ? (uint)MemNode::Memory : (uint)ShenandoahBarrierNode::Memory;
3942                   _phase->igvn().replace_input_of(m, input, phi);
3943                   push = false;
3944                 }
3945               } else {
3946                 DEBUG_ONLY(if (trace) { tty->print("ZZZ skipping region"); u->dump(); });
3947               }
3948               if (push) {
3949                 uses.push(u);
3950               }
3951             }
3952           } else if (!mem_is_valid(m, u) &&
3953                      !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1)) {
3954             uses.push(u);
3955           }
3956         }
3957       }
3958     }
3959     for (int i = 0; i < phis.length(); i++) {
3960       Node* n = phis.at(i);
3961       Node* r = n->in(0);
3962       DEBUG_ONLY(if (trace) { tty->print("ZZZ fixing new phi"); n->dump(); });
3963       for (uint j = 1; j < n->req(); j++) {
3964         Node* m = find_mem(r->in(j), NULL);
3965         _phase->igvn().replace_input_of(n, j, m);
3966         DEBUG_ONLY(if (trace) { tty->print("ZZZ fixing new phi: %d", j); m->dump(); });
3967       }
3968     }
3969   }
3970   uint last = _phase->C->unique();
3971   MergeMemNode* mm = NULL;
3972   int alias = _alias;
3973   DEBUG_ONLY(if (trace) { tty->print("ZZZ raw mem is"); mem->dump(); });
3974   for (DUIterator i = mem->outs(); mem->has_out(i); i++) {
3975     Node* u = mem->out(i);
3976     if (u->_idx < last) {
3977       if (u->is_Mem()) {
3978         if (_phase->C->get_alias_index(u->adr_type()) == alias) {
3979           Node* m = find_mem(_phase->get_ctrl(u), u);
3980           if (m != mem) {
3981             DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
3982             _phase->igvn().replace_input_of(u, MemNode::Memory, m);
3983             --i;
3984           }
3985         }
3986       } else if (u->is_MergeMem()) {
3987         MergeMemNode* u_mm = u->as_MergeMem();
3988         if (u_mm->memory_at(alias) == mem) {
3989           MergeMemNode* newmm = NULL;
3990           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
3991             Node* uu = u->fast_out(j);
3992             assert(!uu->is_MergeMem(), "chain of MergeMems?");
3993             if (uu->is_Phi()) {
3994               assert(uu->adr_type() == TypePtr::BOTTOM, "");
3995               Node* region = uu->in(0);
3996               int nb = 0;
3997               for (uint k = 1; k < uu->req(); k++) {
3998                 if (uu->in(k) == u) {
3999                   Node* m = find_mem(region->in(k), NULL);
4000                   if (m != mem) {
4001                     DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of phi %d", k); uu->dump(); });
4002                     newmm = clone_merge_mem(u, mem, m, _phase->ctrl_or_self(m), i);
4003                     if (newmm != u) {
4004                       _phase->igvn().replace_input_of(uu, k, newmm);
4005                       nb++;
4006                       --jmax;
4007                     }
4008                   }
4009                 }
4010               }
4011               if (nb > 0) {
4012                 --j;
4013               }
4014             } else {
4015               Node* m = find_mem(_phase->ctrl_or_self(uu), uu);
4016               if (m != mem) {
4017                 DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); uu->dump(); });
4018                 newmm = clone_merge_mem(u, mem, m, _phase->ctrl_or_self(m), i);
4019                 if (newmm != u) {
4020                   _phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
4021                   --j, --jmax;
4022                 }
4023               }
4024             }
4025           }
4026         }
4027       } else if (u->is_Phi()) {
4028         assert(u->bottom_type() == Type::MEMORY, "what else?");
4029         if (_phase->C->get_alias_index(u->adr_type()) == alias || u->adr_type() == TypePtr::BOTTOM) {
4030           Node* region = u->in(0);
4031           bool replaced = false;
4032           for (uint j = 1; j < u->req(); j++) {
4033             if (u->in(j) == mem) {
4034               Node* m = find_mem(region->in(j), NULL);
4035               Node* nnew = m;
4036               if (m != mem) {
4037                 if (u->adr_type() == TypePtr::BOTTOM) {
4038                   mm = allocate_merge_mem(mem, m, _phase->ctrl_or_self(m));
4039                   nnew = mm;
4040                 }
4041                 DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of phi %d", j); u->dump(); });
4042                 _phase->igvn().replace_input_of(u, j, nnew);
4043                 replaced = true;
4044               }
4045             }
4046           }
4047           if (replaced) {
4048             --i;
4049           }
4050         }
4051       } else if ((u->adr_type() == TypePtr::BOTTOM && u->Opcode() != Op_StrInflatedCopy) ||
4052                  u->adr_type() == NULL) {
4053         assert(u->adr_type() != NULL ||
4054                u->Opcode() == Op_Rethrow ||
4055                u->Opcode() == Op_Return ||
4056                u->Opcode() == Op_SafePoint ||
4057                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
4058                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
4059                u->Opcode() == Op_CallLeaf, "");
4060         Node* m = find_mem(_phase->ctrl_or_self(u), u);
4061         if (m != mem) {
4062           mm = allocate_merge_mem(mem, m, _phase->get_ctrl(m));
4063           _phase->igvn().replace_input_of(u, u->find_edge(mem), mm);
4064           --i;
4065         }
4066       } else if (_phase->C->get_alias_index(u->adr_type()) == alias) {
4067         Node* m = find_mem(_phase->ctrl_or_self(u), u);
4068         if (m != mem) {
4069           DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
4070           _phase->igvn().replace_input_of(u, u->find_edge(mem), m);
4071           --i;
4072         }
4073       } else if (u->adr_type() != TypePtr::BOTTOM &&
4074                  _memory_nodes[_phase->ctrl_or_self(u)->_idx] == u) {
4075         Node* m = find_mem(_phase->ctrl_or_self(u), u);
4076         assert(m != mem, "");
4077         // u is on the wrong slice...
4078         assert(u->is_ClearArray(), "");
4079         DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
4080         _phase->igvn().replace_input_of(u, u->find_edge(mem), m);
4081         --i;
4082       }
4083     }
4084   }
4085 #ifdef ASSERT
4086   assert(new_mem->outcnt() > 0, "");
4087   for (int i = 0; i < phis.length(); i++) {
4088     Node* n = phis.at(i);
4089     assert(n->outcnt() > 0, "new phi must have uses now");
4090   }
4091 #endif
4092 }
4093 
4094 MergeMemNode* MemoryGraphFixer::allocate_merge_mem(Node* mem, Node* rep_proj, Node* rep_ctrl) const {
4095   MergeMemNode* mm = MergeMemNode::make(mem);
4096   mm->set_memory_at(_alias, rep_proj);
4097   _phase->register_new_node(mm, rep_ctrl);
4098   return mm;
4099 }
4100 
4101 MergeMemNode* MemoryGraphFixer::clone_merge_mem(Node* u, Node* mem, Node* rep_proj, Node* rep_ctrl, DUIterator& i) const {
4102   MergeMemNode* newmm = NULL;
4103   MergeMemNode* u_mm = u->as_MergeMem();
4104   Node* c = _phase->get_ctrl(u);
4105   if (_phase->is_dominator(c, rep_ctrl)) {
4106     c = rep_ctrl;
4107   } else {
4108     assert(_phase->is_dominator(rep_ctrl, c), "one must dominate the other");
4109   }
4110   if (u->outcnt() == 1) {
4111     if (u->req() > (uint)_alias && u->in(_alias) == mem) {
4112       _phase->igvn().replace_input_of(u, _alias, rep_proj);
4113       --i;
4114     } else {
4115       _phase->igvn().rehash_node_delayed(u);
4116       u_mm->set_memory_at(_alias, rep_proj);
4117     }
4118     newmm = u_mm;
4119     _phase->set_ctrl_and_loop(u, c);
4120   } else {
4121     // can't simply clone u and then change one of its input because
4122     // it adds and then removes an edge which messes with the
4123     // DUIterator
4124     newmm = MergeMemNode::make(u_mm->base_memory());
4125     for (uint j = 0; j < u->req(); j++) {
4126       if (j < newmm->req()) {
4127         if (j == (uint)_alias) {
4128           newmm->set_req(j, rep_proj);
4129         } else if (newmm->in(j) != u->in(j)) {
4130           newmm->set_req(j, u->in(j));
4131         }
4132       } else if (j == (uint)_alias) {
4133         newmm->add_req(rep_proj);
4134       } else {
4135         newmm->add_req(u->in(j));
4136       }
4137     }
4138     if ((uint)_alias >= u->req()) {
4139       newmm->set_memory_at(_alias, rep_proj);
4140     }
4141     _phase->register_new_node(newmm, c);
4142   }
4143   return newmm;
4144 }
4145 
4146 bool MemoryGraphFixer::should_process_phi(Node* phi) const {
4147   if (phi->adr_type() == TypePtr::BOTTOM) {
4148     Node* region = phi->in(0);
4149     for (DUIterator_Fast jmax, j = region->fast_outs(jmax); j < jmax; j++) {
4150       Node* uu = region->fast_out(j);
4151       if (uu->is_Phi() && uu != phi && uu->bottom_type() == Type::MEMORY && _phase->C->get_alias_index(uu->adr_type()) == _alias) {
4152         return false;
4153       }
4154     }
4155     return true;
4156   }
4157   return _phase->C->get_alias_index(phi->adr_type()) == _alias;
4158 }
4159 
4160 void MemoryGraphFixer::fix_memory_uses(Node* mem, Node* replacement, Node* rep_proj, Node* rep_ctrl) const {
4161   uint last = _phase-> C->unique();
4162   MergeMemNode* mm = NULL;
4163   assert(mem->bottom_type() == Type::MEMORY, "");
4164   for (DUIterator i = mem->outs(); mem->has_out(i); i++) {
4165     Node* u = mem->out(i);
4166     if (u != replacement && u->_idx < last) {
4167       if (u->is_ShenandoahBarrier() && _alias != Compile::AliasIdxRaw) {
4168         if (_phase->C->get_alias_index(u->adr_type()) == _alias && ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4169           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
4170           assert(u->find_edge(mem) == -1, "only one edge");
4171           --i;
4172         }
4173       } else if (u->is_Mem()) {
4174         if (_phase->C->get_alias_index(u->adr_type()) == _alias && ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4175           assert(_alias == Compile::AliasIdxRaw , "only raw memory can lead to a memory operation");
4176           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
4177           assert(u->find_edge(mem) == -1, "only one edge");
4178           --i;
4179         }
4180       } else if (u->is_MergeMem()) {
4181         MergeMemNode* u_mm = u->as_MergeMem();
4182         if (u_mm->memory_at(_alias) == mem) {
4183           MergeMemNode* newmm = NULL;
4184           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
4185             Node* uu = u->fast_out(j);
4186             assert(!uu->is_MergeMem(), "chain of MergeMems?");
4187             if (uu->is_Phi()) {
4188               if (should_process_phi(uu)) {
4189                 Node* region = uu->in(0);
4190                 int nb = 0;
4191                 for (uint k = 1; k < uu->req(); k++) {
4192                   if (uu->in(k) == u && _phase->is_dominator(rep_ctrl, region->in(k))) {
4193                     if (newmm == NULL) {
4194                       newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
4195                     }
4196                     if (newmm != u) {
4197                       _phase->igvn().replace_input_of(uu, k, newmm);
4198                       nb++;
4199                       --jmax;
4200                     }
4201                   }
4202                 }
4203                 if (nb > 0) {
4204                   --j;
4205                 }
4206               }
4207             } else {
4208               if (rep_ctrl != uu && ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(uu), replacement, uu, _phase)) {
4209                 if (newmm == NULL) {
4210                   newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
4211                 }
4212                 if (newmm != u) {
4213                   _phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
4214                   --j, --jmax;
4215                 }
4216               }
4217             }
4218           }
4219         }
4220       } else if (u->is_Phi()) {
4221         assert(u->bottom_type() == Type::MEMORY, "what else?");
4222         Node* region = u->in(0);
4223         if (should_process_phi(u)) {
4224           bool replaced = false;
4225           for (uint j = 1; j < u->req(); j++) {
4226             if (u->in(j) == mem && _phase->is_dominator(rep_ctrl, region->in(j))) {
4227               Node* nnew = rep_proj;
4228               if (u->adr_type() == TypePtr::BOTTOM) {
4229                 if (mm == NULL) {
4230                   mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
4231                 }
4232                 nnew = mm;
4233               }
4234               _phase->igvn().replace_input_of(u, j, nnew);
4235               replaced = true;
4236             }
4237           }
4238           if (replaced) {
4239             --i;
4240           }
4241 
4242         }
4243       } else if ((u->adr_type() == TypePtr::BOTTOM && u->Opcode() != Op_StrInflatedCopy) ||
4244                  u->adr_type() == NULL) {
4245         assert(u->adr_type() != NULL ||
4246                u->Opcode() == Op_Rethrow ||
4247                u->Opcode() == Op_Return ||
4248                u->Opcode() == Op_SafePoint ||
4249                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
4250                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
4251                u->Opcode() == Op_CallLeaf, "");
4252         if (ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4253           if (mm == NULL) {
4254             mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
4255           }
4256           _phase->igvn().replace_input_of(u, u->find_edge(mem), mm);
4257           --i;
4258         }
4259       } else if (_phase->C->get_alias_index(u->adr_type()) == _alias) {
4260         if (ShenandoahWriteBarrierNode::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
4261           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
4262           --i;
4263         }
4264       }
4265     }
4266   }
4267 }
4268 
4269 void MemoryGraphFixer::remove(Node* n) {
4270   assert(n->Opcode() == Op_ShenandoahWBMemProj, "");
4271   Node* c = _phase->get_ctrl(n);
4272   Node* mem = find_mem(c, NULL);
4273   if (mem == n) {
4274     _memory_nodes.map(c->_idx, mem->in(ShenandoahWBMemProjNode::WriteBarrier)->in(ShenandoahBarrierNode::Memory));
4275   }
4276 }
4277 
4278