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