1 /* 2 * Copyright (c) 2000, 2023, 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 "ci/ciConstant.hpp" 27 #include "ci/ciField.hpp" 28 #include "ci/ciInlineKlass.hpp" 29 #include "ci/ciMethod.hpp" 30 #include "ci/ciMethodData.hpp" 31 #include "ci/ciObjArrayKlass.hpp" 32 #include "ci/ciStreams.hpp" 33 #include "ci/ciTypeArrayKlass.hpp" 34 #include "ci/ciTypeFlow.hpp" 35 #include "compiler/compileLog.hpp" 36 #include "interpreter/bytecode.hpp" 37 #include "interpreter/bytecodes.hpp" 38 #include "memory/allocation.inline.hpp" 39 #include "memory/resourceArea.hpp" 40 #include "oops/oop.inline.hpp" 41 #include "opto/compile.hpp" 42 #include "opto/node.hpp" 43 #include "runtime/deoptimization.hpp" 44 #include "utilities/growableArray.hpp" 45 46 // ciTypeFlow::JsrSet 47 // 48 // A JsrSet represents some set of JsrRecords. This class 49 // is used to record a set of all jsr routines which we permit 50 // execution to return (ret) from. 51 // 52 // During abstract interpretation, JsrSets are used to determine 53 // whether two paths which reach a given block are unique, and 54 // should be cloned apart, or are compatible, and should merge 55 // together. 56 57 // ------------------------------------------------------------------ 58 // ciTypeFlow::JsrSet::JsrSet 59 60 // Allocate growable array storage in Arena. 61 ciTypeFlow::JsrSet::JsrSet(Arena* arena, int default_len) : _set(arena, default_len, 0, nullptr) { 62 assert(arena != nullptr, "invariant"); 63 } 64 65 // Allocate growable array storage in current ResourceArea. 66 ciTypeFlow::JsrSet::JsrSet(int default_len) : _set(default_len, 0, nullptr) {} 67 68 // ------------------------------------------------------------------ 69 // ciTypeFlow::JsrSet::copy_into 70 void ciTypeFlow::JsrSet::copy_into(JsrSet* jsrs) { 71 int len = size(); 72 jsrs->_set.clear(); 73 for (int i = 0; i < len; i++) { 74 jsrs->_set.append(_set.at(i)); 75 } 76 } 77 78 // ------------------------------------------------------------------ 79 // ciTypeFlow::JsrSet::is_compatible_with 80 // 81 // !!!! MISGIVINGS ABOUT THIS... disregard 82 // 83 // Is this JsrSet compatible with some other JsrSet? 84 // 85 // In set-theoretic terms, a JsrSet can be viewed as a partial function 86 // from entry addresses to return addresses. Two JsrSets A and B are 87 // compatible iff 88 // 89 // For any x, 90 // A(x) defined and B(x) defined implies A(x) == B(x) 91 // 92 // Less formally, two JsrSets are compatible when they have identical 93 // return addresses for any entry addresses they share in common. 94 bool ciTypeFlow::JsrSet::is_compatible_with(JsrSet* other) { 95 // Walk through both sets in parallel. If the same entry address 96 // appears in both sets, then the return address must match for 97 // the sets to be compatible. 98 int size1 = size(); 99 int size2 = other->size(); 100 101 // Special case. If nothing is on the jsr stack, then there can 102 // be no ret. 103 if (size2 == 0) { 104 return true; 105 } else if (size1 != size2) { 106 return false; 107 } else { 108 for (int i = 0; i < size1; i++) { 109 JsrRecord* record1 = record_at(i); 110 JsrRecord* record2 = other->record_at(i); 111 if (record1->entry_address() != record2->entry_address() || 112 record1->return_address() != record2->return_address()) { 113 return false; 114 } 115 } 116 return true; 117 } 118 119 #if 0 120 int pos1 = 0; 121 int pos2 = 0; 122 int size1 = size(); 123 int size2 = other->size(); 124 while (pos1 < size1 && pos2 < size2) { 125 JsrRecord* record1 = record_at(pos1); 126 JsrRecord* record2 = other->record_at(pos2); 127 int entry1 = record1->entry_address(); 128 int entry2 = record2->entry_address(); 129 if (entry1 < entry2) { 130 pos1++; 131 } else if (entry1 > entry2) { 132 pos2++; 133 } else { 134 if (record1->return_address() == record2->return_address()) { 135 pos1++; 136 pos2++; 137 } else { 138 // These two JsrSets are incompatible. 139 return false; 140 } 141 } 142 } 143 // The two JsrSets agree. 144 return true; 145 #endif 146 } 147 148 // ------------------------------------------------------------------ 149 // ciTypeFlow::JsrSet::insert_jsr_record 150 // 151 // Insert the given JsrRecord into the JsrSet, maintaining the order 152 // of the set and replacing any element with the same entry address. 153 void ciTypeFlow::JsrSet::insert_jsr_record(JsrRecord* record) { 154 int len = size(); 155 int entry = record->entry_address(); 156 int pos = 0; 157 for ( ; pos < len; pos++) { 158 JsrRecord* current = record_at(pos); 159 if (entry == current->entry_address()) { 160 // Stomp over this entry. 161 _set.at_put(pos, record); 162 assert(size() == len, "must be same size"); 163 return; 164 } else if (entry < current->entry_address()) { 165 break; 166 } 167 } 168 169 // Insert the record into the list. 170 JsrRecord* swap = record; 171 JsrRecord* temp = nullptr; 172 for ( ; pos < len; pos++) { 173 temp = _set.at(pos); 174 _set.at_put(pos, swap); 175 swap = temp; 176 } 177 _set.append(swap); 178 assert(size() == len+1, "must be larger"); 179 } 180 181 // ------------------------------------------------------------------ 182 // ciTypeFlow::JsrSet::remove_jsr_record 183 // 184 // Remove the JsrRecord with the given return address from the JsrSet. 185 void ciTypeFlow::JsrSet::remove_jsr_record(int return_address) { 186 int len = size(); 187 for (int i = 0; i < len; i++) { 188 if (record_at(i)->return_address() == return_address) { 189 // We have found the proper entry. Remove it from the 190 // JsrSet and exit. 191 for (int j = i + 1; j < len ; j++) { 192 _set.at_put(j - 1, _set.at(j)); 193 } 194 _set.trunc_to(len - 1); 195 assert(size() == len-1, "must be smaller"); 196 return; 197 } 198 } 199 assert(false, "verify: returning from invalid subroutine"); 200 } 201 202 // ------------------------------------------------------------------ 203 // ciTypeFlow::JsrSet::apply_control 204 // 205 // Apply the effect of a control-flow bytecode on the JsrSet. The 206 // only bytecodes that modify the JsrSet are jsr and ret. 207 void ciTypeFlow::JsrSet::apply_control(ciTypeFlow* analyzer, 208 ciBytecodeStream* str, 209 ciTypeFlow::StateVector* state) { 210 Bytecodes::Code code = str->cur_bc(); 211 if (code == Bytecodes::_jsr) { 212 JsrRecord* record = 213 analyzer->make_jsr_record(str->get_dest(), str->next_bci()); 214 insert_jsr_record(record); 215 } else if (code == Bytecodes::_jsr_w) { 216 JsrRecord* record = 217 analyzer->make_jsr_record(str->get_far_dest(), str->next_bci()); 218 insert_jsr_record(record); 219 } else if (code == Bytecodes::_ret) { 220 Cell local = state->local(str->get_index()); 221 ciType* return_address = state->type_at(local); 222 assert(return_address->is_return_address(), "verify: wrong type"); 223 if (size() == 0) { 224 // Ret-state underflow: Hit a ret w/o any previous jsrs. Bail out. 225 // This can happen when a loop is inside a finally clause (4614060). 226 analyzer->record_failure("OSR in finally clause"); 227 return; 228 } 229 remove_jsr_record(return_address->as_return_address()->bci()); 230 } 231 } 232 233 #ifndef PRODUCT 234 // ------------------------------------------------------------------ 235 // ciTypeFlow::JsrSet::print_on 236 void ciTypeFlow::JsrSet::print_on(outputStream* st) const { 237 st->print("{ "); 238 int num_elements = size(); 239 if (num_elements > 0) { 240 int i = 0; 241 for( ; i < num_elements - 1; i++) { 242 _set.at(i)->print_on(st); 243 st->print(", "); 244 } 245 _set.at(i)->print_on(st); 246 st->print(" "); 247 } 248 st->print("}"); 249 } 250 #endif 251 252 // ciTypeFlow::StateVector 253 // 254 // A StateVector summarizes the type information at some point in 255 // the program. 256 257 // ------------------------------------------------------------------ 258 // ciTypeFlow::StateVector::type_meet 259 // 260 // Meet two types. 261 // 262 // The semi-lattice of types use by this analysis are modeled on those 263 // of the verifier. The lattice is as follows: 264 // 265 // top_type() >= all non-extremal types >= bottom_type 266 // and 267 // Every primitive type is comparable only with itself. The meet of 268 // reference types is determined by their kind: instance class, 269 // interface, or array class. The meet of two types of the same 270 // kind is their least common ancestor. The meet of two types of 271 // different kinds is always java.lang.Object. 272 ciType* ciTypeFlow::StateVector::type_meet_internal(ciType* t1, ciType* t2, ciTypeFlow* analyzer) { 273 assert(t1 != t2, "checked in caller"); 274 if (t1->equals(top_type())) { 275 return t2; 276 } else if (t2->equals(top_type())) { 277 return t1; 278 } 279 // Unwrap after saving nullness information and handling top meets 280 bool null_free1 = t1->is_null_free(); 281 bool null_free2 = t2->is_null_free(); 282 if (t1->unwrap() == t2->unwrap() && null_free1 == null_free2) { 283 return t1; 284 } 285 t1 = t1->unwrap(); 286 t2 = t2->unwrap(); 287 288 if (t1->is_primitive_type() || t2->is_primitive_type()) { 289 // Special case null_type. null_type meet any reference type T 290 // is T. null_type meet null_type is null_type. 291 if (t1->equals(null_type())) { 292 if (!t2->is_primitive_type() || t2->equals(null_type())) { 293 return t2; 294 } 295 } else if (t2->equals(null_type())) { 296 if (!t1->is_primitive_type()) { 297 return t1; 298 } 299 } 300 301 // At least one of the two types is a non-top primitive type. 302 // The other type is not equal to it. Fall to bottom. 303 return bottom_type(); 304 } 305 306 // Both types are non-top non-primitive types. That is, 307 // both types are either instanceKlasses or arrayKlasses. 308 ciKlass* object_klass = analyzer->env()->Object_klass(); 309 ciKlass* k1 = t1->as_klass(); 310 ciKlass* k2 = t2->as_klass(); 311 if (k1->equals(object_klass) || k2->equals(object_klass)) { 312 return object_klass; 313 } else if (!k1->is_loaded() || !k2->is_loaded()) { 314 // Unloaded classes fall to java.lang.Object at a merge. 315 return object_klass; 316 } else if (k1->is_interface() != k2->is_interface()) { 317 // When an interface meets a non-interface, we get Object; 318 // This is what the verifier does. 319 return object_klass; 320 } else if (k1->is_array_klass() || k2->is_array_klass()) { 321 // When an array meets a non-array, we get Object. 322 // When (obj/flat)Array meets typeArray, we also get Object. 323 // And when typeArray meets different typeArray, we again get Object. 324 // But when (obj/flat)Array meets (obj/flat)Array, we look carefully at element types. 325 if ((k1->is_obj_array_klass() || k1->is_flat_array_klass()) && 326 (k2->is_obj_array_klass() || k2->is_flat_array_klass())) { 327 bool null_free = k1->as_array_klass()->is_elem_null_free() && 328 k2->as_array_klass()->is_elem_null_free(); 329 ciType* elem1 = k1->as_array_klass()->element_klass(); 330 ciType* elem2 = k2->as_array_klass()->element_klass(); 331 ciType* elem = elem1; 332 if (elem1 != elem2) { 333 elem = type_meet_internal(elem1, elem2, analyzer)->as_klass(); 334 } 335 // Do an easy shortcut if one type is a super of the other. 336 if (elem == elem1 && !elem->is_inlinetype()) { 337 assert(k1 == ciArrayKlass::make(elem, null_free), "shortcut is OK"); 338 return k1; 339 } else if (elem == elem2 && !elem->is_inlinetype()) { 340 assert(k2 == ciArrayKlass::make(elem, null_free), "shortcut is OK"); 341 return k2; 342 } else { 343 // TODO 8325106 Remove 344 assert(!null_free, "should be dead"); 345 return ciArrayKlass::make(elem); 346 } 347 } else { 348 return object_klass; 349 } 350 } else { 351 // Must be two plain old instance klasses. 352 assert(k1->is_instance_klass(), "previous cases handle non-instances"); 353 assert(k2->is_instance_klass(), "previous cases handle non-instances"); 354 ciType* result = k1->least_common_ancestor(k2); 355 if (null_free1 && null_free2 && result->is_inlinetype()) { 356 result = analyzer->mark_as_null_free(result); 357 } 358 return result; 359 } 360 } 361 362 363 // ------------------------------------------------------------------ 364 // ciTypeFlow::StateVector::StateVector 365 // 366 // Build a new state vector 367 ciTypeFlow::StateVector::StateVector(ciTypeFlow* analyzer) { 368 _outer = analyzer; 369 _stack_size = -1; 370 _monitor_count = -1; 371 // Allocate the _types array 372 int max_cells = analyzer->max_cells(); 373 _types = (ciType**)analyzer->arena()->Amalloc(sizeof(ciType*) * max_cells); 374 for (int i=0; i<max_cells; i++) { 375 _types[i] = top_type(); 376 } 377 _trap_bci = -1; 378 _trap_index = 0; 379 _def_locals.clear(); 380 } 381 382 383 // ------------------------------------------------------------------ 384 // ciTypeFlow::get_start_state 385 // 386 // Set this vector to the method entry state. 387 const ciTypeFlow::StateVector* ciTypeFlow::get_start_state() { 388 StateVector* state = new StateVector(this); 389 if (is_osr_flow()) { 390 ciTypeFlow* non_osr_flow = method()->get_flow_analysis(); 391 if (non_osr_flow->failing()) { 392 record_failure(non_osr_flow->failure_reason()); 393 return nullptr; 394 } 395 JsrSet* jsrs = new JsrSet(4); 396 Block* non_osr_block = non_osr_flow->existing_block_at(start_bci(), jsrs); 397 if (non_osr_block == nullptr) { 398 record_failure("cannot reach OSR point"); 399 return nullptr; 400 } 401 // load up the non-OSR state at this point 402 non_osr_block->copy_state_into(state); 403 int non_osr_start = non_osr_block->start(); 404 if (non_osr_start != start_bci()) { 405 // must flow forward from it 406 if (CITraceTypeFlow) { 407 tty->print_cr(">> Interpreting pre-OSR block %d:", non_osr_start); 408 } 409 Block* block = block_at(non_osr_start, jsrs); 410 assert(block->limit() == start_bci(), "must flow forward to start"); 411 flow_block(block, state, jsrs); 412 } 413 return state; 414 // Note: The code below would be an incorrect for an OSR flow, 415 // even if it were possible for an OSR entry point to be at bci zero. 416 } 417 // "Push" the method signature into the first few locals. 418 state->set_stack_size(-max_locals()); 419 if (!method()->is_static()) { 420 ciType* holder = method()->holder(); 421 if (holder->is_inlinetype()) { 422 // The receiver is null-free 423 holder = mark_as_null_free(holder); 424 } 425 state->push(holder); 426 assert(state->tos() == state->local(0), ""); 427 } 428 for (ciSignatureStream str(method()->signature()); 429 !str.at_return_type(); 430 str.next()) { 431 state->push_translate(str.type()); 432 } 433 // Set the rest of the locals to bottom. 434 Cell cell = state->next_cell(state->tos()); 435 state->set_stack_size(0); 436 int limit = state->limit_cell(); 437 for (; cell < limit; cell = state->next_cell(cell)) { 438 state->set_type_at(cell, state->bottom_type()); 439 } 440 // Lock an object, if necessary. 441 state->set_monitor_count(method()->is_synchronized() ? 1 : 0); 442 return state; 443 } 444 445 // ------------------------------------------------------------------ 446 // ciTypeFlow::StateVector::copy_into 447 // 448 // Copy our value into some other StateVector 449 void ciTypeFlow::StateVector::copy_into(ciTypeFlow::StateVector* copy) 450 const { 451 copy->set_stack_size(stack_size()); 452 copy->set_monitor_count(monitor_count()); 453 Cell limit = limit_cell(); 454 for (Cell c = start_cell(); c < limit; c = next_cell(c)) { 455 copy->set_type_at(c, type_at(c)); 456 } 457 } 458 459 // ------------------------------------------------------------------ 460 // ciTypeFlow::StateVector::meet 461 // 462 // Meets this StateVector with another, destructively modifying this 463 // one. Returns true if any modification takes place. 464 bool ciTypeFlow::StateVector::meet(const ciTypeFlow::StateVector* incoming) { 465 if (monitor_count() == -1) { 466 set_monitor_count(incoming->monitor_count()); 467 } 468 assert(monitor_count() == incoming->monitor_count(), "monitors must match"); 469 470 if (stack_size() == -1) { 471 set_stack_size(incoming->stack_size()); 472 Cell limit = limit_cell(); 473 #ifdef ASSERT 474 { for (Cell c = start_cell(); c < limit; c = next_cell(c)) { 475 assert(type_at(c) == top_type(), ""); 476 } } 477 #endif 478 // Make a simple copy of the incoming state. 479 for (Cell c = start_cell(); c < limit; c = next_cell(c)) { 480 set_type_at(c, incoming->type_at(c)); 481 } 482 return true; // it is always different the first time 483 } 484 #ifdef ASSERT 485 if (stack_size() != incoming->stack_size()) { 486 _outer->method()->print_codes(); 487 tty->print_cr("!!!! Stack size conflict"); 488 tty->print_cr("Current state:"); 489 print_on(tty); 490 tty->print_cr("Incoming state:"); 491 ((StateVector*)incoming)->print_on(tty); 492 } 493 #endif 494 assert(stack_size() == incoming->stack_size(), "sanity"); 495 496 bool different = false; 497 Cell limit = limit_cell(); 498 for (Cell c = start_cell(); c < limit; c = next_cell(c)) { 499 ciType* t1 = type_at(c); 500 ciType* t2 = incoming->type_at(c); 501 if (!t1->equals(t2)) { 502 ciType* new_type = type_meet(t1, t2); 503 if (!t1->equals(new_type)) { 504 set_type_at(c, new_type); 505 different = true; 506 } 507 } 508 } 509 return different; 510 } 511 512 // ------------------------------------------------------------------ 513 // ciTypeFlow::StateVector::meet_exception 514 // 515 // Meets this StateVector with another, destructively modifying this 516 // one. The incoming state is coming via an exception. Returns true 517 // if any modification takes place. 518 bool ciTypeFlow::StateVector::meet_exception(ciInstanceKlass* exc, 519 const ciTypeFlow::StateVector* incoming) { 520 if (monitor_count() == -1) { 521 set_monitor_count(incoming->monitor_count()); 522 } 523 assert(monitor_count() == incoming->monitor_count(), "monitors must match"); 524 525 if (stack_size() == -1) { 526 set_stack_size(1); 527 } 528 529 assert(stack_size() == 1, "must have one-element stack"); 530 531 bool different = false; 532 533 // Meet locals from incoming array. 534 Cell limit = local(_outer->max_locals()-1); 535 for (Cell c = start_cell(); c <= limit; c = next_cell(c)) { 536 ciType* t1 = type_at(c); 537 ciType* t2 = incoming->type_at(c); 538 if (!t1->equals(t2)) { 539 ciType* new_type = type_meet(t1, t2); 540 if (!t1->equals(new_type)) { 541 set_type_at(c, new_type); 542 different = true; 543 } 544 } 545 } 546 547 // Handle stack separately. When an exception occurs, the 548 // only stack entry is the exception instance. 549 ciType* tos_type = type_at_tos(); 550 if (!tos_type->equals(exc)) { 551 ciType* new_type = type_meet(tos_type, exc); 552 if (!tos_type->equals(new_type)) { 553 set_type_at_tos(new_type); 554 different = true; 555 } 556 } 557 558 return different; 559 } 560 561 // ------------------------------------------------------------------ 562 // ciTypeFlow::StateVector::push_translate 563 void ciTypeFlow::StateVector::push_translate(ciType* type) { 564 BasicType basic_type = type->basic_type(); 565 if (basic_type == T_BOOLEAN || basic_type == T_CHAR || 566 basic_type == T_BYTE || basic_type == T_SHORT) { 567 push_int(); 568 } else { 569 push(type); 570 if (type->is_two_word()) { 571 push(half_type(type)); 572 } 573 } 574 } 575 576 // ------------------------------------------------------------------ 577 // ciTypeFlow::StateVector::do_aload 578 void ciTypeFlow::StateVector::do_aload(ciBytecodeStream* str) { 579 pop_int(); 580 ciArrayKlass* array_klass = pop_objOrFlatArray(); 581 if (array_klass == nullptr) { 582 // Did aload on a null reference; push a null and ignore the exception. 583 // This instruction will never continue normally. All we have to do 584 // is report a value that will meet correctly with any downstream 585 // reference types on paths that will truly be executed. This null type 586 // meets with any reference type to yield that same reference type. 587 // (The compiler will generate an unconditional exception here.) 588 push(null_type()); 589 return; 590 } 591 if (!array_klass->is_loaded()) { 592 // Only fails for some -Xcomp runs 593 trap(str, array_klass, 594 Deoptimization::make_trap_request 595 (Deoptimization::Reason_unloaded, 596 Deoptimization::Action_reinterpret)); 597 return; 598 } 599 ciKlass* element_klass = array_klass->element_klass(); 600 if (!element_klass->is_loaded() && element_klass->is_instance_klass()) { 601 Untested("unloaded array element class in ciTypeFlow"); 602 trap(str, element_klass, 603 Deoptimization::make_trap_request 604 (Deoptimization::Reason_unloaded, 605 Deoptimization::Action_reinterpret)); 606 } else { 607 if (array_klass->is_elem_null_free()) { 608 // TODO 8325106 Is this dead? 609 push(outer()->mark_as_null_free(element_klass)); 610 } else { 611 push_object(element_klass); 612 } 613 } 614 } 615 616 617 // ------------------------------------------------------------------ 618 // ciTypeFlow::StateVector::do_checkcast 619 void ciTypeFlow::StateVector::do_checkcast(ciBytecodeStream* str) { 620 bool will_link; 621 ciKlass* klass = str->get_klass(will_link); 622 if (!will_link) { 623 // VM's interpreter will not load 'klass' if object is nullptr. 624 // Type flow after this block may still be needed in two situations: 625 // 1) C2 uses do_null_assert() and continues compilation for later blocks 626 // 2) C2 does an OSR compile in a later block (see bug 4778368). 627 pop_object(); 628 do_null_assert(klass); 629 } else { 630 ciType* type = pop_value(); 631 type = type->unwrap(); 632 if (type->is_loaded() && klass->is_loaded() && 633 type != klass && type->is_subtype_of(klass)) { 634 // Useless cast, propagate more precise type of object 635 klass = type->as_klass(); 636 } 637 if (klass->is_inlinetype() && type->is_null_free()) { 638 // TODO 8325106 Is this dead? 639 push(outer()->mark_as_null_free(klass)); 640 } else { 641 push_object(klass); 642 } 643 } 644 } 645 646 // ------------------------------------------------------------------ 647 // ciTypeFlow::StateVector::do_getfield 648 void ciTypeFlow::StateVector::do_getfield(ciBytecodeStream* str) { 649 // could add assert here for type of object. 650 pop_object(); 651 do_getstatic(str); 652 } 653 654 // ------------------------------------------------------------------ 655 // ciTypeFlow::StateVector::do_getstatic 656 void ciTypeFlow::StateVector::do_getstatic(ciBytecodeStream* str) { 657 bool will_link; 658 ciField* field = str->get_field(will_link); 659 if (!will_link) { 660 trap(str, field->holder(), str->get_field_holder_index()); 661 } else { 662 ciType* field_type = field->type(); 663 if (field->is_static() && field->is_null_free() && 664 !field_type->as_instance_klass()->is_initialized()) { 665 // Deoptimize if we load from a static field with an uninitialized inline type 666 // because we need to throw an exception if initialization of the type failed. 667 trap(str, field_type->as_klass(), 668 Deoptimization::make_trap_request 669 (Deoptimization::Reason_unloaded, 670 Deoptimization::Action_reinterpret)); 671 return; 672 } else if (!field_type->is_loaded()) { 673 // Normally, we need the field's type to be loaded if we are to 674 // do anything interesting with its value. 675 // We used to do this: trap(str, str->get_field_signature_index()); 676 // 677 // There is one good reason not to trap here. Execution can 678 // get past this "getfield" or "getstatic" if the value of 679 // the field is null. As long as the value is null, the class 680 // does not need to be loaded! The compiler must assume that 681 // the value of the unloaded class reference is null; if the code 682 // ever sees a non-null value, loading has occurred. 683 // 684 // This actually happens often enough to be annoying. If the 685 // compiler throws an uncommon trap at this bytecode, you can 686 // get an endless loop of recompilations, when all the code 687 // needs to do is load a series of null values. Also, a trap 688 // here can make an OSR entry point unreachable, triggering the 689 // assert on non_osr_block in ciTypeFlow::get_start_state. 690 // (See bug 4379915.) 691 do_null_assert(field_type->as_klass()); 692 } else { 693 if (field->is_null_free()) { 694 field_type = outer()->mark_as_null_free(field_type); 695 } 696 push_translate(field_type); 697 } 698 } 699 } 700 701 // ------------------------------------------------------------------ 702 // ciTypeFlow::StateVector::do_invoke 703 void ciTypeFlow::StateVector::do_invoke(ciBytecodeStream* str, 704 bool has_receiver) { 705 bool will_link; 706 ciSignature* declared_signature = nullptr; 707 ciMethod* callee = str->get_method(will_link, &declared_signature); 708 assert(declared_signature != nullptr, "cannot be null"); 709 if (!will_link) { 710 // We weren't able to find the method. 711 if (str->cur_bc() == Bytecodes::_invokedynamic) { 712 trap(str, nullptr, 713 Deoptimization::make_trap_request 714 (Deoptimization::Reason_uninitialized, 715 Deoptimization::Action_reinterpret)); 716 } else { 717 ciKlass* unloaded_holder = callee->holder(); 718 trap(str, unloaded_holder, str->get_method_holder_index()); 719 } 720 } else { 721 // We are using the declared signature here because it might be 722 // different from the callee signature (Cf. invokedynamic and 723 // invokehandle). 724 ciSignatureStream sigstr(declared_signature); 725 const int arg_size = declared_signature->size(); 726 const int stack_base = stack_size() - arg_size; 727 int i = 0; 728 for( ; !sigstr.at_return_type(); sigstr.next()) { 729 ciType* type = sigstr.type(); 730 ciType* stack_type = type_at(stack(stack_base + i++)); 731 // Do I want to check this type? 732 // assert(stack_type->is_subtype_of(type), "bad type for field value"); 733 if (type->is_two_word()) { 734 ciType* stack_type2 = type_at(stack(stack_base + i++)); 735 assert(stack_type2->equals(half_type(type)), "must be 2nd half"); 736 } 737 } 738 assert(arg_size == i, "must match"); 739 for (int j = 0; j < arg_size; j++) { 740 pop(); 741 } 742 if (has_receiver) { 743 // Check this? 744 pop_object(); 745 } 746 assert(!sigstr.is_done(), "must have return type"); 747 ciType* return_type = sigstr.type(); 748 if (!return_type->is_void()) { 749 if (!return_type->is_loaded()) { 750 // As in do_getstatic(), generally speaking, we need the return type to 751 // be loaded if we are to do anything interesting with its value. 752 // We used to do this: trap(str, str->get_method_signature_index()); 753 // 754 // We do not trap here since execution can get past this invoke if 755 // the return value is null. As long as the value is null, the class 756 // does not need to be loaded! The compiler must assume that 757 // the value of the unloaded class reference is null; if the code 758 // ever sees a non-null value, loading has occurred. 759 // 760 // See do_getstatic() for similar explanation, as well as bug 4684993. 761 if (InlineTypeReturnedAsFields) { 762 // Return might be in scalarized form but we can't handle it because we 763 // don't know the type. This can happen due to a missing preload attribute. 764 // TODO 8284443 Use PhaseMacroExpand::expand_mh_intrinsic_return for this 765 trap(str, nullptr, 766 Deoptimization::make_trap_request 767 (Deoptimization::Reason_uninitialized, 768 Deoptimization::Action_reinterpret)); 769 } else { 770 do_null_assert(return_type->as_klass()); 771 } 772 } else { 773 push_translate(return_type); 774 } 775 } 776 } 777 } 778 779 // ------------------------------------------------------------------ 780 // ciTypeFlow::StateVector::do_jsr 781 void ciTypeFlow::StateVector::do_jsr(ciBytecodeStream* str) { 782 push(ciReturnAddress::make(str->next_bci())); 783 } 784 785 // ------------------------------------------------------------------ 786 // ciTypeFlow::StateVector::do_ldc 787 void ciTypeFlow::StateVector::do_ldc(ciBytecodeStream* str) { 788 if (str->is_in_error()) { 789 trap(str, nullptr, Deoptimization::make_trap_request(Deoptimization::Reason_unhandled, 790 Deoptimization::Action_none)); 791 return; 792 } 793 ciConstant con = str->get_constant(); 794 if (con.is_valid()) { 795 int cp_index = str->get_constant_pool_index(); 796 BasicType basic_type = str->get_basic_type_for_constant_at(cp_index); 797 if (is_reference_type(basic_type)) { 798 ciObject* obj = con.as_object(); 799 if (obj->is_null_object()) { 800 push_null(); 801 } else { 802 assert(obj->is_instance() || obj->is_array(), "must be java_mirror of klass"); 803 ciType* type = obj->klass(); 804 if (type->is_inlinetype()) { 805 type = outer()->mark_as_null_free(type); 806 } 807 push(type); 808 } 809 } else { 810 assert(basic_type == con.basic_type() || con.basic_type() == T_OBJECT, 811 "not a boxed form: %s vs %s", type2name(basic_type), type2name(con.basic_type())); 812 push_translate(ciType::make(basic_type)); 813 } 814 } else { 815 // OutOfMemoryError in the CI while loading a String constant. 816 push_null(); 817 outer()->record_failure("ldc did not link"); 818 } 819 } 820 821 // ------------------------------------------------------------------ 822 // ciTypeFlow::StateVector::do_multianewarray 823 void ciTypeFlow::StateVector::do_multianewarray(ciBytecodeStream* str) { 824 int dimensions = str->get_dimensions(); 825 bool will_link; 826 ciArrayKlass* array_klass = str->get_klass(will_link)->as_array_klass(); 827 if (!will_link) { 828 trap(str, array_klass, str->get_klass_index()); 829 } else { 830 for (int i = 0; i < dimensions; i++) { 831 pop_int(); 832 } 833 push_object(array_klass); 834 } 835 } 836 837 // ------------------------------------------------------------------ 838 // ciTypeFlow::StateVector::do_new 839 void ciTypeFlow::StateVector::do_new(ciBytecodeStream* str) { 840 bool will_link; 841 ciKlass* klass = str->get_klass(will_link); 842 if (!will_link || str->is_unresolved_klass()) { 843 trap(str, klass, str->get_klass_index()); 844 } else { 845 push_object(klass); 846 } 847 } 848 849 // ------------------------------------------------------------------ 850 // ciTypeFlow::StateVector::do_newarray 851 void ciTypeFlow::StateVector::do_newarray(ciBytecodeStream* str) { 852 pop_int(); 853 ciKlass* klass = ciTypeArrayKlass::make((BasicType)str->get_index()); 854 push_object(klass); 855 } 856 857 // ------------------------------------------------------------------ 858 // ciTypeFlow::StateVector::do_putfield 859 void ciTypeFlow::StateVector::do_putfield(ciBytecodeStream* str) { 860 do_putstatic(str); 861 if (_trap_bci != -1) return; // unloaded field holder, etc. 862 // could add assert here for type of object. 863 pop_object(); 864 } 865 866 // ------------------------------------------------------------------ 867 // ciTypeFlow::StateVector::do_putstatic 868 void ciTypeFlow::StateVector::do_putstatic(ciBytecodeStream* str) { 869 bool will_link; 870 ciField* field = str->get_field(will_link); 871 if (!will_link) { 872 trap(str, field->holder(), str->get_field_holder_index()); 873 } else { 874 ciType* field_type = field->type(); 875 ciType* type = pop_value(); 876 // Do I want to check this type? 877 // assert(type->is_subtype_of(field_type), "bad type for field value"); 878 if (field_type->is_two_word()) { 879 ciType* type2 = pop_value(); 880 assert(type2->is_two_word(), "must be 2nd half"); 881 assert(type == half_type(type2), "must be 2nd half"); 882 } 883 } 884 } 885 886 // ------------------------------------------------------------------ 887 // ciTypeFlow::StateVector::do_ret 888 void ciTypeFlow::StateVector::do_ret(ciBytecodeStream* str) { 889 Cell index = local(str->get_index()); 890 891 ciType* address = type_at(index); 892 assert(address->is_return_address(), "bad return address"); 893 set_type_at(index, bottom_type()); 894 } 895 896 // ------------------------------------------------------------------ 897 // ciTypeFlow::StateVector::trap 898 // 899 // Stop interpretation of this path with a trap. 900 void ciTypeFlow::StateVector::trap(ciBytecodeStream* str, ciKlass* klass, int index) { 901 _trap_bci = str->cur_bci(); 902 _trap_index = index; 903 904 // Log information about this trap: 905 CompileLog* log = outer()->env()->log(); 906 if (log != nullptr) { 907 int mid = log->identify(outer()->method()); 908 int kid = (klass == nullptr)? -1: log->identify(klass); 909 log->begin_elem("uncommon_trap method='%d' bci='%d'", mid, str->cur_bci()); 910 char buf[100]; 911 log->print(" %s", Deoptimization::format_trap_request(buf, sizeof(buf), 912 index)); 913 if (kid >= 0) 914 log->print(" klass='%d'", kid); 915 log->end_elem(); 916 } 917 } 918 919 // ------------------------------------------------------------------ 920 // ciTypeFlow::StateVector::do_null_assert 921 // Corresponds to graphKit::do_null_assert. 922 void ciTypeFlow::StateVector::do_null_assert(ciKlass* unloaded_klass) { 923 if (unloaded_klass->is_loaded()) { 924 // We failed to link, but we can still compute with this class, 925 // since it is loaded somewhere. The compiler will uncommon_trap 926 // if the object is not null, but the typeflow pass can not assume 927 // that the object will be null, otherwise it may incorrectly tell 928 // the parser that an object is known to be null. 4761344, 4807707 929 push_object(unloaded_klass); 930 } else { 931 // The class is not loaded anywhere. It is safe to model the 932 // null in the typestates, because we can compile in a null check 933 // which will deoptimize us if someone manages to load the 934 // class later. 935 push_null(); 936 } 937 } 938 939 940 // ------------------------------------------------------------------ 941 // ciTypeFlow::StateVector::apply_one_bytecode 942 // 943 // Apply the effect of one bytecode to this StateVector 944 bool ciTypeFlow::StateVector::apply_one_bytecode(ciBytecodeStream* str) { 945 _trap_bci = -1; 946 _trap_index = 0; 947 948 if (CITraceTypeFlow) { 949 tty->print_cr(">> Interpreting bytecode %d:%s", str->cur_bci(), 950 Bytecodes::name(str->cur_bc())); 951 } 952 953 switch(str->cur_bc()) { 954 case Bytecodes::_aaload: do_aload(str); break; 955 956 case Bytecodes::_aastore: 957 { 958 pop_object(); 959 pop_int(); 960 pop_objOrFlatArray(); 961 break; 962 } 963 case Bytecodes::_aconst_null: 964 { 965 push_null(); 966 break; 967 } 968 case Bytecodes::_aload: load_local_object(str->get_index()); break; 969 case Bytecodes::_aload_0: load_local_object(0); break; 970 case Bytecodes::_aload_1: load_local_object(1); break; 971 case Bytecodes::_aload_2: load_local_object(2); break; 972 case Bytecodes::_aload_3: load_local_object(3); break; 973 974 case Bytecodes::_anewarray: 975 { 976 pop_int(); 977 bool will_link; 978 ciKlass* element_klass = str->get_klass(will_link); 979 if (!will_link) { 980 trap(str, element_klass, str->get_klass_index()); 981 } else { 982 push_object(ciArrayKlass::make(element_klass)); 983 } 984 break; 985 } 986 case Bytecodes::_areturn: 987 case Bytecodes::_ifnonnull: 988 case Bytecodes::_ifnull: 989 { 990 pop_object(); 991 break; 992 } 993 case Bytecodes::_monitorenter: 994 { 995 pop_object(); 996 set_monitor_count(monitor_count() + 1); 997 break; 998 } 999 case Bytecodes::_monitorexit: 1000 { 1001 pop_object(); 1002 assert(monitor_count() > 0, "must be a monitor to exit from"); 1003 set_monitor_count(monitor_count() - 1); 1004 break; 1005 } 1006 case Bytecodes::_arraylength: 1007 { 1008 pop_array(); 1009 push_int(); 1010 break; 1011 } 1012 case Bytecodes::_astore: store_local_object(str->get_index()); break; 1013 case Bytecodes::_astore_0: store_local_object(0); break; 1014 case Bytecodes::_astore_1: store_local_object(1); break; 1015 case Bytecodes::_astore_2: store_local_object(2); break; 1016 case Bytecodes::_astore_3: store_local_object(3); break; 1017 1018 case Bytecodes::_athrow: 1019 { 1020 NEEDS_CLEANUP; 1021 pop_object(); 1022 break; 1023 } 1024 case Bytecodes::_baload: 1025 case Bytecodes::_caload: 1026 case Bytecodes::_iaload: 1027 case Bytecodes::_saload: 1028 { 1029 pop_int(); 1030 ciTypeArrayKlass* array_klass = pop_typeArray(); 1031 // Put assert here for right type? 1032 push_int(); 1033 break; 1034 } 1035 case Bytecodes::_bastore: 1036 case Bytecodes::_castore: 1037 case Bytecodes::_iastore: 1038 case Bytecodes::_sastore: 1039 { 1040 pop_int(); 1041 pop_int(); 1042 pop_typeArray(); 1043 // assert here? 1044 break; 1045 } 1046 case Bytecodes::_bipush: 1047 case Bytecodes::_iconst_m1: 1048 case Bytecodes::_iconst_0: 1049 case Bytecodes::_iconst_1: 1050 case Bytecodes::_iconst_2: 1051 case Bytecodes::_iconst_3: 1052 case Bytecodes::_iconst_4: 1053 case Bytecodes::_iconst_5: 1054 case Bytecodes::_sipush: 1055 { 1056 push_int(); 1057 break; 1058 } 1059 case Bytecodes::_checkcast: do_checkcast(str); break; 1060 1061 case Bytecodes::_d2f: 1062 { 1063 pop_double(); 1064 push_float(); 1065 break; 1066 } 1067 case Bytecodes::_d2i: 1068 { 1069 pop_double(); 1070 push_int(); 1071 break; 1072 } 1073 case Bytecodes::_d2l: 1074 { 1075 pop_double(); 1076 push_long(); 1077 break; 1078 } 1079 case Bytecodes::_dadd: 1080 case Bytecodes::_ddiv: 1081 case Bytecodes::_dmul: 1082 case Bytecodes::_drem: 1083 case Bytecodes::_dsub: 1084 { 1085 pop_double(); 1086 pop_double(); 1087 push_double(); 1088 break; 1089 } 1090 case Bytecodes::_daload: 1091 { 1092 pop_int(); 1093 ciTypeArrayKlass* array_klass = pop_typeArray(); 1094 // Put assert here for right type? 1095 push_double(); 1096 break; 1097 } 1098 case Bytecodes::_dastore: 1099 { 1100 pop_double(); 1101 pop_int(); 1102 pop_typeArray(); 1103 // assert here? 1104 break; 1105 } 1106 case Bytecodes::_dcmpg: 1107 case Bytecodes::_dcmpl: 1108 { 1109 pop_double(); 1110 pop_double(); 1111 push_int(); 1112 break; 1113 } 1114 case Bytecodes::_dconst_0: 1115 case Bytecodes::_dconst_1: 1116 { 1117 push_double(); 1118 break; 1119 } 1120 case Bytecodes::_dload: load_local_double(str->get_index()); break; 1121 case Bytecodes::_dload_0: load_local_double(0); break; 1122 case Bytecodes::_dload_1: load_local_double(1); break; 1123 case Bytecodes::_dload_2: load_local_double(2); break; 1124 case Bytecodes::_dload_3: load_local_double(3); break; 1125 1126 case Bytecodes::_dneg: 1127 { 1128 pop_double(); 1129 push_double(); 1130 break; 1131 } 1132 case Bytecodes::_dreturn: 1133 { 1134 pop_double(); 1135 break; 1136 } 1137 case Bytecodes::_dstore: store_local_double(str->get_index()); break; 1138 case Bytecodes::_dstore_0: store_local_double(0); break; 1139 case Bytecodes::_dstore_1: store_local_double(1); break; 1140 case Bytecodes::_dstore_2: store_local_double(2); break; 1141 case Bytecodes::_dstore_3: store_local_double(3); break; 1142 1143 case Bytecodes::_dup: 1144 { 1145 push(type_at_tos()); 1146 break; 1147 } 1148 case Bytecodes::_dup_x1: 1149 { 1150 ciType* value1 = pop_value(); 1151 ciType* value2 = pop_value(); 1152 push(value1); 1153 push(value2); 1154 push(value1); 1155 break; 1156 } 1157 case Bytecodes::_dup_x2: 1158 { 1159 ciType* value1 = pop_value(); 1160 ciType* value2 = pop_value(); 1161 ciType* value3 = pop_value(); 1162 push(value1); 1163 push(value3); 1164 push(value2); 1165 push(value1); 1166 break; 1167 } 1168 case Bytecodes::_dup2: 1169 { 1170 ciType* value1 = pop_value(); 1171 ciType* value2 = pop_value(); 1172 push(value2); 1173 push(value1); 1174 push(value2); 1175 push(value1); 1176 break; 1177 } 1178 case Bytecodes::_dup2_x1: 1179 { 1180 ciType* value1 = pop_value(); 1181 ciType* value2 = pop_value(); 1182 ciType* value3 = pop_value(); 1183 push(value2); 1184 push(value1); 1185 push(value3); 1186 push(value2); 1187 push(value1); 1188 break; 1189 } 1190 case Bytecodes::_dup2_x2: 1191 { 1192 ciType* value1 = pop_value(); 1193 ciType* value2 = pop_value(); 1194 ciType* value3 = pop_value(); 1195 ciType* value4 = pop_value(); 1196 push(value2); 1197 push(value1); 1198 push(value4); 1199 push(value3); 1200 push(value2); 1201 push(value1); 1202 break; 1203 } 1204 case Bytecodes::_f2d: 1205 { 1206 pop_float(); 1207 push_double(); 1208 break; 1209 } 1210 case Bytecodes::_f2i: 1211 { 1212 pop_float(); 1213 push_int(); 1214 break; 1215 } 1216 case Bytecodes::_f2l: 1217 { 1218 pop_float(); 1219 push_long(); 1220 break; 1221 } 1222 case Bytecodes::_fadd: 1223 case Bytecodes::_fdiv: 1224 case Bytecodes::_fmul: 1225 case Bytecodes::_frem: 1226 case Bytecodes::_fsub: 1227 { 1228 pop_float(); 1229 pop_float(); 1230 push_float(); 1231 break; 1232 } 1233 case Bytecodes::_faload: 1234 { 1235 pop_int(); 1236 ciTypeArrayKlass* array_klass = pop_typeArray(); 1237 // Put assert here. 1238 push_float(); 1239 break; 1240 } 1241 case Bytecodes::_fastore: 1242 { 1243 pop_float(); 1244 pop_int(); 1245 ciTypeArrayKlass* array_klass = pop_typeArray(); 1246 // Put assert here. 1247 break; 1248 } 1249 case Bytecodes::_fcmpg: 1250 case Bytecodes::_fcmpl: 1251 { 1252 pop_float(); 1253 pop_float(); 1254 push_int(); 1255 break; 1256 } 1257 case Bytecodes::_fconst_0: 1258 case Bytecodes::_fconst_1: 1259 case Bytecodes::_fconst_2: 1260 { 1261 push_float(); 1262 break; 1263 } 1264 case Bytecodes::_fload: load_local_float(str->get_index()); break; 1265 case Bytecodes::_fload_0: load_local_float(0); break; 1266 case Bytecodes::_fload_1: load_local_float(1); break; 1267 case Bytecodes::_fload_2: load_local_float(2); break; 1268 case Bytecodes::_fload_3: load_local_float(3); break; 1269 1270 case Bytecodes::_fneg: 1271 { 1272 pop_float(); 1273 push_float(); 1274 break; 1275 } 1276 case Bytecodes::_freturn: 1277 { 1278 pop_float(); 1279 break; 1280 } 1281 case Bytecodes::_fstore: store_local_float(str->get_index()); break; 1282 case Bytecodes::_fstore_0: store_local_float(0); break; 1283 case Bytecodes::_fstore_1: store_local_float(1); break; 1284 case Bytecodes::_fstore_2: store_local_float(2); break; 1285 case Bytecodes::_fstore_3: store_local_float(3); break; 1286 1287 case Bytecodes::_getfield: do_getfield(str); break; 1288 case Bytecodes::_getstatic: do_getstatic(str); break; 1289 1290 case Bytecodes::_goto: 1291 case Bytecodes::_goto_w: 1292 case Bytecodes::_nop: 1293 case Bytecodes::_return: 1294 { 1295 // do nothing. 1296 break; 1297 } 1298 case Bytecodes::_i2b: 1299 case Bytecodes::_i2c: 1300 case Bytecodes::_i2s: 1301 case Bytecodes::_ineg: 1302 { 1303 pop_int(); 1304 push_int(); 1305 break; 1306 } 1307 case Bytecodes::_i2d: 1308 { 1309 pop_int(); 1310 push_double(); 1311 break; 1312 } 1313 case Bytecodes::_i2f: 1314 { 1315 pop_int(); 1316 push_float(); 1317 break; 1318 } 1319 case Bytecodes::_i2l: 1320 { 1321 pop_int(); 1322 push_long(); 1323 break; 1324 } 1325 case Bytecodes::_iadd: 1326 case Bytecodes::_iand: 1327 case Bytecodes::_idiv: 1328 case Bytecodes::_imul: 1329 case Bytecodes::_ior: 1330 case Bytecodes::_irem: 1331 case Bytecodes::_ishl: 1332 case Bytecodes::_ishr: 1333 case Bytecodes::_isub: 1334 case Bytecodes::_iushr: 1335 case Bytecodes::_ixor: 1336 { 1337 pop_int(); 1338 pop_int(); 1339 push_int(); 1340 break; 1341 } 1342 case Bytecodes::_if_acmpeq: 1343 case Bytecodes::_if_acmpne: 1344 { 1345 pop_object(); 1346 pop_object(); 1347 break; 1348 } 1349 case Bytecodes::_if_icmpeq: 1350 case Bytecodes::_if_icmpge: 1351 case Bytecodes::_if_icmpgt: 1352 case Bytecodes::_if_icmple: 1353 case Bytecodes::_if_icmplt: 1354 case Bytecodes::_if_icmpne: 1355 { 1356 pop_int(); 1357 pop_int(); 1358 break; 1359 } 1360 case Bytecodes::_ifeq: 1361 case Bytecodes::_ifle: 1362 case Bytecodes::_iflt: 1363 case Bytecodes::_ifge: 1364 case Bytecodes::_ifgt: 1365 case Bytecodes::_ifne: 1366 case Bytecodes::_ireturn: 1367 case Bytecodes::_lookupswitch: 1368 case Bytecodes::_tableswitch: 1369 { 1370 pop_int(); 1371 break; 1372 } 1373 case Bytecodes::_iinc: 1374 { 1375 int lnum = str->get_index(); 1376 check_int(local(lnum)); 1377 store_to_local(lnum); 1378 break; 1379 } 1380 case Bytecodes::_iload: load_local_int(str->get_index()); break; 1381 case Bytecodes::_iload_0: load_local_int(0); break; 1382 case Bytecodes::_iload_1: load_local_int(1); break; 1383 case Bytecodes::_iload_2: load_local_int(2); break; 1384 case Bytecodes::_iload_3: load_local_int(3); break; 1385 1386 case Bytecodes::_instanceof: 1387 { 1388 // Check for uncommon trap: 1389 do_checkcast(str); 1390 pop_object(); 1391 push_int(); 1392 break; 1393 } 1394 case Bytecodes::_invokeinterface: do_invoke(str, true); break; 1395 case Bytecodes::_invokespecial: do_invoke(str, true); break; 1396 case Bytecodes::_invokestatic: do_invoke(str, false); break; 1397 case Bytecodes::_invokevirtual: do_invoke(str, true); break; 1398 case Bytecodes::_invokedynamic: do_invoke(str, false); break; 1399 1400 case Bytecodes::_istore: store_local_int(str->get_index()); break; 1401 case Bytecodes::_istore_0: store_local_int(0); break; 1402 case Bytecodes::_istore_1: store_local_int(1); break; 1403 case Bytecodes::_istore_2: store_local_int(2); break; 1404 case Bytecodes::_istore_3: store_local_int(3); break; 1405 1406 case Bytecodes::_jsr: 1407 case Bytecodes::_jsr_w: do_jsr(str); break; 1408 1409 case Bytecodes::_l2d: 1410 { 1411 pop_long(); 1412 push_double(); 1413 break; 1414 } 1415 case Bytecodes::_l2f: 1416 { 1417 pop_long(); 1418 push_float(); 1419 break; 1420 } 1421 case Bytecodes::_l2i: 1422 { 1423 pop_long(); 1424 push_int(); 1425 break; 1426 } 1427 case Bytecodes::_ladd: 1428 case Bytecodes::_land: 1429 case Bytecodes::_ldiv: 1430 case Bytecodes::_lmul: 1431 case Bytecodes::_lor: 1432 case Bytecodes::_lrem: 1433 case Bytecodes::_lsub: 1434 case Bytecodes::_lxor: 1435 { 1436 pop_long(); 1437 pop_long(); 1438 push_long(); 1439 break; 1440 } 1441 case Bytecodes::_laload: 1442 { 1443 pop_int(); 1444 ciTypeArrayKlass* array_klass = pop_typeArray(); 1445 // Put assert here for right type? 1446 push_long(); 1447 break; 1448 } 1449 case Bytecodes::_lastore: 1450 { 1451 pop_long(); 1452 pop_int(); 1453 pop_typeArray(); 1454 // assert here? 1455 break; 1456 } 1457 case Bytecodes::_lcmp: 1458 { 1459 pop_long(); 1460 pop_long(); 1461 push_int(); 1462 break; 1463 } 1464 case Bytecodes::_lconst_0: 1465 case Bytecodes::_lconst_1: 1466 { 1467 push_long(); 1468 break; 1469 } 1470 case Bytecodes::_ldc: 1471 case Bytecodes::_ldc_w: 1472 case Bytecodes::_ldc2_w: 1473 { 1474 do_ldc(str); 1475 break; 1476 } 1477 1478 case Bytecodes::_lload: load_local_long(str->get_index()); break; 1479 case Bytecodes::_lload_0: load_local_long(0); break; 1480 case Bytecodes::_lload_1: load_local_long(1); break; 1481 case Bytecodes::_lload_2: load_local_long(2); break; 1482 case Bytecodes::_lload_3: load_local_long(3); break; 1483 1484 case Bytecodes::_lneg: 1485 { 1486 pop_long(); 1487 push_long(); 1488 break; 1489 } 1490 case Bytecodes::_lreturn: 1491 { 1492 pop_long(); 1493 break; 1494 } 1495 case Bytecodes::_lshl: 1496 case Bytecodes::_lshr: 1497 case Bytecodes::_lushr: 1498 { 1499 pop_int(); 1500 pop_long(); 1501 push_long(); 1502 break; 1503 } 1504 case Bytecodes::_lstore: store_local_long(str->get_index()); break; 1505 case Bytecodes::_lstore_0: store_local_long(0); break; 1506 case Bytecodes::_lstore_1: store_local_long(1); break; 1507 case Bytecodes::_lstore_2: store_local_long(2); break; 1508 case Bytecodes::_lstore_3: store_local_long(3); break; 1509 1510 case Bytecodes::_multianewarray: do_multianewarray(str); break; 1511 1512 case Bytecodes::_new: do_new(str); break; 1513 1514 case Bytecodes::_newarray: do_newarray(str); break; 1515 1516 case Bytecodes::_pop: 1517 { 1518 pop(); 1519 break; 1520 } 1521 case Bytecodes::_pop2: 1522 { 1523 pop(); 1524 pop(); 1525 break; 1526 } 1527 1528 case Bytecodes::_putfield: do_putfield(str); break; 1529 case Bytecodes::_putstatic: do_putstatic(str); break; 1530 1531 case Bytecodes::_ret: do_ret(str); break; 1532 1533 case Bytecodes::_swap: 1534 { 1535 ciType* value1 = pop_value(); 1536 ciType* value2 = pop_value(); 1537 push(value1); 1538 push(value2); 1539 break; 1540 } 1541 1542 case Bytecodes::_wide: 1543 default: 1544 { 1545 // The iterator should skip this. 1546 ShouldNotReachHere(); 1547 break; 1548 } 1549 } 1550 1551 if (CITraceTypeFlow) { 1552 print_on(tty); 1553 } 1554 1555 return (_trap_bci != -1); 1556 } 1557 1558 #ifndef PRODUCT 1559 // ------------------------------------------------------------------ 1560 // ciTypeFlow::StateVector::print_cell_on 1561 void ciTypeFlow::StateVector::print_cell_on(outputStream* st, Cell c) const { 1562 ciType* type = type_at(c)->unwrap(); 1563 if (type == top_type()) { 1564 st->print("top"); 1565 } else if (type == bottom_type()) { 1566 st->print("bottom"); 1567 } else if (type == null_type()) { 1568 st->print("null"); 1569 } else if (type == long2_type()) { 1570 st->print("long2"); 1571 } else if (type == double2_type()) { 1572 st->print("double2"); 1573 } else if (is_int(type)) { 1574 st->print("int"); 1575 } else if (is_long(type)) { 1576 st->print("long"); 1577 } else if (is_float(type)) { 1578 st->print("float"); 1579 } else if (is_double(type)) { 1580 st->print("double"); 1581 } else if (type->is_return_address()) { 1582 st->print("address(%d)", type->as_return_address()->bci()); 1583 } else { 1584 if (type->is_klass()) { 1585 type->as_klass()->name()->print_symbol_on(st); 1586 } else { 1587 st->print("UNEXPECTED TYPE"); 1588 type->print(); 1589 } 1590 } 1591 } 1592 1593 // ------------------------------------------------------------------ 1594 // ciTypeFlow::StateVector::print_on 1595 void ciTypeFlow::StateVector::print_on(outputStream* st) const { 1596 int num_locals = _outer->max_locals(); 1597 int num_stack = stack_size(); 1598 int num_monitors = monitor_count(); 1599 st->print_cr(" State : locals %d, stack %d, monitors %d", num_locals, num_stack, num_monitors); 1600 if (num_stack >= 0) { 1601 int i; 1602 for (i = 0; i < num_locals; i++) { 1603 st->print(" local %2d : ", i); 1604 print_cell_on(st, local(i)); 1605 st->cr(); 1606 } 1607 for (i = 0; i < num_stack; i++) { 1608 st->print(" stack %2d : ", i); 1609 print_cell_on(st, stack(i)); 1610 st->cr(); 1611 } 1612 } 1613 } 1614 #endif 1615 1616 1617 // ------------------------------------------------------------------ 1618 // ciTypeFlow::SuccIter::next 1619 // 1620 void ciTypeFlow::SuccIter::next() { 1621 int succ_ct = _pred->successors()->length(); 1622 int next = _index + 1; 1623 if (next < succ_ct) { 1624 _index = next; 1625 _succ = _pred->successors()->at(next); 1626 return; 1627 } 1628 for (int i = next - succ_ct; i < _pred->exceptions()->length(); i++) { 1629 // Do not compile any code for unloaded exception types. 1630 // Following compiler passes are responsible for doing this also. 1631 ciInstanceKlass* exception_klass = _pred->exc_klasses()->at(i); 1632 if (exception_klass->is_loaded()) { 1633 _index = next; 1634 _succ = _pred->exceptions()->at(i); 1635 return; 1636 } 1637 next++; 1638 } 1639 _index = -1; 1640 _succ = nullptr; 1641 } 1642 1643 // ------------------------------------------------------------------ 1644 // ciTypeFlow::SuccIter::set_succ 1645 // 1646 void ciTypeFlow::SuccIter::set_succ(Block* succ) { 1647 int succ_ct = _pred->successors()->length(); 1648 if (_index < succ_ct) { 1649 _pred->successors()->at_put(_index, succ); 1650 } else { 1651 int idx = _index - succ_ct; 1652 _pred->exceptions()->at_put(idx, succ); 1653 } 1654 } 1655 1656 // ciTypeFlow::Block 1657 // 1658 // A basic block. 1659 1660 // ------------------------------------------------------------------ 1661 // ciTypeFlow::Block::Block 1662 ciTypeFlow::Block::Block(ciTypeFlow* outer, 1663 ciBlock *ciblk, 1664 ciTypeFlow::JsrSet* jsrs) : _predecessors(outer->arena(), 1, 0, nullptr) { 1665 _ciblock = ciblk; 1666 _exceptions = nullptr; 1667 _exc_klasses = nullptr; 1668 _successors = nullptr; 1669 _state = new (outer->arena()) StateVector(outer); 1670 JsrSet* new_jsrs = 1671 new (outer->arena()) JsrSet(outer->arena(), jsrs->size()); 1672 jsrs->copy_into(new_jsrs); 1673 _jsrs = new_jsrs; 1674 _next = nullptr; 1675 _on_work_list = false; 1676 _backedge_copy = false; 1677 _has_monitorenter = false; 1678 _trap_bci = -1; 1679 _trap_index = 0; 1680 df_init(); 1681 1682 if (CITraceTypeFlow) { 1683 tty->print_cr(">> Created new block"); 1684 print_on(tty); 1685 } 1686 1687 assert(this->outer() == outer, "outer link set up"); 1688 assert(!outer->have_block_count(), "must not have mapped blocks yet"); 1689 } 1690 1691 // ------------------------------------------------------------------ 1692 // ciTypeFlow::Block::df_init 1693 void ciTypeFlow::Block::df_init() { 1694 _pre_order = -1; assert(!has_pre_order(), ""); 1695 _post_order = -1; assert(!has_post_order(), ""); 1696 _loop = nullptr; 1697 _irreducible_loop_head = false; 1698 _irreducible_loop_secondary_entry = false; 1699 _rpo_next = nullptr; 1700 } 1701 1702 // ------------------------------------------------------------------ 1703 // ciTypeFlow::Block::successors 1704 // 1705 // Get the successors for this Block. 1706 GrowableArray<ciTypeFlow::Block*>* 1707 ciTypeFlow::Block::successors(ciBytecodeStream* str, 1708 ciTypeFlow::StateVector* state, 1709 ciTypeFlow::JsrSet* jsrs) { 1710 if (_successors == nullptr) { 1711 if (CITraceTypeFlow) { 1712 tty->print(">> Computing successors for block "); 1713 print_value_on(tty); 1714 tty->cr(); 1715 } 1716 1717 ciTypeFlow* analyzer = outer(); 1718 Arena* arena = analyzer->arena(); 1719 Block* block = nullptr; 1720 bool has_successor = !has_trap() && 1721 (control() != ciBlock::fall_through_bci || limit() < analyzer->code_size()); 1722 if (!has_successor) { 1723 _successors = 1724 new (arena) GrowableArray<Block*>(arena, 1, 0, nullptr); 1725 // No successors 1726 } else if (control() == ciBlock::fall_through_bci) { 1727 assert(str->cur_bci() == limit(), "bad block end"); 1728 // This block simply falls through to the next. 1729 _successors = 1730 new (arena) GrowableArray<Block*>(arena, 1, 0, nullptr); 1731 1732 Block* block = analyzer->block_at(limit(), _jsrs); 1733 assert(_successors->length() == FALL_THROUGH, ""); 1734 _successors->append(block); 1735 } else { 1736 int current_bci = str->cur_bci(); 1737 int next_bci = str->next_bci(); 1738 int branch_bci = -1; 1739 Block* target = nullptr; 1740 assert(str->next_bci() == limit(), "bad block end"); 1741 // This block is not a simple fall-though. Interpret 1742 // the current bytecode to find our successors. 1743 switch (str->cur_bc()) { 1744 case Bytecodes::_ifeq: case Bytecodes::_ifne: 1745 case Bytecodes::_iflt: case Bytecodes::_ifge: 1746 case Bytecodes::_ifgt: case Bytecodes::_ifle: 1747 case Bytecodes::_if_icmpeq: case Bytecodes::_if_icmpne: 1748 case Bytecodes::_if_icmplt: case Bytecodes::_if_icmpge: 1749 case Bytecodes::_if_icmpgt: case Bytecodes::_if_icmple: 1750 case Bytecodes::_if_acmpeq: case Bytecodes::_if_acmpne: 1751 case Bytecodes::_ifnull: case Bytecodes::_ifnonnull: 1752 // Our successors are the branch target and the next bci. 1753 branch_bci = str->get_dest(); 1754 _successors = 1755 new (arena) GrowableArray<Block*>(arena, 2, 0, nullptr); 1756 assert(_successors->length() == IF_NOT_TAKEN, ""); 1757 _successors->append(analyzer->block_at(next_bci, jsrs)); 1758 assert(_successors->length() == IF_TAKEN, ""); 1759 _successors->append(analyzer->block_at(branch_bci, jsrs)); 1760 break; 1761 1762 case Bytecodes::_goto: 1763 branch_bci = str->get_dest(); 1764 _successors = 1765 new (arena) GrowableArray<Block*>(arena, 1, 0, nullptr); 1766 assert(_successors->length() == GOTO_TARGET, ""); 1767 _successors->append(analyzer->block_at(branch_bci, jsrs)); 1768 break; 1769 1770 case Bytecodes::_jsr: 1771 branch_bci = str->get_dest(); 1772 _successors = 1773 new (arena) GrowableArray<Block*>(arena, 1, 0, nullptr); 1774 assert(_successors->length() == GOTO_TARGET, ""); 1775 _successors->append(analyzer->block_at(branch_bci, jsrs)); 1776 break; 1777 1778 case Bytecodes::_goto_w: 1779 case Bytecodes::_jsr_w: 1780 _successors = 1781 new (arena) GrowableArray<Block*>(arena, 1, 0, nullptr); 1782 assert(_successors->length() == GOTO_TARGET, ""); 1783 _successors->append(analyzer->block_at(str->get_far_dest(), jsrs)); 1784 break; 1785 1786 case Bytecodes::_tableswitch: { 1787 Bytecode_tableswitch tableswitch(str); 1788 1789 int len = tableswitch.length(); 1790 _successors = 1791 new (arena) GrowableArray<Block*>(arena, len+1, 0, nullptr); 1792 int bci = current_bci + tableswitch.default_offset(); 1793 Block* block = analyzer->block_at(bci, jsrs); 1794 assert(_successors->length() == SWITCH_DEFAULT, ""); 1795 _successors->append(block); 1796 while (--len >= 0) { 1797 int bci = current_bci + tableswitch.dest_offset_at(len); 1798 block = analyzer->block_at(bci, jsrs); 1799 assert(_successors->length() >= SWITCH_CASES, ""); 1800 _successors->append_if_missing(block); 1801 } 1802 break; 1803 } 1804 1805 case Bytecodes::_lookupswitch: { 1806 Bytecode_lookupswitch lookupswitch(str); 1807 1808 int npairs = lookupswitch.number_of_pairs(); 1809 _successors = 1810 new (arena) GrowableArray<Block*>(arena, npairs+1, 0, nullptr); 1811 int bci = current_bci + lookupswitch.default_offset(); 1812 Block* block = analyzer->block_at(bci, jsrs); 1813 assert(_successors->length() == SWITCH_DEFAULT, ""); 1814 _successors->append(block); 1815 while(--npairs >= 0) { 1816 LookupswitchPair pair = lookupswitch.pair_at(npairs); 1817 int bci = current_bci + pair.offset(); 1818 Block* block = analyzer->block_at(bci, jsrs); 1819 assert(_successors->length() >= SWITCH_CASES, ""); 1820 _successors->append_if_missing(block); 1821 } 1822 break; 1823 } 1824 1825 case Bytecodes::_athrow: 1826 case Bytecodes::_ireturn: 1827 case Bytecodes::_lreturn: 1828 case Bytecodes::_freturn: 1829 case Bytecodes::_dreturn: 1830 case Bytecodes::_areturn: 1831 case Bytecodes::_return: 1832 _successors = 1833 new (arena) GrowableArray<Block*>(arena, 1, 0, nullptr); 1834 // No successors 1835 break; 1836 1837 case Bytecodes::_ret: { 1838 _successors = 1839 new (arena) GrowableArray<Block*>(arena, 1, 0, nullptr); 1840 1841 Cell local = state->local(str->get_index()); 1842 ciType* return_address = state->type_at(local); 1843 assert(return_address->is_return_address(), "verify: wrong type"); 1844 int bci = return_address->as_return_address()->bci(); 1845 assert(_successors->length() == GOTO_TARGET, ""); 1846 _successors->append(analyzer->block_at(bci, jsrs)); 1847 break; 1848 } 1849 1850 case Bytecodes::_wide: 1851 default: 1852 ShouldNotReachHere(); 1853 break; 1854 } 1855 } 1856 1857 // Set predecessor information 1858 for (int i = 0; i < _successors->length(); i++) { 1859 Block* block = _successors->at(i); 1860 block->predecessors()->append(this); 1861 } 1862 } 1863 return _successors; 1864 } 1865 1866 // ------------------------------------------------------------------ 1867 // ciTypeFlow::Block:compute_exceptions 1868 // 1869 // Compute the exceptional successors and types for this Block. 1870 void ciTypeFlow::Block::compute_exceptions() { 1871 assert(_exceptions == nullptr && _exc_klasses == nullptr, "repeat"); 1872 1873 if (CITraceTypeFlow) { 1874 tty->print(">> Computing exceptions for block "); 1875 print_value_on(tty); 1876 tty->cr(); 1877 } 1878 1879 ciTypeFlow* analyzer = outer(); 1880 Arena* arena = analyzer->arena(); 1881 1882 // Any bci in the block will do. 1883 ciExceptionHandlerStream str(analyzer->method(), start()); 1884 1885 // Allocate our growable arrays. 1886 int exc_count = str.count(); 1887 _exceptions = new (arena) GrowableArray<Block*>(arena, exc_count, 0, nullptr); 1888 _exc_klasses = new (arena) GrowableArray<ciInstanceKlass*>(arena, exc_count, 1889 0, nullptr); 1890 1891 for ( ; !str.is_done(); str.next()) { 1892 ciExceptionHandler* handler = str.handler(); 1893 int bci = handler->handler_bci(); 1894 ciInstanceKlass* klass = nullptr; 1895 if (bci == -1) { 1896 // There is no catch all. It is possible to exit the method. 1897 break; 1898 } 1899 if (handler->is_catch_all()) { 1900 klass = analyzer->env()->Throwable_klass(); 1901 } else { 1902 klass = handler->catch_klass(); 1903 } 1904 Block* block = analyzer->block_at(bci, _jsrs); 1905 _exceptions->append(block); 1906 block->predecessors()->append(this); 1907 _exc_klasses->append(klass); 1908 } 1909 } 1910 1911 // ------------------------------------------------------------------ 1912 // ciTypeFlow::Block::set_backedge_copy 1913 // Use this only to make a pre-existing public block into a backedge copy. 1914 void ciTypeFlow::Block::set_backedge_copy(bool z) { 1915 assert(z || (z == is_backedge_copy()), "cannot make a backedge copy public"); 1916 _backedge_copy = z; 1917 } 1918 1919 // Analogous to PhaseIdealLoop::is_in_irreducible_loop 1920 bool ciTypeFlow::Block::is_in_irreducible_loop() const { 1921 if (!outer()->has_irreducible_entry()) { 1922 return false; // No irreducible loop in method. 1923 } 1924 Loop* lp = loop(); // Innermost loop containing block. 1925 if (lp == nullptr) { 1926 assert(!is_post_visited(), "must have enclosing loop once post-visited"); 1927 return false; // Not yet processed, so we do not know, yet. 1928 } 1929 // Walk all the way up the loop-tree, search for an irreducible loop. 1930 do { 1931 if (lp->is_irreducible()) { 1932 return true; // We are in irreducible loop. 1933 } 1934 if (lp->head()->pre_order() == 0) { 1935 return false; // Found root loop, terminate. 1936 } 1937 lp = lp->parent(); 1938 } while (lp != nullptr); 1939 // We have "lp->parent() == nullptr", which happens only for infinite loops, 1940 // where no parent is attached to the loop. We did not find any irreducible 1941 // loop from this block out to lp. Thus lp only has one entry, and no exit 1942 // (it is infinite and reducible). We can always rewrite an infinite loop 1943 // that is nested inside other loops: 1944 // while(condition) { infinite_loop; } 1945 // with an equivalent program where the infinite loop is an outermost loop 1946 // that is not nested in any loop: 1947 // while(condition) { break; } infinite_loop; 1948 // Thus, we can understand lp as an outermost loop, and can terminate and 1949 // conclude: this block is in no irreducible loop. 1950 return false; 1951 } 1952 1953 // ------------------------------------------------------------------ 1954 // ciTypeFlow::Block::is_clonable_exit 1955 // 1956 // At most 2 normal successors, one of which continues looping, 1957 // and all exceptional successors must exit. 1958 bool ciTypeFlow::Block::is_clonable_exit(ciTypeFlow::Loop* lp) { 1959 int normal_cnt = 0; 1960 int in_loop_cnt = 0; 1961 for (SuccIter iter(this); !iter.done(); iter.next()) { 1962 Block* succ = iter.succ(); 1963 if (iter.is_normal_ctrl()) { 1964 if (++normal_cnt > 2) return false; 1965 if (lp->contains(succ->loop())) { 1966 if (++in_loop_cnt > 1) return false; 1967 } 1968 } else { 1969 if (lp->contains(succ->loop())) return false; 1970 } 1971 } 1972 return in_loop_cnt == 1; 1973 } 1974 1975 // ------------------------------------------------------------------ 1976 // ciTypeFlow::Block::looping_succ 1977 // 1978 ciTypeFlow::Block* ciTypeFlow::Block::looping_succ(ciTypeFlow::Loop* lp) { 1979 assert(successors()->length() <= 2, "at most 2 normal successors"); 1980 for (SuccIter iter(this); !iter.done(); iter.next()) { 1981 Block* succ = iter.succ(); 1982 if (lp->contains(succ->loop())) { 1983 return succ; 1984 } 1985 } 1986 return nullptr; 1987 } 1988 1989 #ifndef PRODUCT 1990 // ------------------------------------------------------------------ 1991 // ciTypeFlow::Block::print_value_on 1992 void ciTypeFlow::Block::print_value_on(outputStream* st) const { 1993 if (has_pre_order()) st->print("#%-2d ", pre_order()); 1994 if (has_rpo()) st->print("rpo#%-2d ", rpo()); 1995 st->print("[%d - %d)", start(), limit()); 1996 if (is_loop_head()) st->print(" lphd"); 1997 if (is_in_irreducible_loop()) st->print(" in_irred"); 1998 if (is_irreducible_loop_head()) st->print(" irred_head"); 1999 if (is_irreducible_loop_secondary_entry()) st->print(" irred_entry"); 2000 if (_jsrs->size() > 0) { st->print("/"); _jsrs->print_on(st); } 2001 if (is_backedge_copy()) st->print("/backedge_copy"); 2002 } 2003 2004 // ------------------------------------------------------------------ 2005 // ciTypeFlow::Block::print_on 2006 void ciTypeFlow::Block::print_on(outputStream* st) const { 2007 if ((Verbose || WizardMode) && (limit() >= 0)) { 2008 // Don't print 'dummy' blocks (i.e. blocks with limit() '-1') 2009 outer()->method()->print_codes_on(start(), limit(), st); 2010 } 2011 st->print_cr(" ==================================================== "); 2012 st->print (" "); 2013 print_value_on(st); 2014 st->print(" Stored locals: "); def_locals()->print_on(st, outer()->method()->max_locals()); tty->cr(); 2015 if (loop() && loop()->parent() != nullptr) { 2016 st->print(" loops:"); 2017 Loop* lp = loop(); 2018 do { 2019 st->print(" %d<-%d", lp->head()->pre_order(),lp->tail()->pre_order()); 2020 if (lp->is_irreducible()) st->print("(ir)"); 2021 lp = lp->parent(); 2022 } while (lp->parent() != nullptr); 2023 } 2024 st->cr(); 2025 _state->print_on(st); 2026 if (_successors == nullptr) { 2027 st->print_cr(" No successor information"); 2028 } else { 2029 int num_successors = _successors->length(); 2030 st->print_cr(" Successors : %d", num_successors); 2031 for (int i = 0; i < num_successors; i++) { 2032 Block* successor = _successors->at(i); 2033 st->print(" "); 2034 successor->print_value_on(st); 2035 st->cr(); 2036 } 2037 } 2038 if (_predecessors.is_empty()) { 2039 st->print_cr(" No predecessor information"); 2040 } else { 2041 int num_predecessors = _predecessors.length(); 2042 st->print_cr(" Predecessors : %d", num_predecessors); 2043 for (int i = 0; i < num_predecessors; i++) { 2044 Block* predecessor = _predecessors.at(i); 2045 st->print(" "); 2046 predecessor->print_value_on(st); 2047 st->cr(); 2048 } 2049 } 2050 if (_exceptions == nullptr) { 2051 st->print_cr(" No exception information"); 2052 } else { 2053 int num_exceptions = _exceptions->length(); 2054 st->print_cr(" Exceptions : %d", num_exceptions); 2055 for (int i = 0; i < num_exceptions; i++) { 2056 Block* exc_succ = _exceptions->at(i); 2057 ciInstanceKlass* exc_klass = _exc_klasses->at(i); 2058 st->print(" "); 2059 exc_succ->print_value_on(st); 2060 st->print(" -- "); 2061 exc_klass->name()->print_symbol_on(st); 2062 st->cr(); 2063 } 2064 } 2065 if (has_trap()) { 2066 st->print_cr(" Traps on %d with trap index %d", trap_bci(), trap_index()); 2067 } 2068 st->print_cr(" ==================================================== "); 2069 } 2070 #endif 2071 2072 #ifndef PRODUCT 2073 // ------------------------------------------------------------------ 2074 // ciTypeFlow::LocalSet::print_on 2075 void ciTypeFlow::LocalSet::print_on(outputStream* st, int limit) const { 2076 st->print("{"); 2077 for (int i = 0; i < max; i++) { 2078 if (test(i)) st->print(" %d", i); 2079 } 2080 if (limit > max) { 2081 st->print(" %d..%d ", max, limit); 2082 } 2083 st->print(" }"); 2084 } 2085 #endif 2086 2087 // ciTypeFlow 2088 // 2089 // This is a pass over the bytecodes which computes the following: 2090 // basic block structure 2091 // interpreter type-states (a la the verifier) 2092 2093 // ------------------------------------------------------------------ 2094 // ciTypeFlow::ciTypeFlow 2095 ciTypeFlow::ciTypeFlow(ciEnv* env, ciMethod* method, int osr_bci) { 2096 _env = env; 2097 _method = method; 2098 _has_irreducible_entry = false; 2099 _osr_bci = osr_bci; 2100 _failure_reason = nullptr; 2101 assert(0 <= start_bci() && start_bci() < code_size() , "correct osr_bci argument: 0 <= %d < %d", start_bci(), code_size()); 2102 _work_list = nullptr; 2103 2104 int ciblock_count = _method->get_method_blocks()->num_blocks(); 2105 _idx_to_blocklist = NEW_ARENA_ARRAY(arena(), GrowableArray<Block*>*, ciblock_count); 2106 for (int i = 0; i < ciblock_count; i++) { 2107 _idx_to_blocklist[i] = nullptr; 2108 } 2109 _block_map = nullptr; // until all blocks are seen 2110 _jsr_records = nullptr; 2111 } 2112 2113 // ------------------------------------------------------------------ 2114 // ciTypeFlow::work_list_next 2115 // 2116 // Get the next basic block from our work list. 2117 ciTypeFlow::Block* ciTypeFlow::work_list_next() { 2118 assert(!work_list_empty(), "work list must not be empty"); 2119 Block* next_block = _work_list; 2120 _work_list = next_block->next(); 2121 next_block->set_next(nullptr); 2122 next_block->set_on_work_list(false); 2123 return next_block; 2124 } 2125 2126 // ------------------------------------------------------------------ 2127 // ciTypeFlow::add_to_work_list 2128 // 2129 // Add a basic block to our work list. 2130 // List is sorted by decreasing postorder sort (same as increasing RPO) 2131 void ciTypeFlow::add_to_work_list(ciTypeFlow::Block* block) { 2132 assert(!block->is_on_work_list(), "must not already be on work list"); 2133 2134 if (CITraceTypeFlow) { 2135 tty->print(">> Adding block "); 2136 block->print_value_on(tty); 2137 tty->print_cr(" to the work list : "); 2138 } 2139 2140 block->set_on_work_list(true); 2141 2142 // decreasing post order sort 2143 2144 Block* prev = nullptr; 2145 Block* current = _work_list; 2146 int po = block->post_order(); 2147 while (current != nullptr) { 2148 if (!current->has_post_order() || po > current->post_order()) 2149 break; 2150 prev = current; 2151 current = current->next(); 2152 } 2153 if (prev == nullptr) { 2154 block->set_next(_work_list); 2155 _work_list = block; 2156 } else { 2157 block->set_next(current); 2158 prev->set_next(block); 2159 } 2160 2161 if (CITraceTypeFlow) { 2162 tty->cr(); 2163 } 2164 } 2165 2166 // ------------------------------------------------------------------ 2167 // ciTypeFlow::block_at 2168 // 2169 // Return the block beginning at bci which has a JsrSet compatible 2170 // with jsrs. 2171 ciTypeFlow::Block* ciTypeFlow::block_at(int bci, ciTypeFlow::JsrSet* jsrs, CreateOption option) { 2172 // First find the right ciBlock. 2173 if (CITraceTypeFlow) { 2174 tty->print(">> Requesting block for %d/", bci); 2175 jsrs->print_on(tty); 2176 tty->cr(); 2177 } 2178 2179 ciBlock* ciblk = _method->get_method_blocks()->block_containing(bci); 2180 assert(ciblk->start_bci() == bci, "bad ciBlock boundaries"); 2181 Block* block = get_block_for(ciblk->index(), jsrs, option); 2182 2183 assert(block == nullptr? (option == no_create): block->is_backedge_copy() == (option == create_backedge_copy), "create option consistent with result"); 2184 2185 if (CITraceTypeFlow) { 2186 if (block != nullptr) { 2187 tty->print(">> Found block "); 2188 block->print_value_on(tty); 2189 tty->cr(); 2190 } else { 2191 tty->print_cr(">> No such block."); 2192 } 2193 } 2194 2195 return block; 2196 } 2197 2198 // ------------------------------------------------------------------ 2199 // ciTypeFlow::make_jsr_record 2200 // 2201 // Make a JsrRecord for a given (entry, return) pair, if such a record 2202 // does not already exist. 2203 ciTypeFlow::JsrRecord* ciTypeFlow::make_jsr_record(int entry_address, 2204 int return_address) { 2205 if (_jsr_records == nullptr) { 2206 _jsr_records = new (arena()) GrowableArray<JsrRecord*>(arena(), 2207 2, 2208 0, 2209 nullptr); 2210 } 2211 JsrRecord* record = nullptr; 2212 int len = _jsr_records->length(); 2213 for (int i = 0; i < len; i++) { 2214 JsrRecord* record = _jsr_records->at(i); 2215 if (record->entry_address() == entry_address && 2216 record->return_address() == return_address) { 2217 return record; 2218 } 2219 } 2220 2221 record = new (arena()) JsrRecord(entry_address, return_address); 2222 _jsr_records->append(record); 2223 return record; 2224 } 2225 2226 // ------------------------------------------------------------------ 2227 // ciTypeFlow::flow_exceptions 2228 // 2229 // Merge the current state into all exceptional successors at the 2230 // current point in the code. 2231 void ciTypeFlow::flow_exceptions(GrowableArray<ciTypeFlow::Block*>* exceptions, 2232 GrowableArray<ciInstanceKlass*>* exc_klasses, 2233 ciTypeFlow::StateVector* state) { 2234 int len = exceptions->length(); 2235 assert(exc_klasses->length() == len, "must have same length"); 2236 for (int i = 0; i < len; i++) { 2237 Block* block = exceptions->at(i); 2238 ciInstanceKlass* exception_klass = exc_klasses->at(i); 2239 2240 if (!exception_klass->is_loaded()) { 2241 // Do not compile any code for unloaded exception types. 2242 // Following compiler passes are responsible for doing this also. 2243 continue; 2244 } 2245 2246 if (block->meet_exception(exception_klass, state)) { 2247 // Block was modified and has PO. Add it to the work list. 2248 if (block->has_post_order() && 2249 !block->is_on_work_list()) { 2250 add_to_work_list(block); 2251 } 2252 } 2253 } 2254 } 2255 2256 // ------------------------------------------------------------------ 2257 // ciTypeFlow::flow_successors 2258 // 2259 // Merge the current state into all successors at the current point 2260 // in the code. 2261 void ciTypeFlow::flow_successors(GrowableArray<ciTypeFlow::Block*>* successors, 2262 ciTypeFlow::StateVector* state) { 2263 int len = successors->length(); 2264 for (int i = 0; i < len; i++) { 2265 Block* block = successors->at(i); 2266 if (block->meet(state)) { 2267 // Block was modified and has PO. Add it to the work list. 2268 if (block->has_post_order() && 2269 !block->is_on_work_list()) { 2270 add_to_work_list(block); 2271 } 2272 } 2273 } 2274 } 2275 2276 // ------------------------------------------------------------------ 2277 // ciTypeFlow::can_trap 2278 // 2279 // Tells if a given instruction is able to generate an exception edge. 2280 bool ciTypeFlow::can_trap(ciBytecodeStream& str) { 2281 // Cf. GenerateOopMap::do_exception_edge. 2282 if (!Bytecodes::can_trap(str.cur_bc())) return false; 2283 2284 switch (str.cur_bc()) { 2285 // %%% FIXME: ldc of Class can generate an exception 2286 case Bytecodes::_ldc: 2287 case Bytecodes::_ldc_w: 2288 case Bytecodes::_ldc2_w: 2289 return str.is_in_error(); 2290 2291 case Bytecodes::_aload_0: 2292 // These bytecodes can trap for rewriting. We need to assume that 2293 // they do not throw exceptions to make the monitor analysis work. 2294 return false; 2295 2296 case Bytecodes::_ireturn: 2297 case Bytecodes::_lreturn: 2298 case Bytecodes::_freturn: 2299 case Bytecodes::_dreturn: 2300 case Bytecodes::_areturn: 2301 case Bytecodes::_return: 2302 // We can assume the monitor stack is empty in this analysis. 2303 return false; 2304 2305 case Bytecodes::_monitorexit: 2306 // We can assume monitors are matched in this analysis. 2307 return false; 2308 2309 default: 2310 return true; 2311 } 2312 } 2313 2314 // ------------------------------------------------------------------ 2315 // ciTypeFlow::clone_loop_heads 2316 // 2317 // Clone the loop heads 2318 bool ciTypeFlow::clone_loop_heads(StateVector* temp_vector, JsrSet* temp_set) { 2319 bool rslt = false; 2320 for (PreorderLoops iter(loop_tree_root()); !iter.done(); iter.next()) { 2321 Loop* lp = iter.current(); 2322 Block* head = lp->head(); 2323 if (lp == loop_tree_root() || 2324 lp->is_irreducible() || 2325 !head->is_clonable_exit(lp)) 2326 continue; 2327 2328 // Avoid BoxLock merge. 2329 if (EliminateNestedLocks && head->has_monitorenter()) 2330 continue; 2331 2332 // check not already cloned 2333 if (head->backedge_copy_count() != 0) 2334 continue; 2335 2336 // Don't clone head of OSR loop to get correct types in start block. 2337 if (is_osr_flow() && head->start() == start_bci()) 2338 continue; 2339 2340 // check _no_ shared head below us 2341 Loop* ch; 2342 for (ch = lp->child(); ch != nullptr && ch->head() != head; ch = ch->sibling()); 2343 if (ch != nullptr) 2344 continue; 2345 2346 // Clone head 2347 Block* new_head = head->looping_succ(lp); 2348 Block* clone = clone_loop_head(lp, temp_vector, temp_set); 2349 // Update lp's info 2350 clone->set_loop(lp); 2351 lp->set_head(new_head); 2352 lp->set_tail(clone); 2353 // And move original head into outer loop 2354 head->set_loop(lp->parent()); 2355 2356 rslt = true; 2357 } 2358 return rslt; 2359 } 2360 2361 // ------------------------------------------------------------------ 2362 // ciTypeFlow::clone_loop_head 2363 // 2364 // Clone lp's head and replace tail's successors with clone. 2365 // 2366 // | 2367 // v 2368 // head <-> body 2369 // | 2370 // v 2371 // exit 2372 // 2373 // new_head 2374 // 2375 // | 2376 // v 2377 // head ----------\ 2378 // | | 2379 // | v 2380 // | clone <-> body 2381 // | | 2382 // | /--/ 2383 // | | 2384 // v v 2385 // exit 2386 // 2387 ciTypeFlow::Block* ciTypeFlow::clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) { 2388 Block* head = lp->head(); 2389 Block* tail = lp->tail(); 2390 if (CITraceTypeFlow) { 2391 tty->print(">> Requesting clone of loop head "); head->print_value_on(tty); 2392 tty->print(" for predecessor "); tail->print_value_on(tty); 2393 tty->cr(); 2394 } 2395 Block* clone = block_at(head->start(), head->jsrs(), create_backedge_copy); 2396 assert(clone->backedge_copy_count() == 1, "one backedge copy for all back edges"); 2397 2398 assert(!clone->has_pre_order(), "just created"); 2399 clone->set_next_pre_order(); 2400 2401 // Accumulate profiled count for all backedges that share this loop's head 2402 int total_count = lp->profiled_count(); 2403 for (Loop* lp1 = lp->parent(); lp1 != nullptr; lp1 = lp1->parent()) { 2404 for (Loop* lp2 = lp1; lp2 != nullptr; lp2 = lp2->sibling()) { 2405 if (lp2->head() == head && !lp2->tail()->is_backedge_copy()) { 2406 total_count += lp2->profiled_count(); 2407 } 2408 } 2409 } 2410 // Have the most frequent ones branch to the clone instead 2411 int count = 0; 2412 int loops_with_shared_head = 0; 2413 Block* latest_tail = tail; 2414 bool done = false; 2415 for (Loop* lp1 = lp; lp1 != nullptr && !done; lp1 = lp1->parent()) { 2416 for (Loop* lp2 = lp1; lp2 != nullptr && !done; lp2 = lp2->sibling()) { 2417 if (lp2->head() == head && !lp2->tail()->is_backedge_copy()) { 2418 count += lp2->profiled_count(); 2419 if (lp2->tail()->post_order() < latest_tail->post_order()) { 2420 latest_tail = lp2->tail(); 2421 } 2422 loops_with_shared_head++; 2423 for (SuccIter iter(lp2->tail()); !iter.done(); iter.next()) { 2424 if (iter.succ() == head) { 2425 iter.set_succ(clone); 2426 // Update predecessor information 2427 head->predecessors()->remove(lp2->tail()); 2428 clone->predecessors()->append(lp2->tail()); 2429 } 2430 } 2431 flow_block(lp2->tail(), temp_vector, temp_set); 2432 if (lp2->head() == lp2->tail()) { 2433 // For self-loops, clone->head becomes clone->clone 2434 flow_block(clone, temp_vector, temp_set); 2435 for (SuccIter iter(clone); !iter.done(); iter.next()) { 2436 if (iter.succ() == lp2->head()) { 2437 iter.set_succ(clone); 2438 // Update predecessor information 2439 lp2->head()->predecessors()->remove(clone); 2440 clone->predecessors()->append(clone); 2441 break; 2442 } 2443 } 2444 } 2445 if (total_count == 0 || count > (total_count * .9)) { 2446 done = true; 2447 } 2448 } 2449 } 2450 } 2451 assert(loops_with_shared_head >= 1, "at least one new"); 2452 clone->set_rpo_next(latest_tail->rpo_next()); 2453 latest_tail->set_rpo_next(clone); 2454 flow_block(clone, temp_vector, temp_set); 2455 2456 return clone; 2457 } 2458 2459 // ------------------------------------------------------------------ 2460 // ciTypeFlow::flow_block 2461 // 2462 // Interpret the effects of the bytecodes on the incoming state 2463 // vector of a basic block. Push the changed state to succeeding 2464 // basic blocks. 2465 void ciTypeFlow::flow_block(ciTypeFlow::Block* block, 2466 ciTypeFlow::StateVector* state, 2467 ciTypeFlow::JsrSet* jsrs) { 2468 if (CITraceTypeFlow) { 2469 tty->print("\n>> ANALYZING BLOCK : "); 2470 tty->cr(); 2471 block->print_on(tty); 2472 } 2473 assert(block->has_pre_order(), "pre-order is assigned before 1st flow"); 2474 2475 int start = block->start(); 2476 int limit = block->limit(); 2477 int control = block->control(); 2478 if (control != ciBlock::fall_through_bci) { 2479 limit = control; 2480 } 2481 2482 // Grab the state from the current block. 2483 block->copy_state_into(state); 2484 state->def_locals()->clear(); 2485 2486 GrowableArray<Block*>* exceptions = block->exceptions(); 2487 GrowableArray<ciInstanceKlass*>* exc_klasses = block->exc_klasses(); 2488 bool has_exceptions = exceptions->length() > 0; 2489 2490 bool exceptions_used = false; 2491 2492 ciBytecodeStream str(method()); 2493 str.reset_to_bci(start); 2494 Bytecodes::Code code; 2495 while ((code = str.next()) != ciBytecodeStream::EOBC() && 2496 str.cur_bci() < limit) { 2497 // Check for exceptional control flow from this point. 2498 if (has_exceptions && can_trap(str)) { 2499 flow_exceptions(exceptions, exc_klasses, state); 2500 exceptions_used = true; 2501 } 2502 // Apply the effects of the current bytecode to our state. 2503 bool res = state->apply_one_bytecode(&str); 2504 2505 // Watch for bailouts. 2506 if (failing()) return; 2507 2508 if (str.cur_bc() == Bytecodes::_monitorenter) { 2509 block->set_has_monitorenter(); 2510 } 2511 2512 if (res) { 2513 2514 // We have encountered a trap. Record it in this block. 2515 block->set_trap(state->trap_bci(), state->trap_index()); 2516 2517 if (CITraceTypeFlow) { 2518 tty->print_cr(">> Found trap"); 2519 block->print_on(tty); 2520 } 2521 2522 // Save set of locals defined in this block 2523 block->def_locals()->add(state->def_locals()); 2524 2525 // Record (no) successors. 2526 block->successors(&str, state, jsrs); 2527 2528 assert(!has_exceptions || exceptions_used, "Not removing exceptions"); 2529 2530 // Discontinue interpretation of this Block. 2531 return; 2532 } 2533 } 2534 2535 GrowableArray<Block*>* successors = nullptr; 2536 if (control != ciBlock::fall_through_bci) { 2537 // Check for exceptional control flow from this point. 2538 if (has_exceptions && can_trap(str)) { 2539 flow_exceptions(exceptions, exc_klasses, state); 2540 exceptions_used = true; 2541 } 2542 2543 // Fix the JsrSet to reflect effect of the bytecode. 2544 block->copy_jsrs_into(jsrs); 2545 jsrs->apply_control(this, &str, state); 2546 2547 // Find successor edges based on old state and new JsrSet. 2548 successors = block->successors(&str, state, jsrs); 2549 2550 // Apply the control changes to the state. 2551 state->apply_one_bytecode(&str); 2552 } else { 2553 // Fall through control 2554 successors = block->successors(&str, nullptr, nullptr); 2555 } 2556 2557 // Save set of locals defined in this block 2558 block->def_locals()->add(state->def_locals()); 2559 2560 // Remove untaken exception paths 2561 if (!exceptions_used) 2562 exceptions->clear(); 2563 2564 // Pass our state to successors. 2565 flow_successors(successors, state); 2566 } 2567 2568 // ------------------------------------------------------------------ 2569 // ciTypeFlow::PreOrderLoops::next 2570 // 2571 // Advance to next loop tree using a preorder, left-to-right traversal. 2572 void ciTypeFlow::PreorderLoops::next() { 2573 assert(!done(), "must not be done."); 2574 if (_current->child() != nullptr) { 2575 _current = _current->child(); 2576 } else if (_current->sibling() != nullptr) { 2577 _current = _current->sibling(); 2578 } else { 2579 while (_current != _root && _current->sibling() == nullptr) { 2580 _current = _current->parent(); 2581 } 2582 if (_current == _root) { 2583 _current = nullptr; 2584 assert(done(), "must be done."); 2585 } else { 2586 assert(_current->sibling() != nullptr, "must be more to do"); 2587 _current = _current->sibling(); 2588 } 2589 } 2590 } 2591 2592 // If the tail is a branch to the head, retrieve how many times that path was taken from profiling 2593 int ciTypeFlow::Loop::profiled_count() { 2594 if (_profiled_count >= 0) { 2595 return _profiled_count; 2596 } 2597 ciMethodData* methodData = outer()->method()->method_data(); 2598 if (!methodData->is_mature()) { 2599 _profiled_count = 0; 2600 return 0; 2601 } 2602 ciTypeFlow::Block* tail = this->tail(); 2603 if (tail->control() == -1 || tail->has_trap()) { 2604 _profiled_count = 0; 2605 return 0; 2606 } 2607 2608 ciProfileData* data = methodData->bci_to_data(tail->control()); 2609 2610 if (data == nullptr || !data->is_JumpData()) { 2611 _profiled_count = 0; 2612 return 0; 2613 } 2614 2615 ciBytecodeStream iter(outer()->method()); 2616 iter.reset_to_bci(tail->control()); 2617 2618 bool is_an_if = false; 2619 bool wide = false; 2620 Bytecodes::Code bc = iter.next(); 2621 switch (bc) { 2622 case Bytecodes::_ifeq: 2623 case Bytecodes::_ifne: 2624 case Bytecodes::_iflt: 2625 case Bytecodes::_ifge: 2626 case Bytecodes::_ifgt: 2627 case Bytecodes::_ifle: 2628 case Bytecodes::_if_icmpeq: 2629 case Bytecodes::_if_icmpne: 2630 case Bytecodes::_if_icmplt: 2631 case Bytecodes::_if_icmpge: 2632 case Bytecodes::_if_icmpgt: 2633 case Bytecodes::_if_icmple: 2634 case Bytecodes::_if_acmpeq: 2635 case Bytecodes::_if_acmpne: 2636 case Bytecodes::_ifnull: 2637 case Bytecodes::_ifnonnull: 2638 is_an_if = true; 2639 break; 2640 case Bytecodes::_goto_w: 2641 case Bytecodes::_jsr_w: 2642 wide = true; 2643 break; 2644 case Bytecodes::_goto: 2645 case Bytecodes::_jsr: 2646 break; 2647 default: 2648 fatal(" invalid bytecode: %s", Bytecodes::name(iter.cur_bc())); 2649 } 2650 2651 GrowableArray<ciTypeFlow::Block*>* succs = tail->successors(); 2652 2653 if (!is_an_if) { 2654 assert(((wide ? iter.get_far_dest() : iter.get_dest()) == head()->start()) == (succs->at(ciTypeFlow::GOTO_TARGET) == head()), "branch should lead to loop head"); 2655 if (succs->at(ciTypeFlow::GOTO_TARGET) == head()) { 2656 _profiled_count = outer()->method()->scale_count(data->as_JumpData()->taken()); 2657 return _profiled_count; 2658 } 2659 } else { 2660 assert((iter.get_dest() == head()->start()) == (succs->at(ciTypeFlow::IF_TAKEN) == head()), "bytecode and CFG not consistent"); 2661 assert((tail->limit() == head()->start()) == (succs->at(ciTypeFlow::IF_NOT_TAKEN) == head()), "bytecode and CFG not consistent"); 2662 if (succs->at(ciTypeFlow::IF_TAKEN) == head()) { 2663 _profiled_count = outer()->method()->scale_count(data->as_JumpData()->taken()); 2664 return _profiled_count; 2665 } else if (succs->at(ciTypeFlow::IF_NOT_TAKEN) == head()) { 2666 _profiled_count = outer()->method()->scale_count(data->as_BranchData()->not_taken()); 2667 return _profiled_count; 2668 } 2669 } 2670 2671 _profiled_count = 0; 2672 return _profiled_count; 2673 } 2674 2675 bool ciTypeFlow::Loop::at_insertion_point(Loop* lp, Loop* current) { 2676 int lp_pre_order = lp->head()->pre_order(); 2677 if (current->head()->pre_order() < lp_pre_order) { 2678 return true; 2679 } else if (current->head()->pre_order() > lp_pre_order) { 2680 return false; 2681 } 2682 // In the case of a shared head, make the most frequent head/tail (as reported by profiling) the inner loop 2683 if (current->head() == lp->head()) { 2684 int lp_count = lp->profiled_count(); 2685 int current_count = current->profiled_count(); 2686 if (current_count < lp_count) { 2687 return true; 2688 } else if (current_count > lp_count) { 2689 return false; 2690 } 2691 } 2692 if (current->tail()->pre_order() > lp->tail()->pre_order()) { 2693 return true; 2694 } 2695 return false; 2696 } 2697 2698 // ------------------------------------------------------------------ 2699 // ciTypeFlow::Loop::sorted_merge 2700 // 2701 // Merge the branch lp into this branch, sorting on the loop head 2702 // pre_orders. Returns the leaf of the merged branch. 2703 // Child and sibling pointers will be setup later. 2704 // Sort is (looking from leaf towards the root) 2705 // descending on primary key: loop head's pre_order, and 2706 // ascending on secondary key: loop tail's pre_order. 2707 ciTypeFlow::Loop* ciTypeFlow::Loop::sorted_merge(Loop* lp) { 2708 Loop* leaf = this; 2709 Loop* prev = nullptr; 2710 Loop* current = leaf; 2711 while (lp != nullptr) { 2712 int lp_pre_order = lp->head()->pre_order(); 2713 // Find insertion point for "lp" 2714 while (current != nullptr) { 2715 if (current == lp) { 2716 return leaf; // Already in list 2717 } 2718 if (at_insertion_point(lp, current)) { 2719 break; 2720 } 2721 prev = current; 2722 current = current->parent(); 2723 } 2724 Loop* next_lp = lp->parent(); // Save future list of items to insert 2725 // Insert lp before current 2726 lp->set_parent(current); 2727 if (prev != nullptr) { 2728 prev->set_parent(lp); 2729 } else { 2730 leaf = lp; 2731 } 2732 prev = lp; // Inserted item is new prev[ious] 2733 lp = next_lp; // Next item to insert 2734 } 2735 return leaf; 2736 } 2737 2738 // ------------------------------------------------------------------ 2739 // ciTypeFlow::build_loop_tree 2740 // 2741 // Incrementally build loop tree. 2742 void ciTypeFlow::build_loop_tree(Block* blk) { 2743 assert(!blk->is_post_visited(), "precondition"); 2744 Loop* innermost = nullptr; // merge of loop tree branches over all successors 2745 2746 for (SuccIter iter(blk); !iter.done(); iter.next()) { 2747 Loop* lp = nullptr; 2748 Block* succ = iter.succ(); 2749 if (!succ->is_post_visited()) { 2750 // Found backedge since predecessor post visited, but successor is not 2751 assert(succ->pre_order() <= blk->pre_order(), "should be backedge"); 2752 2753 // Create a LoopNode to mark this loop. 2754 lp = new (arena()) Loop(succ, blk); 2755 if (succ->loop() == nullptr) 2756 succ->set_loop(lp); 2757 // succ->loop will be updated to innermost loop on a later call, when blk==succ 2758 2759 } else { // Nested loop 2760 lp = succ->loop(); 2761 2762 // If succ is loop head, find outer loop. 2763 while (lp != nullptr && lp->head() == succ) { 2764 lp = lp->parent(); 2765 } 2766 if (lp == nullptr) { 2767 // Infinite loop, it's parent is the root 2768 lp = loop_tree_root(); 2769 } 2770 } 2771 2772 // Check for irreducible loop. 2773 // Successor has already been visited. If the successor's loop head 2774 // has already been post-visited, then this is another entry into the loop. 2775 while (lp->head()->is_post_visited() && lp != loop_tree_root()) { 2776 _has_irreducible_entry = true; 2777 lp->set_irreducible(succ); 2778 if (!succ->is_on_work_list()) { 2779 // Assume irreducible entries need more data flow 2780 add_to_work_list(succ); 2781 } 2782 Loop* plp = lp->parent(); 2783 if (plp == nullptr) { 2784 // This only happens for some irreducible cases. The parent 2785 // will be updated during a later pass. 2786 break; 2787 } 2788 lp = plp; 2789 } 2790 2791 // Merge loop tree branch for all successors. 2792 innermost = innermost == nullptr ? lp : innermost->sorted_merge(lp); 2793 2794 } // end loop 2795 2796 if (innermost == nullptr) { 2797 assert(blk->successors()->length() == 0, "CFG exit"); 2798 blk->set_loop(loop_tree_root()); 2799 } else if (innermost->head() == blk) { 2800 // If loop header, complete the tree pointers 2801 if (blk->loop() != innermost) { 2802 #ifdef ASSERT 2803 assert(blk->loop()->head() == innermost->head(), "same head"); 2804 Loop* dl; 2805 for (dl = innermost; dl != nullptr && dl != blk->loop(); dl = dl->parent()); 2806 assert(dl == blk->loop(), "blk->loop() already in innermost list"); 2807 #endif 2808 blk->set_loop(innermost); 2809 } 2810 innermost->def_locals()->add(blk->def_locals()); 2811 Loop* l = innermost; 2812 Loop* p = l->parent(); 2813 while (p && l->head() == blk) { 2814 l->set_sibling(p->child()); // Put self on parents 'next child' 2815 p->set_child(l); // Make self the first child of parent 2816 p->def_locals()->add(l->def_locals()); 2817 l = p; // Walk up the parent chain 2818 p = l->parent(); 2819 } 2820 } else { 2821 blk->set_loop(innermost); 2822 innermost->def_locals()->add(blk->def_locals()); 2823 } 2824 } 2825 2826 // ------------------------------------------------------------------ 2827 // ciTypeFlow::Loop::contains 2828 // 2829 // Returns true if lp is nested loop. 2830 bool ciTypeFlow::Loop::contains(ciTypeFlow::Loop* lp) const { 2831 assert(lp != nullptr, ""); 2832 if (this == lp || head() == lp->head()) return true; 2833 int depth1 = depth(); 2834 int depth2 = lp->depth(); 2835 if (depth1 > depth2) 2836 return false; 2837 while (depth1 < depth2) { 2838 depth2--; 2839 lp = lp->parent(); 2840 } 2841 return this == lp; 2842 } 2843 2844 // ------------------------------------------------------------------ 2845 // ciTypeFlow::Loop::depth 2846 // 2847 // Loop depth 2848 int ciTypeFlow::Loop::depth() const { 2849 int dp = 0; 2850 for (Loop* lp = this->parent(); lp != nullptr; lp = lp->parent()) 2851 dp++; 2852 return dp; 2853 } 2854 2855 #ifndef PRODUCT 2856 // ------------------------------------------------------------------ 2857 // ciTypeFlow::Loop::print 2858 void ciTypeFlow::Loop::print(outputStream* st, int indent) const { 2859 for (int i = 0; i < indent; i++) st->print(" "); 2860 st->print("%d<-%d %s", 2861 is_root() ? 0 : this->head()->pre_order(), 2862 is_root() ? 0 : this->tail()->pre_order(), 2863 is_irreducible()?" irr":""); 2864 st->print(" defs: "); 2865 def_locals()->print_on(st, _head->outer()->method()->max_locals()); 2866 st->cr(); 2867 for (Loop* ch = child(); ch != nullptr; ch = ch->sibling()) 2868 ch->print(st, indent+2); 2869 } 2870 #endif 2871 2872 // ------------------------------------------------------------------ 2873 // ciTypeFlow::df_flow_types 2874 // 2875 // Perform the depth first type flow analysis. Helper for flow_types. 2876 void ciTypeFlow::df_flow_types(Block* start, 2877 bool do_flow, 2878 StateVector* temp_vector, 2879 JsrSet* temp_set) { 2880 int dft_len = 100; 2881 GrowableArray<Block*> stk(dft_len); 2882 2883 ciBlock* dummy = _method->get_method_blocks()->make_dummy_block(); 2884 JsrSet* root_set = new JsrSet(0); 2885 Block* root_head = new (arena()) Block(this, dummy, root_set); 2886 Block* root_tail = new (arena()) Block(this, dummy, root_set); 2887 root_head->set_pre_order(0); 2888 root_head->set_post_order(0); 2889 root_tail->set_pre_order(max_jint); 2890 root_tail->set_post_order(max_jint); 2891 set_loop_tree_root(new (arena()) Loop(root_head, root_tail)); 2892 2893 stk.push(start); 2894 2895 _next_pre_order = 0; // initialize pre_order counter 2896 _rpo_list = nullptr; 2897 int next_po = 0; // initialize post_order counter 2898 2899 // Compute RPO and the control flow graph 2900 int size; 2901 while ((size = stk.length()) > 0) { 2902 Block* blk = stk.top(); // Leave node on stack 2903 if (!blk->is_visited()) { 2904 // forward arc in graph 2905 assert (!blk->has_pre_order(), ""); 2906 blk->set_next_pre_order(); 2907 2908 if (_next_pre_order >= (int)Compile::current()->max_node_limit() / 2) { 2909 // Too many basic blocks. Bail out. 2910 // This can happen when try/finally constructs are nested to depth N, 2911 // and there is O(2**N) cloning of jsr bodies. See bug 4697245! 2912 // "MaxNodeLimit / 2" is used because probably the parser will 2913 // generate at least twice that many nodes and bail out. 2914 record_failure("too many basic blocks"); 2915 return; 2916 } 2917 if (do_flow) { 2918 flow_block(blk, temp_vector, temp_set); 2919 if (failing()) return; // Watch for bailouts. 2920 } 2921 } else if (!blk->is_post_visited()) { 2922 // cross or back arc 2923 for (SuccIter iter(blk); !iter.done(); iter.next()) { 2924 Block* succ = iter.succ(); 2925 if (!succ->is_visited()) { 2926 stk.push(succ); 2927 } 2928 } 2929 if (stk.length() == size) { 2930 // There were no additional children, post visit node now 2931 stk.pop(); // Remove node from stack 2932 2933 build_loop_tree(blk); 2934 blk->set_post_order(next_po++); // Assign post order 2935 prepend_to_rpo_list(blk); 2936 assert(blk->is_post_visited(), ""); 2937 2938 if (blk->is_loop_head() && !blk->is_on_work_list()) { 2939 // Assume loop heads need more data flow 2940 add_to_work_list(blk); 2941 } 2942 } 2943 } else { 2944 stk.pop(); // Remove post-visited node from stack 2945 } 2946 } 2947 } 2948 2949 // ------------------------------------------------------------------ 2950 // ciTypeFlow::flow_types 2951 // 2952 // Perform the type flow analysis, creating and cloning Blocks as 2953 // necessary. 2954 void ciTypeFlow::flow_types() { 2955 ResourceMark rm; 2956 StateVector* temp_vector = new StateVector(this); 2957 JsrSet* temp_set = new JsrSet(4); 2958 2959 // Create the method entry block. 2960 Block* start = block_at(start_bci(), temp_set); 2961 2962 // Load the initial state into it. 2963 const StateVector* start_state = get_start_state(); 2964 if (failing()) return; 2965 start->meet(start_state); 2966 2967 // Depth first visit 2968 df_flow_types(start, true /*do flow*/, temp_vector, temp_set); 2969 2970 if (failing()) return; 2971 assert(_rpo_list == start, "must be start"); 2972 2973 // Any loops found? 2974 if (loop_tree_root()->child() != nullptr && 2975 env()->comp_level() >= CompLevel_full_optimization) { 2976 // Loop optimizations are not performed on Tier1 compiles. 2977 2978 bool changed = clone_loop_heads(temp_vector, temp_set); 2979 2980 // If some loop heads were cloned, recompute postorder and loop tree 2981 if (changed) { 2982 loop_tree_root()->set_child(nullptr); 2983 for (Block* blk = _rpo_list; blk != nullptr;) { 2984 Block* next = blk->rpo_next(); 2985 blk->df_init(); 2986 blk = next; 2987 } 2988 df_flow_types(start, false /*no flow*/, temp_vector, temp_set); 2989 } 2990 } 2991 2992 if (CITraceTypeFlow) { 2993 tty->print_cr("\nLoop tree"); 2994 loop_tree_root()->print(); 2995 } 2996 2997 // Continue flow analysis until fixed point reached 2998 2999 debug_only(int max_block = _next_pre_order;) 3000 3001 while (!work_list_empty()) { 3002 Block* blk = work_list_next(); 3003 assert (blk->has_post_order(), "post order assigned above"); 3004 3005 flow_block(blk, temp_vector, temp_set); 3006 3007 assert (max_block == _next_pre_order, "no new blocks"); 3008 assert (!failing(), "no more bailouts"); 3009 } 3010 } 3011 3012 // ------------------------------------------------------------------ 3013 // ciTypeFlow::map_blocks 3014 // 3015 // Create the block map, which indexes blocks in reverse post-order. 3016 void ciTypeFlow::map_blocks() { 3017 assert(_block_map == nullptr, "single initialization"); 3018 int block_ct = _next_pre_order; 3019 _block_map = NEW_ARENA_ARRAY(arena(), Block*, block_ct); 3020 assert(block_ct == block_count(), ""); 3021 3022 Block* blk = _rpo_list; 3023 for (int m = 0; m < block_ct; m++) { 3024 int rpo = blk->rpo(); 3025 assert(rpo == m, "should be sequential"); 3026 _block_map[rpo] = blk; 3027 blk = blk->rpo_next(); 3028 } 3029 assert(blk == nullptr, "should be done"); 3030 3031 for (int j = 0; j < block_ct; j++) { 3032 assert(_block_map[j] != nullptr, "must not drop any blocks"); 3033 Block* block = _block_map[j]; 3034 // Remove dead blocks from successor lists: 3035 for (int e = 0; e <= 1; e++) { 3036 GrowableArray<Block*>* l = e? block->exceptions(): block->successors(); 3037 for (int k = 0; k < l->length(); k++) { 3038 Block* s = l->at(k); 3039 if (!s->has_post_order()) { 3040 if (CITraceTypeFlow) { 3041 tty->print("Removing dead %s successor of #%d: ", (e? "exceptional": "normal"), block->pre_order()); 3042 s->print_value_on(tty); 3043 tty->cr(); 3044 } 3045 l->remove(s); 3046 --k; 3047 } 3048 } 3049 } 3050 } 3051 } 3052 3053 // ------------------------------------------------------------------ 3054 // ciTypeFlow::get_block_for 3055 // 3056 // Find a block with this ciBlock which has a compatible JsrSet. 3057 // If no such block exists, create it, unless the option is no_create. 3058 // If the option is create_backedge_copy, always create a fresh backedge copy. 3059 ciTypeFlow::Block* ciTypeFlow::get_block_for(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs, CreateOption option) { 3060 Arena* a = arena(); 3061 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex]; 3062 if (blocks == nullptr) { 3063 // Query only? 3064 if (option == no_create) return nullptr; 3065 3066 // Allocate the growable array. 3067 blocks = new (a) GrowableArray<Block*>(a, 4, 0, nullptr); 3068 _idx_to_blocklist[ciBlockIndex] = blocks; 3069 } 3070 3071 if (option != create_backedge_copy) { 3072 int len = blocks->length(); 3073 for (int i = 0; i < len; i++) { 3074 Block* block = blocks->at(i); 3075 if (!block->is_backedge_copy() && block->is_compatible_with(jsrs)) { 3076 return block; 3077 } 3078 } 3079 } 3080 3081 // Query only? 3082 if (option == no_create) return nullptr; 3083 3084 // We did not find a compatible block. Create one. 3085 Block* new_block = new (a) Block(this, _method->get_method_blocks()->block(ciBlockIndex), jsrs); 3086 if (option == create_backedge_copy) new_block->set_backedge_copy(true); 3087 blocks->append(new_block); 3088 return new_block; 3089 } 3090 3091 // ------------------------------------------------------------------ 3092 // ciTypeFlow::backedge_copy_count 3093 // 3094 int ciTypeFlow::backedge_copy_count(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs) const { 3095 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex]; 3096 3097 if (blocks == nullptr) { 3098 return 0; 3099 } 3100 3101 int count = 0; 3102 int len = blocks->length(); 3103 for (int i = 0; i < len; i++) { 3104 Block* block = blocks->at(i); 3105 if (block->is_backedge_copy() && block->is_compatible_with(jsrs)) { 3106 count++; 3107 } 3108 } 3109 3110 return count; 3111 } 3112 3113 // ------------------------------------------------------------------ 3114 // ciTypeFlow::do_flow 3115 // 3116 // Perform type inference flow analysis. 3117 void ciTypeFlow::do_flow() { 3118 if (CITraceTypeFlow) { 3119 tty->print_cr("\nPerforming flow analysis on method"); 3120 method()->print(); 3121 if (is_osr_flow()) tty->print(" at OSR bci %d", start_bci()); 3122 tty->cr(); 3123 method()->print_codes(); 3124 } 3125 if (CITraceTypeFlow) { 3126 tty->print_cr("Initial CI Blocks"); 3127 print_on(tty); 3128 } 3129 flow_types(); 3130 // Watch for bailouts. 3131 if (failing()) { 3132 return; 3133 } 3134 3135 map_blocks(); 3136 3137 if (CIPrintTypeFlow || CITraceTypeFlow) { 3138 rpo_print_on(tty); 3139 } 3140 } 3141 3142 // ------------------------------------------------------------------ 3143 // ciTypeFlow::is_dominated_by 3144 // 3145 // Determine if the instruction at bci is dominated by the instruction at dom_bci. 3146 bool ciTypeFlow::is_dominated_by(int bci, int dom_bci) { 3147 assert(!method()->has_jsrs(), "jsrs are not supported"); 3148 3149 ResourceMark rm; 3150 JsrSet* jsrs = new ciTypeFlow::JsrSet(); 3151 int index = _method->get_method_blocks()->block_containing(bci)->index(); 3152 int dom_index = _method->get_method_blocks()->block_containing(dom_bci)->index(); 3153 Block* block = get_block_for(index, jsrs, ciTypeFlow::no_create); 3154 Block* dom_block = get_block_for(dom_index, jsrs, ciTypeFlow::no_create); 3155 3156 // Start block dominates all other blocks 3157 if (start_block()->rpo() == dom_block->rpo()) { 3158 return true; 3159 } 3160 3161 // Dominated[i] is true if block i is dominated by dom_block 3162 int num_blocks = block_count(); 3163 bool* dominated = NEW_RESOURCE_ARRAY(bool, num_blocks); 3164 for (int i = 0; i < num_blocks; ++i) { 3165 dominated[i] = true; 3166 } 3167 dominated[start_block()->rpo()] = false; 3168 3169 // Iterative dominator algorithm 3170 bool changed = true; 3171 while (changed) { 3172 changed = false; 3173 // Use reverse postorder iteration 3174 for (Block* blk = _rpo_list; blk != nullptr; blk = blk->rpo_next()) { 3175 if (blk->is_start()) { 3176 // Ignore start block 3177 continue; 3178 } 3179 // The block is dominated if it is the dominating block 3180 // itself or if all predecessors are dominated. 3181 int index = blk->rpo(); 3182 bool dom = (index == dom_block->rpo()); 3183 if (!dom) { 3184 // Check if all predecessors are dominated 3185 dom = true; 3186 for (int i = 0; i < blk->predecessors()->length(); ++i) { 3187 Block* pred = blk->predecessors()->at(i); 3188 if (!dominated[pred->rpo()]) { 3189 dom = false; 3190 break; 3191 } 3192 } 3193 } 3194 // Update dominator information 3195 if (dominated[index] != dom) { 3196 changed = true; 3197 dominated[index] = dom; 3198 } 3199 } 3200 } 3201 // block dominated by dom_block? 3202 return dominated[block->rpo()]; 3203 } 3204 3205 // ------------------------------------------------------------------ 3206 // ciTypeFlow::record_failure() 3207 // The ciTypeFlow object keeps track of failure reasons separately from the ciEnv. 3208 // This is required because there is not a 1-1 relation between the ciEnv and 3209 // the TypeFlow passes within a compilation task. For example, if the compiler 3210 // is considering inlining a method, it will request a TypeFlow. If that fails, 3211 // the compilation as a whole may continue without the inlining. Some TypeFlow 3212 // requests are not optional; if they fail the requestor is responsible for 3213 // copying the failure reason up to the ciEnv. (See Parse::Parse.) 3214 void ciTypeFlow::record_failure(const char* reason) { 3215 if (env()->log() != nullptr) { 3216 env()->log()->elem("failure reason='%s' phase='typeflow'", reason); 3217 } 3218 if (_failure_reason == nullptr) { 3219 // Record the first failure reason. 3220 _failure_reason = reason; 3221 } 3222 } 3223 3224 ciType* ciTypeFlow::mark_as_null_free(ciType* type) { 3225 // Wrap the type to carry the information that it is null-free 3226 return env()->make_null_free_wrapper(type); 3227 } 3228 3229 #ifndef PRODUCT 3230 void ciTypeFlow::print() const { print_on(tty); } 3231 3232 // ------------------------------------------------------------------ 3233 // ciTypeFlow::print_on 3234 void ciTypeFlow::print_on(outputStream* st) const { 3235 // Walk through CI blocks 3236 st->print_cr("********************************************************"); 3237 st->print ("TypeFlow for "); 3238 method()->name()->print_symbol_on(st); 3239 int limit_bci = code_size(); 3240 st->print_cr(" %d bytes", limit_bci); 3241 ciMethodBlocks* mblks = _method->get_method_blocks(); 3242 ciBlock* current = nullptr; 3243 for (int bci = 0; bci < limit_bci; bci++) { 3244 ciBlock* blk = mblks->block_containing(bci); 3245 if (blk != nullptr && blk != current) { 3246 current = blk; 3247 current->print_on(st); 3248 3249 GrowableArray<Block*>* blocks = _idx_to_blocklist[blk->index()]; 3250 int num_blocks = (blocks == nullptr) ? 0 : blocks->length(); 3251 3252 if (num_blocks == 0) { 3253 st->print_cr(" No Blocks"); 3254 } else { 3255 for (int i = 0; i < num_blocks; i++) { 3256 Block* block = blocks->at(i); 3257 block->print_on(st); 3258 } 3259 } 3260 st->print_cr("--------------------------------------------------------"); 3261 st->cr(); 3262 } 3263 } 3264 st->print_cr("********************************************************"); 3265 st->cr(); 3266 } 3267 3268 void ciTypeFlow::rpo_print_on(outputStream* st) const { 3269 st->print_cr("********************************************************"); 3270 st->print ("TypeFlow for "); 3271 method()->name()->print_symbol_on(st); 3272 int limit_bci = code_size(); 3273 st->print_cr(" %d bytes", limit_bci); 3274 for (Block* blk = _rpo_list; blk != nullptr; blk = blk->rpo_next()) { 3275 blk->print_on(st); 3276 st->print_cr("--------------------------------------------------------"); 3277 st->cr(); 3278 } 3279 st->print_cr("********************************************************"); 3280 st->cr(); 3281 } 3282 #endif