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