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