1 /*
   2  * Copyright (c) 1999, 2013, 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   }
 243   return false;
 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   }
 254   return false;
 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();
 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   ciType *t = _target->signature()->return_type();
 364   assert(t->basic_type() != T_VOID, "need return value of void method?");
 365   return t;
 366 }
 367 
 368 // Implementation of Contant
 369 intx Constant::hash() const {
 370   if (state_before() == NULL) {
 371     switch (type()->tag()) {
 372     case intTag:
 373       return HASH2(name(), type()->as_IntConstant()->value());
 374     case addressTag:
 375       return HASH2(name(), type()->as_AddressConstant()->value());
 376     case longTag:
 377       {
 378         jlong temp = type()->as_LongConstant()->value();
 379         return HASH3(name(), high(temp), low(temp));
 380       }
 381     case floatTag:
 382       return HASH2(name(), jint_cast(type()->as_FloatConstant()->value()));
 383     case doubleTag:
 384       {
 385         jlong temp = jlong_cast(type()->as_DoubleConstant()->value());
 386         return HASH3(name(), high(temp), low(temp));
 387       }
 388     case objectTag:
 389       assert(type()->as_ObjectType()->is_loaded(), "can't handle unloaded values");
 390       return HASH2(name(), type()->as_ObjectType()->constant_value());
 391     case metaDataTag:
 392       assert(type()->as_MetadataType()->is_loaded(), "can't handle unloaded values");
 393       return HASH2(name(), type()->as_MetadataType()->constant_value());
 394     default:
 395       ShouldNotReachHere();
 396     }
 397   }
 398   return 0;
 399 }
 400 
 401 bool Constant::is_equal(Value v) const {
 402   if (v->as_Constant() == NULL) return false;
 403 
 404   switch (type()->tag()) {
 405     case intTag:
 406       {
 407         IntConstant* t1 =    type()->as_IntConstant();
 408         IntConstant* t2 = v->type()->as_IntConstant();
 409         return (t1 != NULL && t2 != NULL &&
 410                 t1->value() == t2->value());
 411       }
 412     case longTag:
 413       {
 414         LongConstant* t1 =    type()->as_LongConstant();
 415         LongConstant* t2 = v->type()->as_LongConstant();
 416         return (t1 != NULL && t2 != NULL &&
 417                 t1->value() == t2->value());
 418       }
 419     case floatTag:
 420       {
 421         FloatConstant* t1 =    type()->as_FloatConstant();
 422         FloatConstant* t2 = v->type()->as_FloatConstant();
 423         return (t1 != NULL && t2 != NULL &&
 424                 jint_cast(t1->value()) == jint_cast(t2->value()));
 425       }
 426     case doubleTag:
 427       {
 428         DoubleConstant* t1 =    type()->as_DoubleConstant();
 429         DoubleConstant* t2 = v->type()->as_DoubleConstant();
 430         return (t1 != NULL && t2 != NULL &&
 431                 jlong_cast(t1->value()) == jlong_cast(t2->value()));
 432       }
 433     case objectTag:
 434       {
 435         ObjectType* t1 =    type()->as_ObjectType();
 436         ObjectType* t2 = v->type()->as_ObjectType();
 437         return (t1 != NULL && t2 != NULL &&
 438                 t1->is_loaded() && t2->is_loaded() &&
 439                 t1->constant_value() == t2->constant_value());
 440       }
 441     case metaDataTag:
 442       {
 443         MetadataType* t1 =    type()->as_MetadataType();
 444         MetadataType* t2 = v->type()->as_MetadataType();
 445         return (t1 != NULL && t2 != NULL &&
 446                 t1->is_loaded() && t2->is_loaded() &&
 447                 t1->constant_value() == t2->constant_value());
 448       }
 449   }
 450   return false;
 451 }
 452 
 453 Constant::CompareResult Constant::compare(Instruction::Condition cond, Value right) const {
 454   Constant* rc = right->as_Constant();
 455   // other is not a constant
 456   if (rc == NULL) return not_comparable;
 457 
 458   ValueType* lt = type();
 459   ValueType* rt = rc->type();
 460   // different types
 461   if (lt->base() != rt->base()) return not_comparable;
 462   switch (lt->tag()) {
 463   case intTag: {
 464     int x = lt->as_IntConstant()->value();
 465     int y = rt->as_IntConstant()->value();
 466     switch (cond) {
 467     case If::eql: return x == y ? cond_true : cond_false;
 468     case If::neq: return x != y ? cond_true : cond_false;
 469     case If::lss: return x <  y ? cond_true : cond_false;
 470     case If::leq: return x <= y ? cond_true : cond_false;
 471     case If::gtr: return x >  y ? cond_true : cond_false;
 472     case If::geq: return x >= y ? cond_true : cond_false;
 473     }
 474     break;
 475   }
 476   case longTag: {
 477     jlong x = lt->as_LongConstant()->value();
 478     jlong y = rt->as_LongConstant()->value();
 479     switch (cond) {
 480     case If::eql: return x == y ? cond_true : cond_false;
 481     case If::neq: return x != y ? cond_true : cond_false;
 482     case If::lss: return x <  y ? cond_true : cond_false;
 483     case If::leq: return x <= y ? cond_true : cond_false;
 484     case If::gtr: return x >  y ? cond_true : cond_false;
 485     case If::geq: return x >= y ? cond_true : cond_false;
 486     }
 487     break;
 488   }
 489   case objectTag: {
 490     ciObject* xvalue = lt->as_ObjectType()->constant_value();
 491     ciObject* yvalue = rt->as_ObjectType()->constant_value();
 492     assert(xvalue != NULL && yvalue != NULL, "not constants");
 493     if (xvalue->is_loaded() && yvalue->is_loaded()) {
 494       switch (cond) {
 495       case If::eql: return xvalue == yvalue ? cond_true : cond_false;
 496       case If::neq: return xvalue != yvalue ? cond_true : cond_false;
 497       }
 498     }
 499     break;
 500   }
 501   case metaDataTag: {
 502     ciMetadata* xvalue = lt->as_MetadataType()->constant_value();
 503     ciMetadata* yvalue = rt->as_MetadataType()->constant_value();
 504     assert(xvalue != NULL && yvalue != NULL, "not constants");
 505     if (xvalue->is_loaded() && yvalue->is_loaded()) {
 506       switch (cond) {
 507       case If::eql: return xvalue == yvalue ? cond_true : cond_false;
 508       case If::neq: return xvalue != yvalue ? cond_true : cond_false;
 509       }
 510     }
 511     break;
 512   }
 513   }
 514   return not_comparable;
 515 }
 516 
 517 
 518 // Implementation of BlockBegin
 519 
 520 void BlockBegin::set_end(BlockEnd* end) {
 521   assert(end != NULL, "should not reset block end to NULL");
 522   if (end == _end) {
 523     return;
 524   }
 525   clear_end();
 526 
 527   // Set the new end
 528   _end = end;
 529 
 530   _successors.clear();
 531   // Now reset successors list based on BlockEnd
 532   for (int i = 0; i < end->number_of_sux(); i++) {
 533     BlockBegin* sux = end->sux_at(i);
 534     _successors.append(sux);
 535     sux->_predecessors.append(this);
 536   }
 537   _end->set_begin(this);
 538 }
 539 
 540 
 541 void BlockBegin::clear_end() {
 542   // Must make the predecessors/successors match up with the
 543   // BlockEnd's notion.
 544   if (_end != NULL) {
 545     // disconnect from the old end
 546     _end->set_begin(NULL);
 547 
 548     // disconnect this block from it's current successors
 549     for (int i = 0; i < _successors.length(); i++) {
 550       _successors.at(i)->remove_predecessor(this);
 551     }
 552     _end = NULL;
 553   }
 554 }
 555 
 556 
 557 void BlockBegin::disconnect_edge(BlockBegin* from, BlockBegin* to) {
 558   // disconnect any edges between from and to
 559 #ifndef PRODUCT
 560   if (PrintIR && Verbose) {
 561     tty->print_cr("Disconnected edge B%d -> B%d", from->block_id(), to->block_id());
 562   }
 563 #endif
 564   for (int s = 0; s < from->number_of_sux();) {
 565     BlockBegin* sux = from->sux_at(s);
 566     if (sux == to) {
 567       int index = sux->_predecessors.index_of(from);
 568       if (index >= 0) {
 569         sux->_predecessors.remove_at(index);
 570       }
 571       from->_successors.remove_at(s);
 572     } else {
 573       s++;
 574     }
 575   }
 576 }
 577 
 578 
 579 void BlockBegin::disconnect_from_graph() {
 580   // disconnect this block from all other blocks
 581   for (int p = 0; p < number_of_preds(); p++) {
 582     pred_at(p)->remove_successor(this);
 583   }
 584   for (int s = 0; s < number_of_sux(); s++) {
 585     sux_at(s)->remove_predecessor(this);
 586   }
 587 }
 588 
 589 void BlockBegin::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
 590   // modify predecessors before substituting successors
 591   for (int i = 0; i < number_of_sux(); i++) {
 592     if (sux_at(i) == old_sux) {
 593       // remove old predecessor before adding new predecessor
 594       // otherwise there is a dead predecessor in the list
 595       new_sux->remove_predecessor(old_sux);
 596       new_sux->add_predecessor(this);
 597     }
 598   }
 599   old_sux->remove_predecessor(this);
 600   end()->substitute_sux(old_sux, new_sux);
 601 }
 602 
 603 
 604 
 605 // In general it is not possible to calculate a value for the field "depth_first_number"
 606 // of the inserted block, without recomputing the values of the other blocks
 607 // in the CFG. Therefore the value of "depth_first_number" in BlockBegin becomes meaningless.
 608 BlockBegin* BlockBegin::insert_block_between(BlockBegin* sux) {
 609   int bci = sux->bci();
 610   // critical edge splitting may introduce a goto after a if and array
 611   // bound check elimination may insert a predicate between the if and
 612   // goto. The bci of the goto can't be the one of the if otherwise
 613   // the state and bci are inconsistent and a deoptimization triggered
 614   // by the predicate would lead to incorrect execution/a crash.
 615   BlockBegin* new_sux = new BlockBegin(bci);
 616 
 617   // mark this block (special treatment when block order is computed)
 618   new_sux->set(critical_edge_split_flag);
 619 
 620   // This goto is not a safepoint.
 621   Goto* e = new Goto(sux, false);
 622   new_sux->set_next(e, bci);
 623   new_sux->set_end(e);
 624   // setup states
 625   ValueStack* s = end()->state();
 626   new_sux->set_state(s->copy(s->kind(), bci));
 627   e->set_state(s->copy(s->kind(), bci));
 628   assert(new_sux->state()->locals_size() == s->locals_size(), "local size mismatch!");
 629   assert(new_sux->state()->stack_size() == s->stack_size(), "stack size mismatch!");
 630   assert(new_sux->state()->locks_size() == s->locks_size(), "locks size mismatch!");
 631 
 632   // link predecessor to new block
 633   end()->substitute_sux(sux, new_sux);
 634 
 635   // The ordering needs to be the same, so remove the link that the
 636   // set_end call above added and substitute the new_sux for this
 637   // block.
 638   sux->remove_predecessor(new_sux);
 639 
 640   // the successor could be the target of a switch so it might have
 641   // multiple copies of this predecessor, so substitute the new_sux
 642   // for the first and delete the rest.
 643   bool assigned = false;
 644   BlockList& list = sux->_predecessors;
 645   for (int i = 0; i < list.length(); i++) {
 646     BlockBegin** b = list.adr_at(i);
 647     if (*b == this) {
 648       if (assigned) {
 649         list.remove_at(i);
 650         // reprocess this index
 651         i--;
 652       } else {
 653         assigned = true;
 654         *b = new_sux;
 655       }
 656       // link the new block back to it's predecessors.
 657       new_sux->add_predecessor(this);
 658     }
 659   }
 660   assert(assigned == true, "should have assigned at least once");
 661   return new_sux;
 662 }
 663 
 664 
 665 void BlockBegin::remove_successor(BlockBegin* pred) {
 666   int idx;
 667   while ((idx = _successors.index_of(pred)) >= 0) {
 668     _successors.remove_at(idx);
 669   }
 670 }
 671 
 672 
 673 void BlockBegin::add_predecessor(BlockBegin* pred) {
 674   _predecessors.append(pred);
 675 }
 676 
 677 
 678 void BlockBegin::remove_predecessor(BlockBegin* pred) {
 679   int idx;
 680   while ((idx = _predecessors.index_of(pred)) >= 0) {
 681     _predecessors.remove_at(idx);
 682   }
 683 }
 684 
 685 
 686 void BlockBegin::add_exception_handler(BlockBegin* b) {
 687   assert(b != NULL && (b->is_set(exception_entry_flag)), "exception handler must exist");
 688   // add only if not in the list already
 689   if (!_exception_handlers.contains(b)) _exception_handlers.append(b);
 690 }
 691 
 692 int BlockBegin::add_exception_state(ValueStack* state) {
 693   assert(is_set(exception_entry_flag), "only for xhandlers");
 694   if (_exception_states == NULL) {
 695     _exception_states = new ValueStackStack(4);
 696   }
 697   _exception_states->append(state);
 698   return _exception_states->length() - 1;
 699 }
 700 
 701 
 702 void BlockBegin::iterate_preorder(boolArray& mark, BlockClosure* closure) {
 703   if (!mark.at(block_id())) {
 704     mark.at_put(block_id(), true);
 705     closure->block_do(this);
 706     BlockEnd* e = end(); // must do this after block_do because block_do may change it!
 707     { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_preorder(mark, closure); }
 708     { for (int i = e->number_of_sux            () - 1; i >= 0; i--) e->sux_at           (i)->iterate_preorder(mark, closure); }
 709   }
 710 }
 711 
 712 
 713 void BlockBegin::iterate_postorder(boolArray& mark, BlockClosure* closure) {
 714   if (!mark.at(block_id())) {
 715     mark.at_put(block_id(), true);
 716     BlockEnd* e = end();
 717     { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_postorder(mark, closure); }
 718     { for (int i = e->number_of_sux            () - 1; i >= 0; i--) e->sux_at           (i)->iterate_postorder(mark, closure); }
 719     closure->block_do(this);
 720   }
 721 }
 722 
 723 
 724 void BlockBegin::iterate_preorder(BlockClosure* closure) {
 725   boolArray mark(number_of_blocks(), false);
 726   iterate_preorder(mark, closure);
 727 }
 728 
 729 
 730 void BlockBegin::iterate_postorder(BlockClosure* closure) {
 731   boolArray mark(number_of_blocks(), false);
 732   iterate_postorder(mark, closure);
 733 }
 734 
 735 
 736 void BlockBegin::block_values_do(ValueVisitor* f) {
 737   for (Instruction* n = this; n != NULL; n = n->next()) n->values_do(f);
 738 }
 739 
 740 
 741 #ifndef PRODUCT
 742    #define TRACE_PHI(code) if (PrintPhiFunctions) { code; }
 743 #else
 744    #define TRACE_PHI(coce)
 745 #endif
 746 
 747 
 748 bool BlockBegin::try_merge(ValueStack* new_state) {
 749   TRACE_PHI(tty->print_cr("********** try_merge for block B%d", block_id()));
 750 
 751   // local variables used for state iteration
 752   int index;
 753   Value new_value, existing_value;
 754 
 755   ValueStack* existing_state = state();
 756   if (existing_state == NULL) {
 757     TRACE_PHI(tty->print_cr("first call of try_merge for this block"));
 758 
 759     if (is_set(BlockBegin::was_visited_flag)) {
 760       // this actually happens for complicated jsr/ret structures
 761       return false; // BAILOUT in caller
 762     }
 763 
 764     // copy state because it is altered
 765     new_state = new_state->copy(ValueStack::BlockBeginState, bci());
 766 
 767     // Use method liveness to invalidate dead locals
 768     MethodLivenessResult liveness = new_state->scope()->method()->liveness_at_bci(bci());
 769     if (liveness.is_valid()) {
 770       assert((int)liveness.size() == new_state->locals_size(), "error in use of liveness");
 771 
 772       for_each_local_value(new_state, index, new_value) {
 773         if (!liveness.at(index) || new_value->type()->is_illegal()) {
 774           new_state->invalidate_local(index);
 775           TRACE_PHI(tty->print_cr("invalidating dead local %d", index));
 776         }
 777       }
 778     }
 779 
 780     if (is_set(BlockBegin::parser_loop_header_flag)) {
 781       TRACE_PHI(tty->print_cr("loop header block, initializing phi functions"));
 782 
 783       for_each_stack_value(new_state, index, new_value) {
 784         new_state->setup_phi_for_stack(this, index);
 785         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));
 786       }
 787 
 788       BitMap requires_phi_function = new_state->scope()->requires_phi_function();
 789 
 790       for_each_local_value(new_state, index, new_value) {
 791         bool requires_phi = requires_phi_function.at(index) || (new_value->type()->is_double_word() && requires_phi_function.at(index + 1));
 792         if (requires_phi || !SelectivePhiFunctions) {
 793           new_state->setup_phi_for_local(this, index);
 794           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));
 795         }
 796       }
 797     }
 798 
 799     // initialize state of block
 800     set_state(new_state);
 801 
 802   } else if (existing_state->is_same(new_state)) {
 803     TRACE_PHI(tty->print_cr("exisiting state found"));
 804 
 805     assert(existing_state->scope() == new_state->scope(), "not matching");
 806     assert(existing_state->locals_size() == new_state->locals_size(), "not matching");
 807     assert(existing_state->stack_size() == new_state->stack_size(), "not matching");
 808 
 809     if (is_set(BlockBegin::was_visited_flag)) {
 810       TRACE_PHI(tty->print_cr("loop header block, phis must be present"));
 811 
 812       if (!is_set(BlockBegin::parser_loop_header_flag)) {
 813         // this actually happens for complicated jsr/ret structures
 814         return false; // BAILOUT in caller
 815       }
 816 
 817       for_each_local_value(existing_state, index, existing_value) {
 818         Value new_value = new_state->local_at(index);
 819         if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
 820           // The old code invalidated the phi function here
 821           // Because dead locals are replaced with NULL, this is a very rare case now, so simply bail out
 822           return false; // BAILOUT in caller
 823         }
 824       }
 825 
 826 #ifdef ASSERT
 827       // check that all necessary phi functions are present
 828       for_each_stack_value(existing_state, index, existing_value) {
 829         assert(existing_value->as_Phi() != NULL && existing_value->as_Phi()->block() == this, "phi function required");
 830       }
 831       for_each_local_value(existing_state, index, existing_value) {
 832         assert(existing_value == new_state->local_at(index) || (existing_value->as_Phi() != NULL && existing_value->as_Phi()->as_Phi()->block() == this), "phi function required");
 833       }
 834 #endif
 835 
 836     } else {
 837       TRACE_PHI(tty->print_cr("creating phi functions on demand"));
 838 
 839       // create necessary phi functions for stack
 840       for_each_stack_value(existing_state, index, existing_value) {
 841         Value new_value = new_state->stack_at(index);
 842         Phi* existing_phi = existing_value->as_Phi();
 843 
 844         if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
 845           existing_state->setup_phi_for_stack(this, index);
 846           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));
 847         }
 848       }
 849 
 850       // create necessary phi functions for locals
 851       for_each_local_value(existing_state, index, existing_value) {
 852         Value new_value = new_state->local_at(index);
 853         Phi* existing_phi = existing_value->as_Phi();
 854 
 855         if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
 856           existing_state->invalidate_local(index);
 857           TRACE_PHI(tty->print_cr("invalidating local %d because of type mismatch", index));
 858         } else if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
 859           existing_state->setup_phi_for_local(this, index);
 860           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));
 861         }
 862       }
 863     }
 864 
 865     assert(existing_state->caller_state() == new_state->caller_state(), "caller states must be equal");
 866 
 867   } else {
 868     assert(false, "stack or locks not matching (invalid bytecodes)");
 869     return false;
 870   }
 871 
 872   TRACE_PHI(tty->print_cr("********** try_merge for block B%d successful", block_id()));
 873 
 874   return true;
 875 }
 876 
 877 
 878 #ifndef PRODUCT
 879 void BlockBegin::print_block() {
 880   InstructionPrinter ip;
 881   print_block(ip, false);
 882 }
 883 
 884 
 885 void BlockBegin::print_block(InstructionPrinter& ip, bool live_only) {
 886   ip.print_instr(this); tty->cr();
 887   ip.print_stack(this->state()); tty->cr();
 888   ip.print_inline_level(this);
 889   ip.print_head();
 890   for (Instruction* n = next(); n != NULL; n = n->next()) {
 891     if (!live_only || n->is_pinned() || n->use_count() > 0) {
 892       ip.print_line(n);
 893     }
 894   }
 895   tty->cr();
 896 }
 897 #endif // PRODUCT
 898 
 899 
 900 // Implementation of BlockList
 901 
 902 void BlockList::iterate_forward (BlockClosure* closure) {
 903   const int l = length();
 904   for (int i = 0; i < l; i++) closure->block_do(at(i));
 905 }
 906 
 907 
 908 void BlockList::iterate_backward(BlockClosure* closure) {
 909   for (int i = length() - 1; i >= 0; i--) closure->block_do(at(i));
 910 }
 911 
 912 
 913 void BlockList::blocks_do(void f(BlockBegin*)) {
 914   for (int i = length() - 1; i >= 0; i--) f(at(i));
 915 }
 916 
 917 
 918 void BlockList::values_do(ValueVisitor* f) {
 919   for (int i = length() - 1; i >= 0; i--) at(i)->block_values_do(f);
 920 }
 921 
 922 
 923 #ifndef PRODUCT
 924 void BlockList::print(bool cfg_only, bool live_only) {
 925   InstructionPrinter ip;
 926   for (int i = 0; i < length(); i++) {
 927     BlockBegin* block = at(i);
 928     if (cfg_only) {
 929       ip.print_instr(block); tty->cr();
 930     } else {
 931       block->print_block(ip, live_only);
 932     }
 933   }
 934 }
 935 #endif // PRODUCT
 936 
 937 
 938 // Implementation of BlockEnd
 939 
 940 void BlockEnd::set_begin(BlockBegin* begin) {
 941   BlockList* sux = NULL;
 942   if (begin != NULL) {
 943     sux = begin->successors();
 944   } else if (this->begin() != NULL) {
 945     // copy our sux list
 946     BlockList* sux = new BlockList(this->begin()->number_of_sux());
 947     for (int i = 0; i < this->begin()->number_of_sux(); i++) {
 948       sux->append(this->begin()->sux_at(i));
 949     }
 950   }
 951   _sux = sux;
 952 }
 953 
 954 
 955 void BlockEnd::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
 956   substitute(*_sux, old_sux, new_sux);
 957 }
 958 
 959 
 960 // Implementation of Phi
 961 
 962 // Normal phi functions take their operands from the last instruction of the
 963 // predecessor. Special handling is needed for xhanlder entries because there
 964 // the state of arbitrary instructions are needed.
 965 
 966 Value Phi::operand_at(int i) const {
 967   ValueStack* state;
 968   if (_block->is_set(BlockBegin::exception_entry_flag)) {
 969     state = _block->exception_state_at(i);
 970   } else {
 971     state = _block->pred_at(i)->end()->state();
 972   }
 973   assert(state != NULL, "");
 974 
 975   if (is_local()) {
 976     return state->local_at(local_index());
 977   } else {
 978     return state->stack_at(stack_index());
 979   }
 980 }
 981 
 982 
 983 int Phi::operand_count() const {
 984   if (_block->is_set(BlockBegin::exception_entry_flag)) {
 985     return _block->number_of_exception_states();
 986   } else {
 987     return _block->number_of_preds();
 988   }
 989 }
 990 
 991 #ifdef ASSERT
 992 // Constructor of Assert
 993 Assert::Assert(Value x, Condition cond, bool unordered_is_true, Value y) : Instruction(illegalType)
 994   , _x(x)
 995   , _cond(cond)
 996   , _y(y)
 997 {
 998   set_flag(UnorderedIsTrueFlag, unordered_is_true);
 999   assert(x->type()->tag() == y->type()->tag(), "types must match");
1000   pin();
1001 
1002   stringStream strStream;
1003   Compilation::current()->method()->print_name(&strStream);
1004 
1005   stringStream strStream1;
1006   InstructionPrinter ip1(1, &strStream1);
1007   ip1.print_instr(x);
1008 
1009   stringStream strStream2;
1010   InstructionPrinter ip2(1, &strStream2);
1011   ip2.print_instr(y);
1012 
1013   stringStream ss;
1014   ss.print("Assertion %s %s %s in method %s", strStream1.as_string(), ip2.cond_name(cond), strStream2.as_string(), strStream.as_string());
1015 
1016   _message = ss.as_string();
1017 }
1018 #endif
1019 
1020 void RangeCheckPredicate::check_state() {
1021   assert(state()->kind() != ValueStack::EmptyExceptionState && state()->kind() != ValueStack::ExceptionState, "will deopt with empty state");
1022 }
1023 
1024 void ProfileInvoke::state_values_do(ValueVisitor* f) {
1025   if (state() != NULL) state()->values_do(f);
1026 }