1 /*
   2  * Copyright (c) 2015, 2019, Red Hat, Inc. All rights reserved.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  *
  22  */
  23 
  24 #include "precompiled.hpp"
  25 
  26 #include "gc/shenandoah/c2/shenandoahSupport.hpp"
  27 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
  28 #include "gc/shenandoah/shenandoahBarrierSetAssembler.hpp"
  29 #include "gc/shenandoah/shenandoahForwarding.hpp"
  30 #include "gc/shenandoah/shenandoahHeap.hpp"
  31 #include "gc/shenandoah/shenandoahHeapRegion.hpp"
  32 #include "gc/shenandoah/shenandoahRuntime.hpp"
  33 #include "gc/shenandoah/shenandoahThreadLocalData.hpp"
  34 #include "opto/arraycopynode.hpp"
  35 #include "opto/block.hpp"
  36 #include "opto/callnode.hpp"
  37 #include "opto/castnode.hpp"
  38 #include "opto/movenode.hpp"
  39 #include "opto/phaseX.hpp"
  40 #include "opto/rootnode.hpp"
  41 #include "opto/runtime.hpp"
  42 #include "opto/subnode.hpp"
  43 
  44 bool ShenandoahBarrierC2Support::expand(Compile* C, PhaseIterGVN& igvn) {
  45   ShenandoahBarrierSetC2State* state = ShenandoahBarrierSetC2::bsc2()->state();
  46   if ((state->enqueue_barriers_count() +
  47        state->load_reference_barriers_count()) > 0) {
  48     bool attempt_more_loopopts = ShenandoahLoopOptsAfterExpansion;
  49     C->clear_major_progress();
  50     PhaseIdealLoop ideal_loop(igvn, LoopOptsShenandoahExpand);
  51     if (C->failing()) return false;
  52     PhaseIdealLoop::verify(igvn);
  53     DEBUG_ONLY(verify_raw_mem(C->root());)
  54     if (attempt_more_loopopts) {
  55       C->set_major_progress();
  56       if (!C->optimize_loops(igvn, LoopOptsShenandoahPostExpand)) {
  57         return false;
  58       }
  59       C->clear_major_progress();
  60     }
  61   }
  62   return true;
  63 }
  64 
  65 bool ShenandoahBarrierC2Support::is_heap_state_test(Node* iff, int mask) {
  66   if (!UseShenandoahGC) {
  67     return false;
  68   }
  69   assert(iff->is_If(), "bad input");
  70   if (iff->Opcode() != Op_If) {
  71     return false;
  72   }
  73   Node* bol = iff->in(1);
  74   if (!bol->is_Bool() || bol->as_Bool()->_test._test != BoolTest::ne) {
  75     return false;
  76   }
  77   Node* cmp = bol->in(1);
  78   if (cmp->Opcode() != Op_CmpI) {
  79     return false;
  80   }
  81   Node* in1 = cmp->in(1);
  82   Node* in2 = cmp->in(2);
  83   if (in2->find_int_con(-1) != 0) {
  84     return false;
  85   }
  86   if (in1->Opcode() != Op_AndI) {
  87     return false;
  88   }
  89   in2 = in1->in(2);
  90   if (in2->find_int_con(-1) != mask) {
  91     return false;
  92   }
  93   in1 = in1->in(1);
  94 
  95   return is_gc_state_load(in1);
  96 }
  97 
  98 bool ShenandoahBarrierC2Support::is_heap_stable_test(Node* iff) {
  99   return is_heap_state_test(iff, ShenandoahHeap::HAS_FORWARDED);
 100 }
 101 
 102 bool ShenandoahBarrierC2Support::is_gc_state_load(Node *n) {
 103   if (!UseShenandoahGC) {
 104     return false;
 105   }
 106   if (n->Opcode() != Op_LoadB && n->Opcode() != Op_LoadUB) {
 107     return false;
 108   }
 109   Node* addp = n->in(MemNode::Address);
 110   if (!addp->is_AddP()) {
 111     return false;
 112   }
 113   Node* base = addp->in(AddPNode::Address);
 114   Node* off = addp->in(AddPNode::Offset);
 115   if (base->Opcode() != Op_ThreadLocal) {
 116     return false;
 117   }
 118   if (off->find_intptr_t_con(-1) != in_bytes(ShenandoahThreadLocalData::gc_state_offset())) {
 119     return false;
 120   }
 121   return true;
 122 }
 123 
 124 bool ShenandoahBarrierC2Support::has_safepoint_between(Node* start, Node* stop, PhaseIdealLoop *phase) {
 125   assert(phase->is_dominator(stop, start), "bad inputs");
 126   ResourceMark rm;
 127   Unique_Node_List wq;
 128   wq.push(start);
 129   for (uint next = 0; next < wq.size(); next++) {
 130     Node *m = wq.at(next);
 131     if (m == stop) {
 132       continue;
 133     }
 134     if (m->is_SafePoint() && !m->is_CallLeaf()) {
 135       return true;
 136     }
 137     if (m->is_Region()) {
 138       for (uint i = 1; i < m->req(); i++) {
 139         wq.push(m->in(i));
 140       }
 141     } else {
 142       wq.push(m->in(0));
 143     }
 144   }
 145   return false;
 146 }
 147 
 148 bool ShenandoahBarrierC2Support::try_common_gc_state_load(Node *n, PhaseIdealLoop *phase) {
 149   assert(is_gc_state_load(n), "inconsistent");
 150   Node* addp = n->in(MemNode::Address);
 151   Node* dominator = NULL;
 152   for (DUIterator_Fast imax, i = addp->fast_outs(imax); i < imax; i++) {
 153     Node* u = addp->fast_out(i);
 154     assert(is_gc_state_load(u), "inconsistent");
 155     if (u != n && phase->is_dominator(u->in(0), n->in(0))) {
 156       if (dominator == NULL) {
 157         dominator = u;
 158       } else {
 159         if (phase->dom_depth(u->in(0)) < phase->dom_depth(dominator->in(0))) {
 160           dominator = u;
 161         }
 162       }
 163     }
 164   }
 165   if (dominator == NULL || has_safepoint_between(n->in(0), dominator->in(0), phase)) {
 166     return false;
 167   }
 168   phase->igvn().replace_node(n, dominator);
 169 
 170   return true;
 171 }
 172 
 173 #ifdef ASSERT
 174 bool ShenandoahBarrierC2Support::verify_helper(Node* in, Node_Stack& phis, VectorSet& visited, verify_type t, bool trace, Unique_Node_List& barriers_used) {
 175   assert(phis.size() == 0, "");
 176 
 177   while (true) {
 178     if (in->bottom_type() == TypePtr::NULL_PTR) {
 179       if (trace) {tty->print_cr("NULL");}
 180     } else if (!in->bottom_type()->make_ptr()->make_oopptr()) {
 181       if (trace) {tty->print_cr("Non oop");}
 182     } else if (t == ShenandoahLoad && ShenandoahOptimizeStableFinals &&
 183                in->bottom_type()->make_ptr()->isa_aryptr() &&
 184                in->bottom_type()->make_ptr()->is_aryptr()->is_stable()) {
 185       if (trace) {tty->print_cr("Stable array load");}
 186     } else {
 187       if (in->is_ConstraintCast()) {
 188         in = in->in(1);
 189         continue;
 190       } else if (in->is_AddP()) {
 191         assert(!in->in(AddPNode::Address)->is_top(), "no raw memory access");
 192         in = in->in(AddPNode::Address);
 193         continue;
 194       } else if (in->is_Con()) {
 195         if (trace) {
 196           tty->print("Found constant");
 197           in->dump();
 198         }
 199       } else if (in->Opcode() == Op_Parm) {
 200         if (trace) {
 201           tty->print("Found argument");
 202         }
 203       } else if (in->Opcode() == Op_CreateEx) {
 204         if (trace) {
 205           tty->print("Found create-exception");
 206         }
 207       } else if (in->Opcode() == Op_LoadP && in->adr_type() == TypeRawPtr::BOTTOM) {
 208         if (trace) {
 209           tty->print("Found raw LoadP (OSR argument?)");
 210         }
 211       } else if (in->Opcode() == Op_ShenandoahLoadReferenceBarrier ||
 212                  (in->Opcode() == Op_Proj &&
 213                   in->in(0)->Opcode() == Op_CallLeaf &&
 214                   strcmp(in->in(0)->as_Call()->_name, "ShenandoahRuntime::oop_load_from_native_barrier") == 0)) {
 215         if (t == ShenandoahOopStore) {
 216           uint i = 0;
 217           for (; i < phis.size(); i++) {
 218             Node* n = phis.node_at(i);
 219             if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {
 220               break;
 221             }
 222           }
 223           if (i == phis.size()) {
 224             return false;
 225           }
 226         }
 227         barriers_used.push(in);
 228         if (trace) {tty->print("Found barrier"); in->dump();}
 229       } else if (in->Opcode() == Op_ShenandoahEnqueueBarrier) {
 230         if (t != ShenandoahOopStore) {
 231           in = in->in(1);
 232           continue;
 233         }
 234         if (trace) {tty->print("Found enqueue barrier"); in->dump();}
 235         phis.push(in, in->req());
 236         in = in->in(1);
 237         continue;
 238       } else if (in->is_Proj() && in->in(0)->is_Allocate()) {
 239         if (trace) {
 240           tty->print("Found alloc");
 241           in->in(0)->dump();
 242         }
 243       } else if (in->is_Proj() && (in->in(0)->Opcode() == Op_CallStaticJava || in->in(0)->Opcode() == Op_CallDynamicJava)) {
 244         if (trace) {
 245           tty->print("Found Java call");
 246         }
 247       } else if (in->is_Phi()) {
 248         if (!visited.test_set(in->_idx)) {
 249           if (trace) {tty->print("Pushed phi:"); in->dump();}
 250           phis.push(in, 2);
 251           in = in->in(1);
 252           continue;
 253         }
 254         if (trace) {tty->print("Already seen phi:"); in->dump();}
 255       } else if (in->Opcode() == Op_CMoveP || in->Opcode() == Op_CMoveN) {
 256         if (!visited.test_set(in->_idx)) {
 257           if (trace) {tty->print("Pushed cmovep:"); in->dump();}
 258           phis.push(in, CMoveNode::IfTrue);
 259           in = in->in(CMoveNode::IfFalse);
 260           continue;
 261         }
 262         if (trace) {tty->print("Already seen cmovep:"); in->dump();}
 263       } else if (in->Opcode() == Op_EncodeP || in->Opcode() == Op_DecodeN) {
 264         in = in->in(1);
 265         continue;
 266       } else {
 267         return false;
 268       }
 269     }
 270     bool cont = false;
 271     while (phis.is_nonempty()) {
 272       uint idx = phis.index();
 273       Node* phi = phis.node();
 274       if (idx >= phi->req()) {
 275         if (trace) {tty->print("Popped phi:"); phi->dump();}
 276         phis.pop();
 277         continue;
 278       }
 279       if (trace) {tty->print("Next entry(%d) for phi:", idx); phi->dump();}
 280       in = phi->in(idx);
 281       phis.set_index(idx+1);
 282       cont = true;
 283       break;
 284     }
 285     if (!cont) {
 286       break;
 287     }
 288   }
 289   return true;
 290 }
 291 
 292 void ShenandoahBarrierC2Support::report_verify_failure(const char* msg, Node* n1, Node* n2) {
 293   if (n1 != NULL) {
 294     n1->dump(+10);
 295   }
 296   if (n2 != NULL) {
 297     n2->dump(+10);
 298   }
 299   fatal("%s", msg);
 300 }
 301 
 302 void ShenandoahBarrierC2Support::verify(RootNode* root) {
 303   ResourceMark rm;
 304   Unique_Node_List wq;
 305   GrowableArray<Node*> barriers;
 306   Unique_Node_List barriers_used;
 307   Node_Stack phis(0);
 308   VectorSet visited(Thread::current()->resource_area());
 309   const bool trace = false;
 310   const bool verify_no_useless_barrier = false;
 311 
 312   wq.push(root);
 313   for (uint next = 0; next < wq.size(); next++) {
 314     Node *n = wq.at(next);
 315     if (n->is_Load()) {
 316       const bool trace = false;
 317       if (trace) {tty->print("Verifying"); n->dump();}
 318       if (n->Opcode() == Op_LoadRange || n->Opcode() == Op_LoadKlass || n->Opcode() == Op_LoadNKlass) {
 319         if (trace) {tty->print_cr("Load range/klass");}
 320       } else {
 321         const TypePtr* adr_type = n->as_Load()->adr_type();
 322 
 323         if (adr_type->isa_oopptr() && adr_type->is_oopptr()->offset() == oopDesc::mark_offset_in_bytes()) {
 324           if (trace) {tty->print_cr("Mark load");}
 325         } else if (adr_type->isa_instptr() &&
 326                    adr_type->is_instptr()->klass()->is_subtype_of(Compile::current()->env()->Reference_klass()) &&
 327                    adr_type->is_instptr()->offset() == java_lang_ref_Reference::referent_offset) {
 328           if (trace) {tty->print_cr("Reference.get()");}
 329         } else {
 330           bool verify = true;
 331           if (adr_type->isa_instptr()) {
 332             const TypeInstPtr* tinst = adr_type->is_instptr();
 333             ciKlass* k = tinst->klass();
 334             assert(k->is_instance_klass(), "");
 335             ciInstanceKlass* ik = (ciInstanceKlass*)k;
 336             int offset = adr_type->offset();
 337 
 338             if ((ik->debug_final_field_at(offset) && ShenandoahOptimizeInstanceFinals) ||
 339                 (ik->debug_stable_field_at(offset) && ShenandoahOptimizeStableFinals)) {
 340               if (trace) {tty->print_cr("Final/stable");}
 341               verify = false;
 342             } else if (k == ciEnv::current()->Class_klass() &&
 343                        tinst->const_oop() != NULL &&
 344                        tinst->offset() >= (ik->size_helper() * wordSize)) {
 345               ciInstanceKlass* k = tinst->const_oop()->as_instance()->java_lang_Class_klass()->as_instance_klass();
 346               ciField* field = k->get_field_by_offset(tinst->offset(), true);
 347               if ((ShenandoahOptimizeStaticFinals && field->is_final()) ||
 348                   (ShenandoahOptimizeStableFinals && field->is_stable())) {
 349                 verify = false;
 350               }
 351             }
 352           }
 353 
 354           if (verify && !verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahLoad, trace, barriers_used)) {
 355             report_verify_failure("Shenandoah verification: Load should have barriers", n);
 356           }
 357         }
 358       }
 359     } else if (n->is_Store()) {
 360       const bool trace = false;
 361 
 362       if (trace) {tty->print("Verifying"); n->dump();}
 363       if (n->in(MemNode::ValueIn)->bottom_type()->make_oopptr()) {
 364         Node* adr = n->in(MemNode::Address);
 365         bool verify = true;
 366 
 367         if (adr->is_AddP() && adr->in(AddPNode::Base)->is_top()) {
 368           adr = adr->in(AddPNode::Address);
 369           if (adr->is_AddP()) {
 370             assert(adr->in(AddPNode::Base)->is_top(), "");
 371             adr = adr->in(AddPNode::Address);
 372             if (adr->Opcode() == Op_LoadP &&
 373                 adr->in(MemNode::Address)->in(AddPNode::Base)->is_top() &&
 374                 adr->in(MemNode::Address)->in(AddPNode::Address)->Opcode() == Op_ThreadLocal &&
 375                 adr->in(MemNode::Address)->in(AddPNode::Offset)->find_intptr_t_con(-1) == in_bytes(ShenandoahThreadLocalData::satb_mark_queue_buffer_offset())) {
 376               if (trace) {tty->print_cr("SATB prebarrier");}
 377               verify = false;
 378             }
 379           }
 380         }
 381 
 382         if (verify && !verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahStoreValEnqueueBarrier ? ShenandoahOopStore : ShenandoahValue, trace, barriers_used)) {
 383           report_verify_failure("Shenandoah verification: Store should have barriers", n);
 384         }
 385       }
 386       if (!verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 387         report_verify_failure("Shenandoah verification: Store (address) should have barriers", n);
 388       }
 389     } else if (n->Opcode() == Op_CmpP) {
 390       const bool trace = false;
 391 
 392       Node* in1 = n->in(1);
 393       Node* in2 = n->in(2);
 394       if (in1->bottom_type()->isa_oopptr()) {
 395         if (trace) {tty->print("Verifying"); n->dump();}
 396 
 397         bool mark_inputs = false;
 398         if (in1->bottom_type() == TypePtr::NULL_PTR || in2->bottom_type() == TypePtr::NULL_PTR ||
 399             (in1->is_Con() || in2->is_Con())) {
 400           if (trace) {tty->print_cr("Comparison against a constant");}
 401           mark_inputs = true;
 402         } else if ((in1->is_CheckCastPP() && in1->in(1)->is_Proj() && in1->in(1)->in(0)->is_Allocate()) ||
 403                    (in2->is_CheckCastPP() && in2->in(1)->is_Proj() && in2->in(1)->in(0)->is_Allocate())) {
 404           if (trace) {tty->print_cr("Comparison with newly alloc'ed object");}
 405           mark_inputs = true;
 406         } else {
 407           assert(in2->bottom_type()->isa_oopptr(), "");
 408 
 409           if (!verify_helper(in1, phis, visited, ShenandoahStore, trace, barriers_used) ||
 410               !verify_helper(in2, phis, visited, ShenandoahStore, trace, barriers_used)) {
 411             report_verify_failure("Shenandoah verification: Cmp should have barriers", n);
 412           }
 413         }
 414         if (verify_no_useless_barrier &&
 415             mark_inputs &&
 416             (!verify_helper(in1, phis, visited, ShenandoahValue, trace, barriers_used) ||
 417              !verify_helper(in2, phis, visited, ShenandoahValue, trace, barriers_used))) {
 418           phis.clear();
 419           visited.Reset();
 420         }
 421       }
 422     } else if (n->is_LoadStore()) {
 423       if (n->in(MemNode::ValueIn)->bottom_type()->make_ptr() &&
 424           !verify_helper(n->in(MemNode::ValueIn), phis, visited, ShenandoahStoreValEnqueueBarrier ? ShenandoahOopStore : ShenandoahValue, trace, barriers_used)) {
 425         report_verify_failure("Shenandoah verification: LoadStore (value) should have barriers", n);
 426       }
 427 
 428       if (n->in(MemNode::Address)->bottom_type()->make_oopptr() && !verify_helper(n->in(MemNode::Address), phis, visited, ShenandoahStore, trace, barriers_used)) {
 429         report_verify_failure("Shenandoah verification: LoadStore (address) should have barriers", n);
 430       }
 431     } else if (n->Opcode() == Op_CallLeafNoFP || n->Opcode() == Op_CallLeaf) {
 432       CallNode* call = n->as_Call();
 433 
 434       static struct {
 435         const char* name;
 436         struct {
 437           int pos;
 438           verify_type t;
 439         } args[6];
 440       } calls[] = {
 441         "aescrypt_encryptBlock",
 442         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 443           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 444         "aescrypt_decryptBlock",
 445         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 446           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 447         "multiplyToLen",
 448         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },   { TypeFunc::Parms+4, ShenandoahStore },
 449           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 450         "squareToLen",
 451         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },   { -1,  ShenandoahNone},
 452           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 453         "montgomery_multiply",
 454         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },
 455           { TypeFunc::Parms+6, ShenandoahStore }, { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 456         "montgomery_square",
 457         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+5, ShenandoahStore },
 458           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 459         "mulAdd",
 460         { { TypeFunc::Parms, ShenandoahStore },  { TypeFunc::Parms+1, ShenandoahLoad },   { -1,  ShenandoahNone},
 461           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 462         "vectorizedMismatch",
 463         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahLoad },   { -1,  ShenandoahNone},
 464           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 465         "updateBytesCRC32",
 466         { { TypeFunc::Parms+1, ShenandoahLoad }, { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 467           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 468         "updateBytesAdler32",
 469         { { TypeFunc::Parms+1, ShenandoahLoad }, { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 470           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 471         "updateBytesCRC32C",
 472         { { TypeFunc::Parms+1, ShenandoahLoad }, { TypeFunc::Parms+3, ShenandoahLoad},    { -1,  ShenandoahNone},
 473           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 474         "counterMode_AESCrypt",
 475         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 476           { TypeFunc::Parms+3, ShenandoahStore }, { TypeFunc::Parms+5, ShenandoahStore }, { TypeFunc::Parms+6, ShenandoahStore } },
 477         "cipherBlockChaining_encryptAESCrypt",
 478         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 479           { TypeFunc::Parms+3, ShenandoahLoad },  { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 480         "cipherBlockChaining_decryptAESCrypt",
 481         { { TypeFunc::Parms, ShenandoahLoad },   { TypeFunc::Parms+1, ShenandoahStore },  { TypeFunc::Parms+2, ShenandoahLoad },
 482           { TypeFunc::Parms+3, ShenandoahLoad },  { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 483         "shenandoah_clone_barrier",
 484         { { TypeFunc::Parms, ShenandoahLoad },   { -1,  ShenandoahNone},                  { -1,  ShenandoahNone},
 485           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 486         "ghash_processBlocks",
 487         { { TypeFunc::Parms, ShenandoahStore },  { TypeFunc::Parms+1, ShenandoahLoad },   { TypeFunc::Parms+2, ShenandoahLoad },
 488           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 489         "sha1_implCompress",
 490         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 491           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 492         "sha256_implCompress",
 493         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 494           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 495         "sha512_implCompress",
 496         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 497           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 498         "sha1_implCompressMB",
 499         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 500           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 501         "sha256_implCompressMB",
 502         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 503           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 504         "sha512_implCompressMB",
 505         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+1, ShenandoahStore },   { -1, ShenandoahNone },
 506           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 507         "encodeBlock",
 508         { { TypeFunc::Parms, ShenandoahLoad },  { TypeFunc::Parms+3, ShenandoahStore },   { -1, ShenandoahNone },
 509           { -1,  ShenandoahNone},                 { -1,  ShenandoahNone},                 { -1,  ShenandoahNone} },
 510       };
 511 
 512       if (call->is_call_to_arraycopystub()) {
 513         Node* dest = NULL;
 514         const TypeTuple* args = n->as_Call()->_tf->domain();
 515         for (uint i = TypeFunc::Parms, j = 0; i < args->cnt(); i++) {
 516           if (args->field_at(i)->isa_ptr()) {
 517             j++;
 518             if (j == 2) {
 519               dest = n->in(i);
 520               break;
 521             }
 522           }
 523         }
 524         if (!verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahLoad, trace, barriers_used) ||
 525             !verify_helper(dest, phis, visited, ShenandoahStore, trace, barriers_used)) {
 526           report_verify_failure("Shenandoah verification: ArrayCopy should have barriers", n);
 527         }
 528       } else if (strlen(call->_name) > 5 &&
 529                  !strcmp(call->_name + strlen(call->_name) - 5, "_fill")) {
 530         if (!verify_helper(n->in(TypeFunc::Parms), phis, visited, ShenandoahStore, trace, barriers_used)) {
 531           report_verify_failure("Shenandoah verification: _fill should have barriers", n);
 532         }
 533       } else if (!strcmp(call->_name, "shenandoah_wb_pre") || !strcmp(call->_name, "ShenandoahRuntime::oop_load_from_native_barrier")) {
 534         // skip
 535       } else {
 536         const int calls_len = sizeof(calls) / sizeof(calls[0]);
 537         int i = 0;
 538         for (; i < calls_len; i++) {
 539           if (!strcmp(calls[i].name, call->_name)) {
 540             break;
 541           }
 542         }
 543         if (i != calls_len) {
 544           const uint args_len = sizeof(calls[0].args) / sizeof(calls[0].args[0]);
 545           for (uint j = 0; j < args_len; j++) {
 546             int pos = calls[i].args[j].pos;
 547             if (pos == -1) {
 548               break;
 549             }
 550             if (!verify_helper(call->in(pos), phis, visited, calls[i].args[j].t, trace, barriers_used)) {
 551               report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
 552             }
 553           }
 554           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
 555             if (call->in(j)->bottom_type()->make_ptr() &&
 556                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 557               uint k = 0;
 558               for (; k < args_len && calls[i].args[k].pos != (int)j; k++);
 559               if (k == args_len) {
 560                 fatal("arg %d for call %s not covered", j, call->_name);
 561               }
 562             }
 563           }
 564         } else {
 565           for (uint j = TypeFunc::Parms; j < call->req(); j++) {
 566             if (call->in(j)->bottom_type()->make_ptr() &&
 567                 call->in(j)->bottom_type()->make_ptr()->isa_oopptr()) {
 568               fatal("%s not covered", call->_name);
 569             }
 570           }
 571         }
 572       }
 573     } else if (n->Opcode() == Op_ShenandoahEnqueueBarrier || n->Opcode() == Op_ShenandoahLoadReferenceBarrier) {
 574       // skip
 575     } else if (n->is_AddP()
 576                || n->is_Phi()
 577                || n->is_ConstraintCast()
 578                || n->Opcode() == Op_Return
 579                || n->Opcode() == Op_CMoveP
 580                || n->Opcode() == Op_CMoveN
 581                || n->Opcode() == Op_Rethrow
 582                || n->is_MemBar()
 583                || n->Opcode() == Op_Conv2B
 584                || n->Opcode() == Op_SafePoint
 585                || n->is_CallJava()
 586                || n->Opcode() == Op_Unlock
 587                || n->Opcode() == Op_EncodeP
 588                || n->Opcode() == Op_DecodeN) {
 589       // nothing to do
 590     } else {
 591       static struct {
 592         int opcode;
 593         struct {
 594           int pos;
 595           verify_type t;
 596         } inputs[2];
 597       } others[] = {
 598         Op_FastLock,
 599         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
 600         Op_Lock,
 601         { { TypeFunc::Parms, ShenandoahLoad },    { -1, ShenandoahNone} },
 602         Op_ArrayCopy,
 603         { { ArrayCopyNode::Src, ShenandoahLoad }, { ArrayCopyNode::Dest, ShenandoahStore } },
 604         Op_StrCompressedCopy,
 605         { { 2, ShenandoahLoad },                  { 3, ShenandoahStore } },
 606         Op_StrInflatedCopy,
 607         { { 2, ShenandoahLoad },                  { 3, ShenandoahStore } },
 608         Op_AryEq,
 609         { { 2, ShenandoahLoad },                  { 3, ShenandoahLoad } },
 610         Op_StrIndexOf,
 611         { { 2, ShenandoahLoad },                  { 4, ShenandoahLoad } },
 612         Op_StrComp,
 613         { { 2, ShenandoahLoad },                  { 4, ShenandoahLoad } },
 614         Op_StrEquals,
 615         { { 2, ShenandoahLoad },                  { 3, ShenandoahLoad } },
 616         Op_EncodeISOArray,
 617         { { 2, ShenandoahLoad },                  { 3, ShenandoahStore } },
 618         Op_HasNegatives,
 619         { { 2, ShenandoahLoad },                  { -1, ShenandoahNone} },
 620         Op_CastP2X,
 621         { { 1, ShenandoahLoad },                  { -1, ShenandoahNone} },
 622         Op_StrIndexOfChar,
 623         { { 2, ShenandoahLoad },                  { -1, ShenandoahNone } },
 624       };
 625 
 626       const int others_len = sizeof(others) / sizeof(others[0]);
 627       int i = 0;
 628       for (; i < others_len; i++) {
 629         if (others[i].opcode == n->Opcode()) {
 630           break;
 631         }
 632       }
 633       uint stop = n->is_Call() ? n->as_Call()->tf()->domain()->cnt() : n->req();
 634       if (i != others_len) {
 635         const uint inputs_len = sizeof(others[0].inputs) / sizeof(others[0].inputs[0]);
 636         for (uint j = 0; j < inputs_len; j++) {
 637           int pos = others[i].inputs[j].pos;
 638           if (pos == -1) {
 639             break;
 640           }
 641           if (!verify_helper(n->in(pos), phis, visited, others[i].inputs[j].t, trace, barriers_used)) {
 642             report_verify_failure("Shenandoah verification: intrinsic calls should have barriers", n);
 643           }
 644         }
 645         for (uint j = 1; j < stop; j++) {
 646           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
 647               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
 648             uint k = 0;
 649             for (; k < inputs_len && others[i].inputs[k].pos != (int)j; k++);
 650             if (k == inputs_len) {
 651               fatal("arg %d for node %s not covered", j, n->Name());
 652             }
 653           }
 654         }
 655       } else {
 656         for (uint j = 1; j < stop; j++) {
 657           if (n->in(j) != NULL && n->in(j)->bottom_type()->make_ptr() &&
 658               n->in(j)->bottom_type()->make_ptr()->make_oopptr()) {
 659             fatal("%s not covered", n->Name());
 660           }
 661         }
 662       }
 663     }
 664 
 665     if (n->is_SafePoint()) {
 666       SafePointNode* sfpt = n->as_SafePoint();
 667       if (verify_no_useless_barrier && sfpt->jvms() != NULL) {
 668         for (uint i = sfpt->jvms()->scloff(); i < sfpt->jvms()->endoff(); i++) {
 669           if (!verify_helper(sfpt->in(i), phis, visited, ShenandoahLoad, trace, barriers_used)) {
 670             phis.clear();
 671             visited.Reset();
 672           }
 673         }
 674       }
 675     }
 676     for( uint i = 0; i < n->len(); ++i ) {
 677       Node *m = n->in(i);
 678       if (m == NULL) continue;
 679 
 680       // In most cases, inputs should be known to be non null. If it's
 681       // not the case, it could be a missing cast_not_null() in an
 682       // intrinsic or support might be needed in AddPNode::Ideal() to
 683       // avoid a NULL+offset input.
 684       if (!(n->is_Phi() ||
 685             (n->is_SafePoint() && (!n->is_CallRuntime() || !strcmp(n->as_Call()->_name, "shenandoah_wb_pre") || !strcmp(n->as_Call()->_name, "unsafe_arraycopy"))) ||
 686             n->Opcode() == Op_CmpP ||
 687             n->Opcode() == Op_CmpN ||
 688             (n->Opcode() == Op_StoreP && i == StoreNode::ValueIn) ||
 689             (n->Opcode() == Op_StoreN && i == StoreNode::ValueIn) ||
 690             n->is_ConstraintCast() ||
 691             n->Opcode() == Op_Return ||
 692             n->Opcode() == Op_Conv2B ||
 693             n->is_AddP() ||
 694             n->Opcode() == Op_CMoveP ||
 695             n->Opcode() == Op_CMoveN ||
 696             n->Opcode() == Op_Rethrow ||
 697             n->is_MemBar() ||
 698             n->is_Mem() ||
 699             n->Opcode() == Op_AryEq ||
 700             n->Opcode() == Op_SCMemProj ||
 701             n->Opcode() == Op_EncodeP ||
 702             n->Opcode() == Op_DecodeN ||
 703             n->Opcode() == Op_ShenandoahEnqueueBarrier ||
 704             n->Opcode() == Op_ShenandoahLoadReferenceBarrier)) {
 705         if (m->bottom_type()->make_oopptr() && m->bottom_type()->make_oopptr()->meet(TypePtr::NULL_PTR) == m->bottom_type()) {
 706           report_verify_failure("Shenandoah verification: null input", n, m);
 707         }
 708       }
 709 
 710       wq.push(m);
 711     }
 712   }
 713 
 714   if (verify_no_useless_barrier) {
 715     for (int i = 0; i < barriers.length(); i++) {
 716       Node* n = barriers.at(i);
 717       if (!barriers_used.member(n)) {
 718         tty->print("XXX useless barrier"); n->dump(-2);
 719         ShouldNotReachHere();
 720       }
 721     }
 722   }
 723 }
 724 #endif
 725 
 726 bool ShenandoahBarrierC2Support::is_dominator_same_ctrl(Node* c, Node* d, Node* n, PhaseIdealLoop* phase) {
 727   // That both nodes have the same control is not sufficient to prove
 728   // domination, verify that there's no path from d to n
 729   ResourceMark rm;
 730   Unique_Node_List wq;
 731   wq.push(d);
 732   for (uint next = 0; next < wq.size(); next++) {
 733     Node *m = wq.at(next);
 734     if (m == n) {
 735       return false;
 736     }
 737     if (m->is_Phi() && m->in(0)->is_Loop()) {
 738       assert(phase->ctrl_or_self(m->in(LoopNode::EntryControl)) != c, "following loop entry should lead to new control");
 739     } else {
 740       for (uint i = 0; i < m->req(); i++) {
 741         if (m->in(i) != NULL && phase->ctrl_or_self(m->in(i)) == c) {
 742           wq.push(m->in(i));
 743         }
 744       }
 745     }
 746   }
 747   return true;
 748 }
 749 
 750 bool ShenandoahBarrierC2Support::is_dominator(Node* d_c, Node* n_c, Node* d, Node* n, PhaseIdealLoop* phase) {
 751   if (d_c != n_c) {
 752     return phase->is_dominator(d_c, n_c);
 753   }
 754   return is_dominator_same_ctrl(d_c, d, n, phase);
 755 }
 756 
 757 Node* next_mem(Node* mem, int alias) {
 758   Node* res = NULL;
 759   if (mem->is_Proj()) {
 760     res = mem->in(0);
 761   } else if (mem->is_SafePoint() || mem->is_MemBar()) {
 762     res = mem->in(TypeFunc::Memory);
 763   } else if (mem->is_Phi()) {
 764     res = mem->in(1);
 765   } else if (mem->is_MergeMem()) {
 766     res = mem->as_MergeMem()->memory_at(alias);
 767   } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
 768     assert(alias = Compile::AliasIdxRaw, "following raw memory can't lead to a barrier");
 769     res = mem->in(MemNode::Memory);
 770   } else {
 771 #ifdef ASSERT
 772     mem->dump();
 773 #endif
 774     ShouldNotReachHere();
 775   }
 776   return res;
 777 }
 778 
 779 Node* ShenandoahBarrierC2Support::no_branches(Node* c, Node* dom, bool allow_one_proj, PhaseIdealLoop* phase) {
 780   Node* iffproj = NULL;
 781   while (c != dom) {
 782     Node* next = phase->idom(c);
 783     assert(next->unique_ctrl_out() == c || c->is_Proj() || c->is_Region(), "multiple control flow out but no proj or region?");
 784     if (c->is_Region()) {
 785       ResourceMark rm;
 786       Unique_Node_List wq;
 787       wq.push(c);
 788       for (uint i = 0; i < wq.size(); i++) {
 789         Node *n = wq.at(i);
 790         if (n == next) {
 791           continue;
 792         }
 793         if (n->is_Region()) {
 794           for (uint j = 1; j < n->req(); j++) {
 795             wq.push(n->in(j));
 796           }
 797         } else {
 798           wq.push(n->in(0));
 799         }
 800       }
 801       for (uint i = 0; i < wq.size(); i++) {
 802         Node *n = wq.at(i);
 803         assert(n->is_CFG(), "");
 804         if (n->is_Multi()) {
 805           for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
 806             Node* u = n->fast_out(j);
 807             if (u->is_CFG()) {
 808               if (!wq.member(u) && !u->as_Proj()->is_uncommon_trap_proj(Deoptimization::Reason_none)) {
 809                 return NodeSentinel;
 810               }
 811             }
 812           }
 813         }
 814       }
 815     } else  if (c->is_Proj()) {
 816       if (c->is_IfProj()) {
 817         if (c->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) != NULL) {
 818           // continue;
 819         } else {
 820           if (!allow_one_proj) {
 821             return NodeSentinel;
 822           }
 823           if (iffproj == NULL) {
 824             iffproj = c;
 825           } else {
 826             return NodeSentinel;
 827           }
 828         }
 829       } else if (c->Opcode() == Op_JumpProj) {
 830         return NodeSentinel; // unsupported
 831       } else if (c->Opcode() == Op_CatchProj) {
 832         return NodeSentinel; // unsupported
 833       } else if (c->Opcode() == Op_CProj && next->Opcode() == Op_NeverBranch) {
 834         return NodeSentinel; // unsupported
 835       } else {
 836         assert(next->unique_ctrl_out() == c, "unsupported branch pattern");
 837       }
 838     }
 839     c = next;
 840   }
 841   return iffproj;
 842 }
 843 
 844 Node* ShenandoahBarrierC2Support::dom_mem(Node* mem, Node* ctrl, int alias, Node*& mem_ctrl, PhaseIdealLoop* phase) {
 845   ResourceMark rm;
 846   VectorSet wq(Thread::current()->resource_area());
 847   wq.set(mem->_idx);
 848   mem_ctrl = phase->ctrl_or_self(mem);
 849   while (!phase->is_dominator(mem_ctrl, ctrl) || mem_ctrl == ctrl) {
 850     mem = next_mem(mem, alias);
 851     if (wq.test_set(mem->_idx)) {
 852       return NULL;
 853     }
 854     mem_ctrl = phase->ctrl_or_self(mem);
 855   }
 856   if (mem->is_MergeMem()) {
 857     mem = mem->as_MergeMem()->memory_at(alias);
 858     mem_ctrl = phase->ctrl_or_self(mem);
 859   }
 860   return mem;
 861 }
 862 
 863 Node* ShenandoahBarrierC2Support::find_bottom_mem(Node* ctrl, PhaseIdealLoop* phase) {
 864   Node* mem = NULL;
 865   Node* c = ctrl;
 866   do {
 867     if (c->is_Region()) {
 868       Node* phi_bottom = NULL;
 869       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax && mem == NULL; i++) {
 870         Node* u = c->fast_out(i);
 871         if (u->is_Phi() && u->bottom_type() == Type::MEMORY) {
 872           if (u->adr_type() == TypePtr::BOTTOM) {
 873             mem = u;
 874           }
 875         }
 876       }
 877     } else {
 878       if (c->is_Call() && c->as_Call()->adr_type() != NULL) {
 879         CallProjections projs;
 880         c->as_Call()->extract_projections(&projs, true, false);
 881         if (projs.fallthrough_memproj != NULL) {
 882           if (projs.fallthrough_memproj->adr_type() == TypePtr::BOTTOM) {
 883             if (projs.catchall_memproj == NULL) {
 884               mem = projs.fallthrough_memproj;
 885             } else {
 886               if (phase->is_dominator(projs.fallthrough_catchproj, ctrl)) {
 887                 mem = projs.fallthrough_memproj;
 888               } else {
 889                 assert(phase->is_dominator(projs.catchall_catchproj, ctrl), "one proj must dominate barrier");
 890                 mem = projs.catchall_memproj;
 891               }
 892             }
 893           }
 894         } else {
 895           Node* proj = c->as_Call()->proj_out(TypeFunc::Memory);
 896           if (proj != NULL &&
 897               proj->adr_type() == TypePtr::BOTTOM) {
 898             mem = proj;
 899           }
 900         }
 901       } else {
 902         for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
 903           Node* u = c->fast_out(i);
 904           if (u->is_Proj() &&
 905               u->bottom_type() == Type::MEMORY &&
 906               u->adr_type() == TypePtr::BOTTOM) {
 907               assert(c->is_SafePoint() || c->is_MemBar() || c->is_Start(), "");
 908               assert(mem == NULL, "only one proj");
 909               mem = u;
 910           }
 911         }
 912         assert(!c->is_Call() || c->as_Call()->adr_type() != NULL || mem == NULL, "no mem projection expected");
 913       }
 914     }
 915     c = phase->idom(c);
 916   } while (mem == NULL);
 917   return mem;
 918 }
 919 
 920 void ShenandoahBarrierC2Support::follow_barrier_uses(Node* n, Node* ctrl, Unique_Node_List& uses, PhaseIdealLoop* phase) {
 921   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
 922     Node* u = n->fast_out(i);
 923     if (!u->is_CFG() && phase->get_ctrl(u) == ctrl && (!u->is_Phi() || !u->in(0)->is_Loop() || u->in(LoopNode::LoopBackControl) != n)) {
 924       uses.push(u);
 925     }
 926   }
 927 }
 928 
 929 static void hide_strip_mined_loop(OuterStripMinedLoopNode* outer, CountedLoopNode* inner, PhaseIdealLoop* phase) {
 930   OuterStripMinedLoopEndNode* le = inner->outer_loop_end();
 931   Node* new_outer = new LoopNode(outer->in(LoopNode::EntryControl), outer->in(LoopNode::LoopBackControl));
 932   phase->register_control(new_outer, phase->get_loop(outer), outer->in(LoopNode::EntryControl));
 933   Node* new_le = new IfNode(le->in(0), le->in(1), le->_prob, le->_fcnt);
 934   phase->register_control(new_le, phase->get_loop(le), le->in(0));
 935   phase->lazy_replace(outer, new_outer);
 936   phase->lazy_replace(le, new_le);
 937   inner->clear_strip_mined();
 938 }
 939 
 940 void ShenandoahBarrierC2Support::test_heap_stable(Node*& ctrl, Node* raw_mem, Node*& heap_stable_ctrl,
 941                                                   PhaseIdealLoop* phase) {
 942   IdealLoopTree* loop = phase->get_loop(ctrl);
 943   Node* thread = new ThreadLocalNode();
 944   phase->register_new_node(thread, ctrl);
 945   Node* offset = phase->igvn().MakeConX(in_bytes(ShenandoahThreadLocalData::gc_state_offset()));
 946   phase->set_ctrl(offset, phase->C->root());
 947   Node* gc_state_addr = new AddPNode(phase->C->top(), thread, offset);
 948   phase->register_new_node(gc_state_addr, ctrl);
 949   uint gc_state_idx = Compile::AliasIdxRaw;
 950   const TypePtr* gc_state_adr_type = NULL; // debug-mode-only argument
 951   debug_only(gc_state_adr_type = phase->C->get_adr_type(gc_state_idx));
 952 
 953   Node* gc_state = new LoadBNode(ctrl, raw_mem, gc_state_addr, gc_state_adr_type, TypeInt::BYTE, MemNode::unordered);
 954   phase->register_new_node(gc_state, ctrl);
 955   Node* heap_stable_and = new AndINode(gc_state, phase->igvn().intcon(ShenandoahHeap::HAS_FORWARDED));
 956   phase->register_new_node(heap_stable_and, ctrl);
 957   Node* heap_stable_cmp = new CmpINode(heap_stable_and, phase->igvn().zerocon(T_INT));
 958   phase->register_new_node(heap_stable_cmp, ctrl);
 959   Node* heap_stable_test = new BoolNode(heap_stable_cmp, BoolTest::ne);
 960   phase->register_new_node(heap_stable_test, ctrl);
 961   IfNode* heap_stable_iff = new IfNode(ctrl, heap_stable_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
 962   phase->register_control(heap_stable_iff, loop, ctrl);
 963 
 964   heap_stable_ctrl = new IfFalseNode(heap_stable_iff);
 965   phase->register_control(heap_stable_ctrl, loop, heap_stable_iff);
 966   ctrl = new IfTrueNode(heap_stable_iff);
 967   phase->register_control(ctrl, loop, heap_stable_iff);
 968 
 969   assert(is_heap_stable_test(heap_stable_iff), "Should match the shape");
 970 }
 971 
 972 void ShenandoahBarrierC2Support::test_null(Node*& ctrl, Node* val, Node*& null_ctrl, PhaseIdealLoop* phase) {
 973   const Type* val_t = phase->igvn().type(val);
 974   if (val_t->meet(TypePtr::NULL_PTR) == val_t) {
 975     IdealLoopTree* loop = phase->get_loop(ctrl);
 976     Node* null_cmp = new CmpPNode(val, phase->igvn().zerocon(T_OBJECT));
 977     phase->register_new_node(null_cmp, ctrl);
 978     Node* null_test = new BoolNode(null_cmp, BoolTest::ne);
 979     phase->register_new_node(null_test, ctrl);
 980     IfNode* null_iff = new IfNode(ctrl, null_test, PROB_LIKELY(0.999), COUNT_UNKNOWN);
 981     phase->register_control(null_iff, loop, ctrl);
 982     ctrl = new IfTrueNode(null_iff);
 983     phase->register_control(ctrl, loop, null_iff);
 984     null_ctrl = new IfFalseNode(null_iff);
 985     phase->register_control(null_ctrl, loop, null_iff);
 986   }
 987 }
 988 
 989 Node* ShenandoahBarrierC2Support::clone_null_check(Node*& c, Node* val, Node* unc_ctrl, PhaseIdealLoop* phase) {
 990   IdealLoopTree *loop = phase->get_loop(c);
 991   Node* iff = unc_ctrl->in(0);
 992   assert(iff->is_If(), "broken");
 993   Node* new_iff = iff->clone();
 994   new_iff->set_req(0, c);
 995   phase->register_control(new_iff, loop, c);
 996   Node* iffalse = new IfFalseNode(new_iff->as_If());
 997   phase->register_control(iffalse, loop, new_iff);
 998   Node* iftrue = new IfTrueNode(new_iff->as_If());
 999   phase->register_control(iftrue, loop, new_iff);
1000   c = iftrue;
1001   const Type *t = phase->igvn().type(val);
1002   assert(val->Opcode() == Op_CastPP, "expect cast to non null here");
1003   Node* uncasted_val = val->in(1);
1004   val = new CastPPNode(uncasted_val, t);
1005   val->init_req(0, c);
1006   phase->register_new_node(val, c);
1007   return val;
1008 }
1009 
1010 void ShenandoahBarrierC2Support::fix_null_check(Node* unc, Node* unc_ctrl, Node* new_unc_ctrl,
1011                                                 Unique_Node_List& uses, PhaseIdealLoop* phase) {
1012   IfNode* iff = unc_ctrl->in(0)->as_If();
1013   Node* proj = iff->proj_out(0);
1014   assert(proj != unc_ctrl, "bad projection");
1015   Node* use = proj->unique_ctrl_out();
1016 
1017   assert(use == unc || use->is_Region(), "what else?");
1018 
1019   uses.clear();
1020   if (use == unc) {
1021     phase->set_idom(use, new_unc_ctrl, phase->dom_depth(use));
1022     for (uint i = 1; i < unc->req(); i++) {
1023       Node* n = unc->in(i);
1024       if (phase->has_ctrl(n) && phase->get_ctrl(n) == proj) {
1025         uses.push(n);
1026       }
1027     }
1028   } else {
1029     assert(use->is_Region(), "what else?");
1030     uint idx = 1;
1031     for (; use->in(idx) != proj; idx++);
1032     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1033       Node* u = use->fast_out(i);
1034       if (u->is_Phi() && phase->get_ctrl(u->in(idx)) == proj) {
1035         uses.push(u->in(idx));
1036       }
1037     }
1038   }
1039   for(uint next = 0; next < uses.size(); next++ ) {
1040     Node *n = uses.at(next);
1041     assert(phase->get_ctrl(n) == proj, "bad control");
1042     phase->set_ctrl_and_loop(n, new_unc_ctrl);
1043     if (n->in(0) == proj) {
1044       phase->igvn().replace_input_of(n, 0, new_unc_ctrl);
1045     }
1046     for (uint i = 0; i < n->req(); i++) {
1047       Node* m = n->in(i);
1048       if (m != NULL && phase->has_ctrl(m) && phase->get_ctrl(m) == proj) {
1049         uses.push(m);
1050       }
1051     }
1052   }
1053 
1054   phase->igvn().rehash_node_delayed(use);
1055   int nb = use->replace_edge(proj, new_unc_ctrl);
1056   assert(nb == 1, "only use expected");
1057 }
1058 
1059 void ShenandoahBarrierC2Support::in_cset_fast_test(Node*& ctrl, Node*& not_cset_ctrl, Node* val, Node* raw_mem, PhaseIdealLoop* phase) {
1060   IdealLoopTree *loop = phase->get_loop(ctrl);
1061   Node* raw_rbtrue = new CastP2XNode(ctrl, val);
1062   phase->register_new_node(raw_rbtrue, ctrl);
1063   Node* cset_offset = new URShiftXNode(raw_rbtrue, phase->igvn().intcon(ShenandoahHeapRegion::region_size_bytes_shift_jint()));
1064   phase->register_new_node(cset_offset, ctrl);
1065   Node* in_cset_fast_test_base_addr = phase->igvn().makecon(TypeRawPtr::make(ShenandoahHeap::in_cset_fast_test_addr()));
1066   phase->set_ctrl(in_cset_fast_test_base_addr, phase->C->root());
1067   Node* in_cset_fast_test_adr = new AddPNode(phase->C->top(), in_cset_fast_test_base_addr, cset_offset);
1068   phase->register_new_node(in_cset_fast_test_adr, ctrl);
1069   uint in_cset_fast_test_idx = Compile::AliasIdxRaw;
1070   const TypePtr* in_cset_fast_test_adr_type = NULL; // debug-mode-only argument
1071   debug_only(in_cset_fast_test_adr_type = phase->C->get_adr_type(in_cset_fast_test_idx));
1072   Node* in_cset_fast_test_load = new LoadBNode(ctrl, raw_mem, in_cset_fast_test_adr, in_cset_fast_test_adr_type, TypeInt::BYTE, MemNode::unordered);
1073   phase->register_new_node(in_cset_fast_test_load, ctrl);
1074   Node* in_cset_fast_test_cmp = new CmpINode(in_cset_fast_test_load, phase->igvn().zerocon(T_INT));
1075   phase->register_new_node(in_cset_fast_test_cmp, ctrl);
1076   Node* in_cset_fast_test_test = new BoolNode(in_cset_fast_test_cmp, BoolTest::eq);
1077   phase->register_new_node(in_cset_fast_test_test, ctrl);
1078   IfNode* in_cset_fast_test_iff = new IfNode(ctrl, in_cset_fast_test_test, PROB_UNLIKELY(0.999), COUNT_UNKNOWN);
1079   phase->register_control(in_cset_fast_test_iff, loop, ctrl);
1080 
1081   not_cset_ctrl = new IfTrueNode(in_cset_fast_test_iff);
1082   phase->register_control(not_cset_ctrl, loop, in_cset_fast_test_iff);
1083 
1084   ctrl = new IfFalseNode(in_cset_fast_test_iff);
1085   phase->register_control(ctrl, loop, in_cset_fast_test_iff);
1086 }
1087 
1088 void ShenandoahBarrierC2Support::call_lrb_stub(Node*& ctrl, Node*& val, Node*& result_mem, Node* raw_mem, PhaseIdealLoop* phase) {
1089   IdealLoopTree*loop = phase->get_loop(ctrl);
1090   const TypePtr* obj_type = phase->igvn().type(val)->is_oopptr()->cast_to_nonconst();
1091 
1092   // The slow path stub consumes and produces raw memory in addition
1093   // to the existing memory edges
1094   Node* base = find_bottom_mem(ctrl, phase);
1095   MergeMemNode* mm = MergeMemNode::make(base);
1096   mm->set_memory_at(Compile::AliasIdxRaw, raw_mem);
1097   phase->register_new_node(mm, ctrl);
1098 
1099   Node* call = new CallLeafNode(ShenandoahBarrierSetC2::shenandoah_load_reference_barrier_Type(), CAST_FROM_FN_PTR(address, ShenandoahRuntime::load_reference_barrier_JRT), "shenandoah_load_reference_barrier", TypeRawPtr::BOTTOM);
1100   call->init_req(TypeFunc::Control, ctrl);
1101   call->init_req(TypeFunc::I_O, phase->C->top());
1102   call->init_req(TypeFunc::Memory, mm);
1103   call->init_req(TypeFunc::FramePtr, phase->C->top());
1104   call->init_req(TypeFunc::ReturnAdr, phase->C->top());
1105   call->init_req(TypeFunc::Parms, val);
1106   phase->register_control(call, loop, ctrl);
1107   ctrl = new ProjNode(call, TypeFunc::Control);
1108   phase->register_control(ctrl, loop, call);
1109   result_mem = new ProjNode(call, TypeFunc::Memory);
1110   phase->register_new_node(result_mem, call);
1111   val = new ProjNode(call, TypeFunc::Parms);
1112   phase->register_new_node(val, call);
1113   val = new CheckCastPPNode(ctrl, val, obj_type);
1114   phase->register_new_node(val, ctrl);
1115 }
1116 
1117 void ShenandoahBarrierC2Support::fix_ctrl(Node* barrier, Node* region, const MemoryGraphFixer& fixer, Unique_Node_List& uses, Unique_Node_List& uses_to_ignore, uint last, PhaseIdealLoop* phase) {
1118   Node* ctrl = phase->get_ctrl(barrier);
1119   Node* init_raw_mem = fixer.find_mem(ctrl, barrier);
1120 
1121   // Update the control of all nodes that should be after the
1122   // barrier control flow
1123   uses.clear();
1124   // Every node that is control dependent on the barrier's input
1125   // control will be after the expanded barrier. The raw memory (if
1126   // its memory is control dependent on the barrier's input control)
1127   // must stay above the barrier.
1128   uses_to_ignore.clear();
1129   if (phase->has_ctrl(init_raw_mem) && phase->get_ctrl(init_raw_mem) == ctrl && !init_raw_mem->is_Phi()) {
1130     uses_to_ignore.push(init_raw_mem);
1131   }
1132   for (uint next = 0; next < uses_to_ignore.size(); next++) {
1133     Node *n = uses_to_ignore.at(next);
1134     for (uint i = 0; i < n->req(); i++) {
1135       Node* in = n->in(i);
1136       if (in != NULL && phase->has_ctrl(in) && phase->get_ctrl(in) == ctrl) {
1137         uses_to_ignore.push(in);
1138       }
1139     }
1140   }
1141   for (DUIterator_Fast imax, i = ctrl->fast_outs(imax); i < imax; i++) {
1142     Node* u = ctrl->fast_out(i);
1143     if (u->_idx < last &&
1144         u != barrier &&
1145         !uses_to_ignore.member(u) &&
1146         (u->in(0) != ctrl || (!u->is_Region() && !u->is_Phi())) &&
1147         (ctrl->Opcode() != Op_CatchProj || u->Opcode() != Op_CreateEx)) {
1148       Node* old_c = phase->ctrl_or_self(u);
1149       Node* c = old_c;
1150       if (c != ctrl ||
1151           is_dominator_same_ctrl(old_c, barrier, u, phase) ||
1152           ShenandoahBarrierSetC2::is_shenandoah_state_load(u)) {
1153         phase->igvn().rehash_node_delayed(u);
1154         int nb = u->replace_edge(ctrl, region);
1155         if (u->is_CFG()) {
1156           if (phase->idom(u) == ctrl) {
1157             phase->set_idom(u, region, phase->dom_depth(region));
1158           }
1159         } else if (phase->get_ctrl(u) == ctrl) {
1160           assert(u != init_raw_mem, "should leave input raw mem above the barrier");
1161           uses.push(u);
1162         }
1163         assert(nb == 1, "more than 1 ctrl input?");
1164         --i, imax -= nb;
1165       }
1166     }
1167   }
1168 }
1169 
1170 static Node* create_phis_on_call_return(Node* ctrl, Node* c, Node* n, Node* n_clone, const CallProjections& projs, PhaseIdealLoop* phase) {
1171   Node* region = NULL;
1172   while (c != ctrl) {
1173     if (c->is_Region()) {
1174       region = c;
1175     }
1176     c = phase->idom(c);
1177   }
1178   assert(region != NULL, "");
1179   Node* phi = new PhiNode(region, n->bottom_type());
1180   for (uint j = 1; j < region->req(); j++) {
1181     Node* in = region->in(j);
1182     if (phase->is_dominator(projs.fallthrough_catchproj, in)) {
1183       phi->init_req(j, n);
1184     } else if (phase->is_dominator(projs.catchall_catchproj, in)) {
1185       phi->init_req(j, n_clone);
1186     } else {
1187       phi->init_req(j, create_phis_on_call_return(ctrl, in, n, n_clone, projs, phase));
1188     }
1189   }
1190   phase->register_new_node(phi, region);
1191   return phi;
1192 }
1193 
1194 void ShenandoahBarrierC2Support::pin_and_expand(PhaseIdealLoop* phase) {
1195   ShenandoahBarrierSetC2State* state = ShenandoahBarrierSetC2::bsc2()->state();
1196 
1197   Unique_Node_List uses;
1198   for (int i = 0; i < state->enqueue_barriers_count(); i++) {
1199     Node* barrier = state->enqueue_barrier(i);
1200     Node* ctrl = phase->get_ctrl(barrier);
1201     IdealLoopTree* loop = phase->get_loop(ctrl);
1202     if (loop->_head->is_OuterStripMinedLoop()) {
1203       // Expanding a barrier here will break loop strip mining
1204       // verification. Transform the loop so the loop nest doesn't
1205       // appear as strip mined.
1206       OuterStripMinedLoopNode* outer = loop->_head->as_OuterStripMinedLoop();
1207       hide_strip_mined_loop(outer, outer->unique_ctrl_out()->as_CountedLoop(), phase);
1208     }
1209   }
1210 
1211   Node_Stack stack(0);
1212   Node_List clones;
1213   for (int i = state->load_reference_barriers_count() - 1; i >= 0; i--) {
1214     ShenandoahLoadReferenceBarrierNode* lrb = state->load_reference_barrier(i);
1215     if (lrb->get_barrier_strength() == ShenandoahLoadReferenceBarrierNode::NONE) {
1216       continue;
1217     }
1218 
1219     Node* ctrl = phase->get_ctrl(lrb);
1220     Node* val = lrb->in(ShenandoahLoadReferenceBarrierNode::ValueIn);
1221 
1222     CallStaticJavaNode* unc = NULL;
1223     Node* unc_ctrl = NULL;
1224     Node* uncasted_val = val;
1225 
1226     for (DUIterator_Fast imax, i = lrb->fast_outs(imax); i < imax; i++) {
1227       Node* u = lrb->fast_out(i);
1228       if (u->Opcode() == Op_CastPP &&
1229           u->in(0) != NULL &&
1230           phase->is_dominator(u->in(0), ctrl)) {
1231         const Type* u_t = phase->igvn().type(u);
1232 
1233         if (u_t->meet(TypePtr::NULL_PTR) != u_t &&
1234             u->in(0)->Opcode() == Op_IfTrue &&
1235             u->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
1236             u->in(0)->in(0)->is_If() &&
1237             u->in(0)->in(0)->in(1)->Opcode() == Op_Bool &&
1238             u->in(0)->in(0)->in(1)->as_Bool()->_test._test == BoolTest::ne &&
1239             u->in(0)->in(0)->in(1)->in(1)->Opcode() == Op_CmpP &&
1240             u->in(0)->in(0)->in(1)->in(1)->in(1) == val &&
1241             u->in(0)->in(0)->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
1242           IdealLoopTree* loop = phase->get_loop(ctrl);
1243           IdealLoopTree* unc_loop = phase->get_loop(u->in(0));
1244 
1245           if (!unc_loop->is_member(loop)) {
1246             continue;
1247           }
1248 
1249           Node* branch = no_branches(ctrl, u->in(0), false, phase);
1250           assert(branch == NULL || branch == NodeSentinel, "was not looking for a branch");
1251           if (branch == NodeSentinel) {
1252             continue;
1253           }
1254 
1255           phase->igvn().replace_input_of(u, 1, val);
1256           phase->igvn().replace_input_of(lrb, ShenandoahLoadReferenceBarrierNode::ValueIn, u);
1257           phase->set_ctrl(u, u->in(0));
1258           phase->set_ctrl(lrb, u->in(0));
1259           unc = u->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
1260           unc_ctrl = u->in(0);
1261           val = u;
1262 
1263           for (DUIterator_Fast jmax, j = val->fast_outs(jmax); j < jmax; j++) {
1264             Node* u = val->fast_out(j);
1265             if (u == lrb) continue;
1266             phase->igvn().rehash_node_delayed(u);
1267             int nb = u->replace_edge(val, lrb);
1268             --j; jmax -= nb;
1269           }
1270 
1271           RegionNode* r = new RegionNode(3);
1272           IfNode* iff = unc_ctrl->in(0)->as_If();
1273 
1274           Node* ctrl_use = unc_ctrl->unique_ctrl_out();
1275           Node* unc_ctrl_clone = unc_ctrl->clone();
1276           phase->register_control(unc_ctrl_clone, loop, iff);
1277           Node* c = unc_ctrl_clone;
1278           Node* new_cast = clone_null_check(c, val, unc_ctrl_clone, phase);
1279           r->init_req(1, new_cast->in(0)->in(0)->as_If()->proj_out(0));
1280 
1281           phase->igvn().replace_input_of(unc_ctrl, 0, c->in(0));
1282           phase->set_idom(unc_ctrl, c->in(0), phase->dom_depth(unc_ctrl));
1283           phase->lazy_replace(c, unc_ctrl);
1284           c = NULL;;
1285           phase->igvn().replace_input_of(val, 0, unc_ctrl_clone);
1286           phase->set_ctrl(val, unc_ctrl_clone);
1287 
1288           IfNode* new_iff = new_cast->in(0)->in(0)->as_If();
1289           fix_null_check(unc, unc_ctrl_clone, r, uses, phase);
1290           Node* iff_proj = iff->proj_out(0);
1291           r->init_req(2, iff_proj);
1292           phase->register_control(r, phase->ltree_root(), iff);
1293 
1294           Node* new_bol = new_iff->in(1)->clone();
1295           Node* new_cmp = new_bol->in(1)->clone();
1296           assert(new_cmp->Opcode() == Op_CmpP, "broken");
1297           assert(new_cmp->in(1) == val->in(1), "broken");
1298           new_bol->set_req(1, new_cmp);
1299           new_cmp->set_req(1, lrb);
1300           phase->register_new_node(new_bol, new_iff->in(0));
1301           phase->register_new_node(new_cmp, new_iff->in(0));
1302           phase->igvn().replace_input_of(new_iff, 1, new_bol);
1303           phase->igvn().replace_input_of(new_cast, 1, lrb);
1304 
1305           for (DUIterator_Fast imax, i = lrb->fast_outs(imax); i < imax; i++) {
1306             Node* u = lrb->fast_out(i);
1307             if (u == new_cast || u == new_cmp) {
1308               continue;
1309             }
1310             phase->igvn().rehash_node_delayed(u);
1311             int nb = u->replace_edge(lrb, new_cast);
1312             assert(nb > 0, "no update?");
1313             --i; imax -= nb;
1314           }
1315 
1316           for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
1317             Node* u = val->fast_out(i);
1318             if (u == lrb) {
1319               continue;
1320             }
1321             phase->igvn().rehash_node_delayed(u);
1322             int nb = u->replace_edge(val, new_cast);
1323             assert(nb > 0, "no update?");
1324             --i; imax -= nb;
1325           }
1326 
1327           ctrl = unc_ctrl_clone;
1328           phase->set_ctrl_and_loop(lrb, ctrl);
1329           break;
1330         }
1331       }
1332     }
1333     if ((ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) || ctrl->is_CallJava()) {
1334       CallNode* call = ctrl->is_Proj() ? ctrl->in(0)->as_CallJava() : ctrl->as_CallJava();
1335       CallProjections projs;
1336       call->extract_projections(&projs, false, false);
1337 
1338       Node* lrb_clone = lrb->clone();
1339       phase->register_new_node(lrb_clone, projs.catchall_catchproj);
1340       phase->set_ctrl(lrb, projs.fallthrough_catchproj);
1341 
1342       stack.push(lrb, 0);
1343       clones.push(lrb_clone);
1344 
1345       do {
1346         assert(stack.size() == clones.size(), "");
1347         Node* n = stack.node();
1348 #ifdef ASSERT
1349         if (n->is_Load()) {
1350           Node* mem = n->in(MemNode::Memory);
1351           for (DUIterator_Fast jmax, j = mem->fast_outs(jmax); j < jmax; j++) {
1352             Node* u = mem->fast_out(j);
1353             assert(!u->is_Store() || !u->is_LoadStore() || phase->get_ctrl(u) != ctrl, "anti dependent store?");
1354           }
1355         }
1356 #endif
1357         uint idx = stack.index();
1358         Node* n_clone = clones.at(clones.size()-1);
1359         if (idx < n->outcnt()) {
1360           Node* u = n->raw_out(idx);
1361           Node* c = phase->ctrl_or_self(u);
1362           if (phase->is_dominator(call, c) && phase->is_dominator(c, projs.fallthrough_proj)) {
1363             stack.set_index(idx+1);
1364             assert(!u->is_CFG(), "");
1365             stack.push(u, 0);
1366             Node* u_clone = u->clone();
1367             int nb = u_clone->replace_edge(n, n_clone);
1368             assert(nb > 0, "should have replaced some uses");
1369             phase->register_new_node(u_clone, projs.catchall_catchproj);
1370             clones.push(u_clone);
1371             phase->set_ctrl(u, projs.fallthrough_catchproj);
1372           } else {
1373             bool replaced = false;
1374             if (u->is_Phi()) {
1375               for (uint k = 1; k < u->req(); k++) {
1376                 if (u->in(k) == n) {
1377                   if (phase->is_dominator(projs.catchall_catchproj, u->in(0)->in(k))) {
1378                     phase->igvn().replace_input_of(u, k, n_clone);
1379                     replaced = true;
1380                   } else if (!phase->is_dominator(projs.fallthrough_catchproj, u->in(0)->in(k))) {
1381                     phase->igvn().replace_input_of(u, k, create_phis_on_call_return(ctrl, u->in(0)->in(k), n, n_clone, projs, phase));
1382                     replaced = true;
1383                   }
1384                 }
1385               }
1386             } else {
1387               if (phase->is_dominator(projs.catchall_catchproj, c)) {
1388                 phase->igvn().rehash_node_delayed(u);
1389                 int nb = u->replace_edge(n, n_clone);
1390                 assert(nb > 0, "should have replaced some uses");
1391                 replaced = true;
1392               } else if (!phase->is_dominator(projs.fallthrough_catchproj, c)) {
1393                 phase->igvn().rehash_node_delayed(u);
1394                 int nb = u->replace_edge(n, create_phis_on_call_return(ctrl, c, n, n_clone, projs, phase));
1395                 assert(nb > 0, "should have replaced some uses");
1396                 replaced = true;
1397               }
1398             }
1399             if (!replaced) {
1400               stack.set_index(idx+1);
1401             }
1402           }
1403         } else {
1404           stack.pop();
1405           clones.pop();
1406         }
1407       } while (stack.size() > 0);
1408       assert(stack.size() == 0 && clones.size() == 0, "");
1409     }
1410   }
1411 
1412   for (int i = 0; i < state->load_reference_barriers_count(); i++) {
1413     ShenandoahLoadReferenceBarrierNode* lrb = state->load_reference_barrier(i);
1414     if (lrb->get_barrier_strength() == ShenandoahLoadReferenceBarrierNode::NONE) {
1415       continue;
1416     }
1417     Node* ctrl = phase->get_ctrl(lrb);
1418     IdealLoopTree* loop = phase->get_loop(ctrl);
1419     if (loop->_head->is_OuterStripMinedLoop()) {
1420       // Expanding a barrier here will break loop strip mining
1421       // verification. Transform the loop so the loop nest doesn't
1422       // appear as strip mined.
1423       OuterStripMinedLoopNode* outer = loop->_head->as_OuterStripMinedLoop();
1424       hide_strip_mined_loop(outer, outer->unique_ctrl_out()->as_CountedLoop(), phase);
1425     }
1426   }
1427 
1428   // Expand load-reference-barriers
1429   MemoryGraphFixer fixer(Compile::AliasIdxRaw, true, phase);
1430   Unique_Node_List uses_to_ignore;
1431   for (int i = state->load_reference_barriers_count() - 1; i >= 0; i--) {
1432     ShenandoahLoadReferenceBarrierNode* lrb = state->load_reference_barrier(i);
1433     if (lrb->get_barrier_strength() == ShenandoahLoadReferenceBarrierNode::NONE) {
1434       phase->igvn().replace_node(lrb, lrb->in(ShenandoahLoadReferenceBarrierNode::ValueIn));
1435       continue;
1436     }
1437     uint last = phase->C->unique();
1438     Node* ctrl = phase->get_ctrl(lrb);
1439     Node* val = lrb->in(ShenandoahLoadReferenceBarrierNode::ValueIn);
1440 
1441 
1442     Node* orig_ctrl = ctrl;
1443 
1444     Node* raw_mem = fixer.find_mem(ctrl, lrb);
1445     Node* init_raw_mem = raw_mem;
1446     Node* raw_mem_for_ctrl = fixer.find_mem(ctrl, NULL);
1447 
1448     IdealLoopTree *loop = phase->get_loop(ctrl);
1449     CallStaticJavaNode* unc = lrb->pin_and_expand_null_check(phase->igvn());
1450     Node* unc_ctrl = NULL;
1451     if (unc != NULL) {
1452       if (val->in(ShenandoahLoadReferenceBarrierNode::Control) != ctrl) {
1453         unc = NULL;
1454       } else {
1455         unc_ctrl = val->in(ShenandoahLoadReferenceBarrierNode::Control);
1456       }
1457     }
1458 
1459     Node* uncasted_val = val;
1460     if (unc != NULL) {
1461       uncasted_val = val->in(1);
1462     }
1463 
1464     Node* heap_stable_ctrl = NULL;
1465     Node* null_ctrl = NULL;
1466 
1467     assert(val->bottom_type()->make_oopptr(), "need oop");
1468     assert(val->bottom_type()->make_oopptr()->const_oop() == NULL, "expect non-constant");
1469 
1470     enum { _heap_stable = 1, _not_cset, _fwded, _evac_path, _null_path, PATH_LIMIT };
1471     Node* region = new RegionNode(PATH_LIMIT);
1472     Node* val_phi = new PhiNode(region, uncasted_val->bottom_type()->is_oopptr());
1473     Node* raw_mem_phi = PhiNode::make(region, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
1474 
1475     // Stable path.
1476     test_heap_stable(ctrl, raw_mem, heap_stable_ctrl, phase);
1477     IfNode* heap_stable_iff = heap_stable_ctrl->in(0)->as_If();
1478 
1479     // Heap stable case
1480     region->init_req(_heap_stable, heap_stable_ctrl);
1481     val_phi->init_req(_heap_stable, uncasted_val);
1482     raw_mem_phi->init_req(_heap_stable, raw_mem);
1483 
1484     Node* reg2_ctrl = NULL;
1485     // Null case
1486     test_null(ctrl, val, null_ctrl, phase);
1487     if (null_ctrl != NULL) {
1488       reg2_ctrl = null_ctrl->in(0);
1489       region->init_req(_null_path, null_ctrl);
1490       val_phi->init_req(_null_path, uncasted_val);
1491       raw_mem_phi->init_req(_null_path, raw_mem);
1492     } else {
1493       region->del_req(_null_path);
1494       val_phi->del_req(_null_path);
1495       raw_mem_phi->del_req(_null_path);
1496     }
1497 
1498     // Test for in-cset.
1499     // Wires !in_cset(obj) to slot 2 of region and phis
1500     Node* not_cset_ctrl = NULL;
1501     in_cset_fast_test(ctrl, not_cset_ctrl, uncasted_val, raw_mem, phase);
1502     if (not_cset_ctrl != NULL) {
1503       if (reg2_ctrl == NULL) reg2_ctrl = not_cset_ctrl->in(0);
1504       region->init_req(_not_cset, not_cset_ctrl);
1505       val_phi->init_req(_not_cset, uncasted_val);
1506       raw_mem_phi->init_req(_not_cset, raw_mem);
1507     }
1508 
1509     // Resolve object when orig-value is in cset.
1510     // Make the unconditional resolve for fwdptr.
1511     Node* new_val = uncasted_val;
1512     if (unc_ctrl != NULL) {
1513       // Clone the null check in this branch to allow implicit null check
1514       new_val = clone_null_check(ctrl, val, unc_ctrl, phase);
1515       fix_null_check(unc, unc_ctrl, ctrl->in(0)->as_If()->proj_out(0), uses, phase);
1516 
1517       IfNode* iff = unc_ctrl->in(0)->as_If();
1518       phase->igvn().replace_input_of(iff, 1, phase->igvn().intcon(1));
1519     }
1520     Node* addr = new AddPNode(new_val, uncasted_val, phase->igvn().MakeConX(oopDesc::mark_offset_in_bytes()));
1521     phase->register_new_node(addr, ctrl);
1522     assert(new_val->bottom_type()->isa_oopptr(), "what else?");
1523     Node* markword = new LoadXNode(ctrl, raw_mem, addr, TypeRawPtr::BOTTOM, TypeX_X, MemNode::unordered);
1524     phase->register_new_node(markword, ctrl);
1525 
1526     // Test if object is forwarded. This is the case if lowest two bits are set.
1527     Node* masked = new AndXNode(markword, phase->igvn().MakeConX(markOopDesc::lock_mask_in_place));
1528     phase->register_new_node(masked, ctrl);
1529     Node* cmp = new CmpXNode(masked, phase->igvn().MakeConX(markOopDesc::marked_value));
1530     phase->register_new_node(cmp, ctrl);
1531 
1532     // Only branch to LRB stub if object is not forwarded; otherwise reply with fwd ptr
1533     Node* bol = new BoolNode(cmp, BoolTest::eq); // Equals 3 means it's forwarded
1534     phase->register_new_node(bol, ctrl);
1535 
1536     IfNode* iff = new IfNode(ctrl, bol, PROB_LIKELY(0.999), COUNT_UNKNOWN);
1537     phase->register_control(iff, loop, ctrl);
1538     Node* if_fwd = new IfTrueNode(iff);
1539     phase->register_control(if_fwd, loop, iff);
1540     Node* if_not_fwd = new IfFalseNode(iff);
1541     phase->register_control(if_not_fwd, loop, iff);
1542 
1543     // Decode forward pointer: since we already have the lowest bits, we can just subtract them
1544     // from the mark word without the need for large immediate mask.
1545     Node* masked2 = new SubXNode(markword, masked);
1546     phase->register_new_node(masked2, if_fwd);
1547     Node* fwdraw = new CastX2PNode(masked2);
1548     fwdraw->init_req(0, if_fwd);
1549     phase->register_new_node(fwdraw, if_fwd);
1550     Node* fwd = new CheckCastPPNode(NULL, fwdraw, val->bottom_type());
1551     phase->register_new_node(fwd, if_fwd);
1552 
1553     // Wire up not-equal-path in slots 3.
1554     region->init_req(_fwded, if_fwd);
1555     val_phi->init_req(_fwded, fwd);
1556     raw_mem_phi->init_req(_fwded, raw_mem);
1557 
1558     // Call lrb-stub and wire up that path in slots 4
1559     Node* result_mem = NULL;
1560     ctrl = if_not_fwd;
1561     fwd = new_val;
1562     call_lrb_stub(ctrl, fwd, result_mem, raw_mem, phase);
1563     region->init_req(_evac_path, ctrl);
1564     val_phi->init_req(_evac_path, fwd);
1565     raw_mem_phi->init_req(_evac_path, result_mem);
1566 
1567     phase->register_control(region, loop, heap_stable_iff);
1568     Node* out_val = val_phi;
1569     phase->register_new_node(val_phi, region);
1570     phase->register_new_node(raw_mem_phi, region);
1571 
1572     fix_ctrl(lrb, region, fixer, uses, uses_to_ignore, last, phase);
1573 
1574     ctrl = orig_ctrl;
1575 
1576     if (unc != NULL) {
1577       for (DUIterator_Fast imax, i = val->fast_outs(imax); i < imax; i++) {
1578         Node* u = val->fast_out(i);
1579         Node* c = phase->ctrl_or_self(u);
1580         if (u != lrb && (c != ctrl || is_dominator_same_ctrl(c, lrb, u, phase))) {
1581           phase->igvn().rehash_node_delayed(u);
1582           int nb = u->replace_edge(val, out_val);
1583           --i, imax -= nb;
1584         }
1585       }
1586       if (val->outcnt() == 0) {
1587         phase->igvn()._worklist.push(val);
1588       }
1589     }
1590     phase->igvn().replace_node(lrb, out_val);
1591 
1592     follow_barrier_uses(out_val, ctrl, uses, phase);
1593 
1594     for(uint next = 0; next < uses.size(); next++ ) {
1595       Node *n = uses.at(next);
1596       assert(phase->get_ctrl(n) == ctrl, "bad control");
1597       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
1598       phase->set_ctrl(n, region);
1599       follow_barrier_uses(n, ctrl, uses, phase);
1600     }
1601 
1602     // The slow path call produces memory: hook the raw memory phi
1603     // from the expanded load reference barrier with the rest of the graph
1604     // which may require adding memory phis at every post dominated
1605     // region and at enclosing loop heads. Use the memory state
1606     // collected in memory_nodes to fix the memory graph. Update that
1607     // memory state as we go.
1608     fixer.fix_mem(ctrl, region, init_raw_mem, raw_mem_for_ctrl, raw_mem_phi, uses);
1609   }
1610   // Done expanding load-reference-barriers.
1611   assert(ShenandoahBarrierSetC2::bsc2()->state()->load_reference_barriers_count() == 0, "all load reference barrier nodes should have been replaced");
1612 
1613   for (int i = state->enqueue_barriers_count() - 1; i >= 0; i--) {
1614     Node* barrier = state->enqueue_barrier(i);
1615     Node* pre_val = barrier->in(1);
1616 
1617     if (phase->igvn().type(pre_val)->higher_equal(TypePtr::NULL_PTR)) {
1618       ShouldNotReachHere();
1619       continue;
1620     }
1621 
1622     Node* ctrl = phase->get_ctrl(barrier);
1623 
1624     if (ctrl->is_Proj() && ctrl->in(0)->is_CallJava()) {
1625       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0)->in(0), pre_val, ctrl->in(0), phase), "can't move");
1626       ctrl = ctrl->in(0)->in(0);
1627       phase->set_ctrl(barrier, ctrl);
1628     } else if (ctrl->is_CallRuntime()) {
1629       assert(is_dominator(phase->get_ctrl(pre_val), ctrl->in(0), pre_val, ctrl, phase), "can't move");
1630       ctrl = ctrl->in(0);
1631       phase->set_ctrl(barrier, ctrl);
1632     }
1633 
1634     Node* init_ctrl = ctrl;
1635     IdealLoopTree* loop = phase->get_loop(ctrl);
1636     Node* raw_mem = fixer.find_mem(ctrl, barrier);
1637     Node* init_raw_mem = raw_mem;
1638     Node* raw_mem_for_ctrl = fixer.find_mem(ctrl, NULL);
1639     Node* heap_stable_ctrl = NULL;
1640     Node* null_ctrl = NULL;
1641     uint last = phase->C->unique();
1642 
1643     enum { _heap_stable = 1, _heap_unstable, PATH_LIMIT };
1644     Node* region = new RegionNode(PATH_LIMIT);
1645     Node* phi = PhiNode::make(region, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
1646 
1647     enum { _fast_path = 1, _slow_path, _null_path, PATH_LIMIT2 };
1648     Node* region2 = new RegionNode(PATH_LIMIT2);
1649     Node* phi2 = PhiNode::make(region2, raw_mem, Type::MEMORY, TypeRawPtr::BOTTOM);
1650 
1651     // Stable path.
1652     test_heap_stable(ctrl, raw_mem, heap_stable_ctrl, phase);
1653     region->init_req(_heap_stable, heap_stable_ctrl);
1654     phi->init_req(_heap_stable, raw_mem);
1655 
1656     // Null path
1657     Node* reg2_ctrl = NULL;
1658     test_null(ctrl, pre_val, null_ctrl, phase);
1659     if (null_ctrl != NULL) {
1660       reg2_ctrl = null_ctrl->in(0);
1661       region2->init_req(_null_path, null_ctrl);
1662       phi2->init_req(_null_path, raw_mem);
1663     } else {
1664       region2->del_req(_null_path);
1665       phi2->del_req(_null_path);
1666     }
1667 
1668     const int index_offset = in_bytes(ShenandoahThreadLocalData::satb_mark_queue_index_offset());
1669     const int buffer_offset = in_bytes(ShenandoahThreadLocalData::satb_mark_queue_buffer_offset());
1670     Node* thread = new ThreadLocalNode();
1671     phase->register_new_node(thread, ctrl);
1672     Node* buffer_adr = new AddPNode(phase->C->top(), thread, phase->igvn().MakeConX(buffer_offset));
1673     phase->register_new_node(buffer_adr, ctrl);
1674     Node* index_adr = new AddPNode(phase->C->top(), thread, phase->igvn().MakeConX(index_offset));
1675     phase->register_new_node(index_adr, ctrl);
1676 
1677     BasicType index_bt = TypeX_X->basic_type();
1678     assert(sizeof(size_t) == type2aelembytes(index_bt), "Loading G1 SATBMarkQueue::_index with wrong size.");
1679     const TypePtr* adr_type = TypeRawPtr::BOTTOM;
1680     Node* index = new LoadXNode(ctrl, raw_mem, index_adr, adr_type, TypeX_X, MemNode::unordered);
1681     phase->register_new_node(index, ctrl);
1682     Node* index_cmp = new CmpXNode(index, phase->igvn().MakeConX(0));
1683     phase->register_new_node(index_cmp, ctrl);
1684     Node* index_test = new BoolNode(index_cmp, BoolTest::ne);
1685     phase->register_new_node(index_test, ctrl);
1686     IfNode* queue_full_iff = new IfNode(ctrl, index_test, PROB_LIKELY(0.999), COUNT_UNKNOWN);
1687     if (reg2_ctrl == NULL) reg2_ctrl = queue_full_iff;
1688     phase->register_control(queue_full_iff, loop, ctrl);
1689     Node* not_full = new IfTrueNode(queue_full_iff);
1690     phase->register_control(not_full, loop, queue_full_iff);
1691     Node* full = new IfFalseNode(queue_full_iff);
1692     phase->register_control(full, loop, queue_full_iff);
1693 
1694     ctrl = not_full;
1695 
1696     Node* next_index = new SubXNode(index, phase->igvn().MakeConX(sizeof(intptr_t)));
1697     phase->register_new_node(next_index, ctrl);
1698 
1699     Node* buffer  = new LoadPNode(ctrl, raw_mem, buffer_adr, adr_type, TypeRawPtr::NOTNULL, MemNode::unordered);
1700     phase->register_new_node(buffer, ctrl);
1701     Node *log_addr = new AddPNode(phase->C->top(), buffer, next_index);
1702     phase->register_new_node(log_addr, ctrl);
1703     Node* log_store = new StorePNode(ctrl, raw_mem, log_addr, adr_type, pre_val, MemNode::unordered);
1704     phase->register_new_node(log_store, ctrl);
1705     // update the index
1706     Node* index_update = new StoreXNode(ctrl, log_store, index_adr, adr_type, next_index, MemNode::unordered);
1707     phase->register_new_node(index_update, ctrl);
1708 
1709     // Fast-path case
1710     region2->init_req(_fast_path, ctrl);
1711     phi2->init_req(_fast_path, index_update);
1712 
1713     ctrl = full;
1714 
1715     Node* base = find_bottom_mem(ctrl, phase);
1716 
1717     MergeMemNode* mm = MergeMemNode::make(base);
1718     mm->set_memory_at(Compile::AliasIdxRaw, raw_mem);
1719     phase->register_new_node(mm, ctrl);
1720 
1721     Node* call = new CallLeafNode(ShenandoahBarrierSetC2::write_ref_field_pre_entry_Type(), CAST_FROM_FN_PTR(address, ShenandoahRuntime::write_ref_field_pre_entry), "shenandoah_wb_pre", TypeRawPtr::BOTTOM);
1722     call->init_req(TypeFunc::Control, ctrl);
1723     call->init_req(TypeFunc::I_O, phase->C->top());
1724     call->init_req(TypeFunc::Memory, mm);
1725     call->init_req(TypeFunc::FramePtr, phase->C->top());
1726     call->init_req(TypeFunc::ReturnAdr, phase->C->top());
1727     call->init_req(TypeFunc::Parms, pre_val);
1728     call->init_req(TypeFunc::Parms+1, thread);
1729     phase->register_control(call, loop, ctrl);
1730 
1731     Node* ctrl_proj = new ProjNode(call, TypeFunc::Control);
1732     phase->register_control(ctrl_proj, loop, call);
1733     Node* mem_proj = new ProjNode(call, TypeFunc::Memory);
1734     phase->register_new_node(mem_proj, call);
1735 
1736     // Slow-path case
1737     region2->init_req(_slow_path, ctrl_proj);
1738     phi2->init_req(_slow_path, mem_proj);
1739 
1740     phase->register_control(region2, loop, reg2_ctrl);
1741     phase->register_new_node(phi2, region2);
1742 
1743     region->init_req(_heap_unstable, region2);
1744     phi->init_req(_heap_unstable, phi2);
1745 
1746     phase->register_control(region, loop, heap_stable_ctrl->in(0));
1747     phase->register_new_node(phi, region);
1748 
1749     fix_ctrl(barrier, region, fixer, uses, uses_to_ignore, last, phase);
1750     for(uint next = 0; next < uses.size(); next++ ) {
1751       Node *n = uses.at(next);
1752       assert(phase->get_ctrl(n) == init_ctrl, "bad control");
1753       assert(n != init_raw_mem, "should leave input raw mem above the barrier");
1754       phase->set_ctrl(n, region);
1755       follow_barrier_uses(n, init_ctrl, uses, phase);
1756     }
1757     fixer.fix_mem(init_ctrl, region, init_raw_mem, raw_mem_for_ctrl, phi, uses);
1758 
1759     phase->igvn().replace_node(barrier, pre_val);
1760   }
1761   assert(state->enqueue_barriers_count() == 0, "all enqueue barrier nodes should have been replaced");
1762 
1763 }
1764 
1765 void ShenandoahBarrierC2Support::move_heap_stable_test_out_of_loop(IfNode* iff, PhaseIdealLoop* phase) {
1766   IdealLoopTree *loop = phase->get_loop(iff);
1767   Node* loop_head = loop->_head;
1768   Node* entry_c = loop_head->in(LoopNode::EntryControl);
1769 
1770   Node* bol = iff->in(1);
1771   Node* cmp = bol->in(1);
1772   Node* andi = cmp->in(1);
1773   Node* load = andi->in(1);
1774 
1775   assert(is_gc_state_load(load), "broken");
1776   if (!phase->is_dominator(load->in(0), entry_c)) {
1777     Node* mem_ctrl = NULL;
1778     Node* mem = dom_mem(load->in(MemNode::Memory), loop_head, Compile::AliasIdxRaw, mem_ctrl, phase);
1779     load = load->clone();
1780     load->set_req(MemNode::Memory, mem);
1781     load->set_req(0, entry_c);
1782     phase->register_new_node(load, entry_c);
1783     andi = andi->clone();
1784     andi->set_req(1, load);
1785     phase->register_new_node(andi, entry_c);
1786     cmp = cmp->clone();
1787     cmp->set_req(1, andi);
1788     phase->register_new_node(cmp, entry_c);
1789     bol = bol->clone();
1790     bol->set_req(1, cmp);
1791     phase->register_new_node(bol, entry_c);
1792 
1793     Node* old_bol =iff->in(1);
1794     phase->igvn().replace_input_of(iff, 1, bol);
1795   }
1796 }
1797 
1798 bool ShenandoahBarrierC2Support::identical_backtoback_ifs(Node* n, PhaseIdealLoop* phase) {
1799   if (!n->is_If() || n->is_CountedLoopEnd()) {
1800     return false;
1801   }
1802   Node* region = n->in(0);
1803 
1804   if (!region->is_Region()) {
1805     return false;
1806   }
1807   Node* dom = phase->idom(region);
1808   if (!dom->is_If()) {
1809     return false;
1810   }
1811 
1812   if (!is_heap_stable_test(n) || !is_heap_stable_test(dom)) {
1813     return false;
1814   }
1815 
1816   IfNode* dom_if = dom->as_If();
1817   Node* proj_true = dom_if->proj_out(1);
1818   Node* proj_false = dom_if->proj_out(0);
1819 
1820   for (uint i = 1; i < region->req(); i++) {
1821     if (phase->is_dominator(proj_true, region->in(i))) {
1822       continue;
1823     }
1824     if (phase->is_dominator(proj_false, region->in(i))) {
1825       continue;
1826     }
1827     return false;
1828   }
1829 
1830   return true;
1831 }
1832 
1833 void ShenandoahBarrierC2Support::merge_back_to_back_tests(Node* n, PhaseIdealLoop* phase) {
1834   assert(is_heap_stable_test(n), "no other tests");
1835   if (identical_backtoback_ifs(n, phase)) {
1836     Node* n_ctrl = n->in(0);
1837     if (phase->can_split_if(n_ctrl)) {
1838       IfNode* dom_if = phase->idom(n_ctrl)->as_If();
1839       if (is_heap_stable_test(n)) {
1840         Node* gc_state_load = n->in(1)->in(1)->in(1)->in(1);
1841         assert(is_gc_state_load(gc_state_load), "broken");
1842         Node* dom_gc_state_load = dom_if->in(1)->in(1)->in(1)->in(1);
1843         assert(is_gc_state_load(dom_gc_state_load), "broken");
1844         if (gc_state_load != dom_gc_state_load) {
1845           phase->igvn().replace_node(gc_state_load, dom_gc_state_load);
1846         }
1847       }
1848       PhiNode* bolphi = PhiNode::make_blank(n_ctrl, n->in(1));
1849       Node* proj_true = dom_if->proj_out(1);
1850       Node* proj_false = dom_if->proj_out(0);
1851       Node* con_true = phase->igvn().makecon(TypeInt::ONE);
1852       Node* con_false = phase->igvn().makecon(TypeInt::ZERO);
1853 
1854       for (uint i = 1; i < n_ctrl->req(); i++) {
1855         if (phase->is_dominator(proj_true, n_ctrl->in(i))) {
1856           bolphi->init_req(i, con_true);
1857         } else {
1858           assert(phase->is_dominator(proj_false, n_ctrl->in(i)), "bad if");
1859           bolphi->init_req(i, con_false);
1860         }
1861       }
1862       phase->register_new_node(bolphi, n_ctrl);
1863       phase->igvn().replace_input_of(n, 1, bolphi);
1864       phase->do_split_if(n);
1865     }
1866   }
1867 }
1868 
1869 IfNode* ShenandoahBarrierC2Support::find_unswitching_candidate(const IdealLoopTree* loop, PhaseIdealLoop* phase) {
1870   // Find first invariant test that doesn't exit the loop
1871   LoopNode *head = loop->_head->as_Loop();
1872   IfNode* unswitch_iff = NULL;
1873   Node* n = head->in(LoopNode::LoopBackControl);
1874   int loop_has_sfpts = -1;
1875   while (n != head) {
1876     Node* n_dom = phase->idom(n);
1877     if (n->is_Region()) {
1878       if (n_dom->is_If()) {
1879         IfNode* iff = n_dom->as_If();
1880         if (iff->in(1)->is_Bool()) {
1881           BoolNode* bol = iff->in(1)->as_Bool();
1882           if (bol->in(1)->is_Cmp()) {
1883             // If condition is invariant and not a loop exit,
1884             // then found reason to unswitch.
1885             if (is_heap_stable_test(iff) &&
1886                 (loop_has_sfpts == -1 || loop_has_sfpts == 0)) {
1887               assert(!loop->is_loop_exit(iff), "both branches should be in the loop");
1888               if (loop_has_sfpts == -1) {
1889                 for(uint i = 0; i < loop->_body.size(); i++) {
1890                   Node *m = loop->_body[i];
1891                   if (m->is_SafePoint() && !m->is_CallLeaf()) {
1892                     loop_has_sfpts = 1;
1893                     break;
1894                   }
1895                 }
1896                 if (loop_has_sfpts == -1) {
1897                   loop_has_sfpts = 0;
1898                 }
1899               }
1900               if (!loop_has_sfpts) {
1901                 unswitch_iff = iff;
1902               }
1903             }
1904           }
1905         }
1906       }
1907     }
1908     n = n_dom;
1909   }
1910   return unswitch_iff;
1911 }
1912 
1913 
1914 void ShenandoahBarrierC2Support::optimize_after_expansion(VectorSet &visited, Node_Stack &stack, Node_List &old_new, PhaseIdealLoop* phase) {
1915   Node_List heap_stable_tests;
1916   Node_List gc_state_loads;
1917   stack.push(phase->C->start(), 0);
1918   do {
1919     Node* n = stack.node();
1920     uint i = stack.index();
1921 
1922     if (i < n->outcnt()) {
1923       Node* u = n->raw_out(i);
1924       stack.set_index(i+1);
1925       if (!visited.test_set(u->_idx)) {
1926         stack.push(u, 0);
1927       }
1928     } else {
1929       stack.pop();
1930       if (ShenandoahCommonGCStateLoads && is_gc_state_load(n)) {
1931         gc_state_loads.push(n);
1932       }
1933       if (n->is_If() && is_heap_stable_test(n)) {
1934         heap_stable_tests.push(n);
1935       }
1936     }
1937   } while (stack.size() > 0);
1938 
1939   bool progress;
1940   do {
1941     progress = false;
1942     for (uint i = 0; i < gc_state_loads.size(); i++) {
1943       Node* n = gc_state_loads.at(i);
1944       if (n->outcnt() != 0) {
1945         progress |= try_common_gc_state_load(n, phase);
1946       }
1947     }
1948   } while (progress);
1949 
1950   for (uint i = 0; i < heap_stable_tests.size(); i++) {
1951     Node* n = heap_stable_tests.at(i);
1952     assert(is_heap_stable_test(n), "only evacuation test");
1953     merge_back_to_back_tests(n, phase);
1954   }
1955 
1956   if (!phase->C->major_progress()) {
1957     VectorSet seen(Thread::current()->resource_area());
1958     for (uint i = 0; i < heap_stable_tests.size(); i++) {
1959       Node* n = heap_stable_tests.at(i);
1960       IdealLoopTree* loop = phase->get_loop(n);
1961       if (loop != phase->ltree_root() &&
1962           loop->_child == NULL &&
1963           !loop->_irreducible) {
1964         LoopNode* head = loop->_head->as_Loop();
1965         if ((!head->is_CountedLoop() || head->as_CountedLoop()->is_main_loop() || head->as_CountedLoop()->is_normal_loop()) &&
1966             !seen.test_set(head->_idx)) {
1967           IfNode* iff = find_unswitching_candidate(loop, phase);
1968           if (iff != NULL) {
1969             Node* bol = iff->in(1);
1970             if (head->is_strip_mined()) {
1971               head->verify_strip_mined(0);
1972             }
1973             move_heap_stable_test_out_of_loop(iff, phase);
1974 
1975             AutoNodeBudget node_budget(phase);
1976 
1977             if (loop->policy_unswitching(phase)) {
1978               if (head->is_strip_mined()) {
1979                 OuterStripMinedLoopNode* outer = head->as_CountedLoop()->outer_loop();
1980                 hide_strip_mined_loop(outer, head->as_CountedLoop(), phase);
1981               }
1982               phase->do_unswitching(loop, old_new);
1983             } else {
1984               // Not proceeding with unswitching. Move load back in
1985               // the loop.
1986               phase->igvn().replace_input_of(iff, 1, bol);
1987             }
1988           }
1989         }
1990       }
1991     }
1992   }
1993 }
1994 
1995 #ifdef ASSERT
1996 void ShenandoahBarrierC2Support::verify_raw_mem(RootNode* root) {
1997   const bool trace = false;
1998   ResourceMark rm;
1999   Unique_Node_List nodes;
2000   Unique_Node_List controls;
2001   Unique_Node_List memories;
2002 
2003   nodes.push(root);
2004   for (uint next = 0; next < nodes.size(); next++) {
2005     Node *n  = nodes.at(next);
2006     if (ShenandoahBarrierSetC2::is_shenandoah_lrb_call(n)) {
2007       controls.push(n);
2008       if (trace) { tty->print("XXXXXX verifying"); n->dump(); }
2009       for (uint next2 = 0; next2 < controls.size(); next2++) {
2010         Node *m = controls.at(next2);
2011         for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
2012           Node* u = m->fast_out(i);
2013           if (u->is_CFG() && !u->is_Root() &&
2014               !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1) &&
2015               !(u->is_Region() && u->unique_ctrl_out()->Opcode() == Op_Halt)) {
2016             if (trace) { tty->print("XXXXXX pushing control"); u->dump(); }
2017             controls.push(u);
2018           }
2019         }
2020       }
2021       memories.push(n->as_Call()->proj_out(TypeFunc::Memory));
2022       for (uint next2 = 0; next2 < memories.size(); next2++) {
2023         Node *m = memories.at(next2);
2024         assert(m->bottom_type() == Type::MEMORY, "");
2025         for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
2026           Node* u = m->fast_out(i);
2027           if (u->bottom_type() == Type::MEMORY && (u->is_Mem() || u->is_ClearArray())) {
2028             if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
2029             memories.push(u);
2030           } else if (u->is_LoadStore()) {
2031             if (trace) { tty->print("XXXXXX pushing memory"); u->find_out_with(Op_SCMemProj)->dump(); }
2032             memories.push(u->find_out_with(Op_SCMemProj));
2033           } else if (u->is_MergeMem() && u->as_MergeMem()->memory_at(Compile::AliasIdxRaw) == m) {
2034             if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
2035             memories.push(u);
2036           } else if (u->is_Phi()) {
2037             assert(u->bottom_type() == Type::MEMORY, "");
2038             if (u->adr_type() == TypeRawPtr::BOTTOM || u->adr_type() == TypePtr::BOTTOM) {
2039               assert(controls.member(u->in(0)), "");
2040               if (trace) { tty->print("XXXXXX pushing memory"); u->dump(); }
2041               memories.push(u);
2042             }
2043           } else if (u->is_SafePoint() || u->is_MemBar()) {
2044             for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
2045               Node* uu = u->fast_out(j);
2046               if (uu->bottom_type() == Type::MEMORY) {
2047                 if (trace) { tty->print("XXXXXX pushing memory"); uu->dump(); }
2048                 memories.push(uu);
2049               }
2050             }
2051           }
2052         }
2053       }
2054       for (uint next2 = 0; next2 < controls.size(); next2++) {
2055         Node *m = controls.at(next2);
2056         if (m->is_Region()) {
2057           bool all_in = true;
2058           for (uint i = 1; i < m->req(); i++) {
2059             if (!controls.member(m->in(i))) {
2060               all_in = false;
2061               break;
2062             }
2063           }
2064           if (trace) { tty->print("XXX verifying %s", all_in ? "all in" : ""); m->dump(); }
2065           bool found_phi = false;
2066           for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax && !found_phi; j++) {
2067             Node* u = m->fast_out(j);
2068             if (u->is_Phi() && memories.member(u)) {
2069               found_phi = true;
2070               for (uint i = 1; i < u->req() && found_phi; i++) {
2071                 Node* k = u->in(i);
2072                 if (memories.member(k) != controls.member(m->in(i))) {
2073                   found_phi = false;
2074                 }
2075               }
2076             }
2077           }
2078           assert(found_phi || all_in, "");
2079         }
2080       }
2081       controls.clear();
2082       memories.clear();
2083     }
2084     for( uint i = 0; i < n->len(); ++i ) {
2085       Node *m = n->in(i);
2086       if (m != NULL) {
2087         nodes.push(m);
2088       }
2089     }
2090   }
2091 }
2092 #endif
2093 
2094 ShenandoahEnqueueBarrierNode::ShenandoahEnqueueBarrierNode(Node* val) : Node(NULL, val) {
2095   ShenandoahBarrierSetC2::bsc2()->state()->add_enqueue_barrier(this);
2096 }
2097 
2098 const Type* ShenandoahEnqueueBarrierNode::bottom_type() const {
2099   if (in(1) == NULL || in(1)->is_top()) {
2100     return Type::TOP;
2101   }
2102   const Type* t = in(1)->bottom_type();
2103   if (t == TypePtr::NULL_PTR) {
2104     return t;
2105   }
2106   return t->is_oopptr()->cast_to_nonconst();
2107 }
2108 
2109 const Type* ShenandoahEnqueueBarrierNode::Value(PhaseGVN* phase) const {
2110   if (in(1) == NULL) {
2111     return Type::TOP;
2112   }
2113   const Type* t = phase->type(in(1));
2114   if (t == Type::TOP) {
2115     return Type::TOP;
2116   }
2117   if (t == TypePtr::NULL_PTR) {
2118     return t;
2119   }
2120   return t->is_oopptr()->cast_to_nonconst();
2121 }
2122 
2123 int ShenandoahEnqueueBarrierNode::needed(Node* n) {
2124   if (n == NULL ||
2125       n->is_Allocate() ||
2126       n->Opcode() == Op_ShenandoahEnqueueBarrier ||
2127       n->bottom_type() == TypePtr::NULL_PTR ||
2128       (n->bottom_type()->make_oopptr() != NULL && n->bottom_type()->make_oopptr()->const_oop() != NULL)) {
2129     return NotNeeded;
2130   }
2131   if (n->is_Phi() ||
2132       n->is_CMove()) {
2133     return MaybeNeeded;
2134   }
2135   return Needed;
2136 }
2137 
2138 Node* ShenandoahEnqueueBarrierNode::next(Node* n) {
2139   for (;;) {
2140     if (n == NULL) {
2141       return n;
2142     } else if (n->bottom_type() == TypePtr::NULL_PTR) {
2143       return n;
2144     } else if (n->bottom_type()->make_oopptr() != NULL && n->bottom_type()->make_oopptr()->const_oop() != NULL) {
2145       return n;
2146     } else if (n->is_ConstraintCast() ||
2147                n->Opcode() == Op_DecodeN ||
2148                n->Opcode() == Op_EncodeP) {
2149       n = n->in(1);
2150     } else if (n->is_Proj()) {
2151       n = n->in(0);
2152     } else {
2153       return n;
2154     }
2155   }
2156   ShouldNotReachHere();
2157   return NULL;
2158 }
2159 
2160 Node* ShenandoahEnqueueBarrierNode::Identity(PhaseGVN* phase) {
2161   PhaseIterGVN* igvn = phase->is_IterGVN();
2162 
2163   Node* n = next(in(1));
2164 
2165   int cont = needed(n);
2166 
2167   if (cont == NotNeeded) {
2168     return in(1);
2169   } else if (cont == MaybeNeeded) {
2170     if (igvn == NULL) {
2171       phase->record_for_igvn(this);
2172       return this;
2173     } else {
2174       ResourceMark rm;
2175       Unique_Node_List wq;
2176       uint wq_i = 0;
2177 
2178       for (;;) {
2179         if (n->is_Phi()) {
2180           for (uint i = 1; i < n->req(); i++) {
2181             Node* m = n->in(i);
2182             if (m != NULL) {
2183               wq.push(m);
2184             }
2185           }
2186         } else {
2187           assert(n->is_CMove(), "nothing else here");
2188           Node* m = n->in(CMoveNode::IfFalse);
2189           wq.push(m);
2190           m = n->in(CMoveNode::IfTrue);
2191           wq.push(m);
2192         }
2193         Node* orig_n = NULL;
2194         do {
2195           if (wq_i >= wq.size()) {
2196             return in(1);
2197           }
2198           n = wq.at(wq_i);
2199           wq_i++;
2200           orig_n = n;
2201           n = next(n);
2202           cont = needed(n);
2203           if (cont == Needed) {
2204             return this;
2205           }
2206         } while (cont != MaybeNeeded || (orig_n != n && wq.member(n)));
2207       }
2208     }
2209   }
2210 
2211   return this;
2212 }
2213 
2214 #ifdef ASSERT
2215 static bool has_never_branch(Node* root) {
2216   for (uint i = 1; i < root->req(); i++) {
2217     Node* in = root->in(i);
2218     if (in != NULL && in->Opcode() == Op_Halt && in->in(0)->is_Proj() && in->in(0)->in(0)->Opcode() == Op_NeverBranch) {
2219       return true;
2220     }
2221   }
2222   return false;
2223 }
2224 #endif
2225 
2226 void MemoryGraphFixer::collect_memory_nodes() {
2227   Node_Stack stack(0);
2228   VectorSet visited(Thread::current()->resource_area());
2229   Node_List regions;
2230 
2231   // Walk the raw memory graph and create a mapping from CFG node to
2232   // memory node. Exclude phis for now.
2233   stack.push(_phase->C->root(), 1);
2234   do {
2235     Node* n = stack.node();
2236     int opc = n->Opcode();
2237     uint i = stack.index();
2238     if (i < n->req()) {
2239       Node* mem = NULL;
2240       if (opc == Op_Root) {
2241         Node* in = n->in(i);
2242         int in_opc = in->Opcode();
2243         if (in_opc == Op_Return || in_opc == Op_Rethrow) {
2244           mem = in->in(TypeFunc::Memory);
2245         } else if (in_opc == Op_Halt) {
2246           if (!in->in(0)->is_Region()) {
2247             Node* proj = in->in(0);
2248             assert(proj->is_Proj(), "");
2249             Node* in = proj->in(0);
2250             assert(in->is_CallStaticJava() || in->Opcode() == Op_NeverBranch || in->Opcode() == Op_Catch || proj->is_IfProj(), "");
2251             if (in->is_CallStaticJava()) {
2252               mem = in->in(TypeFunc::Memory);
2253             } else if (in->Opcode() == Op_Catch) {
2254               Node* call = in->in(0)->in(0);
2255               assert(call->is_Call(), "");
2256               mem = call->in(TypeFunc::Memory);
2257             } else if (in->Opcode() == Op_NeverBranch) {
2258               ResourceMark rm;
2259               Unique_Node_List wq;
2260               wq.push(in);
2261               wq.push(in->as_Multi()->proj_out(0));
2262               for (uint j = 1; j < wq.size(); j++) {
2263                 Node* c = wq.at(j);
2264                 assert(!c->is_Root(), "shouldn't leave loop");
2265                 if (c->is_SafePoint()) {
2266                   assert(mem == NULL, "only one safepoint");
2267                   mem = c->in(TypeFunc::Memory);
2268                 }
2269                 for (DUIterator_Fast kmax, k = c->fast_outs(kmax); k < kmax; k++) {
2270                   Node* u = c->fast_out(k);
2271                   if (u->is_CFG()) {
2272                     wq.push(u);
2273                   }
2274                 }
2275               }
2276               assert(mem != NULL, "should have found safepoint");
2277             }
2278           }
2279         } else {
2280 #ifdef ASSERT
2281           n->dump();
2282           in->dump();
2283 #endif
2284           ShouldNotReachHere();
2285         }
2286       } else {
2287         assert(n->is_Phi() && n->bottom_type() == Type::MEMORY, "");
2288         assert(n->adr_type() == TypePtr::BOTTOM || _phase->C->get_alias_index(n->adr_type()) == _alias, "");
2289         mem = n->in(i);
2290       }
2291       i++;
2292       stack.set_index(i);
2293       if (mem == NULL) {
2294         continue;
2295       }
2296       for (;;) {
2297         if (visited.test_set(mem->_idx) || mem->is_Start()) {
2298           break;
2299         }
2300         if (mem->is_Phi()) {
2301           stack.push(mem, 2);
2302           mem = mem->in(1);
2303         } else if (mem->is_Proj()) {
2304           stack.push(mem, mem->req());
2305           mem = mem->in(0);
2306         } else if (mem->is_SafePoint() || mem->is_MemBar()) {
2307           mem = mem->in(TypeFunc::Memory);
2308         } else if (mem->is_MergeMem()) {
2309           MergeMemNode* mm = mem->as_MergeMem();
2310           mem = mm->memory_at(_alias);
2311         } else if (mem->is_Store() || mem->is_LoadStore() || mem->is_ClearArray()) {
2312           assert(_alias == Compile::AliasIdxRaw, "");
2313           stack.push(mem, mem->req());
2314           mem = mem->in(MemNode::Memory);
2315         } else {
2316 #ifdef ASSERT
2317           mem->dump();
2318 #endif
2319           ShouldNotReachHere();
2320         }
2321       }
2322     } else {
2323       if (n->is_Phi()) {
2324         // Nothing
2325       } else if (!n->is_Root()) {
2326         Node* c = get_ctrl(n);
2327         _memory_nodes.map(c->_idx, n);
2328       }
2329       stack.pop();
2330     }
2331   } while(stack.is_nonempty());
2332 
2333   // Iterate over CFG nodes in rpo and propagate memory state to
2334   // compute memory state at regions, creating new phis if needed.
2335   Node_List rpo_list;
2336   visited.Clear();
2337   _phase->rpo(_phase->C->root(), stack, visited, rpo_list);
2338   Node* root = rpo_list.pop();
2339   assert(root == _phase->C->root(), "");
2340 
2341   const bool trace = false;
2342 #ifdef ASSERT
2343   if (trace) {
2344     for (int i = rpo_list.size() - 1; i >= 0; i--) {
2345       Node* c = rpo_list.at(i);
2346       if (_memory_nodes[c->_idx] != NULL) {
2347         tty->print("X %d", c->_idx);  _memory_nodes[c->_idx]->dump();
2348       }
2349     }
2350   }
2351 #endif
2352   uint last = _phase->C->unique();
2353 
2354 #ifdef ASSERT
2355   uint8_t max_depth = 0;
2356   for (LoopTreeIterator iter(_phase->ltree_root()); !iter.done(); iter.next()) {
2357     IdealLoopTree* lpt = iter.current();
2358     max_depth = MAX2(max_depth, lpt->_nest);
2359   }
2360 #endif
2361 
2362   bool progress = true;
2363   int iteration = 0;
2364   Node_List dead_phis;
2365   while (progress) {
2366     progress = false;
2367     iteration++;
2368     assert(iteration <= 2+max_depth || _phase->C->has_irreducible_loop() || has_never_branch(_phase->C->root()), "");
2369     if (trace) { tty->print_cr("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"); }
2370     IdealLoopTree* last_updated_ilt = NULL;
2371     for (int i = rpo_list.size() - 1; i >= 0; i--) {
2372       Node* c = rpo_list.at(i);
2373 
2374       Node* prev_mem = _memory_nodes[c->_idx];
2375       if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
2376         Node* prev_region = regions[c->_idx];
2377         Node* unique = NULL;
2378         for (uint j = 1; j < c->req() && unique != NodeSentinel; j++) {
2379           Node* m = _memory_nodes[c->in(j)->_idx];
2380           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");
2381           if (m != NULL) {
2382             if (m == prev_region && ((c->is_Loop() && j == LoopNode::LoopBackControl) || (prev_region->is_Phi() && prev_region->in(0) == c))) {
2383               assert(c->is_Loop() && j == LoopNode::LoopBackControl || _phase->C->has_irreducible_loop(), "");
2384               // continue
2385             } else if (unique == NULL) {
2386               unique = m;
2387             } else if (m == unique) {
2388               // continue
2389             } else {
2390               unique = NodeSentinel;
2391             }
2392           }
2393         }
2394         assert(unique != NULL, "empty phi???");
2395         if (unique != NodeSentinel) {
2396           if (prev_region != NULL && prev_region->is_Phi() && prev_region->in(0) == c) {
2397             dead_phis.push(prev_region);
2398           }
2399           regions.map(c->_idx, unique);
2400         } else {
2401           Node* phi = NULL;
2402           if (prev_region != NULL && prev_region->is_Phi() && prev_region->in(0) == c && prev_region->_idx >= last) {
2403             phi = prev_region;
2404             for (uint k = 1; k < c->req(); k++) {
2405               Node* m = _memory_nodes[c->in(k)->_idx];
2406               assert(m != NULL, "expect memory state");
2407               phi->set_req(k, m);
2408             }
2409           } else {
2410             for (DUIterator_Fast jmax, j = c->fast_outs(jmax); j < jmax && phi == NULL; j++) {
2411               Node* u = c->fast_out(j);
2412               if (u->is_Phi() && u->bottom_type() == Type::MEMORY &&
2413                   (u->adr_type() == TypePtr::BOTTOM || _phase->C->get_alias_index(u->adr_type()) == _alias)) {
2414                 phi = u;
2415                 for (uint k = 1; k < c->req() && phi != NULL; k++) {
2416                   Node* m = _memory_nodes[c->in(k)->_idx];
2417                   assert(m != NULL, "expect memory state");
2418                   if (u->in(k) != m) {
2419                     phi = NULL;
2420                   }
2421                 }
2422               }
2423             }
2424             if (phi == NULL) {
2425               phi = new PhiNode(c, Type::MEMORY, _phase->C->get_adr_type(_alias));
2426               for (uint k = 1; k < c->req(); k++) {
2427                 Node* m = _memory_nodes[c->in(k)->_idx];
2428                 assert(m != NULL, "expect memory state");
2429                 phi->init_req(k, m);
2430               }
2431             }
2432           }
2433           assert(phi != NULL, "");
2434           regions.map(c->_idx, phi);
2435         }
2436         Node* current_region = regions[c->_idx];
2437         if (current_region != prev_region) {
2438           progress = true;
2439           if (prev_region == prev_mem) {
2440             _memory_nodes.map(c->_idx, current_region);
2441           }
2442         }
2443       } else if (prev_mem == NULL || prev_mem->is_Phi() || ctrl_or_self(prev_mem) != c) {
2444         Node* m = _memory_nodes[_phase->idom(c)->_idx];
2445         assert(m != NULL, "expect memory state");
2446         if (m != prev_mem) {
2447           _memory_nodes.map(c->_idx, m);
2448           progress = true;
2449         }
2450       }
2451 #ifdef ASSERT
2452       if (trace) { tty->print("X %d", c->_idx);  _memory_nodes[c->_idx]->dump(); }
2453 #endif
2454     }
2455   }
2456 
2457   // Replace existing phi with computed memory state for that region
2458   // if different (could be a new phi or a dominating memory node if
2459   // that phi was found to be useless).
2460   while (dead_phis.size() > 0) {
2461     Node* n = dead_phis.pop();
2462     n->replace_by(_phase->C->top());
2463     n->destruct();
2464   }
2465   for (int i = rpo_list.size() - 1; i >= 0; i--) {
2466     Node* c = rpo_list.at(i);
2467     if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
2468       Node* n = regions[c->_idx];
2469       if (n->is_Phi() && n->_idx >= last && n->in(0) == c) {
2470         _phase->register_new_node(n, c);
2471       }
2472     }
2473   }
2474   for (int i = rpo_list.size() - 1; i >= 0; i--) {
2475     Node* c = rpo_list.at(i);
2476     if (c->is_Region() && (_include_lsm || !c->is_OuterStripMinedLoop())) {
2477       Node* n = regions[c->_idx];
2478       for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
2479         Node* u = c->fast_out(i);
2480         if (u->is_Phi() && u->bottom_type() == Type::MEMORY &&
2481             u != n) {
2482           if (u->adr_type() == TypePtr::BOTTOM) {
2483             fix_memory_uses(u, n, n, c);
2484           } else if (_phase->C->get_alias_index(u->adr_type()) == _alias) {
2485             _phase->lazy_replace(u, n);
2486             --i; --imax;
2487           }
2488         }
2489       }
2490     }
2491   }
2492 }
2493 
2494 Node* MemoryGraphFixer::get_ctrl(Node* n) const {
2495   Node* c = _phase->get_ctrl(n);
2496   if (n->is_Proj() && n->in(0) != NULL && n->in(0)->is_Call()) {
2497     assert(c == n->in(0), "");
2498     CallNode* call = c->as_Call();
2499     CallProjections projs;
2500     call->extract_projections(&projs, true, false);
2501     if (projs.catchall_memproj != NULL) {
2502       if (projs.fallthrough_memproj == n) {
2503         c = projs.fallthrough_catchproj;
2504       } else {
2505         assert(projs.catchall_memproj == n, "");
2506         c = projs.catchall_catchproj;
2507       }
2508     }
2509   }
2510   return c;
2511 }
2512 
2513 Node* MemoryGraphFixer::ctrl_or_self(Node* n) const {
2514   if (_phase->has_ctrl(n))
2515     return get_ctrl(n);
2516   else {
2517     assert (n->is_CFG(), "must be a CFG node");
2518     return n;
2519   }
2520 }
2521 
2522 bool MemoryGraphFixer::mem_is_valid(Node* m, Node* c) const {
2523   return m != NULL && get_ctrl(m) == c;
2524 }
2525 
2526 Node* MemoryGraphFixer::find_mem(Node* ctrl, Node* n) const {
2527   assert(n == NULL || _phase->ctrl_or_self(n) == ctrl, "");
2528   Node* mem = _memory_nodes[ctrl->_idx];
2529   Node* c = ctrl;
2530   while (!mem_is_valid(mem, c) &&
2531          (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem))) {
2532     c = _phase->idom(c);
2533     mem = _memory_nodes[c->_idx];
2534   }
2535   if (n != NULL && mem_is_valid(mem, c)) {
2536     while (!ShenandoahBarrierC2Support::is_dominator_same_ctrl(c, mem, n, _phase) && _phase->ctrl_or_self(mem) == ctrl) {
2537       mem = next_mem(mem, _alias);
2538     }
2539     if (mem->is_MergeMem()) {
2540       mem = mem->as_MergeMem()->memory_at(_alias);
2541     }
2542     if (!mem_is_valid(mem, c)) {
2543       do {
2544         c = _phase->idom(c);
2545         mem = _memory_nodes[c->_idx];
2546       } while (!mem_is_valid(mem, c) &&
2547                (!c->is_CatchProj() || mem == NULL || c->in(0)->in(0)->in(0) != get_ctrl(mem)));
2548     }
2549   }
2550   assert(mem->bottom_type() == Type::MEMORY, "");
2551   return mem;
2552 }
2553 
2554 bool MemoryGraphFixer::has_mem_phi(Node* region) const {
2555   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
2556     Node* use = region->fast_out(i);
2557     if (use->is_Phi() && use->bottom_type() == Type::MEMORY &&
2558         (_phase->C->get_alias_index(use->adr_type()) == _alias)) {
2559       return true;
2560     }
2561   }
2562   return false;
2563 }
2564 
2565 void MemoryGraphFixer::fix_mem(Node* ctrl, Node* new_ctrl, Node* mem, Node* mem_for_ctrl, Node* new_mem, Unique_Node_List& uses) {
2566   assert(_phase->ctrl_or_self(new_mem) == new_ctrl, "");
2567   const bool trace = false;
2568   DEBUG_ONLY(if (trace) { tty->print("ZZZ control is"); ctrl->dump(); });
2569   DEBUG_ONLY(if (trace) { tty->print("ZZZ mem is"); mem->dump(); });
2570   GrowableArray<Node*> phis;
2571   if (mem_for_ctrl != mem) {
2572     Node* old = mem_for_ctrl;
2573     Node* prev = NULL;
2574     while (old != mem) {
2575       prev = old;
2576       if (old->is_Store() || old->is_ClearArray() || old->is_LoadStore()) {
2577         assert(_alias == Compile::AliasIdxRaw, "");
2578         old = old->in(MemNode::Memory);
2579       } else if (old->Opcode() == Op_SCMemProj) {
2580         assert(_alias == Compile::AliasIdxRaw, "");
2581         old = old->in(0);
2582       } else {
2583         ShouldNotReachHere();
2584       }
2585     }
2586     assert(prev != NULL, "");
2587     if (new_ctrl != ctrl) {
2588       _memory_nodes.map(ctrl->_idx, mem);
2589       _memory_nodes.map(new_ctrl->_idx, mem_for_ctrl);
2590     }
2591     uint input = (uint)MemNode::Memory;
2592     _phase->igvn().replace_input_of(prev, input, new_mem);
2593   } else {
2594     uses.clear();
2595     _memory_nodes.map(new_ctrl->_idx, new_mem);
2596     uses.push(new_ctrl);
2597     for(uint next = 0; next < uses.size(); next++ ) {
2598       Node *n = uses.at(next);
2599       assert(n->is_CFG(), "");
2600       DEBUG_ONLY(if (trace) { tty->print("ZZZ ctrl"); n->dump(); });
2601       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2602         Node* u = n->fast_out(i);
2603         if (!u->is_Root() && u->is_CFG() && u != n) {
2604           Node* m = _memory_nodes[u->_idx];
2605           if (u->is_Region() && (!u->is_OuterStripMinedLoop() || _include_lsm) &&
2606               !has_mem_phi(u) &&
2607               u->unique_ctrl_out()->Opcode() != Op_Halt) {
2608             DEBUG_ONLY(if (trace) { tty->print("ZZZ region"); u->dump(); });
2609             DEBUG_ONLY(if (trace && m != NULL) { tty->print("ZZZ mem"); m->dump(); });
2610 
2611             if (!mem_is_valid(m, u) || !m->is_Phi()) {
2612               bool push = true;
2613               bool create_phi = true;
2614               if (_phase->is_dominator(new_ctrl, u)) {
2615                 create_phi = false;
2616               } else if (!_phase->C->has_irreducible_loop()) {
2617                 IdealLoopTree* loop = _phase->get_loop(ctrl);
2618                 bool do_check = true;
2619                 IdealLoopTree* l = loop;
2620                 create_phi = false;
2621                 while (l != _phase->ltree_root()) {
2622                   Node* head = l->_head;
2623                   if (head->in(0) == NULL) {
2624                     head = _phase->get_ctrl(head);
2625                   }
2626                   if (_phase->is_dominator(head, u) && _phase->is_dominator(_phase->idom(u), head)) {
2627                     create_phi = true;
2628                     do_check = false;
2629                     break;
2630                   }
2631                   l = l->_parent;
2632                 }
2633 
2634                 if (do_check) {
2635                   assert(!create_phi, "");
2636                   IdealLoopTree* u_loop = _phase->get_loop(u);
2637                   if (u_loop != _phase->ltree_root() && u_loop->is_member(loop)) {
2638                     Node* c = ctrl;
2639                     while (!_phase->is_dominator(c, u_loop->tail())) {
2640                       c = _phase->idom(c);
2641                     }
2642                     if (!_phase->is_dominator(c, u)) {
2643                       do_check = false;
2644                     }
2645                   }
2646                 }
2647 
2648                 if (do_check && _phase->is_dominator(_phase->idom(u), new_ctrl)) {
2649                   create_phi = true;
2650                 }
2651               }
2652               if (create_phi) {
2653                 Node* phi = new PhiNode(u, Type::MEMORY, _phase->C->get_adr_type(_alias));
2654                 _phase->register_new_node(phi, u);
2655                 phis.push(phi);
2656                 DEBUG_ONLY(if (trace) { tty->print("ZZZ new phi"); phi->dump(); });
2657                 if (!mem_is_valid(m, u)) {
2658                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting mem"); phi->dump(); });
2659                   _memory_nodes.map(u->_idx, phi);
2660                 } else {
2661                   DEBUG_ONLY(if (trace) { tty->print("ZZZ NOT setting mem"); m->dump(); });
2662                   for (;;) {
2663                     assert(m->is_Mem() || m->is_LoadStore() || m->is_Proj(), "");
2664                     Node* next = NULL;
2665                     if (m->is_Proj()) {
2666                       next = m->in(0);
2667                     } else {
2668                       assert(m->is_Mem() || m->is_LoadStore(), "");
2669                       assert(_alias == Compile::AliasIdxRaw, "");
2670                       next = m->in(MemNode::Memory);
2671                     }
2672                     if (_phase->get_ctrl(next) != u) {
2673                       break;
2674                     }
2675                     if (next->is_MergeMem()) {
2676                       assert(_phase->get_ctrl(next->as_MergeMem()->memory_at(_alias)) != u, "");
2677                       break;
2678                     }
2679                     if (next->is_Phi()) {
2680                       assert(next->adr_type() == TypePtr::BOTTOM && next->in(0) == u, "");
2681                       break;
2682                     }
2683                     m = next;
2684                   }
2685 
2686                   DEBUG_ONLY(if (trace) { tty->print("ZZZ setting to phi"); m->dump(); });
2687                   assert(m->is_Mem() || m->is_LoadStore(), "");
2688                   uint input = (uint)MemNode::Memory;
2689                   _phase->igvn().replace_input_of(m, input, phi);
2690                   push = false;
2691                 }
2692               } else {
2693                 DEBUG_ONLY(if (trace) { tty->print("ZZZ skipping region"); u->dump(); });
2694               }
2695               if (push) {
2696                 uses.push(u);
2697               }
2698             }
2699           } else if (!mem_is_valid(m, u) &&
2700                      !(u->Opcode() == Op_CProj && u->in(0)->Opcode() == Op_NeverBranch && u->as_Proj()->_con == 1)) {
2701             uses.push(u);
2702           }
2703         }
2704       }
2705     }
2706     for (int i = 0; i < phis.length(); i++) {
2707       Node* n = phis.at(i);
2708       Node* r = n->in(0);
2709       DEBUG_ONLY(if (trace) { tty->print("ZZZ fixing new phi"); n->dump(); });
2710       for (uint j = 1; j < n->req(); j++) {
2711         Node* m = find_mem(r->in(j), NULL);
2712         _phase->igvn().replace_input_of(n, j, m);
2713         DEBUG_ONLY(if (trace) { tty->print("ZZZ fixing new phi: %d", j); m->dump(); });
2714       }
2715     }
2716   }
2717   uint last = _phase->C->unique();
2718   MergeMemNode* mm = NULL;
2719   int alias = _alias;
2720   DEBUG_ONLY(if (trace) { tty->print("ZZZ raw mem is"); mem->dump(); });
2721   for (DUIterator i = mem->outs(); mem->has_out(i); i++) {
2722     Node* u = mem->out(i);
2723     if (u->_idx < last) {
2724       if (u->is_Mem()) {
2725         if (_phase->C->get_alias_index(u->adr_type()) == alias) {
2726           Node* m = find_mem(_phase->get_ctrl(u), u);
2727           if (m != mem) {
2728             DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
2729             _phase->igvn().replace_input_of(u, MemNode::Memory, m);
2730             --i;
2731           }
2732         }
2733       } else if (u->is_MergeMem()) {
2734         MergeMemNode* u_mm = u->as_MergeMem();
2735         if (u_mm->memory_at(alias) == mem) {
2736           MergeMemNode* newmm = NULL;
2737           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
2738             Node* uu = u->fast_out(j);
2739             assert(!uu->is_MergeMem(), "chain of MergeMems?");
2740             if (uu->is_Phi()) {
2741               assert(uu->adr_type() == TypePtr::BOTTOM, "");
2742               Node* region = uu->in(0);
2743               int nb = 0;
2744               for (uint k = 1; k < uu->req(); k++) {
2745                 if (uu->in(k) == u) {
2746                   Node* m = find_mem(region->in(k), NULL);
2747                   if (m != mem) {
2748                     DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of phi %d", k); uu->dump(); });
2749                     newmm = clone_merge_mem(u, mem, m, _phase->ctrl_or_self(m), i);
2750                     if (newmm != u) {
2751                       _phase->igvn().replace_input_of(uu, k, newmm);
2752                       nb++;
2753                       --jmax;
2754                     }
2755                   }
2756                 }
2757               }
2758               if (nb > 0) {
2759                 --j;
2760               }
2761             } else {
2762               Node* m = find_mem(_phase->ctrl_or_self(uu), uu);
2763               if (m != mem) {
2764                 DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); uu->dump(); });
2765                 newmm = clone_merge_mem(u, mem, m, _phase->ctrl_or_self(m), i);
2766                 if (newmm != u) {
2767                   _phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
2768                   --j, --jmax;
2769                 }
2770               }
2771             }
2772           }
2773         }
2774       } else if (u->is_Phi()) {
2775         assert(u->bottom_type() == Type::MEMORY, "what else?");
2776         if (_phase->C->get_alias_index(u->adr_type()) == alias || u->adr_type() == TypePtr::BOTTOM) {
2777           Node* region = u->in(0);
2778           bool replaced = false;
2779           for (uint j = 1; j < u->req(); j++) {
2780             if (u->in(j) == mem) {
2781               Node* m = find_mem(region->in(j), NULL);
2782               Node* nnew = m;
2783               if (m != mem) {
2784                 if (u->adr_type() == TypePtr::BOTTOM) {
2785                   mm = allocate_merge_mem(mem, m, _phase->ctrl_or_self(m));
2786                   nnew = mm;
2787                 }
2788                 DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of phi %d", j); u->dump(); });
2789                 _phase->igvn().replace_input_of(u, j, nnew);
2790                 replaced = true;
2791               }
2792             }
2793           }
2794           if (replaced) {
2795             --i;
2796           }
2797         }
2798       } else if ((u->adr_type() == TypePtr::BOTTOM && u->Opcode() != Op_StrInflatedCopy) ||
2799                  u->adr_type() == NULL) {
2800         assert(u->adr_type() != NULL ||
2801                u->Opcode() == Op_Rethrow ||
2802                u->Opcode() == Op_Return ||
2803                u->Opcode() == Op_SafePoint ||
2804                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
2805                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
2806                u->Opcode() == Op_CallLeaf, "");
2807         Node* m = find_mem(_phase->ctrl_or_self(u), u);
2808         if (m != mem) {
2809           mm = allocate_merge_mem(mem, m, _phase->get_ctrl(m));
2810           _phase->igvn().replace_input_of(u, u->find_edge(mem), mm);
2811           --i;
2812         }
2813       } else if (_phase->C->get_alias_index(u->adr_type()) == alias) {
2814         Node* m = find_mem(_phase->ctrl_or_self(u), u);
2815         if (m != mem) {
2816           DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
2817           _phase->igvn().replace_input_of(u, u->find_edge(mem), m);
2818           --i;
2819         }
2820       } else if (u->adr_type() != TypePtr::BOTTOM &&
2821                  _memory_nodes[_phase->ctrl_or_self(u)->_idx] == u) {
2822         Node* m = find_mem(_phase->ctrl_or_self(u), u);
2823         assert(m != mem, "");
2824         // u is on the wrong slice...
2825         assert(u->is_ClearArray(), "");
2826         DEBUG_ONLY(if (trace) { tty->print("ZZZ setting memory of use"); u->dump(); });
2827         _phase->igvn().replace_input_of(u, u->find_edge(mem), m);
2828         --i;
2829       }
2830     }
2831   }
2832 #ifdef ASSERT
2833   assert(new_mem->outcnt() > 0, "");
2834   for (int i = 0; i < phis.length(); i++) {
2835     Node* n = phis.at(i);
2836     assert(n->outcnt() > 0, "new phi must have uses now");
2837   }
2838 #endif
2839 }
2840 
2841 MergeMemNode* MemoryGraphFixer::allocate_merge_mem(Node* mem, Node* rep_proj, Node* rep_ctrl) const {
2842   MergeMemNode* mm = MergeMemNode::make(mem);
2843   mm->set_memory_at(_alias, rep_proj);
2844   _phase->register_new_node(mm, rep_ctrl);
2845   return mm;
2846 }
2847 
2848 MergeMemNode* MemoryGraphFixer::clone_merge_mem(Node* u, Node* mem, Node* rep_proj, Node* rep_ctrl, DUIterator& i) const {
2849   MergeMemNode* newmm = NULL;
2850   MergeMemNode* u_mm = u->as_MergeMem();
2851   Node* c = _phase->get_ctrl(u);
2852   if (_phase->is_dominator(c, rep_ctrl)) {
2853     c = rep_ctrl;
2854   } else {
2855     assert(_phase->is_dominator(rep_ctrl, c), "one must dominate the other");
2856   }
2857   if (u->outcnt() == 1) {
2858     if (u->req() > (uint)_alias && u->in(_alias) == mem) {
2859       _phase->igvn().replace_input_of(u, _alias, rep_proj);
2860       --i;
2861     } else {
2862       _phase->igvn().rehash_node_delayed(u);
2863       u_mm->set_memory_at(_alias, rep_proj);
2864     }
2865     newmm = u_mm;
2866     _phase->set_ctrl_and_loop(u, c);
2867   } else {
2868     // can't simply clone u and then change one of its input because
2869     // it adds and then removes an edge which messes with the
2870     // DUIterator
2871     newmm = MergeMemNode::make(u_mm->base_memory());
2872     for (uint j = 0; j < u->req(); j++) {
2873       if (j < newmm->req()) {
2874         if (j == (uint)_alias) {
2875           newmm->set_req(j, rep_proj);
2876         } else if (newmm->in(j) != u->in(j)) {
2877           newmm->set_req(j, u->in(j));
2878         }
2879       } else if (j == (uint)_alias) {
2880         newmm->add_req(rep_proj);
2881       } else {
2882         newmm->add_req(u->in(j));
2883       }
2884     }
2885     if ((uint)_alias >= u->req()) {
2886       newmm->set_memory_at(_alias, rep_proj);
2887     }
2888     _phase->register_new_node(newmm, c);
2889   }
2890   return newmm;
2891 }
2892 
2893 bool MemoryGraphFixer::should_process_phi(Node* phi) const {
2894   if (phi->adr_type() == TypePtr::BOTTOM) {
2895     Node* region = phi->in(0);
2896     for (DUIterator_Fast jmax, j = region->fast_outs(jmax); j < jmax; j++) {
2897       Node* uu = region->fast_out(j);
2898       if (uu->is_Phi() && uu != phi && uu->bottom_type() == Type::MEMORY && _phase->C->get_alias_index(uu->adr_type()) == _alias) {
2899         return false;
2900       }
2901     }
2902     return true;
2903   }
2904   return _phase->C->get_alias_index(phi->adr_type()) == _alias;
2905 }
2906 
2907 void MemoryGraphFixer::fix_memory_uses(Node* mem, Node* replacement, Node* rep_proj, Node* rep_ctrl) const {
2908   uint last = _phase-> C->unique();
2909   MergeMemNode* mm = NULL;
2910   assert(mem->bottom_type() == Type::MEMORY, "");
2911   for (DUIterator i = mem->outs(); mem->has_out(i); i++) {
2912     Node* u = mem->out(i);
2913     if (u != replacement && u->_idx < last) {
2914       if (u->is_MergeMem()) {
2915         MergeMemNode* u_mm = u->as_MergeMem();
2916         if (u_mm->memory_at(_alias) == mem) {
2917           MergeMemNode* newmm = NULL;
2918           for (DUIterator_Fast jmax, j = u->fast_outs(jmax); j < jmax; j++) {
2919             Node* uu = u->fast_out(j);
2920             assert(!uu->is_MergeMem(), "chain of MergeMems?");
2921             if (uu->is_Phi()) {
2922               if (should_process_phi(uu)) {
2923                 Node* region = uu->in(0);
2924                 int nb = 0;
2925                 for (uint k = 1; k < uu->req(); k++) {
2926                   if (uu->in(k) == u && _phase->is_dominator(rep_ctrl, region->in(k))) {
2927                     if (newmm == NULL) {
2928                       newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
2929                     }
2930                     if (newmm != u) {
2931                       _phase->igvn().replace_input_of(uu, k, newmm);
2932                       nb++;
2933                       --jmax;
2934                     }
2935                   }
2936                 }
2937                 if (nb > 0) {
2938                   --j;
2939                 }
2940               }
2941             } else {
2942               if (rep_ctrl != uu && ShenandoahBarrierC2Support::is_dominator(rep_ctrl, _phase->ctrl_or_self(uu), replacement, uu, _phase)) {
2943                 if (newmm == NULL) {
2944                   newmm = clone_merge_mem(u, mem, rep_proj, rep_ctrl, i);
2945                 }
2946                 if (newmm != u) {
2947                   _phase->igvn().replace_input_of(uu, uu->find_edge(u), newmm);
2948                   --j, --jmax;
2949                 }
2950               }
2951             }
2952           }
2953         }
2954       } else if (u->is_Phi()) {
2955         assert(u->bottom_type() == Type::MEMORY, "what else?");
2956         Node* region = u->in(0);
2957         if (should_process_phi(u)) {
2958           bool replaced = false;
2959           for (uint j = 1; j < u->req(); j++) {
2960             if (u->in(j) == mem && _phase->is_dominator(rep_ctrl, region->in(j))) {
2961               Node* nnew = rep_proj;
2962               if (u->adr_type() == TypePtr::BOTTOM) {
2963                 if (mm == NULL) {
2964                   mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
2965                 }
2966                 nnew = mm;
2967               }
2968               _phase->igvn().replace_input_of(u, j, nnew);
2969               replaced = true;
2970             }
2971           }
2972           if (replaced) {
2973             --i;
2974           }
2975 
2976         }
2977       } else if ((u->adr_type() == TypePtr::BOTTOM && u->Opcode() != Op_StrInflatedCopy) ||
2978                  u->adr_type() == NULL) {
2979         assert(u->adr_type() != NULL ||
2980                u->Opcode() == Op_Rethrow ||
2981                u->Opcode() == Op_Return ||
2982                u->Opcode() == Op_SafePoint ||
2983                u->Opcode() == Op_StoreIConditional ||
2984                u->Opcode() == Op_StoreLConditional ||
2985                (u->is_CallStaticJava() && u->as_CallStaticJava()->uncommon_trap_request() != 0) ||
2986                (u->is_CallStaticJava() && u->as_CallStaticJava()->_entry_point == OptoRuntime::rethrow_stub()) ||
2987                u->Opcode() == Op_CallLeaf, "%s", u->Name());
2988         if (ShenandoahBarrierC2Support::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
2989           if (mm == NULL) {
2990             mm = allocate_merge_mem(mem, rep_proj, rep_ctrl);
2991           }
2992           _phase->igvn().replace_input_of(u, u->find_edge(mem), mm);
2993           --i;
2994         }
2995       } else if (_phase->C->get_alias_index(u->adr_type()) == _alias) {
2996         if (ShenandoahBarrierC2Support::is_dominator(rep_ctrl, _phase->ctrl_or_self(u), replacement, u, _phase)) {
2997           _phase->igvn().replace_input_of(u, u->find_edge(mem), rep_proj);
2998           --i;
2999         }
3000       }
3001     }
3002   }
3003 }
3004 
3005 ShenandoahLoadReferenceBarrierNode::ShenandoahLoadReferenceBarrierNode(Node* ctrl, Node* obj)
3006 : Node(ctrl, obj) {
3007   ShenandoahBarrierSetC2::bsc2()->state()->add_load_reference_barrier(this);
3008 }
3009 
3010 const Type* ShenandoahLoadReferenceBarrierNode::bottom_type() const {
3011   if (in(ValueIn) == NULL || in(ValueIn)->is_top()) {
3012     return Type::TOP;
3013   }
3014   const Type* t = in(ValueIn)->bottom_type();
3015   if (t == TypePtr::NULL_PTR) {
3016     return t;
3017   }
3018   return t->is_oopptr();
3019 }
3020 
3021 const Type* ShenandoahLoadReferenceBarrierNode::Value(PhaseGVN* phase) const {
3022   // Either input is TOP ==> the result is TOP
3023   const Type *t2 = phase->type(in(ValueIn));
3024   if( t2 == Type::TOP ) return Type::TOP;
3025 
3026   if (t2 == TypePtr::NULL_PTR) {
3027     return t2;
3028   }
3029 
3030   const Type* type = t2->is_oopptr()/*->cast_to_nonconst()*/;
3031   return type;
3032 }
3033 
3034 Node* ShenandoahLoadReferenceBarrierNode::Identity(PhaseGVN* phase) {
3035   Node* value = in(ValueIn);
3036   if (!needs_barrier(phase, value)) {
3037     return value;
3038   }
3039   return this;
3040 }
3041 
3042 bool ShenandoahLoadReferenceBarrierNode::needs_barrier(PhaseGVN* phase, Node* n) {
3043   Unique_Node_List visited;
3044   return needs_barrier_impl(phase, n, visited);
3045 }
3046 
3047 bool ShenandoahLoadReferenceBarrierNode::needs_barrier_impl(PhaseGVN* phase, Node* n, Unique_Node_List &visited) {
3048   if (n == NULL) return false;
3049   if (visited.member(n)) {
3050     return false; // Been there.
3051   }
3052   visited.push(n);
3053 
3054   if (n->is_Allocate()) {
3055     // tty->print_cr("optimize barrier on alloc");
3056     return false;
3057   }
3058   if (n->is_Call()) {
3059     // tty->print_cr("optimize barrier on call");
3060     return false;
3061   }
3062 
3063   const Type* type = phase->type(n);
3064   if (type == Type::TOP) {
3065     return false;
3066   }
3067   if (type->make_ptr()->higher_equal(TypePtr::NULL_PTR)) {
3068     // tty->print_cr("optimize barrier on null");
3069     return false;
3070   }
3071   if (type->make_oopptr() && type->make_oopptr()->const_oop() != NULL) {
3072     // tty->print_cr("optimize barrier on constant");
3073     return false;
3074   }
3075 
3076   switch (n->Opcode()) {
3077     case Op_AddP:
3078       return true; // TODO: Can refine?
3079     case Op_LoadP:
3080     case Op_ShenandoahCompareAndExchangeN:
3081     case Op_ShenandoahCompareAndExchangeP:
3082     case Op_CompareAndExchangeN:
3083     case Op_CompareAndExchangeP:
3084     case Op_GetAndSetN:
3085     case Op_GetAndSetP:
3086       return true;
3087     case Op_Phi: {
3088       for (uint i = 1; i < n->req(); i++) {
3089         if (needs_barrier_impl(phase, n->in(i), visited)) return true;
3090       }
3091       return false;
3092     }
3093     case Op_CheckCastPP:
3094     case Op_CastPP:
3095       return needs_barrier_impl(phase, n->in(1), visited);
3096     case Op_Proj:
3097       return needs_barrier_impl(phase, n->in(0), visited);
3098     case Op_ShenandoahLoadReferenceBarrier:
3099       // tty->print_cr("optimize barrier on barrier");
3100       return false;
3101     case Op_Parm:
3102       // tty->print_cr("optimize barrier on input arg");
3103       return false;
3104     case Op_DecodeN:
3105     case Op_EncodeP:
3106       return needs_barrier_impl(phase, n->in(1), visited);
3107     case Op_LoadN:
3108       return true;
3109     case Op_CMoveP:
3110       return needs_barrier_impl(phase, n->in(2), visited) ||
3111              needs_barrier_impl(phase, n->in(3), visited);
3112     case Op_ShenandoahEnqueueBarrier:
3113       return needs_barrier_impl(phase, n->in(1), visited);
3114     default:
3115       break;
3116   }
3117 #ifdef ASSERT
3118   tty->print("need barrier on?: ");
3119   tty->print_cr("ins:");
3120   n->dump(2);
3121   tty->print_cr("outs:");
3122   n->dump(-2);
3123   ShouldNotReachHere();
3124 #endif
3125   return true;
3126 }
3127 
3128 ShenandoahLoadReferenceBarrierNode::Strength ShenandoahLoadReferenceBarrierNode::get_barrier_strength() {
3129   Unique_Node_List visited;
3130   Node_Stack stack(0);
3131   stack.push(this, 0);
3132   Strength strength = NONE;
3133   while (strength != STRONG && stack.size() > 0) {
3134     Node* n = stack.node();
3135     if (visited.member(n)) {
3136       stack.pop();
3137       continue;
3138     }
3139     visited.push(n);
3140     bool visit_users = false;
3141     switch (n->Opcode()) {
3142       case Op_StoreN:
3143       case Op_StoreP: {
3144         strength = STRONG;
3145         break;
3146       }
3147       case Op_CmpP: {
3148         if (!n->in(1)->bottom_type()->higher_equal(TypePtr::NULL_PTR) &&
3149             !n->in(2)->bottom_type()->higher_equal(TypePtr::NULL_PTR)) {
3150           strength = STRONG;
3151         }
3152         break;
3153       }
3154       case Op_CallStaticJava: {
3155         strength = STRONG;
3156         break;
3157       }
3158       case Op_CallDynamicJava:
3159       case Op_CallLeaf:
3160       case Op_CallLeafNoFP:
3161       case Op_CompareAndSwapL:
3162       case Op_CompareAndSwapI:
3163       case Op_CompareAndSwapB:
3164       case Op_CompareAndSwapS:
3165       case Op_CompareAndSwapN:
3166       case Op_CompareAndSwapP:
3167       case Op_CompareAndExchangeL:
3168       case Op_CompareAndExchangeI:
3169       case Op_CompareAndExchangeB:
3170       case Op_CompareAndExchangeS:
3171       case Op_CompareAndExchangeN:
3172       case Op_CompareAndExchangeP:
3173       case Op_WeakCompareAndSwapL:
3174       case Op_WeakCompareAndSwapI:
3175       case Op_WeakCompareAndSwapB:
3176       case Op_WeakCompareAndSwapS:
3177       case Op_WeakCompareAndSwapN:
3178       case Op_WeakCompareAndSwapP:
3179       case Op_ShenandoahCompareAndSwapN:
3180       case Op_ShenandoahCompareAndSwapP:
3181       case Op_ShenandoahWeakCompareAndSwapN:
3182       case Op_ShenandoahWeakCompareAndSwapP:
3183       case Op_ShenandoahCompareAndExchangeN:
3184       case Op_ShenandoahCompareAndExchangeP:
3185       case Op_GetAndSetL:
3186       case Op_GetAndSetI:
3187       case Op_GetAndSetB:
3188       case Op_GetAndSetS:
3189       case Op_GetAndSetP:
3190       case Op_GetAndSetN:
3191       case Op_GetAndAddL:
3192       case Op_GetAndAddI:
3193       case Op_GetAndAddB:
3194       case Op_GetAndAddS:
3195       case Op_ShenandoahEnqueueBarrier:
3196       case Op_FastLock:
3197       case Op_FastUnlock:
3198       case Op_Rethrow:
3199       case Op_Return:
3200       case Op_StoreB:
3201       case Op_StoreC:
3202       case Op_StoreD:
3203       case Op_StoreF:
3204       case Op_StoreL:
3205       case Op_StoreLConditional:
3206       case Op_StoreI:
3207       case Op_StoreIConditional:
3208       case Op_StoreVector:
3209       case Op_StrInflatedCopy:
3210       case Op_StrCompressedCopy:
3211       case Op_EncodeP:
3212       case Op_CastP2X:
3213       case Op_SafePoint:
3214       case Op_EncodeISOArray:
3215         strength = STRONG;
3216         break;
3217       case Op_LoadB:
3218       case Op_LoadUB:
3219       case Op_LoadUS:
3220       case Op_LoadD:
3221       case Op_LoadF:
3222       case Op_LoadL:
3223       case Op_LoadI:
3224       case Op_LoadS:
3225       case Op_LoadN:
3226       case Op_LoadP:
3227       case Op_LoadVector: {
3228         const TypePtr* adr_type = n->adr_type();
3229         int alias_idx = Compile::current()->get_alias_index(adr_type);
3230         Compile::AliasType* alias_type = Compile::current()->alias_type(alias_idx);
3231         ciField* field = alias_type->field();
3232         bool is_static = field != NULL && field->is_static();
3233         bool is_final = field != NULL && field->is_final();
3234         bool is_stable = field != NULL && field->is_stable();
3235         if (ShenandoahOptimizeStaticFinals && is_static && is_final) {
3236           // Leave strength as is.
3237         } else if (ShenandoahOptimizeInstanceFinals && !is_static && is_final) {
3238           // Leave strength as is.
3239         } else if (ShenandoahOptimizeStableFinals && (is_stable || (adr_type->isa_aryptr() && adr_type->isa_aryptr()->is_stable()))) {
3240           // Leave strength as is.
3241         } else {
3242           strength = WEAK;
3243         }
3244         break;
3245       }
3246       case Op_AryEq: {
3247         Node* n1 = n->in(2);
3248         Node* n2 = n->in(3);
3249         if (!ShenandoahOptimizeStableFinals ||
3250             !n1->bottom_type()->isa_aryptr() || !n1->bottom_type()->isa_aryptr()->is_stable() ||
3251             !n2->bottom_type()->isa_aryptr() || !n2->bottom_type()->isa_aryptr()->is_stable()) {
3252           strength = WEAK;
3253         }
3254         break;
3255       }
3256       case Op_StrEquals:
3257       case Op_StrComp:
3258       case Op_StrIndexOf:
3259       case Op_StrIndexOfChar:
3260         if (!ShenandoahOptimizeStableFinals) {
3261            strength = WEAK;
3262         }
3263         break;
3264       case Op_Conv2B:
3265       case Op_LoadRange:
3266       case Op_LoadKlass:
3267       case Op_LoadNKlass:
3268         // NONE, i.e. leave current strength as is
3269         break;
3270       case Op_AddP:
3271       case Op_CheckCastPP:
3272       case Op_CastPP:
3273       case Op_CMoveP:
3274       case Op_Phi:
3275       case Op_ShenandoahLoadReferenceBarrier:
3276         visit_users = true;
3277         break;
3278       default: {
3279 #ifdef ASSERT
3280         tty->print_cr("Unknown node in get_barrier_strength:");
3281         n->dump(1);
3282         ShouldNotReachHere();
3283 #else
3284         strength = STRONG;
3285 #endif
3286       }
3287     }
3288 #ifdef ASSERT
3289 /*
3290     if (strength == STRONG) {
3291       tty->print("strengthening node: ");
3292       n->dump();
3293     }
3294     */
3295 #endif
3296     stack.pop();
3297     if (visit_users) {
3298       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3299         Node* user = n->fast_out(i);
3300         if (user != NULL) {
3301           stack.push(user, 0);
3302         }
3303       }
3304     }
3305   }
3306   return strength;
3307 }
3308 
3309 CallStaticJavaNode* ShenandoahLoadReferenceBarrierNode::pin_and_expand_null_check(PhaseIterGVN& igvn) {
3310   Node* val = in(ValueIn);
3311 
3312   const Type* val_t = igvn.type(val);
3313 
3314   if (val_t->meet(TypePtr::NULL_PTR) != val_t &&
3315       val->Opcode() == Op_CastPP &&
3316       val->in(0) != NULL &&
3317       val->in(0)->Opcode() == Op_IfTrue &&
3318       val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
3319       val->in(0)->in(0)->is_If() &&
3320       val->in(0)->in(0)->in(1)->Opcode() == Op_Bool &&
3321       val->in(0)->in(0)->in(1)->as_Bool()->_test._test == BoolTest::ne &&
3322       val->in(0)->in(0)->in(1)->in(1)->Opcode() == Op_CmpP &&
3323       val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1) &&
3324       val->in(0)->in(0)->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {
3325     assert(val->in(0)->in(0)->in(1)->in(1)->in(1) == val->in(1), "");
3326     CallStaticJavaNode* unc = val->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
3327     return unc;
3328   }
3329   return NULL;
3330 }