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 #include "gc_implementation/shenandoah/shenandoahBrooksPointer.hpp"
  26 #include "gc_implementation/shenandoah/shenandoahHeap.hpp"
  27 #include "gc_implementation/shenandoah/shenandoahHeapRegion.hpp"
  28 #include "opto/callnode.hpp"
  29 #include "opto/connode.hpp"
  30 #include "opto/phaseX.hpp"
  31 #include "opto/rootnode.hpp"
  32 #include "opto/runtime.hpp"
  33 #include "opto/shenandoahSupport.hpp"
  34 #include "opto/subnode.hpp"
  35 
  36 Node* ShenandoahBarrierNode::skip_through_barrier(Node* n) {
  37   if (!UseShenandoahGC) {
  38     return n;
  39   }
  40   if (n == NULL) {
  41     return NULL;
  42   } else if (n->is_ShenandoahBarrier()) {
  43     return n->in(ValueIn);
  44   } else if (n->is_Phi() &&
  45              n->req() == 3 &&
  46              n->in(1) != NULL &&
  47              n->in(1)->is_ShenandoahBarrier() &&
  48              n->in(2) != NULL &&
  49              n->in(2)->bottom_type() == TypePtr::NULL_PTR &&
  50              n->in(0) != NULL &&
  51              n->in(0)->in(1) != NULL &&
  52              n->in(0)->in(1)->is_IfProj() &&
  53              n->in(0)->in(2) != NULL &&
  54              n->in(0)->in(2)->is_IfProj() &&
  55              n->in(0)->in(1)->in(0) != NULL &&
  56              n->in(0)->in(1)->in(0) == n->in(0)->in(2)->in(0) &&
  57              n->in(1)->in(ShenandoahBarrierNode::ValueIn)->Opcode() == Op_CastPP) {
  58     Node* iff = n->in(0)->in(1)->in(0);
  59     Node* res = n->in(1)->in(ShenandoahBarrierNode::ValueIn)->in(1);
  60     if (iff->is_If() &&
  61         iff->in(1) != NULL &&
  62         iff->in(1)->is_Bool() &&
  63         iff->in(1)->as_Bool()->_test._test == BoolTest::ne &&
  64         iff->in(1)->in(1) != NULL &&
  65         iff->in(1)->in(1)->Opcode() == Op_CmpP &&
  66         iff->in(1)->in(1)->in(1) != NULL &&
  67         iff->in(1)->in(1)->in(1) == res &&
  68         iff->in(1)->in(1)->in(2) != NULL &&
  69         iff->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
  70       return res;
  71     }
  72   }
  73   return n;
  74 }
  75 
  76 bool ShenandoahBarrierNode::needs_barrier(PhaseTransform* phase, ShenandoahBarrierNode* orig, Node* n, Node* rb_mem, bool allow_fromspace) {
  77   Unique_Node_List visited;
  78   return needs_barrier_impl(phase, orig, n, rb_mem, allow_fromspace, visited);
  79 }
  80 
  81 bool ShenandoahBarrierNode::needs_barrier_impl(PhaseTransform* phase, ShenandoahBarrierNode* orig, Node* n, Node* rb_mem, bool allow_fromspace, Unique_Node_List &visited) {
  82 
  83   if (visited.member(n)) {
  84     return false; // Been there.
  85   }
  86   visited.push(n);
  87 
  88   if (n->is_Allocate()) {
  89     return false;
  90   }
  91 
  92   if (n->is_CallJava() || n->Opcode() == Op_CallLeafNoFP) {
  93     return true;
  94   }
  95 
  96   const Type* type = phase->type(n);
  97   if (type == Type::TOP) {
  98     return false;
  99   }
 100   if (type->make_ptr()->higher_equal(TypePtr::NULL_PTR)) {
 101     return false;
 102   }
 103   if (type->make_oopptr() && type->make_oopptr()->const_oop() != NULL) {
 104     return false;
 105   }
 106 
 107   if (ShenandoahOptimizeStableFinals) {
 108     const TypeAryPtr* ary = type->isa_aryptr();
 109     if (ary && ary->is_stable() && allow_fromspace) {
 110       return false;
 111     }
 112   }
 113 
 114   if (n->is_CheckCastPP() || n->is_ConstraintCast()) {
 115     return needs_barrier_impl(phase, orig, n->in(1), rb_mem, allow_fromspace, visited);
 116   }
 117   if (n->is_Parm()) {
 118     return true;
 119   }
 120   if (n->is_Proj()) {
 121     return needs_barrier_impl(phase, orig, n->in(0), rb_mem, allow_fromspace, visited);
 122   }
 123   if (n->is_Phi()) {
 124     bool need_barrier = false;
 125     for (uint i = 1; i < n->req() && ! need_barrier; i++) {
 126       Node* input = n->in(i);
 127       if (input == NULL) {
 128         need_barrier = true; // Phi not complete yet?
 129       } else if (needs_barrier_impl(phase, orig, input, rb_mem, allow_fromspace, visited)) {
 130         need_barrier = true;
 131       }
 132     }
 133     return need_barrier;
 134   }
 135   if (n->is_CMove()) {
 136     return needs_barrier_impl(phase, orig, n->in(CMoveNode::IfFalse), rb_mem, allow_fromspace, visited) ||
 137            needs_barrier_impl(phase, orig, n->in(CMoveNode::IfTrue ), rb_mem, allow_fromspace, visited);
 138   }
 139   if (n->Opcode() == Op_CreateEx) {
 140     return true;
 141   }
 142   if (n->Opcode() == Op_ShenandoahWriteBarrier) {
 143     return false;
 144   }
 145   if (n->Opcode() == Op_ShenandoahReadBarrier) {
 146     if (rb_mem == n->in(Memory)) {
 147       return false;
 148     } else {
 149       return true;
 150     }
 151   }
 152 
 153   if (n->Opcode() == Op_LoadP ||
 154       n->Opcode() == Op_LoadN ||
 155       n->Opcode() == Op_GetAndSetP ||
 156       n->Opcode() == Op_GetAndSetN) {
 157     return true;
 158   }
 159   if (n->Opcode() == Op_DecodeN ||
 160       n->Opcode() == Op_EncodeP) {
 161     return needs_barrier_impl(phase, orig, n->in(1), rb_mem, allow_fromspace, visited);
 162   }
 163 
 164 #ifdef ASSERT
 165   tty->print("need barrier on?: "); n->dump();
 166   ShouldNotReachHere();
 167 #endif
 168   return true;
 169 }
 170 
 171 bool ShenandoahReadBarrierNode::dominates_memory_rb_impl(PhaseTransform* phase,
 172                                                          Node* b1,
 173                                                          Node* b2,
 174                                                          Node* current,
 175                                                          bool linear) {
 176   ResourceMark rm;
 177   VectorSet visited(Thread::current()->resource_area());
 178   Node_Stack phis(0);
 179 
 180   for(int i = 0; i < 10; i++) {
 181     if (current == NULL) {
 182       return false;
 183     } else if (visited.test_set(current->_idx) || current->is_top() || current == b1) {
 184       current = NULL;
 185       while (phis.is_nonempty() && current == NULL) {
 186         uint idx = phis.index();
 187         Node* phi = phis.node();
 188         if (idx >= phi->req()) {
 189           phis.pop();
 190         } else {
 191           current = phi->in(idx);
 192           phis.set_index(idx+1);
 193         }
 194       }
 195       if (current == NULL) {
 196         return true;
 197       }
 198     } else if (current == phase->C->immutable_memory()) {
 199       return false;
 200     } else if (current->isa_Phi()) {
 201       if (!linear) {
 202         return false;
 203       }
 204       phis.push(current, 2);
 205       current = current->in(1);
 206     } else if (current->Opcode() == Op_ShenandoahWriteBarrier) {
 207       const Type* in_type = current->bottom_type();
 208       const Type* this_type = b2->bottom_type();
 209       if (is_independent(in_type, this_type)) {
 210         current = current->in(Memory);
 211       } else {
 212         return false;
 213       }
 214     } else if (current->Opcode() == Op_ShenandoahWBMemProj) {
 215       current = current->in(0);
 216     } else if (current->is_Proj()) {
 217       current = current->in(0);
 218     } else if (current->is_Call()) {
 219       return false; // TODO: Maybe improve by looking at the call's memory effects?
 220     } else if (current->is_MemBar()) {
 221       return false; // TODO: Do we need to stop at *any* membar?
 222     } else if (current->is_MergeMem()) {
 223       const TypePtr* adr_type = brooks_pointer_type(phase->type(b2));
 224       uint alias_idx = phase->C->get_alias_index(adr_type);
 225       current = current->as_MergeMem()->memory_at(alias_idx);
 226     } else {
 227 #ifdef ASSERT
 228       current->dump();
 229 #endif
 230       ShouldNotReachHere();
 231       return false;
 232     }
 233   }
 234   return false;
 235 }
 236 
 237 bool ShenandoahReadBarrierNode::is_independent(Node* mem) {
 238   if (mem->is_Phi() || mem->is_Proj() || mem->is_MergeMem()) {
 239     return true;
 240   } else if (mem->Opcode() == Op_ShenandoahWriteBarrier) {
 241     const Type* mem_type = mem->bottom_type();
 242     const Type* this_type = bottom_type();
 243     if (is_independent(mem_type, this_type)) {
 244       return true;
 245     } else {
 246       return false;
 247     }
 248   } else if (mem->is_Call() || mem->is_MemBar()) {
 249     return false;
 250   }
 251 #ifdef ASSERT
 252   mem->dump();
 253 #endif
 254   ShouldNotReachHere();
 255   return true;
 256 }
 257 
 258 
 259 bool ShenandoahReadBarrierNode::dominates_memory_rb(PhaseTransform* phase, Node* b1, Node* b2, bool linear) {
 260   return dominates_memory_rb_impl(phase, b1->in(Memory), b2, b2->in(Memory), linear);
 261 }
 262 
 263 bool ShenandoahReadBarrierNode::is_independent(const Type* in_type, const Type* this_type) {
 264   assert(in_type->isa_oopptr(), "expect oop ptr");
 265   assert(this_type->isa_oopptr(), "expect oop ptr");
 266 
 267   ciKlass* in_kls = in_type->is_oopptr()->klass();
 268   ciKlass* this_kls = this_type->is_oopptr()->klass();
 269   if (in_kls != NULL && this_kls != NULL &&
 270       in_kls->is_loaded() && this_kls->is_loaded() &&
 271       (!in_kls->is_subclass_of(this_kls)) &&
 272       (!this_kls->is_subclass_of(in_kls))) {
 273     return true;
 274   }
 275   return false;
 276 }
 277 
 278 Node* ShenandoahReadBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 279 
 280   if (! can_reshape) {
 281     return NULL;
 282   }
 283 
 284   if (in(Memory) == phase->C->immutable_memory()) return NULL;
 285 
 286   // If memory input is a MergeMem, take the appropriate slice out of it.
 287   Node* mem_in = in(Memory);
 288   if (mem_in->isa_MergeMem()) {
 289     const TypePtr* adr_type = brooks_pointer_type(bottom_type());
 290     uint alias_idx = phase->C->get_alias_index(adr_type);
 291     mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);
 292     set_req(Memory, mem_in);
 293     return this;
 294   }
 295 
 296   Node* input = in(Memory);
 297   if (input->Opcode() == Op_ShenandoahWBMemProj) {
 298     Node* wb = input->in(0);
 299     const Type* in_type = phase->type(wb);
 300     // is_top() test not sufficient here: we can come here after CCP
 301     // in a dead branch of the graph that has not yet been removed.
 302     if (in_type == Type::TOP) return NULL; // Dead path.
 303     assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "expect write barrier");
 304     if (is_independent(in_type, _type)) {
 305       if (phase->is_IterGVN()) {
 306         phase->is_IterGVN()->rehash_node_delayed(wb);
 307       }
 308       set_req(Memory, wb->in(Memory));
 309       if (can_reshape && input->outcnt() == 0) {
 310         phase->is_IterGVN()->_worklist.push(input);
 311       }
 312       return this;
 313     }
 314   }
 315   return NULL;
 316 }
 317 
 318 Node* ShenandoahWriteBarrierNode::Identity(PhaseTransform* phase) {
 319   assert(in(0) != NULL, "should have control");
 320   PhaseIterGVN* igvn = phase->is_IterGVN();
 321   Node* mem_in = in(Memory);
 322   Node* mem_proj = NULL;
 323 
 324   if (igvn != NULL) {
 325     mem_proj = find_out_with(Op_ShenandoahWBMemProj);
 326     if (mem_proj == NULL || mem_in == mem_proj) {
 327       return this;
 328     }
 329   }
 330 
 331   Node* replacement = Identity_impl(phase);
 332   if (igvn != NULL) {
 333     if (replacement != NULL && replacement != this) {
 334       igvn->replace_node(mem_proj, mem_in);
 335     }
 336   }
 337   return replacement;
 338 }
 339 
 340 
 341 Node* ShenandoahWriteBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 342   assert(in(0) != NULL, "should have control");
 343   if (!can_reshape) {
 344     return NULL;
 345   }
 346 
 347   PhaseIterGVN* igvn = phase->is_IterGVN();
 348   Node* mem_proj = find_out_with(Op_ShenandoahWBMemProj);
 349   Node* mem_in = in(Memory);
 350 
 351   if (mem_in == phase->C->immutable_memory()) return NULL;
 352 
 353   if (mem_in->isa_MergeMem()) {
 354     const TypePtr* adr_type = brooks_pointer_type(bottom_type());
 355     uint alias_idx = phase->C->get_alias_index(adr_type);
 356     mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);
 357     set_req(Memory, mem_in);
 358     return this;
 359   }
 360 
 361   return NULL;
 362 }
 363 
 364 bool ShenandoahBarrierNode::dominates_memory_impl(PhaseTransform* phase,
 365                                                   Node* b1,
 366                                                   Node* b2,
 367                                                   Node* current,
 368                                                   bool linear) {
 369   ResourceMark rm;
 370   VectorSet visited(Thread::current()->resource_area());
 371   Node_Stack phis(0);
 372 
 373 
 374   for(int i = 0; i < 10; i++) {
 375     if (current == NULL) {
 376       return false;
 377     } else if (visited.test_set(current->_idx) || current->is_top() || current == b1) {
 378       current = NULL;
 379       while (phis.is_nonempty() && current == NULL) {
 380         uint idx = phis.index();
 381         Node* phi = phis.node();
 382         if (idx >= phi->req()) {
 383           phis.pop();
 384         } else {
 385           current = phi->in(idx);
 386           phis.set_index(idx+1);
 387         }
 388       }
 389       if (current == NULL) {
 390         return true;
 391       }
 392     } else if (current == b2) {
 393       return false;
 394     } else if (current == phase->C->immutable_memory()) {
 395       return false;
 396     } else if (current->isa_Phi()) {
 397       if (!linear) {
 398         return false;
 399       }
 400       phis.push(current, 2);
 401       current = current->in(1);
 402     } else if (current->Opcode() == Op_ShenandoahWriteBarrier) {
 403       current = current->in(Memory);
 404     } else if (current->Opcode() == Op_ShenandoahWBMemProj) {
 405       current = current->in(0);
 406     } else if (current->is_Proj()) {
 407       current = current->in(0);
 408     } else if (current->is_Call()) {
 409       current = current->in(TypeFunc::Memory);
 410     } else if (current->is_MemBar()) {
 411       current = current->in(TypeFunc::Memory);
 412     } else if (current->is_MergeMem()) {
 413       const TypePtr* adr_type = brooks_pointer_type(phase->type(b2));
 414       uint alias_idx = phase->C->get_alias_index(adr_type);
 415       current = current->as_MergeMem()->memory_at(alias_idx);
 416     } else {
 417 #ifdef ASSERT
 418       current->dump();
 419 #endif
 420       ShouldNotReachHere();
 421       return false;
 422     }
 423   }
 424   return false;
 425 }
 426 
 427 /**
 428  * Determines if b1 dominates b2 through memory inputs. It returns true if:
 429  * - b1 can be reached by following each branch in b2's memory input (through phis, etc)
 430  * - or we get back to b2 (i.e. through a loop) without seeing b1
 431  * In all other cases, (in particular, if we reach immutable_memory without having seen b1)
 432  * we return false.
 433  */
 434 bool ShenandoahBarrierNode::dominates_memory(PhaseTransform* phase, Node* b1, Node* b2, bool linear) {
 435   return dominates_memory_impl(phase, b1, b2, b2->in(Memory), linear);
 436 }
 437 
 438 Node* ShenandoahBarrierNode::Identity_impl(PhaseTransform* phase) {
 439   Node* n = in(ValueIn);
 440 
 441   Node* rb_mem = Opcode() == Op_ShenandoahReadBarrier ? in(Memory) : NULL;
 442   if (! needs_barrier(phase, this, n, rb_mem, _allow_fromspace)) {
 443     return n;
 444   }
 445 
 446   // Try to find a write barrier sibling with identical inputs that we can fold into.
 447   for (DUIterator i = n->outs(); n->has_out(i); i++) {
 448     Node* sibling = n->out(i);
 449     if (sibling == this) {
 450       continue;
 451     }
 452     if (sibling->Opcode() != Op_ShenandoahWriteBarrier) {
 453       continue;
 454     }
 455 
 456     assert(sibling->in(ValueIn) == in(ValueIn), "sanity");
 457     assert(sibling->Opcode() == Op_ShenandoahWriteBarrier, "sanity");
 458 
 459     if (dominates_memory(phase, sibling, this, phase->is_IterGVN() == NULL)) {
 460       return sibling;
 461     }
 462   }
 463   return this;
 464 }
 465 
 466 #ifndef PRODUCT
 467 void ShenandoahBarrierNode::dump_spec(outputStream *st) const {
 468   const TypePtr* adr = adr_type();
 469   if (adr == NULL) {
 470     return;
 471   }
 472   st->print(" @");
 473   adr->dump_on(st);
 474   st->print(" (");
 475   Compile::current()->alias_type(adr)->adr_type()->dump_on(st);
 476   st->print(") ");
 477 }
 478 #endif
 479 
 480 Node* ShenandoahReadBarrierNode::Identity(PhaseTransform* phase) {
 481   Node* id = Identity_impl(phase);
 482 
 483   if (id == this && phase->is_IterGVN()) {
 484     Node* n = in(ValueIn);
 485     // No success in super call. Try to combine identical read barriers.
 486     for (DUIterator i = n->outs(); n->has_out(i); i++) {
 487       Node* sibling = n->out(i);
 488       if (sibling == this || sibling->Opcode() != Op_ShenandoahReadBarrier) {
 489         continue;
 490       }
 491       assert(sibling->in(ValueIn)  == in(ValueIn), "sanity");
 492       if (phase->is_IterGVN()->hash_find(sibling) &&
 493           sibling->bottom_type() == bottom_type() &&
 494           sibling->in(Control) == in(Control) &&
 495           dominates_memory_rb(phase, sibling, this, phase->is_IterGVN() == NULL)) {
 496         return sibling;
 497       }
 498     }
 499   }
 500   return id;
 501 }
 502 
 503 const Type* ShenandoahBarrierNode::Value(PhaseTransform* phase) const {
 504   // Either input is TOP ==> the result is TOP
 505   const Type *t1 = phase->type(in(Memory));
 506   if (t1 == Type::TOP) return Type::TOP;
 507   const Type *t2 = phase->type(in(ValueIn));
 508   if( t2 == Type::TOP ) return Type::TOP;
 509 
 510   Node* input = in(ValueIn);
 511   const Type* type = phase->type(input)->is_oopptr()->cast_to_nonconst();
 512   return type->filter_speculative(_type);
 513 }
 514 
 515 uint ShenandoahBarrierNode::hash() const {
 516   return TypeNode::hash() + _allow_fromspace;
 517 }
 518 
 519 uint ShenandoahBarrierNode::cmp(const Node& n) const {
 520   return _allow_fromspace == ((ShenandoahBarrierNode&) n)._allow_fromspace
 521     && TypeNode::cmp(n);
 522 }
 523 
 524 uint ShenandoahBarrierNode::size_of() const {
 525   return sizeof(*this);
 526 }
 527 
 528 Node* ShenandoahWBMemProjNode::Identity(PhaseTransform* phase) {
 529 
 530   Node* wb = in(0);
 531   if (wb->is_top()) return phase->C->top(); // Dead path.
 532 
 533   assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "expect write barrier");
 534   PhaseIterGVN* igvn = phase->is_IterGVN();
 535   // We can't do the below unless the graph is fully constructed.
 536   if (igvn == NULL) {
 537     return this;
 538   }
 539 
 540   // If the mem projection has no barrier users, it's not needed anymore.
 541   Unique_Node_List visited;
 542   if (wb->outcnt() == 1) {
 543     return wb->in(ShenandoahBarrierNode::Memory);
 544   }
 545 
 546   return this;
 547 }
 548 
 549 #ifdef ASSERT
 550 bool ShenandoahBarrierNode::verify_helper(Node* in, Node_Stack& phis, VectorSet& visited, verify_type t, bool trace, Unique_Node_List& barriers_used) {
 551   assert(phis.size() == 0, "");
 552 
 553   while (true) {
 554     if (!in->bottom_type()->make_ptr()->isa_oopptr()) {
 555       if (trace) {tty->print_cr("Non oop");}
 556     } else if (t == ShenandoahLoad && ShenandoahOptimizeStableFinals &&
 557                in->bottom_type()->make_ptr()->isa_aryptr() &&
 558                in->bottom_type()->make_ptr()->is_aryptr()->is_stable()) {
 559       if (trace) {tty->print_cr("Stable array load");}
 560     } else {
 561       if (in->Opcode() == Op_CastPP || in->Opcode() == Op_CheckCastPP) {
 562         in = in->in(1);
 563         continue;
 564       } else if (in->is_AddP()) {
 565         assert(!in->in(AddPNode::Address)->is_top(), "no raw memory access");
 566         in = in->in(AddPNode::Address);
 567         continue;
 568       } else if (in->is_Con()) {
 569         if (trace) {tty->print("Found constant"); in->dump();}
 570       } else if (in->is_ShenandoahBarrier()) {
 571         if (t == ShenandoahStore && in->Opcode() != Op_ShenandoahWriteBarrier) {
 572           return false;
 573         }
 574         barriers_used.push(in);
 575         if (trace) {tty->print("Found barrier"); in->dump();}
 576       } else if (in->is_Proj() && in->in(0)->is_Allocate()) {
 577         if (trace) {tty->print("Found alloc"); in->in(0)->dump();}
 578       } else if (in->is_Phi()) {
 579         if (!visited.test_set(in->_idx)) {
 580           if (trace) {tty->print("Pushed phi:"); in->dump();}
 581           phis.push(in, 2);
 582           in = in->in(1);
 583           continue;
 584         }
 585         if (trace) {tty->print("Already seen phi:"); in->dump();}
 586       } else if (in->Opcode() == Op_CMoveP || in->Opcode() == Op_CMoveN) {
 587         if (!visited.test_set(in->_idx)) {
 588           if (trace) {tty->print("Pushed cmovep:"); in->dump();}
 589           phis.push(in, CMoveNode::IfTrue);
 590           in = in->in(CMoveNode::IfFalse);
 591           continue;
 592         }
 593         if (trace) {tty->print("Already seen cmovep:"); in->dump();}
 594       } else if (in->Opcode() == Op_EncodeP || in->Opcode() == Op_DecodeN) {
 595         in = in->in(1);
 596         continue;
 597       } else {
 598         return false;
 599       }
 600     }
 601     bool cont = false;
 602     while (phis.is_nonempty()) {
 603       uint idx = phis.index();
 604       Node* phi = phis.node();
 605       if (idx >= phi->req()) {
 606         if (trace) {tty->print("Popped phi:"); phi->dump();}
 607         phis.pop();
 608         continue;
 609       }
 610       if (trace) {tty->print("Next entry(%d) for phi:", idx); phi->dump();}
 611       in = phi->in(idx);
 612       phis.set_index(idx+1);
 613       cont = true;
 614       break;
 615     }
 616     if (!cont) {
 617       break;
 618     }
 619   }
 620   return true;
 621 }
 622 
 623 void ShenandoahBarrierNode::report_verify_failure(const char *msg, Node *n1, Node *n2) {
 624   if (n1 != NULL) {
 625     n1->dump(+10);
 626   }
 627   if (n2 != NULL) {
 628     n2->dump(+10);
 629   }
 630   fatal(msg);
 631 }
 632 
 633 void ShenandoahBarrierNode::verify(RootNode* root) {
 634   ResourceMark rm;
 635   Unique_Node_List wq;
 636   GrowableArray<Node*> barriers;
 637   Unique_Node_List barriers_used;
 638   Node_Stack phis(0);
 639   VectorSet visited(Thread::current()->resource_area());
 640   const bool trace = false;
 641   const bool verify_no_useless_barrier = false;
 642 
 643   wq.push(root);
 644   for (uint next = 0; next < wq.size(); next++) {
 645     Node *n = wq.at(next);
 646     if (n->is_Load()) {
 647       const bool trace = false;
 648       if (trace) {tty->print("Verifying"); n->dump();}
 649       if (n->Opcode() == Op_LoadRange || n->Opcode() == Op_LoadKlass || n->Opcode() == Op_LoadNKlass) {
 650         if (trace) {tty->print_cr("Load range/klass");}
 651       } else {
 652         const TypePtr* adr_type = n->as_Load()->adr_type();
 653 
 654         if (adr_type->isa_oopptr() && adr_type->is_oopptr()->offset() == oopDesc::mark_offset_in_bytes()) {
 655           if (trace) {tty->print_cr("Mark load");}
 656         } else if (adr_type->isa_instptr() &&
 657                    adr_type->is_instptr()->klass()->is_subtype_of(Compile::current()->env()->Reference_klass()) &&
 658                    adr_type->is_instptr()->offset() == java_lang_ref_Reference::referent_offset) {
 659           if (trace) {tty->print_cr("Reference.get()");}
 660         } else {
 661           bool verify = true;
 662           if (adr_type->isa_instptr()) {
 663             ciKlass* k = adr_type->is_instptr()->klass();
 664             assert(k->is_instance_klass(), "");
 665             ciInstanceKlass* ik = (ciInstanceKlass*)k;
 666             int offset = adr_type->offset();
 667 
 668             if ((ik->debug_final_field_at(offset) && ShenandoahOptimizeInstanceFinals) ||
 669                 (ik->debug_stable_field_at(offset) && ShenandoahOptimizeStableFinals)) {
 670               if (trace) {tty->print_cr("Final/stable");}
 671               verify = false;
 672             }
 673           }
 674 
 675           if (verify && !ShenandoahBarrierNode::verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahLoad, trace, barriers_used)) {
 676             report_verify_failure("Shenandoah verification: Load should have barriers", n);
 677           }
 678         }
 679       }
 680     } else if (n->is_Store()) {
 681       const bool trace = false;
 682 
 683       if (trace) {tty->print("Verifying"); n->dump();}
 684       if (n->in(MemNode::ValueIn)->bottom_type()->isa_oopptr()) {
 685         Node* adr = n->in(MemNode::Address);
 686         bool verify = true;
 687 
 688         if (adr->is_AddP() && adr->in(AddPNode::Base)->is_top()) {
 689           adr = adr->in(AddPNode::Address);
 690           if (adr->is_AddP()) {
 691             assert(adr->in(AddPNode::Base)->is_top(), "");
 692             adr = adr->in(AddPNode::Address);
 693             if (adr->Opcode() == Op_LoadP &&
 694                 adr->in(MemNode::Address)->in(AddPNode::Base)->is_top() &&
 695                 adr->in(MemNode::Address)->in(AddPNode::Address)->Opcode() == Op_ThreadLocal &&
 696                 adr->in(MemNode::Address)->in(AddPNode::Offset)->find_intptr_t_con(-1) == in_bytes(JavaThread::satb_mark_queue_offset() +
 697                                                                                               PtrQueue::byte_offset_of_buf())) {
 698               if (trace) {tty->print_cr("G1 prebarrier");}
 699               verify = false;
 700             }
 701           }
 702         }
 703 
 704         if (verify && !ShenandoahBarrierNode::verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahValue, trace, barriers_used)) {
 705           report_verify_failure("Shenandoah verification: Store should have barriers", n);
 706         }
 707       }
 708       if (!ShenandoahBarrierNode::verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 709         report_verify_failure("Shenandoah verification: Store (address) should have barriers", n);
 710       }
 711     } else if (n->is_ClearArray()) {
 712       if (!ShenandoahBarrierNode::verify_helper(n->in(3), phis, visited, ShenandoahStore, trace, barriers_used)) {
 713         report_verify_failure("Shenandoah verification: ClearArray should have barriers", n);
 714       }
 715     } else if (n->Opcode() == Op_CmpP) {
 716       const bool trace = false;
 717 
 718       Node* in1 = n->in(1);
 719       Node* in2 = n->in(2);
 720       if (in1->bottom_type()->isa_oopptr()) {
 721         if (trace) {tty->print("Verifying"); n->dump();}
 722 
 723         bool mark_inputs = false;
 724         if (in1->is_Con() || in2->is_Con()) {
 725           if (trace) {tty->print_cr("Comparison against a constant");}
 726           mark_inputs = true;
 727         } else if ((in1->is_CheckCastPP() && in1->in(1)->is_Proj() && in1->in(1)->in(0)->is_Allocate()) ||
 728                    (in2->is_CheckCastPP() && in2->in(1)->is_Proj() && in2->in(1)->in(0)->is_Allocate())) {
 729           if (trace) {tty->print_cr("Comparison with newly alloc'ed object");}
 730           mark_inputs = true;
 731         } else {
 732           assert(in2->bottom_type()->isa_oopptr(), "");
 733 
 734           if (!ShenandoahBarrierNode::verify_helper(in1, phis, visited, ShenandoahStore, trace, barriers_used) ||
 735               !ShenandoahBarrierNode::verify_helper(in2, phis, visited, ShenandoahStore, trace, barriers_used)) {
 736             report_verify_failure("Shenandoah verification: Cmp should have barriers", n);
 737           }
 738         }
 739         if (verify_no_useless_barrier &&
 740             mark_inputs &&
 741             (!ShenandoahBarrierNode::verify_helper(in1, phis, visited, ShenandoahValue, trace, barriers_used) ||
 742              !ShenandoahBarrierNode::verify_helper(in2, phis, visited, ShenandoahValue, trace, barriers_used))) {
 743           phis.clear();
 744           visited.Reset();
 745         }
 746       }
 747     } else if (n->is_LoadStore()) {
 748       if (n->in(MemNode::ValueIn)->bottom_type()->make_ptr() &&
 749           !ShenandoahBarrierNode::verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahValue, trace, barriers_used)) {
 750         report_verify_failure("Shenandoah verification: LoadStore (value) should have barriers", n);
 751       }
 752 
 753       if (n->in(MemNode::Address)->bottom_type()->make_oopptr() && !ShenandoahBarrierNode::verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 754         report_verify_failure("Shenandoah verification: LoadStore (address) should have barriers", n);
 755       }
 756     } else if (n->Opcode() == Op_CallLeafNoFP || n->Opcode() == Op_CallLeaf) {
 757       CallRuntimeNode* call = n->as_CallRuntime();
 758 
 759       static struct {
 760         const char* name;
 761         struct {
 762           int pos;
 763           verify_type t;
 764         } args[6];
 765       } calls[] = {
 766         "aescrypt_encryptBlock",
 767         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 768           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 769         "aescrypt_decryptBlock",
 770         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 771           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 772         "multiplyToLen",
 773         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },   { TypeFunc::Parms+4, ShenandoahStore },
 774           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 775         "squareToLen",
 776         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },   { -1,  ShenandoahNone},
 777           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 778         "montgomery_multiply",
 779         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },
 780           { TypeFunc::Parms+6, ShenandoahStore }, { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 781         "montgomery_square",
 782         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+5, ShenandoahStore },
 783           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 784         "mulAdd",
 785         { { TypeFunc::Parms, ShenandoahStore },  { TypeFunc::Parms+1, ShenandoahLoad },   { -1,  ShenandoahNone},
 786           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 787         "vectorizedMismatch",
 788         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { -1,  ShenandoahNone},
 789           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 790         "updateBytesCRC32",
 791         { { TypeFunc::Parms+1, ShenandoahLoad }, { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 792           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 793         "updateBytesAdler32",
 794         { { TypeFunc::Parms+1, ShenandoahLoad }, { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 795           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 796         "updateBytesCRC32C",
 797         { { TypeFunc::Parms+1, ShenandoahLoad }, { TypeFunc::Parms+3, ShenandoahLoad},    { -1,  ShenandoahNone},
 798           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 799         "counterMode_AESCrypt",
 800         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 801           { TypeFunc::Parms+3, ShenandoahStore }, { TypeFunc::Parms+5, ShenandoahStore }, { TypeFunc::Parms+6, ShenandoahStore } },
 802         "cipherBlockChaining_encryptAESCrypt",
 803         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 804           { TypeFunc::Parms+3, ShenandoahLoad },  { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 805         "cipherBlockChaining_decryptAESCrypt",
 806         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 807           { TypeFunc::Parms+3, ShenandoahLoad },  { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 808         "shenandoah_clone_barrier",
 809         { { TypeFunc::Parms, ShenandoahLoad },   { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 810           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 811         "ghash_processBlocks",
 812         { { TypeFunc::Parms, ShenandoahStore },  { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },
 813           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 814         "sha1_implCompress",
 815         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 816           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 817         "sha256_implCompress",
 818         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 819           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 820         "sha512_implCompress",
 821         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 822           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 823         "sha1_implCompressMB",
 824         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 825           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 826         "sha256_implCompressMB",
 827         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 828           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 829         "sha512_implCompressMB",
 830         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 831           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 832       };
 833 
 834       if (call->is_call_to_arraycopystub()) {
 835         Node* dest = NULL;
 836         const TypeTuple* args = n->as_Call()->_tf->domain();
 837         for (uint i = TypeFunc::Parms, j = 0; i < args->cnt(); i++) {
 838           if (args->field_at(i)->isa_ptr()) {
 839             j++;
 840             if (j == 2) {
 841               dest = n->in(i);
 842               break;
 843             }
 844           }
 845         }
 846         if (!ShenandoahBarrierNode::verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahLoad, trace, barriers_used) ||
 847             !ShenandoahBarrierNode::verify_helper(dest, phis, visited, ShenandoahStore, trace, barriers_used)) {
 848           report_verify_failure("Shenandoah verification: ArrayCopy should have barriers", n);
 849         }
 850       } else if (strlen(call->_name) > 5 &&
 851                  !strcmp(call->_name + strlen(call->_name) - 5, "_fill")) {
 852         if (!ShenandoahBarrierNode::verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahStore, trace, barriers_used)) {
 853           report_verify_failure("Shenandoah verification: _fill should have barriers", n);
 854         }
 855       } else if (!strcmp(call->_name, "g1_wb_pre")) {
 856         // skip
 857       } else {
 858         const int calls_len = sizeof(calls) / sizeof(calls[0]);
 859         int i = 0;
 860         for (; i < calls_len; i++) {
 861           if (!strcmp(calls[i].name, call->_name)) {
 862             break;
 863           }
 864         }
 865         if (i != calls_len) {
 866           const uint args_len = sizeof(calls[0].args) / sizeof(calls[0].args[0]);
 867           for (uint j = 0; j < args_len; j++) {
 868             int pos = calls[i].args[j].pos;
 869             if (pos == -1) {
 870               break;
 871             }
 872             if (!ShenandoahBarrierNode::verify_helper(call->in(pos), phis, visited, calls[i].args[j].t, trace, barriers_used)) {
 873               report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
 874             }
 875           }
 876           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
 877             if (call->in(j)->bottom_type()->make_ptr() &&
 878                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 879               uint k = 0;
 880               for (; k < args_len && calls[i].args[k].pos != (int)j; k++);
 881               if (k == args_len) {
 882                 fatal(err_msg("arg %d for call %s not covered", j, call->_name));
 883               }
 884             }
 885           }
 886         } else {
 887           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
 888             if (call->in(j)->bottom_type()->make_ptr() &&
 889                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 890               fatal(err_msg("%s not covered", call->_name));
 891             }
 892           }
 893         }
 894       }
 895     } else if (n->is_ShenandoahBarrier()) {
 896       assert(!barriers.contains(n), "");
 897       assert(n->Opcode() != Op_ShenandoahWriteBarrier || n->find_out_with(Op_ShenandoahWBMemProj) != NULL, "bad shenandoah write barrier");
 898       assert(n->Opcode() != Op_ShenandoahWriteBarrier || n->outcnt() > 1, "bad shenandoah write barrier");
 899       barriers.push(n);
 900     } else if (n->is_AddP()
 901                || n->is_Phi()
 902                || n->Opcode() == Op_CastPP
 903                || n->Opcode() == Op_CheckCastPP
 904                || n->Opcode() == Op_Return
 905                || n->Opcode() == Op_CMoveP
 906                || n->Opcode() == Op_CMoveN
 907                || n->Opcode() == Op_Rethrow
 908                || n->is_MemBar()
 909                || n->Opcode() == Op_Conv2B
 910                || n->Opcode() == Op_SafePoint
 911                || n->is_CallJava()
 912                || n->Opcode() == Op_Unlock
 913                || n->Opcode() == Op_EncodeP
 914                || n->Opcode() == Op_DecodeN) {
 915       // nothing to do
 916     } else {
 917       static struct {
 918         int opcode;
 919         struct {
 920           int pos;
 921           verify_type t;
 922         } inputs[2];
 923       } others[] = {
 924         Op_FastLock,
 925         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
 926         Op_Lock,
 927         { { TypeFunc::Parms, ShenandoahLoad },    { -1, ShenandoahNone} },
 928         Op_AryEq,
 929         { { 2, ShenandoahLoad },                  { 3, ShenandoahLoad } },
 930         Op_StrIndexOf,
 931         { { 2, ShenandoahLoad },                  { 4, ShenandoahLoad } },
 932         Op_StrComp,
 933         { { 2, ShenandoahLoad },                  { 4, ShenandoahLoad } },
 934         Op_StrEquals,
 935         { { 2, ShenandoahLoad },                  { 3, ShenandoahLoad } },
 936         Op_EncodeISOArray,
 937         { { 2, ShenandoahLoad },                  { 3, ShenandoahStore } },
 938         Op_CastP2X,
 939         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
 940       };
 941 
 942       const int others_len = sizeof(others) / sizeof(others[0]);
 943       int i = 0;
 944       for (; i < others_len; i++) {
 945         if (others[i].opcode == n->Opcode()) {
 946           break;
 947         }
 948       }
 949       uint stop = n->is_Call() ? n->as_Call()->tf()->domain()->cnt() : n->req();
 950       if (i != others_len) {
 951         const uint inputs_len = sizeof(others[0].inputs) / sizeof(others[0].inputs[0]);
 952         for (uint j = 0; j < inputs_len; j++) {
 953           int pos = others[i].inputs[j].pos;
 954           if (pos == -1) {
 955             break;
 956           }
 957           if (!ShenandoahBarrierNode::verify_helper(n->in(pos), phis, visited, others[i].inputs[j].t, trace, barriers_used)) {
 958             report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
 959           }
 960         }
 961         for (uint j = 1; j < stop; j++) {
 962           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
 963               n->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 964             uint k = 0;
 965             for (; k < inputs_len && others[i].inputs[k].pos != (int)j; k++);
 966             if (k == inputs_len) {
 967               fatal(err_msg("arg %d for node %s not covered", j, n->Name()));
 968             }
 969           }
 970         }
 971       } else {
 972         for (uint j = 1; j < stop; j++) {
 973           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
 974               n->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 975             fatal(err_msg("%s not covered", n->Name()));
 976           }
 977         }
 978       }
 979     }
 980 
 981     if (n->is_SafePoint()) {
 982       SafePointNode* sfpt = n->as_SafePoint();
 983       if (verify_no_useless_barrier && sfpt->jvms() != NULL) {
 984         for (uint i = sfpt->jvms()->scloff(); i < sfpt->jvms()->endoff(); i++) {
 985           if (!ShenandoahBarrierNode::verify_helper(sfpt->in(i), phis, visited, ShenandoahLoad, trace, barriers_used)) {
 986             phis.clear();
 987             visited.Reset();
 988           }
 989         }
 990       }
 991     }
 992     for( uint i = 0; i < n->len(); ++i ) {
 993       Node *m = n->in(i);
 994       if (m == NULL) continue;
 995 
 996       // In most cases, inputs should be known to be non null. If it's
 997       // not the case, it could be a missing cast_not_null() in an
 998       // intrinsic or support might be needed in AddPNode::Ideal() to
 999       // avoid a NULL+offset input.
1000       if (!(n->is_Phi() ||
1001             (n->is_SafePoint() && (!n->is_CallRuntime() || !strcmp(n->as_CallRuntime()->_name, "g1_wb_pre") || !strcmp(n->as_CallRuntime()->_name, "unsafe_arraycopy"))) ||
1002             n->Opcode() == Op_CmpP ||
1003             n->Opcode() == Op_CmpN ||
1004             (n->Opcode() == Op_StoreP && i == StoreNode::ValueIn) ||
1005             (n->Opcode() == Op_StoreN && i == StoreNode::ValueIn) ||
1006             n->Opcode() == Op_CheckCastPP ||
1007             n->Opcode() == Op_CastPP ||
1008             n->Opcode() == Op_Return ||
1009             n->Opcode() == Op_Conv2B ||
1010             n->is_AddP() ||
1011             n->Opcode() == Op_CMoveP ||
1012             n->Opcode() == Op_CMoveN ||
1013             n->Opcode() == Op_Rethrow ||
1014             n->is_MemBar() ||
1015             n->is_Mem() ||
1016             n->Opcode() == Op_AryEq ||
1017             n->Opcode() == Op_SCMemProj ||
1018             n->Opcode() == Op_EncodeP ||
1019             n->Opcode() == Op_DecodeN ||
1020             (n->is_CallRuntime() && !strcmp(n->as_CallRuntime()->_name, "generic_arraycopy")))) {
1021         if (m->bottom_type()->isa_oopptr() && m->bottom_type()->meet(TypePtr::NULL_PTR) == m->bottom_type()) {
1022           report_verify_failure("Shenandoah verification: null input", n, m);
1023         }
1024       }
1025 
1026       wq.push(m);
1027     }
1028   }
1029 
1030   if (verify_no_useless_barrier) {
1031     for (int i = 0; i < barriers.length(); i++) {
1032       Node* n = barriers.at(i);
1033       if (!barriers_used.member(n)) {
1034         tty->print("XXX useless barrier"); n->dump(-2);
1035         ShouldNotReachHere();
1036       }
1037     }
1038   }
1039 }
1040 #endif
1041 
1042 MergeMemNode* ShenandoahWriteBarrierNode::allocate_merge_mem(Node* mem, int alias, Node* rep_proj, Node* rep_ctrl, PhaseIdealLoop* phase) {
1043   MergeMemNode* mm = MergeMemNode::make(phase->C, mem);
1044   mm->set_memory_at(alias, rep_proj);
1045   phase->register_new_node(mm, rep_ctrl);
1046   return mm;
1047 }
1048 
1049 MergeMemNode* ShenandoahWriteBarrierNode::clone_merge_mem(Node* u, Node* mem, int alias, Node* rep_proj, Node* rep_ctrl, DUIterator& i, PhaseIdealLoop* phase) {
1050   MergeMemNode* newmm = NULL;
1051   MergeMemNode* u_mm = u->as_MergeMem();
1052   Node* c = phase->get_ctrl(u);
1053   if (phase->is_dominator(c, rep_ctrl)) {
1054     c = rep_ctrl;
1055   } else {
1056     assert(phase->is_dominator(rep_ctrl, c), "one must dominate the other");
1057   }
1058   if (u->outcnt() == 1) {
1059     if (u->req() > (uint)alias && u->in(alias) == mem) {
1060       phase->igvn().replace_input_of(u, alias, rep_proj);
1061       --i;
1062     } else {
1063       phase->igvn().rehash_node_delayed(u);
1064       u_mm->set_memory_at(alias, rep_proj);
1065     }
1066     newmm = u_mm;
1067     phase->set_ctrl_and_loop(u, c);
1068   } else {
1069     // can't simply clone u and then change one of its input because
1070     // it adds and then removes an edge which messes with the
1071     // DUIterator
1072     newmm = MergeMemNode::make(phase->C, u_mm->base_memory());
1073     for (uint j = 0; j < u->req(); j++) {
1074       if (j < newmm->req()) {
1075         if (j == (uint)alias) {
1076           newmm->set_req(j, rep_proj);
1077         } else if (newmm->in(j) != u->in(j)) {
1078           newmm->set_req(j, u->in(j));
1079         }
1080       } else if (j == (uint)alias) {
1081         newmm->add_req(rep_proj);
1082       } else {
1083         newmm->add_req(u->in(j));
1084       }
1085     }
1086     if ((uint)alias >= u->req()) {
1087       newmm->set_memory_at(alias, rep_proj);
1088     }
1089     phase->register_new_node(newmm, c);
1090   }
1091   return newmm;
1092 }
1093 
1094 bool ShenandoahWriteBarrierNode::should_process_phi(Node* phi, int alias, Compile* C) {
1095   if (phi->adr_type() == TypePtr::BOTTOM) {
1096     Node* region = phi->in(0);
1097     for (DUIterator_Fast jmax, j = region->fast_outs(jmax); j < jmax; j++) {
1098       Node* uu = region->fast_out(j);
1099       if (uu->is_Phi() && uu != phi && uu->bottom_type() == Type::MEMORY && C->get_alias_index(uu->adr_type()) == alias) {
1100         return false;
1101       }
1102     }
1103     return true;
1104   }
1105   return C->get_alias_index(phi->adr_type()) == alias;
1106 }
1107 
1108 bool ShenandoahBarrierNode::is_dominator_same_ctrl(Node*c, Node* d, Node* n, PhaseIdealLoop* phase) {
1109   // That both nodes have the same control is not sufficient to prove
1110   // domination, verify that there's no path from d to n
1111   ResourceMark rm;
1112   Unique_Node_List wq;
1113   wq.push(d);
1114   for (uint next = 0; next < wq.size(); next++) {
1115     Node *m = wq.at(next);
1116     if (m == n) {
1117       return false;
1118     }
1119     if (m->is_Phi() && m->in(0)->is_Loop()) {
1120       assert(phase->ctrl_or_self(m->in(LoopNode::EntryControl)) != c, "following loop entry should lead to new control");
1121     } else {
1122       for (uint i = 0; i < m->req(); i++) {
1123         if (m->in(i) != NULL && phase->ctrl_or_self(m->in(i)) == c) {
1124           wq.push(m->in(i));
1125         }
1126       }
1127     }
1128   }
1129   return true;
1130 }
1131 
1132 bool ShenandoahBarrierNode::is_dominator(Node *d_c, Node *n_c, Node* d, Node* n, PhaseIdealLoop* phase) {
1133   if (d_c != n_c) {
1134     return phase->is_dominator(d_c, n_c);
1135   }
1136   return is_dominator_same_ctrl(d_c, d, n, phase);
1137 }
1138 
1139 Node* next_mem(Node* mem, int alias) {
1140   Node* res = NULL;
1141   if (mem->is_Proj()) {
1142     res = mem->in(0);
1143   } else if (mem->is_SafePoint() || mem->is_MemBar()) {
1144     res = mem->in(TypeFunc::Memory);
1145   } else if (mem->is_Phi()) {
1146     res = mem->in(1);
1147   } else if (mem->is_ShenandoahBarrier()) {
1148     res = mem->in(ShenandoahBarrierNode::Memory);
1149   } else if (mem->is_MergeMem()) {
1150     res = mem->as_MergeMem()->memory_at(alias);
1151   } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
1152     assert(alias = Compile::AliasIdxRaw, "following raw memory can't lead to a barrier");
1153     res = mem->in(MemNode::Memory);
1154   } else {
1155 #ifdef ASSERT
1156     mem->dump();
1157 #endif
1158     ShouldNotReachHere();
1159   }
1160   return res;
1161 }
1162 
1163 bool shenandoah_suitable_mem(Node* mem, Node* old_mem, Node* rep_proj) {
1164   for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
1165     Node* u = mem->fast_out(i);
1166     if (u->is_MergeMem()) {
1167       if (u->has_out_with(Op_MergeMem)) {
1168         // too complicated for now
1169         return false;
1170       }
1171       if (old_mem == u && rep_proj->has_out_with(Op_MergeMem)) {
1172         return false;
1173       }
1174     }
1175     if (u->Opcode() == Op_Unlock && mem->is_Proj() && mem->in(0)->Opcode() == Op_MemBarReleaseLock) {
1176       // would require a merge mem between unlock and the
1177       // preceding membar. Would confuse logic that eliminates
1178       // lock/unlock nodes.
1179       return false;
1180     }
1181   }
1182   return true;
1183 }
1184 
1185 void ShenandoahWriteBarrierNode::fix_memory_uses(Node* mem, Node* replacement, Node* rep_proj, Node* rep_ctrl, int alias, PhaseIdealLoop* phase) {
1186   uint last =phase-> C->unique();
1187   MergeMemNode* mm = NULL;
1188   assert(mem->bottom_type() == Type::MEMORY, "");
1189   for (DUIterator i = mem->outs(); mem->has_out(i); i++) {
1190     Node* u = mem->out(i);
1191     if (u != replacement && u->_idx < last) {
1192       if (u->is_ShenandoahBarrier() && alias != Compile::AliasIdxRaw) {
1193         if (phase->C->get_alias_index(u->adr_type()) == alias && is_dominator(rep_ctrl, phase->ctrl_or_self(u), replacement, u, phase)) {
1194           phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
1195           assert(u->find_edge(mem) == -1, "only one edge");
1196           --i;
1197         }
1198       } else if (u->is_Mem()) {
1199         if (phase->C->get_alias_index(u->adr_type()) == alias && is_dominator(rep_ctrl, phase->ctrl_or_self(u), replacement, u, phase)) {
1200           assert(alias == Compile::AliasIdxRaw , "only raw memory can lead to a memory operation");
1201           phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
1202           assert(u->find_edge(mem) == -1, "only one edge");
1203           --i;
1204         }
1205       } else if (u->is_MergeMem()) {
1206         MergeMemNode* u_mm = u->as_MergeMem();
1207         if (u_mm->memory_at(alias) == mem) {
1208           MergeMemNode* newmm = NULL;
1209           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
1210             Node* uu = u->fast_out(j);
1211             assert(!uu->is_MergeMem(), "chain of MergeMems?");
1212             if (uu->is_Phi()) {
1213               if (should_process_phi(uu, alias, phase->C)) {
1214                 Node* region = uu->in(0);
1215                 int nb = 0;
1216                 for (uint k = 1; k < uu->req(); k++) {
1217                   if (uu->in(k) == u && phase->is_dominator(rep_ctrl, region->in(k))) {
1218                     if (newmm == NULL) {
1219                       newmm = clone_merge_mem(u, mem, alias, rep_proj, rep_ctrl, i, phase);
1220                     }
1221                     if (newmm != u) {
1222                       phase->igvn().replace_input_of(uu, k, newmm);
1223                       nb++;
1224                       --jmax;
1225                     }
1226                   }
1227                 }
1228                 if (nb > 0) {
1229                   --j;
1230                 }
1231               }
1232             } else {
1233               if (rep_ctrl != uu && is_dominator(rep_ctrl, phase->ctrl_or_self(uu), replacement, uu, phase)) {
1234                 if (newmm == NULL) {
1235                   newmm = clone_merge_mem(u, mem, alias, rep_proj, rep_ctrl, i, phase);
1236                 }
1237                 if (newmm != u) {
1238                   phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
1239                   --j, --jmax;
1240                 }
1241               }
1242             }
1243           }
1244         }
1245       } else if (u->is_Phi()) {
1246         assert(u->bottom_type() == Type::MEMORY, "what else?");
1247         Node* region = u->in(0);
1248         if (should_process_phi(u, alias, phase->C)) {
1249           bool replaced = false;
1250           for (uint j = 1; j < u->req(); j++) {
1251             if (u->in(j) == mem && phase->is_dominator(rep_ctrl, region->in(j))) {
1252               Node* nnew = rep_proj;
1253               if (u->adr_type() == TypePtr::BOTTOM) {
1254                 if (mm == NULL) {
1255                   mm = allocate_merge_mem(mem, alias, rep_proj, rep_ctrl, phase);
1256                 }
1257                 nnew = mm;
1258               }
1259               phase->igvn().replace_input_of(u, j, nnew);
1260               replaced = true;
1261             }
1262           }
1263           if (replaced) {
1264             --i;
1265           }
1266 
1267         }
1268       } else if (u->adr_type() == TypePtr::BOTTOM || u->adr_type() == NULL) {
1269         assert(u->adr_type() != NULL ||
1270                u->Opcode() == Op_Rethrow ||
1271                u->Opcode() == Op_Return ||
1272                u->Opcode() == Op_SafePoint ||
1273                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
1274                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
1275                u->Opcode() == Op_CallLeaf, "");
1276         if (is_dominator(rep_ctrl, phase->ctrl_or_self(u), replacement, u, phase)) {
1277           if (mm == NULL) {
1278             mm = allocate_merge_mem(mem, alias, rep_proj, rep_ctrl, phase);
1279           }
1280           phase->igvn().replace_input_of(u, u->find_edge(mem), mm);
1281           --i;
1282         }
1283       } else if (phase->C->get_alias_index(u->adr_type()) == alias) {
1284         if (is_dominator(rep_ctrl, phase->ctrl_or_self(u), replacement, u, phase)) {
1285           phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
1286           --i;
1287         }
1288       }
1289     }
1290   }
1291 }
1292 
1293 Node* PhaseIdealLoop::shenandoah_no_branches(Node* c, Node* dom, bool allow_one_proj) {
1294   Node* iffproj = NULL;
1295   while (c != dom) {
1296     Node* next = idom(c);
1297     assert(next->unique_ctrl_out() == c || c->is_Proj() || c->is_Region(), "multiple control flow out but no proj or region?");
1298     if (c->is_Region()) {
1299       ResourceMark rm;
1300       Unique_Node_List wq;
1301       wq.push(c);
1302       for (uint i = 0; i < wq.size(); i++) {
1303         Node *n = wq.at(i);
1304         if (n->is_Region()) {
1305           for (uint j = 1; j < n->req(); j++) {
1306             if (n->in(j) != next) {
1307               wq.push(n->in(j));
1308             }
1309           }
1310         } else {
1311           if (n->in(0) != next) {
1312             wq.push(n->in(0));
1313           }
1314         }
1315       }
1316       for (DUIterator_Fast imax, i = next->fast_outs(imax); i < imax; i++) {
1317         Node* u = next->fast_out(i);
1318         if (u->is_CFG()) {
1319           if (!wq.member(u)) {
1320             return NodeSentinel;
1321           }
1322         }
1323       }
1324 
1325     } else  if (c->is_Proj()) {
1326       if (c->is_IfProj()) {
1327         if (c->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) != NULL) {
1328           // continue;
1329         } else {
1330           if (!allow_one_proj) {
1331             return NodeSentinel;
1332           }
1333           if (iffproj == NULL) {
1334             iffproj = c;
1335           } else {
1336             return NodeSentinel;
1337           }
1338         }
1339       } else if (c->Opcode() == Op_JumpProj) {
1340         return NodeSentinel; // unsupported
1341       } else if (c->Opcode() == Op_CatchProj) {
1342         return NodeSentinel; // unsupported
1343       } else if (c->Opcode() == Op_CProj && next->Opcode() == Op_NeverBranch) {
1344         return NodeSentinel; // unsupported
1345       } else {
1346         assert(next->unique_ctrl_out() == c, "unsupported branch pattern");
1347       }
1348     }
1349     c = next;
1350   }
1351   return iffproj;
1352 }
1353 
1354 #ifdef ASSERT
1355 void PhaseIdealLoop::shenandoah_memory_dominates_all_paths_helper(Node* c, Node* rep_ctrl, Unique_Node_List& controls) {
1356   const bool trace = false;
1357   if (trace) { tty->print("X control is"); c->dump(); }
1358 
1359   uint start = controls.size();
1360   controls.push(c);
1361   for (uint i = start; i < controls.size(); i++) {
1362     Node *n = controls.at(i);
1363 
1364     if (trace) { tty->print("X from"); n->dump(); }
1365 
1366     if (n == rep_ctrl) {
1367       continue;
1368     }
1369 
1370     if (n->is_Proj()) {
1371       Node* n_dom = n->in(0);
1372       IdealLoopTree* n_dom_loop = get_loop(n_dom);
1373       if (n->is_IfProj() && n_dom->outcnt() == 2) {
1374         n_dom_loop = get_loop(n_dom->as_If()->proj_out(n->as_Proj()->_con == 0 ? 1 : 0));
1375       }
1376       if (n_dom_loop != _ltree_root) {
1377         Node* tail = n_dom_loop->tail();
1378         if (tail->is_Region()) {
1379           for (uint j = 1; j < tail->req(); j++) {
1380             if (is_dominator(n_dom, tail->in(j)) && !is_dominator(n, tail->in(j))) {
1381               assert(is_dominator(rep_ctrl, tail->in(j)), "why are we here?");
1382               // entering loop from below, mark backedge
1383               if (trace) { tty->print("X pushing backedge"); tail->in(j)->dump(); }
1384               controls.push(tail->in(j));
1385               //assert(n->in(0) == n_dom, "strange flow control");
1386             }
1387           }
1388         } else if (get_loop(n) != n_dom_loop && is_dominator(n_dom, tail)) {
1389           // entering loop from below, mark backedge
1390           if (trace) { tty->print("X pushing backedge"); tail->dump(); }
1391           controls.push(tail);
1392           //assert(n->in(0) == n_dom, "strange flow control");
1393         }
1394       }
1395     }
1396 
1397     if (n->is_Loop()) {
1398       Node* c = n->in(LoopNode::EntryControl);
1399       if (trace) { tty->print("X pushing"); c->dump(); }
1400       controls.push(c);
1401     } else if (n->is_Region()) {
1402       for (uint i = 1; i < n->req(); i++) {
1403         Node* c = n->in(i);
1404         if (trace) { tty->print("X pushing"); c->dump(); }
1405         controls.push(c);
1406       }
1407     } else {
1408       Node* c = n->in(0);
1409       if (trace) { tty->print("X pushing"); c->dump(); }
1410       controls.push(c);
1411     }
1412   }
1413 }
1414 
1415 bool PhaseIdealLoop::shenandoah_memory_dominates_all_paths(Node* mem, Node* rep_ctrl, int alias) {
1416   const bool trace = false;
1417   if (trace) {
1418     tty->print("XXX mem is"); mem->dump();
1419     tty->print("XXX rep ctrl is"); rep_ctrl->dump();
1420     tty->print_cr("XXX alias is %d", alias);
1421   }
1422   ResourceMark rm;
1423   Unique_Node_List wq;
1424   Unique_Node_List controls;
1425   wq.push(mem);
1426   for (uint next = 0; next < wq.size(); next++) {
1427     Node *nn = wq.at(next);
1428     if (trace) { tty->print("XX from mem"); nn->dump(); }
1429     assert(nn->bottom_type() == Type::MEMORY, "memory only");
1430 
1431     if (nn->is_Phi()) {
1432       Node* r = nn->in(0);
1433       for (DUIterator_Fast jmax, j = r->fast_outs(jmax); j < jmax; j++) {
1434         Node* u = r->fast_out(j);
1435         if (u->is_Phi() && u->bottom_type() == Type::MEMORY && u != nn &&
1436             (u->adr_type() == TypePtr::BOTTOM || C->get_alias_index(u->adr_type()) == alias)) {
1437           if (trace) { tty->print("XX Next mem (other phi)"); u->dump(); }
1438           wq.push(u);
1439         }
1440       }
1441     }
1442 
1443     for (DUIterator_Fast imax, i = nn->fast_outs(imax); i < imax; i++) {
1444       Node* use = nn->fast_out(i);
1445 
1446       if (trace) { tty->print("XX use %p", use->adr_type()); use->dump(); }
1447       if (use->is_CFG()) {
1448         assert(use->in(TypeFunc::Memory) == nn, "bad cfg node");
1449         Node* c = use->in(0);
1450         if (is_dominator(rep_ctrl, c)) {
1451           shenandoah_memory_dominates_all_paths_helper(c, rep_ctrl, controls);
1452         } else if (use->is_CallStaticJava() && use->as_CallStaticJava()->uncommon_trap_request() != 0 && c->is_Region()) {
1453           Node* region = c;
1454           if (trace) { tty->print("XX unc region"); region->dump(); }
1455           for (uint j = 1; j < region->req(); j++) {
1456             if (is_dominator(rep_ctrl, region->in(j))) {
1457               if (trace) { tty->print("XX unc follows"); region->in(j)->dump(); }
1458               shenandoah_memory_dominates_all_paths_helper(region->in(j), rep_ctrl, controls);
1459             }
1460           }
1461         }
1462         //continue;
1463       } else if (use->is_Phi()) {
1464         assert(use->bottom_type() == Type::MEMORY, "bad phi");
1465         if ((use->adr_type() == TypePtr::BOTTOM /*&& !shenandoah_has_alias_phi(C, use, alias)*/) ||
1466             C->get_alias_index(use->adr_type()) == alias) {
1467           for (uint j = 1; j < use->req(); j++) {
1468             if (use->in(j) == nn) {
1469               Node* c = use->in(0)->in(j);
1470               if (is_dominator(rep_ctrl, c)) {
1471                 shenandoah_memory_dominates_all_paths_helper(c, rep_ctrl, controls);
1472               }
1473             }
1474           }
1475         }
1476         //        continue;
1477       }
1478 
1479       if (use->is_MergeMem()) {
1480         if (use->as_MergeMem()->memory_at(alias) == nn) {
1481           if (trace) { tty->print("XX Next mem"); use->dump(); }
1482           // follow the memory edges
1483           wq.push(use);
1484         }
1485       } else if (use->is_Phi()) {
1486         assert(use->bottom_type() == Type::MEMORY, "bad phi");
1487         if ((use->adr_type() == TypePtr::BOTTOM /*&& !shenandoah_has_alias_phi(C, use, alias)*/) ||
1488             C->get_alias_index(use->adr_type()) == alias) {
1489           if (trace) { tty->print("XX Next mem"); use->dump(); }
1490           // follow the memory edges
1491           wq.push(use);
1492         }
1493       } else if (use->bottom_type() == Type::MEMORY &&
1494                  (use->adr_type() == TypePtr::BOTTOM || C->get_alias_index(use->adr_type()) == alias)) {
1495         if (trace) { tty->print("XX Next mem"); use->dump(); }
1496         // follow the memory edges
1497         wq.push(use);
1498       } else if ((use->is_SafePoint() || use->is_MemBar()) &&
1499                  (use->adr_type() == TypePtr::BOTTOM || C->get_alias_index(use->adr_type()) == alias)) {
1500         for (DUIterator_Fast jmax, j = use->fast_outs(jmax); j < jmax; j++) {
1501           Node* u = use->fast_out(j);
1502           if (u->bottom_type() == Type::MEMORY) {
1503             if (trace) { tty->print("XX Next mem"); u->dump(); }
1504             // follow the memory edges
1505             wq.push(u);
1506           }
1507         }
1508       } else if (use->Opcode() == Op_ShenandoahWriteBarrier && C->get_alias_index(use->adr_type()) == alias) {
1509         Node* m = use->find_out_with(Op_ShenandoahWBMemProj);
1510         if (m != NULL) {
1511           if (trace) { tty->print("XX Next mem"); m->dump(); }
1512           // follow the memory edges
1513           wq.push(m);
1514         }
1515       }
1516     }
1517   }
1518 
1519   if (controls.size() == 0) {
1520     return false;
1521   }
1522 
1523   for (uint i = 0; i < controls.size(); i++) {
1524     Node *n = controls.at(i);
1525 
1526     if (trace) { tty->print("X checking"); n->dump(); }
1527 
1528     if (n->unique_ctrl_out() != NULL) {
1529       continue;
1530     }
1531 
1532     if (n->Opcode() == Op_NeverBranch) {
1533       Node* taken = n->as_Multi()->proj_out(0);
1534       if (!controls.member(taken)) {
1535         if (trace) { tty->print("X not seen"); taken->dump(); }
1536         return false;
1537       }
1538       continue;
1539     }
1540 
1541     for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1542       Node* u = n->fast_out(j);
1543 
1544       if (u->is_CFG()) {
1545         if (!controls.member(u)) {
1546           if (u->is_Proj() && u->as_Proj()->is_uncommon_trap_proj(Deoptimization::Reason_none)) {
1547             if (trace) { tty->print("X not seen but unc"); u->dump(); }
1548           } else if (u->unique_ctrl_out() != NULL && u->unique_ctrl_out()->Opcode() == Op_Halt) {
1549             if (trace) { tty->print("X not seen but halt"); u->dump(); }
1550           } else {
1551             Node* c = u;
1552             do {
1553               c = c->unique_ctrl_out();
1554             } while (c != NULL && c->is_Region());
1555             if (c != NULL && c->Opcode() == Op_Halt) {
1556               if (trace) { tty->print("X not seen but halt"); c->dump(); }
1557             } else {
1558               if (trace) { tty->print("X not seen"); u->dump(); }
1559               return false;
1560             }
1561           }
1562         } else {
1563           if (trace) { tty->print("X seen"); u->dump(); }
1564         }
1565       }
1566     }
1567   }
1568   return true;
1569 }
1570 #endif
1571 
1572 static bool has_mem_phi(Compile* C, Node* region, int alias) {
1573   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1574     Node* use = region->fast_out(i);
1575     if (use->is_Phi() && use->bottom_type() == Type::MEMORY &&
1576         (C->get_alias_index(use->adr_type()) == alias)) {
1577       return true;
1578     }
1579   }
1580   return false;
1581 }
1582 
1583 bool PhaseIdealLoop::shenandoah_fix_mem_phis_helper(Node* c, Node* mem, Node* mem_ctrl, Node* rep_ctrl, int alias, VectorSet& controls, GrowableArray<Node*>& regions) {
1584   const bool trace = false;
1585   Node_List wq;
1586   wq.push(c);
1587 
1588 #ifdef ASSERT
1589   if (trace) { tty->print("YYY from"); c->dump(); }
1590   if (trace) { tty->print("YYY with mem"); mem->dump(); }
1591 #endif
1592 
1593   while(wq.size() > 0) {
1594     c = wq.pop();
1595 
1596     while (!c->is_Region() || c->is_Loop()) {
1597 #ifdef ASSERT
1598       if (trace) { tty->print("YYY"); c->dump(); }
1599 #endif
1600       assert(c->is_CFG(), "node should be control node");
1601       if (c == mem_ctrl || is_dominator(c, rep_ctrl)) {
1602         c = NULL;
1603         break;
1604       } else if (c->is_Loop()) {
1605         c = c->in(LoopNode::EntryControl);
1606       } else {
1607         c = c->in(0);
1608       }
1609     }
1610     if (c == NULL) {
1611       continue;
1612     }
1613 
1614 #ifdef ASSERT
1615     if (trace) { tty->print("YYY new region"); c->dump(); }
1616 #endif
1617 
1618     bool has_phi = has_mem_phi(C, c, alias);
1619     if (!has_phi) {
1620 
1621       Node* m = mem;
1622       Node* m_ctrl = ctrl_or_self(m);
1623       {
1624         ResourceMark rm;
1625         VectorSet wq(Thread::current()->resource_area());
1626         wq.set(m->_idx);
1627         while (!is_dominator(m_ctrl, c) || m_ctrl == c) {
1628           m = next_mem(m, alias);
1629           if (wq.test_set(m->_idx)) {
1630             return false;
1631           }
1632           m_ctrl = ctrl_or_self(m);
1633         }
1634       }
1635 
1636       assert(m->bottom_type() == Type::MEMORY, "");
1637 
1638       if (m->is_MergeMem()) {
1639         m = m->as_MergeMem()->memory_at(alias);
1640         m_ctrl = ctrl_or_self(m);
1641       }
1642 
1643 #ifdef ASSERT
1644       if (trace) { tty->print("YYY mem "); m->dump(); }
1645 #endif
1646 
1647       if (controls.test(c->_idx)) {
1648         int i;
1649         for (i = 0; i < regions.length() && regions.at(i) != c; i+=2) {
1650           // deliberately empty, rolling over the regions
1651         }
1652         assert(i < regions.length(), "missing region");
1653         Node* prev_m = regions.at(i+1);
1654         if (prev_m == m) {
1655           continue;
1656         }
1657 #ifdef ASSERT
1658         if (trace) { tty->print("YYY prev mem "); prev_m->dump(); }
1659 #endif
1660         Node* prev_m_ctrl = ctrl_or_self(prev_m);
1661         assert(ShenandoahBarrierNode::is_dominator(m_ctrl, prev_m_ctrl, m, prev_m, this) ||
1662                ShenandoahBarrierNode::is_dominator(prev_m_ctrl, m_ctrl, prev_m, m, this), "one should dominate the other");
1663         if (ShenandoahBarrierNode::is_dominator(m_ctrl, prev_m_ctrl, m, prev_m, this)) {
1664           continue;
1665         }
1666 #ifdef ASSERT
1667         if (trace) { tty->print("YYY Fixing "); c->dump(); }
1668 #endif
1669         regions.at_put(i+1, m);
1670       } else {
1671 #ifdef ASSERT
1672         if (trace) { tty->print("YYY Pushing "); c->dump(); }
1673 #endif
1674         regions.push(c);
1675         regions.push(m);
1676       }
1677     } else {
1678       continue;
1679     }
1680 
1681     controls.set(c->_idx);
1682 
1683     for (uint i = 1; i < c->req(); i++) {
1684       wq.push(c->in(i));
1685     }
1686   }
1687   return true;
1688 }
1689 
1690 
1691 bool PhaseIdealLoop::shenandoah_fix_mem_phis(Node* mem, Node* mem_ctrl, Node* rep_ctrl, int alias) {
1692   GrowableArray<Node*> regions;
1693   VectorSet controls(Thread::current()->resource_area());
1694   const bool trace = false;
1695 
1696 #ifdef ASSERT
1697   if (trace) { tty->print("YYY mem is "); mem->dump(); }
1698   if (trace) { tty->print("YYY mem ctrl is "); mem_ctrl->dump(); }
1699   if (trace) { tty->print("YYY rep ctrl is "); rep_ctrl->dump(); }
1700   if (trace) { tty->print_cr("YYY alias is %d", alias); }
1701 #endif
1702 
1703   // Walk memory edges from mem until we hit a memory point where
1704   // control is known then follow the control up looking for regions
1705   // with no memory Phi for alias
1706   Unique_Node_List wq;
1707   wq.push(mem);
1708 
1709   for (uint next = 0; next < wq.size(); next++) {
1710     Node *n = wq.at(next);
1711 #ifdef ASSERT
1712     if (trace) { tty->print("YYY from (2) "); n->dump(); }
1713 #endif
1714     for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1715       Node* u = n->fast_out(i);
1716 #ifdef ASSERT
1717       if (trace) { tty->print("YYY processing "); u->dump(); }
1718 #endif
1719       if (u->is_Phi()) {
1720         assert(u->bottom_type() == Type::MEMORY, "strange memory graph");
1721         if (ShenandoahWriteBarrierNode::should_process_phi(u, alias, C)) {
1722           for (uint j = 1; j < u->req(); j++) {
1723             if (u->in(j) == n) {
1724               Node *c = u->in(0)->in(j);
1725               if (!shenandoah_fix_mem_phis_helper(c, n, mem_ctrl, rep_ctrl, alias, controls, regions)) {
1726                 return false;
1727               }
1728             }
1729           }
1730         }
1731 #ifdef ASSERT
1732       } else if (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) {
1733         if (!shenandoah_fix_mem_phis_helper(u->in(0), n, mem_ctrl, rep_ctrl, alias, controls, regions)) {
1734           return false;
1735         }
1736 #endif
1737       } else if ((u->is_CFG() && u->adr_type() == TypePtr::BOTTOM) || u->Opcode() == Op_Rethrow || u->Opcode() == Op_Return) {
1738         if (!shenandoah_fix_mem_phis_helper(u->in(0), n, mem_ctrl, rep_ctrl, alias, controls, regions)) {
1739           return false;
1740         }
1741       } else if (u->is_MergeMem() && u->as_MergeMem()->memory_at(alias) == n) {
1742         wq.push(u);
1743       } else if (u->Opcode() == Op_ShenandoahWriteBarrier && C->get_alias_index(u->adr_type()) == alias) {
1744         Node* m = u->find_out_with(Op_ShenandoahWBMemProj);
1745         if (m != NULL) {
1746           wq.push(m);
1747         }
1748       }
1749     }
1750   }
1751 #ifdef ASSERT
1752   if (trace) {
1753     tty->print_cr("XXXXXXXXXXXXXXXXXXXX");
1754     for (int i = 0; i < regions.length(); i++) {
1755       Node* r = regions.at(i);
1756       tty->print("%d", i); r->dump();
1757     }
1758     tty->print_cr("XXXXXXXXXXXXXXXXXXXX");
1759   }
1760 #endif
1761 
1762   if (regions.length() == 0) {
1763     return true;
1764   }
1765 
1766   {
1767     int i = 0;
1768     for (; i < regions.length(); i+=2) {
1769       Node* region = regions.at(i);
1770       bool has_phi = false;
1771       for (DUIterator_Fast jmax, j = region->fast_outs(jmax); j < jmax && !has_phi; j++) {
1772         Node* u = region->fast_out(j);
1773         if (u->is_Phi() && u->bottom_type() == Type::MEMORY &&
1774             (u->adr_type() == TypePtr::BOTTOM || C->get_alias_index(u->adr_type()) == alias)) {
1775           has_phi = true;
1776         }
1777       }
1778       if (!has_phi) {
1779         break;
1780       }
1781     }
1782     if (i == regions.length()) {
1783       return true;
1784     }
1785   }
1786 
1787   // Try to restrict the update to path that post dominates rep_ctrl
1788   int k = 0;
1789   int start = 0;
1790   int end = 0;
1791   do {
1792     start = end;
1793     end = k;
1794     for (int i = end; i < regions.length(); i+=2) {
1795       Node* r = regions.at(i);
1796       int prev = k;
1797       for (uint j = 1; j < r->req() && prev == k; j++) {
1798         if (end == 0) {
1799           if (is_dominator(rep_ctrl, r->in(j))) {
1800             Node* mem = regions.at(i+1);
1801             regions.at_put(i, regions.at(k));
1802             regions.at_put(i+1, regions.at(k+1));
1803             regions.at_put(k, r);
1804             regions.at_put(k+1, mem);
1805             k+=2;
1806           }
1807         } else {
1808           for (int l = start; l < end && prev == k; l+=2) {
1809             Node* r2 = regions.at(l);
1810             if (is_dominator(r2, r->in(j))) {
1811               Node* mem = regions.at(i+1);
1812               regions.at_put(i, regions.at(k));
1813               regions.at_put(i+1, regions.at(k+1));
1814               regions.at_put(k, r);
1815               regions.at_put(k+1, mem);
1816               k+=2;
1817             }
1818           }
1819         }
1820       }
1821     }
1822 #ifdef ASSERT
1823     if (trace) { tty->print_cr("k = %d start = %d end = %d", k, start, end); }
1824 #endif
1825   } while(k != end);
1826 
1827 #ifdef ASSERT
1828   if (end != regions.length()) {
1829     if (trace) { tty->print_cr("Compacting %d -> %d", regions.length(), end); }
1830   }
1831 #endif
1832   regions.trunc_to(end);
1833 
1834 #ifdef ASSERT
1835   if (trace) {
1836     tty->print_cr("XXXXXXXXXXXXXXXXXXXX");
1837     for (int i = 0; i < regions.length(); i++) {
1838       Node* r = regions.at(i);
1839       tty->print("%d", i); r->dump();
1840     }
1841     tty->print_cr("XXXXXXXXXXXXXXXXXXXX");
1842   }
1843 #endif
1844 
1845   // Creating new phis must be done in post order
1846   while (regions.length() > 0) {
1847     int i = 0;
1848     for (; i < regions.length(); i+=2) {
1849       Node* r1 = regions.at(i);
1850       bool is_dom = false;
1851       for (int j = 0; j < regions.length() && !is_dom; j+=2) {
1852         if (i != j) {
1853           Node* r2 = regions.at(j);
1854           for (uint k = 1; k < r2->req() && !is_dom; k++) {
1855             if (is_dominator(r1, r2->in(k))) {
1856               is_dom = true;
1857             }
1858           }
1859         }
1860       }
1861       if (!is_dom) {
1862         break;
1863       }
1864     }
1865     assert(i < regions.length(), "need one");
1866     Node* r = regions.at(i);
1867     Node* m = regions.at(i+1);
1868     regions.delete_at(i+1);
1869     regions.delete_at(i);
1870 
1871     if (!shenandoah_suitable_mem(m, NULL, NULL)) {
1872       return false;
1873     }
1874     Node* phi = PhiNode::make(r, m, Type::MEMORY, C->get_adr_type(alias));
1875 #ifdef ASSERT
1876     if (trace) { tty->print("YYY Adding new mem phi "); phi->dump(); }
1877 #endif
1878     register_new_node(phi, r);
1879 
1880     ShenandoahWriteBarrierNode::fix_memory_uses(m, phi, phi, r, C->get_alias_index(phi->adr_type()), this);
1881     assert(phi->outcnt() != 0, "new proj should have uses");
1882     if (phi->outcnt() == 0) {
1883       _igvn.remove_dead_node(phi);
1884     }
1885   }
1886 
1887   return true;
1888 }
1889 
1890 Node* PhaseIdealLoop::shenandoah_dom_mem(Node* mem, Node*& mem_ctrl, Node* n, Node* rep_ctrl, int alias) {
1891   ResourceMark rm;
1892   VectorSet wq(Thread::current()->resource_area());
1893   wq.set(mem->_idx);
1894   mem_ctrl = get_ctrl(mem);
1895   while (!ShenandoahBarrierNode::is_dominator(mem_ctrl, rep_ctrl, mem, n, this)) {
1896     mem = next_mem(mem, alias);
1897     if (wq.test_set(mem->_idx)) {
1898       return NULL; // hit an unexpected loop
1899     }
1900     mem_ctrl = ctrl_or_self(mem);
1901   }
1902   if (mem->is_MergeMem()) {
1903     mem = mem->as_MergeMem()->memory_at(alias);
1904     mem_ctrl = ctrl_or_self(mem);
1905   }
1906   return mem;
1907 }
1908 
1909 Node* PhaseIdealLoop::try_common_shenandoah_barriers(Node* n, Node *n_ctrl) {
1910   if (n->is_ShenandoahBarrier() && !C->has_irreducible_loop()) {
1911     // We look for a write barrier whose memory edge dominates n
1912     // Either the replacement write barrier dominates n or we have,
1913     // for instance:
1914     // if ( ) {
1915     //   read barrier n
1916     // } else {
1917     //   write barrier
1918     // }
1919     // in which case replacing n by the write barrier causes the write
1920     // barrier to move above the if() and the memory Phi that merges
1921     // the memory state for both branches must be updated so both
1922     // inputs become the write barrier's memory projection (and the
1923     // Phi is optimized out) otherwise we risk loosing a memory
1924     // dependency.
1925     // Once we find a replacement write barrier, the code below fixes
1926     // the memory graph in cases like the one above.
1927     Node* val = n->in(ShenandoahBarrierNode::ValueIn);
1928     Node* val_ctrl = get_ctrl(val);
1929     Node* n_proj = n->find_out_with(Op_ShenandoahWBMemProj);
1930     Node* replacement = NULL;
1931     int alias = C->get_alias_index(n->adr_type());
1932     for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax && replacement == NULL; i++) {
1933       Node* u = val->fast_out(i);
1934       if (u != n && u->Opcode() == Op_ShenandoahWriteBarrier) {
1935         Node* u_mem = u->in(ShenandoahBarrierNode::Memory);
1936         Node* u_proj = u->find_out_with(Op_ShenandoahWBMemProj);
1937         Node* u_ctrl = get_ctrl(u);
1938         Node* u_mem_ctrl = get_ctrl(u_mem);
1939         IdealLoopTree* n_loop = get_loop(n_ctrl);
1940         IdealLoopTree* u_loop = get_loop(u_ctrl);
1941 
1942         Node* ctrl = dom_lca(u_ctrl, n_ctrl);
1943 
1944         if (ctrl->is_Proj() &&
1945             ctrl->in(0)->is_Call() &&
1946             ctrl->unique_ctrl_out() != NULL &&
1947             ctrl->unique_ctrl_out()->Opcode() == Op_Catch &&
1948             !is_dominator(val_ctrl, ctrl->in(0)->in(0))) {
1949           continue;
1950         }
1951 
1952         if (n->Opcode() == Op_ShenandoahWriteBarrier && u_proj == NULL && n_proj != NULL) {
1953           continue;
1954         }
1955 
1956         IdealLoopTree* loop = get_loop(ctrl);
1957 
1958         // we don't want to move a write barrier in a loop
1959         if (loop->is_member(u_loop) || (n->Opcode() == Op_ShenandoahWriteBarrier && loop->is_member(n_loop))) {
1960           if (ShenandoahDontIncreaseWBFreq) {
1961             Node* u_iffproj = shenandoah_no_branches(u_ctrl, ctrl, true);
1962             if (n->Opcode() == Op_ShenandoahWriteBarrier) {
1963               Node* n_iffproj = shenandoah_no_branches(n_ctrl, ctrl, true);
1964               if (u_iffproj == NULL || n_iffproj == NULL) {
1965                 replacement = u;
1966               } else if (u_iffproj != NodeSentinel && n_iffproj != NodeSentinel && u_iffproj->in(0) == n_iffproj->in(0)) {
1967                 replacement = u;
1968               }
1969             } else if (u_iffproj == NULL) {
1970               replacement = u;
1971             }
1972           } else {
1973             replacement = u;
1974           }
1975         }
1976       }
1977     }
1978     if (replacement != NULL) {
1979       Node* old_ctrl = get_ctrl(replacement);
1980       Node* rep_ctrl = dom_lca(n_ctrl, old_ctrl);
1981       if (rep_ctrl->is_Proj() &&
1982           rep_ctrl->in(0)->is_Call() &&
1983           rep_ctrl->unique_ctrl_out() != NULL &&
1984           rep_ctrl->unique_ctrl_out()->Opcode() == Op_Catch) {
1985         rep_ctrl = rep_ctrl->in(0)->in(0);
1986         assert(is_dominator(val_ctrl, rep_ctrl), "bad control");
1987       } else {
1988         Node* c = try_move_shenandoah_barrier_before_pre_loop(rep_ctrl, val_ctrl);
1989         if (c != NULL) {
1990           rep_ctrl = shenandoah_move_above_predicates(c, val_ctrl);
1991         } else {
1992           while (rep_ctrl->is_IfProj()) {
1993             CallStaticJavaNode* unc = rep_ctrl->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
1994             if (unc != NULL) {
1995               int req = unc->uncommon_trap_request();
1996               Deoptimization::DeoptReason trap_reason = Deoptimization::trap_request_reason(req);
1997               if ((trap_reason == Deoptimization::Reason_loop_limit_check ||
1998                    trap_reason == Deoptimization::Reason_predicate) && is_dominator(val_ctrl, rep_ctrl->in(0)->in(0))) {
1999                 rep_ctrl = rep_ctrl->in(0)->in(0);
2000                 continue;
2001               }
2002             }
2003             break;
2004           }
2005         }
2006       }
2007 
2008       Node* mem = replacement->in(ShenandoahBarrierNode::Memory);
2009       Node* old_mem = mem;
2010       Node* rep_proj = replacement->find_out_with(Op_ShenandoahWBMemProj);
2011       {
2012         Node* mem_ctrl = NULL;
2013 
2014         mem = shenandoah_dom_mem(mem, mem_ctrl, n, rep_ctrl, alias);
2015         if (mem == NULL) {
2016           return NULL;
2017         }
2018 
2019         // Add a memory Phi for the slice of the write barrier to any
2020         // region that post dominates rep_ctrl and doesn't have one
2021         // already.
2022         if (rep_proj != NULL && !shenandoah_fix_mem_phis(mem, mem_ctrl, rep_ctrl, alias)) {
2023           return NULL;
2024         }
2025 
2026         assert(shenandoah_memory_dominates_all_paths(mem, rep_ctrl, alias), "can't fix the memory graph");
2027       }
2028       assert(_igvn.type(mem) == Type::MEMORY, "not memory");
2029 
2030       if (rep_proj != NULL) {
2031         Node* old_mem = replacement->in(ShenandoahBarrierNode::Memory);
2032         if (!shenandoah_suitable_mem(mem, old_mem, rep_proj)) {
2033           return NULL;
2034         }
2035 
2036         if (replacement->in(ShenandoahBarrierNode::Memory) != mem) {
2037           for (DUIterator_Last imin, i = rep_proj->last_outs(imin); i >= imin; ) {
2038             Node* u = rep_proj->last_out(i);
2039             _igvn.rehash_node_delayed(u);
2040             int uses_found = u->replace_edge(rep_proj, old_mem);
2041             i -= uses_found;
2042           }
2043           _igvn.replace_input_of(replacement, ShenandoahBarrierNode::Memory, mem);
2044         }
2045         set_ctrl_and_loop(replacement, rep_ctrl);
2046         _igvn.replace_input_of(replacement, ShenandoahBarrierNode::Control, rep_ctrl);
2047 
2048         ShenandoahWriteBarrierNode::fix_memory_uses(mem, replacement, rep_proj, rep_ctrl, C->get_alias_index(replacement->adr_type()), this);
2049         assert(rep_proj->outcnt() != 0, "new proj should have uses");
2050       } else {
2051         if (replacement->in(ShenandoahBarrierNode::Memory) != mem) {
2052           _igvn._worklist.push(replacement->in(ShenandoahBarrierNode::Memory));
2053           _igvn.replace_input_of(replacement, ShenandoahBarrierNode::Memory, mem);
2054         }
2055         set_ctrl_and_loop(replacement, rep_ctrl);
2056         _igvn.replace_input_of(replacement, ShenandoahBarrierNode::Control, rep_ctrl);
2057       }
2058       if (n->Opcode() == Op_ShenandoahWriteBarrier) {
2059         if (n_proj != NULL) {
2060           lazy_replace(n_proj, n->in(ShenandoahBarrierNode::Memory));
2061         }
2062       }
2063       lazy_replace(n, replacement);
2064       if (rep_proj != NULL) {
2065         set_ctrl_and_loop(rep_proj, rep_ctrl);
2066       }
2067       return replacement;
2068     }
2069   }
2070 
2071   return NULL;
2072 }
2073 
2074 static void shenandoah_disconnect_barrier_mem(Node* wb, PhaseIterGVN& igvn) {
2075   Node* mem_in = wb->in(ShenandoahBarrierNode::Memory);
2076   Node* proj = wb->find_out_with(Op_ShenandoahWBMemProj);
2077 
2078   for (DUIterator_Last imin, i = proj->last_outs(imin); i >= imin; ) {
2079     Node* u = proj->last_out(i);
2080     igvn.rehash_node_delayed(u);
2081     int nb = u->replace_edge(proj, mem_in);
2082     assert(nb > 0, "no replacement?");
2083     i -= nb;
2084   }
2085 }
2086 
2087 Node* PhaseIdealLoop::shenandoah_move_above_predicates(Node* cl, Node* val_ctrl) {
2088   Node* entry = cl->in(LoopNode::EntryControl);
2089   Node* above_pred = skip_loop_predicates(entry);
2090   Node* ctrl = entry;
2091   while (ctrl != above_pred) {
2092     Node* next = ctrl->in(0);
2093     if (!is_dominator(val_ctrl, next)) {
2094       break;
2095     }
2096     ctrl = next;
2097   }
2098   return ctrl;
2099 }
2100 
2101 Node* PhaseIdealLoop::try_move_shenandoah_barrier_before_loop_helper(Node* n, Node* cl, Node* val_ctrl, Node* mem) {
2102   assert(cl->is_Loop(), "bad control");
2103   assert(n->Opcode() == Op_ShenandoahWriteBarrier, "only for shenandoah write barriers");
2104   Node* ctrl = shenandoah_move_above_predicates(cl, val_ctrl);
2105   Node* mem_ctrl = NULL;
2106   int alias = C->get_alias_index(n->adr_type());
2107   mem = shenandoah_dom_mem(mem, mem_ctrl, n, ctrl, alias);
2108   if (mem == NULL) {
2109     return NULL;
2110   }
2111 
2112   Node* old_mem = n->in(ShenandoahBarrierNode::Memory);
2113   Node* proj = n->find_out_with(Op_ShenandoahWBMemProj);
2114   if (old_mem != mem && !shenandoah_suitable_mem(mem, old_mem, proj)) {
2115     return NULL;
2116   }
2117 
2118   assert(shenandoah_memory_dominates_all_paths(mem, ctrl, alias), "can't fix the memory graph");
2119   set_ctrl_and_loop(n, ctrl);
2120   _igvn.replace_input_of(n, ShenandoahBarrierNode::Control, ctrl);
2121   if (old_mem != mem) {
2122     if (proj != NULL) {
2123       shenandoah_disconnect_barrier_mem(n, _igvn);
2124       ShenandoahWriteBarrierNode::fix_memory_uses(mem, n, proj, ctrl, C->get_alias_index(n->adr_type()), this);
2125       assert(proj->outcnt() > 0, "disconnected write barrier");
2126     }
2127     _igvn.replace_input_of(n, ShenandoahBarrierNode::Memory, mem);
2128   }
2129   if (proj != NULL) {
2130     set_ctrl_and_loop(proj, ctrl);
2131   }
2132   return n;
2133 }
2134 
2135 Node* PhaseIdealLoop::try_move_shenandoah_barrier_before_pre_loop(Node* c, Node* val_ctrl) {
2136   // A write barrier between a pre and main loop can get in the way of
2137   // vectorization. Move it above the pre loop if possible
2138   CountedLoopNode* cl = NULL;
2139   if (c->is_IfFalse() &&
2140       c->in(0)->is_CountedLoopEnd()) {
2141     cl = c->in(0)->as_CountedLoopEnd()->loopnode();
2142   } else if (c->is_IfProj() &&
2143              c->in(0)->is_If() &&
2144              c->in(0)->in(0)->is_IfFalse() &&
2145              c->in(0)->in(0)->in(0)->is_CountedLoopEnd()) {
2146     cl = c->in(0)->in(0)->in(0)->as_CountedLoopEnd()->loopnode();
2147   }
2148   if (cl != NULL &&
2149       cl->is_pre_loop() &&
2150       val_ctrl != cl &&
2151       is_dominator(val_ctrl, cl)) {
2152     return cl;
2153   }
2154   return NULL;
2155 }
2156 
2157 Node* PhaseIdealLoop::try_move_shenandoah_barrier_before_loop(Node* n, Node *n_ctrl) {
2158   if (n->Opcode() == Op_ShenandoahWriteBarrier) {
2159     IdealLoopTree *n_loop = get_loop(n_ctrl);
2160     Node* val = n->in(ShenandoahBarrierNode::ValueIn);
2161     Node* val_ctrl = get_ctrl(val);
2162     if (n_loop != _ltree_root && !n_loop->_irreducible) {
2163       IdealLoopTree *val_loop = get_loop(val_ctrl);
2164       Node* mem = n->in(ShenandoahBarrierNode::Memory);
2165       IdealLoopTree *mem_loop = get_loop(get_ctrl(mem));
2166       if (!n_loop->is_member(val_loop) &&
2167           n_loop->is_member(mem_loop)) {
2168         Node* n_loop_head = n_loop->_head;
2169 
2170         if (n_loop_head->is_Loop()) {
2171           Node* loop = n_loop_head;
2172           if (n_loop_head->is_CountedLoop() && n_loop_head->as_CountedLoop()->is_main_loop()) {
2173             Node* res = try_move_shenandoah_barrier_before_pre_loop(n_loop_head->in(LoopNode::EntryControl), val_ctrl);
2174             if (res != NULL) {
2175               loop = res;
2176             }
2177           }
2178 
2179           return try_move_shenandoah_barrier_before_loop_helper(n, loop, val_ctrl, mem);
2180         }
2181       }
2182     }
2183     Node* ctrl = try_move_shenandoah_barrier_before_pre_loop(n->in(0), val_ctrl);
2184     if (ctrl != NULL) {
2185       return try_move_shenandoah_barrier_before_loop_helper(n, ctrl, val_ctrl, n->in(ShenandoahBarrierNode::Memory));
2186     }
2187   }
2188   return NULL;
2189 }
2190 
2191 void PhaseIdealLoop::try_move_shenandoah_read_barrier(Node* n, Node *n_ctrl) {
2192   if (n->Opcode() == Op_ShenandoahReadBarrier) {
2193     ShenandoahReadBarrierNode* rb = (ShenandoahReadBarrierNode*)n;
2194     Node* mem = n->in(MemNode::Memory);
2195     int alias = C->get_alias_index(n->adr_type());
2196     const bool trace = false;
2197 
2198 #ifdef ASSERT
2199     if (trace) { tty->print("Trying to move mem of"); n->dump(); }
2200 #endif
2201 
2202     Node* new_mem = mem;
2203 
2204     ResourceMark rm;
2205     VectorSet seen(Thread::current()->resource_area());
2206     Node_List phis;
2207 
2208     for (;;) {
2209 #ifdef ASSERT
2210       if (trace) { tty->print("Looking for dominator from"); mem->dump(); }
2211 #endif
2212       if (mem->is_Proj() && mem->in(0)->is_Start()) {
2213         if (new_mem != n->in(MemNode::Memory)) {
2214 #ifdef ASSERT
2215           if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); n->dump(); }
2216 #endif
2217           _igvn.replace_input_of(n, MemNode::Memory, new_mem);
2218         }
2219         return;
2220       }
2221 
2222       Node* candidate = mem;
2223       do {
2224         if (!rb->is_independent(mem)) {
2225           if (trace) { tty->print_cr("Not independent"); }
2226           if (new_mem != n->in(MemNode::Memory)) {
2227 #ifdef ASSERT
2228             if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); n->dump(); }
2229 #endif
2230             _igvn.replace_input_of(n, MemNode::Memory, new_mem);
2231           }
2232           return;
2233         }
2234         if (seen.test_set(mem->_idx)) {
2235           if (trace) { tty->print_cr("Already seen"); }
2236           ShouldNotReachHere();
2237           // Strange graph
2238           if (new_mem != n->in(MemNode::Memory)) {
2239 #ifdef ASSERT
2240             if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); n->dump(); }
2241 #endif
2242             _igvn.replace_input_of(n, MemNode::Memory, new_mem);
2243           }
2244           return;
2245         }
2246         if (mem->is_Phi()) {
2247           phis.push(mem);
2248         }
2249         mem = next_mem(mem, alias);
2250         if (mem->bottom_type() == Type::MEMORY) {
2251           candidate = mem;
2252         }
2253         assert(ShenandoahBarrierNode::is_dominator(ctrl_or_self(mem), n_ctrl, mem, n, this) == is_dominator(ctrl_or_self(mem), n_ctrl), "strange dominator");
2254 #ifdef ASSERT
2255         if (trace) { tty->print("Next mem is"); mem->dump(); }
2256 #endif
2257       } while (mem->bottom_type() != Type::MEMORY || !is_dominator(ctrl_or_self(mem), n_ctrl));
2258 
2259       assert(mem->bottom_type() == Type::MEMORY, "bad mem");
2260 
2261       bool not_dom = false;
2262       for (uint i = 0; i < phis.size() && !not_dom; i++) {
2263         Node* nn = phis.at(i);
2264 
2265 #ifdef ASSERT
2266         if (trace) { tty->print("Looking from phi"); nn->dump(); }
2267 #endif
2268         assert(nn->is_Phi(), "phis only");
2269         for (uint j = 2; j < nn->req() && !not_dom; j++) {
2270           Node* m = nn->in(j);
2271 #ifdef ASSERT
2272           if (trace) { tty->print("Input %d is", j); m->dump(); }
2273 #endif
2274           while (m != mem && !seen.test_set(m->_idx)) {
2275             if (ShenandoahBarrierNode::is_dominator(ctrl_or_self(m), ctrl_or_self(mem), m, mem, this)) {
2276               not_dom = true;
2277               // Scheduling anomaly
2278 #ifdef ASSERT
2279               if (trace) { tty->print("Giving up"); m->dump(); }
2280 #endif
2281               break;
2282             }
2283             if (!rb->is_independent(m)) {
2284               if (trace) { tty->print_cr("Not independent"); }
2285               if (new_mem != n->in(MemNode::Memory)) {
2286 #ifdef ASSERT
2287                 if (trace) { tty->print("XXX Setting mem to"); new_mem->dump(); tty->print(" for "); n->dump(); }
2288 #endif
2289                 _igvn.replace_input_of(n, MemNode::Memory, new_mem);
2290               }
2291               return;
2292             }
2293             if (m->is_Phi()) {
2294               phis.push(m);
2295             }
2296             m = next_mem(m, alias);
2297 #ifdef ASSERT
2298             if (trace) { tty->print("Next mem is"); m->dump(); }
2299 #endif
2300           }
2301         }
2302       }
2303       if (!not_dom) {
2304         new_mem = mem;
2305         phis.clear();
2306       } else {
2307         seen.Clear();
2308       }
2309     }
2310   }
2311 }
2312 
2313 CallStaticJavaNode* PhaseIdealLoop::shenandoah_pin_and_expand_barriers_null_check(ShenandoahBarrierNode* wb) {
2314   Node* val = wb->in(ShenandoahBarrierNode::ValueIn);
2315 
2316 #ifdef ASSERT
2317   const Type* val_t = _igvn.type(val);
2318   assert(val_t->meet(TypePtr::NULL_PTR) != val_t, "should be not null");
2319 #endif
2320 
2321   if (val->Opcode() == Op_CastPP &&
2322       val->in(0) != NULL &&
2323       val->in(0)->Opcode() == Op_IfTrue &&
2324       val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
2325       val->in(0)->in(0)->is_If() &&
2326       val->in(0)->in(0)->in(1)->Opcode() == Op_Bool &&
2327       val->in(0)->in(0)->in(1)->as_Bool()->_test._test == BoolTest::ne &&
2328       val->in(0)->in(0)->in(1)->in(1)->Opcode() == Op_CmpP &&
2329       val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1) &&
2330       val->in(0)->in(0)->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
2331     assert(val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1), "");
2332     CallStaticJavaNode* unc = val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
2333     return unc;
2334   }
2335   return NULL;
2336 }
2337 
2338 void PhaseIdealLoop::shenandoah_pin_and_expand_barriers_move_barrier(ShenandoahBarrierNode* wb) {
2339   Node* unc = shenandoah_pin_and_expand_barriers_null_check(wb);
2340   Node* val = wb->in(ShenandoahBarrierNode::ValueIn);
2341 
2342   if (unc != NULL) {
2343     Node* ctrl = get_ctrl(wb);
2344     Node* unc_ctrl = val->in(0);
2345 
2346     Node* branch = shenandoah_no_branches(ctrl, unc_ctrl, false);
2347     assert(branch == NULL || branch == NodeSentinel, "was not looking for a branch");
2348     if (branch == NodeSentinel) {
2349       return;
2350     }
2351 
2352     Node* mem = wb->in(ShenandoahBarrierNode::Memory);
2353     Node* old_mem = mem;
2354 
2355     Node* mem_ctrl = NULL;
2356     int alias = C->get_alias_index(wb->adr_type());
2357     mem = shenandoah_dom_mem(mem, mem_ctrl, wb, unc_ctrl, alias);
2358     if (mem == NULL) {
2359       return;
2360     }
2361 
2362     Node* proj = wb->find_out_with(Op_ShenandoahWBMemProj);
2363     if (mem != old_mem && !shenandoah_fix_mem_phis(mem, mem_ctrl, unc_ctrl, alias)) {
2364       return;
2365     }
2366 
2367     assert(mem == old_mem || shenandoah_memory_dominates_all_paths(mem, unc_ctrl, alias), "can't fix the memory graph");
2368     set_ctrl_and_loop(wb, unc_ctrl);
2369     if (wb->in(ShenandoahBarrierNode::Control) != NULL) {
2370       _igvn.replace_input_of(wb, ShenandoahBarrierNode::Control, unc_ctrl);
2371     }
2372     shenandoah_disconnect_barrier_mem(wb, _igvn);
2373     ShenandoahWriteBarrierNode::fix_memory_uses(mem, wb, proj, unc_ctrl, C->get_alias_index(wb->adr_type()), this);
2374     assert(proj->outcnt() > 0, "disconnected write barrier");
2375     _igvn.replace_input_of(wb, ShenandoahBarrierNode::Memory, mem);
2376     set_ctrl_and_loop(proj, unc_ctrl);
2377   }
2378 }
2379 
2380 Node* PhaseIdealLoop::shenandoah_pick_phi(Node* phi1, Node* phi2, Node_Stack& phis, VectorSet& visited) {
2381   assert(phis.size() == 0, "stack needs to be empty");
2382   uint i = 1;
2383   int phi_dominates = -1;
2384   for (;;) {
2385     assert(phi1->req() == phi2->req(), "strange pair of phis");
2386     assert(phis.size() % 2 == 0, "");
2387     Node* in1 = phi1->in(i);
2388     Node* in2 = phi2->in(i);
2389 
2390     if (in1->is_MergeMem()) {
2391       in1 = in1->as_MergeMem()->base_memory();
2392     }
2393     if (in2->is_MergeMem()) {
2394       in2 = in2->as_MergeMem()->base_memory();
2395     }
2396 
2397     if (in1 == in2) {
2398       //continue
2399     } else if (in1->is_Phi() && in2->is_Phi() && in1->in(0) == in2->in(0)) {
2400       assert(!visited.test_set(in1->_idx), "no loop");
2401       assert(!visited.test_set(in2->_idx), "no loop");
2402       phis.push(phi1, i+1);
2403       phis.push(phi2, i+1);
2404       phi1 = in1;
2405       phi2 = in2;
2406       i = 1;
2407     } else {
2408       Node* in1_c = get_ctrl(in1);
2409       Node* in2_c = get_ctrl(in2);
2410       if (ShenandoahBarrierNode::is_dominator(in1_c, in2_c, in1, in2, this)) {
2411         assert(!ShenandoahBarrierNode::is_dominator(in2_c, in1_c, in2, in1, this), "one has to dominate the other");
2412         assert(phi_dominates == -1 || phi_dominates == 1, "all inputs must dominate");
2413         phi_dominates = 1;
2414       } else {
2415         assert(ShenandoahBarrierNode::is_dominator(in2_c, in1_c, in2, in1, this), "one must dominate the other");
2416         assert(!ShenandoahBarrierNode::is_dominator(in1_c, in2_c, in1, in2, this), "one has to dominate the other");
2417         assert(phi_dominates == -1 || phi_dominates == 2, "all inputs must dominate");
2418         phi_dominates = 2;
2419       }
2420     }
2421     i++;
2422 
2423     while (i >= phi1->req() && phis.size() > 0) {
2424       i = phis.index();
2425       phi2 = phis.node();
2426       phis.pop();
2427       phi1 = phis.node();
2428       phis.pop();
2429     }
2430 
2431     if (i >= phi1->req() && phis.size() == 0) {
2432       Node* phi = NULL;
2433       if (phi_dominates == 1) {
2434         return phi2;
2435       } else if (phi_dominates == 2) {
2436         return phi1;
2437       } else {
2438         return phi1;
2439       }
2440     }
2441   }
2442   return NULL;
2443 }
2444 
2445 bool ShenandoahWriteBarrierNode::mem_is_valid(Node* m, Node* c, PhaseIdealLoop* phase) {
2446   return m != NULL && get_ctrl(m, phase) == c;
2447 }
2448 
2449 Node* ShenandoahWriteBarrierNode::find_raw_mem(Node* ctrl, Node* n, const Node_List& memory_nodes, PhaseIdealLoop* phase) {
2450   assert(n == NULL || phase->ctrl_or_self(n) == ctrl, "");
2451   Node* raw_mem = memory_nodes[ctrl->_idx];
2452   Node* c = ctrl;
2453   while (!mem_is_valid(raw_mem, c, phase) &&
2454          (!c->is_CatchProj() || raw_mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(raw_mem, phase))) {
2455     c = phase->idom(c);
2456     raw_mem = memory_nodes[c->_idx];
2457   }
2458   if (n != NULL && mem_is_valid(raw_mem, c, phase)) {
2459     while (!is_dominator_same_ctrl(c, raw_mem, n, phase) && phase->ctrl_or_self(raw_mem) == ctrl) {
2460       raw_mem = next_mem(raw_mem, Compile::AliasIdxRaw);
2461     }
2462     if (raw_mem->is_MergeMem()) {
2463       raw_mem = raw_mem->as_MergeMem()->memory_at(Compile::AliasIdxRaw);
2464     }
2465     if (!mem_is_valid(raw_mem, c, phase)) {
2466       do {
2467         c = phase->idom(c);
2468         raw_mem = memory_nodes[c->_idx];
2469       } while (!mem_is_valid(raw_mem, c, phase) &&
2470                (!c->is_CatchProj() || raw_mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(raw_mem, phase)));
2471     }
2472   }
2473   assert(raw_mem->bottom_type() == Type::MEMORY, "");
2474   return raw_mem;
2475 }
2476 
2477 Node* PhaseIdealLoop::shenandoah_find_bottom_mem(Node* ctrl) {
2478   Node* mem = NULL;
2479   Node* c = ctrl;
2480   do {
2481     if (c->is_Region()) {
2482       Node* phi_bottom = NULL;
2483       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
2484         Node* u = c->fast_out(i);
2485         if (u->is_Phi() && u->bottom_type() == Type::MEMORY) {
2486           if (u->adr_type() == TypePtr::BOTTOM) {
2487             if (phi_bottom != NULL) {
2488               phi_bottom = NodeSentinel;
2489             } else {
2490               phi_bottom = u;
2491             }
2492           }
2493         }
2494       }
2495       if (phi_bottom != NULL) {
2496         if (phi_bottom != NodeSentinel) {
2497           mem = phi_bottom;
2498         } else {
2499           Node* phi = NULL;
2500           ResourceMark rm;
2501           Node_Stack phis(0);
2502           VectorSet visited(Thread::current()->resource_area());
2503           for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
2504             Node* u = c->fast_out(i);
2505             if (u->is_Phi() && u->bottom_type() == Type::MEMORY && u->adr_type() == TypePtr::BOTTOM) {
2506               if (phi == NULL) {
2507                 phi = u;
2508               } else {
2509                 phi = shenandoah_pick_phi(phi, u, phis, visited);
2510               }
2511             }
2512           }
2513           mem = phi;
2514         }
2515       }
2516     } else {
2517       if (c->is_Call() && c->as_Call()->adr_type() != NULL) {
2518         CallProjections projs;
2519         c->as_Call()->extract_projections(&projs, true, false);
2520         if (projs.fallthrough_memproj != NULL) {
2521           if (projs.fallthrough_memproj->adr_type() == TypePtr::BOTTOM) {
2522             if (projs.catchall_memproj == NULL) {
2523               mem = projs.fallthrough_memproj;
2524             } else {
2525               if (is_dominator(projs.fallthrough_catchproj, ctrl)) {
2526                 mem = projs.fallthrough_memproj;
2527               } else {
2528                 assert(is_dominator(projs.catchall_catchproj, ctrl), "one proj must dominate barrier");
2529                 mem = projs.catchall_memproj;
2530               }
2531             }
2532           }
2533         } else {
2534           Node* proj = c->as_Call()->proj_out(TypeFunc::Memory);
2535           if (proj != NULL &&
2536               proj->adr_type() == TypePtr::BOTTOM) {
2537             mem = proj;
2538           }
2539         }
2540       } else {
2541         for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
2542           Node* u = c->fast_out(i);
2543           if (u->is_Proj() &&
2544               u->bottom_type() == Type::MEMORY &&
2545               u->adr_type() == TypePtr::BOTTOM) {
2546               assert(c->is_SafePoint() || c->is_MemBar() || c->is_Start(), "");
2547               assert(mem == NULL, "only one proj");
2548               mem = u;
2549           }
2550         }
2551         assert(!c->is_Call() || c->as_Call()->adr_type() != NULL || mem == NULL, "no mem projection expected");
2552       }
2553     }
2554     c = idom(c);
2555   } while (mem == NULL);
2556   return mem;
2557 }
2558 
2559 void PhaseIdealLoop::shenandoah_follow_barrier_uses(Node* n, Node* ctrl, Unique_Node_List& uses) {
2560   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2561     Node* u = n->fast_out(i);
2562     if (!u->is_CFG() && get_ctrl(u) == ctrl && (!u->is_Phi() || !u->in(0)->is_Loop() || u->in(LoopNode::LoopBackControl) != n)) {
2563       uses.push(u);
2564     }
2565   }
2566 }
2567 
2568 Node* ShenandoahWriteBarrierNode::get_ctrl(Node* n, PhaseIdealLoop* phase) {
2569   Node* c = phase->get_ctrl(n);
2570   if (n->is_Proj() && n->in(0)->is_Call()) {
2571     assert(c == n->in(0), "");
2572     CallNode* call = c->as_Call();
2573     CallProjections projs;
2574     call->extract_projections(&projs, true, false);
2575     if (projs.catchall_memproj != NULL) {
2576       if (projs.fallthrough_memproj == n) {
2577         c = projs.fallthrough_catchproj;
2578       } else {
2579         assert(projs.catchall_memproj == n, "");
2580         c = projs.catchall_catchproj;
2581       }
2582     }
2583   }
2584   return c;
2585 }
2586 
2587 Node* ShenandoahWriteBarrierNode::ctrl_or_self(Node* n, PhaseIdealLoop* phase) {
2588   if (phase->has_ctrl(n))
2589     return get_ctrl(n, phase);
2590   else {
2591     assert (n->is_CFG(), "must be a CFG node");
2592     return n;
2593   }
2594 }
2595 
2596 #ifdef ASSERT
2597 static bool has_never_branch(Node* root) {
2598   for (uint i = 1; i < root->req(); i++) {
2599     Node* in = root->in(i);
2600     if (in != NULL && in->Opcode() == Op_Halt && in->in(0)->is_Proj() && in->in(0)->in(0)->Opcode() == Op_NeverBranch) {
2601       return true;
2602     }
2603   }
2604   return false;
2605 }
2606 #endif
2607 
2608 void ShenandoahWriteBarrierNode::collect_memory_nodes(int alias, Node_List& memory_nodes, PhaseIdealLoop* phase) {
2609   Node_Stack stack(0);
2610   VectorSet visited(Thread::current()->resource_area());
2611   Node_List regions;
2612 
2613   // Walk the raw memory graph and create a mapping from CFG node to
2614   // memory node. Exclude phis for now.
2615   stack.push(phase->C->root(), 1);
2616   do {
2617     Node* n = stack.node();
2618     int opc = n->Opcode();
2619     uint i = stack.index();
2620     if (i < n->req()) {
2621       Node* mem = NULL;
2622       if (opc == Op_Root) {
2623         Node* in = n->in(i);
2624         int in_opc = in->Opcode();
2625         if (in_opc == Op_Return || in_opc == Op_Rethrow) {
2626           mem = in->in(TypeFunc::Memory);
2627         } else if (in_opc == Op_Halt) {
2628           if (in->in(0)->is_Region()) {
2629 #ifdef ASSERT
2630             Node* r = in->in(0);
2631             for (uint j = 1; j <  r->req(); j++) {
2632               assert(r->in(j)->is_Proj() && r->in(j)->in(0)->Opcode() == Op_NeverBranch, "");
2633             }
2634 #endif
2635           } else {
2636             Node* proj = in->in(0);
2637             assert(proj->is_Proj(), "");
2638             Node* in = proj->in(0);
2639             assert(in->is_CallStaticJava() || in->Opcode() == Op_NeverBranch || in->Opcode() == Op_Catch, "");
2640             if (in->is_CallStaticJava()) {
2641               mem = in->in(TypeFunc::Memory);
2642             } else if (in->Opcode() == Op_Catch) {
2643               Node* call = in->in(0)->in(0);
2644               assert(call->is_Call(), "");
2645               mem = call->in(TypeFunc::Memory);
2646             }
2647           }
2648         } else {
2649 #ifdef ASSERT
2650           n->dump();
2651           in->dump();
2652 #endif
2653           ShouldNotReachHere();
2654         }
2655       } else {
2656         assert(n->is_Phi() && n->bottom_type() == Type::MEMORY, "");
2657         assert(n->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(n->adr_type()) == alias, "");
2658         mem = n->in(i);
2659       }
2660       i++;
2661       stack.set_index(i);
2662       if (mem == NULL) {
2663         continue;
2664       }
2665       for (;;) {
2666         if (visited.test_set(mem->_idx) || mem->is_Start()) {
2667           break;
2668         }
2669         if (mem->is_Phi()) {
2670           stack.push(mem, 2);
2671           mem = mem->in(1);
2672         } else if (mem->is_Proj()) {
2673           stack.push(mem, mem->req());
2674           mem = mem->in(0);
2675         } else if (mem->is_SafePoint() || mem->is_MemBar()) {
2676           mem = mem->in(TypeFunc::Memory);
2677         } else if (mem->is_MergeMem()) {
2678           mem = mem->as_MergeMem()->memory_at(alias);
2679         } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
2680           stack.push(mem, mem->req());
2681           mem = mem->in(MemNode::Memory);
2682         } else {
2683 #ifdef ASSERT
2684           mem->dump();
2685 #endif
2686           ShouldNotReachHere();
2687         }
2688       }
2689     } else {
2690       if (n->is_Phi()) {
2691         // Nothing
2692       } else if (!n->is_Root()) {
2693         Node* c = get_ctrl(n, phase);
2694         memory_nodes.map(c->_idx, n);
2695       }
2696       stack.pop();
2697     }
2698   } while(stack.is_nonempty());
2699 
2700   // Iterate over CFG nodes in rpo and propagate memory state to
2701   // compute memory state at regions, creating new phis if needed.
2702   Node_List rpo_list;
2703   visited.Clear();
2704   phase->rpo(phase->C->root(), stack, visited, rpo_list);
2705   Node* root = rpo_list.pop();
2706   assert(root == phase->C->root(), "");
2707 
2708   const bool trace = false;
2709 #ifdef ASSERT
2710   if (trace) {
2711     for (int i = rpo_list.size() - 1; i >= 0; i--) {
2712       Node* c = rpo_list.at(i);
2713       if (memory_nodes[c->_idx] != NULL) {
2714         tty->print("X %d", c->_idx);  memory_nodes[c->_idx]->dump();
2715       }
2716     }
2717   }
2718 #endif
2719   uint last = phase->C->unique();
2720 
2721 #ifdef ASSERT
2722   uint8_t max_depth = 0;
2723   for (LoopTreeIterator iter(phase->ltree_root()); !iter.done(); iter.next()) {
2724     IdealLoopTree* lpt = iter.current();
2725     max_depth = MAX2(max_depth, lpt->_nest);
2726   }
2727 #endif
2728 
2729   bool progress = true;
2730   int iteration = 0;
2731   Node_List dead_phis;
2732   while (progress) {
2733     progress = false;
2734     iteration++;
2735     assert(iteration <= 2+max_depth || phase->C->has_irreducible_loop(), "");
2736     if (trace) { tty->print_cr("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"); }
2737     IdealLoopTree* last_updated_ilt = NULL;
2738     for (int i = rpo_list.size() - 1; i >= 0; i--) {
2739       Node* c = rpo_list.at(i);
2740 
2741       Node* prev_mem = memory_nodes[c->_idx];
2742       if (c->is_Region()) {
2743         Node* prev_region = regions[c->_idx];
2744         Node* unique = NULL;
2745         for (uint j = 1; j < c->req() && unique != NodeSentinel; j++) {
2746           Node* m = memory_nodes[c->in(j)->_idx];
2747           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");
2748           if (m != NULL) {
2749             if (m == prev_region && ((c->is_Loop() && j == LoopNode::LoopBackControl) || (prev_region->is_Phi() && prev_region->in(0) == c))) {
2750               assert(c->is_Loop() && j == LoopNode::LoopBackControl || phase->C->has_irreducible_loop(), "");
2751               // continue
2752             } else if (unique == NULL) {
2753               unique = m;
2754             } else if (m == unique) {
2755               // continue
2756             } else {
2757               unique = NodeSentinel;
2758             }
2759           }
2760         }
2761         assert(unique != NULL, "empty phi???");
2762         if (unique != NodeSentinel) {
2763           if (prev_region != NULL && prev_region->is_Phi() && prev_region->in(0) == c) {
2764             dead_phis.push(prev_region);
2765           }
2766           regions.map(c->_idx, unique);
2767         } else {
2768           Node* phi = NULL;
2769           if (prev_region != NULL && prev_region->is_Phi() && prev_region->in(0) == c && prev_region->_idx >= last) {
2770             phi = prev_region;
2771             for (uint k = 1; k < c->req(); k++) {
2772               Node* m = memory_nodes[c->in(k)->_idx];
2773               assert(m != NULL, "expect memory state");
2774               phi->set_req(k, m);
2775             }
2776           } else {
2777             for (DUIterator_Fast jmax, j = c->fast_outs(jmax); j < jmax && phi == NULL; j++) {
2778               Node* u = c->fast_out(j);
2779               if (u->is_Phi() && u->bottom_type() == Type::MEMORY &&
2780                   (u->adr_type() == TypePtr::BOTTOM || phase->C->get_alias_index(u->adr_type()) == alias)) {
2781                 phi = u;
2782                 for (uint k = 1; k < c->req() && phi != NULL; k++) {
2783                   Node* m = memory_nodes[c->in(k)->_idx];
2784                   assert(m != NULL, "expect memory state");
2785                   if (u->in(k) != m) {
2786                     phi = NULL;
2787                   }
2788                 }
2789               }
2790             }
2791             if (phi == NULL) {
2792               phi = new (phase->C) PhiNode(c, Type::MEMORY, phase->C->get_adr_type(alias));
2793               for (uint k = 1; k < c->req(); k++) {
2794                 Node* m = memory_nodes[c->in(k)->_idx];
2795                 assert(m != NULL, "expect memory state");
2796                 phi->init_req(k, m);
2797               }
2798             }
2799           }
2800           assert(phi != NULL, "");
2801           regions.map(c->_idx, phi);
2802         }
2803         Node* current_region = regions[c->_idx];
2804         if (current_region != prev_region) {
2805           progress = true;
2806           if (prev_region == prev_mem) {
2807             memory_nodes.map(c->_idx, current_region);
2808           }
2809         }
2810       } else if (prev_mem == NULL || prev_mem->is_Phi() || ctrl_or_self(prev_mem, phase) != c) {
2811         Node* m = memory_nodes[phase->idom(c)->_idx];
2812         assert(m != NULL, "expect memory state");
2813         if (m != prev_mem) {
2814           memory_nodes.map(c->_idx, m);
2815           progress = true;
2816         }
2817       }
2818 #ifdef ASSERT
2819       if (trace) { tty->print("X %d", c->_idx);  memory_nodes[c->_idx]->dump(); }
2820 #endif
2821     }
2822   }
2823 
2824   // Replace existing phi with computed memory state for that region
2825   // if different (could be a new phi or a dominating memory node if
2826   // that phi was found to be useless).
2827   while (dead_phis.size() > 0) {
2828     Node* n = dead_phis.pop();
2829     n->replace_by(phase->C->top());
2830     n->destruct();
2831   }
2832   for (int i = rpo_list.size() - 1; i >= 0; i--) {
2833     Node* c = rpo_list.at(i);
2834     if (c->is_Region()) {
2835       Node* n = regions[c->_idx];
2836       if (n->is_Phi() && n->_idx >= last && n->in(0) == c) {
2837         phase->register_new_node(n, c);
2838       }
2839     }
2840   }
2841   for (int i = rpo_list.size() - 1; i >= 0; i--) {
2842     Node* c = rpo_list.at(i);
2843     if (c->is_Region()) {
2844       Node* n = regions[c->_idx];
2845       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
2846         Node* u = c->fast_out(i);
2847         if (u->is_Phi() && u->bottom_type() == Type::MEMORY &&
2848             u != n) {
2849           if (u->adr_type() == TypePtr::BOTTOM) {
2850             fix_memory_uses(u, n, n, c, alias, phase);
2851           } else if (phase->C->get_alias_index(u->adr_type()) == alias) {
2852             phase->lazy_replace(u, n);
2853             --i; --imax;
2854           }
2855         }
2856       }
2857     }
2858   }
2859 }
2860 
2861 void ShenandoahWriteBarrierNode::fix_raw_mem(Node* ctrl, Node* region, Node* raw_mem, Node* raw_mem_for_ctrl, Node* raw_mem_phi,
2862                                              Node_List& memory_nodes, Unique_Node_List& uses, PhaseIdealLoop* phase) {
2863   const bool trace = false;
2864   DEBUG_ONLY(if (trace) { tty->print("ZZZ control is"); ctrl->dump(); });
2865   DEBUG_ONLY(if (trace) { tty->print("ZZZ mem is"); raw_mem->dump(); });
2866   GrowableArray<Node*> phis;
2867   if (raw_mem_for_ctrl != raw_mem) {
2868     Node* old = raw_mem_for_ctrl;
2869     Node* prev = NULL;
2870     while (old != raw_mem) {
2871       assert(old->is_Store() || old->is_LoadStore() || old->is_ClearArray(), "");
2872       prev = old;
2873       old = old->in(MemNode::Memory);
2874     }
2875     assert(prev != NULL, "");
2876     memory_nodes.map(ctrl->_idx, raw_mem);
2877     memory_nodes.map(region->_idx, raw_mem_for_ctrl);
2878     phase->igvn().replace_input_of(prev, MemNode::Memory, raw_mem_phi);
2879   } else {
2880     memory_nodes.map(region->_idx, raw_mem_phi);
2881     uses.clear();
2882     uses.push(region);
2883     for(uint next = 0; next < uses.size(); next++ ) {
2884       Node *n = uses.at(next);
2885       assert(n->is_CFG(), "");
2886       DEBUG_ONLY(if (trace) { tty->print("ZZZ ctrl"); n->dump(); });
2887       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2888         Node* u = n->fast_out(i);
2889         if (!u->is_Root() && u->is_CFG() && u != n) {
2890           Node* m = memory_nodes[u->_idx];
2891           if (u->is_Region() && !has_mem_phi(phase->C, u, Compile::AliasIdxRaw)) {
2892             DEBUG_ONLY(if (trace) { tty->print("ZZZ region"); u->dump(); });
2893             DEBUG_ONLY(if (trace && m != NULL) { tty->print("ZZZ mem"); m->dump(); });
2894 
2895             if (!mem_is_valid(m, u, phase) || !m->is_Phi()) {
2896               bool push = true;
2897               bool create_phi = true;
2898               if (phase->is_dominator(region, u)) {
2899                 create_phi = false;
2900               } else if (!phase->C->has_irreducible_loop()) {
2901                 IdealLoopTree* loop = phase->get_loop(ctrl);
2902                 bool do_check = true;
2903                 IdealLoopTree* l = loop;
2904                 create_phi = false;
2905                 while (l != phase->ltree_root()) {
2906                   if (phase->is_dominator(l->_head, u) && phase->is_dominator(phase->idom(u), l->_head)) {
2907                     create_phi = true;
2908                     do_check = false;
2909                     break;
2910                   }
2911                   l = l->_parent;
2912                 }
2913 
2914                 if (do_check) {
2915                   assert(!create_phi, "");
2916                   IdealLoopTree* u_loop = phase->get_loop(u);
2917                   if (u_loop != phase->ltree_root() && u_loop->is_member(loop)) {
2918                     Node* c = ctrl;
2919                     while (!phase->is_dominator(c, u_loop->tail())) {
2920                       c = phase->idom(c);
2921                     }
2922                     if (!phase->is_dominator(c, u)) {
2923                       do_check = false;
2924                     }
2925                   }
2926                 }
2927 
2928                 if (do_check && phase->is_dominator(phase->idom(u), region)) {
2929                   create_phi = true;
2930                 }
2931               }
2932               if (create_phi) {
2933                 Node* phi = new (phase->C) PhiNode(u, Type::MEMORY, TypeRawPtr::BOTTOM);
2934                 phase->register_new_node(phi, u);
2935                 phis.push(phi);
2936                 DEBUG_ONLY(if (trace) { tty->print("ZZZ new phi"); phi->dump(); });
2937                 if (!mem_is_valid(m, u, phase)) {
2938                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting mem"); phi->dump(); });
2939                   memory_nodes.map(u->_idx, phi);
2940                 } else {
2941                   DEBUG_ONLY(if (trace) { tty->print("ZZZ NOT setting mem"); m->dump(); });
2942                   for (;;) {
2943                     assert(m->is_Mem() || m->is_LoadStore() || m->is_Proj() /*|| m->is_MergeMem()*/, "");
2944                     Node* next = NULL;
2945                     if (m->is_Proj()) {
2946                       next = m->in(0);
2947                     } else {
2948                       next = m->in(MemNode::Memory);
2949                     }
2950                     if (phase->get_ctrl(next) != u) {
2951                       break;
2952                     }
2953                     if (next->is_MergeMem()) {
2954                       assert(phase->get_ctrl(next->as_MergeMem()->memory_at(Compile::AliasIdxRaw)) != u, "");
2955                       break;
2956                     }
2957                     if (next->is_Phi()) {
2958                       assert(next->adr_type() == TypePtr::BOTTOM && next->in(0) == u, "");
2959                       break;
2960                     }
2961                     m = next;
2962                   }
2963 
2964                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting to phi"); m->dump(); });
2965                   assert(m->is_Mem() || m->is_LoadStore(), "");
2966                   phase->igvn().replace_input_of(m, MemNode::Memory, phi);
2967                   push = false;
2968                 }
2969               } else {
2970                 DEBUG_ONLY(if (trace) { tty->print("ZZZ skipping region"); u->dump(); });
2971               }
2972               if (push) {
2973                 uses.push(u);
2974               }
2975             }
2976           } else if (!mem_is_valid(m, u, phase) &&
2977                      !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1)) {
2978             uses.push(u);
2979           }
2980         }
2981       }
2982     }
2983     for (int i = 0; i < phis.length(); i++) {
2984       Node* n = phis.at(i);
2985       Node* r = n->in(0);
2986       DEBUG_ONLY(if (trace) { tty->print("ZZZ fixing new phi"); n->dump(); });
2987       for (uint j = 1; j < n->req(); j++) {
2988         Node* m = find_raw_mem(r->in(j), NULL, memory_nodes, phase);
2989         phase->igvn().replace_input_of(n, j, m);
2990         DEBUG_ONLY(if (trace) { tty->print("ZZZ fixing new phi: %d", j); m->dump(); });
2991       }
2992     }
2993   }
2994   uint last = phase->C->unique();
2995   MergeMemNode* mm = NULL;
2996   int alias = Compile::AliasIdxRaw;
2997   DEBUG_ONLY(if (trace) { tty->print("ZZZ raw mem is"); raw_mem->dump(); });
2998   for (DUIterator i = raw_mem->outs(); raw_mem->has_out(i); i++) {
2999     Node* u = raw_mem->out(i);
3000     if (u->_idx < last) {
3001       if (u->is_Mem()) {
3002         if (phase->C->get_alias_index(u->adr_type()) == alias) {
3003           Node* m = find_raw_mem(phase->get_ctrl(u), u, memory_nodes, phase);
3004           if (m != raw_mem) {
3005             DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
3006             phase->igvn().replace_input_of(u, MemNode::Memory, m);
3007             --i;
3008           }
3009         }
3010       } else if (u->is_MergeMem()) {
3011         MergeMemNode* u_mm = u->as_MergeMem();
3012         if (u_mm->memory_at(alias) == raw_mem) {
3013           MergeMemNode* newmm = NULL;
3014           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
3015             Node* uu = u->fast_out(j);
3016             assert(!uu->is_MergeMem(), "chain of MergeMems?");
3017             if (uu->is_Phi()) {
3018               assert(uu->adr_type() == TypePtr::BOTTOM, "");
3019               Node* region = uu->in(0);
3020               int nb = 0;
3021               for (uint k = 1; k < uu->req(); k++) {
3022                 if (uu->in(k) == u) {
3023                   Node* m = find_raw_mem(region->in(k), NULL, memory_nodes, phase);
3024                   if (m != raw_mem) {
3025                     DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of phi %d", k); uu->dump(); });
3026                     if (newmm == NULL || 1) {
3027                       newmm = clone_merge_mem(u, raw_mem, alias, m, phase->ctrl_or_self(m), i, phase);
3028                     }
3029                     if (newmm != u) {
3030                       phase->igvn().replace_input_of(uu, k, newmm);
3031                       nb++;
3032                       --jmax;
3033                     }
3034                   }
3035                 }
3036               }
3037               if (nb > 0) {
3038                 --j;
3039               }
3040             } else {
3041               Node* m = find_raw_mem(phase->ctrl_or_self(uu), uu, memory_nodes, phase);
3042               if (m != raw_mem) {
3043                 DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); uu->dump(); });
3044                 if (newmm == NULL || 1) {
3045                   newmm = clone_merge_mem(u, raw_mem, alias, m, phase->ctrl_or_self(m), i, phase);
3046                 }
3047                 if (newmm != u) {
3048                   phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
3049                   --j, --jmax;
3050                 }
3051               }
3052             }
3053           }
3054         }
3055       } else if (u->is_Phi()) {
3056         assert(u->bottom_type() == Type::MEMORY, "what else?");
3057         if (u->adr_type() == TypeRawPtr::BOTTOM || u->adr_type() == TypePtr::BOTTOM) {
3058           Node* region = u->in(0);
3059           bool replaced = false;
3060           for (uint j = 1; j < u->req(); j++) {
3061             if (u->in(j) == raw_mem) {
3062               Node* m = find_raw_mem(region->in(j), NULL, memory_nodes, phase);
3063               Node* nnew = m;
3064               if (m != raw_mem) {
3065                 if (u->adr_type() == TypePtr::BOTTOM) {
3066                   if (mm == NULL || 1) {
3067                     mm = allocate_merge_mem(raw_mem, alias, m, phase->ctrl_or_self(m), phase);
3068                   }
3069                   nnew = mm;
3070                 }
3071                 DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of phi %d", j); u->dump(); });
3072                 phase->igvn().replace_input_of(u, j, nnew);
3073                 replaced = true;
3074               }
3075             }
3076           }
3077           if (replaced) {
3078             --i;
3079           }
3080         }
3081       } else if (u->adr_type() == TypePtr::BOTTOM || u->adr_type() == NULL) {
3082         assert(u->adr_type() != NULL ||
3083                u->Opcode() == Op_Rethrow ||
3084                u->Opcode() == Op_Return ||
3085                u->Opcode() == Op_SafePoint ||
3086                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
3087                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
3088                u->Opcode() == Op_CallLeaf, "");
3089         Node* m = find_raw_mem(phase->ctrl_or_self(u), u, memory_nodes, phase);
3090         if (m != raw_mem) {
3091           if (mm == NULL || 1) {
3092             mm = allocate_merge_mem(raw_mem, alias, m, phase->get_ctrl(m), phase);
3093           }
3094           phase->igvn().replace_input_of(u, u->find_edge(raw_mem), mm);
3095           --i;
3096         }
3097       } else if (phase->C->get_alias_index(u->adr_type()) == alias) {
3098         Node* m = find_raw_mem(phase->ctrl_or_self(u), u, memory_nodes, phase);
3099         if (m != raw_mem) {
3100           DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
3101           phase->igvn().replace_input_of(u, u->find_edge(raw_mem), m);
3102           --i;
3103         }
3104       }
3105     }
3106   }
3107 #ifdef ASSERT
3108   assert(raw_mem_phi->outcnt() > 0, "");
3109   for (int i = 0; i < phis.length(); i++) {
3110     Node* n = phis.at(i);
3111     assert(n->outcnt() > 0, "new phi must have uses now");
3112   }
3113 #endif
3114 }
3115 
3116 bool ShenandoahBarrierNode::is_evacuation_in_progress_test(Node* iff) {
3117   if (!UseShenandoahGC) {
3118     return false;
3119   }
3120 
3121   assert(iff->is_If(), "bad input");
3122   if (iff->Opcode() != Op_If) {
3123     return false;
3124   }
3125   Node* bol = iff->in(1);
3126   if (!bol->is_Bool() || bol->as_Bool()->_test._test != BoolTest::ne) {
3127     return false;
3128   }
3129   Node* cmp = bol->in(1);
3130   if (cmp->Opcode() != Op_CmpI) {
3131     return false;
3132   }
3133   Node* in1 = cmp->in(1);
3134   Node* in2 = cmp->in(2);
3135   if (in2->find_int_con(-1) != 0) {
3136     return false;
3137   }
3138   if (in1->Opcode() != Op_AndI) {
3139     return false;
3140   }
3141   in2 = in1->in(2);
3142   if (in2->find_int_con(-1) != ShenandoahHeap::EVACUATION) {
3143     return false;
3144   }
3145   in1 = in1->in(1);
3146 
3147   return is_gc_state_load(in1);
3148 }
3149 
3150 bool ShenandoahBarrierNode::is_gc_state_load(Node *n) {
3151   if (!UseShenandoahGC) {
3152     return false;
3153   }
3154 
3155   if (n->Opcode() != Op_LoadB) {
3156     return false;
3157   }
3158   Node* addp = n->in(MemNode::Address);
3159   if (!addp->is_AddP()) {
3160     return false;
3161   }
3162   Node* base = addp->in(AddPNode::Address);
3163   Node* off = addp->in(AddPNode::Offset);
3164   if (base->Opcode() != Op_ThreadLocal) {
3165     return false;
3166   }
3167   if (off->find_intptr_t_con(-1) != in_bytes(JavaThread::gc_state_offset())) {
3168     return false;
3169   }
3170   return true;
3171 }
3172 
3173 
3174 void PhaseIdealLoop::shenandoah_test_evacuation_in_progress(Node* ctrl, int alias, Node*& raw_mem, Node*& wb_mem,
3175                                                             IfNode*& evacuation_iff, Node*& evac_in_progress,
3176                                                             Node*& evac_not_in_progress) {
3177   IdealLoopTree *loop = get_loop(ctrl);
3178   Node* thread = new (C) ThreadLocalNode();
3179   register_new_node(thread, ctrl);
3180   Node* offset = _igvn.MakeConX(in_bytes(JavaThread::gc_state_offset()));
3181   set_ctrl(offset, C->root());
3182   Node* gc_state_addr = new (C) AddPNode(C->top(), thread, offset);
3183   register_new_node(gc_state_addr, ctrl);
3184   uint gc_state_idx = Compile::AliasIdxRaw;
3185   const TypePtr* gc_state_adr_type = NULL; // debug-mode-only argument
3186   debug_only(gc_state_adr_type = C->get_adr_type(gc_state_idx));
3187 
3188   Node* gc_state = new (C) LoadBNode(ctrl, raw_mem, gc_state_addr, gc_state_adr_type, TypeInt::BYTE, MemNode::unordered);
3189   register_new_node(gc_state, ctrl);
3190 
3191   Node* evacuation_in_progress = new (C) AndINode(gc_state, _igvn.intcon(ShenandoahHeap::EVACUATION));
3192   register_new_node(evacuation_in_progress, ctrl);
3193   Node* evacuation_in_progress_cmp = new (C) CmpINode(evacuation_in_progress, _igvn.zerocon(T_INT));
3194   register_new_node(evacuation_in_progress_cmp, ctrl);
3195   Node* evacuation_in_progress_test = new (C) BoolNode(evacuation_in_progress_cmp, BoolTest::ne);
3196   register_new_node(evacuation_in_progress_test, ctrl);
3197   evacuation_iff = new (C) IfNode(ctrl, evacuation_in_progress_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
3198   register_control(evacuation_iff, loop, ctrl);
3199 
3200   assert(ShenandoahBarrierNode::is_evacuation_in_progress_test(evacuation_iff), "Should match the shape");
3201   assert(ShenandoahBarrierNode::is_gc_state_load(gc_state), "Should match the shape");
3202 
3203   evac_not_in_progress = new (C) IfFalseNode(evacuation_iff);
3204   register_control(evac_not_in_progress, loop, evacuation_iff);
3205   evac_in_progress = new (C) IfTrueNode(evacuation_iff);
3206   register_control(evac_in_progress, loop, evacuation_iff);
3207 }
3208 
3209 void PhaseIdealLoop::shenandoah_evacuation_not_in_progress_null_check(Node*& c, Node*& val, Node* unc_ctrl, Node*& unc_region) {
3210   if (unc_ctrl != NULL) {
3211     // Clone the null check in this branch to allow implicit null check
3212     IdealLoopTree *loop = get_loop(c);
3213     Node* iff = unc_ctrl->in(0);
3214     assert(iff->is_If(), "broken");
3215     Node* new_iff = iff->clone();
3216     new_iff->set_req(0, c);
3217     register_control(new_iff, loop, c);
3218     Node* iffalse = new (C) IfFalseNode(new_iff->as_If());
3219     register_control(iffalse, loop, new_iff);
3220     Node* iftrue = new (C) IfTrueNode(new_iff->as_If());
3221     register_control(iftrue, loop, new_iff);
3222     c = iftrue;
3223     unc_region = new (C) RegionNode(3);
3224     unc_region->init_req(1, iffalse);
3225     const Type *t = _igvn.type(val);
3226     assert(val->Opcode() == Op_CastPP, "expect cast to non null here");
3227     Node* uncasted_val = val->in(1);
3228     val = new (C) CastPPNode(uncasted_val, t);
3229     val->init_req(0, c);
3230     register_new_node(val, c);
3231   }
3232 }
3233 
3234 void PhaseIdealLoop::shenandoah_evacuation_not_in_progress(Node* c, Node* val, Node* unc_ctrl, Node* raw_mem, Node* wb_mem, Node* region,
3235                                                            Node* val_phi, Node* mem_phi, Node* raw_mem_phi, Node*& unc_region) {
3236   shenandoah_evacuation_not_in_progress_null_check(c, val, unc_ctrl, unc_region);
3237   region->init_req(1, c);
3238   Node *rbfalse = new(C) ShenandoahReadBarrierNode(c, wb_mem, val);
3239   register_new_node(rbfalse, c);
3240   val_phi->init_req(1, rbfalse);
3241   mem_phi->init_req(1, wb_mem);
3242   raw_mem_phi->init_req(1, raw_mem);
3243 }
3244 
3245 void PhaseIdealLoop::shenandoah_evacuation_in_progress_null_check(Node*& c, Node*& val, Node* evacuation_iff, Node* unc, Node* unc_ctrl,
3246                                                                   Node* unc_region, Unique_Node_List& uses) {
3247   if (unc != NULL) {
3248     // Clone the null check in this branch to allow implicit null check
3249     IdealLoopTree *loop = get_loop(c);
3250     Node* iff = unc_ctrl->in(0);
3251     assert(iff->is_If(), "broken");
3252     Node* new_iff = iff->clone();
3253     new_iff->set_req(0, c);
3254     register_control(new_iff, loop, c);
3255     Node* iffalse = new (C) IfFalseNode(new_iff->as_If());
3256     register_control(iffalse, loop, new_iff);
3257     Node* iftrue = new (C) IfTrueNode(new_iff->as_If());
3258     register_control(iftrue, loop, new_iff);
3259     c = iftrue;
3260     unc_region->init_req(2, iffalse);
3261 
3262     Node* proj = iff->as_If()->proj_out(0);
3263     assert(proj != unc_ctrl, "bad projection");
3264     Node* use = proj->unique_ctrl_out();
3265 
3266     assert(use == unc || use->is_Region(), "what else?");
3267 
3268     uses.clear();
3269     if (use == unc) {
3270       set_idom(use, unc_region, dom_depth(unc_region)+1);
3271       for (uint i = 1; i < unc->req(); i++) {
3272         Node* n = unc->in(i);
3273         if (has_ctrl(n) && get_ctrl(n) == proj) {
3274           uses.push(n);
3275         }
3276       }
3277     } else {
3278       assert(use->is_Region(), "what else?");
3279       uint idx = 1;
3280       for (; use->in(idx) != proj; idx++);
3281       for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3282         Node* u = use->fast_out(i);
3283         if (u->is_Phi() && get_ctrl(u->in(idx)) == proj) {
3284           uses.push(u->in(idx));
3285         }
3286       }
3287     }
3288     for(uint next = 0; next < uses.size(); next++ ) {
3289       Node *n = uses.at(next);
3290       assert(get_ctrl(n) == proj, "bad control");
3291       set_ctrl_and_loop(n, unc_region);
3292       if (n->in(0) == proj) {
3293         _igvn.replace_input_of(n, 0, unc_region);
3294       }
3295       for (uint i = 0; i < n->req(); i++) {
3296         Node* m = n->in(i);
3297         if (m != NULL && has_ctrl(m) && get_ctrl(m) == proj) {
3298           uses.push(m);
3299         }
3300       }
3301     }
3302 
3303     _igvn.rehash_node_delayed(use);
3304     int nb = use->replace_edge(proj, unc_region);
3305     assert(nb == 1, "only use expected");
3306     register_control(unc_region, _ltree_root, evacuation_iff);
3307 
3308     _igvn.replace_input_of(iff, 1, _igvn.intcon(1));
3309     const Type *t = _igvn.type(val);
3310     assert(val->Opcode() == Op_CastPP, "expect cast to non null here");
3311     Node* uncasted_val = val->in(1);
3312     val = new (C) CastPPNode(uncasted_val, t);
3313     val->init_req(0, c);
3314     register_new_node(val, c);
3315   }
3316 }
3317 
3318 void PhaseIdealLoop::shenandoah_in_cset_fast_test(Node*& c, Node* rbtrue, Node* raw_mem, Node* wb_mem, Node* region, Node* val_phi, Node* mem_phi,
3319                                                   Node* raw_mem_phi) {
3320   IdealLoopTree *loop = get_loop(c);
3321   Node* raw_rbtrue = new (C) CastP2XNode(c, rbtrue);
3322   register_new_node(raw_rbtrue, c);
3323   Node* cset_offset = new (C) URShiftXNode(raw_rbtrue, _igvn.intcon(ShenandoahHeapRegion::region_size_bytes_shift_jint()));
3324   register_new_node(cset_offset, c);
3325   Node* in_cset_fast_test_base_addr = _igvn.makecon(TypeRawPtr::make(ShenandoahHeap::in_cset_fast_test_addr()));
3326   set_ctrl(in_cset_fast_test_base_addr, C->root());
3327   Node* in_cset_fast_test_adr = new (C) AddPNode(C->top(), in_cset_fast_test_base_addr, cset_offset);
3328   register_new_node(in_cset_fast_test_adr, c);
3329   uint in_cset_fast_test_idx = Compile::AliasIdxRaw;
3330   const TypePtr* in_cset_fast_test_adr_type = NULL; // debug-mode-only argument
3331   debug_only(in_cset_fast_test_adr_type = C->get_adr_type(in_cset_fast_test_idx));
3332   Node* in_cset_fast_test_load = new (C) LoadBNode(c, raw_mem, in_cset_fast_test_adr, in_cset_fast_test_adr_type, TypeInt::BOOL, MemNode::unordered);
3333   register_new_node(in_cset_fast_test_load, c);
3334   Node* in_cset_fast_test_cmp = new (C) CmpINode(in_cset_fast_test_load, _igvn.zerocon(T_INT));
3335   register_new_node(in_cset_fast_test_cmp, c);
3336   Node* in_cset_fast_test_test = new (C) BoolNode(in_cset_fast_test_cmp, BoolTest::ne);
3337   register_new_node(in_cset_fast_test_test, c);
3338   IfNode* in_cset_fast_test_iff = new (C) IfNode(c, in_cset_fast_test_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
3339   register_control(in_cset_fast_test_iff, loop, c);
3340 
3341   Node* in_cset_fast_test_success = new (C) IfFalseNode(in_cset_fast_test_iff);
3342   register_control(in_cset_fast_test_success, loop, in_cset_fast_test_iff);
3343 
3344   region->init_req(3, in_cset_fast_test_success);
3345   val_phi->init_req(3, rbtrue);
3346   mem_phi->init_req(3, wb_mem);
3347   raw_mem_phi->init_req(3, raw_mem);
3348 
3349   Node* in_cset_fast_test_failure = new (C) IfTrueNode(in_cset_fast_test_iff);
3350   register_control(in_cset_fast_test_failure, loop, in_cset_fast_test_iff);
3351 
3352   c = in_cset_fast_test_failure;
3353 }
3354 
3355 void PhaseIdealLoop::shenandoah_evacuation_in_progress(Node* c, Node* val, Node* evacuation_iff, Node* unc, Node* unc_ctrl,
3356                                                        Node* raw_mem, Node* wb_mem, Node* region, Node* val_phi, Node* mem_phi,
3357                                                        Node* raw_mem_phi, Node* unc_region, int alias, Unique_Node_List& uses) {
3358   shenandoah_evacuation_in_progress_null_check(c, val, evacuation_iff, unc, unc_ctrl, unc_region, uses);
3359 
3360   IdealLoopTree *loop = get_loop(c);
3361 
3362   Node* rbtrue = new (C) ShenandoahReadBarrierNode(c, wb_mem, val);
3363   register_new_node(rbtrue, c);
3364 
3365   Node* in_cset_fast_test_failure = NULL;
3366   shenandoah_in_cset_fast_test(c, rbtrue, raw_mem, wb_mem, region, val_phi, mem_phi, raw_mem_phi);
3367 
3368   // The slow path stub consumes and produces raw memory in addition
3369   // to the existing memory edges
3370   Node* base = shenandoah_find_bottom_mem(c);
3371 
3372   MergeMemNode* mm = MergeMemNode::make(C, base);
3373   mm->set_memory_at(alias, wb_mem);
3374   mm->set_memory_at(Compile::AliasIdxRaw, raw_mem);
3375   register_new_node(mm, c);
3376 
3377   Node* call = new (C) CallLeafNoFPNode(OptoRuntime::shenandoah_write_barrier_Type(), StubRoutines::shenandoah_wb_C(), "shenandoah_write_barrier", TypeRawPtr::BOTTOM);
3378   call->init_req(TypeFunc::Control, c);
3379   call->init_req(TypeFunc::I_O, C->top());
3380   call->init_req(TypeFunc::Memory, mm);
3381   call->init_req(TypeFunc::FramePtr, C->top());
3382   call->init_req(TypeFunc::ReturnAdr, C->top());
3383   call->init_req(TypeFunc::Parms, rbtrue);
3384   register_control(call, loop, c);
3385   Node* ctrl_proj = new (C) ProjNode(call, TypeFunc::Control);
3386   register_control(ctrl_proj, loop, call);
3387   Node* mem_proj = new (C) ProjNode(call, TypeFunc::Memory);
3388   register_new_node(mem_proj, call);
3389   Node* res_proj = new (C) ProjNode(call, TypeFunc::Parms);
3390   register_new_node(res_proj, call);
3391   Node* res = new (C) CheckCastPPNode(ctrl_proj, res_proj, _igvn.type(val)->is_oopptr()->cast_to_nonconst());
3392   register_new_node(res, ctrl_proj);
3393   region->init_req(2, ctrl_proj);
3394   val_phi->init_req(2, res);
3395   mem_phi->init_req(2, mem_proj);
3396   raw_mem_phi->init_req(2, mem_proj);
3397   register_control(region, loop, evacuation_iff);
3398 
3399 }
3400 
3401 void PhaseIdealLoop::shenandoah_pin_and_expand_barriers() {
3402   const bool trace = false;
3403 
3404   // Collect raw memory state at CFG points in the entire graph and
3405   // record it in memory_nodes. Optimize the raw memory graph in the
3406   // process. Optimizing the memory graph also makes the memory graph
3407   // simpler.
3408   Node_List memory_nodes;
3409   ShenandoahWriteBarrierNode::collect_memory_nodes(Compile::AliasIdxRaw, memory_nodes, this);
3410 
3411   // Let's try to common write barriers again
3412   for (int i = C->shenandoah_barriers_count(); i > 0; i--) {
3413     ShenandoahBarrierNode* wb = C->shenandoah_barrier(i-1);
3414     Node* ctrl = get_ctrl(wb);
3415     try_common_shenandoah_barriers(wb, ctrl);
3416   }
3417 
3418   for (int i = 0; i < C->shenandoah_barriers_count(); i++) {
3419     ShenandoahBarrierNode* wb = C->shenandoah_barrier(i);
3420     Node* ctrl = get_ctrl(wb);
3421 
3422     Node* val = wb->in(ShenandoahBarrierNode::ValueIn);
3423     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
3424       assert(ShenandoahBarrierNode::is_dominator(get_ctrl(val), ctrl->in(0)->in(0), val, ctrl->in(0), this), "can't move");
3425       set_ctrl(wb, ctrl->in(0)->in(0));
3426     } else if (ctrl->is_CallRuntime()) {
3427       assert(ShenandoahBarrierNode::is_dominator(get_ctrl(val), ctrl->in(0), val, ctrl, this), "can't move");
3428       set_ctrl(wb, ctrl->in(0));
3429     }
3430 
3431     assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "only for write barriers");
3432     // Look for a null check that dominates this barrier and move the
3433     // barrier right after the null check to enable implicit null
3434     // checks
3435     shenandoah_pin_and_expand_barriers_move_barrier(wb);
3436 
3437     ctrl = get_ctrl(wb);
3438   }
3439 
3440   Unique_Node_List uses;
3441   Unique_Node_List uses_to_ignore;
3442   for (int i = C->shenandoah_barriers_count(); i > 0; i--) {
3443     int cnt = C->shenandoah_barriers_count();
3444     ShenandoahBarrierNode* wb = C->shenandoah_barrier(i-1);
3445     assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "only for write barriers");
3446 
3447     uint last = C->unique();
3448     Node* ctrl = get_ctrl(wb);
3449 
3450     Node* raw_mem = ShenandoahWriteBarrierNode::find_raw_mem(ctrl, wb, memory_nodes, this);
3451     Node* init_raw_mem = raw_mem;
3452     Node* raw_mem_for_ctrl = ShenandoahWriteBarrierNode::find_raw_mem(ctrl, NULL, memory_nodes, this);
3453     int alias = C->get_alias_index(wb->adr_type());
3454     Node* wb_mem =  wb->in(ShenandoahBarrierNode::Memory);
3455 
3456     Node* val = wb->in(ShenandoahBarrierNode::ValueIn);
3457     Node* wbproj = wb->find_out_with(Op_ShenandoahWBMemProj);
3458     IdealLoopTree *loop = get_loop(ctrl);
3459 
3460     assert(val->Opcode() != Op_ShenandoahWriteBarrier || C->has_irreducible_loop(), "No chain of write barriers");
3461 
3462     CallStaticJavaNode* unc = shenandoah_pin_and_expand_barriers_null_check(wb);
3463     Node* unc_ctrl = NULL;
3464     if (unc != NULL) {
3465       if (val->in(0) != ctrl) {
3466         unc = NULL;
3467       } else {
3468         unc_ctrl = val->in(0);
3469       }
3470     }
3471 
3472     Node* uncasted_val = val;
3473     if (unc != NULL) {
3474       uncasted_val = val->in(1);
3475     }
3476 
3477     Node* evac_in_progress = NULL;
3478     Node* evac_not_in_progress = NULL;
3479     IfNode* evacuation_iff = NULL;
3480     shenandoah_test_evacuation_in_progress(ctrl, alias, raw_mem, wb_mem, evacuation_iff, evac_in_progress, evac_not_in_progress);
3481 
3482     Node* region = new (C) RegionNode(4);
3483     Node* val_phi = new (C) PhiNode(region, val->bottom_type()->is_oopptr()->cast_to_nonconst());
3484     Node* mem_phi = PhiNode::make(region, wb_mem, Type::MEMORY, C->alias_type(wb->adr_type())->adr_type());
3485     Node* raw_mem_phi = PhiNode::make(region, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
3486 
3487     Node* unc_region = NULL;
3488     shenandoah_evacuation_not_in_progress(evac_not_in_progress, val, unc_ctrl, raw_mem, wb_mem,
3489                                           region, val_phi, mem_phi, raw_mem_phi, unc_region);
3490 
3491     shenandoah_evacuation_in_progress(evac_in_progress, val, evacuation_iff, unc, unc_ctrl,
3492                                       raw_mem, wb_mem, region, val_phi, mem_phi, raw_mem_phi,
3493                                       unc_region, alias, uses);
3494     Node* out_val = val_phi;
3495     register_new_node(val_phi, region);
3496     register_new_node(mem_phi, region);
3497     register_new_node(raw_mem_phi, region);
3498 
3499     // Update the control of all nodes that should be after the
3500     // barrier control flow
3501     uses.clear();
3502     // Every node that is control dependent on the barrier's input
3503     // control will be after the expanded barrier. The raw memory (if
3504     // its memory is control dependent on the barrier's input control)
3505     // must stay above the barrier.
3506     uses_to_ignore.clear();
3507     if (has_ctrl(init_raw_mem) && get_ctrl(init_raw_mem) == ctrl && !init_raw_mem->is_Phi()) {
3508       uses_to_ignore.push(init_raw_mem);
3509     }
3510     for (uint next = 0; next < uses_to_ignore.size(); next++) {
3511       Node *n = uses_to_ignore.at(next);
3512       for (uint i = 0; i < n->req(); i++) {
3513         Node* in = n->in(i);
3514         if (in != NULL && has_ctrl(in) && get_ctrl(in) == ctrl) {
3515           uses_to_ignore.push(in);
3516         }
3517       }
3518     }
3519     for (DUIterator_Fast imax, i = ctrl->fast_outs(imax); i < imax; i++) {
3520       Node* u = ctrl->fast_out(i);
3521       if (u->_idx < last &&
3522           u != wb &&
3523           !uses_to_ignore.member(u) &&
3524           (u->in(0) != ctrl || (!u->is_Region() && !u->is_Phi())) &&
3525           (ctrl->Opcode() != Op_CatchProj || u->Opcode() != Op_CreateEx)) {
3526         Node* old_c = ctrl_or_self(u);
3527         Node* c = old_c;
3528         if (c != ctrl ||
3529             ShenandoahBarrierNode::is_dominator_same_ctrl(old_c, wb, u, this) ||
3530             u->is_shenandoah_state_load()) {
3531           _igvn.rehash_node_delayed(u);
3532           int nb = u->replace_edge(ctrl, region);
3533           if (u->is_CFG()) {
3534             if (idom(u) == ctrl) {
3535               set_idom(u, region, dom_depth(region));
3536             }
3537           } else if (get_ctrl(u) == ctrl) {
3538             assert(u != init_raw_mem, "should leave input raw mem above the barrier");
3539             uses.push(u);
3540           }
3541           assert(nb == 1, "more than 1 ctrl input?");
3542           --i, imax -= nb;
3543         }
3544       }
3545     }
3546 
3547     if (wbproj != NULL) {
3548       _igvn.replace_input_of(wbproj, 0, C->top());
3549       lazy_replace(wbproj, mem_phi);
3550     }
3551     if (unc != NULL) {
3552       for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
3553         Node* u = val->fast_out(i);
3554         Node* c = ctrl_or_self(u);
3555         if (u != wb && (c != ctrl || ShenandoahBarrierNode::is_dominator_same_ctrl(c, wb, u, this))) {
3556           _igvn.rehash_node_delayed(u);
3557           int nb = u->replace_edge(val, out_val);
3558           --i, imax -= nb;
3559         }
3560       }
3561       if (val->outcnt() == 0) {
3562         lazy_update(val, out_val);
3563         _igvn._worklist.push(val);
3564       }
3565     }
3566     lazy_replace(wb, out_val);
3567 
3568     shenandoah_follow_barrier_uses(mem_phi, ctrl, uses);
3569     shenandoah_follow_barrier_uses(out_val, ctrl, uses);
3570 
3571     for(uint next = 0; next < uses.size(); next++ ) {
3572       Node *n = uses.at(next);
3573       assert(get_ctrl(n) == ctrl, "bad control");
3574       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
3575       set_ctrl(n, region);
3576       shenandoah_follow_barrier_uses(n, ctrl, uses);
3577     }
3578 
3579     recompute_dom_depth();
3580 
3581     // The slow path call produces memory: hook the raw memory phi
3582     // from the expanded write barrier with the rest of the graph
3583     // which may require adding memory phis at every post dominated
3584     // region and at enclosing loop heads. Use the memory state
3585     // collected in memory_nodes to fix the memory graph. Update that
3586     // memory state as we go.
3587     ShenandoahWriteBarrierNode::fix_raw_mem(ctrl, region, init_raw_mem, raw_mem_for_ctrl, raw_mem_phi, memory_nodes, uses, this);
3588     assert(C->shenandoah_barriers_count() == cnt - 1, "not replaced");
3589   }
3590 
3591   assert(C->shenandoah_barriers_count() == 0, "all write barrier nodes should have been replaced");
3592 }
3593 
3594 #ifdef ASSERT
3595 void ShenandoahBarrierNode::verify_raw_mem(RootNode* root) {
3596   const bool trace = false;
3597   ResourceMark rm;
3598   Unique_Node_List nodes;
3599   Unique_Node_List controls;
3600   Unique_Node_List memories;
3601 
3602   nodes.push(root);
3603   for (uint next = 0; next < nodes.size(); next++) {
3604     Node *n  = nodes.at(next);
3605     if (n->Opcode() == Op_CallLeafNoFP && n->as_Call()->_entry_point == StubRoutines::shenandoah_wb_C()) {
3606       controls.push(n);
3607       if (trace) { tty->print("XXXXXX verifying"); n->dump(); }
3608       for (uint next2 = 0; next2 < controls.size(); next2++) {
3609         Node *m = controls.at(next2);
3610         if (!m->is_Loop() || controls.member(m->in(LoopNode::EntryControl)) || 1) {
3611           for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
3612             Node* u = m->fast_out(i);
3613             if (u->is_CFG() && !u->is_Root() &&
3614                 !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1)) {
3615               if (trace) { tty->print("XXXXXX pushing control"); u->dump(); }
3616               controls.push(u);
3617             }
3618           }
3619         }
3620       }
3621       memories.push(n->as_Call()->proj_out(TypeFunc::Memory));
3622       for (uint next2 = 0; next2 < memories.size(); next2++) {
3623         Node *m = memories.at(next2);
3624         assert(m->bottom_type() == Type::MEMORY, "");
3625         if (!m->is_Phi() || !m->in(0)->is_Loop() || controls.member(m->in(0)->in(LoopNode::EntryControl)) || 1) {
3626           for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
3627             Node* u = m->fast_out(i);
3628             if (u->bottom_type() == Type::MEMORY && (u->is_Mem() || u->is_ClearArray())) {
3629               if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
3630               memories.push(u);
3631             } else if (u->is_LoadStore()) {
3632               if (trace) { tty->print("XXXXXX pushing memory"); u->find_out_with(Op_SCMemProj)->dump(); }
3633               memories.push(u->find_out_with(Op_SCMemProj));
3634             } else if (u->is_MergeMem() && u->as_MergeMem()->memory_at(Compile::AliasIdxRaw) == m) {
3635               if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
3636               memories.push(u);
3637             } else if (u->is_Phi()) {
3638               assert(u->bottom_type() == Type::MEMORY, "");
3639               if (u->adr_type() == TypeRawPtr::BOTTOM || u->adr_type() == TypePtr::BOTTOM) {
3640                 assert(controls.member(u->in(0)), "");
3641                 if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
3642                 memories.push(u);
3643               }
3644             } else if (u->is_SafePoint() || u->is_MemBar()) {
3645               for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
3646                 Node* uu = u->fast_out(j);
3647                 if (uu->bottom_type() == Type::MEMORY) {
3648                   if (trace) { tty->print("XXXXXX pushing memory"); uu->dump(); }
3649                   memories.push(uu);
3650                 }
3651               }
3652             }
3653           }
3654         }
3655       }
3656       for (uint next2 = 0; next2 < controls.size(); next2++) {
3657         Node *m = controls.at(next2);
3658         if (m->is_Region()) {
3659           bool all_in = true;
3660           for (uint i = 1; i < m->req(); i++) {
3661             if (!controls.member(m->in(i))) {
3662               all_in = false;
3663               break;
3664             }
3665           }
3666           if (trace) { tty->print("XXX verifying %s", all_in ? "all in" : ""); m->dump(); }
3667           bool found_phi = false;
3668           for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax && !found_phi; j++) {
3669             Node* u = m->fast_out(j);
3670             if (u->is_Phi() && memories.member(u)) {
3671               found_phi = true;
3672               for (uint i = 1; i < u->req() && found_phi; i++) {
3673                 Node* k = u->in(i);
3674                 if (memories.member(k) != controls.member(m->in(i))) {
3675                   found_phi = false;
3676                 }
3677               }
3678             }
3679           }
3680           assert(found_phi || all_in, "");
3681         }
3682       }
3683       controls.clear();
3684       memories.clear();
3685     }
3686     for( uint i = 0; i < n->len(); ++i ) {
3687       Node *m = n->in(i);
3688       if (m != NULL) {
3689         nodes.push(m);
3690       }
3691     }
3692   }
3693 }
3694 #endif