1 /*
   2  * Copyright (c) 1999, 2017, 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 "c1/c1_IR.hpp"
  27 #include "c1/c1_Instruction.hpp"
  28 #include "c1/c1_InstructionPrinter.hpp"
  29 #include "c1/c1_ValueStack.hpp"
  30 #include "ci/ciObjArrayKlass.hpp"
  31 #include "ci/ciTypeArrayKlass.hpp"
  32 #include "ci/ciValueArrayKlass.hpp"
  33 #include "ci/ciValueKlass.hpp"
  34 
  35 
  36 // Implementation of Instruction
  37 
  38 
  39 int Instruction::dominator_depth() {
  40   int result = -1;
  41   if (block()) {
  42     result = block()->dominator_depth();
  43   }
  44   assert(result != -1 || this->as_Local(), "Only locals have dominator depth -1");
  45   return result;
  46 }
  47 
  48 Instruction::Condition Instruction::mirror(Condition cond) {
  49   switch (cond) {
  50     case eql: return eql;
  51     case neq: return neq;
  52     case lss: return gtr;
  53     case leq: return geq;
  54     case gtr: return lss;
  55     case geq: return leq;
  56     case aeq: return beq;
  57     case beq: return aeq;
  58   }
  59   ShouldNotReachHere();
  60   return eql;
  61 }
  62 
  63 
  64 Instruction::Condition Instruction::negate(Condition cond) {
  65   switch (cond) {
  66     case eql: return neq;
  67     case neq: return eql;
  68     case lss: return geq;
  69     case leq: return gtr;
  70     case gtr: return leq;
  71     case geq: return lss;
  72     case aeq: assert(false, "Above equal cannot be negated");
  73     case beq: assert(false, "Below equal cannot be negated");
  74   }
  75   ShouldNotReachHere();
  76   return eql;
  77 }
  78 
  79 void Instruction::update_exception_state(ValueStack* state) {
  80   if (state != NULL && (state->kind() == ValueStack::EmptyExceptionState || state->kind() == ValueStack::ExceptionState)) {
  81     assert(state->kind() == ValueStack::EmptyExceptionState || Compilation::current()->env()->should_retain_local_variables(), "unexpected state kind");
  82     _exception_state = state;
  83   } else {
  84     _exception_state = NULL;
  85   }
  86 }
  87 
  88 // Prev without need to have BlockBegin
  89 Instruction* Instruction::prev() {
  90   Instruction* p = NULL;
  91   Instruction* q = block();
  92   while (q != this) {
  93     assert(q != NULL, "this is not in the block's instruction list");
  94     p = q; q = q->next();
  95   }
  96   return p;
  97 }
  98 
  99 
 100 void Instruction::state_values_do(ValueVisitor* f) {
 101   if (state_before() != NULL) {
 102     state_before()->values_do(f);
 103   }
 104   if (exception_state() != NULL){
 105     exception_state()->values_do(f);
 106   }
 107 }
 108 
 109 ciType* Instruction::exact_type() const {
 110   ciType* t =  declared_type();
 111   if (t != NULL && t->is_klass()) {
 112     return t->as_klass()->exact_klass();
 113   }
 114   return NULL;
 115 }
 116 
 117 bool Instruction::is_flattened_array() const {
 118   if (ValueArrayFlatten) {
 119     ciType* type = declared_type();
 120     if (type != NULL && type->is_value_array_klass()) {
 121       ciValueKlass* element_klass = type->as_value_array_klass()->element_klass()->as_value_klass();
 122       if (!element_klass->is_loaded() || element_klass->flatten_array()) {
 123         // Assume that all unloaded value arrays are not flattenable. If they
 124         // turn out to be flattenable, we deoptimize on aaload/aastore.
 125         return true;
 126       }
 127     }
 128   }
 129 
 130   return false;
 131 }
 132 
 133 #ifndef PRODUCT
 134 void Instruction::check_state(ValueStack* state) {
 135   if (state != NULL) {
 136     state->verify();
 137   }
 138 }
 139 
 140 
 141 void Instruction::print() {
 142   InstructionPrinter ip;
 143   print(ip);
 144 }
 145 
 146 
 147 void Instruction::print_line() {
 148   InstructionPrinter ip;
 149   ip.print_line(this);
 150 }
 151 
 152 
 153 void Instruction::print(InstructionPrinter& ip) {
 154   ip.print_head();
 155   ip.print_line(this);
 156   tty->cr();
 157 }
 158 #endif // PRODUCT
 159 
 160 
 161 // perform constant and interval tests on index value
 162 bool AccessIndexed::compute_needs_range_check() {
 163   if (length()) {
 164     Constant* clength = length()->as_Constant();
 165     Constant* cindex = index()->as_Constant();
 166     if (clength && cindex) {
 167       IntConstant* l = clength->type()->as_IntConstant();
 168       IntConstant* i = cindex->type()->as_IntConstant();
 169       if (l && i && i->value() < l->value() && i->value() >= 0) {
 170         return false;
 171       }
 172     }
 173   }
 174 
 175   if (!this->check_flag(NeedsRangeCheckFlag)) {
 176     return false;
 177   }
 178 
 179   return true;
 180 }
 181 
 182 
 183 ciType* Constant::exact_type() const {
 184   if (type()->is_object() && type()->as_ObjectType()->is_loaded()) {
 185     return type()->as_ObjectType()->exact_type();
 186   }
 187   return NULL;
 188 }
 189 
 190 ciType* LoadIndexed::exact_type() const {
 191   ciType* array_type = array()->exact_type();
 192   if (array_type != NULL) {
 193     assert(array_type->is_array_klass(), "what else?");
 194     ciArrayKlass* ak = (ciArrayKlass*)array_type;
 195 
 196     if (ak->element_type()->is_instance_klass()) {
 197       ciInstanceKlass* ik = (ciInstanceKlass*)ak->element_type();
 198       if (ik->is_loaded() && ik->is_final()) {
 199         return ik;
 200       }
 201     }
 202   }
 203   return Instruction::exact_type();
 204 }
 205 
 206 
 207 ciType* LoadIndexed::declared_type() const {
 208   ciType* array_type = array()->declared_type();
 209   if (array_type == NULL || !array_type->is_loaded()) {
 210     return NULL;
 211   }
 212   assert(array_type->is_array_klass(), "what else?");
 213   ciArrayKlass* ak = (ciArrayKlass*)array_type;
 214   return ak->element_type();
 215 }
 216 
 217 
 218 ciType* LoadField::declared_type() const {
 219   return field()->type();
 220 }
 221 
 222 
 223 ciType* NewTypeArray::exact_type() const {
 224   return ciTypeArrayKlass::make(elt_type());
 225 }
 226 
 227 ciType* NewObjectArray::exact_type() const {
 228   ciKlass* element_klass = klass();
 229   if (element_klass->is_valuetype()) {
 230     return ciValueArrayKlass::make(element_klass);
 231   } else {
 232     return ciObjArrayKlass::make(element_klass);
 233   }
 234 }
 235 
 236 ciType* NewMultiArray::exact_type() const {
 237   return _klass;
 238 }
 239 
 240 ciType* NewArray::declared_type() const {
 241   return exact_type();
 242 }
 243 
 244 ciType* NewInstance::exact_type() const {
 245   return klass();
 246 }
 247 
 248 ciType* NewInstance::declared_type() const {
 249   return exact_type();
 250 }
 251 
 252 Value NewValueTypeInstance::depends_on() {
 253   if (_depends_on != this) {
 254     if (_depends_on->as_NewValueTypeInstance() != NULL) {
 255       return _depends_on->as_NewValueTypeInstance()->depends_on();
 256     }
 257   }
 258   return _depends_on;
 259 }
 260 
 261 ciType* NewValueTypeInstance::exact_type() const {
 262   return klass();
 263 }
 264 
 265 ciType* NewValueTypeInstance::declared_type() const {
 266   return exact_type();
 267 }
 268 
 269 ciType* CheckCast::declared_type() const {
 270   return klass();
 271 }
 272 
 273 // Implementation of ArithmeticOp
 274 
 275 bool ArithmeticOp::is_commutative() const {
 276   switch (op()) {
 277     case Bytecodes::_iadd: // fall through
 278     case Bytecodes::_ladd: // fall through
 279     case Bytecodes::_fadd: // fall through
 280     case Bytecodes::_dadd: // fall through
 281     case Bytecodes::_imul: // fall through
 282     case Bytecodes::_lmul: // fall through
 283     case Bytecodes::_fmul: // fall through
 284     case Bytecodes::_dmul: return true;
 285     default              : return false;
 286   }
 287 }
 288 
 289 
 290 bool ArithmeticOp::can_trap() const {
 291   switch (op()) {
 292     case Bytecodes::_idiv: // fall through
 293     case Bytecodes::_ldiv: // fall through
 294     case Bytecodes::_irem: // fall through
 295     case Bytecodes::_lrem: return true;
 296     default              : return false;
 297   }
 298 }
 299 
 300 
 301 // Implementation of LogicOp
 302 
 303 bool LogicOp::is_commutative() const {
 304 #ifdef ASSERT
 305   switch (op()) {
 306     case Bytecodes::_iand: // fall through
 307     case Bytecodes::_land: // fall through
 308     case Bytecodes::_ior : // fall through
 309     case Bytecodes::_lor : // fall through
 310     case Bytecodes::_ixor: // fall through
 311     case Bytecodes::_lxor: break;
 312     default              : ShouldNotReachHere(); break;
 313   }
 314 #endif
 315   // all LogicOps are commutative
 316   return true;
 317 }
 318 
 319 
 320 // Implementation of IfOp
 321 
 322 bool IfOp::is_commutative() const {
 323   return cond() == eql || cond() == neq;
 324 }
 325 
 326 
 327 // Implementation of StateSplit
 328 
 329 void StateSplit::substitute(BlockList& list, BlockBegin* old_block, BlockBegin* new_block) {
 330   NOT_PRODUCT(bool assigned = false;)
 331   for (int i = 0; i < list.length(); i++) {
 332     BlockBegin** b = list.adr_at(i);
 333     if (*b == old_block) {
 334       *b = new_block;
 335       NOT_PRODUCT(assigned = true;)
 336     }
 337   }
 338   assert(assigned == true, "should have assigned at least once");
 339 }
 340 
 341 
 342 IRScope* StateSplit::scope() const {
 343   return _state->scope();
 344 }
 345 
 346 
 347 void StateSplit::state_values_do(ValueVisitor* f) {
 348   Instruction::state_values_do(f);
 349   if (state() != NULL) state()->values_do(f);
 350 }
 351 
 352 
 353 void BlockBegin::state_values_do(ValueVisitor* f) {
 354   StateSplit::state_values_do(f);
 355 
 356   if (is_set(BlockBegin::exception_entry_flag)) {
 357     for (int i = 0; i < number_of_exception_states(); i++) {
 358       exception_state_at(i)->values_do(f);
 359     }
 360   }
 361 }
 362 
 363 
 364 // Implementation of Invoke
 365 
 366 
 367 Invoke::Invoke(Bytecodes::Code code, ValueType* result_type, Value recv, Values* args,
 368                int vtable_index, ciMethod* target, ValueStack* state_before)
 369   : StateSplit(result_type, state_before)
 370   , _code(code)
 371   , _recv(recv)
 372   , _args(args)
 373   , _vtable_index(vtable_index)
 374   , _target(target)
 375 {
 376   set_flag(TargetIsLoadedFlag,   target->is_loaded());
 377   set_flag(TargetIsFinalFlag,    target_is_loaded() && target->is_final_method());
 378   set_flag(TargetIsStrictfpFlag, target_is_loaded() && target->is_strict());
 379 
 380   assert(args != NULL, "args must exist");
 381 #ifdef ASSERT
 382   AssertValues assert_value;
 383   values_do(&assert_value);
 384 #endif
 385 
 386   // provide an initial guess of signature size.
 387   _signature = new BasicTypeList(number_of_arguments() + (has_receiver() ? 1 : 0));
 388   if (has_receiver()) {
 389     _signature->append(as_BasicType(receiver()->type()));
 390   }
 391   for (int i = 0; i < number_of_arguments(); i++) {
 392     ValueType* t = argument_at(i)->type();
 393     BasicType bt = as_BasicType(t);
 394     _signature->append(bt);
 395   }
 396 }
 397 
 398 
 399 void Invoke::state_values_do(ValueVisitor* f) {
 400   StateSplit::state_values_do(f);
 401   if (state_before() != NULL) state_before()->values_do(f);
 402   if (state()        != NULL) state()->values_do(f);
 403 }
 404 
 405 ciType* Invoke::declared_type() const {
 406   ciSignature* declared_signature = state()->scope()->method()->get_declared_signature_at_bci(state()->bci());
 407   ciType *t = declared_signature->return_type();
 408   assert(t->basic_type() != T_VOID, "need return value of void method?");
 409   return t;
 410 }
 411 
 412 // Implementation of Contant
 413 intx Constant::hash() const {
 414   if (state_before() == NULL) {
 415     switch (type()->tag()) {
 416     case intTag:
 417       return HASH2(name(), type()->as_IntConstant()->value());
 418     case addressTag:
 419       return HASH2(name(), type()->as_AddressConstant()->value());
 420     case longTag:
 421       {
 422         jlong temp = type()->as_LongConstant()->value();
 423         return HASH3(name(), high(temp), low(temp));
 424       }
 425     case floatTag:
 426       return HASH2(name(), jint_cast(type()->as_FloatConstant()->value()));
 427     case doubleTag:
 428       {
 429         jlong temp = jlong_cast(type()->as_DoubleConstant()->value());
 430         return HASH3(name(), high(temp), low(temp));
 431       }
 432     case objectTag:
 433       assert(type()->as_ObjectType()->is_loaded(), "can't handle unloaded values");
 434       return HASH2(name(), type()->as_ObjectType()->constant_value());
 435     case metaDataTag:
 436       assert(type()->as_MetadataType()->is_loaded(), "can't handle unloaded values");
 437       return HASH2(name(), type()->as_MetadataType()->constant_value());
 438     default:
 439       ShouldNotReachHere();
 440     }
 441   }
 442   return 0;
 443 }
 444 
 445 bool Constant::is_equal(Value v) const {
 446   if (v->as_Constant() == NULL) return false;
 447 
 448   switch (type()->tag()) {
 449     case intTag:
 450       {
 451         IntConstant* t1 =    type()->as_IntConstant();
 452         IntConstant* t2 = v->type()->as_IntConstant();
 453         return (t1 != NULL && t2 != NULL &&
 454                 t1->value() == t2->value());
 455       }
 456     case longTag:
 457       {
 458         LongConstant* t1 =    type()->as_LongConstant();
 459         LongConstant* t2 = v->type()->as_LongConstant();
 460         return (t1 != NULL && t2 != NULL &&
 461                 t1->value() == t2->value());
 462       }
 463     case floatTag:
 464       {
 465         FloatConstant* t1 =    type()->as_FloatConstant();
 466         FloatConstant* t2 = v->type()->as_FloatConstant();
 467         return (t1 != NULL && t2 != NULL &&
 468                 jint_cast(t1->value()) == jint_cast(t2->value()));
 469       }
 470     case doubleTag:
 471       {
 472         DoubleConstant* t1 =    type()->as_DoubleConstant();
 473         DoubleConstant* t2 = v->type()->as_DoubleConstant();
 474         return (t1 != NULL && t2 != NULL &&
 475                 jlong_cast(t1->value()) == jlong_cast(t2->value()));
 476       }
 477     case objectTag:
 478       {
 479         ObjectType* t1 =    type()->as_ObjectType();
 480         ObjectType* t2 = v->type()->as_ObjectType();
 481         return (t1 != NULL && t2 != NULL &&
 482                 t1->is_loaded() && t2->is_loaded() &&
 483                 t1->constant_value() == t2->constant_value());
 484       }
 485     case metaDataTag:
 486       {
 487         MetadataType* t1 =    type()->as_MetadataType();
 488         MetadataType* t2 = v->type()->as_MetadataType();
 489         return (t1 != NULL && t2 != NULL &&
 490                 t1->is_loaded() && t2->is_loaded() &&
 491                 t1->constant_value() == t2->constant_value());
 492       }
 493     default:
 494       return false;
 495   }
 496 }
 497 
 498 Constant::CompareResult Constant::compare(Instruction::Condition cond, Value right) const {
 499   Constant* rc = right->as_Constant();
 500   // other is not a constant
 501   if (rc == NULL) return not_comparable;
 502 
 503   ValueType* lt = type();
 504   ValueType* rt = rc->type();
 505   // different types
 506   if (lt->base() != rt->base()) return not_comparable;
 507   switch (lt->tag()) {
 508   case intTag: {
 509     int x = lt->as_IntConstant()->value();
 510     int y = rt->as_IntConstant()->value();
 511     switch (cond) {
 512     case If::eql: return x == y ? cond_true : cond_false;
 513     case If::neq: return x != y ? cond_true : cond_false;
 514     case If::lss: return x <  y ? cond_true : cond_false;
 515     case If::leq: return x <= y ? cond_true : cond_false;
 516     case If::gtr: return x >  y ? cond_true : cond_false;
 517     case If::geq: return x >= y ? cond_true : cond_false;
 518     default     : break;
 519     }
 520     break;
 521   }
 522   case longTag: {
 523     jlong x = lt->as_LongConstant()->value();
 524     jlong y = rt->as_LongConstant()->value();
 525     switch (cond) {
 526     case If::eql: return x == y ? cond_true : cond_false;
 527     case If::neq: return x != y ? cond_true : cond_false;
 528     case If::lss: return x <  y ? cond_true : cond_false;
 529     case If::leq: return x <= y ? cond_true : cond_false;
 530     case If::gtr: return x >  y ? cond_true : cond_false;
 531     case If::geq: return x >= y ? cond_true : cond_false;
 532     default     : break;
 533     }
 534     break;
 535   }
 536   case objectTag: {
 537     ciObject* xvalue = lt->as_ObjectType()->constant_value();
 538     ciObject* yvalue = rt->as_ObjectType()->constant_value();
 539     assert(xvalue != NULL && yvalue != NULL, "not constants");
 540     if (xvalue->is_loaded() && yvalue->is_loaded()) {
 541       switch (cond) {
 542       case If::eql: return xvalue == yvalue ? cond_true : cond_false;
 543       case If::neq: return xvalue != yvalue ? cond_true : cond_false;
 544       default     : break;
 545       }
 546     }
 547     break;
 548   }
 549   case metaDataTag: {
 550     ciMetadata* xvalue = lt->as_MetadataType()->constant_value();
 551     ciMetadata* yvalue = rt->as_MetadataType()->constant_value();
 552     assert(xvalue != NULL && yvalue != NULL, "not constants");
 553     if (xvalue->is_loaded() && yvalue->is_loaded()) {
 554       switch (cond) {
 555       case If::eql: return xvalue == yvalue ? cond_true : cond_false;
 556       case If::neq: return xvalue != yvalue ? cond_true : cond_false;
 557       default     : break;
 558       }
 559     }
 560     break;
 561   }
 562   default:
 563     break;
 564   }
 565   return not_comparable;
 566 }
 567 
 568 
 569 // Implementation of BlockBegin
 570 
 571 void BlockBegin::set_end(BlockEnd* end) {
 572   assert(end != NULL, "should not reset block end to NULL");
 573   if (end == _end) {
 574     return;
 575   }
 576   clear_end();
 577 
 578   // Set the new end
 579   _end = end;
 580 
 581   _successors.clear();
 582   // Now reset successors list based on BlockEnd
 583   for (int i = 0; i < end->number_of_sux(); i++) {
 584     BlockBegin* sux = end->sux_at(i);
 585     _successors.append(sux);
 586     sux->_predecessors.append(this);
 587   }
 588   _end->set_begin(this);
 589 }
 590 
 591 
 592 void BlockBegin::clear_end() {
 593   // Must make the predecessors/successors match up with the
 594   // BlockEnd's notion.
 595   if (_end != NULL) {
 596     // disconnect from the old end
 597     _end->set_begin(NULL);
 598 
 599     // disconnect this block from it's current successors
 600     for (int i = 0; i < _successors.length(); i++) {
 601       _successors.at(i)->remove_predecessor(this);
 602     }
 603     _end = NULL;
 604   }
 605 }
 606 
 607 
 608 void BlockBegin::disconnect_edge(BlockBegin* from, BlockBegin* to) {
 609   // disconnect any edges between from and to
 610 #ifndef PRODUCT
 611   if (PrintIR && Verbose) {
 612     tty->print_cr("Disconnected edge B%d -> B%d", from->block_id(), to->block_id());
 613   }
 614 #endif
 615   for (int s = 0; s < from->number_of_sux();) {
 616     BlockBegin* sux = from->sux_at(s);
 617     if (sux == to) {
 618       int index = sux->_predecessors.find(from);
 619       if (index >= 0) {
 620         sux->_predecessors.remove_at(index);
 621       }
 622       from->_successors.remove_at(s);
 623     } else {
 624       s++;
 625     }
 626   }
 627 }
 628 
 629 
 630 void BlockBegin::disconnect_from_graph() {
 631   // disconnect this block from all other blocks
 632   for (int p = 0; p < number_of_preds(); p++) {
 633     pred_at(p)->remove_successor(this);
 634   }
 635   for (int s = 0; s < number_of_sux(); s++) {
 636     sux_at(s)->remove_predecessor(this);
 637   }
 638 }
 639 
 640 void BlockBegin::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
 641   // modify predecessors before substituting successors
 642   for (int i = 0; i < number_of_sux(); i++) {
 643     if (sux_at(i) == old_sux) {
 644       // remove old predecessor before adding new predecessor
 645       // otherwise there is a dead predecessor in the list
 646       new_sux->remove_predecessor(old_sux);
 647       new_sux->add_predecessor(this);
 648     }
 649   }
 650   old_sux->remove_predecessor(this);
 651   end()->substitute_sux(old_sux, new_sux);
 652 }
 653 
 654 
 655 
 656 // In general it is not possible to calculate a value for the field "depth_first_number"
 657 // of the inserted block, without recomputing the values of the other blocks
 658 // in the CFG. Therefore the value of "depth_first_number" in BlockBegin becomes meaningless.
 659 BlockBegin* BlockBegin::insert_block_between(BlockBegin* sux) {
 660   int bci = sux->bci();
 661   // critical edge splitting may introduce a goto after a if and array
 662   // bound check elimination may insert a predicate between the if and
 663   // goto. The bci of the goto can't be the one of the if otherwise
 664   // the state and bci are inconsistent and a deoptimization triggered
 665   // by the predicate would lead to incorrect execution/a crash.
 666   BlockBegin* new_sux = new BlockBegin(bci);
 667 
 668   // mark this block (special treatment when block order is computed)
 669   new_sux->set(critical_edge_split_flag);
 670 
 671   // This goto is not a safepoint.
 672   Goto* e = new Goto(sux, false);
 673   new_sux->set_next(e, bci);
 674   new_sux->set_end(e);
 675   // setup states
 676   ValueStack* s = end()->state();
 677   new_sux->set_state(s->copy(s->kind(), bci));
 678   e->set_state(s->copy(s->kind(), bci));
 679   assert(new_sux->state()->locals_size() == s->locals_size(), "local size mismatch!");
 680   assert(new_sux->state()->stack_size() == s->stack_size(), "stack size mismatch!");
 681   assert(new_sux->state()->locks_size() == s->locks_size(), "locks size mismatch!");
 682 
 683   // link predecessor to new block
 684   end()->substitute_sux(sux, new_sux);
 685 
 686   // The ordering needs to be the same, so remove the link that the
 687   // set_end call above added and substitute the new_sux for this
 688   // block.
 689   sux->remove_predecessor(new_sux);
 690 
 691   // the successor could be the target of a switch so it might have
 692   // multiple copies of this predecessor, so substitute the new_sux
 693   // for the first and delete the rest.
 694   bool assigned = false;
 695   BlockList& list = sux->_predecessors;
 696   for (int i = 0; i < list.length(); i++) {
 697     BlockBegin** b = list.adr_at(i);
 698     if (*b == this) {
 699       if (assigned) {
 700         list.remove_at(i);
 701         // reprocess this index
 702         i--;
 703       } else {
 704         assigned = true;
 705         *b = new_sux;
 706       }
 707       // link the new block back to it's predecessors.
 708       new_sux->add_predecessor(this);
 709     }
 710   }
 711   assert(assigned == true, "should have assigned at least once");
 712   return new_sux;
 713 }
 714 
 715 
 716 void BlockBegin::remove_successor(BlockBegin* pred) {
 717   int idx;
 718   while ((idx = _successors.find(pred)) >= 0) {
 719     _successors.remove_at(idx);
 720   }
 721 }
 722 
 723 
 724 void BlockBegin::add_predecessor(BlockBegin* pred) {
 725   _predecessors.append(pred);
 726 }
 727 
 728 
 729 void BlockBegin::remove_predecessor(BlockBegin* pred) {
 730   int idx;
 731   while ((idx = _predecessors.find(pred)) >= 0) {
 732     _predecessors.remove_at(idx);
 733   }
 734 }
 735 
 736 
 737 void BlockBegin::add_exception_handler(BlockBegin* b) {
 738   assert(b != NULL && (b->is_set(exception_entry_flag)), "exception handler must exist");
 739   // add only if not in the list already
 740   if (!_exception_handlers.contains(b)) _exception_handlers.append(b);
 741 }
 742 
 743 int BlockBegin::add_exception_state(ValueStack* state) {
 744   assert(is_set(exception_entry_flag), "only for xhandlers");
 745   if (_exception_states == NULL) {
 746     _exception_states = new ValueStackStack(4);
 747   }
 748   _exception_states->append(state);
 749   return _exception_states->length() - 1;
 750 }
 751 
 752 
 753 void BlockBegin::iterate_preorder(boolArray& mark, BlockClosure* closure) {
 754   if (!mark.at(block_id())) {
 755     mark.at_put(block_id(), true);
 756     closure->block_do(this);
 757     BlockEnd* e = end(); // must do this after block_do because block_do may change it!
 758     { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_preorder(mark, closure); }
 759     { for (int i = e->number_of_sux            () - 1; i >= 0; i--) e->sux_at           (i)->iterate_preorder(mark, closure); }
 760   }
 761 }
 762 
 763 
 764 void BlockBegin::iterate_postorder(boolArray& mark, BlockClosure* closure) {
 765   if (!mark.at(block_id())) {
 766     mark.at_put(block_id(), true);
 767     BlockEnd* e = end();
 768     { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_postorder(mark, closure); }
 769     { for (int i = e->number_of_sux            () - 1; i >= 0; i--) e->sux_at           (i)->iterate_postorder(mark, closure); }
 770     closure->block_do(this);
 771   }
 772 }
 773 
 774 
 775 void BlockBegin::iterate_preorder(BlockClosure* closure) {
 776   int mark_len = number_of_blocks();
 777   boolArray mark(mark_len, mark_len, false);
 778   iterate_preorder(mark, closure);
 779 }
 780 
 781 
 782 void BlockBegin::iterate_postorder(BlockClosure* closure) {
 783   int mark_len = number_of_blocks();
 784   boolArray mark(mark_len, mark_len, false);
 785   iterate_postorder(mark, closure);
 786 }
 787 
 788 
 789 void BlockBegin::block_values_do(ValueVisitor* f) {
 790   for (Instruction* n = this; n != NULL; n = n->next()) n->values_do(f);
 791 }
 792 
 793 
 794 #ifndef PRODUCT
 795    #define TRACE_PHI(code) if (PrintPhiFunctions) { code; }
 796 #else
 797    #define TRACE_PHI(coce)
 798 #endif
 799 
 800 
 801 bool BlockBegin::try_merge(ValueStack* new_state) {
 802   TRACE_PHI(tty->print_cr("********** try_merge for block B%d", block_id()));
 803 
 804   // local variables used for state iteration
 805   int index;
 806   Value new_value, existing_value;
 807 
 808   ValueStack* existing_state = state();
 809   if (existing_state == NULL) {
 810     TRACE_PHI(tty->print_cr("first call of try_merge for this block"));
 811 
 812     if (is_set(BlockBegin::was_visited_flag)) {
 813       // this actually happens for complicated jsr/ret structures
 814       return false; // BAILOUT in caller
 815     }
 816 
 817     // copy state because it is altered
 818     new_state = new_state->copy(ValueStack::BlockBeginState, bci());
 819 
 820     // Use method liveness to invalidate dead locals
 821     MethodLivenessResult liveness = new_state->scope()->method()->liveness_at_bci(bci());
 822     if (liveness.is_valid()) {
 823       assert((int)liveness.size() == new_state->locals_size(), "error in use of liveness");
 824 
 825       for_each_local_value(new_state, index, new_value) {
 826         if (!liveness.at(index) || new_value->type()->is_illegal()) {
 827           new_state->invalidate_local(index);
 828           TRACE_PHI(tty->print_cr("invalidating dead local %d", index));
 829         }
 830       }
 831     }
 832 
 833     if (is_set(BlockBegin::parser_loop_header_flag)) {
 834       TRACE_PHI(tty->print_cr("loop header block, initializing phi functions"));
 835 
 836       for_each_stack_value(new_state, index, new_value) {
 837         new_state->setup_phi_for_stack(this, index, NULL, new_value);
 838         TRACE_PHI(tty->print_cr("creating phi-function %c%d for stack %d", new_state->stack_at(index)->type()->tchar(), new_state->stack_at(index)->id(), index));
 839       }
 840 
 841       BitMap& requires_phi_function = new_state->scope()->requires_phi_function();
 842 
 843       for_each_local_value(new_state, index, new_value) {
 844         bool requires_phi = requires_phi_function.at(index) || (new_value->type()->is_double_word() && requires_phi_function.at(index + 1));
 845         if (requires_phi || !SelectivePhiFunctions) {
 846           new_state->setup_phi_for_local(this, index, NULL, new_value);
 847           TRACE_PHI(tty->print_cr("creating phi-function %c%d for local %d", new_state->local_at(index)->type()->tchar(), new_state->local_at(index)->id(), index));
 848         }
 849       }
 850     }
 851 
 852     // initialize state of block
 853     set_state(new_state);
 854 
 855   } else if (existing_state->is_same(new_state)) {
 856     TRACE_PHI(tty->print_cr("exisiting state found"));
 857 
 858     assert(existing_state->scope() == new_state->scope(), "not matching");
 859     assert(existing_state->locals_size() == new_state->locals_size(), "not matching");
 860     assert(existing_state->stack_size() == new_state->stack_size(), "not matching");
 861 
 862     if (is_set(BlockBegin::was_visited_flag)) {
 863       TRACE_PHI(tty->print_cr("loop header block, phis must be present"));
 864 
 865       if (!is_set(BlockBegin::parser_loop_header_flag)) {
 866         // this actually happens for complicated jsr/ret structures
 867         return false; // BAILOUT in caller
 868       }
 869 
 870       for_each_local_value(existing_state, index, existing_value) {
 871         Value new_value = new_state->local_at(index);
 872         if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
 873           Phi* existing_phi = existing_value->as_Phi();
 874           if (existing_phi == NULL) {
 875             return false; // BAILOUT in caller
 876           }
 877           // Invalidate the phi function here. This case is very rare except for
 878           // JVMTI capability "can_access_local_variables".
 879           // In really rare cases we will bail out in LIRGenerator::move_to_phi.
 880           existing_phi->make_illegal();
 881           existing_state->invalidate_local(index);
 882           TRACE_PHI(tty->print_cr("invalidating local %d because of type mismatch", index));
 883         }
 884       }
 885 
 886 #ifdef ASSERT
 887       // check that all necessary phi functions are present
 888       for_each_stack_value(existing_state, index, existing_value) {
 889         assert(existing_value->as_Phi() != NULL && existing_value->as_Phi()->block() == this, "phi function required");
 890       }
 891       for_each_local_value(existing_state, index, existing_value) {
 892         assert(existing_value == new_state->local_at(index) || (existing_value->as_Phi() != NULL && existing_value->as_Phi()->as_Phi()->block() == this), "phi function required");
 893       }
 894 #endif
 895 
 896     } else {
 897       TRACE_PHI(tty->print_cr("creating phi functions on demand"));
 898 
 899       // create necessary phi functions for stack
 900       for_each_stack_value(existing_state, index, existing_value) {
 901         Value new_value = new_state->stack_at(index);
 902         Phi* existing_phi = existing_value->as_Phi();
 903 
 904         if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
 905           existing_state->setup_phi_for_stack(this, index, existing_value, new_value);
 906           TRACE_PHI(tty->print_cr("creating phi-function %c%d for stack %d", existing_state->stack_at(index)->type()->tchar(), existing_state->stack_at(index)->id(), index));
 907         }
 908       }
 909 
 910       // create necessary phi functions for locals
 911       for_each_local_value(existing_state, index, existing_value) {
 912         Value new_value = new_state->local_at(index);
 913         Phi* existing_phi = existing_value->as_Phi();
 914 
 915         if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
 916           existing_state->invalidate_local(index);
 917           TRACE_PHI(tty->print_cr("invalidating local %d because of type mismatch", index));
 918         } else if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
 919           existing_state->setup_phi_for_local(this, index, existing_value, new_value);
 920           TRACE_PHI(tty->print_cr("creating phi-function %c%d for local %d", existing_state->local_at(index)->type()->tchar(), existing_state->local_at(index)->id(), index));
 921         }
 922       }
 923     }
 924 
 925     assert(existing_state->caller_state() == new_state->caller_state(), "caller states must be equal");
 926 
 927   } else {
 928     assert(false, "stack or locks not matching (invalid bytecodes)");
 929     return false;
 930   }
 931 
 932   TRACE_PHI(tty->print_cr("********** try_merge for block B%d successful", block_id()));
 933 
 934   return true;
 935 }
 936 
 937 
 938 #ifndef PRODUCT
 939 void BlockBegin::print_block() {
 940   InstructionPrinter ip;
 941   print_block(ip, false);
 942 }
 943 
 944 
 945 void BlockBegin::print_block(InstructionPrinter& ip, bool live_only) {
 946   ip.print_instr(this); tty->cr();
 947   ip.print_stack(this->state()); tty->cr();
 948   ip.print_inline_level(this);
 949   ip.print_head();
 950   for (Instruction* n = next(); n != NULL; n = n->next()) {
 951     if (!live_only || n->is_pinned() || n->use_count() > 0) {
 952       ip.print_line(n);
 953     }
 954   }
 955   tty->cr();
 956 }
 957 #endif // PRODUCT
 958 
 959 
 960 // Implementation of BlockList
 961 
 962 void BlockList::iterate_forward (BlockClosure* closure) {
 963   const int l = length();
 964   for (int i = 0; i < l; i++) closure->block_do(at(i));
 965 }
 966 
 967 
 968 void BlockList::iterate_backward(BlockClosure* closure) {
 969   for (int i = length() - 1; i >= 0; i--) closure->block_do(at(i));
 970 }
 971 
 972 
 973 void BlockList::blocks_do(void f(BlockBegin*)) {
 974   for (int i = length() - 1; i >= 0; i--) f(at(i));
 975 }
 976 
 977 
 978 void BlockList::values_do(ValueVisitor* f) {
 979   for (int i = length() - 1; i >= 0; i--) at(i)->block_values_do(f);
 980 }
 981 
 982 
 983 #ifndef PRODUCT
 984 void BlockList::print(bool cfg_only, bool live_only) {
 985   InstructionPrinter ip;
 986   for (int i = 0; i < length(); i++) {
 987     BlockBegin* block = at(i);
 988     if (cfg_only) {
 989       ip.print_instr(block); tty->cr();
 990     } else {
 991       block->print_block(ip, live_only);
 992     }
 993   }
 994 }
 995 #endif // PRODUCT
 996 
 997 
 998 // Implementation of BlockEnd
 999 
1000 void BlockEnd::set_begin(BlockBegin* begin) {
1001   BlockList* sux = NULL;
1002   if (begin != NULL) {
1003     sux = begin->successors();
1004   } else if (this->begin() != NULL) {
1005     // copy our sux list
1006     BlockList* sux = new BlockList(this->begin()->number_of_sux());
1007     for (int i = 0; i < this->begin()->number_of_sux(); i++) {
1008       sux->append(this->begin()->sux_at(i));
1009     }
1010   }
1011   _sux = sux;
1012 }
1013 
1014 
1015 void BlockEnd::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
1016   substitute(*_sux, old_sux, new_sux);
1017 }
1018 
1019 
1020 // Implementation of Phi
1021 
1022 // Normal phi functions take their operands from the last instruction of the
1023 // predecessor. Special handling is needed for xhanlder entries because there
1024 // the state of arbitrary instructions are needed.
1025 
1026 Value Phi::operand_at(int i) const {
1027   ValueStack* state;
1028   if (_block->is_set(BlockBegin::exception_entry_flag)) {
1029     state = _block->exception_state_at(i);
1030   } else {
1031     state = _block->pred_at(i)->end()->state();
1032   }
1033   assert(state != NULL, "");
1034 
1035   if (is_local()) {
1036     return state->local_at(local_index());
1037   } else {
1038     return state->stack_at(stack_index());
1039   }
1040 }
1041 
1042 
1043 int Phi::operand_count() const {
1044   if (_block->is_set(BlockBegin::exception_entry_flag)) {
1045     return _block->number_of_exception_states();
1046   } else {
1047     return _block->number_of_preds();
1048   }
1049 }
1050 
1051 #ifdef ASSERT
1052 // Constructor of Assert
1053 Assert::Assert(Value x, Condition cond, bool unordered_is_true, Value y) : Instruction(illegalType)
1054   , _x(x)
1055   , _cond(cond)
1056   , _y(y)
1057 {
1058   set_flag(UnorderedIsTrueFlag, unordered_is_true);
1059   assert(x->type()->tag() == y->type()->tag(), "types must match");
1060   pin();
1061 
1062   stringStream strStream;
1063   Compilation::current()->method()->print_name(&strStream);
1064 
1065   stringStream strStream1;
1066   InstructionPrinter ip1(1, &strStream1);
1067   ip1.print_instr(x);
1068 
1069   stringStream strStream2;
1070   InstructionPrinter ip2(1, &strStream2);
1071   ip2.print_instr(y);
1072 
1073   stringStream ss;
1074   ss.print("Assertion %s %s %s in method %s", strStream1.as_string(), ip2.cond_name(cond), strStream2.as_string(), strStream.as_string());
1075 
1076   _message = ss.as_string();
1077 }
1078 #endif
1079 
1080 void RangeCheckPredicate::check_state() {
1081   assert(state()->kind() != ValueStack::EmptyExceptionState && state()->kind() != ValueStack::ExceptionState, "will deopt with empty state");
1082 }
1083 
1084 void ProfileInvoke::state_values_do(ValueVisitor* f) {
1085   if (state() != NULL) state()->values_do(f);
1086 }