1 /*
   2  * Copyright (c) 2016, Oracle and/or its affiliates. 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 #include "opto/arraycopynode.hpp"
  27 #include "opto/graphKit.hpp"
  28 
  29 ArrayCopyNode::ArrayCopyNode(Compile* C, bool alloc_tightly_coupled)
  30   : CallNode(arraycopy_type(), NULL, TypeRawPtr::BOTTOM),
  31     _alloc_tightly_coupled(alloc_tightly_coupled),
  32     _kind(None),
  33     _arguments_validated(false),
  34     _src_type(TypeOopPtr::BOTTOM),
  35     _dest_type(TypeOopPtr::BOTTOM) {
  36   init_class_id(Class_ArrayCopy);
  37   init_flags(Flag_is_macro);
  38   C->add_macro_node(this);
  39 }
  40 
  41 uint ArrayCopyNode::size_of() const { return sizeof(*this); }
  42 
  43 ArrayCopyNode* ArrayCopyNode::make(GraphKit* kit, bool may_throw,
  44                                    Node* src, Node* src_offset,
  45                                    Node* dest, Node* dest_offset,
  46                                    Node* length,
  47                                    bool alloc_tightly_coupled,
  48                                    Node* src_klass, Node* dest_klass,
  49                                    Node* src_length, Node* dest_length) {
  50 
  51   ArrayCopyNode* ac = new ArrayCopyNode(kit->C, alloc_tightly_coupled);
  52   Node* prev_mem = kit->set_predefined_input_for_runtime_call(ac);
  53 
  54   ac->init_req(ArrayCopyNode::Src, src);
  55   ac->init_req(ArrayCopyNode::SrcPos, src_offset);
  56   ac->init_req(ArrayCopyNode::Dest, dest);
  57   ac->init_req(ArrayCopyNode::DestPos, dest_offset);
  58   ac->init_req(ArrayCopyNode::Length, length);
  59   ac->init_req(ArrayCopyNode::SrcLen, src_length);
  60   ac->init_req(ArrayCopyNode::DestLen, dest_length);
  61   ac->init_req(ArrayCopyNode::SrcKlass, src_klass);
  62   ac->init_req(ArrayCopyNode::DestKlass, dest_klass);
  63 
  64   if (may_throw) {
  65     ac->set_req(TypeFunc::I_O , kit->i_o());
  66     kit->add_safepoint_edges(ac, false);
  67   }
  68 
  69   return ac;
  70 }
  71 
  72 void ArrayCopyNode::connect_outputs(GraphKit* kit) {
  73   kit->set_all_memory_call(this, true);
  74   kit->set_control(kit->gvn().transform(new ProjNode(this,TypeFunc::Control)));
  75   kit->set_i_o(kit->gvn().transform(new ProjNode(this, TypeFunc::I_O)));
  76   kit->make_slow_call_ex(this, kit->env()->Throwable_klass(), true);
  77   kit->set_all_memory_call(this);
  78 }
  79 
  80 #ifndef PRODUCT
  81 const char* ArrayCopyNode::_kind_names[] = {"arraycopy", "arraycopy, validated arguments", "clone", "oop array clone", "CopyOf", "CopyOfRange"};
  82 
  83 void ArrayCopyNode::dump_spec(outputStream *st) const {
  84   CallNode::dump_spec(st);
  85   st->print(" (%s%s)", _kind_names[_kind], _alloc_tightly_coupled ? ", tightly coupled allocation" : "");
  86 }
  87 
  88 void ArrayCopyNode::dump_compact_spec(outputStream* st) const {
  89   st->print("%s%s", _kind_names[_kind], _alloc_tightly_coupled ? ",tight" : "");
  90 }
  91 #endif
  92 
  93 intptr_t ArrayCopyNode::get_length_if_constant(PhaseGVN *phase) const {
  94   // check that length is constant
  95   Node* length = in(ArrayCopyNode::Length);
  96   const Type* length_type = phase->type(length);
  97 
  98   if (length_type == Type::TOP) {
  99     return -1;
 100   }
 101 
 102   assert(is_clonebasic() || is_arraycopy() || is_copyof() || is_copyofrange(), "unexpected array copy type");
 103 
 104   return is_clonebasic() ? length->find_intptr_t_con(-1) : length->find_int_con(-1);
 105 }
 106 
 107 int ArrayCopyNode::get_count(PhaseGVN *phase) const {
 108   Node* src = in(ArrayCopyNode::Src);
 109   const Type* src_type = phase->type(src);
 110 
 111   if (is_clonebasic()) {
 112     if (src_type->isa_instptr()) {
 113       const TypeInstPtr* inst_src = src_type->is_instptr();
 114       ciInstanceKlass* ik = inst_src->klass()->as_instance_klass();
 115       // ciInstanceKlass::nof_nonstatic_fields() doesn't take injected
 116       // fields into account. They are rare anyway so easier to simply
 117       // skip instances with injected fields.
 118       if ((!inst_src->klass_is_exact() && (ik->is_interface() || ik->has_subklass())) || ik->has_injected_fields()) {
 119         return -1;
 120       }
 121       int nb_fields = ik->nof_nonstatic_fields();
 122       return nb_fields;
 123     } else {
 124       const TypeAryPtr* ary_src = src_type->isa_aryptr();
 125       assert (ary_src != NULL, "not an array or instance?");
 126       // clone passes a length as a rounded number of longs. If we're
 127       // cloning an array we'll do it element by element. If the
 128       // length input to ArrayCopyNode is constant, length of input
 129       // array must be too.
 130 
 131       assert((get_length_if_constant(phase) == -1) == !ary_src->size()->is_con() ||
 132              phase->is_IterGVN(), "inconsistent");
 133 
 134       if (ary_src->size()->is_con()) {
 135         return ary_src->size()->get_con();
 136       }
 137       return -1;
 138     }
 139   }
 140 
 141   return get_length_if_constant(phase);
 142 }
 143 
 144 Node* ArrayCopyNode::try_clone_instance(PhaseGVN *phase, bool can_reshape, int count) {
 145   if (!is_clonebasic()) {
 146     return NULL;
 147   }
 148 
 149   Node* src = in(ArrayCopyNode::Src);
 150   Node* dest = in(ArrayCopyNode::Dest);
 151   Node* ctl = in(TypeFunc::Control);
 152   Node* in_mem = in(TypeFunc::Memory);
 153 
 154   const Type* src_type = phase->type(src);
 155 
 156   assert(src->is_AddP(), "should be base + off");
 157   assert(dest->is_AddP(), "should be base + off");
 158   Node* base_src = src->in(AddPNode::Base);
 159   Node* base_dest = dest->in(AddPNode::Base);
 160 
 161   MergeMemNode* mem = MergeMemNode::make(in_mem);
 162 
 163   const TypeInstPtr* inst_src = src_type->isa_instptr();
 164 
 165   if (inst_src == NULL) {
 166     return NULL;
 167   }
 168 
 169   if (!inst_src->klass_is_exact()) {
 170     ciInstanceKlass* ik = inst_src->klass()->as_instance_klass();
 171     assert(!ik->is_interface() && !ik->has_subklass(), "inconsistent klass hierarchy");
 172     phase->C->dependencies()->assert_leaf_type(ik);
 173   }
 174 
 175   ciInstanceKlass* ik = inst_src->klass()->as_instance_klass();
 176   assert(ik->nof_nonstatic_fields() <= ArrayCopyLoadStoreMaxElem, "too many fields");
 177 
 178   for (int i = 0; i < count; i++) {
 179     ciField* field = ik->nonstatic_field_at(i);
 180     int fieldidx = phase->C->alias_type(field)->index();
 181     const TypePtr* adr_type = phase->C->alias_type(field)->adr_type();
 182     Node* off = phase->MakeConX(field->offset());
 183     Node* next_src = phase->transform(new AddPNode(base_src,base_src,off));
 184     Node* next_dest = phase->transform(new AddPNode(base_dest,base_dest,off));
 185     BasicType bt = field->layout_type();
 186 
 187     const Type *type;
 188     if (bt == T_OBJECT) {
 189       if (!field->type()->is_loaded()) {
 190         type = TypeInstPtr::BOTTOM;
 191       } else {
 192         ciType* field_klass = field->type();
 193         type = TypeOopPtr::make_from_klass(field_klass->as_klass());
 194       }
 195     } else {
 196       type = Type::get_const_basic_type(bt);
 197     }
 198 
 199     Node* v = LoadNode::make(*phase, ctl, mem->memory_at(fieldidx), next_src, adr_type, type, bt, MemNode::unordered);
 200     v = phase->transform(v);
 201     Node* s = StoreNode::make(*phase, ctl, mem->memory_at(fieldidx), next_dest, adr_type, v, bt, MemNode::unordered);
 202     s = phase->transform(s);
 203     mem->set_memory_at(fieldidx, s);
 204   }
 205 
 206   if (!finish_transform(phase, can_reshape, ctl, mem)) {
 207     // Return NodeSentinel to indicate that the transform failed
 208     return NodeSentinel;
 209   }
 210 
 211   return mem;
 212 }
 213 
 214 bool ArrayCopyNode::prepare_array_copy(PhaseGVN *phase, bool can_reshape,
 215                                        Node*& adr_src,
 216                                        Node*& base_src,
 217                                        Node*& adr_dest,
 218                                        Node*& base_dest,
 219                                        BasicType& copy_type,
 220                                        const Type*& value_type,
 221                                        bool& disjoint_bases) {
 222   Node* src = in(ArrayCopyNode::Src);
 223   Node* dest = in(ArrayCopyNode::Dest);
 224   const Type* src_type = phase->type(src);
 225   const TypeAryPtr* ary_src = src_type->isa_aryptr();
 226   assert(ary_src != NULL, "should be an array copy/clone");
 227 
 228   if (is_arraycopy() || is_copyofrange() || is_copyof()) {
 229     const Type* dest_type = phase->type(dest);
 230     const TypeAryPtr* ary_dest = dest_type->isa_aryptr();
 231     Node* src_offset = in(ArrayCopyNode::SrcPos);
 232     Node* dest_offset = in(ArrayCopyNode::DestPos);
 233 
 234     // newly allocated object is guaranteed to not overlap with source object
 235     disjoint_bases = is_alloc_tightly_coupled();
 236 
 237     if (ary_src  == NULL || ary_src->klass()  == NULL ||
 238         ary_dest == NULL || ary_dest->klass() == NULL) {
 239       // We don't know if arguments are arrays
 240       return false;
 241     }
 242 
 243     BasicType src_elem  = ary_src->klass()->as_array_klass()->element_type()->basic_type();
 244     BasicType dest_elem = ary_dest->klass()->as_array_klass()->element_type()->basic_type();
 245     if (src_elem  == T_ARRAY)  src_elem  = T_OBJECT;
 246     if (dest_elem == T_ARRAY)  dest_elem = T_OBJECT;
 247 
 248     if (src_elem != dest_elem || dest_elem == T_VOID) {
 249       // We don't know if arguments are arrays of the same type
 250       return false;
 251     }
 252 
 253     if (dest_elem == T_OBJECT && (!is_alloc_tightly_coupled() || !GraphKit::use_ReduceInitialCardMarks())) {
 254       // It's an object array copy but we can't emit the card marking
 255       // that is needed
 256       return false;
 257     }
 258 
 259     value_type = ary_src->elem();
 260 
 261     base_src = src;
 262     base_dest = dest;
 263 
 264     uint shift  = exact_log2(type2aelembytes(dest_elem));
 265     uint header = arrayOopDesc::base_offset_in_bytes(dest_elem);
 266 
 267     adr_src = src;
 268     adr_dest = dest;
 269 
 270     src_offset = Compile::conv_I2X_index(phase, src_offset, ary_src->size());
 271     dest_offset = Compile::conv_I2X_index(phase, dest_offset, ary_dest->size());
 272 
 273     Node* src_scale = phase->transform(new LShiftXNode(src_offset, phase->intcon(shift)));
 274     Node* dest_scale = phase->transform(new LShiftXNode(dest_offset, phase->intcon(shift)));
 275 
 276     adr_src = phase->transform(new AddPNode(base_src, adr_src, src_scale));
 277     adr_dest = phase->transform(new AddPNode(base_dest, adr_dest, dest_scale));
 278 
 279     adr_src = new AddPNode(base_src, adr_src, phase->MakeConX(header));
 280     adr_dest = new AddPNode(base_dest, adr_dest, phase->MakeConX(header));
 281 
 282     adr_src = phase->transform(adr_src);
 283     adr_dest = phase->transform(adr_dest);
 284 
 285     copy_type = dest_elem;
 286   } else {
 287     assert (is_clonebasic(), "should be");
 288 
 289     disjoint_bases = true;
 290     assert(src->is_AddP(), "should be base + off");
 291     assert(dest->is_AddP(), "should be base + off");
 292     adr_src = src;
 293     base_src = src->in(AddPNode::Base);
 294     adr_dest = dest;
 295     base_dest = dest->in(AddPNode::Base);
 296 
 297     assert(phase->type(src->in(AddPNode::Offset))->is_intptr_t()->get_con() == phase->type(dest->in(AddPNode::Offset))->is_intptr_t()->get_con(), "same start offset?");
 298     BasicType elem = ary_src->klass()->as_array_klass()->element_type()->basic_type();
 299     if (elem == T_ARRAY)  elem = T_OBJECT;
 300 
 301     int diff = arrayOopDesc::base_offset_in_bytes(elem) - phase->type(src->in(AddPNode::Offset))->is_intptr_t()->get_con();
 302     assert(diff >= 0, "clone should not start after 1st array element");
 303     if (diff > 0) {
 304       adr_src = phase->transform(new AddPNode(base_src, adr_src, phase->MakeConX(diff)));
 305       adr_dest = phase->transform(new AddPNode(base_dest, adr_dest, phase->MakeConX(diff)));
 306     }
 307 
 308     copy_type = elem;
 309     value_type = ary_src->elem();
 310   }
 311   return true;
 312 }
 313 
 314 const TypePtr* ArrayCopyNode::get_address_type(PhaseGVN *phase, Node* n) {
 315   const Type* at = phase->type(n);
 316   assert(at != Type::TOP, "unexpected type");
 317   const TypePtr* atp = at->isa_ptr();
 318   // adjust atp to be the correct array element address type
 319   atp = atp->add_offset(Type::OffsetBot);
 320   return atp;
 321 }
 322 
 323 void ArrayCopyNode::array_copy_test_overlap(PhaseGVN *phase, bool can_reshape, bool disjoint_bases, int count, Node*& forward_ctl, Node*& backward_ctl) {
 324   Node* ctl = in(TypeFunc::Control);
 325   if (!disjoint_bases && count > 1) {
 326     Node* src_offset = in(ArrayCopyNode::SrcPos);
 327     Node* dest_offset = in(ArrayCopyNode::DestPos);
 328     assert(src_offset != NULL && dest_offset != NULL, "should be");
 329     Node* cmp = phase->transform(new CmpINode(src_offset, dest_offset));
 330     Node *bol = phase->transform(new BoolNode(cmp, BoolTest::lt));
 331     IfNode *iff = new IfNode(ctl, bol, PROB_FAIR, COUNT_UNKNOWN);
 332 
 333     phase->transform(iff);
 334 
 335     forward_ctl = phase->transform(new IfFalseNode(iff));
 336     backward_ctl = phase->transform(new IfTrueNode(iff));
 337   } else {
 338     forward_ctl = ctl;
 339   }
 340 }
 341 
 342 Node* ArrayCopyNode::array_copy_forward(PhaseGVN *phase,
 343                                         bool can_reshape,
 344                                         Node* forward_ctl,
 345                                         Node* start_mem_src,
 346                                         Node* start_mem_dest,
 347                                         const TypePtr* atp_src,
 348                                         const TypePtr* atp_dest,
 349                                         Node* adr_src,
 350                                         Node* base_src,
 351                                         Node* adr_dest,
 352                                         Node* base_dest,
 353                                         BasicType copy_type,
 354                                         const Type* value_type,
 355                                         int count) {
 356   Node* mem = phase->C->top();
 357   if (!forward_ctl->is_top()) {
 358     // copy forward
 359     mem = start_mem_dest;
 360 
 361     if (count > 0) {
 362       Node* v = LoadNode::make(*phase, forward_ctl, start_mem_src, adr_src, atp_src, value_type, copy_type, MemNode::unordered);
 363       v = phase->transform(v);
 364       mem = StoreNode::make(*phase, forward_ctl, mem, adr_dest, atp_dest, v, copy_type, MemNode::unordered);
 365       mem = phase->transform(mem);
 366       for (int i = 1; i < count; i++) {
 367         Node* off  = phase->MakeConX(type2aelembytes(copy_type) * i);
 368         Node* next_src = phase->transform(new AddPNode(base_src,adr_src,off));
 369         Node* next_dest = phase->transform(new AddPNode(base_dest,adr_dest,off));
 370         v = LoadNode::make(*phase, forward_ctl, mem, next_src, atp_src, value_type, copy_type, MemNode::unordered);
 371         v = phase->transform(v);
 372         mem = StoreNode::make(*phase, forward_ctl,mem,next_dest,atp_dest,v, copy_type, MemNode::unordered);
 373         mem = phase->transform(mem);
 374       }
 375     } else if(can_reshape) {
 376       PhaseIterGVN* igvn = phase->is_IterGVN();
 377       igvn->_worklist.push(adr_src);
 378       igvn->_worklist.push(adr_dest);
 379     }
 380   }
 381   return mem;
 382 }
 383 
 384 Node* ArrayCopyNode::array_copy_backward(PhaseGVN *phase,
 385                                          bool can_reshape,
 386                                          Node* backward_ctl,
 387                                          Node* start_mem_src,
 388                                          Node* start_mem_dest,
 389                                          const TypePtr* atp_src,
 390                                          const TypePtr* atp_dest,
 391                                          Node* adr_src,
 392                                          Node* base_src,
 393                                          Node* adr_dest,
 394                                          Node* base_dest,
 395                                          BasicType copy_type,
 396                                          const Type* value_type,
 397                                          int count) {
 398   Node* mem = phase->C->top();
 399   if (!backward_ctl->is_top()) {
 400     // copy backward
 401     mem = start_mem_dest;
 402 
 403     if (count > 0) {
 404       for (int i = count-1; i >= 1; i--) {
 405         Node* off  = phase->MakeConX(type2aelembytes(copy_type) * i);
 406         Node* next_src = phase->transform(new AddPNode(base_src,adr_src,off));
 407         Node* next_dest = phase->transform(new AddPNode(base_dest,adr_dest,off));
 408         Node* v = LoadNode::make(*phase, backward_ctl, mem, next_src, atp_src, value_type, copy_type, MemNode::unordered);
 409         v = phase->transform(v);
 410         mem = StoreNode::make(*phase, backward_ctl,mem,next_dest,atp_dest,v, copy_type, MemNode::unordered);
 411         mem = phase->transform(mem);
 412       }
 413       Node* v = LoadNode::make(*phase, backward_ctl, mem, adr_src, atp_src, value_type, copy_type, MemNode::unordered);
 414       v = phase->transform(v);
 415       mem = StoreNode::make(*phase, backward_ctl, mem, adr_dest, atp_dest, v, copy_type, MemNode::unordered);
 416       mem = phase->transform(mem);
 417     } else if(can_reshape) {
 418       PhaseIterGVN* igvn = phase->is_IterGVN();
 419       igvn->_worklist.push(adr_src);
 420       igvn->_worklist.push(adr_dest);
 421     }
 422   }
 423   return mem;
 424 }
 425 
 426 bool ArrayCopyNode::finish_transform(PhaseGVN *phase, bool can_reshape,
 427                                      Node* ctl, Node *mem) {
 428   if (can_reshape) {
 429     PhaseIterGVN* igvn = phase->is_IterGVN();
 430     igvn->set_delay_transform(false);
 431     if (is_clonebasic()) {
 432       Node* out_mem = proj_out(TypeFunc::Memory);
 433 
 434       if (out_mem->outcnt() != 1 || !out_mem->raw_out(0)->is_MergeMem() ||
 435           out_mem->raw_out(0)->outcnt() != 1 || !out_mem->raw_out(0)->raw_out(0)->is_MemBar()) {
 436         assert(!GraphKit::use_ReduceInitialCardMarks(), "can only happen with card marking");
 437         return false;
 438       }
 439 
 440       igvn->replace_node(out_mem->raw_out(0), mem);
 441 
 442       Node* out_ctl = proj_out(TypeFunc::Control);
 443       igvn->replace_node(out_ctl, ctl);
 444     } else {
 445       // replace fallthrough projections of the ArrayCopyNode by the
 446       // new memory, control and the input IO.
 447       CallProjections callprojs;
 448       extract_projections(&callprojs, true, false);
 449 
 450       if (callprojs.fallthrough_ioproj != NULL) {
 451         igvn->replace_node(callprojs.fallthrough_ioproj, in(TypeFunc::I_O));
 452       }
 453       if (callprojs.fallthrough_memproj != NULL) {
 454         igvn->replace_node(callprojs.fallthrough_memproj, mem);
 455       }
 456       if (callprojs.fallthrough_catchproj != NULL) {
 457         igvn->replace_node(callprojs.fallthrough_catchproj, ctl);
 458       }
 459 
 460       // The ArrayCopyNode is not disconnected. It still has the
 461       // projections for the exception case. Replace current
 462       // ArrayCopyNode with a dummy new one with a top() control so
 463       // that this part of the graph stays consistent but is
 464       // eventually removed.
 465 
 466       set_req(0, phase->C->top());
 467       remove_dead_region(phase, can_reshape);
 468     }
 469   } else {
 470     if (in(TypeFunc::Control) != ctl) {
 471       // we can't return new memory and control from Ideal at parse time
 472       assert(!is_clonebasic(), "added control for clone?");
 473       return false;
 474     }
 475   }
 476   return true;
 477 }
 478 
 479 
 480 Node *ArrayCopyNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 481   if (remove_dead_region(phase, can_reshape))  return this;
 482 
 483   if (StressArrayCopyMacroNode && !can_reshape) {
 484     phase->record_for_igvn(this);
 485     return NULL;
 486   }
 487 
 488   // See if it's a small array copy and we can inline it as
 489   // loads/stores
 490   // Here we can only do:
 491   // - arraycopy if all arguments were validated before and we don't
 492   // need card marking
 493   // - clone for which we don't need to do card marking
 494 
 495   if (!is_clonebasic() && !is_arraycopy_validated() &&
 496       !is_copyofrange_validated() && !is_copyof_validated()) {
 497     return NULL;
 498   }
 499 
 500   assert(in(TypeFunc::Control) != NULL &&
 501          in(TypeFunc::Memory) != NULL &&
 502          in(ArrayCopyNode::Src) != NULL &&
 503          in(ArrayCopyNode::Dest) != NULL &&
 504          in(ArrayCopyNode::Length) != NULL &&
 505          ((in(ArrayCopyNode::SrcPos) != NULL && in(ArrayCopyNode::DestPos) != NULL) ||
 506           is_clonebasic()), "broken inputs");
 507 
 508   if (in(TypeFunc::Control)->is_top() ||
 509       in(TypeFunc::Memory)->is_top() ||
 510       phase->type(in(ArrayCopyNode::Src)) == Type::TOP ||
 511       phase->type(in(ArrayCopyNode::Dest)) == Type::TOP ||
 512       (in(ArrayCopyNode::SrcPos) != NULL && in(ArrayCopyNode::SrcPos)->is_top()) ||
 513       (in(ArrayCopyNode::DestPos) != NULL && in(ArrayCopyNode::DestPos)->is_top())) {
 514     return NULL;
 515   }
 516 
 517   int count = get_count(phase);
 518 
 519   if (count < 0 || count > ArrayCopyLoadStoreMaxElem) {
 520     return NULL;
 521   }
 522 
 523   Node* mem = try_clone_instance(phase, can_reshape, count);
 524   if (mem != NULL) {
 525     return (mem == NodeSentinel) ? NULL : mem;
 526   }
 527 
 528   Node* adr_src = NULL;
 529   Node* base_src = NULL;
 530   Node* adr_dest = NULL;
 531   Node* base_dest = NULL;
 532   BasicType copy_type = T_ILLEGAL;
 533   const Type* value_type = NULL;
 534   bool disjoint_bases = false;
 535 
 536   if (!prepare_array_copy(phase, can_reshape,
 537                           adr_src, base_src, adr_dest, base_dest,
 538                           copy_type, value_type, disjoint_bases)) {
 539     return NULL;
 540   }
 541 
 542   Node* src = in(ArrayCopyNode::Src);
 543   Node* dest = in(ArrayCopyNode::Dest);
 544   const TypePtr* atp_src = get_address_type(phase, src);
 545   const TypePtr* atp_dest = get_address_type(phase, dest);
 546   uint alias_idx_src = phase->C->get_alias_index(atp_src);
 547   uint alias_idx_dest = phase->C->get_alias_index(atp_dest);
 548 
 549   Node *in_mem = in(TypeFunc::Memory);
 550   Node *start_mem_src = in_mem;
 551   Node *start_mem_dest = in_mem;
 552   if (in_mem->is_MergeMem()) {
 553     start_mem_src = in_mem->as_MergeMem()->memory_at(alias_idx_src);
 554     start_mem_dest = in_mem->as_MergeMem()->memory_at(alias_idx_dest);
 555   }
 556 
 557 
 558   if (can_reshape) {
 559     assert(!phase->is_IterGVN()->delay_transform(), "cannot delay transforms");
 560     phase->is_IterGVN()->set_delay_transform(true);
 561   }
 562 
 563   Node* backward_ctl = phase->C->top();
 564   Node* forward_ctl = phase->C->top();
 565   array_copy_test_overlap(phase, can_reshape, disjoint_bases, count, forward_ctl, backward_ctl);
 566 
 567   Node* forward_mem = array_copy_forward(phase, can_reshape, forward_ctl,
 568                                          start_mem_src, start_mem_dest,
 569                                          atp_src, atp_dest,
 570                                          adr_src, base_src, adr_dest, base_dest,
 571                                          copy_type, value_type, count);
 572 
 573   Node* backward_mem = array_copy_backward(phase, can_reshape, backward_ctl,
 574                                            start_mem_src, start_mem_dest,
 575                                            atp_src, atp_dest,
 576                                            adr_src, base_src, adr_dest, base_dest,
 577                                            copy_type, value_type, count);
 578 
 579   Node* ctl = NULL;
 580   if (!forward_ctl->is_top() && !backward_ctl->is_top()) {
 581     ctl = new RegionNode(3);
 582     mem = new PhiNode(ctl, Type::MEMORY, atp_dest);
 583     ctl->init_req(1, forward_ctl);
 584     mem->init_req(1, forward_mem);
 585     ctl->init_req(2, backward_ctl);
 586     mem->init_req(2, backward_mem);
 587     ctl = phase->transform(ctl);
 588     mem = phase->transform(mem);
 589   } else if (!forward_ctl->is_top()) {
 590     ctl = forward_ctl;
 591     mem = forward_mem;
 592   } else {
 593     assert(!backward_ctl->is_top(), "no copy?");
 594     ctl = backward_ctl;
 595     mem = backward_mem;
 596   }
 597 
 598   if (can_reshape) {
 599     assert(phase->is_IterGVN()->delay_transform(), "should be delaying transforms");
 600     phase->is_IterGVN()->set_delay_transform(false);
 601   }
 602 
 603   MergeMemNode* out_mem = MergeMemNode::make(in_mem);
 604   out_mem->set_memory_at(alias_idx_dest, mem);
 605   mem = out_mem;
 606 
 607   if (!finish_transform(phase, can_reshape, ctl, mem)) {
 608     return NULL;
 609   }
 610 
 611   return mem;
 612 }
 613 
 614 bool ArrayCopyNode::may_modify(const TypeOopPtr *t_oop, PhaseTransform *phase) {
 615   Node* dest = in(ArrayCopyNode::Dest);
 616   if (dest->is_top()) {
 617     return false;
 618   }
 619   const TypeOopPtr* dest_t = phase->type(dest)->is_oopptr();
 620   assert(!dest_t->is_known_instance() || _dest_type->is_known_instance(), "result of EA not recorded");
 621   assert(in(ArrayCopyNode::Src)->is_top() || !phase->type(in(ArrayCopyNode::Src))->is_oopptr()->is_known_instance() ||
 622          _src_type->is_known_instance(), "result of EA not recorded");
 623 
 624   if (_dest_type != TypeOopPtr::BOTTOM || t_oop->is_known_instance()) {
 625     assert(_dest_type == TypeOopPtr::BOTTOM || _dest_type->is_known_instance(), "result of EA is known instance");
 626     return t_oop->instance_id() == _dest_type->instance_id();
 627   }
 628 
 629   return CallNode::may_modify_arraycopy_helper(dest_t, t_oop, phase);
 630 }
 631 
 632 bool ArrayCopyNode::may_modify_helper(const TypeOopPtr *t_oop, Node* n, PhaseTransform *phase, ArrayCopyNode*& ac) {
 633   if (n->is_Proj()) {
 634     n = n->in(0);
 635     if (n->is_Call() && n->as_Call()->may_modify(t_oop, phase)) {
 636       if (n->isa_ArrayCopy() != NULL) {
 637         ac = n->as_ArrayCopy();
 638       }
 639       return true;
 640     }
 641   }
 642   return false;
 643 }
 644 
 645 bool ArrayCopyNode::may_modify(const TypeOopPtr *t_oop, MemBarNode* mb, PhaseTransform *phase, ArrayCopyNode*& ac) {
 646   Node* mem = mb->in(TypeFunc::Memory);
 647 
 648   if (mem->is_MergeMem()) {
 649     Node* n = mem->as_MergeMem()->memory_at(Compile::AliasIdxRaw);
 650     if (may_modify_helper(t_oop, n, phase, ac)) {
 651       return true;
 652     } else if (n->is_Phi()) {
 653       for (uint i = 1; i < n->req(); i++) {
 654         if (n->in(i) != NULL) {
 655           if (may_modify_helper(t_oop, n->in(i), phase, ac)) {
 656             return true;
 657           }
 658         }
 659       }
 660     } else if (n->Opcode() == Op_StoreCM) {
 661       // Ignore card mark stores
 662       return may_modify_helper(t_oop, n->in(MemNode::Memory), phase, ac);
 663     }
 664   }
 665 
 666   return false;
 667 }
 668 
 669 // Does this array copy modify offsets between offset_lo and offset_hi
 670 // in the destination array
 671 // if must_modify is false, return true if the copy could write
 672 // between offset_lo and offset_hi
 673 // if must_modify is true, return true if the copy is guaranteed to
 674 // write between offset_lo and offset_hi
 675 bool ArrayCopyNode::modifies(intptr_t offset_lo, intptr_t offset_hi, PhaseTransform* phase, bool must_modify) {
 676   assert(_kind == ArrayCopy || _kind == CopyOf || _kind == CopyOfRange, "only for real array copies");
 677 
 678   Node* dest = in(ArrayCopyNode::Dest);
 679   Node* src_pos = in(ArrayCopyNode::SrcPos);
 680   Node* dest_pos = in(ArrayCopyNode::DestPos);
 681   Node* len = in(ArrayCopyNode::Length);
 682 
 683   const TypeInt *dest_pos_t = phase->type(dest_pos)->isa_int();
 684   const TypeInt *len_t = phase->type(len)->isa_int();
 685   const TypeAryPtr* ary_t = phase->type(dest)->isa_aryptr();
 686 
 687   if (dest_pos_t != NULL && len_t != NULL && ary_t != NULL) {
 688     BasicType ary_elem = ary_t->klass()->as_array_klass()->element_type()->basic_type();
 689     uint header = arrayOopDesc::base_offset_in_bytes(ary_elem);
 690     uint elemsize = type2aelembytes(ary_elem);
 691 
 692     jlong dest_pos_plus_len_lo = (((jlong)dest_pos_t->_lo) + len_t->_lo) * elemsize + header;
 693     jlong dest_pos_plus_len_hi = (((jlong)dest_pos_t->_hi) + len_t->_hi) * elemsize + header;
 694     jlong dest_pos_lo = ((jlong)dest_pos_t->_lo) * elemsize + header;
 695     jlong dest_pos_hi = ((jlong)dest_pos_t->_hi) * elemsize + header;
 696 
 697     if (must_modify) {
 698       if (offset_lo >= dest_pos_hi && offset_hi < dest_pos_plus_len_lo) {
 699         return true;
 700       }
 701     } else {
 702       if (offset_hi >= dest_pos_lo && offset_lo < dest_pos_plus_len_hi) {
 703         return true;
 704       }
 705     }
 706   }
 707   return false;
 708 }
--- EOF ---